Tiến Sĩ Nghiên cứu cải thiện chất lượng mã LDPC

LUẬN ÁN TIẾN SĨ
NĂM 2014

MỤC LỤC
TRANG PHỤ BÌA
LỜI CAM ĐOAN . i
LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CÁC TỪ VIẾT TẮT . v
DANH MỤC HÌNH VẼ . viii
DANH MỤC KÝ HIỆU TOÁN HỌC xi
MỞ ĐẦU . 1
Chương 1: TỔNG QUAN 9
1.1 Giới hạn Shannon 9
1.1.1 Lượng tin 11
1.1.2 Entropy . 12
1.1.3 Kênh thông tin 13
1.1.4 Lượng tin tương hỗ . 15
1.1.5 Dung lượng kênh rời rạc . 15
1.1.6 Lý thuyết về mã kênh . 15
1.2 Mã LDPC . 17
1.2.1 Sự phát triển của các kỹ thuật mã kênh nhằm đạt giới hạn Shannon . 17
1.2.2 Quá trình phát triển của mã LDPC 19
1.2.3 Cơ bản về mã LDPC . 21
1.2.4 Đặc điểm của mã LDPC 25
1.3 Sơ đồ BICM-ID truyền thống 26
1.4 Đặt vấn đề nghiên cứu 32

Chương 2: SƠ ĐỒ KẾT HỢP LDPC VÀ BICM-ID . 35
2.1 Sơ đồ khối hệ thống điều chế mã LDPC 35
2.2 Cải tiến thuật toán giải mã SPA . 37
2.2.1 Bộ giải mã cứng 37
2.2.2 Giải mã mềm: Thuật toán tổng-tích SPA . 39
2.2.3 Thuật toán giải mã SPA trong miền Log 47
2.2.4 Các thuật toán xấp xỉ 51
2.2.5 Cải tiến thuật toán SPA . 51
2.2.6 Giảm sự ảnh hưởng của sai số ước lượng kênh tới chất lượng thuật toán
giải mã SPA . 57
2.3 Xây dựng sơ đồ mô phỏng hệ thống BILCM-ID 60
2.3.1 Mã hóa LDPC . 60
2.3.2 Hệ thống BILCM-ID có trộn bít . 63
2.4 Kết luận chương . 67

Chương 3: ĐIỀU CHẾ MÃ LDPC DỰA TRÊN ĐỘ TIN CẬY CỦA CÁC BÍT MÃ 69
3.1 Xây dựng bộ hoán vị dựa trên độ tin cậy của các bít mã 69
3.2 Kết quả mô phỏng hệ thống BILCM-ID với tín hiệu đa mức 75
3.3 Kết quả mô phỏng hệ thống BILCM-ID với tín hiệu đa chiều 80
3.4 Kết luận chương . 90
KẾT LUẬN . 91
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ . 94
TÀI LIỆU THAM KHẢO . 95

