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
Điều chế
Mã hóa kênh
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 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
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
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 đó
cải thiện xác suất lỗi của hệ thống mã hóa.
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
1.6 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: ⁄
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
6
b) Chất lượng giải mã cứng
(1.14)
. Ta có giới hạn xác xuất lỗi symbol là: Trường hợp giải mã cứng với xác suất lỗi bit là: √ ⁄
) (
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.
Bắt đầu
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
Đọc vectơ nhận 𝑦𝑖 và số vòng lặp cực đại 𝑛 Hình 1. 8. Lưu đồ thuật toán tổng tích SPA
Giai đoạn 1
𝑖
𝑖
>0
<
𝐿(𝑞𝑖𝑗) 𝑙𝑜𝑔
𝐿 𝑄𝑖
𝑐̅𝑖
𝑐̅𝑖
𝑞𝑖𝑗 𝑞𝑖𝑗
Đ
Đ
𝑖 < 𝑛
𝑖 < 𝑛 1
S
S
𝐿(𝑟𝑗𝑖) 𝛼𝑖′𝑗
𝛽𝑖′𝑗
𝑖′
S
𝐜̅ 𝐇𝑇 1
Đ
𝐿(𝑞𝑖𝑗) 𝐿 𝑐𝑖 𝐿(𝑟𝑗′𝑖)
Kết thúc
𝑗′∈𝐶𝑖~𝑗
𝐿 𝑄𝑖 𝐿 𝑐𝑖 𝐿(𝑟𝑗′𝑖)
𝑗∈𝐶𝑖
7
1.3.3 Thuật toán tổng cực tiểu
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
a) Định nghĩa:
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 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ố
𝑐3
𝑐4
𝑐
𝑐5
𝑐6
𝑐2
𝑐7
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
𝑛 7
[ ] 0 1 1 0 0 1 1
𝑓2
𝑓3
𝑓
1 0 1 0 1 0 1
Hình 2. 1. Ma trận kiểm tra và đồ thị Tanner tương ứng của mã Hamming 7,4
10
b) d ng c c ma t n i m t a tư ng đư ng
cho các nút bit , đặt:
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
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.
Hình 2. 2. Chất lượng giải mã BPA mã Hamming (7,4)
Hình 2. 3. Chất lượng giải mã BPA mã Hamming (31,26)
11
tương ứng của 2 3
Giải mã ̅ ̅2 ̅3 ̅4 ̅5 ̅6 ̅7
Từ mã truyền 2 3 4 5 6 7 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
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.
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
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
Hamming có > 7 tại 4 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.
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.
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.
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
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 .
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.
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. 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).
Bộ mã
BPA
BPA– DCS
Tỷ lệ thời gian của thuật toán 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
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
- 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].
Hình 2. 9. So sánh BER của mã Hamming 7,4 giữa các thuật toán
Hình 2. 10. So sánh BER của mã Hamming (15,11) giữa các thuật toán
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
Với các mã Hamming (15,11); (31,26) và (63,57), BPA– DCZ cho độ lợi tương ứng 0,3 dB; 0,45 dB; 0,65 dB tại 4 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.
Hình 2. 12. So sánh BER của mã Hamming 63,57 giữa các thuật toán
Hình 2. 11. So sánh BER của mã Hamming 31,26 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ố lượng phép tính tối đa so với BPA là 2 . 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).
BPA
Bộ mã
BPA – DCZ
0,4743 ms
C (7,4)
0,589 ms
1,006 ms
C(15,11)
1,142 ms
3,625 ms
C(31,26)
3,664 ms
14,229 ms
C(63,57)
14,528 ms
Bắt đầu
𝑙𝑛
𝐿 𝑐 𝑖
𝐲 𝑐 𝑖 𝐲 𝑐 𝑖
𝐾
𝑝ℓ tanh(𝐿 𝑐 ′ℓ ⁄ ) với ℓ 𝑛
𝑖
2𝑟
𝑛
𝑐 𝑗ℓ⨁𝛿𝑖ℓ
𝑐̅𝑖
Đ >
𝑃𝑖 𝑡𝑎𝑛ℎ(𝐿 𝑐 ′ℓ ⁄ )
ℓ=
𝑗=
S
𝑐̅𝑖
𝑖 𝑖
𝐾 𝐾
Đ
𝑖 𝑛
S
𝐜̅ 𝑐̅𝑖 𝑖 𝑛
Đ
S
𝐬 𝐜̅ 𝐇𝑇 [ ]
𝐾 𝐾𝑚𝑎𝑥
S
Đ
Kết thúc
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
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 , ′
Mã
Vòng kín 4
Vòng kín 6
(7,4) (15,11)
3 36
′ 21 630
4 224
′ 252 31220
(31,26)
280
13020
5600
2744120
𝐸𝑏 𝑁 (dB)
Hình 2. 14. BER của BPDCA, BPA và HDD cho các mã Hamming
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
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
Hình 2. 15. Chất lượng giải mã theo thuật toán DCA, HDD cho các mã Hamming.
Chất lượng của DCA tại 4, 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)
Độ 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
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
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ã cột
𝑟 𝑟2 bit kiểm tra chẵn lẻ mã hóa các bit kiểm tra chẵn lẻ
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ã Turbo (MAP)
′
Viterbi
/Đơn vị Lần lặp Lần lặp Mỗi giai đoạn
Độ phức tạp (phép tính) 2 2
18
′ ℓ )
3.15 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) của bit thứ m. Dễ dàng tính được 2 . Để ứ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 2 với
3.16 ℓ ℓ
ℓ=
′ ℓ ℓ )
3.17 ℓ ℓ
2 2 ( = 2 ( =
ℓ=
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:
Bắt đầu
) 𝑙𝑛
𝐿(𝑐 𝑖𝑗
𝐲 𝑐 𝑖𝑗 𝐲 𝑐 𝑖𝑗
Ite= 1
Giải mã các cột
Giải mã các hàng
Ite= Ite + 1
Đ
Ite
S
Đ
>
𝐵𝑖𝑗
𝑐̅𝑖𝑗
𝐵2 𝐵 𝐵2 𝐵
S
𝑐̅𝑖𝑗
𝐜̅
Kết thúc
19
Hình 3. 5. Lưu đồ thuật toán giải mã đối ngẫu của mã tích
Bắt đầu
𝑝ℓ tanh 𝐿 𝑐 ℓ ℓ 𝑛
𝑚
′ 𝑐𝑗ℓ
′ 𝛿𝑚ℓ 𝑐𝑗ℓ
∑
∑
𝝋𝑚
′ 𝑐𝑗ℓ
′ 𝛿𝑚ℓ 𝑐𝑗ℓ
∑
∑
2𝑛 𝑘 𝑗= 2𝑛 𝑘 𝑗=
𝑛 ∏ 𝑝ℓ ℓ= 𝑛 ∏ 𝑝ℓ ℓ=
2𝑛 𝑘 𝑗= 2𝑛 𝑘 𝑗=
𝑛 ∏ 𝑝ℓ ℓ= 𝑛 ∏ 𝑝ℓ ℓ=
𝑚 𝑚
Đ
𝑚 𝑛 S
Kết thúc
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
20
của từng bit trong tin nhận được.
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
Khởi tạo : Tính Tại vòng lặp thứ nhất Bước 1: Giải mã cột mã tích. Bước 2: Giải mã 2 hàng mã tích. Thực hiện vòng lặp thứ 2. Bước 3: Quyết định từ mã đầu ra. 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 Nhược điểm về việc sử dụng mã tích làm giảm tốc độ mã hóa rất lớn sẽ được khắc phục khi sử dụng mã Hamming. 3.3.1 Đánh giá chất lượng thuật toán giải mã đối ngẫu mã tích
Hình 3. 7. Chất lượng của mã tích 15,11,3 15,11,3 trên kênh AWGN
Hình 3. 8. Chất lượng của mã tích 31,26,3 31,26,3 trên kênh AWGN
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
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
Hình 3. 10. So sánh chất lượng thuật toán mới với thuật toán MDUDC
DCAPC cho khả năng sửa lỗi rất tốt so với các phương pháp khác và các mã tích có tốc độ mã hóa càng cao cho độ lợi giải mã càng lớn (Hình 3.7, 3.8, 3.9 và 3.10). So sánh hiệu quả kiểm soát lỗi của
21
DCAPC với thuật toán được đánh giá cao như giải mã MAP cho mã tích sử dụng mã đối ngẫu MAP Decoder Using the Dual Code: MDUDC của Hagenauer Hình 3.10 , dễ dàng thấy chất lượng giải mã của hệ thống đang đề xuất kém hơn so với MDUDC. 3.3.2 Đề xuất thuật toán giải mã đối ngẫu mã tích cải tiến . Từ cấu trúc mã tích, tồn tại một phần mã tích chứa các bit mã hóa của các bit kiểm tra, làm ảnh hưởng đến tốc độ mã hóa (Bảng 3.3). 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ẻ
Công thức tính
2
3 0,3265
4 0,5378
5 0,7034
6 0,8185
0,4000
0,5789
0,7222
0,8261
Mã hóa bit kiểm tra chẵn lẻ Không mã hóa bit kiểm tra chẵn lẻ
2 2 2 2 2
𝐸𝑏 𝑁 (dB)
𝐸𝑏 𝑁 (dB)
Luận án đưa ra hai cải tiến cho DCAPC: Sử dụng sơ đồ không mã hóa các bit kiểm tra chẵn lẻ ở phía phát và tính ảnh hưởng của xác suất không đều của các bit mã. DCAPC cải tiến thực hiện như sau:
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
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
được làm đầu vào cho bước 2.
tương
Bước 1: Thực hiện như thuật toán DCAPC + Tính tương ứng cho các bit của từng cột, cập nhật trung bình nhân của với Bước 2: Giải mã cột mã tích. Với giá trị , tính lại ℓ cho từng bit của từng cột. cập nhật lại là trung bình nhân của với ứng. Quay trở lại bước 1 thực hiện vòng lặp tiếp theo.
22
Bước 3: Quyết định từ mã đầu ra. Mô phỏng chất lượng mã tích sau hai lần lặp cho trường hợp có và không có mã hóa đối với bit kiểm tra chẵn lẻ, trường hợp không mã hóa đạt độ lợi lên tới 1,15 dB so với có mã hóa Hình 3.11 . Hình 3.12, DCAPC cải tiến không những đảm bảo được tốc độ mã hóa cao mà còn cho độ lợi khoảng 0,3 dB đến 1 dB so với kết quả của Hagenauer tại 5. 3.3.3 Độ phức tạp Bảng 3. 4. Độ phức tạp của thuật toán DCAPC và thuật toán cải tiến.
Số phép tính nhân
Số phép tính cộng
Thuật toán DCAPC
2 2 2 2
2 2
DCAPC cải tiến
Đánh giá độ phức tạp của DCAPC với thuật toán do Hagenauer trình bày trong Bảng 3.5. Bảng 3. 5. So sánh độ phức tạp của DCAPC và MDUDC.
Tính theo độ phức tạp của Viterbi
VA VA
Thuật toán DCAPC MDUDC
Bảng 3.5 cho thấy, MDUDC có độ phức tạp gấp lần so với DCAPC. MDUDC quá phức tạp và chỉ dừng lại ở mức nghiên cứu lý thuyết chứ rất khó có thể áp dụng vào thực tế ngay cả khi chúng ta có những bộ vi xử lý có khả năng tính toán mạnh. DCAPC mở ra tính khả thi khi hiện thực hóa mã tích bằng các thiết bị phần cứng. 3.4 Kết luận chương DCAPC đưa ra được cơ sở lý thuyết là nền tảng cho việc nghiên cứu, đề xuất các thuật toán giải mã cải tiến có độ phức tạp thấp hơn, có tốc độ mã hóa cao hơn và có thể cho chất lượng giải mã tốt hơn. Điều này được khẳng định bởi thuật toán DCAPC cải tiến, đạt độ lợi giải mã từ 0,3 dB đến 1 dB so với thuật toán giải mã Turbo với giải mã MAP cho các mã thành phần.
23
KẾT LUẬN
Các kết quả chính đạt được của Luận án: - Đề xuất các thuật toán giải mã mềm cải tiến dựa vào tính chất mang tin giải mã của mã đối ngẫu, BPA– DCS và BPA– DCZ, chất lượng giải mã tốt hơn tương ứng đến 0,45 dB và 0,65 dB so với BPA, nhưng hệ thống phức tạp hơn. - Đề xuất thuật toán giải mã đối ngẫu DCA cho các mã khối mật độ cao, so với thuật toán giải mã cứng, độ lợi mã hóa đạt tới 1,57dB đối với mã Hamming và 1,85dB đối với mã Golay tại 4. Thuật toán giải mã DCA phải trả giá là tăng độ phức tạp thuật toán theo hàm . - Xây dựng và đề xuất được phương pháp giải mã mới cho mã tích. Thuật toán DCAPC đề xuất yêu cầu tỉ số tín hiệu trên tạp chỉ khoảng 5 dB để đảm bảo tỉ lệ lỗi bit không vượt quá 8 khi sử dụng Hamming 63,57 làm mã thành phần. Đưa ra giải pháp cải tiến cho DCAPC với độ phức tạp tăng thêm không đáng kể và chất lượng giải mã tăng đến 1,15 dB tại tỉ lệ lỗi bit 5 nếu sử dụng các mã thành phần là mã Hamming (7,4). Từ việc đánh giá về độ phức tạp và kết quả mô phỏng chất lượng giải mã cho mã tích, thấy rằng, mã tích với các mã thành phần là các mã khối tốc độ cao, sử dụng thuật toán được đề xuất, là những ứng viên rất tốt và có thể trở thành giải pháp thay thế mang tính thực tiễn cao. Hướng nghiên cứu tương lai Để ứng dụng trong các hệ thống truyền dẫn vô tuyến, các mạng cảm biến vô tuyến, có thể xem xét tới việc đánh giá khả năng giải mã tại các giá trị xác xuất lỗi thấp hơn nữa nhằm tìm sàn lỗi hay giới hạn kiểm soát lỗi của thuật toán. Khảo sát thuật toán mới với các mã khối Hamming có chiều dài lớn hơn hay các mã BCH tốc độ mã hóa cao nhằm khai thác tối đa ưu điểm của các mã khối mật độ cao trong vai trò là mã thành phần cho mã tích. Mô phỏng đánh giá trên các kênh khác kênh Gauss như kênh fading là một trong các hướng phát triển tiếp theo của Luận án.
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ
1. Nguyễn Thị Hồng Nhung, Phạm Xuân Nghĩa, Vũ Thị Thắng, Lê
Tiến Cường, “Giải mã mềm mã Hamming dựa trên các mã đối
ngẫu,” Tạp chí Nghiên cứu Khoa học và Công nghệ Quân sự, số
46, trang 27- 35, tháng 12-2016.
2. Nguyễn Thị Hồng Nhung, Phạm Khắc Hoan, Phạm Xuân Nghĩa,
“Thuật toán giải mã khối mật độ cao sử dụng mã đối ngẫu,” Kỷ
yếu hội thảo quốc gia 2017 về điện tử, truyền thông và công
nghệ thông tin (REV - ECIT 2017), trang 192- 194, tháng 12-
2017.
3. Nguyen Thi Hong Nhung, Pham Khac Hoan, Pham Xuan Nghia,
Bui Huy Hai, “Dual Codes decoding Algorithm for high density
parity check codes,” Asian Academic Research Journal of
Multidisciplinary, vol. 5, pp. 114-124, May 2018.
4. Nguyen Thi Hong Nhung, Pham Khac Hoan, Nguyen Trung
Thanh. “The Soft-decision decoding algorithm for Hamming
code using zeros codeword of dual code,” 2018 IEEE Seventh
International Conference on Communications and Electronics,
July 2018.
5. Phạm Xuân Nghĩa, Nguyễn Thị Hồng Nhung, “Giải mã tích
bằng giải mã quyết định mềm dùng mã đối ngẫu đảm bảo tính
khả dụng,” Tạp chí Nghiên cứu Khoa học và Công nghệ Quân
sự, số 57, trang 11- 17, tháng 10-2018.
