Nghiên cứu, đánh giá chất lượng của thuật toán BPA-EH cải tiến cho mã LDPC

Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 177 – 181 
177 
- LDPC 
Phạm Xuân Nghĩa1, Nguyễn Anh Tuấn2*, Nguyễn Đức Đài1 
 1Học viện Kỹ thuật quân sự 
 2Trường Đại học Công nghệ thông tin và truyền thông – ĐH Thái Nguyên 
TÓM TẮT 
kiểm tra chẵn lẻ mật độ thấp (LDPC-Low 
Density Parity Check)
-
1,2 dB trên kênh pha-đinh. 
Từ khóa: Mã LDPC, ma trận kiểm tra tương đương, giải mã BPA, kênh Gauss, kênh fadinh 
ĐẶT VẤN ĐỀ* 
Mã kiểm tra chẵn lẻ mật độ thấp (LDPC-Low 
Density Parity Check)
, tuy nhi
. 
có rất nhiều công trình nghiên cứu nhằm cải 
thiện hiệu quả bộ giải mã này, trong đó cải 
tiến nâng cao chất lƣợng giải mã vẫn là nội 
dung đang tiếp tục đƣợc nghiên cứu. 
 H. Mặt khác,
. T
. 
CÁC THUẬT TOÁN GIẢI MÃ BPA, BPA-
EH VÀ Ý TƢỞNG NGHIÊN CỨU 
Thuật toán giải mã BPA 
Xét mã LDPC ( , )n k với tỷ lệ mã 
/R k n ( m n k là số lƣợng các bit kiểm 
tra). Các bit tin 1 2, ,... ku u u u đƣợc mã hóa 
thành từ mã 1 2, ,... ny y y y sau đó đƣợc 
điều chế và truyền trên kênh. Đầu vào bộ giải 
mã BPA là tỷ lệ ƣớc lƣợng theo hàm log (Log 
Likelihood Ratio – LLR) [2,3]: 
*
 Tel: 0912 998396, Email: natuan@ictu.edu.vn 
Pr( 0 | )
( ) log
Pr( 1| )
i
i
i
y r
L y
y r
 (1) 
