Tài liệu giải mã mềm cho mã khối dựa trên không gian mã đối ngẫu

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ NGUYỄN THỊ HỒNG NHUNG GIẢI MÃ MỀM CHO MÃ KHỐI DỰA TRÊN KHÔNG GIAN MÃ ĐỐI NGẪU LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ HÀ NỘI – NĂM 2019 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ NGUYỄN THỊ HỒNG NHUNG GIẢI MÃ MỀM CHO MÃ KHỐI DỰA TRÊN KHÔNG GIAN MÃ ĐỐI NGẪU Chuyên nghành: Kỹ thuật Điện tử Mã số: 9.52.02.03 LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS VŨ THANH HẢI 2. PGS. TS PHẠM KHẮC HOAN HÀ NỘI – NĂM 2019 i LỜI CAM ĐOAN Tôi 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 18 tháng 01 năm 2019 Tác giả Nguyễn Thị Hồng Nhung ii LỜI CẢM ƠN Trong quá trình học tập, nghiên cứu và hoàn thành Luận án này, tác giả đã nhận đƣợc rất nhiều sự giúp đỡ và đóng góp quý báu từ những ngƣời Thầy tận tâm nhất. Đầu tiên, tác giả xin bày tỏ lòng cảm ơn chân thành tới Thầy giáo hƣớng dẫn PGS. TS Vũ Thanh Hải, PGS. TS Phạm Khắc Hoan đã tận tình hƣớng dẫn và giúp đỡ tác giả trong quá trình nghiên cứu. Đồng thời, tác giả xin gửi lời cảm ơn sâu sắc đến PGS. TS Đinh Thế Cƣờng và TS Phạm Xuân Nghĩa đã có những đóng góp, tƣ vấn quan trọng cho Luận án. 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 Trƣờng Đại học Kinh tế Kỹ thuật Công nghiệp, 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ả iii MỤC LỤC TRANG BÌA PHỤ LỜI CAM ĐOAN ............................................................................................... LỜI CẢM ƠN ..................................................................................................... MỤC LỤC ........................................................................................................... DANH MỤC CHỮ VIẾT TẮT .......................................................................... DANH MỤC HÌNH VẼ ...................................................................................... DANH MỤC BẢNG BIỂU ................................................................................ DANH MỤC KÝ HIỆU TOÁN HỌC ................................................................ MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1. TỔNG QUAN VỀ MÃ KHỐI TUYẾN TÍNH........................... 8 1.1 Mã khối nhị phân tuyến tính .................................................................... 8 1.1.1 Mô hình hệ thống thông tin .............................................................. 8 1.1.2 Ma trận sinh .................................................................................... 10 1.1.3 Ma trận kiểm tra.............................................................................. 12 1.2 Giải mã mã khối .................................................................................... 13 1.2.1 Các phƣơng pháp giải mã mã khối ................................................. 13 1.2.2 Chất lƣợng giải mã ......................................................................... 16 1.3 Các thuật toán giải mã mềm mã khối .................................................... 20 1.3.1 Thuật toán lan truyền niềm tin........................................................ 20 1.3.2 Thuật toán tổng tích ........................................................................ 23 1.4 Đặt vấn đề nghiên cứu ........................................................................... 28 CHƢƠNG 2. GIẢI MÃ MỀM MÃ KHỐI SỬ DỤNG MÃ ĐỐI NGẪU ...... 34 2.1 Mã đối ngẫu ........................................................................................... 34 2.1.1 Giới thiệu mã đối ngẫu ................................................................... 34 2.1.2 Vai trò mã đối ngẫu trong việc mang tin giải mã ........................... 35 iv 2.2 Đề xuất các thuật toán giải mã mềm cho mã khối áp dụng tính chất mang tin của mã đối ngẫu ............................................................................. 38 2.2.1 Thuật toán giải mã mềm mã Hamming dựa trên mã đối ngẫu ....... 38 2.2.2 Thuật toán giải mã Hamming sử dụng từ mã đối ngẫu toàn “0”.... 41 2.2.3 Kết quả mô phỏng và thảo luận về chất lƣợng các thuật toán giải mã mềm BPA – DCS và BPA – DCZ ............................................................ 45 2.3 Giải mã mềm sử dụng mã đối ngẫu ....................................................... 52 2.3.1 Đề xuất thuật toán giải mã cho các mã khối mật độ cao sử dụng mã đối ngẫu..................................................................................................... 53 2.3.2 Đánh giá chất lƣợng thuât toán giải mã dựa trên mã đối ngẫu....... 56 2.4 Kết luận chƣơng .................................................................................... 60 CHƢƠNG 3. GIẢI MÃ MỀM MÃ TÍCH ...................................................... 61 3.1 Mã tích và các đặc điểm ........................................................................ 61 3.1.1 Các tham số cơ bản của mã tích ..................................................... 61 3.1.2 Giải mã mã tích............................................................................... 64 3.2 Đề xuất thuật toán giải mã đối ngẫu mã tích ......................................... 70 3.2.1 Xây dựng cơ sở lý thuyết cho thuật toán giải mã tích mới .......... 71 3.2.2 Thuật toán giải mã mềm mã tích sử dụng mã đối ngẫu ................. 73 3.3 Đánh giá chất lƣợng thuật toán giải mã đối ngẫu mã tích và đề xuất cải tiến ................................................................................................................ 76 3.3.1 Đánh giá chất lƣợng thuật toán giải mã đối ngẫu mã tích .............. 76 3.3.2 Đề xuất thuật toán giải mã đối ngẫu mã tích cải tiến ..................... 82 3.3.3 Độ phức tạp..................................................................................... 86 3.4 Kết luận chƣơng .................................................................................... 88 KẾT LUẬN ..................................................................................................... 90 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ ...................................... 92 TÀI LIỆU THAM KHẢO ............................................................................... 93 v DANH MỤC CHỮ VIẾT TẮT Từ viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt AWGN Tạp âm Gauss trắng cộng tính Additive White Gaussian Noise BCH Bose, Chaudhuri and Mã BCH Hocquenghem BER Bit Error Rate Tỉ lệ lỗi bit BMA Berlekamp- Massey Thuật toán Berlekamp- Massey Algorithm BPA Belief Propagation Algorithm Thuật toán lan truyền niềm tin BPA-DCS Belief Propagation Algorithm Thuật toán lan truyền niềm tin based on Dual Codes dựa trên các mã đối ngẫu BPA – using Dual Code' Thuật toán lan truyền niềm tin codeword of Zeros sử dụng từ mã toàn “0” BPSK Binary Phase Shift Keying Khóa dịch pha nhị phân DCA Dual Codes decoding Thuật toán giải mã đối ngẫu BPA-DCZ Algorithm DCAPC DVB-S2 Dual Codes decoding Thuật toán giải mã đối ngẫu cho Algorithm for Product Codes mã tích Digital Video Broadcasting – Truyền hình số – Vệ tinh – Thế Satellite – Second Generation hệ thứ hai vi FEC Forward Error Correction Sửa lỗi hƣớng đi GF Galois Field Trƣờng Galoa GMD Generalized Minimum Khoảng cách tối thiểu tổng quát Distance HDD Hard Decision Decoding Giải mã quyết định cứng HDPC High-Density Parity Check Mã kiểm tra chẵn lẻ mật độ cao Code LDPC Low - Density Parity Check Mã kiểm tra chẵn lẻ mật độ thấp Code LLR Log Likelihood Ratio Tỉ lệ hợp lẽ theo hàm log MAP Maximum A posteriori Cực đại hóa xác suất hậu Probability nghiệm MAP Decoder Using the Giải mã MAP sử dụng mã đối Dual Code ngẫu MPA Message Passing Algorithm Thuật toán truyền tin MSA Min - Sum Algorithm Thuật toán tổng – cực tiểu MLD Maximum Likelihood Bộ giải mã hợp lẽ cực đại MDUDC Decoder SDD Soft Decision Decoding Giải mã quyết định mềm SIHO Soft Input Hard Output Đầu vào mềm đầu ra cứng vii 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 SOVA Soft Output Viterbi Thuật toán Viterbi đầu ra mềm Algorithm SPA Sum - Product Algorithm Thuật toán tổng- tích VA Viterbi Algorithm Thuật toán Viterbi viii DANH MỤC HÌNH VẼ Hình 1. 1. Hệ thống thông tin số ....................................................................... 8 Hình 1. 2. Nguyên lý về giải mã lặp ............................................................... 14 Hình 1. 3. Cây giải mã độ sâu b ng 1 ............................................................. 15 Hình 1. 4. Cây giải mã độ sâu b ng 2 ............................................................. 15 Hình 1. 5. Chất lƣợng giải mã mềm Hamming (7,4) so với giải mã cứng và không mã hóa trên kênh AWGN, điều chế BPSK [57]. ................................. 18 Hình 1. 6. Chất lƣợng giải mã mềm Hamming (15,11) so với giải mã cứng và không mã hóa trên kênh AWGN, điều chế BPSK [57]. ................................. 19 Hình 1. 7. Quá trình truyền bản tin từ nút bit đến nút kiểm tra và ngƣợc lại. 21 Hình 1. 8. Lƣu đồ thuật toán tổng tích SPA.................................................... 23 Hình 1. 9. Lƣu đồ thuật toán MSA.................................................................. 27 Hình 2. 1. Ma trận kiểm tra và đồ thị Tanner tƣơng ứng của mã Hamming (7,4) ......................................................................................................................... 38 Hình 2. 2. Chất lƣợng giải mã BPA mã Hamming (7,4) ................................ 41 Hình 2. 3. Chất lƣợng giải mã BPA mã Hamming (31,26) ............................ 42 Hình 2. 4. Mô hình hệ thống sử dụng mã Hamming ...................................... 45 Hình 2. 5. So sánh chất lƣợng của mã Hamming (7,4) giữa các thuật toán. .. 46 Hình 2. 6. So sánh chất lƣợng của mã Hamming (15,11) giữa các thuật toán. ......................................................................................................................... 47 Hình 2. 7. So sánh chất lƣợng của mã Hamming (31,26) giữa các thuật toán. ......................................................................................................................... 47 Hình 2. 8. So sánh chất lƣợng của mã Hamming (63,57) giữa các thuật toán. ......................................................................................................................... 48 Hình 2. 9. So sánh BER của mã Hamming (7,4) giữa các thuật toán ............. 49 Hình 2. 10. So sánh BER của mã Hamming (15,11) giữa các thuật toán....... 50 ix Hình 2. 11. So sánh BER của mã Hamming (31,26) giữa các thuật toán....... 50 Hình 2. 12. So sánh BER của mã Hamming (63,57) giữa các thuật toán....... 51 Hình 2. 13. Lƣu đồ thuật toán DCA ................................................................ 55 Hình 2. 14. BER của BPDCA, BPA và HDD cho các mã Hamming............ 56 Hình 2. 15. Chất lƣợng giải mã theo thuật toán DCA, HDD cho các mã Hamming. ........................................................................................................................................58 Hình 2. 16. Chất lƣợng giải mã theo thuật toán DCA, HDD cho mã Golay và Golay mở rộng................................................................................................. 59 Hình 3. 1. Cấu trúc mã tích ............................................................................. 62 Hình 3. 2. Lƣới mã của mã Hamming (7, 4, 3) ............................................... 65 Hình 3. 3. Mô hình giải mã mã tích ................................................................ 67 Hình 3. 4. Lƣu đồ thuật toán giải mã lặp cận tối ƣu ....................................... 69 Hình 3. 5. Lƣu đồ thuật toán giải mã đối ngẫu của mã tích ............................ 74 Hình 3. 6. Lƣu đồ thuật toán giải một hàng hoặc cột của mã tích .................. 75 Hình 3. 7. Chất lƣợng của mã tích 15,11,3 15,11,3 trên kênh AWGN .... 77 Hình 3. 8. Chất lƣợng của mã tích 31,26,3 31,26,3 trên kênh AWGN .... 79 Hình 3. 9. Chất lƣợng mã tích với các mã thành phần có chiều dài khác nhau ......................................................................................................................... 80 Hình 3. 10. So sánh chất lƣợng thuật toán mới với thuật toán MDUDC........ 82 Hình 3. 11. Chất lƣợng thuật toán giải mã lặp đối ngẫu mã tích cải tiến với các tốc độ mã hóa khác nhau........................................................................... 85 Hình 3. 12. Chất lƣợng thuật toán giải mã lặp đối ngẫu mã tích cải tiến ....... 86 x DANH MỤC BẢNG BIỂU Bảng 2. 1. Khảo sát một số trƣờng hợp giải mã sai khi truyền tin áp dụng thuật toán BPA cho mã Hamming 7,4 với ma trận kiểm tra trong Hình 2.1. ......................................................................................................................... 43 Bảng 2. 2. So sánh thời gian trung bình xử lý một từ mã giữa BPA và BPA DCS với các bộ mã Hamming (7,4); (15,11); (31,26) và (63,57).................. 48 Bảng 2. 3. So sánh thời gian trung bình xử lý một từ mã giữa BPA và BPA DCZ với các mã Hamming (7,4); (15,11); (31,26) và (63,57). ..................... 52 Bảng 2. 4. Số lƣợng các vòng kín ngắn trong ma trận , .......................... 57 Bảng 2. 5. So sánh kích thƣớc ma trận kiểm tra và độ lợi mã hóa khi sử dụng thuật toán HDD và DCA. ................................................................................ 59 Bảng 3. 1. Độ phức tạp của các phƣơng pháp giải mã tích ............................ 68 Bảng 3.2. Mối quan hệ giữa tốc độ mã thành phần và độ lợi giải mã ............ 81 Bảng 3. 3. So sánh tốc độ mã khi có và không mã hóa các bit kiểm tra chẵn lẻ ......................................................................................................................... 83 Bảng 3. 4. Độ phức tạp của thuật toán DCAPC và thuật toán cải tiến. .......... 87 Bảng 3. 5. So sánh độ phức tạp của DCAPC và MDUDC. ............................ 87 xi DANH MỤC KÝ HIỆU TOÁN HỌC Ký hiệu Ý nghĩa Chữ thƣờng, in nghiêng Biến số Chữ thƣờng, in đứng, đậm Véc-tơ chứa các biến số Chữ hoa, in đứng, đậm Ma trận chứa các biến số Ví dụ Chiều dài từ mã Số bit tin Số bit kiểm tra Số lần lặp Tốc độ mã hóa Một bit mã Chuỗi phát ̂ ̅ Chuỗi thu Chuỗi sau giải mã Xác suất bản tin đƣợc phát đi Tỷ lệ hợp lẽ của Năng lƣợng bit trung bình Mật độ phổ công suất nhiễu hai phía Phƣơng sai 1 MỞ ĐẦU Mã hóa kênh đóng vai trò vô cùng quan trọng trong kỹ thuật truyền dẫn số do có khả năng sửa và phát hiện lỗi cho phép nâng cao độ tin cậy của hệ thống truyền tin [1], [2], [3], [57]. Trong đó mã khối đã đƣợc nghiên cứu và ứng dụng rộng rãi trong nhiều hệ thống thông tin số [38], [52], [54]. Tuy nhiên, phần lớn các phƣơng pháp giải mã mã khối trƣớc đây còn tồn tại những mặt hạn chế nhƣ chất lƣợng giải mã thấp, độ phức tạp tính toán lớn. Hầu hết, các công trình ban đầu đều đánh đổi chất lƣợng tối ƣu để giảm sự phức tạp giải mã [63], [64]. Trong giải mã khoảng cách tối thiểu tổng quát (GMD) [21], Forney sử dụng bộ giải mã đại số để tạo ra một danh sách các ứng viên. Danh sách này đƣợc xác định từ độ tin cậy của các symbol trong mỗi khối nhận đƣợc. Đối với mỗi ứng viên, sẽ đƣợc kiểm tra xem có đạt điều kiện tối ƣu hay không. Các ứng viên có khả năng nhất sẽ đƣợc chọn làm từ mã đầu ra. Cùng chung ý tƣởng, Chase cung cấp một thuật toán với một số bit đáng tin cậy nhất đƣợc hệ thống tìm ra [15]. Đối với thuật toán này, số lƣợng tối đa các từ mã đƣợc xem xét và chất lƣợng lỗi phụ thuộc vào tập hợp các vị trí đƣợc kiểm tra. Sau đó, thuật toán của Chase đã đƣợc sửa đổi để cho phép tìm kiếm chỉ trên các vị trí tƣơng ứng với độ tin cậy thấp hơn một ngƣỡng ấn định trƣớc [59]. Chất lƣợng lỗi phụ thuộc vào việc lựa chọn ngƣỡng này, đồng thời số lƣợng tối đa tính toán cũng phụ thuộc vào sự lựa chọn ngƣỡng và tỷ lệ tín trên tạp (SNR). Các thuật toán này bị giảm một ít chất lƣợng khi sử dụng với mã kích thƣớc nhỏ, nhƣng khoảng cách về chất lƣợng lỗi so với MLD (Maximum Likelihood Decoder) tăng với cùng kích thƣớc mã [14]. Thuật toán MLD tối ƣu, dựa trên cùng một ý tƣởng đã đƣợc đề xuất trong [71]. Thuật toán này không giới hạn về không gian tìm kiếm nhƣng tại mỗi lần lặp, một không gian 2 mới đủ mạnh cho điều kiện tối ƣu đƣợc đƣa ra. Sau mỗi lần lặp, không gian tìm kiếm cho các từ mã tối ƣu giảm và hội tụ tới một kết quả duy nhất. Do hiệu quả liên quan đến các tiêu chuẩn dừng, thuật toán MLD cải thiện đƣợc độ phức tạp tính toán cho các mã ngắn [15], [70]. Tuy nhiên, độ phức tạp của thuật toán này vẫn tăng cấp số nhân theo kích thƣớc của mã. Các phƣơng pháp khác tận dụng lợi thế của các mã có cấu trúc khai triển đƣợc để giảm sự phức tạp trong giải mã lƣới [22], [47]. Tuy nhiên sự phức tạp của lƣới mã vẫn phát triển theo cấp số nhân với kích thƣớc mã [5]. Để duy trì số lƣợng tính toán có thể kiểm soát, nhiều bộ giải mã cận tối ƣu đa tầng dựa trên cấu trúc lƣới mã đã đƣợc đƣa ra [37]. Với phƣơng pháp giải mã tối ƣu ở trên, việc lƣu trữ các kết quả tốt có thể dẫn đến nhiều tìm kiếm và tính toán không cần thiết. Từ đó, một cách tiếp cận khác đƣợc đề xuất: Đối với phạm vi tỉ lệ lỗi bit (BER: Bit Error Rate) nhất định, ta chỉ cần đảm bảo chất lƣợng lỗi kết hợp với MLD. Vì vậy, tồn tại hai vấn đề đối với từ mã quyết định khác từ mã MLD tối ƣu. Đầu tiên, từ mã MLD là chính xác và từ mã đƣợc giải bị lỗi, nhƣng trƣờng hợp này không đủ để làm cho chất lƣợng lỗi tối ƣu bị suy giảm đáng kể. Thứ hai, cả hai đều bị lỗi, trong trƣờng hợp này chất lƣợng tối ƣu cũng không bị giảm. Thuật toán này không phải là tối ƣu, nhƣng thực sự không có sự khác biệt về chất lƣợng lỗi so với khi giải mã MLD. Trong khi đó, nhiều tính toán không cần thiết đƣợc lƣu lại. Bất cứ khi nào chất lƣợng tối ƣu bị giảm không đáng kể, chúng ta xem chất lƣợng lỗi thu đƣợc trên thực tế là tối ƣu với BER xác định. Thuật toán đƣợc đề xuất bao gồm ba bƣớc: 1) Sắp xếp lại các symbol của một chuỗi nhận đƣợc dựa trên độ tin cậy nhƣ trong [34]. 2) Giải mã cứng cho chuỗi nhận đƣợc đã sắp xếp lại, chuỗi tin cung cấp một từ mã dự kiến sẽ có ít bit thông tin bị lỗi nhất có thể và 3) cải tiến việc giải mã cứng dần dần theo từng giai đoạn cho đến khi đạt chất lƣợng lỗi tối ƣu thực tế hoặc chất lƣợng 3 lỗi mong muốn. Các giai đoạn này thực hiện trực tiếp từ các số liệu thống kê sau khi sắp xếp theo xác suất lỗi symbol, làm tăng chất lƣợng giải mã tại mỗi bƣớc. Sự hội tụ nhanh chóng từ mã MLD có thể quan sát thấy trong hầu hết các trƣờng hợp, kết quả là lƣợng tính toán rất thấp. Một tính năng khác của thuật toán là sau mỗi giai đoạn, chúng ta có thể có liên kết chặt chẽ chất lƣợng lỗi đạt đƣợc dựa trên các số liệu thống kê các lệnh. Điều này cho phép xác định số lƣợng các giai đoạn cần thiết để giải mã một mã nhất định đến một BER cụ thể và đánh giá chính xác số lƣợng tối đa các tính toán cần thiết cho trƣờng hợp xấu nhất. Đây là yếu tố rất quan trọng, vì nhiều thuật toán giải mã tối ƣu hoặc cận tối ƣu, mặc dù thực hiện với số lƣợng tính toán trung bình thấp, nhƣng lại có một trƣờng hợp tồi nhất với số lƣợng tính toán cực kỳ cao và rất khó để đánh giá chính xác, chẳng hạn nhƣ các thuật toán [34], [71]. Hơn nữa, các thuật toán đề xuất không yêu cầu lƣu trữ các từ mã còn lại hoặc từ mã ứng viên cho quyết định cuối cùng. Nhiều nhà nghiên cứu đã xem xét đến vấn đề của việc giải mã ngoài giới hạn khoảng cách tối thiểu của mã. Cách tiếp cận này có thể là chọn xây dựng một mã đơn giản, thƣờng là sự kết nối của hai mã trở lên và cố gắng giải mã ngoài một nửa khoảng cách tối thiểu [7], [23], [24]. Một cách rất hay về hƣớng này đƣợc đƣa ra bởi Glavieux và Berrou với hai mã chập kết nối song song đƣợc gọi là mã Turbo [11], [12]. Sau đó ngƣời ta phát hiện r ng Gallager trong một báo cáo trƣớc đó đã đƣa ra ý tƣởng tƣơng tự gọi là mã kiểm tra chẵn lẻ mật độ thấp (LDPC: Low Density Parity Check) [27]. Bộ giải mã LDPC sử dụng thuật toán giải mã lặp do Gallager đề xuất có tên gọi là lan truyền niềm tin BPA (Belief Propagation Algorithm) hay chuyển tin MPA (Message Passing Algorithm) có chất lƣợng cao, thời gian giải mã lâu, chỉ ứng dụng với các mã trung bình và dài [17], [68]. 4 Các mã LDPC có ƣu điểm so với các mã Turbo: độ phức tạp tính toán thấp hơn; Khảo sát thực nghiệm cho thấy, tất cả các lỗi đều đƣợc phát hiện; các phƣơng pháp giải mã đơn giản hơn [74]. Do vậy, các mã LDPC là ứng cử viên triển vọng cho các hệ thống mã sửa lỗi hƣớng đi FEC: Forward Error Correction và đƣợc chấp nhận bởi nhiều tiêu chuẩn tiên tiến nhƣ Ethernet 10 Gigabit (10GBASE - T) và truyền hình số (DVB - S2: Digital Video Broadcasting – Satellite – Second Generation). Tuy nhiên, những nhƣợc điểm nhƣ các mã có chất lƣợng tốt nhất là các mã rất dài. Do chiều dài khối lớn, tốc độ mã thấp và sử dụng giải mã lặp nên LDPC chƣa phù hợp với các hệ thống truyền tin có độ trễ thấp. Mặt khác, ma trận sinh 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ã [4], [67]. Với các hệ thống truyền tin tốc độ cao, độ trễ thấp hiện nay, mã LDPC chƣa là lựa chọn hợp lý có thể thay thế mã Turbo. Mã Turbo là sự kết nối gồm hai hay nhiều bộ mã chập riêng biệt để tạo ra một mã tốt hơn và cũng lớn hơn. Mã Turbo yêu cầu giải mã MAP (Maximum A posteriori Probability) trên lƣới của các mã thành phần nên độ phức tạp rất lớn chỉ có thể áp dụng cho các mã ngắn [9], [69], [65]. Mã tích (Product Codes) có khoảng cách mã lớn đƣợc xây dựng từ các mã thành phần có độ dài và khoảng cách mã nhỏ cho phép đạt chất lƣợng và độ phức tạp có thể so sánh với mã Turbo với số vòng lặp giải mã nhỏ hơn [6], [58]. Có nhiều thuật toán giải mã mã tích đã đƣợc trình bày từ khi mã tích đƣợc biết đến [42], [60], [65],... Các thuật toán này nhìn chung phân làm hai loại: Các thuật toán đơn giản cho chất lƣợng giải mã thấp và các thuật toán cho chất lƣợng giải mã cao nhƣng có độ phức tạp rất cao. Phƣơng pháp giải mã Viterbi đầu ra mềm (gần giống với giải mã MAP) cho mã thành phần, trên mã đối ngẫu, nh m giảm độ phức tạp mã tích, đem lại chất lƣợng giải mã cao 5 nhƣng độ phức tạp vẫn quá lớn và không có tính khả dụng [30], [77]. Nghiên cứu, đề xuất bộ giải mã hiệu quả cho các mã thành phần đáp ứng đƣợc các tiêu chí nhƣ chất lƣợng kiểm soát lỗi cao, thuật toán đơn giản phù hợp cấu trúc mã tích là vấn đề quan trọng để có thể tận dụng khả năng sửa lỗi của mã tích. Theo các nghiên cứu trƣớc đây, giải mã quyết định mềm cho phép nâng cao chất lƣợng giải mã, nhƣng vẫn cần có những cải tiến để giảm độ phức tạp nhất là khi sử dụng cho các mã có cấu trúc liên kết nhƣ mã tích [8], [10], [13], [51],.. Mã tích chính là mã khối dài có thể đƣợc xây dựng bởi hai hay nhiều mã khối thành phần ngắn hơn. Mã tích có tốc độ mã hóa b ng tích các mã thành phần nên việc lựa chọn các mã thành phần là các mã khối có tốc độ mã hóa cao là ý tƣởng hợp lý. Với các mã có tỉ lệ mã hóa cao, vấn đề giải mã b ng mã đối ngẫu sẽ giảm đƣợc sự phức tạp mà vẫn đảm bảo thông tin giải mã nhƣ mã gốc [30], [44], [55]. Đây chính là lý do lựa chọn đề tài “Giải mã mềm cho mã khối dựa trên không gian mã đối ngẫu”. Trong quá trình nghiên cứu, tìm hiểu các phƣơng pháp giải mã mềm và đƣa ra các phƣơng án giải mã với lập luận chắc chắn và đánh giá tin cậy, Luận án hƣớng đến việc xây dựng đƣợc thuật toán giải mã mới nh m nâng cao chất lƣợng giải mã của mã khối để có thể tận dụng khả năng kiểm soát lỗi của mã tích. Mục đích nghiên cứu: - Đề xuất các thuật toán giải mã mềm mới cho mã khối có độ phức tạp thấp, chất lƣợng giải mã tốt. - Đề xuất các thuật toán giải mã mềm cho các mã khối thành phần của mã tích với khả năng ứng dụng thực tế. Nhiệm vụ nghiên cứu: - Nghiên cứu mã khối và các thuật toán giải mã mềm cho mã khối 6 - Nghiên cứu các thuật toán giải mã mã kênh có chất lƣợng giải mã cao. - Nghiên cứu mã tích với mã thành phần là các mã khối và các thuật toán giải mã. Phương pháp nghiên cứu Sử dụng phƣơng pháp phân tích lý thuyết trong mã kênh, đề xuất các - thuật toán giải mã mềm cho mã khối. Sử dụng kỹ thuật mô phỏng Monte-Carlo trên Matlab để kiểm chứng các - kết quả nghiên cứu. Ý nghĩa khoa học và thực tiễn: Trong thiết kế hệ thống thông tin, đặc biệt trong hệ thống không dây Wifi, WiMax,… Giải mã quyết định cứng đƣợc xem là giải mã tiềm năng, giải mã quyết định mềm đƣợc xem là giải mã tình thế. Bởi vậy, có thể thấy giải mã quyết định mềm hiệu quả hơn nhƣng phức tạp hơn giải mã quyết định cứng và sự phức tạp của bộ giải mã là trở ngại chính trong việc sử dụng các mã mạnh. Điều này là do, trong hầu hết các trƣờng hợp, hệ thống truyền dẫn đƣợc thiết kế phải rẻ và không yêu cầu tiêu thụ nhiều công suất. Mặt khác, sử dụng mã mạnh trong việc truyền sẽ làm giảm khả năng gửi lại dữ liệu khi nhiễu quá lớn. Hai họ mã kênh mạnh nhất hiện nay là LDPC và Turbo sử dụng các thuật toán giải mã mềm nhƣ BPA, SOVA,... cho chất lƣợng kiểm soát lỗi rất tốt. Tuy nhiên, các bộ mã này vẫn còn nhƣợc điểm nhƣ thời gian giải mã lâu (LDPC), hệ thống phức tạp Turbo , khó đáp ứng các hệ thống truyền tin tốc độ cao, độ trễ thấp, thời gian thực (ví dụ các mạng cảm biến vô tuyến, IoT,...). Vấn đề quan trọng là nghiên cứu, đề xuất các thuật toán giải mã mềm nhận thông tin giải mã trong không gian mã đối ngẫu, có cơ sở lý thuyết chắc chắn, đồng thời đề xuất ứng dụng cho họ mã cụ thể, nhƣ mã tích với các mã thành phần là mã khối mật độ cao nh m giảm độ phức tạp, đạt chất lƣợng cao,... Đề tài nghiên cứu của Luận án có ý nghĩa khoa học và phù hợp nhu cầu thực tiễn của các hệ thống truyền dẫn 7 vô tuyến thời gian thực. Các thuật toán đề xuất đều đƣợc đánh giá về độ phức tạp và mô phỏng so sánh chất lƣợng với các thuật toán đã đƣợc công bố để khẳng định tính đúng đắn, khả năng phát triển và ứng dụng. Bố cục của Luận án: Luận án đƣợc trình bày gồm 3 chƣơng với các nội dung chính nhƣ sau: - Chương 1: Trình bày tổng quan về mã khối tuyến tính với các phƣơng pháp giải mã khối nhƣ giải mã cứng, giải mã mềm,...Tìm hiểu các thuật toán giải mã mềm nhƣ BPA, ...phù hợp với các mã mật độ thấp. Đặt vấn đề tình hình nghiên cứu liên quan đến đề tài. - Chương 2: Nghiên cứu các hƣớng phát triển của đề tài liên quan đến giải mã mềm cho mã khối từ vai trò mang tin của mã đối ngẫu. Đề xuất các thuật toán giải mã mềm cho mã khối dựa trên tính chất chứa thông tin giải mã của mã đối ngẫu. Đánh giá chất lƣợng các thuật toán đƣợc đề xuất để đƣa ra hƣớng nghiên cứu tiếp theo của Luận án với mục đích tìm kiếm đƣợc phƣơng án giải mã mềm tốt cho mã khối nh m nâng cao khả năng kiểm soát lỗi kênh với độ phức tạp thấp. - Chương 3: Phân tích, đánh giá một số thuật toán giải mã mã tích. Đƣa ra các vấn đề còn tồn tại, hƣớng cần tập trung giải quyết và phát triển của Luận án. Đi sâu vào việc kiểm soát lỗi kênh nhờ sử dụng mã tích với các mã khối mật độ cao làm mã thành phần và dùng thuật toán mềm liên quan đến việc vét cạn thông tin giải mã trong mã đối ngẫu với mã gốc. Lập luận, xây dựng cơ sở lý thuyết cho các thuật toán giải mã mềm của các mã khối thành phần của mã tích. Đánh giá chất lƣợng các thuật toán đề xuất và so sánh với các công trình đã đƣợc công bố.