MỞ ĐẦU
Trong những ngày đầu truyền thông kỹ thuật số ra đời, ưu thế lớn nhất
của tín hiệu số so với truyền thông tương tự truyền thống không phải là tốc độ
dữ liệu mà chính là khả năng sử dụng mã hóa sửa sai của tín hiệu số.
Mã kênh được sử dụng để nâng cao độ tin cậy của các hệ thống thông
tin. Người đặt nền móng cho các nghiên cứu về mã kênh, C. E. Shannon [57]
đã đưa ra các cơ sở toán học là các cận lý thuyết cho việc xây dựng các bộ mã
kênh. Tuy lý thuyết Shannon không trực tiếp chỉ ra cách tạo các bộ mã tối ưu
có thể đạt được giới hạn đó nhưng trên thực tế thì các bộ mã hoá, giải mã đơn
giản, dễ chế tạo vẫn được ứng dụng rộng rãi trong các hệ thống truyền tin và
lưu giữ thông tin. Các nhà nghiên cứu về mã kênh đã không ngừng nghiên
cứu, tìm ra các loại mã kênh vừa đạt chất lượng tốt vừa có tính ứng dụng cao.
Tới nay, đã có nhiều bộ mã kênh được sử dụng hiệu quả trong các hệ thống
thông tin số, trong đó có mã kiểm tra mật độ thấp LDPC (Low Density Parity
Check) được R. G. Gallager đề xuất lần đầu tiên vào năm 1962 [21]. Trong
vòng 30 năm sau đó mã LDPC bị các nhà nghiên cứu lãng quên và chỉ đến
khi xuất hiện các mã Turbo vào năm 1993[37], các mã LDPC mới được tái
phát hiện nhờ chất lượng của chúng rất gần giới hạn Shannon (tương tự như
các mã Turbo). Ngoài ra, các mã LDPC có ba phẩm chất vượt trội so với các
mã Turbo: (1) Giải mã song song có độ phức tạp tính toán thấp hơn các mã
Turbo; (2) Trên thực nghiệm tất cả các lỗi đều được phát hiện mặc dù chưa
được chứng minh bằng lý thuyết; và (3) Các mã LDPC có các phương pháp
giải mã đơn giản hơn. Do vậy, các mã LDPC nổi lên như là ứng cử viên triển
vọng cho các hệ thống mã sửa lỗi hướng đi (FEC) và được chấp nhận bởi
nhiều tiêu chuẩn tiên tiến như Ethernet 10 Gigabit (10GBASET) [67] và
2
truyền hình số (DVB-S2) [68]. Ngoài ra, các thế hệ thông tin tiếp theo của
Wifi và WiMAX đang xem xét các mã LDPC là một bộ phận của hệ thống mã
sửa lỗi [66].
Tuy nhiên, bên cạnh các ưu điểm nổi trội nêu trên, các mã LDPC cũng
tồn tại các hạn chế. Thứ nhất, các mã có chất lượng tốt nhất là các mã rất dài
(như đã được tiên đoán trong lý thuyết mã kênh). Các chiều dài khối lớn, kèm
theo giải mã lặp dẫn đến khó chấp nhận trong nhiều ứng dụng. Thứ hai, ma
trận sinh G 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ã.
Các mã LDPC được biểu diễn bằng đồ hình đôi gọi là đồ hình Tanner
[59], và mầm (girth) của đồ hình Tanner là chiều dài của vòng kín ngắn nhất
trên đồ hình. Các mầm của đồ hình Tanner của các mã LDPC cản trở tính hội
tụ của thuật toán tổng-tích [40]. Hơn nữa, các vòng kín, đặc biệt các vòng kín
ngắn, làm suy giảm chất lượng của các bộ giải mã LDPC vì chúng ảnh hưởng
tới tính độc lập của các thông tin trao đổi (extrinsic information) giữa các
vòng lặp giải mã. Người ta mong muốn xây dựng các mã LDPC có các mầm
lớn, nhưng điều này dẫn đến sự phức tạp về cấu trúc của các ma trận kiểm tra.
Với các đặc điểm nêu trên, trong thời gian qua các mã LDPC đã nhận
được rất nhiều sự quan tâm nghiên cứu trên thế giới. Với mục đích đi sâu
nghiên cứu các mã LDPC, tìm các biện pháp nhằm nâng cao chất lượng mã,
nghiên cứu sinh đã chọn đề tài của luận án là “Nghiên cứu cải thiện chất
lượng mã LDPC”.
Trước kia, trong hệ thống thông tin số, bộ mã hoá kênh và bộ điều chế
là các thành phần tách biệt và hoạt động một cách độc lập. Năm 1974, Masey
nghiên cứu và đề xuất sơ đồ hệ thống kết hợp giữa sử dụng mã kênh với điều
chế nhiều mức cho phép tối ưu hoá cả bộ mã kênh và bộ điều chế, qua đó cải
thiện hiệu quả của hệ thống [43]. Hệ thống như vậy được gọi là hệ thống điều
chế mã CM (Coded Modulation) mà ngày nay được sử dụng một cách rộng
rãi, đặc biệt trong hệ thống thông tin số có băng thông giới hạn [22], [47].
Một số hệ thống điều chế mã đã được phát triển như hệ thống điều chế mã đa
mức MLC (Multi-Level Coding) [62], kỹ thuật điều chế mã lưới TCM (Trellis
Coded Modulation) [19], và gần đây nhất là điều chế mã có hoán vị bit và
giải mã lặp BICM-ID (Bit Interleaved Coded Modulation with Iterative
Decoding) [18]. Trong hệ thống BICM-ID truyền thống, mã chập đóng vai
trò mã vòng ngoài. Như một phát triển lô-gíc, mã LDPC cũng đã được đề
xuất sử dụng trong sơ đồ điều chế mã có hoán vị bít và giải mã lặp, gọi là
BILCM-ID. Luận án đặt vấn đề nghiên cứu phương pháp điều chế mã thích
hợp để cải thiện chất lượng hệ thống BILCM-ID. Hướng nghiên cứu của
Luận án được mô tả như sau.
Một trong những lý do làm cho mã LDPC bị lãng quên trong suốt hơn
30 năm là do độ phức tạp giải mã hợp lẽ cực đại (MLD-Maximum Likelihood
Decoding) đối với mã LDPC tăng theo hàm mũ của chiều dài từ mã. Sau khi
mã turbo được phát hiện cùng với ứng dụng của giải mã lặp, trên thực tế
người ta cũng áp dụng phương pháp cận tối ưu là giải mã lặp cho mã LDPC
với giải thuật Lan truyền niềm tin (BP-Belief Propogation) [41], [58], [53]
hoặc cực tiểu - tổng MS (Min-Sum) [15]. Về lý thuyết, giải mã lặp đối với mã
LDPC cho phép tiệm cận chất lượng giải mã hợp lẽ cực đại, nhưng với điều
kiện từ mã rất dài và mã thực sự ngẫu nhiên. Trên thực tế, với chiều dài từ mã
chấp nhận được trong các ứng dụng truyền tin và các ma trận kiểm tra chẵn lẻ
được thiết kế bằng phương pháp đại số [58] không hoàn toàn ngẫu nhiên thì
chất lượng giải mã lặp chưa đạt chất lượng của giải mã MLD. Hơn nữa, do
tồn tại các tập bẫy lỗi (Trapping Sets) [52], [56], có thể là ở dạng các vòng
ngắn (Short Cycles) trong đồ hình Tanner [38], [59], đường cong tỷ lệ lỗi bít
(BER-Bit Error Rate) của giải mã lặp có hiện tượng “sàn lỗi” (Error floor)
[52]. Vấn đề đặt ra là các cải tiến nhằm cải thiện chất lượng giải mã lặp theo
hướng tiệm cận MLD liệu có giải quyết được vấn đề sàn lỗi.
Để đưa chất lượng giải mã lặp đối với mã LDPC tiệm cận tới chất
lượng giải mã hợp lẽ cực đại (MLD), các nhà nghiên cứu đã phát triển ý
tưởng kết hợp Giải mã theo bậc thống kê OSD (Order Statistic Decoding)
[16] dựa trên độ tin cậy của bít mã [17] với giải mã BP, thành phương pháp
tái xử lý BP-OSD [28]. Tại một vòng lặp nào đó trong quá trình giải mã BP,
nếu không giải ra được từ mã hợp lệ thì sẽ tính độ tin cậy của các thông tin về
bít mã, lấy đó làm đầu vào cho giải mã OSD để xác định xem liệu có cần
thêm một vòng lặp nữa hay không. BP-OSD cho chất lượng giải mã gần với
MLD, nhưng độ phức tạp tăng nhanh cùng chiều dài từ mã. Việc kết hợp giải
mã lặp với xử lý thống kê dựa trên độ tin cậy của bít mã giúp cho chất lượng
giải mã tiến tới giải mã MLD, nhưng không giải quyết được vấn đề sàn lỗi.
Luận án đặt vấn đề nghiên cứu kết hợp nguyên lý điều chế mã dựa trên
độ tin cậy (RBCM- Reliability Based Coded Modulation) [42] với sơ đồ
BICM-ID [35] để hạ thấp sàn lỗi của mã LDPC khi sử dụng điều chế đa mức
như khóa dịch pha MPSK (M-ary Phase Shift Keying) và điều chế cầu
phương MQAM (M-ary Quadrature Amplitude Modulation). Khác với [52]
nghiên cứu xác định các tập bẫy lỗi của mã LDPC để đánh giá ảnh hưởng và
tìm cách loại bỏ chúng, luận án đề xuất ghép vào cùng một tín hiệu các bít có
độ tin cậy cao hơn với các bít có độ tin cậy thấp hơn (do thuộc cùng tập bẫy
lỗi nào đó, ví dụ như nằm trong vòng kín ngắn). Cụ thể, sơ đồ BICM-ID cho
phép tạo ra các kênh nhị phân song song tương đương với độ tin cậy khác
nhau. Về bản chất, các bít mã hóa chập trong sơ đồ BICM-ID truyền thống
thể hiện một đường qua lưới mã nên bộ hoán vị vừa cho phép tạo tính độc lập
tương đối của các bít trong cùng một tín hiệu, vừa đảm bảo bít có độ tin cậy
cao hơn được truyền qua kênh tin cậy hơn. Khi giải mã BICM-ID, bít thu
được với độ tin cậy cao sẽ hỗ trợ thông tin để giải mã bít thu được với độ tin
cậy thấp hơn. Với mã LDPC, các bít mã vốn đã khá độc lập nhờ ma trận kiểm
tra rất thưa nên vai trò của bộ hoán vị lúc này rút gọn lại chỉ là sắp xếp các bít
mã như một phép ánh xạ trước khi điều chế [36]. Các nghiên cứu trước đây về
RBCM [36, 42] dùng ánh xạ Gray với 8PSK cho phép cải thiện chất lượng
giải mã khoảng 0,2~0,3 dB trên toàn dải tỷ lệ tín trên tạp (SNR-Signal to
Noise Ratio), không phải là hướng tới giải quyết vấn đề sàn lỗi. Luận án đề
xuất sử dụng ánh xạ phân hoạch tập, tạo ra các kênh nhị phân song song có độ
tin cậy khác biệt nhằm hạ thấp sàn lỗi trong khi chấp nhận có thể có chất
lượng giải mã kém hơn ở vùng SNR nhỏ.
Ngoài ra, như đã nêu ở trên, các mã LDPC được giải mã bằng thuật
toán Lan truyền niềm tin BP [41] hay một dạng của nó là thuật toán tổng-tích
SPA (Sum-Product Algorithm). Về mặt lý thuyết, thuật toán SPA sẽ tối ưu
nếu ma trận kiểm tra của mã hay đồ hình Tanner không có các vòng kín, đặc
biệt là các vòng kín ngắn [60]. Việc tồn tại các vòng kín ngắn này là một
thách thức lớn đối với các nhà nghiên cứu mã LDPC. Chưa có phương pháp
mã hoá nào đảm bảo loại bỏ hoàn toàn các vòng kín này. Vì vậy, thực tế vẫn
tồn tại các vòng kín ngắn trên đồ hình Tanner. Do đó, thuật toán SPA không
phải là tối ưu với các chiều dài từ mã ngắn và trung bình. Hơn nữa, phần cứng
để thực hiện thuật toán SPA bị giới hạn bởi độ phức tạp tính toán. Có một số
cải tiến của thuật toán SPA được giới thiệu trong [15], [14]. M. Fossorier đề
xuất phương pháp xấp xỉ cực tiểu-tổng [15]. So sánh với thuật toán SPA,
thuật toán cực tiểu-tổng (Min-Sum Algorithm) giảm độ phức tạp tính toán đi
rất nhiều nhưng kết quả là chất lượng giảm đi từ 0,5 đến 1 dB. Để cải thiện
chất lượng thuật toán cực tiểu-tổng, một số cải tiến của thuật toán này đã
được nghiên cứu và đề xuất với việc sử dụng hệ số hiệu chỉnh [69]. Như vậy,
trên thế giới mới chỉ có các nghiên cứu về việc giảm độ phức tạp thuật toán
tổng-tích SPA mà chưa có nghiên cứu cải thiện chất lượng thuật toán này.
Việc cải tiến chất lượng thuật toán SPA nhằm nâng cao chất lượng giải mã
LDPC là một vấn đề nghiên cứu của luận án, làm cơ sở khoa học nâng cao
tính ứng dụng của các mã LDPC vào các hệ thống thông tin vô tuyến số hiện
tại và trong tương lai.