Ở đây r là tập các symbol nhận từ kênh và 
xác suất điều kiện Pr( 0 | )iy r . Thuật toán 
BPA [2,3] là thuật toán giải mã lặp có hai 
công đoạn chính: 
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 rji(b) từ nút kiểm tra tới các nút 
bít nối với nó. 
2. Cập nhật bản tin cho tất cả các nút bít và 
gửi bản tin qji(b) 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 
bít mã đƣợc sử dụng để quyết định thành từ 
mã thăm dò 
^ ^ ^ ^
1 2, ,..., ny y y y . Khi hội chứng 
s thỏa mãn điều kiện: 
^
. [0,0,...,0]Ts y H (2) 
Thì dừng lặp đƣa ra từ mã hợp lệ 
^
y . Nếu 
điều kiện (2) không thỏa mãn thì quá trình 
đƣợc thực hiện lại cho đến khi đạt số lần lặp 
cực đại axm và đƣa ra từ mã. 
-EH 
Nhƣ ta đã biết thuật toán BPA-EH là thuật 
toán sử dụng các ma trận kiểm tra tƣơng 
đƣơng [1]. Từ lý thuyết của mã tuyến tính, ta 
thấ y
Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 177 – 181 
178 
(2). Đây là một hệ 
phƣơng trình tuyến tính nên việc thay thế một 
hàng bằng việc cộng các hàng bất kỳ với nhau 
để
eH
ỉ xét trƣờng hợ eH
ế h(a) của ma trận H bằng 
cách cộng modulo 2 hàng h(b) và h(c). Việc 
lựa chọn các hàng h(a), h(b), h(c) đƣợ
ụ thể trong [1]. 
[1] vẫn còn 
các hạn chế
-
, việ
. 
CÁC ĐỀ XUẤT MỚI ĐỐI VỚI PHƢƠNG 
PHÁP GIẢI MÃ BPA-EH 
- – 
ố
- –
^ ^ ^ ^
1 2, ,...,i nY y y y
hần kết quả mô 
phỏng, đánh giá. 
, trong [1] thực hiện 
thuật toán BPA-EH bằng việc sử dụng các ma 
trậ eH , các ma trậ
ợc tạo ra bằng việc thay thế
ểm tra kém tin cậy). 
Điều này dẫn đến khối lƣợ
ớn. Ở ề xuấ
nhƣ sau: Ngoài việc thay thế hàng có độ tin 
cậ ậ , chúng ta cũng có 
thể thay thế một số ại bằ
toàn “0” điều này sẽ làm giảm khối lƣợ
đáng kể
, một nút bit 
đƣợc nối tới nhiều nút kiểm tra, nên khi ta bỏ 
bớt một số nút kiểm tra vẫn đảm bảo là nút bit 
tin cậy dựa vào các bản tin từ nút kiể
. 
KẾT QUẢ MÔ PHỎNG, ĐÁNH GIÁ 
Sơ đồ mô phỏng hệ thống 
Nguồn tin Mã LDPC
Điều chế 
BPSK
Kênh truyền
Giải điều chế 
BPSK
Giải mã LDPC
So sánh
BPSKmod
s y
ŷŝ
BER
Hình 1. Sơ đồ mô phỏng hệ thống 
Trong sơ đồ
 [4]. Thuật toán giải mã dựa 
Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 177 – 181 
179 
trên thuật toán BPA-EH cải tiến. Theo lý 
thuyết mã tuyến tính, thì từ ma trận H gốc có 
thể tạo ra các ma trận He bằng việc thay thế 1 
hàng h(a) bằng tổng module 2 hàng h(b) và 
h(c): 
ow( ) ow( ) ow( ),|e r a r b r c a b cH H 
(3) 
Việc lựa chọn các hàng h(a), h(b), h(c) đƣợc 
chọn trên việc xét giá trị syndrome mềm [1]: 
( ) ( ( ))min | ( |
i i
i j j
j V j V
L s sign L y L y
(4) min
1,2... 1,2...
| ( ) | min | ( ) | min | ( ) |i j
i m j n
L s L s L y
 (5) 
Ở đây smin là nút có giá trị tuyệt đối của 
syndrome là nhỏ nhất trong lần giải mã đầu 
tiên. Nhƣ ta đã biết nút kiểm tra có syndrome 
nhỏ nhất sẽ kết nối với nút tin có độ tin cậy 
thấp nhất, nên ta chọn a là hàng ứng với 
L(smin) có giá trị nhỏ nhất mang dấu dƣơng 
(việc lựa chọn dấu dƣơng đảm bảo chắc chắn 
syndrome này bị lỗi), hàng b ứng với L(smax) 
có giá trị lớn nhất mang dấu âm, còn hàng c 
ứng với L(si) có giá trị tăng dần với 
a b c . 
Ngoài việc thay thế hàng n
0”) ngẫu nhiên một số 
hàng trừ những hàng có độ tin cậy kém đã 
thay và hàng có độ tin cậy lớn nhất. 
Kết quả mô phỏng 
-
-
AWGN. 
2 
-
H60x120 H120x240.
h , đối với bộ mã C1
H60x120, khi thực hiện thuậ
BPA-EH cải tiế - - -
He -
-
nhau việ
Pe=10
-4
, nhƣng nếu tăng số hàng bị
-
-EH. 
Hình 2. 
, BPA-EH, BPA-EH cải tiế
60x120 trên kênh AWGN 
Hình 3. 
, BPA-EH, BPA-EH cải tiế
120x240 trên kênh AWGN 
Trên h , k
He
. Vì vậy, việc sử dụng ma 
trận H tƣơng đƣơng kết hợp xóa một số
ảm sự phức tạp trong quá 
trình tính toán cỡ (10%) đối với bộ
H60x120 và 20 % đối với bộ
H120x240
-
1 1.5 2 2.5 3 3.5 4 4.5
10
-7
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
Eb/No
B
E
R
Danh gia do thi BER cua ma LDPC bat quy tac
BPA
BPA-EH
BPA-EH erase 12 rows
BPA-EH erase 30 rows
BPA-EH erase 20 rows
Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 177 – 181 
180 
. 
- 
-
pha – đinh: 
Dựa vào kết quả mô phỏng trên kênh AWGN, 
ta tiến hành thực hiện thuật toán BPA-EH cải 
tiến trên kênh pha – đinh với bộ mã C1 đã xóa 
6 hàng và bộ mã C2
h
Eb/N0
H60x120 -
- –
 -
10%). Khi Eb/N0
˃
–
-
- 
Pe=10
-5
. 
Hình 4. 
, BPA-EH, BPA-EH cải tiế
60x120 trên kênh pha – đinh 
1 2
H(120x240 b/N0
- -
Pe=10
-4
b/N0 ˃
-
-
-
 Pe=10
-5
. 
Hình 5. 
, BPA-EH, BPA-EH cải tiế
n H120x240 trên kênh pha - đinh 
KẾT LUẬN 
ả ẳ
-
-
-
–
e = 10
-4
-
-
t . 
-
-
-
H. 
TÀI LIỆU THAM KHẢO 
1. Nguyen Tung Hung, “A new decoding 
algorithm based on equivalent parity check matrix 
for LDPC codes,” REV Journall on Electronics 
and Communications, Vol.3, No. 1-2, Jannuary – 
June, 2013 
2. R,Gallager, “Low-density parity-check codes,” 
IRE Trans, Information Theory, pp. 21-28. 
January 1962. 
3. William E. Ryan, “An introduction to LDPC 
codes,” Department of Electrical and Computer 
Engineering, the University of Arizona, August 
19,2003. 
4. Thomas J. Richardson, M. Amin Shokrollahi, 
Member, IEEE, and Rudiger L.Urbanker “Design 
of capacity-Approaching irregular low-density 
parity-check codes,”IEEE Transactions on 
Information Theory, Vol. 47,No. 2, February 2001.
1 2 3 4 5 6 7 8 9 10
10
-7
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
Eb/No
B
E
R
Danh gia do thi BER cua ma LDPC bat quy tac
BPA
BPA-EH cai tien
BPA-EH
1 2 3 4 5 6 7 8 9 10
10
-8
10
-7
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
Eb/No
B
E
R
Danh gia do thi BER cua ma LDPC bat quy tac
BPA
BPA-EH cai tien
BPA-EH
Trần Ngọc Bích và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 171 – 176 
181 
SUMMARY 
RESEARCH, QUALITY ASSESSMENT OF IMPROVED 
BPA-EH ALGORITHM FOR LDPC CODES 
Pham Xuan Nghia
1
, Nguyen Anh Tuan
2*
, Nguyen Duc Dai
1
 1Le Quy Don Technical University, 
2College of Information and Communication Technology - TNU 
This paper presents the decoding method for LDPC code based on Equivalent parity check matrix. 
This method did not allow significant reduction in decoding time compared with BPA decoding 
techniques, but also improve LDPC decoding perfomance. Simulation results show that the new 
LDPC decoding algorithm can improve LDPC decoding perfomance compared with traditional 
BPA approximately 0.75 dB on Gaussian channels and 1.2 dB on fadinh channels. 
Keywords: LDPC code, Equivalent parity check matrix, BPA decoding, Gaussian channels, 
fadinh channels. 
Ngày nhận bài:31/12/2013; Ngày phản biện:20/1/2014; Ngày duyệt đăng: 9/6/2014 
Phản biện khoa học: TS. Phùng Trung Nghĩa – Trường Đại học Công nghệ Thông tin & Truyền thông- ĐHTN
*
 Tel: 0912 998396, Email: natuan@ictu.edu.vn