Tóm tắt Luận án Giải mã mềm cho mã khối dựa trên không gian mã đối ngẫu

Nội dung tài liệu: Tóm tắt Luận án Giải mã mềm cho mã khối dựa trên không gian mã đối ngẫu

1. 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
2. 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
3. 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
4. 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.
5. 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.
6. 4 퐮 Mã hóa 퐜 Điều 퐱 Ngu ồn kênh chế Kênh truyền 퐲 Đích 퐮 Giải mã 퐜 ′ Giải kênh đ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 là một không gian con chiều của một không gian véctơ thành phần. Do vậy có thể tìm được từ mã độc lập tuyến tính trong , sao cho: c u1 g1 u2 g2 u g (1.1) Với { } và g1, g2, , g là ma trận sinh của mã . 1.1.3 Ma trận kiểm tra Đối với một ma trận sinh bất kỳ có hàng độc lập tuyến tính, tồn tại một ma trận có hàng độc lập tuyến tính. Do đó, một tổ hợp gồm thành phần là một từ mã hợp lệ của mã được tạo ra bởi ma trận sinh 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
7. 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 với từ mã trong 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]: ( ) (√ ⁄ ) 1.9 Xác xuất lỗi symbol gồm bit không mã là: (√ ) (1.10) Vậy, Độ lợi mã hóa tiệm cận
8. 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.
9. 7 Đọc vectơ nhận và Bắt đầu 푖 số vòng lặp cực đại 푛 Khởi tạo [ 푖 푖] và [ 푖 푖] Khởi tạo 푞푖푗 ] và 푞푖푗 푖 Tính toán bản tin 푗푖 푖 푖 và 푞 푖푗 S 푄푖 ≥ 푄푖 푖̅ Tính toán 푄푖 [ 푖 Đ 푖 và các bản tin đã qua] 푖̅ S Cho tấ t cả 푖 퐜̅ 퐇 Đ 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.
10. 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.