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

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 ngành: Kỹ thuật Điện tử Mã số: 9.52.02.03 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI – NĂM 2019 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUẬT QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. PGS. TS VŨ THANH HẢI 2. PGS. TS PHẠM KHẮC HOAN Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện theo quyết định số……/….., ngày …..tháng…..năm……của Giám đốc Học viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật Quân sự vào hồi……giờ…ngày….tháng….năm…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Kỹ thuật Quân sự - Thư viện Quốc gia 1 MỞ ĐẦU Một trong các giải pháp nhằm góp phần khai thác tối đa khả năng truyền dẫn của kênh là sử dụng các loại mã kênh có đặc tính tự sửa sai. Mã kênh có thể phân làm 2 loại là mã khối và mã chập, đại diện bởi hai họ mã mạnh và sử dụng phổ biến hiện nay là mã Turbo và LDPC (Low Density Parity Check). LDPC hiện đang dần thay thế Turbo trong một số hệ thống truyền tin số nhờ các ưu điểm: chất lượng giải mã cao, độ phức tạp tính toán thấp với phương pháp giải mã đơn giản. LDPC không phù hợp với các hệ thống truyền tin yêu cầu thời gian thực với tốc độ cao và độ trễ thấp nên LDPC chưa phải là lựa chọn thay thế hợp lý cho mã Turbo trong các hệ thống này. 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. Nhược điểm là độ phức tạp rất lớn, tốc độ mã tỉ lệ nghịch với chất lượng mã. Điều này làm giảm tính khả dụng của mã Turbo trong các hệ thống truyền tin yêu cầu độ trễ thấp. 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. 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. 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 2 mã tích, đem lại chất lượng giải mã cao nhưng độ phức tạp vẫn quá lớn và không có tính khả dụng. 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. 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. Đâ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, 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 - 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. 3 - 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: Vấn đề quan trọng hiện nay 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. Kết quả đạt được của luận án có thể là giải pháp thay thế cho các kỹ thuật FEC hiện đại mang tính thực tiễn cao trong các hệ thống truyền dẫn vô tuyến, đặc biệt là các dịch vụ thời gian thực. Bố cục của Luận án: Luận án được trình bày gồm 3 chương Chương 1: Trình bày tổng quan về các phương pháp giải mã khối. Chương 2: Nghiên cứu, đánh giá 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, đưa ra hướng nghiên cứu tiếp theo của Luận án. Chương 3: 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ố. Chương 1. TỔNG QUAN VỀ MÃ KHỐI TUYẾN TÍNH Mã hóa kênh đóng vai trò vô cùng quan trọng trong kỹ thuật truyền dẫn thông tin số, trong đó mã khối là họ mã có khả năng sửa và phát hiện lỗi khá tốt đảm bảo độ chính xác cho hệ thống truyền tin. 1.1 Mã khối nhị phân tuyến tính 1.1.1 Mô hình hệ thống thông tin Một hệ thống thông tin số được thể hiện theo sơ đồ khối Hình 1.1. 4 𝐮 Nguồn Mã hóa kênh 𝐜 𝐱 Điều chế Kênh truyền 𝐮 Đích 𝐜′ Giải mã kênh 𝐲 Giải điều chế Hình 1. 1. Hệ thống thông tin số 1.1.2 Ma trận sinh Mã tuyến tính không gian véctơ là một không gian con chiều của một thành phần. Do vậy có thể tìm được từ mã độc lập tuyến tính trong , sao cho: Với { sinh của mã c u1 g1 u2 g2 } và u g g1 , g2 , (1.1) ,g là ma trận . 1.1.3 Ma trận kiểm tra Đối với một ma trận sinh bất kỳ tính, tồn tại một ma trận Do đó, một tổ hợp gồm được tạo ra bởi ma trận sinh có có hàng độc lập tuyến hàng độc lập tuyến tính. thành phần là một từ mã hợp lệ của mã khi và chỉ khi: [ ] (1.5) 1.2 Giải mã mã khối. 1.2.1 Các phương pháp giải mã mã khối a) Giải mã quyết định cứng Phương pháp giải mã đơn giản nhất là giải mã quyết định cứng (HDD: Hard Decision Decoding). Để thuận tiện, trong Luận án gọi tắt HDD là giải mã cứng. b) Giải mã quyết định mềm 5 Giải mã tính đến thông tin tin cậy hoặc sử dụng các giá trị xác suất hay giá trị hợp lý (likelihood) thay vì dữ liệu được lượng tử hóa tại đầu vào bộ giải mã được gọi là giải mã quyết định mềm (SDD: Soft Decision Decoding) - Gọi tắt là giải mã mềm. Giải mã lặp là kỹ thuật sử dụng thuật toán giải mã đầu ra mềm được lặp lại nhiều lần trước khi cho kết quả giải mã cuối cùng, nhằm cải thiện xác suất lỗi của hệ thống mã hóa. Thông tin bên ngoài (tới bước lặp tiếp theo) Thông tin từ kênh Một bước lặp của thuật toán (Thông tin nội tại) Thông tin bên ngoài (từ bước lặp trước đó Hình 1. 2. Nguyên lý về giải mã lặp 1.2.2 Chất lượng giải mã a) Chất lượng giải mã mềm Đối với việc xác định chất lượng giải mã, sử dụng công thức giới hạn liên kết union bound . Xác suất phát hiện lỗi cho một symbol từ mã trong với không gian truyền có giới hạn: ⁄ 1.6 Xác suất lỗi symbol khi giải mã mềm là [40]: ( ) Xác xuất lỗi symbol gồm (√ ⁄ ) 1.9 bit không mã là: (√ Vậy, Độ lợi mã hóa tiệm cận ) (1.10) 6 b) Chất lượng giải mã cứng Trường hợp giải mã cứng với xác suất lỗi bit là: ⁄ . Ta có giới hạn xác xuất lỗi symbol là: √ ( ) (1.14) Trường hợp không mã : . (1.15) √ So sánh hai trường hợp giải mã cứng và không mã, bỏ qua các hệ số, độ lợi đạt được của mã cứng là Độ lợi mã hóa tiệm cận (1.16) Hay độ lợi của giải mã mềm so với giải mã cứng là: Độ lợi mã hóa tiệm cận (1.17) Công thức 1.17 chứng minh giải mã mềm tốt hơn giải mã cứng. 1.3 Các thuật toán giải mã mềm mã khối 1.3.1 Thuật toán lan truyền niềm tin Đầu vào bộ giải mã BPA là tỷ lệ ước lượng theo hàm log: ′ ′ 1.18 ( ) ′ Thuật toán BPA là thuật toán giải mã lặp có hai bước chính: Bước 1: Cập nhật bản tin cho tất cả các nút kiểm tra và gửi bản tin ( ) từ nút kiểm tra tới các nút bit nối với nó. Bước 2: Cập nhật bản tin cho tất cả các nút bit và gửi bản tin ( ) từ các nút bit tới nút các kiểm tra nối với nó. Đầu ra của bộ giải mã là giá trị LLR của các bit mã được sử dụng để quyết định thành từ mã thăm dò ̅. Nếu thỏa mãn điều kiện: ̅ [ ] (1.19) thì dừng lặp và đưa ra từ mã hợp lệ ̅. Nếu không, thực hiện lại đến khi đạt số lần lặp cực đại thì dừng và đưa ra từ mã tại lần lặp cuối. 1.3.2 Thuật toán tổng tích Thuật toán tổng tích SPA có thể miêu tả qua 5 bước, thể hiện trên lưu đồ thuật toán trình bày ở Hình 1.8. 7 Đọc vectơ nhận 𝑦𝑖 và số vòng lặp cực đại 𝑛 Bắt đầu Khởi tạo [𝑐𝑖 𝑦𝑖 ] và [𝑐𝑖 𝑦𝑖 ] Khởi tạo 𝑞𝑖𝑗 ] và 𝑞𝑖𝑗 𝑖 Tính toán bản tin 𝑟𝑗𝑖 𝑏 và 𝑞𝑖𝑗 𝑏 𝑖 𝑖 𝑄𝑖 Tính toán 𝑄𝑖 𝑏 [𝑐𝑖 𝑏 𝑦𝑖 và các bản tin đã qua] S ≥ 𝑄𝑖 𝑐̅𝑖 Đ 𝑐̅𝑖 Cho tất cả 𝑖 S 𝐜̅ 𝐇 𝑇 Đ Kết thúc Hình 1. 8. Lưu đồ thuật toán tổng tích SPA 1.3.3 Thuật toán tổng cực tiểu Giai đoạn 1 𝑖 𝐿(𝑞𝑖𝑗 ) Đ 𝑖 >0 < 𝑞𝑖𝑗 𝑞𝑖𝑗 𝑙𝑜𝑔 𝑐̅𝑖 Đ 𝑖<𝑛 1 𝑖<𝑛 S 𝐿(𝑟𝑗𝑖 ) 𝑐̅𝑖 𝐿 𝑄𝑖 S 𝛼𝑖 ′ 𝑗 𝛽𝑖 ′ 𝑗 𝑖′ S 𝐜̅ 𝐇 1 𝑇 Đ 𝐿(𝑞𝑖𝑗 ) 𝐿 𝑐𝑖 𝐿(𝑟𝑗 ′ 𝑖 ) 𝑗 ′ ∈𝐶𝑖~𝑗 𝐿 𝑄𝑖 𝐿 𝑐𝑖 Kết thúc 𝐿(𝑟𝑗 ′ 𝑖 ) 𝑗∈𝐶𝑖 Hình 1. 9. Lưu đồ thuật toán MSA Lưu đồ thuật toán MSA được trình bày trong Hình 1.9. 8 1.4 Đặt vấn đề nghiên cứu Năm 1971, 1974: Phương pháp giải mã Viterbi có độ phức tạp tăng theo cấp số nhân với kích thước mã. Năm 1993, Giải mã Turbo (sử dụng MAP cho mã thành phần) được giới thiệu và nghiên cứu triển khai cho mã tích. Số lượng phép tính gấp 4 lần VA. Năm 1996, Hagenauer đề xuất Thuật toán VA đầu ra mềm (SOVA), gần giống MAP trên mã đối ngẫu giải mã cho mã tích. Chất lượng giải mã cao, độ phức tạp quá lớn. Năm 1998, Pyndiah cải tiến MAP cho các mã thành phần. Chất lượng xấp xỉ giải mã Turbo và giải mã Map cho mã tích. Tuy nhiên, chưa chứng minh được bằng cơ sở lý thuyết, rất khó phân tích nên việc cải thiện hay áp dụng cho các mã khác không khả thi Năm 2003, Al- Askary đưa ra thuật toán lặp cận tối ưu mới cho mã tích nhằm tránh giải mã MAP của mã thành phần. Độ phức tạp còn cao, sự bế tắc là chưa có bộ giải mã thành phần hiệu quả. Như vậy, vấn đề quan trọng nhất là tìm một thuật toán cho mã tích với độ phức tạp thấp, có cơ sở lý thuyết đầy đủ và đảm bảo ưu điểm kiểm soát lỗi tốt của mã tích vẫn chưa được giải quyết. Từ những phân tích này, Luận án cần giải quyết một số vấn đề: Thứ nhất: Đưa ra thuật toán giải mã sử dụng nhiều từ mã đối ngẫu hình thành nên các ma trận kiểm tra khác nhau nhằm cải thiện thông tin ngoại lai qua mỗi vòng lặp. Ngoài ra, có thể đề xuất thuật toán tận dụng từ mã đối ngẫu toàn “0” để giải mã với mục đích giảm số vòng kín ngắn trên đồ hình Tanner. Thứ hai: Quét toàn bộ thông tin trong bộ mã đối ngẫu tương ứng nhằm đạt được lượng tin quyết định từ mã đầu ra là lớn nhất. Thứ ba: Mã tích có hiệu quả kiểm soát lỗi cao nhưng vẫn còn bất cập về độ phức tạp hay chưa có bộ giải mã các mã thành phần phù hợp. Như vậy, ý tưởng quan trọng là kết hợp ưu điểm về khả năng kiểm soát lỗi cao của mã tích và tận dụng tính chất mang tin giải mã của mã đối ngẫu của các mã thành phần để giải mã mã tích. 9 Chương 2. GIẢI MÃ MỀM MÃ KHỐI SỬ DỤNG MÃ ĐỐI NGẪU Kết quả nghiên cứu được công bố ở công trình số 1, 2, 3 và 4. 2.1 Mã đối ngẫu 2.1.1 Giới thiệu mã đối ngẫu a) Định nghĩa: Cho một mã tuyến tính thuộc trường Galoa , khi đó mã đối ngẫu ′ gồm tất cả các vectơ ′ có: { }}, (2.1) { ′∈ | b) Phân bố trọng số Phân bố trọng số của mã có vai trò quan trọng trong việc tính toán xác suất lỗi. , lần lượt là hàm phân bố trọng số của , ′ và có mối quan hệ dựa vào định lý MacWilliams. 2.1.2 Vai trò mã đối ngẫu trong việc mang tin giải mã Đối với mã khối tuyến tính, mỗi bit mã trong các từ mã đối ngẫu đều chứa các thông tin về các bit mã trong các từ mã gốc. Đồng thời, từ mã đối ngẫu toàn “0” cũng mang thông tin từ mã gốc. 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 2.2.1 Thuật toán giải mã mềm mã Hamming dựa trên mã đối ngẫu BPA– DCS (Belief Propagation Algorithm based on Dual Codes) sẽ sử dụng tại mỗi vòng lặp một ma trận kiểm tra khác nhau để thông tin ngoại lai ở vòng lặp trước đưa tới vòng lặp sau trong quá trình giải mã luôn được cải thiện, giúp khắc phục vấn đề “vòng kín ngắn”. a) uan h gi a ma t n i m t a v đ h nh anne 0 0 0 1 1 1 1 𝑐 𝑐3 𝑐2 𝑐4 𝑐5 𝑐6 [ 0 1 1 0 0 1 1] 𝑐7 𝑛 1 0 1 0 1 0 1 𝑓 Hình 2. 1. Ma trận kiểm tra 𝑓2 𝑓3 và đồ thị Tanner tương ứng của mã Hamming 7,4 7 10 b) d ng c c ma t n i m t a tư ng đư ng Ma trận kiểm tra tương đương được xây dựng từ mã đối ngẫu. c) d ng thu t toán giải mã mềm d a trên các ma tr n ki m tra tư ng đư ng Khởi tạo: Tính LLR cho các nút bit , đặt: 2.12 ( ) Giai đoạn 1: Thực hiện giải mã như trong vòng lặp thứ 1 của thuật toán BPA, nếu không thỏa mãn (1.19), chuyển sang giai đoạn 2. Giai đoạn 2: Thay thế các hàng của ma trận kiểm tra bằng cách lấy hàng đó cộng với hàng tiếp theo được và thực hiện lại giai đoạn 1 với lần lặp sử dụng ,... tiếp tục thực hiện đến khi tìm được từ mã hợp lệ hoặc hết . Luôn kiểm tra điều kiện (1.19) Thuật toán BPA– DCS có chất lượng cải thiện so với BPA, tuy nhiên thời gian cũng như số lượng phép tính lại tăng. 2.2.2 Thuật toán giải mã Hamming sử dụng từ mã đối ngẫu toàn “0” Mã Hamming là mã khối mật độ cao nên khi áp dụng thuật toán BPA sẽ không nâng cao được chất lượng giải mã thậm chí còn kém hơn thuật toán giải mã cứng khi chiều dài từ mã tăng. a) Đ nh gi hi u quả thu t to n BPA giải mã mã Hamming Xét mã Hamming 7 và , điều chế BPSK lý tưởng, kênh tạp trắng cộng tính. BER tai cac vong lap cua thuat toan BPA BER tai cac vong lap cua thuat toan BPA -4 10 BER Hamming (7,4) tren kenh Gauss -4.3 10 BER Hamming (31,26) tren kenh Gauss -4.4 10 -4.5 BER BER 10 -5 10 -4.6 10 -4.7 10 -4.8 10 -6 0 5 10 15 20 So vong lap 25 30 35 Hình 2. 2. Chất lượng giải mã BPA mã Hamming (7,4) 40 10 0 5 10 15 20 So vong lap 25 30 35 Hình 2. 3. Chất lượng giải mã BPA mã Hamming (31,26) 40 11 Kết quả Hình 2.2, Hình 2.3 cho nhận xét: từ lần lặp thứ 5 trở đi chất lượng giải mã cải thiện không đáng kể thậm chí còn kém hơn. b) Thu t toán giải mã mềm t ên c sở sử dụng từ mã đối ngẫu to n “0” Các bit kiểm tra có độ tin cậy thấp dễ dẫn đến cho thông tin giải mã kém tin cậy ví dụ ở Bảng 2.1). 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. Từ mã truyền 2 3 4 5 6 7 Giải mã ̅ 2̅ 3̅ 4̅ 5̅ 6̅ 7̅ tương ứng của 1000110 1010101 1,6135 0,4291 0,2058 0100011 0000000 0,7926 0,1699 1,2368 1110010 0110011 0,5954 1,3045 0,5954 0010111 0000000 1,9698 1,2849 0,9531 0000000 0011001 0,9755 0,1815 0,2757 1000110 1001100 3,1042 0,3243 1,4366 0100011 1000011 1,4595 0,1384 1,2582 0011010 0000000 0,7883 1,1208 0,4190 0111001 0101010 0,4912 0,4786 0,0539 2 3 Như vậy, chỉ nhận thông tin từ các bit kiểm tra có độ tin cậy cao. Thuật toán BPA– DCZ (BPA– using Dual Code’ codeword of Zeros được thực hiện như sau: Bước 1: Thực hiện giải mã theo thuật toán BPA dùng ma trận kiểm tra với số lần lặp . Tại mỗi vòng lặp đều kiểm tra điều kiện 1.19 , nếu thỏa mãn thì đưa ra từ mã tương ứng, nếu không sẽ tiếp tục giải mã đến vòng lặp tối đa và chuyển sang bước 2. Bước 2: Xác định nút kiểm tra có giá trị nhỏ nhất và thực hiện thay thế hàng trong ma trận ứng với vị trí bit kiểm tra có độ tin cậy thấp nhất đó bằng từ mã đối ngẫu toàn “0”. Bước 3: Giải mã lại theo BPA với mới được xây dựng ở bước 2,... tiếp tục thực hiện đến khi tìm được từ mã hợp lệ hoặc hết . 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 - BPA– DCS: Thực hiện mô phỏng đánh giá chất lượng giải mã của BPA– DCS, với thuật toán giải mã cứng, BPA, cho kết quả trên Hình 2.5, Hình 2.6, Hình 2.7 và Hình 2.8. BPA– DCS ứng dụng cho các mã 12 4 Hamming có > 7 tại cho phép nâng cao chất lượng khoảng 0,75 dB đến 1,05 dB so với thuật toán giải mã cứng; 0,3 dB đến 0,45 dB so với BPA khi thực hiện cùng số vòng lặp. BER Hamming (7,4) tren kenh Gauss 0 BER Hamming (15,11) tren kenh Gauss 0 10 10 giai ma cung BPA BPA-DCS -1 10 giai ma cung BPA BPA-DCS -1 10 -2 10 -2 BER BER 10 -3 10 -3 10 -4 10 -4 10 -5 10 -5 10 -6 0 1 2 3 4 EbN0[dB] 𝐸𝑏 𝑁 5 6 7 10 8 0 1 2 3 4 EbN0[dB] 𝐸𝑏 𝑁 (dB) 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. 5 6 7 8 (dB) 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. Thuật toán BPA– DCS cần thêm phép cộng modulo 2 trong mỗi vòng lặp và độ phức tạp tăng tối đa so với BPA là , nên thời gian giải mã lâu hơn Bảng 2.2 . BER Hamming (31,26) tren kenh Gauss 0 10 giai ma cung BPA BPA-DCS -1 10 -2 -2 10 -3 -3 10 10 BER BER giai ma cung BPA BPA-DCS -1 10 10 -4 10 -4 10 -5 -5 10 10 -6 -6 10 10 -7 10 BER Hamming (63, 57) tren kenh Gauss 0 10 -7 0 1 2 3 4 5 EbN0[dB] 𝐸𝑏 𝑁 (dB) 6 7 8 10 0 1 2 3 4 EbN0[dB] 𝐸𝑏 𝑁 5 6 7 8 (dB) Hình 2. 7. So sánh chất lượng của mã Hình 2. 8. So sánh chất lượng của mã Hamming 31,26 giữa các thuật toán. Hamming 63,57 giữa các thuật toán. 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). Tỷ lệ thời gian của thuật toán Bộ mã BPA BPA– DCS BPA– DCS so với BPA C (7,4) 0,4453 ms 1,1297 ms 253,69 % C (15,11) C (31,26) C(63,57) 0,8540 ms 2,8901 ms 15,4322 ms 2,0961 ms 6,8318 ms 33,101 ms 245,445 % 236,386 % 214,493 % 13 - BPA– DCZ: Mô phỏng đánh giá chất lượng của BPA– DCZ với các thuật toán giải mã cứng, BPA, BPA tối ưu với cùng thông tin đầu vào, cho kết quả trên Hình 2.9, Hình 2.10, Hình 2.11 và Hình 2.12 [32]. BER Hamming(7,4) tren kenh Gauss 0 10 giai ma cung BPA BPA-toiuu BPA-DCZ -1 10 -2 -2 10 BER BER giai ma cung BPA BPA-toiuu BPA-DCZ -1 10 10 -3 10 -4 -3 10 -4 10 10 -5 -5 10 10 -6 10 BER Hamming(15,11) tren kenh Gauss 0 10 -6 0 1 2 3 4 5 EbN0[dB] 𝐸𝑏 𝑁 (dB) 6 7 10 8 Hình 2. 9. So sánh BER của mã Hamming 7,4 giữa các thuật toán 0 1 2 3 4 5 EbN0[dB] 𝐸𝑏 𝑁 (dB) 6 7 8 Hình 2. 10. So sánh BER của mã Hamming (15,11) giữa các thuật toán Với các mã Hamming (15,11); (31,26) và (63,57), BPA– DCZ 4 cho độ lợi tương ứng 0,3 dB; 0,45 dB; 0,65 dB tại so với BPA. Nghĩa là từ mã càng dài, thuật toán mới càng cải thiện chất lượng nhiều hơn so với BPA. BER Hamming (31,26) tren kenh Gauss 0 giai ma cung BPA BPA-toi uu BPA-DCZ -1 10 -2 -2 10 BER BER giai ma cung BPA BPA-toiuu BPA-DCZ -1 10 10 -3 10 -3 10 -4 -4 10 10 -5 -5 10 10 -6 -6 10 BER Hamming(63, 57) tren kenh Gauss 0 10 10 10 0 1 2 3 4 EbN0[dB] 5 6 7 8 𝐸𝑏 𝑁 (dB) Hình 2. 11. So sánh BER của mã Hamming 31,26 giữa các thuật toán 0 1 2 3 4 5 EbN0[dB] 𝐸𝑏 𝑁 (dB) 6 7 8 Hình 2. 12. So sánh BER của mã Hamming 63,57 giữa các thuật toán Sử dụng BPA– DCZ, cần thêm bộ so sánh để xác định bít kiểm tra có giá trị nhỏ nhất nên hệ thống phức tạp hơn và thời gian giải mã lâu hơn so với sử dụng BPA. BPA– DCZ giảm được số 2 lượng phép tính tối đa so với BPA là . Nên, thời gian giải mã trung bình cho một từ mã giữa BPA và BPA– DCZ có thể coi là tương đương, thể hiện trên Bảng 2.3. 14 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). Bộ mã BPA BPA – DCZ C (7,4) 0,4743 ms 0,589 ms C(15,11) 1,006 ms 1,142 ms C(31,26) 3,625 ms 3,664 ms C(63,57) 14,229 ms 14,528 ms BPA– DCS và BPA– DCZ đều có thiết kế hệ thống phức tạp hơn, chất lượng giải mã tốt hơn. BPA– DCZ được lợi về mặt thời gian so với BPA– DCS hơn do giảm được số lượng phép tính. 2.3 Giải mã mềm sử dụng mã đối ngẫu 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 Bắt đầu 𝐿 𝑐𝑖 𝑙𝑛 𝐲 𝑐𝑖 𝐲 𝑐𝑖 𝐾 𝑝ℓ tanh(𝐿 𝑐 ′ℓ ⁄ ) với ℓ 𝑛 𝑖 2𝑟 𝑛 𝑗= ℓ= 𝑐 𝑗ℓ⨁𝛿𝑖ℓ 𝑡𝑎𝑛ℎ(𝐿 𝑐 ′ℓ ⁄ ) 𝑃𝑖 > S 𝑐̅𝑖 𝐾 𝑖 𝐾 𝑖 𝑖 Đ 𝑛 S 𝐜̅ Đ 𝐾 S 𝐾𝑚𝑎𝑥 S 𝐬 𝑐̅𝑖 𝑖 𝐜̅ 𝐇 𝑇 𝑛 [ ] Đ Kết thúc Hình 2. 13. Lưu đồ thuật toán DCA Đ 𝑐̅𝑖 15 Sau khi nhận được tin đầu vào mềm của các bit tin từ bộ giải điều chế, bộ giải mã thực hiện quá trình giải mã gồm các 2 bước: Bước 1: Tại vòng lặp thứ nhất bộ giải mã tính giá trị ℓ : Bước 2: Xác định từ mã đầu ra ̅ Lưu đồ thuật toán DCA được thể hiện trong Hình 2.13. 2.3.2 Đánh giá chất lượng thuât toán giải mã dựa trên mã đối ngẫu Trên cơ sở BPA, sử dụng không gian kiểm soát lỗi là ′ (ký hiệu là BPDCA) cho kết quả trên Hình 2.14. Từ mã càng dài, chất lượng càng kém do số lượng vòng kín ngắn càng lớn (Bảng 2.4). Bảng 2. 4. Số lượng các vòng kín ngắn trong ma trận , ′ BER Hamming tren kenh Gauss 0 10 -1 10 -2 Mã 10 Vòng kín 4 BER HDD (7,4) HDD (15,11) HDD (31,26) BPA (7,4) BPA (15,11) BPA (31,26) BPDCA (7,4) BPDCA (15,11) BPDCA (31,26) -4 10 -5 10 -6 10 -7 10 0 1 2 3 4 5 EbNo[dB] 𝐸𝑏 𝑁 (dB) 6 7 Vòng kín 6 (7,4) (15,11) 3 36 ′ 21 630 4 224 ′ 252 31220 (31,26) 280 13020 5600 2744120 -3 10 8 Hình 2. 14. BER của BPDCA, BPA và HDD cho các mã Hamming BER Hamming tren kenh Gauss 0 10 -1 10 -2 (23,12) mo rong (24,12) (23,12) mo rong (24,12) -2 10 10 -3 -3 10 10 BER BER HDD Golay HDD Golay DCA Golay DCA Golay -1 10 -4 10 -4 10 HDD (7,4) HDD (15,11) HDD (31,26) DCA (7,4) DCA (15,11) DCA (31,26) -5 10 -6 10 -7 10 BER Golay tren kenh Gauss 0 10 0 1 2 -5 10 -6 10 -7 3 4 5 EbNo[dB] 𝐸𝑏 𝑁 (dB) 6 7 Hình 2. 15. Chất lượng giải mã theo thuật toán DCA, HDD cho các mã Hamming. 8 10 0 1 2 3 4 5 𝐸EbNo[dB] 𝑏 𝑁 (dB) 6 7 8 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 4 Chất lượng của DCA tại , cho độ lợi 1,57 dB; 1,4 dB và 1,39 dB so với HDD khi áp dụng cho các mã Hamming có chiều dài từ mã tương ứng 7; 15 và 31. Đối với mã Golay và Golay mở rộng, độ lợi đạt tới 1,85 dB so với HDD. 16 Như vậy, với các mã tốc độ càng thấp, cho độ lợi giải mã DCA so với giải mã cứng càng cao. Nhưng phải trả giá về kích thước không gian kiểm soát lỗi lớn, tỉ lệ với Bảng 2.5 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. Bộ mã H (7,4) H (15,11) H (31,26) G (23, 12) G (24, 12) Kích thước ma trận kiểm tra của HDD 7 Kích thước không gian kiểm tra của DCA 3 7 4 5 2 Độ lợi mã hóa DCA so với HDD 1,57 dB 1,4 dB 1,39 dB 1,85 dB 1,85 dB DCA phù hợp với các mã tốc độ cao, hay các mã có độ dư nhỏ. 2.4 Kết luận chương Chương 2 đã đề xuất một số thuật toán cải tiến cho thuật toán BPA trên cơ sở tính chất mang tin của mã đối ngẫu cho các mã mật độ cao HDPC là thuật toán BPA– DCS và BPA– DCZ. Ngoài ra, nội dung chương này còn đề cập đến việc nâng cao chất lượng giải mã HDPC như mã Hamming, Golay,... bằng cách quét toàn bộ thông tin giải mã trong bộ mã đối ngẫu tương ứng để đạt được lượng tin quyết định từ mã đầu ra là lớn nhất, đề xuất thuật toán giải mã đối ngẫu DCA. Khi đó, không gian các từ mã đối ngẫu tăng tỷ lệ với . Từ hai hướng nghiên cứu này, có thể nhận xét sơ bộ là: chất lượng giải mã hướng thứ nhất chưa thực sự khả quan, còn hướng nghiên cứu thứ hai DCA là thuật toán giải mã cho chất lượng giải mã tốt có số lượng phép tính tỉ lệ với 2 . Vì vậy DCA rất phù hợp với các mã khối có độ dư nhỏ. Chương 3. GIẢI MÃ MỀM MÃ TÍCH Nội dung chương 3 được công bố ở công trình số 2, 3 và 5. 3.1 Mã tích và các đặc điểm 3.1.1 Các tham số cơ bản của mã tích Cấu trúc mã tích 2 minh họa trong Hình 3.1. 17 𝑛 𝑘 𝑟 𝑘2 bit kiểm tra chẵn lẻ mã hàng 𝑘2 𝑛2 𝑟 𝑟2 bit kiểm tra chẵn lẻ mã hóa các bit kiểm tra chẵn lẻ 𝑟2 𝑘 bit kiểm tra chẵn lẻ mã cột Hình 3. 1. Cấu trúc mã tích 3.1.2 Giải mã mã tích Giải mã Viterbi trên lưới mã tích rất phức tạp. Giải mã Turbo cho mã tích trên cơ sở giải mã các hàng và các cột thành phần bằng thuật toán MAP (Hình 3.3). Bộ giải mã MAP trả về giá trị thực cho mỗi symbol ̅ với: ̅ ∑∈ ∏ℓ ℓ ∑∈ ∏ℓ ℓ ( ℓ ℓ) ℓ ( ℓ ℓ) ℓ (3.8) Phản hồi bước lặp tiếp theo 𝐿 𝐜 𝐿𝑐 𝐲 𝐿𝑒 𝐜̅ Giải mã hàng 𝐂 𝐿𝑒 𝐜̅ Giải mã cột 𝐂 𝐿 𝐜̅ 𝐿 𝐜̅ Tại lần lặp cuối 𝐿 𝐜̅ Hình 3. 3. Mô hình giải mã mã tích Giá trị mềm cho mỗi symbol bởi giải mã MAP trên mã đối ngẫu được đưa ra như sau: ̅ ∑ ∑ ∏ℓ ( ′ ( ℓ ℓ ) ∏ℓ ℓ ′ ℓ) ( ℓ Bảng 3. 1. Độ phức tạp của các phương pháp giải mã tích Phương pháp giải mã Độ phức tạp (phép tính) Turbo 2 (MAP) ′ 2 Viterbi ℓ) ℓ ′ ℓ /Đơn vị Lần lặp Lần lặp Mỗi giai đoạn 18 Sự phức tạp của giải mã Viterbi và giải mã Turbo chỉ ra trong Bảng 3.1. Các thuật toán này đều giải mã trên lưới mã nên độ phức tạp còn phụ thuộc vào số đỉnh và số nhánh trong lưới. Thuật toán giải mã lặp cận tối ưu có độ phức tạp điều chỉnh được, có thể coi là một giải pháp để giải mã tích. Tuy nhiên, nhược điểm là chưa có bộ giải mã thành phần hiệu quả khiến việc sử dụng mã tích trong thực tế của thuật toán này bị hạn chế. 3.2 Đề xuất thuật toán giải mã đối ngẫu mã tích 3.2.1 Xây dựng cơ sở lý thuyết cho thuật toán giải mã tích mới Cho là mã đối ngẫu của . Ký hiệu ∈ { } là xác suất có điều kiện rằng thu được khi bit mã được gửi đi. Ký hiệu là tỷ lệ hợp lẽ (Likelihood Ratio) 2 của bit thứ m. Dễ dàng tính được . Để ứng dụng phương pháp giải mã đối ngẫu mã tích, cần biến đổi để đầu ra của tính toán trong bước giải mã hàng (cột) có thể làm đầu vào cho bước giải mã cột (hàng) sau. Như vậy, ý tưởng quan trọng của Luận án là đưa ra công thức tính lượng tin đầu vào vòng lặp tiếp theo: 2 3.15 2 với 2 2 = ( ℓ ( ℓ ℓ= ℓ ) 2 = ℓ= ℓ ) ′ ℓ ′ ℓ 3.16 ℓ 3.17 Công thức 3.15 chính là cơ sở lý thuyết cho đề xuất thuật toán giải mã tích mới. 3.2.2 Thuật toán giải mã mềm mã tích sử dụng mã đối ngẫu Thuật toán mới cho mã tích được xây dựng trên cơ sở thuật toán DCA ký hiệu là DCAPC (Dual Codes decoding Algorithm for Product Codes) (Hình 3.5). Giải mã mỗi hàng hay mỗi cột theo lưu đồ thuật toán Hình 3.6. DCAPC gồm các bước chính: