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ố.
- Xem thêm -