Nghiên cứu và đánh giá phương pháp giải mã ldpc năm 2024

Bài báo trình bày việc giải mã mềm sử dụng thuật toán BPA-EH cải tiến cho mã kiểm tra chẵn lẻ mật độ thấp LDPC dựa trên các ma trận kiểm tra tương đương nhằm khắc phục vấn đề vòng kín ngắn trong mã LDPC. Phương pháp này không những cho phép giảm đáng kể thời gian giải mã so với kỹ thuật giải mã BPA-EH mà còn mang lại độ lợi mã hóa cao hơn.

• 1. VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ - HÀ THỊ KIM THOA NGHIÊN CỨU CẢI THIỆN CHẤT LƯỢNG MÃ LDPC LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI - 2014
• 2. VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ - HÀ THỊ KIM THOA NGHIÊN CỨU CẢI THIỆN CHẤT LƯỢNG MÃ LDPC LUẬN ÁN TIẾN SĨ KỸ THUẬT Chuyên ngành : KỸ THUẬT ĐIỆN TỬ Mã số : 62 52 02 03 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS-TS ĐINH THẾ CƯỜNG HÀ NỘI - 2014
• 3. xin cam đoan các kết quả trình bày trong luận án là công trình nghiên cứu của tôi dưới sự hướng dẫn của cán bộ hướng dẫn. Các số liệu, kết quả trình bày trong luận án là hoàn toàn trung thực và chưa được công bố trong bất kỳ công trình nào trước đây. Các kết quả sử dụng tham khảo đều đã được trích dẫn đầy đủ và theo đúng quy định. Hà Nội, ngày 04 tháng 04 năm 2014 Tác giả Hà Thị Kim Thoa
• 4. quá trình nghiên cứu và hoàn thành luận án này, tác giả đã nhận được nhiều sự giúp đỡ và đóng góp quý báu. Đầu tiên, tác giả xin bày tỏ lòng cảm ơn tới thầy giáo hướng dẫn PGS. TS. Đinh Thế Cường đã tận tình hướng dẫn và giúp đỡ tác giả trong quá trình nghiên cứu. Tác giả xin chân thành cảm ơn Phòng Sau Đại học, Bộ môn Thông tin, Khoa Vô tuyến Điện tử, Học viện Kỹ thuật Quân sự đã tạo điều kiện thuận lợi để tác giả hoàn thành nhiệm vụ. Tác giả cũng xin cảm ơn Cục Tần số vô tuyến điện, là đơn vị chủ quản, đã tạo điều kiện cho phép tác giả có thể tham gia nghiên cứu trong các năm làm nghiên cứu sinh. Cuối cùng, tác giả xin bày tỏ lòng cảm ơn đến gia đình, bạn bè, các đồng nghiệp đã luôn động viên, giúp đỡ tác giả vượt qua khó khăn để đạt được những kết quả nghiên cứu như ngày hôm nay. TÁC GIẢ
• 5. BÌA LỜI CAM ĐOAN................................................................................................... i LỜI CẢM ƠN........................................................................................................ ii MỤC LỤC ............................................................................................................iii DANH MỤC CÁC TỪ VIẾT TẮT....................................................................... v DANH MỤC HÌNH VẼ .....................................................................................viii DANH MỤC KÝ HIỆU TOÁN HỌC.................................................................. xi MỞ ĐẦU ............................................................................................................... 1 Chương 1: TỔNG QUAN...................................................................................... 9 1.1 Giới hạn Shannon ........................................................................................ 9 1.1.1 Lượng tin.............................................................................................. 11 1.1.2 Entropy ................................................................................................. 12 1.1.3 Kênh thông tin...................................................................................... 13 1.1.4 Lượng tin tương hỗ............................................................................... 15 1.1.5 Dung lượng kênh rời rạc....................................................................... 15 1.1.6 Lý thuyết về mã kênh ........................................................................... 15 1.2 Mã LDPC................................................................................................... 17 1.2.1 Sự phát triển của các kỹ thuật mã kênh nhằm đạt giới hạn Shannon ... 17 1.2.2 Quá trình phát triển của mã LDPC...................................................... 19 1.2.3 Cơ bản về mã LDPC............................................................................. 21 1.2.4 Đặc điểm của mã LDPC...................................................................... 25 1.3 Sơ đồ BICM-ID truyền thống.................................................................... 26 1.4 Đặt vấn đề nghiên cứu................................................................................ 32 Chương 2: SƠ ĐỒ KẾT HỢP LDPC VÀ BICM-ID........................................... 35 2.1 Sơ đồ khối hệ thống điều chế mã LDPC .................................................... 35 2.2 Cải tiến thuật toán giải mã SPA................................................................. 37
• 6. mã cứng.................................................................................... 37 2.2.2 Giải mã mềm: Thuật toán tổng-tích SPA ............................................. 39 2.2.3 Thuật toán giải mã SPA trong miền Log.............................................. 47 2.2.4 Các thuật toán xấp xỉ............................................................................ 51 2.2.5 Cải tiến thuật toán SPA ....................................................................... 51 2.2.6 Giảm sự ảnh hưởng của sai số ước lượng kênh tới chất lượng thuật toán giải mã SPA................................................................................................... 57 2.3 Xây dựng sơ đồ mô phỏng hệ thống BILCM-ID........................................ 60 2.3.1 Mã hóa LDPC....................................................................................... 60 2.3.2 Hệ thống BILCM-ID có trộn bít........................................................... 63 2.4 Kết luận chương ......................................................................................... 67 Chương 3: ĐIỀU CHẾ MÃ LDPC DỰA TRÊN ĐỘ TIN CẬY CỦA CÁC BÍT MÃ....................................................................................................................... 69 3.1 Xây dựng bộ hoán vị dựa trên độ tin cậy của các bít mã............................ 69 3.2 Kết quả mô phỏng hệ thống BILCM-ID với tín hiệu đa mức .................... 75 3.3 Kết quả mô phỏng hệ thống BILCM-ID với tín hiệu đa chiều.................. 80 3.4 Kết luận chương ......................................................................................... 90 KẾT LUẬN ......................................................................................................... 91 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ ........................................... 94 TÀI LIỆU THAM KHẢO ................................................................................... 95
• 7. TỪ VIẾT TẮT Từ viết tắt Nghĩa tiếng Anh Nghĩa Tiếng Việt APP A Posteriori Probability Xác suất hậu nghiệm AWGN Additive White Gaussian Noise Tạp âm Gao-xơ trắng cộng tính BCH Bose, Chaudhuri and Hocquenghem Mã BCH BEC Binary Erasure Channel Kênh xóa nhị phân BER Bit Error Rate Tỉ lệ lỗi bít BICM-ID Bit Interleaved Coded Modulation with Iterative Decoding Điều chế mã có hoán vị bit và giải mã lặp BILCM-ID Bit-Interleaved LDPC Coded Modulation with Iterative Decoding Hệ thống điều chế mã kiểm tra mật độ thấp có hoán vị bít và giải mã lặp BPSK Binary Phase Shift Keying Khóa dịch pha nhị phân BP Belief Propogation Lan truyền niềm tin BS Binary Source Nguồn nhị phân BSC Binary Symmetric Channel Kênh nhị phân đối xứng CM Coded Modulation Điều chế mã
• 8. Source Nguồn không nhớ rời rạc DVB-S2 Digital Video Broadcasting – Satellite – Second Generation Truyền hình số - Vệ tinh Thế hệ thứ hai FEC Forward Error Correction Sửa lỗi hướng đi FER Frame Error Rate Tỷ lệ lỗi khung GF Galois Field Trường Galois MLC Multi-Level Coding Mã đa mức MLD Maximum Likelihood Decoding Giải mã hợp lẽ cực đại LDPC Low-Density Parity-Check Code Mã kiểm tra mật độ thấp OSP Order Statistic Decoding Giải mã bậc thống kê PCCC Parallel Concatenated Convolutional Codes Mã chập liên kết song song (Mã Turbo) PSK Phase Shift Keying Khóa dịch pha QAM Quadrature Amplitude Modulation Điều chế cầu phương RA Repeat Accumulate Tích lũy lặp RBCM Reliability Based Coded Modulation Điều chế mã dựa trên độ tin cậy RS Reed - Solomon Mã Reed - Solomon
• 9. Codes Mã chập liên kết nối tiếp SER Symbol Error Rate Tỷ lệ lỗi ký hiệu SF Scale Factor Hệ số hiệu chỉnh SISO Soft Input Soft Output Đầu vào mềm Đầu ra mềm SNR Signal to Noise Ratio Tỉ số công suất tín hiệu trên tạp âm SPA Sum-Product Algorithm Thuật toán tổng-tích SP Set Partitioning Phân hoạch tập SSP Semi-Set Partitioning Bán phân hoạch tập TCM Trellis Coded Modulation Điều chế mã lưới TG Tanner Graph Đồ hình Tanner VA Viterbi Algorithm Thuật toán Viterbi 4G 4th Generation Thế hệ thứ tư
• 10. VẼ Hình 1-1. Sơ đồ khối hệ thống thông tin số đơn giản.......................................... 11 Hình 1-2. Kênh nhị phân đối xứng ...................................................................... 13 Hình 1-3. Kênh xóa nhị phân............................................................................... 14 Hình 1-4. Kênh Gao-xơ ....................................................................................... 16 Hình 1-5. Biểu diễn ma trận và biểu diễn đồ hình Tanner của mã LDPC........... 24 Hình 1-6. Vòng kín chiều dài 4 trong ma trận kiểm tra....................................... 25 Hình 1-7. Sơ đồ khối hệ thống BICM-ID........................................................... 27 Hình 1-8. Nguyên lý giải mã cứng (a) và giải mã mềm (b)................................. 28 Hình 1-9. Phẩm chất hệ thống BICM-ID phụ thuộc vào kiểu ánh xạ.................. 31 Hình 2-1. Sơ đồ khối hệ thống............................................................................. 36 Hình 2-2. Cây kiểm tra trên đồ hình Tanner........................................................ 38 Hình 2-3. Tập con của đồ hình Tanner. (a) Hình cây với i c là gốc. (b) Phần thực tế của đồ hình Tanner với i c là nút gốc. ............................................................. 41 Hình 2-4. Cây hai tầng......................................................................................... 44 Hình 2-5. Độc lập có điều kiện giữa tập các bít................................................... 48 Hình 2-6. Kết quả khảo sát ảnh hưởng của hệ số SF đối với mã LDPC dài 240 bít, 0 / b E N =2,0 dB...................................................................................................... 53 Hình 2-7. Kết quả khảo sát ảnh hưởng của hệ số SF đối với mã LDPC dài 240 bít, 0 / b E N =3,0 dB...................................................................................................... 53 Hình 2-8. Kết quả khảo sát ảnh hưởng của hệ số SF đối với mã LDPC dài 480 bít, 0 / b E N =2,0 dB...................................................................................................... 54 Hình 2-9. Kết quả khảo sát ảnh hưởng của hệ số SF đối với mã LDPC dài 480 bít, 0 / b E N =2,5 dB...................................................................................................... 55
• 11. sánh chất lượng hệ thống BILCM-ID với ánh xạ Gray khi SF=1 và SF =0,9................................................................................................................. 55 Hình 2-11. So sánh chất lượng hệ thống BILCM-ID với ánh xạ SP khi SF=1 và SF =0,9................................................................................................................. 56 Hình 2-12. Ảnh hưởng của sai số ước lượng tỷ lệ tín trên tạp (SF=1) ............... 57 Hình 2-13. Ảnh hưởng của sai số ước lượng tỷ lệ tín trên tạp (SF=0,9) ............. 58 Hình 2-14. Ảnh hưởng của sai số ước lượng tỷ lệ tín trên tạp (SF=0,8) ............. 58 Hình 2-15. Ảnh hưởng của sai số ước lượng tỷ lệ tín trên tạp (SF=0,7) ............. 59 Hình 2-16. Kết quả sau khi hoán vị các hàng và cột. .......................................... 61 Hình 2-17. Sơ đồ khối hệ thống mã LDPC có trộn bít ........................................ 65 Hình 2-18. So sánh kết quả mô phỏng giữa phương pháp cũ và mới.................. 66 Hình 3-1. Mối quan hệ mã hóa-ánh xạ-điều chế.................................................. 73 Hình 3-2. Độ tin cậy của các bít mã của mã LDPC tỷ lệ 1/2, chiều dài 240 bít.. 74 Hình 3-3. Kết quả mô phỏng mã LDPC tỷ lệ 1/2 với điều chế BPSK................. 74 Hình 3-4. Kết quả mô phỏng mã LDPC tỷ lệ 1/2 với điều chế 4PSK ................. 76 Hình 3-5. Kết quả mô phỏng mã LDPC tỷ lệ 1/2 với điều chế 8PSK ................. 77 Hình 3-6. Kết quả mô phỏng mã LDPC tỷ lệ 1/2 với điều chế 16QAM ............. 78 Hình 3-7. So sánh phẩm chất của hệ thống BLCM-ID khi sử dụng bộ hoán vị mới với khi dùng hoán vị ngẫu nhiên.......................................................................... 78 Hình 3-8. So sánh hoán vị trong một từ mã với hoán vị trong nhiều từ mã. ....... 79 Hình 3-9. Các ánh xạ của tín hiệu 2 chiều (2D). ................................................. 81 Hình 3-10. Các ánh xạ của tín hiệu 3 chiều (3D). ............................................... 81 Hình 3-11. Ma trận kiểm tra và đồ hình Tanner của mã LDPC (8,4).................. 83 Hình 3-12. Kết quả mô phỏng cho mã LDPC (8,4), điều chế 2D........................ 84 Hình 3-13. Kết quả mô phỏng cho mã LDPC(20,10), điều chế 2D..................... 85 Hình 3-14. Kết quả mô phỏng cho mã LDPC (256, 128), điều chế 2D và 4D.... 86 Hình 3-15. Kết quả mô phỏng cho mã LDPC (240, 120), điều chế 2D và 3D.... 86
• 12. quả mô phỏng mã LDPC (480, 240), điều chế 2D và 3D........... 87 Hình 3-17. Kết quả mô phỏng mã LDPC (960,480), điều chế 2D và 3D............ 88 Hình 3-18. Kết quả mô phỏng mã LDPC(1920,960), điều chế 2D và 3D........... 89
• 13. HIỆU TOÁN HỌC Ký hiệu Ý nghĩa Ví dụ Chữ thường, in nghiêng Biến số x Chữ thường, in đứng, đậm Véc-tơ chứa các biến số a Chữ hoa, in nghiêng, đậm Ma trận chứa các biến số A n Chiều dài từ mã k Số bít tin Q Số lần lặp i c Chuỗi cơ sở i r Chuỗi thu ( ) i P x Xác suất bản tin i x được phát đi , m i z Phép kiểm tra được tính cho các bít liên quan nút kiểm tra m, trừ i c , m i “bản tin” được truyền từ nút kiểm tra m tới nút bít i ( )  i c Tỷ lệ hợp lẽ của i c b E Năng lượng của bit
• 14. Xác suất hậu nghiệm của bít ( ) mi r x Xác suất phép kiểm tra được thỏa mãn ( ) m i q x Xác suất giả hậu nghiệm của bít  Hằng số chuẩn hóa 2  Phương sai nhiễu ( ) i p x Xác suất hậu nghiệm của kênh c L Độ tin cậy của kênh ( ) O N Bậc N
• 15. ngày đầu truyền thông kỹ thuật số ra đời, ưu thế lớn nhất của tín hiệu số so với truyền thông tương tự truyền thống không phải là tốc độ dữ liệu mà chính là khả năng sử dụng mã hóa sửa sai của tín hiệu số. Mã kênh được sử dụng để nâng cao độ tin cậy của các hệ thống thông tin. Người đặt nền móng cho các nghiên cứu về mã kênh, C. E. Shannon [57] đã đưa ra các cơ sở toán học là các cận lý thuyết cho việc xây dựng các bộ mã kênh. Tuy lý thuyết Shannon không trực tiếp chỉ ra cách tạo các bộ mã tối ưu có thể đạt được giới hạn đó nhưng trên thực tế thì các bộ mã hoá, giải mã đơn giản, dễ chế tạo vẫn được ứng dụng rộng rãi trong các hệ thống truyền tin và lưu giữ thông tin. Các nhà nghiên cứu về mã kênh đã không ngừng nghiên cứu, tìm ra các loại mã kênh vừa đạt chất lượng tốt vừa có tính ứng dụng cao. Tới nay, đã có nhiều bộ mã kênh được sử dụng hiệu quả trong các hệ thống thông tin số, trong đó có mã kiểm tra mật độ thấp LDPC (Low Density Parity Check) được R. G. Gallager đề xuất lần đầu tiên vào năm 1962 [21]. Trong vòng 30 năm sau đó mã LDPC bị các nhà nghiên cứu lãng quên và chỉ đến khi xuất hiện các mã Turbo vào năm 1993[37], các mã LDPC mới được tái phát hiện nhờ chất lượng của chúng rất gần giới hạn Shannon (tương tự như các mã Turbo). Ngoài ra, các mã LDPC có ba phẩm chất vượt trội so với các mã Turbo: (1) Giải mã song song có độ phức tạp tính toán thấp hơn các mã Turbo; (2) Trên thực nghiệm tất cả các lỗi đều được phát hiện mặc dù chưa được chứng minh bằng lý thuyết; và (3) Các mã LDPC có các phương pháp giải mã đơn giản hơn. Do vậy, các mã LDPC nổi lên như là ứng cử viên triển vọng cho các hệ thống mã sửa lỗi hướng đi (FEC) và được chấp nhận bởi nhiều tiêu chuẩn tiên tiến như Ethernet 10 Gigabit (10GBASET) [67] và
• 16. (DVB-S2) [68]. Ngoài ra, các thế hệ thông tin tiếp theo của Wifi và WiMAX đang xem xét các mã LDPC là một bộ phận của hệ thống mã sửa lỗi [66]. Tuy nhiên, bên cạnh các ưu điểm nổi trội nêu trên, các mã LDPC cũng tồn tại các hạn chế. Thứ nhất, các mã có chất lượng tốt nhất là các mã rất dài (như đã được tiên đoán trong lý thuyết mã kênh). Các chiều dài khối lớn, kèm theo giải mã lặp dẫn đến khó chấp nhận trong nhiều ứng dụng. Thứ hai, ma trận sinh G không nhất thiết là ma trận thưa nên việc mã hoá theo ma trận sinh có độ phức tạp tỷ lệ với bình phương chiều dài mã. Các mã LDPC được biểu diễn bằng đồ hình đôi gọi là đồ hình Tanner [59], và mầm (girth) của đồ hình Tanner là chiều dài của vòng kín ngắn nhất trên đồ hình. Các mầm của đồ hình Tanner của các mã LDPC cản trở tính hội tụ của thuật toán tổng-tích [40]. Hơn nữa, các vòng kín, đặc biệt các vòng kín ngắn, làm suy giảm chất lượng của các bộ giải mã LDPC vì chúng ảnh hưởng tới tính độc lập của các thông tin trao đổi (extrinsic information) giữa các vòng lặp giải mã. Người ta mong muốn xây dựng các mã LDPC có các mầm lớn, nhưng điều này dẫn đến sự phức tạp về cấu trúc của các ma trận kiểm tra. Với các đặc điểm nêu trên, trong thời gian qua các mã LDPC đã nhận được rất nhiều sự quan tâm nghiên cứu trên thế giới. Với mục đích đi sâu nghiên cứu các mã LDPC, tìm các biện pháp nhằm nâng cao chất lượng mã, nghiên cứu sinh đã chọn đề tài của luận án là “Nghiên cứu cải thiện chất lượng mã LDPC”. Trước kia, trong hệ thống thông tin số, bộ mã hoá kênh và bộ điều chế là các thành phần tách biệt và hoạt động một cách độc lập. Năm 1974, Masey nghiên cứu và đề xuất sơ đồ hệ thống kết hợp giữa sử dụng mã kênh với điều chế nhiều mức cho phép tối ưu hoá cả bộ mã kênh và bộ điều chế, qua đó cải thiện hiệu quả của hệ thống [43]. Hệ thống như vậy được gọi là hệ thống điều
• 17. (Coded Modulation) mà ngày nay được sử dụng một cách rộng rãi, đặc biệt trong hệ thống thông tin số có băng thông giới hạn [22], [47]. Một số hệ thống điều chế mã đã được phát triển như hệ thống điều chế mã đa mức MLC (Multi-Level Coding) [62], kỹ thuật điều chế mã lưới TCM (Trellis Coded Modulation) [19], và gần đây nhất là điều chế mã có hoán vị bit và giải mã lặp BICM-ID (Bit Interleaved Coded Modulation with Iterative Decoding) [18]. Trong hệ thống BICM-ID truyền thống, mã chập đóng vai trò mã vòng ngoài. Như một phát triển lô-gíc, mã LDPC cũng đã được đề xuất sử dụng trong sơ đồ điều chế mã có hoán vị bít và giải mã lặp, gọi là BILCM-ID. Luận án đặt vấn đề nghiên cứu phương pháp điều chế mã thích hợp để cải thiện chất lượng hệ thống BILCM-ID. Hướng nghiên cứu của Luận án được mô tả như sau. Một trong những lý do làm cho mã LDPC bị lãng quên trong suốt hơn 30 năm là do độ phức tạp giải mã hợp lẽ cực đại (MLD-Maximum Likelihood Decoding) đối với mã LDPC tăng theo hàm mũ của chiều dài từ mã. Sau khi mã turbo được phát hiện cùng với ứng dụng của giải mã lặp, trên thực tế người ta cũng áp dụng phương pháp cận tối ưu là giải mã lặp cho mã LDPC với giải thuật Lan truyền niềm tin (BP-Belief Propogation) [41], [58], [53] hoặc cực tiểu - tổng MS (Min-Sum) [15]. Về lý thuyết, giải mã lặp đối với mã LDPC cho phép tiệm cận chất lượng giải mã hợp lẽ cực đại, nhưng với điều kiện từ mã rất dài và mã thực sự ngẫu nhiên. Trên thực tế, với chiều dài từ mã chấp nhận được trong các ứng dụng truyền tin và các ma trận kiểm tra chẵn lẻ được thiết kế bằng phương pháp đại số [58] không hoàn toàn ngẫu nhiên thì chất lượng giải mã lặp chưa đạt chất lượng của giải mã MLD. Hơn nữa, do tồn tại các tập bẫy lỗi (Trapping Sets) [52], [56], có thể là ở dạng các vòng ngắn (Short Cycles) trong đồ hình Tanner [38], [59], đường cong tỷ lệ lỗi bít (BER-Bit Error Rate) của giải mã lặp có hiện tượng “sàn lỗi” (Error floor)
• 18. đặt ra là các cải tiến nhằm cải thiện chất lượng giải mã lặp theo hướng tiệm cận MLD liệu có giải quyết được vấn đề sàn lỗi. Để đưa chất lượng giải mã lặp đối với mã LDPC tiệm cận tới chất lượng giải mã hợp lẽ cực đại (MLD), các nhà nghiên cứu đã phát triển ý tưởng kết hợp Giải mã theo bậc thống kê OSD (Order Statistic Decoding) [16] dựa trên độ tin cậy của bít mã [17] với giải mã BP, thành phương pháp tái xử lý BP-OSD [28]. Tại một vòng lặp nào đó trong quá trình giải mã BP, nếu không giải ra được từ mã hợp lệ thì sẽ tính độ tin cậy của các thông tin về bít mã, lấy đó làm đầu vào cho giải mã OSD để xác định xem liệu có cần thêm một vòng lặp nữa hay không. BP-OSD cho chất lượng giải mã gần với MLD, nhưng độ phức tạp tăng nhanh cùng chiều dài từ mã. Việc kết hợp giải mã lặp với xử lý thống kê dựa trên độ tin cậy của bít mã giúp cho chất lượng giải mã tiến tới giải mã MLD, nhưng không giải quyết được vấn đề sàn lỗi. Luận án đặt vấn đề nghiên cứu kết hợp nguyên lý điều chế mã dựa trên độ tin cậy (RBCM- Reliability Based Coded Modulation) [42] với sơ đồ BICM-ID [35] để hạ thấp sàn lỗi của mã LDPC khi sử dụng điều chế đa mức như khóa dịch pha MPSK (M-ary Phase Shift Keying) và điều chế cầu phương MQAM (M-ary Quadrature Amplitude Modulation). Khác với [52] nghiên cứu xác định các tập bẫy lỗi của mã LDPC để đánh giá ảnh hưởng và tìm cách loại bỏ chúng, luận án đề xuất ghép vào cùng một tín hiệu các bít có độ tin cậy cao hơn với các bít có độ tin cậy thấp hơn (do thuộc cùng tập bẫy lỗi nào đó, ví dụ như nằm trong vòng kín ngắn). Cụ thể, sơ đồ BICM-ID cho phép tạo ra các kênh nhị phân song song tương đương với độ tin cậy khác nhau. Về bản chất, các bít mã hóa chập trong sơ đồ BICM-ID truyền thống thể hiện một đường qua lưới mã nên bộ hoán vị vừa cho phép tạo tính độc lập tương đối của các bít trong cùng một tín hiệu, vừa đảm bảo bít có độ tin cậy cao hơn được truyền qua kênh tin cậy hơn. Khi giải mã BICM-ID, bít thu
• 19. tin cậy cao sẽ hỗ trợ thông tin để giải mã bít thu được với độ tin cậy thấp hơn. Với mã LDPC, các bít mã vốn đã khá độc lập nhờ ma trận kiểm tra rất thưa nên vai trò của bộ hoán vị lúc này rút gọn lại chỉ là sắp xếp các bít mã như một phép ánh xạ trước khi điều chế [36]. Các nghiên cứu trước đây về RBCM [36, 42] dùng ánh xạ Gray với 8PSK cho phép cải thiện chất lượng giải mã khoảng 0,2~0,3 dB trên toàn dải tỷ lệ tín trên tạp (SNR-Signal to Noise Ratio), không phải là hướng tới giải quyết vấn đề sàn lỗi. Luận án đề xuất sử dụng ánh xạ phân hoạch tập, tạo ra các kênh nhị phân song song có độ tin cậy khác biệt nhằm hạ thấp sàn lỗi trong khi chấp nhận có thể có chất lượng giải mã kém hơn ở vùng SNR nhỏ. Ngoài ra, như đã nêu ở trên, các mã LDPC được giải mã bằng thuật toán Lan truyền niềm tin BP [41] hay một dạng của nó là thuật toán tổng-tích SPA (Sum-Product Algorithm). Về mặt lý thuyết, thuật toán SPA sẽ tối ưu nếu ma trận kiểm tra của mã hay đồ hình Tanner không có các vòng kín, đặc biệt là các vòng kín ngắn [60]. Việc tồn tại các vòng kín ngắn này là một thách thức lớn đối với các nhà nghiên cứu mã LDPC. Chưa có phương pháp mã hoá nào đảm bảo loại bỏ hoàn toàn các vòng kín này. Vì vậy, thực tế vẫn tồn tại các vòng kín ngắn trên đồ hình Tanner. Do đó, thuật toán SPA không phải là tối ưu với các chiều dài từ mã ngắn và trung bình. Hơn nữa, phần cứng để thực hiện thuật toán SPA bị giới hạn bởi độ phức tạp tính toán. Có một số cải tiến của thuật toán SPA được giới thiệu trong [15], [14]. M. Fossorier đề xuất phương pháp xấp xỉ cực tiểu-tổng [15]. So sánh với thuật toán SPA, thuật toán cực tiểu-tổng (Min-Sum Algorithm) giảm độ phức tạp tính toán đi rất nhiều nhưng kết quả là chất lượng giảm đi từ 0,5 đến 1 dB. Để cải thiện chất lượng thuật toán cực tiểu-tổng, một số cải tiến của thuật toán này đã được nghiên cứu và đề xuất với việc sử dụng hệ số hiệu chỉnh [69]. Như vậy, trên thế giới mới chỉ có các nghiên cứu về việc giảm độ phức tạp thuật toán
• 20. chưa có nghiên cứu cải thiện chất lượng thuật toán này. Việc cải tiến chất lượng thuật toán SPA nhằm nâng cao chất lượng giải mã LDPC là một vấn đề nghiên cứu của luận án, làm cơ sở khoa học nâng cao tính ứng dụng của các mã LDPC vào các hệ thống thông tin vô tuyến số hiện tại và trong tương lai. Mục tiêu và cũng là nhiệm vụ cụ thể của luận án là giải quyết các vấn đề sau:  Nghiên cứu phương pháp điều chế trong hệ thống BILCM-ID trên cơ sở độ tin cậy của các bít mã nhằm hạ thấp sàn lỗi. Kết quả nghiên cứu theo hướng này là kết quả mới hoàn toàn, vì trước đây độ tin cậy của bít mã chủ yếu được dùng trong giải mã.  Để áp dụng được nguyên lý BILCM-ID đối với điều chế BPSK, luận án đề xuất sử dụng các ánh xạ đa chiều (2D, 3D, 4D) để biến điều chế hai mức thành điều chế đa mức. Các phép ánh xạ này cũng đã được đề xuất sử dụng trong sơ đồ BICM-ID truyền thống để dùng cho ghi từ số. Luận án đề xuất áp dụng cho BILCM-ID, kết hợp với phương pháp điều chế dựa trên độ tin cậy của bít mã.  Chất lượng giải mã của thuật toán tổng-tích SPA bị ảnh hưởng bởi việc tồn tại các vòng kín ngắn trên đồ hình Tanner. Vấn đề nghiên cứu của luận án là cải tiến thuật toán SPA nhằm nâng cao chất lượng giải mã của thuật toán này. Ngoài ra, việc ước lượng kênh chính xác là rất khó khăn và sai số của ước lượng kênh này lại ảnh hưởng tới chất lượng thuật toán giải mã tổng-tích. Luận án nghiên cứu, khảo sát biện pháp khắc phục ảnh hưởng của sai số ước lượng kênh tới thuật toán SPA. Đối tượng nghiên cứu - Kênh vô tuyến.
• 21. Shannon. - Các vấn đề cơ bản về mã LDPC (các đặc điểm của mã, các phương pháp mã hóa và các thuật toán giải mã). - Nguyên lý hệ thống BICM-ID. - Các ánh xạ đa chiều. Phương pháp nghiên cứu Phương pháp nghiên cứu sử dụng trong luận án là kết hợp giải tích với mô phỏng Monte-Carlo. Phương pháp giải tích được sử dụng để biểu diễn, xây dựng mô hình hệ thống và phân tích chất lượng hệ thống. Mô phỏng Monte-Carlo được sử dụng để đánh giá chất lượng hệ thống thông qua tỷ lệ lỗi bít và tỷ lệ lỗi từ mã. Ý nghĩa khoa học và thực tiễn Mã LDPC là họ mã có chất lượng cao và đang được áp dụng trong một số hệ thống viễn thông hiện đại như hệ thống di động 4G. Các nghiên cứu về mã LDPC đang được thực hiện mạnh mẽ trong và ngoài nước. Từ việc nghiên cứu, đánh giá những phẩm chất tốt của mã LDPC như khả năng giải mã song song, phương pháp giải mã đơn giản (so với mã Turbo), cho thấy việc lựa chọn đề tài của luận án phù hợp với các hướng nghiên cứu hiện nay cho các mã sửa lỗi hướng đi. Những hạn chế của mã LDPC được luận án nghiên cứu, phân tích và đề xuất các biện pháp cải tiến như: điều chế mã LDPC trên cơ sở độ tin cậy bít mã cho cả điều chế nhị phân và điều chế đa mức, cải tiến thuật toán SPA. Các biện pháp này có thể ứng dụng vào thực tế để nâng cao chất lượng mã LDPC. Bố cục của luận án Luận án được chia thành 3 chương với các nội dung chính như sau: - Chương 1: TỔNG QUAN. Nội dung của chương này trình bày về: Giới hạn Shannon về dung lượng kênh; Các giải pháp về mã hóa để
• 22. lượng Shannon; Tìm hiểu quá trình phát triển của các mã LDPC; Các đặc điểm cơ bản của mã LDPC; Các ưu, nhược điểm của mã này và sơ đồ nguyên lý BICM-ID. Từ đó đưa ra các mục tiêu của luận án nhằm khắc phục các hạn chế của mã LDPC, cải thiện chất lượng mã. - Chương 2: SƠ ĐỒ KẾT HỢP BICM-ID VÀ LDPC. Nội dung của Chương 2 trình bày mô hình hệ thống của sơ đồ BILCM-ID, như là sự kết hợp giữa sơ đồ BICM-ID truyền thống với mã LDPC. Chương này đề xuất cải tiến sơ đồ mô phỏng và trình bày một kết quả về cải thiện chất lượng thuật toán giải mã LDPC bằng thuật toán SPA. Các kết quả của Chương 2 liên quan đến công trình nghiên cứu số 1 và số 2. - Chương 3: ĐIỀU CHẾ MÃ LDPC DỰA TRÊN ĐỘ TIN CẬY CỦA CÁC BÍT MÃ. Nội dung của chương này tập trung nghiên cứu về độ tin cậy của các bít mã LDPC; đề xuất phương pháp điều chế mã LDPC trên cơ sở độ tin cậy của các bít mã; Các kết quả mô phỏng khi sử dụng phương pháp điều chế mã này. Các kết quả của Chương 3 liên quan đến công trình nghiên cứu số 3 và số 4.
• 23. QUAN 1.1 Giới hạn Shannon Trong bài báo “Lý thuyết toán học của thông tin”, Claude Shannon [57] đã giới thiệu các khái niệm cơ bản và các định lý, sau này tổng hợp lại được gọi là lý thuyết truyền tin. Các định nghĩa và mô hình cho hai phần tử quan trọng được trình bày trong lý thuyết của ông bao gồm nguồn nhị phân (BS- Binary Source) và kênh nhị phân đối xứng (BSC-Binary Symmetric Channel). Nguồn nhị phân là thiết bị sinh ra một trong hai ký hiệu ‘0’ và ‘1’ một cách ngẫu nhiên với tốc độ nhất định , đo bằng số ký hiệu trên giây. Các ký hiệu này được gọi là bít (con số nhị phân). Kênh nhị phân đối xứng là phương tiện để truyền một bít trong một đơn vị thời gian. Tuy nhiên, kênh này có thể không tin cậy và được đặc trưng bởi xác suất lỗi (0 1/ 2) p p   là xác suất mà bít ra khác với bít vào tương ứng. Tính đối xứng của kênh thể hiện ở chỗ xác suất lỗi p giống nhau đối với cả hai ký hiệu liên quan. Lý thuyết truyền tin được xây dựng lên như một công cụ toán học để phân tích, đánh giá việc truyền tin giữa máy phát và máy thu qua kênh có lỗi, một mặt phân tích nguồn tin (đặc biệt là lượng tin sinh ra bởi nguồn), và mặt khác chỉ ra các điều kiện thực hiện việc truyền tin tin cậy trên các kênh có lỗi. Ba nhóm kết quả chính trong lý thuyết này bao gồm: 1. Thứ nhất, đưa ra định nghĩa một đại lượng mới là lượng tin cùng với đơn vị đo hợp lệ, đảm bảo tính bền vững khi hiểu theo ý nghĩa vật lý với đầy đủ các đặc điểm của nó. 2. Thứ hai, giải quyết mối quan hệ giữa lượng tin và nguồn sinh ra thông tin. Khái niệm này dẫn đến một định nghĩa quan trọng là lượng tin
• 24. nguồn tin. Kỹ thuật nổi tiếng liên quan tới khái niệm này là nén và mã hóa nguồn. 3. Thứ ba, giải quyết mối liên hệ giữa lượng tin và kênh truyền tải lượng tin đó. Khái niệm này dẫn đến một định nghĩa quan trọng là dung lượng kênh. Một kỹ thuật nổi tiếng trong lý thuyết thông tin liên quan tới khái niệm này được gọi là mã hóa kênh. Như vậy, mã hóa là một trong các kỹ thuật quan trọng nhất được sử dụng trong lý thuyết truyền tin. Nói chung, mã hóa là phép gán hai chiều giữa tập các bản tin được (sinh ra) phát đi và tập các từ mã dùng để (ghi) truyền các bản tin này. Đề tài nghiên cứu của luận án thuộc lĩnh vực truyền tin qua kênh có lỗi, và giới hạn Shannon đặt ra đối với mã hóa kênh được chỉ ra như sau: Nếu tốc độ thông tin của một nguồn nhất định không vượt quá dung lượng kênh thì khi đó tồn tại một kỹ thuật mã hóa có thể tạo ra sự truyền dẫn với một tỷ lệ lỗi thấp tùy ý trên kênh không tin cậy này. Lý thuyết này đã tiên đoán khả năng truyền không lỗi trên kênh không tin cậy hay kênh có nhiễu. Điều này đạt được bằng cách sử dụng mã hóa. Lý thuyết của Shannon đã chỉ ra giới hạn truyền thông tin trên kênh có nhiễu và biện pháp khắc phục các giới hạn này bằng cách áp dụng kỹ thuật mã hóa phức tạp hơn nhưng không chỉ ra thực hiện kỹ thuật mã hóa này như thế nào. Sơ đồ khối của hệ thống thông tin liên quan đến lý thuyết truyền tin được chỉ ra trên Hình 1-1 cùng với hai kiểu mã hóa. Bộ mã kênh được thiết kế để sửa lỗi nhằm biến đổi kênh không tin cậy thành kênh tin cậy. Ngoài ra, có bộ mã nguồn được thiết kế để tạo ra tốc độ thông tin nguồn phù hợp với dung lượng kênh.
• 25. hiệu i x là một trong các bản tin tùy ý có thể được nguồn phát đi và ( ) i i P x P  là xác suất mà bản tin này được phát đi. Có thể mô hình hóa đầu ra của nguồn tin này bằng một biến ngẫu nhiên X , coi i X x  là sự kiện với xác suất ( ) i i P X x P   khi ký hiệu i x xuất hiện trên đầu ra của nguồn. Shannon định nghĩa lượng tin của sự kiện i x là đại lượng đo theo hàm lô-ga-rít: 1 log log i b i b i I P P          (1.1) Lượng tin của một sự kiện chỉ phụ thuộc vào xác suất xuất hiện của nó chứ không phụ thuộc vào nội dung. Nếu tính theo cơ số 2 thì lượng tin được đo bằng bít. Nếu tính theo lô-ga-rít tự nhiên thì lượng tin được đo bằng nat. Có thể sử dụng công thức chuyển đổi cơ số lô-ga-rít như sau: 1 log ( ) log ( ). log ( )  a b b x x a (1.2) Với bất cứ hai bản tin nguồn độc lập i x và j x có xác suất tương ứng là i P và j P , xác suất liên kết là ( , ) i j i j P x x PP  thì lượng tin của hai bản tin này bằng tổng lượng tin của mỗi bản tin: Mã hoá kênh Giải điều chế Kênh truyền Điều chế Thông tin vào Thông tin ra t u t c t s t r ˆt c ˆt u Mã hoá nguồn Giải mã nguồn Giải mã kênh Hình 1-1. Sơ đồ khối hệ thống thông tin số đơn giản
• 26. log log      ij b b b i j i j i j I I I PP P P (1.3) 1.1.2 Entropy Nhìn chung, nguồn tin sinh ra một tập M ký hiệu khác nhau, được biểu diễn bằng biến ngẫu nhiên rời rạc X lấy bất kỳ giá trị nào trong dải   1 2 , ,..., M A x x x  . Mỗi ký hiệu i x được phát đi với xác suất i P và chứa thông tin i I . Các xác suất của các ký hiệu thỏa mãn điều kiện là ít nhất một ký hiệu được phát đi nên: 1 1    M P i i (1.4) Giả sử phân bố xác suất của các ký hiệu tuân thủ quá trình dừng (stationary) và các ký hiệu là độc lập và phát đi với tốc độ r ký hiệu trên giây. Nguồn có đặc điểm này gọi là nguồn không nhớ rời rạc (DMS-Discrete Memoryless Source). Mỗi ký hiệu chứa lượng tin i I nên tập   1 2 , ,..., M I I I có thể xem như là các giá trị của một biến ngẫu nhiên rời rạc với lượng tin trung bình:   1 1 1 log M M i b i i i b i i H X PI P P             (1.5) Hàm này được định nghĩa là entropy của nguồn. Nếu tính với cơ số 2, entropy được tính bằng số bít trên giây:   2 1 1 1 log / M M i i i i i i H X PI P bít s P             (1.6) Đối với nguồn nhị phân ( 2 ) M  và giả sử xác suất của các ký hiệu có giá trị: 0   P ; 1 1    P Thì entropy bằng:       2 2 1 1 log 1 log 1 H X                       Ω (1.7)
• 27. - p p p 1 - p Hàm ( )   được sử dụng để biểu diễn entropy của nguồn nhị phân với lô-ga-rít cơ số 2. 1.1.3 Kênh thông tin Định nghĩa: Kênh thông tin được đặc trưng bởi tập các ký hiệu tại đầu vào   1 2 , ,..., U x x x và tập các ký hiệu tại đầu ra   1 2 , ,..., V y y y và tập các xác suất có điều kiện ( / ) i i P y x xác định mối quan hệ giữa đầu vào i x và đầu ra i y . Xác suất này tương ứng với việc thu được ký hiệu i y nếu ký hiệu i x được phát đi trước đó. Tập các xác suất ( / ) i i P y x được sắp xếp theo ma trận ch P , đặc trưng đầy đủ cho kênh rời rạc tương ứng: ij ( / ) j i P P y x  Kênh nhị phân đối xứng (BSC): Kênh BSC (Binary Symmetric Channel) được đặc trưng bởi xác suất p là xác suất mà một ký hiệu nhị phân được chuyển đổi sang ký hiệu khác (Hình 1-2). Mỗi ký hiệu nhị phân có một xác suất được phát đi. Xác suất của 0 và 1 được phát đi là  và 1   tương ứng. Ký hiệu: 1 0, x  2 1 x  và 1 0 y  và 2 1 y  Ma trận xác suất của kênh BSC là: 1 1 ch p p P p p          (1.8) Hình 1-2. Kênh nhị phân đối xứng
• 28. y2 1 y3 1 - p p p 1 - p Kênh xóa nhị phân (BEC): Trong phần lớn các trường hợp cơ bản, truyền dẫn thông tin nhị phân liên quan tới việc gửi đi hai dạng sóng khác nhau để đại diện các ký hiệu ‘0’ và ‘1’. Tại máy thu, quyết định tối ưu thường được sử dụng để quyết định dạng sóng thu được ứng với ‘0’ hay ‘1’ có bị ảnh hưởng của lọc và nhiễu trên kênh. Hoạt động này gọi là quyết định lọc phối hợp, đôi khi đưa ra kết quả không quyết định được. Nếu độ tin cậy của ký hiệu thu không cao, có thể lựa chọn cách chỉ ra kết quả nghi ngờ bằng ký hiệu xóa. Việc sửa các ký hiệu xóa này sau đó thường sử dụng các công cụ khác thuộc phần khác của hệ thống. Hình 1-3. Kênh xóa nhị phân Việc sử dụng ký hiệu xóa này là cải tiến mô hình của kênh BSC và đưa ra mô hình kênh BEC (Binary Erasure Channel) được chỉ ra trên Hình 1-3. Đối với kênh BEC, p là xác suất xóa, 0 1 / 2 p   , và mô hình kênh có hai đầu vào và ba đầu ra. Khi giá trị thu được không tin cậy hay khối nhận được phát hiện có chứa lỗi thì thông báo xóa được chỉ ra bằng ký hiệu ‘?’. Ma trận xác suất của kênh này như sau: 1 0 0 1 ch p p P p p          (1.9)
• 29. tương hỗ Lượng tin tương hỗ khi phát đi i x và nhận được i y được định nghĩa là:    2 ( / ) , log bÝt ( ) i i i i i P x y I x y P x (1.10) Giá trị trung bình khi tính toán lượng tin tương hỗ giữa tất cả các cặp đầu vào - đầu ra của kênh được gọi là lượng tin tương hỗ trung bình:                   2 , , ( / ) , , , , log bÝt/ký hiÖu ( ) i j i j i j i j i j i j i P x y I X Y P x y I x y P x y P x (1.11) 1.1.5 Dung lượng kênh rời rạc Khái niệm lượng tin tương hỗ trung bình dẫn đến khái niệm dung lượng kênh. Tham số này là đặc trưng của kênh và được định nghĩa là giá trị lớn nhất có thể của lượng tin tương hỗ trung bình của kênh: ) ( max ( , ) sè bÝt trªn ký hiÖu i s P x C I X Y  (1.12) Nếu tốc độ tối đa (số ký hiệu trong một giây) là s thì dung lượng của kênh trên một đơn vị thời gian bằng:  s C sC bps (1.13) Được xem là tốc độ truyền tin tối đa trên kênh. 1.1.6 Lý thuyết về mã kênh Nếu tốc độ truyền dẫn R (bps) thỏa mãn điều kiện R C  thì với một giá trị tùy ý 0   tồn tại một mã với chiều dài khối n có xác suất lỗi truyền dẫn nhỏ hơn . Nếu R C  thì không có gì đảm bảo cho việc truyền dẫn tin cậy; tức là không đảm bảo có giá trị tùy ý  nhỏ hơn 1 là cận trên của xác suất lỗi vì nó có thể vượt quá giá trị này. Kênh Gao-xơ sau khi lấy mẫu tín hiệu là một kênh rời rạc được mô tả trên Hình 1-4. Biến N biểu diễn các mẫu biến ngẫu nhiên Gao-xơ có phương
• 30. tín hiệu có công suất P . Nếu như tất các các biến được biểu diễn bởi các véc-tơ chiều dài n thì chúng có mối liên hệ: Y X N   (1.14) Dung lượng của kênh tính theo bít trên một ký hiệu là: 2 1 log 1 2 s N P C P         (1.15) Một kênh liên tục với mật độ phổ công suất 0 / 2 N , băng thông B và công suất tín hiệu P có thể được chuyển sang kênh rời rạc với việc lấy mẫu tại tốc độ Nyquist. Công suất mẫu nhiễu bằng:   0 0 / 2     B N B P N df N B (1.16) Nên dung lượng kênh tính theo bít trên một ký hiệu là: 2 0 1 log 1 2 s P C N B         (1.17) Dung lượng kênh tính theo bít trên giây được bằng: + X N Y=X+N Kênh Gao-xơ, các tín hiệu được biểu diễn bằng các số thực Hình 1-4. Kênh Gao-xơ
• 31. BC B bps N B          (1.18) 1.2 Mã LDPC 1.2.1 Sự phát triển của các kỹ thuật mã kênh nhằm đạt giới hạn Shannon Mã kênh gồm mã dạng sóng và mã chuỗi có cấu trúc. Mã chuỗi có cấu trúc có thể chia thành 3 loại: mã khối, mã chập và mã liên kết. Mã khối được ký hiệu là ( , ) n k , trong đó các khối gồm k bit tin được sắp xếp thành các từ mã n bit với số lượng bit dư là n k  , tỷ lệ mã hoá được định nghĩa là / k n. Do việc sắp xếp các khối k bit tin này được thực hiện độc lập với nhau nên mã khối còn được gọi là mã không nhớ. Mã khối thường sử dụng là mã tuyến tính thỏa mãn hai điều kiện: 1) có từ mã toàn 0, 2) tổng module 2 của hai từ mã là một từ mã khác. Mã khối được nghiên cứu đầu tiên cho nên lý thuyết về nó hoàn chỉnh hơn so với mã chập và các họ mã sau này. Mã khối đầu tiên là mã Hamming [26], sau đó có các họ mã mạnh hơn là mã RS [50] và BCH (Bose, Chaudhuri and Hocquenghem) [6], [27], mã Cyclic [49] ... . Mã BCH nhị phân là bộ mã tổng quát cho các mã Hamming và mã Golay [23]. Mã RS(Reed-Solomon) là một tập hợp con của mã BCH phi nhị phân (nonbinary), được tối ưu hóa cự ly giữa các từ mã với khả năng sửa các lỗi cụm mạnh, thường sử dụng trong các mã liên kết [13]. Thuật toán giải mã khối đầu tiên do Reed đề xuất là thuật toán giải mã ngưỡng [51]. Sau đó các thuật toán giải mã bằng hàm đại số tuyến tính, giải mã tuần tự ... ra đời. Khác với mã khối, mã chập được Elias giới thiệu [46] là bộ mã có nhớ, trong đó k bit thông tin đầu vào cũng được sắp xếp thành n bit mã đầu ra nhưng là một hàm phụ thuộc vào quá khứ. Thuật toán giải mã chập đầu tiên là thuật toán giải mã tuần tự [65]. Thuật toán này rất phức tạp và có số lượng tính toán để giải mã là vô hạn. Thuật toán giải mã đơn giản hơn là giải mã
• 32. số lượng tính toán hạn chế. Năm 1967, Viterbi đề xuất thuật toán VA (Viterbi Algorithm) [63], [64] khá đơn giản cho phép mã chập được ứng dụng rộng rãi cho tới ngày nay. Thuật toán VA hạn chế được số lượng phép tính trên mỗi bước giải mã, vì vậy nó không bị tràn như thuật toán giải mã chuỗi và đơn giản hơn thuật toán giải mã ngưỡng. Đây là thuật toán giải mã cực tiểu xác suất lỗi chuỗi khi quá trình mã hoá là một quá trình Markov. Một thuật toán khác do Bahl [2] đề xuất năm 1974, là giải mã cực tiểu xác suất lỗi bit. Thuật toán này phức tạp hơn trong khi không cải thiện được nhiều về chất lượng giải mã tại các tỷ lệ tín trên tạp cao nên không được sử dụng rộng rãi. Năm 1966, Forney đưa ra ý tưởng liên kết các mã, trong đó chập được sử dụng làm mã vòng trong và mã RS được sử dụng làm mã vòng ngoài, liên kết thông qua bộ hoán vị bít [13]. Các mã liên kết này đã được sử dụng làm chuẩn của NASA trên các hệ thống thông tin vũ trụ. Forney phát biểu rằng, nếu độ phức tạp bộ mã hoá và giải mã tăng theo hàm đại số thì chất lượng có thể tăng theo hàm Log. Nói chung, chất lượng của các họ mã trên còn cách khá xa với giới hạn Shannon. Ví dụ, bộ mã chập Qualcomm 64 trạng thái, tỷ lệ 1/2 có chất lượng chỉ đạt xác suất lỗi là 10-5 tại 4,3 dB, trong khi đó theo lý thuyết về cận Shannon là 0,2 dB. Năm 1993 và 1996, các bộ mã liên kết song song PCCC (Parallel Concatenated Convolutional Codes hay còn gọi là Turbo) [2] và nối tiếp SCCC (Serial Concatenated Convolutional Codes) [3] cùng với thuật toán giải mã lặp được giới thiệu. Các bộ mã này cho phép đạt xác suất lỗi là 10-5 tại tỷ lệ tín trên tạp chỉ còn cách giới hạn Shannon vài phần mười dB. Hai dòng mã khác cũng có chất lượng tương tự là LDPC [41] và RA (Repeat Accumulate) [12].
• 33. kiểm tra mật độ thấp (LDPC) được phát minh bởi Robert G. Gallager trong luận án tiến sỹ của ông tại MIT năm 1963 [20]. Tính không khả thi do phức tạp của thuật toán mã hóa - giải mã trong bước phát triển ban đầu (trước khi có công nghệ silicon và vi xử lý) làm cho các mã LDPC rơi vào quên lãng, và chúng được tái phát hiện trong năm 1996 [24]. Trong những năm gần đây, các tiến bộ của mã LDPC vượt trội mã Turbo về chất lượng tại tỷ lệ mã hóa cao làm cho mã Turbo chỉ còn phù hợp cho các ứng dụng với các tỷ lệ mã hóa thấp hơn. 1.2.2 Quá trình phát triển của mã LDPC Mã LDPC (Mã kiểm tra mật độ thấp), hay còn gọi là mã Gallager, được đề xuất bởi Gallager [20], [21]. Ngày nay, người ta đã chứng minh được rằng các mã LDPC bất qui tắc có độ dài khối lớn có thể tiệm cận giới hạn Shannon. Về cơ bản đây là một loại mã khối tuyến tính có đặc điểm các ma trận kiểm tra (H) là các ma trận thưa (sparse matrix), hầu hết các phần tử là 0 và chỉ một số ít là 1. Theo định nghĩa của Gallager, ma trận kiểm tra của mã LDPC còn có đặc điểm là mỗi hàng chứa đúng i phần tử 1 (trọng số hàng) và mỗi cột chứa đúng j phần tử 1 (trọng số cột). Một mã LDPC như vậy sẽ được gọi là một mã LDPC quy tắc( , , ) n i j , trong đó n là độ dài khối của mã và cũng chính là số cột của ma trận H. Tại thời điểm ra đời của mã LDPC, năng lực tính toán của máy tính còn khá hạn chế nên các kết quả mô phỏng không phản ảnh được khả năng kiểm soát lỗi cao của mã này. Cho đến tận gần đây, đặc tính vượt trội của mã LDPC mới được chứng minh và Mackay và Neal [40], [41] là hai người được coi là đã phát minh ra mã LDPC một lần nữa nhờ sử dụng thuật toán giải mã dựa trên thuật toán tổng-tích SPA.
• 34. ban đầu của Gallager, Luby cùng các tác giả khác đã đánh dấu một bước tiến quan trọng của mã LDPC trong việc đưa ra khái niệm mã LDPC bất quy tắc [37]. Đặc điểm của các mã này là trọng số hàng cũng như trọng số cột không đồng nhất. Các kết quả mô phỏng cho thấy các mã LDPC bất quy tắc được xây dựng phù hợp có đặc tính tốt hơn các mã quy tắc. Tiếp theo đó, Davey và Mackay khảo sát các mã bất quy tắc trên trường Galois ( ) GF q với q>2. Theo các tác giả này, khả năng kiểm soát lỗi của mã LDPC trên ( ) GF q được cải thiện đáng kể so với các mã trên (2) GF [3]. Việc biểu diễn mã LDPC bằng đồ hình (graph) đóng vai trò quan trọng trong việc xây dựng các thuật toán giải mã. Tanner được coi là người đề xuất biểu diễn các mã dựa trên đồ hình [59]. Nhiều nhà nghiên cứu khác đã phát triển các đồ hình Tanner thành các đồ hình thừa số (factor graph) như là một dạng tổng quát của đồ hình Tanner. Các thuật toán giải mã lặp dựa trên xác suất được sử dụng để giải mã LDPC. McEliece cùng các tác giả khác đã chứng minh rằng các thuật toán giải mã này có thể được xây dựng từ thuật toán truyền niềm tin BP, hay còn gọi là thuật toán truyền bản tin (Message Passing Algorithm), một thuật toán được sử dụng khá phổ biến trong ngành trí tuệ nhân tạo [45]. Kschischang cùng các tác giả khác đã tổng quát hoá thuật truyền bản tin để xây dựng thuật toán tổng-tích SPA [34]. Đây là một thuật toán có thể được áp dụng trong nhiều ngành khoa học kĩ thuật như trí tuệ nhân tạo, xử lí tín hiệu và thông tin số. Cấu trúc các mã LDPC cũng là một đề tài nghiên cứu của nhiều nhà lí thuyết truyền tin. Các phương pháp được sử dụng có thể là các phương pháp giải tích hoặc ngẫu nhiên. Cấu trúc đầu tiên của mã LDPC được đề xuất bởi Gallager sử dụng phương pháp hoán vị ngẫu nhiên cột ma trận [21]. Với mục
• 35. lượng vòng kín ngắn (short cycle) trong đồ hình Tanner của mã LDPC, Mackay đã đưa ra một số cấu trúc ngẫu nhiên khác, với các ma trận kiểm tra chẵn lẻ có số bit 1 chồng nhau giữa hai cột bất kì không quá 1 [11]. Trong khi đó, các phương pháp tạo mã giải tích chủ yếu dựa trên hình học hữu hạn (finite geometry) và thiết kế tổ hợp (combinatorial design) [19]. Kou cùng các tác giả khác đã đề xuất bốn lớp mã LDPC dựa trên hình học Ơ-clit (Euclidean geometry) và hình học chiếu (projective geometry) [33]. Do đặc điểm là các mã này có thể được đưa về dạng mã vòng (cyclic) hoặc gần-vòng (quasi-cyclic), nên việc mã hoá có thể sử dụng thanh ghi dịch. Các mã LDPC dựa trên thiết kế tổ hợp được xây dựng từ các hệ Steiner và hệ Kirkman, một trường hợp đặc biệt của hệ Steiner. Mackay và Davey đã khảo sát các mã từ hệ Steiner cho các ứng dụng độ dài khối thấp và tỉ lệ mã cao. Các mã này không có các vòng kín độ dài 4, tuy nhiên đặc tính cự ly Hamming tối thiểu của chúng khá kém. Các mã xây dựng trên các hệ ba Kirkman (Kirkman triple system) được nghiên cứu tại Đại học New Castle (Úc) [30]. 1.2.3 Cơ bản về mã LDPC Ký hiệu n là chiều dài mã, k là chiều dài véc-tơ tin và r n k   là chiều dài phần dư. Trong luận án, ta chỉ xét các mã LDPC nhị phân (mặc dù chúng có thể được cấu tạo từ các trường khác). Giả sử các véc-tơ là các véc-tơ dạng cột. Véc-tơ tin là một véc-tơ 1  k , từ mã là véc-tơ 1  n . Ma trận sinh G kích thước  n k và ma trận kiểm tra H có kích thước  r n , sao cho 0 HG  . Ký hiệu các hàng của ma trận kiểm tra: 1 2 T T T r h h H h              
• 36. c  là điều kiện kiểm tra của từ mã c. Ký hiệu T m m z h c  và gọi m z là một phép kiểm tra. Từ ma trận kiểm tra H của mã, cần xác định ma trận sinhG cho mục đích mã hóa. Dạng hệ thống của ma trận sinh được tìm theo cách sau. Trước hết, dùng phép khử Gao-xơ xác định ma trận 1 p H  kích thước r r  sao cho:   1 2 p H I H H H     Từ việc tìm được H, ta có 2 G I H        Khi đó 0 H G   , nên 0 p H H G HG    , nên G là ma trận sinh của . H Một ma trận được gọi là thưa nếu số phần tử khác 0 nhỏ hơn một nửa. Mã kiểm tra mật độ thấp LDPC là mã khối có ma trận kiểm tra là ma trận rất thưa. Trọng số của véc-tơ nhị phân là số các phần tử khác 0 của nó. Trọng số cột (trọng số hàng ) của một cột (một hàng) của ma trận là trọng số của một cột (một hàng). Mã LDPC được chia làm hai loại: mã LDPC quy tắc và mã LDPC bất quy tắc. Mã LDPC được gọi là mã quy tắc nếu trọng số các hàng là giống nhau và trọng số các cột giống nhau. Để tạo ra mã LDPC quy tắc, lựa chọn trọng số cột c w (thường là một số nguyên có giá trị nhỏ như 3  c w ), chọn các giá trị của n (chiều dài khối) và r (phần dư). Ma trận H được tạo ra có trọng số cột là c w, trọng số hàng là r w thoả mãn điều kiện:  c r w n w r . Tất cả các bít tham gia vào c w phép kiểm tra và mỗi phép kiểm tra liên quan đến r w bít. Mã quy tắc như vậy được ký hiệu là mã ( , , ) c r w w n . Tỷ lệ thiết kế của mã quy tắc là 1 /   c r R w w với điều kiện
• 37. độc lập tuyến tính (bởi vì có trường hợp các hàng phụ thuộc tuyến tính, tốc độ thực có thể cao hơn tốc độ thiết kế). Gallager đã chỉ ra rằng cự ly tối thiểu của mã LDPC quy tắc tăng tuyến tính với n với điều kiện 3  c w . Ma trận kiểm tra không quy tắc là ma trận có trọng số cột thay đổi, tức là ta có mã LDPC bất quy tắc. Các mã LDPC bất quy tắc nếu được thiết kế tốt có thể có chất lượng tốt hơn các mã quy tắc. Đối với nhiều mã LDPC, n lấy giá trị khá lớn (ví dụ 10000 n  ) trong khi trọng số cột chỉ khoảng 3 hay 4, nên mật độ của các số 1 là rất thấp. Bởi vì H là ma trận thưa nên nó có thể biểu diễn một cách hiệu quả bằng cách sử dụng danh sách các vị trí khác 0. Trong cách biểu diễn này, các bít được đánh chỉ số là i hay ' i (ví dụ ' i c ) và các phép kiểm tra được đánh chỉ số là m hay ' m (ví dụ m z ). Tập các bít tham gia phép kiểm tra m z (tức là các phần tử khác 0 của hàng thứ m của H) được ký hiệu:   : 1 m mi N i H   Do đó ta có thể viết phương trình kiểm tra tại nút thứ m : m m i i N z c    Tập các bít tham gia phép kiểm tra m z trừ bít thứ iđược định nghĩa: ,  m i m N N i Ký hiệu m N chỉ số các phần tử của tập m N . Phần tử thứ p của tập m N được ký hiệu ( ) m N p . Tập các nút kiểm tra liên quan tới bít i c được ký hiệu:   , : 1   i m i M m H
• 38. LDPC quy tắc, w i c M  . Tập các nút kiểm tra liên quan tới bít i c trừ nút kiểm tra thứ m được ký hiệu: ,  i m i M M m = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0⎦ ⎥ ⎥ ⎥ ⎤ Hình 1-5. Biểu diễn ma trận và biểu diễn đồ hình Tanner của mã LDPC. Mã LDPC được xác định bởi một ma trận thưa và có thể sử dụng đồ hình hai bên - bipartite graph hay còn gọi là đồ hình Tanner [59] để biểu diễn. Đồ hình hai bên là đồ hình trong đó các nút của nó có thể chia thành hai tập hợp, mỗi nút trong một tập hợp được nối với một nút ở trong tập hợp kia. Hai tập hợp nút trong đồ hình Tanner được gọi là các nút kiểm tra và các nút bít đại diện cho các hàng và các cột tương ứng. Hình 1-5 biểu diễn một ma trận kiểm tra và đồ hình Tanner tương ứng. Nút kiểm tra thứ a được nối với nút bít thứ b nếu và chỉ nếu , 1 a b H  . Các nút 1 2 10 , ,..., c c c biểu diễn các cột của ma trận, 5 1 2 , ,..., z z z là các hàng. Số lượng các cạnh tại mỗi nút kiểm tra bằng trọng số hàng và số lượng các cạnh tại mỗi nút bít bằng trọng số cột. Trọng số hàng và trọng số cột tương ứng bằng 6 và 3 trong ví dụ này. Các nút kiểm tra Các nút bít
• 39. (cycle hay loop) trong ma trận kiểm tra được hình thành bởi một đường khép kín qua các phần tử ‘1’ lần lượt di chuyển giữa các hàng và cột. Trên đồ hình Tanner một vòng được hình thành bởi đường xuất phát từ một nút và kết thúc chính tại nút đó. Độ dài của vòng là số cạnh lập thành vòng đó. Một vòng có độ dài là 4 được biểu diễn bởi các đường nét đứt trên Hình 1-5. Vòng nhỏ nhất trong một đồ hình Tanner hoặc ma trận kiểm tra chẵn lẻ được gọi là mầm. Mầm có độ dài nhỏ nhất có thể là bốn. Trên Hình 1-6, hai con số 1 (ta gọi là 1 m và 2 m ) ở hàng a tương ứng thuộc các cột b và c , hai con số 1 (gọi là 3 m và 4 m ) ở hàng d tương ứng thuộc các cột b và c , như vậy hình ảnh vòng kín chiều dài 4 trong ma trận kiểm tra được chỉ ra trên Hình 1-6. Hình 1-6. Vòng kín chiều dài 4 trong ma trận kiểm tra 1.2.4 Đặc điểm của mã LDPC Các mã LDPC có các đặc điểm về cự ly rất tốt. Gallager đã chỉ ra rằng đối với các mã LDPC ngẫu nhiên, cự ly tối thiểu min d giữa các từ mã tăng theo chiều dài khối n khi trọng số hàng và cột cố định [21]. Các chuỗi mã LDPC được chứng minh là cho phép tiệm cận tới giới hạn dung lượng kênh khi   n [41]. Tuy nhiên với các kỹ thuật xây dựng các mã không ngẫu nhiên vẫn có hiện tượng lỗi sàn [52]. Thuật toán giải mã cho mã LDPC tương đối dễ xử lý. Theo các nghiên cứu, thuật toán giải mã có độ phức tạp tăng theo chiều dài từ mã [57]. Bởi vậy
• 40. những lợi ích thu được của mã ngẫu nhiên, tồn tại độ phức tạp giải mã theo luật mũ của các mã ngẫu nhiên. Mật độ rất thưa của ma trận kiểm tra của các mã LDPC làm cho thuật toán giải mã rất thuận lợi. Đặc điểm mật độ thưa của ma trận kiểm tra góp phần vào việc tạo ra đặc điểm cự ly tốt cũng như độ phức tạp giải mã giảm đi tương ứng. Nhiều nghiên cứu đã chỉ ra rằng có thể đạt được tăng ích mã hoá tốt với các mã có chiều dài hữu hạn (dù vẫn khá dài). Kết quả nghiên cứu của nhóm Chung (2001) [8] đối với mã LDPC bất quy tắc, tỷ lệ mã 1/2 có chiều dài khối 7 10 đã chỉ ra chất lượng mã chỉ cách giới hạn Shannon 0,045dB tại tỷ lệ lỗi bít (BER) là 10-5 . Tuy nhiên, cũng tồn tại các nhược điểm của các mã LDPC. Thứ nhất, các mã có chất lượng tốt nhất là các mã rất dài (như đã được tiên đoán trong lý thuyết mã kênh). Các chiều dài khối lớn, kèm theo giải mã lặp dẫn đến không chấp nhận được trong nhiều ứng dụng. Thứ hai, ma trận sinh G không nhất thiết thưa nên việc mã hoá có độ phức tạp tỷ lệ với bình phương chiều dài khối. Ngoài ra, các mã LDPC cũng có hiện tượng sàn lỗi như mã Turbo. 1.3 Sơ đồ BICM-ID truyền thống Sơ đồ khối hệ thống BICM-ID được trình bày trên Hình 1-7. Ở đầu phát hệ thống gồm có bộ mã sửa lỗi, bộ hoán vị dãy bít ( ) và bộ điều chế tạo thành một liên kết nối tiếp. Ở đầu thu, giữa bộ giải mã và giải điều chế có sử dụng vòng hồi tiếp để giải mã theo thuật toán lặp. Bộ mã sửa lỗi thường được dùng là mã chập để có được cự ly Hamming tối thiểu đạt giá trị lớn nhất với một tỷ lệ mã và độ dài ràng buộc cho trước. Dãy bít mã sau khi hoán vị được đưa tới bộ điều chế M mức để thực hiện việc gán nhãn tín hiệu, điều chế từng nhóm m bít mã tương ứng với một điểm (một symbol) trong chòm sao tín hiệu, trong đó 2 log m M  . Tín hiệu truyền đi qua kênh là một
• 41. ( )   t t s v chọn từ chòm sao tín hiệu S đã cho. Ở đây, hàm  thể hiện quy tắc ánh xạ giữa tập các nhóm m bít với tập các điểm trong chòm sao tín hiệu. Trong hệ thống BICM-ID, bộ mã hoá thường dùng mã chập tỷ lệ k/n, với nhóm k bít thông tin đầu vào 1 2 [ , ... ]  k t u u u u thì đầu ra bộ mã hoá sẽ là nhóm n bít mã 1 2 [ , ... ]  n t c c c c . Bộ hoán vị giả ngẫu nhiên  chiều dài N thực hiện việc hoán vị các bít sau mã hoá 1 2 1 2 1 2 1 1 1 2 2 2 / / / [ , ... , , ... , , , ... ]   n n n t N n N n N n c c c c c c c c c c tạo thành các nhóm bít: 1 2 2 ( , , , ), log , 1,2, , /      m t t t t v v v m M t N m v sau đó, mỗi nhóm t v được ánh xạ vào một symbol t s trong bộ tín hiệu S gồm M điểm, theo phép gán nhãn  : ( ),    t t t s v s S, trong đó, ví dụ đối với tín hiệu MPSK, ta có 2 / ( , 0,1,..., 1)     jl M S e l M . Qua kênh truyền, tín hiệu nhận được ở đầu thu là   t t s t t r h E s n , trong đó t h là hệ số pha-đinh, s E là năng lượng của symbol, t n là tạp âm Gao-xơ trắng cộng tính (AWGN) với mật độ phổ công suất một bên là 0 N . Hình 1-7. Sơ đồ khối hệ thống BICM-ID Mã hoá Giải hoán vị Kênh truyền Hoán vị Giải mã Thông tin vào Thông tin ra t u t c t s t r ˆt u Điều chế Giải điều chế t v Hoán vị
• 42. kênh pha-đinh, t h thường được coi là có phân bố Rayleigh với kỳ vọng 2 ( ) 1  t E h [9]. Với kênh AWGN thì 1  t h . Việc áp dụng kỹ thuật hoán vị dãy bít và thuật toán giải mã lặp không những cải thiện chất lượng của hệ thống khi truyền tin qua kênh pha-đinh, mà còn cho chất lượng tốt trên kênh Gao-xơ [7]. Trong hệ thống BICM-ID, tại đầu thu có thể dùng thuật toán giải mã quyết định cứng hoặc quyết định mềm như mô tả trên Hình 1-8, trong đó: ( ; ) k P v o : Là thông tin ngoài, lối ra giải điều chế ( ; ) k P c o : Là thông tin ngoài, lối ra giải mã ( ; ) k P v I : Là thông tin tiên nghiệm, lối vào giải điều chế ( ; ) k P c I : Là thông tin tiên nghiệm, lối vào giải mã ( ; ) k P u o : Là xác suất hậu nghiệm tổng, lối ra giải mã  : Bộ hoán vị 1  : Bộ giải hoán vị 1   Số đo bit Giải mã Viterbi Thông tin ra t r ˆt u Giải điều chế  Thông tin tiên nghiệm Thông tin ngoài a. Giải mã quyết định cứng 1   1   ( ; ) k P c I Giải mã SISO t r ˆt u Giải điều chế  b. Giải mã quyết định mềm ( ; ) k P v o Quyết định ( ; ) k P u o ( ; ) k P c o ( ; ) k P v I Hình 1-8. Nguyên lý giải mã cứng (a) và giải mã mềm (b)
• 43. quyết định cứng (Hình 1-8.a), trên cơ sở tín hiệu thu được từ kênh thông tin, số đo của các bít được tính toán tại bộ giải điều chế. Các số đo này thực chất là các giá trị xác suất hậu nghiệm được tính theo tiêu chuẩn xác suất hậu nghiệm cực đại MAP theo hàm lô-ga-rit như sau: ( ) log ( | , )      k i b i k s S b P s r h (1.19) Từ bộ giải điều chế, số đo bít qua bộ giải hoán vị được đưa tới bộ giải mã theo thuật toán Viterbi. Trên cơ sở kết quả giải mã, thông qua vòng hồi tiếp, bộ giải mã cung cấp lại cho bộ giải điều chế thông tin tiên nghiệm có giá trị chính xác hơn sau mỗi vòng lặp để tính lại số đo bít. Cứ như vậy, sau một số vòng lặp nhất định, khi đủ độ tin cậy thì bộ giải mã sẽ quyết định giá trị của bít thông tin ra [55]. Trong một symbol gồm m bít, việc quyết định một bít nào đó với điều kiện có sự hiểu biết đầy đủ về ( 1) m  bít còn lại thì chòm tín hiệu M mức có thể coi tương đương như m kênh điều chế nhị phân độc lập [48]. Như vậy, nếu ta chọn được một ánh xạ tốt, hệ thống BICM-ID sẽ có được cự ly Ơ-cơ-lít tối thiểu lớn nhất giữa các dãy bít mã. Điều đó lý giải tại sao hệ thống BICM-ID có hiệu quả tốt cả trên kênh pha-đinh và trên kênh Gao-xơ. Đối với hệ thống BCM-ID dùng giải mã quyết định mềm (Hình 1-8.b), bộ giải mã theo nguyên lý đầu vào mềm, đầu ra mềm SISO (Soft Input Soft Output), thay vì dùng bộ giải mã Viterbi như trong hệ thống quyết định cứng, và bộ giải điều chế cũng hoạt động theo nguyên lý giải điều chế mềm [4], [35]. Trong vòng lặp đầu tiên, với giả thiết xác suất truyền các tín hiệu i s là như nhau (giả thiết giá trị ban đầu của thông tin tiên nghiệm), xác suất hậu nghiệm của các bít mã cũng được tính tương tự như trường hợp giải mã cứng. Giá trị xác suất đó với vai trò là thông tin ngoài (extrinsic information), qua bộ giải hoán vị trở thành thông tin tiên nghiệm cho bộ giải mã SISO. Trên cơ
• 44. giải mã SISO sẽ tính được xác suất hậu nghiệm (a posteriori probability) và qua vòng hồi tiếp trở thành thông tin tiên nghiệm cho bộ giải điều chế để tính lại số đo bít. Sau một số vòng lặp nhất định, bộ giải mã SISO sẽ đưa thông tin ngoài chính là tổng các xác suất hậu nghiệm tới bộ quyết định cứng để cho kết quả là dãy bít thông tin ra. Các sơ đồ BICM-ID trong thực tế chủ yếu sử dụng sơ đồ giải mã quyết định mềm và giải điều chế mềm theo thuật toán Log-MAP. Thuật toán này được xây dựng cho giải mã Turbo, thực hiện tính tỷ lệ hợp lẽ trong miền log cho từng bít, ký hiệu là LLR (Log Likelihood Ratio) [25], dựa vào phép toán lấy log của tổng của các hàm mũ nên có số lượng phép tính rất lớn. Quy tắc ánh xạ, quy tắc hoán vị dãy bit là những yếu tố chi phối chất lượng hệ thống BICM-ID. Việc lựa chọn ánh xạ tốt nhất dùng cho hệ thống BICM-ID cũng là vấn đề rất được quan tâm trong thời gian gần đây. Có nhiều cách ánh xạ các tổ hợp bít vào các tín hiệu trong chùm tín hiệu (constellation), trong đó thường sử dụng ba ánh xạ cơ bản là ánh xạ Gray, ánh xạ phân hoạch tập tín hiệu (SP-Set Partition) và ánh xạ hỗn hợp (SSP-Semi Set Partition). Hiệu quả của hệ thống đối với mỗi ánh xạ là khác nhau như được chỉ ra trên Hình 1-9. Với cùng số mức và loại tín hiệu điều chế thì các phép ánh xạ có cùng độ phức tạp như nhau trong sơ đồ điều chế phía phát và giải điều chế mềm phía thu. Trong các sơ đồ mà giải mã độc lập với giải điều chế (không mang tính giải lặp) thì ánh xạ Gray được dùng nhiều hơn do trên đầu ra giải điều chế có BER nhỏ hơn so với các điều chế khác, trong khi SER là như nhau. Khi mã hóa và điều chế kết hợp (không có hoán vị như trong sơ đồ TCM hay có hoán vị như trong sơ đồ BICM) thì thường sử dụng SP vì mỗi vị trí bít có mức bảo vệ khác nhau cho phép tối ưu hóa hệ thống. Ngoài ra, phép ánh xạ SP được chứng minh là có tính chất nhất dạng hình học, dẫn tới tính
• 45. lỗi đều (xác xuất lỗi không phụ thuộc vào symbol nào được phát đi) nên đơn giản hóa việc phân tích chất lượng hệ thống. Trong các sơ đồ kết hợp điều chế và mã hóa, ta thấy rõ ràng là tại SNR thấp ánh xạ Gray tốt hơn vì tỷ lệ lỗi symbol lớn (khi đó ánh xạ Gray cho lỗi bít ít hơn), nhưng khi SNR lớn thì SP cho chất lượng tốt hơn. Lúc này tỷ lệ lỗi symbol nhỏ, tính chất sửa lỗi của mã được tối ưu với mức bảo vệ của bít trong tín hiệu điều chế sẽ quyết định chất lượng. Kết quả mô phỏng trình bày trên Hình 1-9 so sánh phẩm chất hệ thống điều chế 8-PSK với các ánh xạ khác nhau [1]. Nhìn hình vẽ có thể nói rằng đối với chòm sao 8-PSK, dùng trong hệ thống BICM-ID, phẩm chất BER của ánh xạ SP (Set Partitioning) tốt hơn ánh xạ SSP (Semi-Set Partitioning) và thấp kém nhất là ánh xạ Gray. Tuy nhiên tại vùng SNR thấp thì lại ngược lại, ánh xạ SP kém hơn ánh xạ SSP và ánh xạ Gray, bởi vì SNR thấp khiến cho thông tin hồi tiếp không hoàn hảo thậm chí còn làm cho kết quả giải mã tồi tệ hơn. Ánh xạ Gray tốt hơn các ánh xạ khác tại vùng SNR thấp bởi vì các dấu lân cận nhau chỉ sai khác 1 vị trí bit, dẫn tới tỉ lệ lỗi bit được tối thiểu hóa so với xác tỉ lệ lỗi dấu (SER- Symbol Error Rate). Hình 1-9. Phẩm chất hệ thống BICM-ID phụ thuộc vào kiểu ánh xạ 0 1 2 3 4 5 6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 Eb /N0 [dB] BER PHAM CHAT BER CUA MOT SO ANH XA 8-PSK Gray 8-PSK SP 8-PSK SSP 8-PSK Phẩm chất BER của một số ánh xạ 8-PSK
• 46. đề nghiên cứu Chất lượng của các mã LDPC bị ảnh hưởng xấu bởi sự tồn tại các vòng kín ngắn trên đồ hình Tanner như đã nêu ở trên. Việc xây dựng các mã LDPC không có các vòng kín trên đồ hình Tanner (nhất là đối với các mã có từ mã đủ dài) là việc rất khó khăn, gần như là bất khả thi. Khi xây dựng mã, đã có những cố gắng nghiên cứu và thành công để loại bỏ các vòng kín chiều dài 4, nhưng với các vòng kín chiều dài 6 hoặc 8 thì khó khăn hơn nhiều. Đến nay vẫn chưa có phương pháp xây dựng mã LDPC nào mà loại bỏ được hoàn toàn các vòng kín trên đồ hình Tanner. Trong các hệ thống thông tin số hiện đại, các bít trên đầu ra của máy mã kênh thường được hoán vị (để tăng độ phân tập về thời gian) và cộng nhị phân với chuỗi giả ngẫu nhiên (để tăng khả năng đồng bộ và làm trắng phổ). Như vậy, có thể xem xét phần mã hóa - điều chế như một mã liên kết, với mã LDPC là mã vòng ngoài và bộ điều chế là mã vòng trong. Cấu trúc này gợi ý cho hướng áp dụng sơ đồ BICM-ID để nghiên cứu các giải pháp làm giảm ảnh hưởng xấu của các vòng kín tới chất lượng mã LDPC. Thứ nhất, để giảm thiểu ảnh hưởng của các vòng kín ngắn, luận án nghiên cứu phương pháp điều chế mã sao cho các bít thuộc cùng vòng kín sẽ không được ánh xạ vào cùng một tín hiệu. Điều này sẽ được thực hiện bằng việc xây dựng bộ hoán vị trên cơ sở độ tin cậy của các bít mã. Các bít có độ tin cậy khác nhau sẽ được bảo vệ ở các mức khác nhau. Nếu bít mã có bậc tin cậy cao hơn được ánh xạ vào vị trí bít được bảo vệ tốt hơn trong mỗi tín hiệu thì có thể cải thiện xác suất lỗi bít trong vùng sàn lỗi. Với điều chế đa mức như MPSK hay MQAM với M > 2, nguyên lý BICM-ID có thể áp dụng trực tiếp cho sơ đồ dùng mã LDPC làm mã sửa lỗi hướng đi thay cho mã chập. Còn với BPSK, luận án đề xuất áp dụng ý tưởng tạo điều chế đa mức thông qua điều chế đa chiều, nghĩa là chia khối bít trên đầu ra máy mã LDPC thành
• 47. m bít. Mỗi nhóm này được ánh xạ vào một véc tơ m tín hiệu BPSK. Kết quả nghiên cứu về vấn đề này được trình bày ở Chương 3. Thứ hai, việc tồn tại các vòng kín ngắn trên đồ hình Tanner và/hoặc các ma trận kiểm tra cho các chiều dài từ mã thực tiễn chưa đủ tính ngẫu nhiên ảnh hưởng đến chất lượng giải mã của thuật toán SPA. Luận án nghiên cứu cải thiện chất lượng thuật toán giải mã SPA bằng cách đề xuất áp dụng hệ số hiệu chỉnh khi tính toán các bản tin tại các nút kiểm tra của đồ hình Tanner. Việc sử dụng hệ số hiệu chỉnh này đã được nhiều nhà nghiên cứu xem xét, nhưng mới chỉ áp dụng để cải thiện chất lượng của thuật toán cực tiểu-tổng (Min-Sum) mà chưa từng có nghiên cứu nào cho thuật toán SPA. Việc sử dụng hệ số hiệu chỉnh hầu như không làm tăng độ phức tạp của thuật toán giải mã vì chỉ là phép nhân một hằng số ở các biểu thức tính xác suất phép kiểm tra. Điều này đơn giản hơn nhiều so với việc cố gắng loại bỏ các vòng kín khi xây dựng mã. Luận án cũng nghiên cứu khảo sát tìm các hệ số hiệu chỉnh tối ưu. Mặt khác, để thuật toán giải mã SPA đạt chất lượng tốt cần ước lượng kênh chính xác. Luận án đề xuất sử dụng hệ số hiệu chỉnh phù hợp để giảm ảnh hưởng xấu của việc ước lượng kênh không chính xác. Kết quả nghiên cứu này được trình bày ở Chương 2. Thứ ba, việc xem xét đánh giá khả năng sửa lỗi của mã khối tuyến tính, nhất là trong mô phỏng, không phụ thuộc vào việc giả thiết từ mã nào đã được phát đi. Nhất là đối với mã LDPC, khi phải xét đến các chiều dài từ mã đủ lớn thì việc mã hóa bằng ma trận sinh là khá phức tạp. Vì vậy trong mô phỏng đánh giá chất lượng mã hóa - giải mã người ta thường giả thiết là từ mã toàn '0' được gửi đi. Khi nghiên cứu các sơ đồ BICM-ID, chúng ta phải xét đến các sơ đồ điều chế với các chòm sao tín hiệu khác nhau. Với các điều chế khi mà miền quyết định (vùng Vô-rô-nôi) là giống nhau đối với tất cả các điểm tín hiệu trên chòm sao tín hiệu (ví dụ như MPSK) thì việc giả thiết từ mã toàn '0'
• 48. hưởng tới độ chính xác trong kết quả mô phỏng. Tuy nhiên, nếu có sự khác nhau về hình dạng hay kích thước của miền quyết định (vùng Vô-rô-nôi) đối với các điểm tín hiệu khác nhau trên chòm sao tín hiệu (ví dụ như MQAM) thì kết quả mô phỏng sẽ không chính xác, vì chỉ có điểm ứng với nhãn nhị phân toàn '0' được gửi đi. Trong trường hợp này, luận án nghiên cứu đề xuất lợi dụng việc cộng từ mã LDPC theo modulo 2 với chuỗi giả ngẫu nhiên để mỗi tín hiệu trong chòm sao tín hiệu được chọn với xác suất như nhau, đảm bảo độ chính xác của kết quả mô phỏng. Nghiên cứu ở Chương 2 sẽ đề xuất phương pháp xử lý ở đầu thu tương ứng với xử lý ở đầu phát, nhằm vừa cho phép giả thiết đã phát đi từ mã toàn '0', vừa đạt được độ chính xác của kết quả mô phỏng với các chòm sao tín hiệu khác nhau. Ba chủ đề nghiên cứu trên đây là ba vấn đề chính của luận án và sẽ được triển khai trong hai chương tiếp theo.
• 49. ĐỒ KẾT HỢP LDPC VÀ BICM-ID Chương 2 trình bày mô hình hệ thống của sơ đồ BILCM-ID, như là sự kết hợp giữa sơ đồ BICM-ID truyền thống với mã LDPC. Để chuẩn bị cho các nghiên cứu ở Chương 3, tại chương này đề xuất cải tiến sơ đồ mô phỏng và trình bày một kết quả về cải thiện chất lượng thuật toán giải mã LDPC bằng thuật toán SPA. 2.1 Sơ đồ khối hệ thống điều chế mã LDPC Hình 2-1 mô tả sơ đồ khối của hệ thống điều chế mã LDPC có hoán vị bít (BILCM-ID). Tại máy mã LDPC, từng khối bít tin đầu vào 1 2 ( , , , ) k u u u u   được mã hóa thành từ mã 1 2 ( , , ) , n c c c c   . Trong trường hợp tổng quát, bộ hoán vị bít có chiều dài N Ln  bít, trong đó là chiều dài từ mã LDPC, còn 1 L là số từ mã LDPC chịu cùng một phép hoán vị. Đã có một số công trình nghiên cứu cho rằng 40 50 L   là tối ưu cho các hệ thống BILCM-ID. Luận án chỉ xét trường hợp hoán vị trên một từ mã, nghĩa là 1 L với lý do sau. Cho H là ma trận kiểm tra của mã LDPC đang xét, có kích thước r n  với r n k   . Giả sử 1 L , xét ma trận L H có kích thước Lr Ln  bao gồm L ma trận H xuôi theo đường chéo chính, còn các thành phần khác bằng 0. Rõ ràng hệ thống BILCM-ID có bộ hoán vị bít hoạt động trên 1 L từ mã với ma trận kiểm tra H tương đương với hệ thống BILCM-ID có bộ hoán vị bít hoạt động trên ' 1 L  từ mã với ma trận kiểm tra L H . Nhưng do ma trận kiểm tra L H được tạo ra từ H như trên chưa phải là ma trận thưa kích thước Lr Ln  tốt nhất cho mã LDPC, có thể kết luận rằng cho trước hệ thống BILCM-ID với bộ tham số   , , 1  r n L bất kỳ, luôn tồn tại hệ thống BILCM-ID với bộ
• 50.  ' , , 1  Lr Ln L cho phẩm chất tốt hơn. Cuối Chương 3 sẽ trình bày một ví dụ cho   60, 120, 1, 2, 4, 8 r n L    . Trở lại với bộ hoán vị bít thực hiện phép hoán vị  trên tập các chỉ số   1,2, ,n  các bít của một từ mã, thực chất là sắp xếp lại các bít đầu ra của máy mã theo một qui luật nhất định. Bộ điều chế sau đó lần lượt đọc từng khối nhỏ 2 log m M  bít, ánh xạ vào tập M tín hiệu, chọn lấy một tín hiệu và gửi đi qua kênh. Ở đây, ta xét kênh tạp âm Gao-xơ trắng cộng tính (AWGN - Additive White Gaussian Noise). Ký hiệu 1 2 / ( , , , ) n m s s s   s là véc-tơ tín hiệu tương ứng với phiên bản hoán vị của từ mã c . Cho 1 2 / ( , , , ) n m v v v   v là véc- tơ gồm các thành phần tạp âm AWGN trung bình 0 và phương sai 2 0 / 2 N   trong đó 0 N là mật độ phổ công suất một phía. Ta có véc-tơ thu   r s v . Phía thu hoạt động theo nguyên lý giải mã - giải điều chế lặp như trong sơ đồ BICM-ID. Cũng như trong các sơ đồ điều chế mã LDPC truyền thống, bộ giải điều chế mềm biến đổi véc-tơ tín hiệu thu r thành véc-tơ Máy mã LDPC Hoán vị bít Điều chế Kênh Giải điều chế mềm Giải hoán vị bít Giải mã LDPC Hoán vị bít u c  c s r a  a u  b  b v Hình 2-1. Sơ đồ khối hệ thống
• 51. ,..., ) n a a a  a chứa các giá trị tỷ lệ hợp lẽ theo hàm Lô-ga (LLR - Log Likelihood Ratio) làm đầu vào cho bộ giải mã LDPC. Điểm khác biệt là trong mô hình đang xét, bộ giải điều chế và giải mã LDPC liên kết thông qua giải hoán vị và hoán vị. Ký hiệu đầu vào giải mã là 1 ( )     a a , chính là các giá trị LLR của các bít mã nhận được bằng cách giải hoán vị đối với các thành phần của véc-tơ a . Trong mỗi lần lặp, bộ giải mã LDPC dựa trên thuật toán Tổng - Tích SPA dùng đầu vào  a để cập nhật LLR của nút kiểm tra, sau đó dùng LLR của nút kiểm tra để cập nhật các giá trị LLR của nút mã, cho đầu ra b. Ký hiệu ( )    b b là véc-tơ chứa các giá trị LLR của các bít mã đã được hoán vị, dùng làm thông tin tiên nghiệm hỗ trợ giải điều chế trong vòng lặp tiếp theo. Có thể tham khảo các biểu thức toán học cho giải điều chế mềm trong [31], [53]. 2.2 Cải tiến thuật toán giải mã SPA Như đã lập luận ở Mục 1.4, việc tồn tại các vòng kín ngắn trên đồ hình Tanner và/hoặc các ma trận kiểm tra cho các chiều dài từ mã thực tiễn chưa đủ tính ngẫu nhiên ảnh hưởng đến chất lượng giải mã của thuật toán SPA. Luận án nghiên cứu cải thiện chất lượng thuật toán giải mã SPA bằng cách đề xuất áp dụng hệ số hiệu chỉnh khi tính toán các bản tin tại các nút kiểm tra của đồ hình Tanner. Trước hết, chúng ta xem xét các phương pháp giải mã cơ bản đối với mã LDPC. 2.2.1 Bộ giải mã cứng Đối với mỗi bít i c , tính các phép kiểm tra có liên quan tới i c . Nếu số phép kiểm tra khác 0 vượt ngưỡng (tức đa số các phép kiểm tra khác 0) thì bít đó được xác định không đúng. Bít lỗi này được đảo đi và quá trình sửa lỗi tiếp tục.
• 52. i c bị lỗi và các bít khác ảnh hưởng tới phép kiểm tra của nó cũng bị lỗi. Xếp i c là gốc trên đồ hình Tanner (coi như không có vòng lặp trên đồ hình Tanner). Trên Hình 2-2, các bít trong các hình hộp bị lỗi. Các bít được nối tới các nút kiểm tra có liên quan tới nút gốc gọi là tầng 1. Các bít được nối tới các nút kiểm tra có liên quan các nút bít của tầng 1 gọi là tầng 2. Nhiều tầng như thế được thiết lập. Giải mã được bắt đầu từ các “lá” của cây (từ đỉnh của Hình 2-2). Khi bít i c được giải mã thì một số các bít lỗi khác có thể được sửa. Các bít và các nút kiểm tra không nối trực tiếp tới i c cũng có thể ảnh hưởng tới i c . Độ phức tạp của giải mã cứng đơn giản hơn giải mã mềm được đề cập ở phần sau. Tuy nhiên, chất lượng giải mã cứng không tốt bằng giải mã mềm. Sử dụng các bít này và các nút kiểm tra này Để sửa các bít này Sử dụng các bít này và các nút kiểm tra này Để sửa bít này Tầng 1 Tầng 2 Hình 2-2. Cây kiểm tra trên đồ hình Tanner.
• 53. mềm: Thuật toán tổng-tích SPA Với bộ giải mã quyết định mềm, khác với việc đảo các bít (giải mã quyết định cứng), các xác suất được truyền trên đồ hình Tanner, các thông tin kiểm tra về bít được tích lũy. Bộ giải mã tối ưu (tối thiểu hóa xác suất lỗi giải mã) tìm kiếm từ mã c  có ( | , 0) P c H  r c là lớn nhất, tức là véc-tơ thích hợp nhất thỏa mãn các phương trình kiểm tra, với điều kiện nhận được chuỗi thu   1 2 , ,..., n r r r r  . Tuy nhiên, độ phức tạp giải mã của bộ giải mã tối ưu của mã ngẫu nhiên là hàm mũ của k , đòi hỏi việc tìm kiếm trên toàn bộ 2k từ mã. Thay vào đó, bộ giải mã cố gắng tìm kiếm từ mã có bít i c có xác suất tối đa: ( | , tháa m·ntÊt c¶ c¸c phÐp kiÓm tra liªn quan bÝt ) i i P c c r tức là xác suất hậu nghiệm cho một bít đơn để các phép kiểm tra liên quan đến bít đó được thỏa mãn. Công việc này không thể đạt chính xác hoàn toàn do việc lấy xấp xỉ của các thuật toán thực tế. Tuy nhiên, thuật toán giải mã cũng đem lại chất lượng rất tốt và độ phức tạp giải mã tăng tuyến tính với chiều dài mã. Thuật toán giải mã làm việc với hai tập các xác suất. Tập thứ nhất liên quan tới tiêu chí giải mã, ( | , tháa m·ntÊt c¶ c¸c phÐp kiÓm tra liªn quan bÝt ) i i P c c r Ký hiệu xác suất này là   ( ) ( | , tháa m·n tÊt c¶ c¸c phÐp kiÓm tra liªn quan bÝt ), x 0,1 i i i q x P c c   r Sử dụng các ký hiệu nêu ở Mục 1.2.3 ta có:         | , 0, , 0,1      m i i i q x P c x z m M x r (2.1) Xác suất này được coi là xác suất giả hậu nghiệm và được sử dụng sau cùng để quyết định về các bít giải mã. Một biến đổi của xác suất này, gọi là ( ) mi q x : ( ) ( | , tháa m·ntÊt c¶ c¸c phÐp kiÓm tra liªn quan bÝt trõ z ) mi i i m q x P c x c   r . Viết ngắn gọn hơn ta có:
• 54.    ' , | , 0, ' mi m i i m q x P c x z m M     r Tập thứ hai là xác suất mà phép kiểm tra thỏa mãn với giá trị của bít đơn liên quan đến phép kiểm tra và các quan sát liên quan tới phép kiểm tra này. Xác suất này được ký hiệu là ( ) mi r x với:     0 | , mi m i r x P z c x    r Các giá trị ( ) mi q x và ( ) mi r x chỉ được tính với các phần tử mi H của H khác 0. Thuật toán giải mã kết hợp các dữ liệu thu được để tính các xác suất về các phép kiểm tra, được biểu diễn bằng ( ) mi r x . Thông tin về các phép kiểm tra này được sử dụng để tìm thông tin về các bít, được biểu diễn bằng ( ) mi q x . Thông tin này lại được dùng để cập nhật các xác suất về các phép kiểm tra, và cứ thế tiếp tục. Các giá trị này được truyền trên “cây” của đồ hình Tanner. Quá trình lặp lại các xác suất giữa các phép kiểm tra và các bít cho đến khi tất cả các phép kiểm tra được thỏa mãn hoặc số lần lặp đạt số lần lặp cho trước. Các bước tính theo chiều dọc: cập nhật ( ) mi q x Trên Hình 2-3 (a), một nút bít tùy ý i c từ đồ hình Tanner được sử dụng là gốc của cây với tập con của đồ hình Tanner nối nút bít này với các nút kiểm tra của nó và các nút bít khác liên quan tới các phép kiểm tra này trên cây. Các nút bít khác i c nối tới các bít kiểm tra này được coi là các bít thuộc tầng 1 của cây. Chúng ta giả sử các bít thuộc tầng 1 này là khác nhau, do đó độc lập với nhau. Trên thực tế, phần vẽ lại của đồ hình Tanner không phải là hình cây vì các bít thuộc tầng 1 có thể không tách biệt. Ví dụ, Hình 2-3(b) chỉ ra phần thực sự của đồ hình Tanner từ Hình 1-5 với gốc 1 c . Trong hình này bít 2 c được kiểm tra bởi cả 1 z và 5 z . Ở đây tồn tại vòng kín 4 trên đồ hình, được chỉ ra bằng các đường nét đứt (Hình 1-5). Tồn tại vòng kín như vậy tức là các bít
• 55. không độc lập (không lý tưởng như giả định). Tuy nhiên, với các mã đủ dài, xác suất có những vòng như vậy là nhỏ. Do đó chúng ta giả sử cấu trúc hình cây như Hình 2-3 (a) với sự giả định độc lập tương ứng của nó. Với giả sử sự độc lập của các bít ở tầng 1, các phép kiểm tra trên cây của i c là độc lập thống kê. Thuật toán giải mã sử dụng thông tin mà các nút kiểm tra cung cấp về các bít, được chỉ ra sau đây. Hình 2-3. Tập con của đồ hình Tanner. (a) Hình cây với i c là gốc. (b) Phần thực tế của đồ hình Tanner với i c là nút gốc. Định lý 2.1 [60]: Đối với mỗi bít i c liên quan đến các phép kiểm tra.   , m i z m M  , nếu các phép kiểm tra là độc lập thì:       | 0| ,        i m m M i i i i q x P c x r P z c x r (2.2) Trong đó  là một hằng số chuẩn hóa.               0, 0, | | , 0, 0, |           i i i i i i m m m P c z m M q x P c x z m M P z m M r r r , ∈ , ∈ , , ∈ Tầng (a) (b)
• 56.      1 | 0, | , 0, | i i i i m m P c x P z m M c x P z m M        r r r Do tính độc lập của các bít và nhiễu, xác suất có điều kiện ( | )  i P c x r có thể được viết ( | )  i i P c x r . Với giả thiết các phép kiểm tra là độc lập, xác suất liên kết đối với các phép kiểm tra được coi là hệ số, cho nên:         1 ( ) | 0| , 0, |         i i i i m M m i i m q x P c x r P z c x P z m M r r Hệ số chia của xác suất này có thể được tách ra:           ' | 0| , '| 0| ',             i i m m M m x i i i m i i M i i P c x r P z c x q x P c x r P z c x r r Tức là hệ số là một hằng số chuẩn hóa, ký hiệu là . Trong công thức (2.2), ( ) i q x có hai hệ số xác suất. Hệ số ( 0 | , )     i m i m M P z c x r được gọi là xác suất ngoài. Giống như xác suất ngoài sử dụng trong giải mã Turbo, nó biểu thị khối lượng thông tin về bít i c dựa trên cấu trúc của mã. Hệ số khác trong biểu thức (2.2), ( | ) i i P c r , biểu thị khối lượng thông tin về bít i c dựa trên đầu ra kênh đo được i r tương ứng với i c ; được gọi là xác suất trong. Đặt:     0 | ,    i mi m r x P z c x r (2.3) là xác suất mà phép kiểm tra thứ m được thỏa mãn, được gửi từ bít i c . Phần sau sẽ trình bày cách tính xác suất này. Sử dụng biểu thức (2.3) và Định lý 2.1, ta có:     | ( )      i i i mi m M q x P c x r x r (2.4)