Xem mẫu
- Hội thảo quốc gia 2014 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT2014)
Nghiên cứu kỹ thuật giải mã mềm với thuật
toán BPA-EH cải tiến cho mã LDPC
Nguyễn Anh Tuấn Phạm Xuân Nghĩa
Trường ðại học Công nghệ thông tin & Truyền thông Học viện Kỹ thuật Quân sự
ðại học Thái Nguyên Hà Nội, Việt Nam
Thái Nguyên, Việt Nam Email: nghiapx@mta.edu.vn
Email: natuan@ictu.edu.vn
Tóm tắt - Nội dung bài báo trình bày phương pháp giải ñược mã hóa thành từ mã y = y1, y2 ,...yn sau ñó ñược
mã mềm sử dụng thuật toán BPA-EH cải tiến cho mã kiểm ñiều chế và truyền trên kênh. ðầu vào bộ giải mã BPA
tra chẵn lẻ mật ñộ thấp (LDPC - Low Density Parity là tỷ lệ ước lượng theo hàm log (Log Likelihood Ratio –
Check) dựa trên các ma trận kiểm tra tương ñương nhằm LLR) [2,3]:
khắc phục vấn ñề vòng kín ngắn trong mã LDPC. Phương
pháp này không những cho phép giảm ñáng kể thời gian Pr(yˆi = 0 | r )
L(yˆi ) = log (1)
giải mã so với thuật toán BPA-EH (Belief Propagation Pr(yˆi = 1 | r )
Algorithm based on Equivalent Parity Check Matrix H),
mà còn mang lại ñộ lợi mã hóa cao hơn so với phương
pháp giải mã BPA truyền thống khoảng 0,75 dB trên kênh
Ở ñây r là tập các symbol nhận từ kênh và xác suất
Gauss và 1,2 dB trên kênh pha-ñinh. ñiều kiện Pr(yˆi = 0 | 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:
Từ khóa— Mã LDPC, ma trận kiểm tra tương ñương,
1. Cập nhật bản tin cho tất cả các nút kiểm tra và gửi
giải mã BPA, kênh Gauss, kênh pha-ñinh.
bản tin rji (b) từ nút kiểm tra tới các nút bít nối với nó.
I. GIỚI THIỆU
Mã kiểm tra chẵn lẻ mật ñộ thấp (LDPC-Low 2. Cập nhật bản tin cho tất cả các nút bít và gửi bản
Density Parity Check) ñược biết ñến cùng với các thuật tin q ji (b ) từ các nút bit tới các nút kiểm tra nối với nó.
toán giải mã: BPA, SPA, MPA...[2]. Các thuật toán này
cho chất lượng giải mã khá tốt, tuy nhiên trong các hệ ðầu ra của bộ giải mã là giá trị LLR của các bít mã
thống thông tin hiện ñại việc tiết kiệm công suất phát ñược sử dụng ñể quyết ñịnh thành từ mã thăm dò
mà vẫn ñảm bảo ñược chất lượng thông tin của hệ thống yˆ = yˆ1 , yˆ2 ,..., yˆn . Khi hội chứng s thỏa mãn ñiều kiện:
là vấn ñề thực sự có ý nghĩa. Vì thế, ñã có rất nhiều
công trình nghiên cứu nhằm cải thiện hiệu quả giải mã ˆ T = [0, 0,..., 0]
s = y.H (2)
cho mã LDPC, 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. 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
Với tính chất của một mã khối tuyến tính, cơ chế
phát hiện và sửa sai của mã LDPC dựa vào ña thức kiểm ñến khi ñạt số lần lặp cực ñại γmax và ñưa ra từ mã.
tra H . Mặt khác, với ñặc ñiểm riêng của mình, mã B. Thuật toán giải mã BPA-EH
LDPC lại cho phép áp dụng kỹ thuật giải mã lặp. Từ hai
yếu tố trên ñây gợi cho ta hướng nghiên cứu sử dụng kỹ Như ta ñã biết thuật toán BPA-EH là thuật toán sử
thuật giải mã mềm cho mã LDPC. 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 một từ mã dùng ñúng y bao
II. CÁC THUẬT TOÁN GIẢI MÃ BPA, BPA-EH giờ cũng phải thỏa mãn ñiều kiện (2). ðây là một hệ
VÀ Ý TƯỞNG NGHIÊN CỨU phương trình tuyến tính nên việc thay thế một hàng bằng
A. Thuật toán giải mã BPA việc cộng các hàng bất kỳ với nhau ñể ñược ma trận
Xét mã LDPC (n, k ) với tỷ lệ mã R = k/n (m = n -k kiểm tra tương ñương He thì ma trận này vẫn thỏa mãn
là số lượng các bit kiểm tra). Các bit tin u = u1 , u2 ,...uk (2). Ở ñây mới chỉ chỉ xét trường hợp thành lập He
ISBN: 978-604-67-0349-5 422
- Hội thảo quốc gia 2014 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT2014)
bằng việc thay thế hàng h (a ) của ma trận H bằng cách hàng của H bằng các hàng toàn “0” ta ñã loại bỏ ñược
cộng modulo-2 hàng h (b ) và h (c ) . Việc lựa chọn các các vòng kín ngắn trong H , các vòng kín này là
nguyên nhân dẫn ñến giảm chất lượng mã LDPC. Ý
hàng h (a ) , h (b ) , h (c ) ñược trình bày cụ thể trong [1]. tưởng trên ñây về mặt ñịnh tính sẽ thực sự có ý nghĩa
ñối với các mã LDPC ñặc biệt là các mã có ma trận H
C. ðặt vấn ñề nghiên cứu
kích thước lớn, tuy nhiên việc xác ñịnh số lượng cũng
Trong cách giải quyết vấn ñề của [1] vẫn còn các hạn như vị trí hàng bị thay thế tối ưu ñối với các mã này sẽ
chế. Thứ nhất, kết quả ñánh giá chưa ñược thực hiện với cực kỳ phức tạp vì ta không thể xác ñịnh cụ thể vị trí
kênh pha-ñinh, loại kênh có chất lượng tồi hơn kênh tạp các vòng kín ngắn trong các ma trận này. Do vậy giải
âm Gao-xơ trắng cộng tính AWGN (Addative White pháp ñề xuất trong bài báo ñược trình bày như sau: Khi
Gaussan Noise) rất nhiều, nhưng lại thường gặp hơn xây dựng ma trận tương ñương He ta thực hiện thay thế
trong các hệ thống truyền tin vô tuyến. Thứ hai, việc sử
dụng các ma trận kiểm tra tương ñương ñể giải mã làm các hàng của ma trận H gốc với số lượng ≤1/3 tổng số
cho khối lượng tính toán tăng lên rất nhiều (ít nhất là hàng của ma trận này bằng các hàng toàn “0”, việc thay
bằng số ma trận H tương ñương). Các nhược ñiểm này thế sẽ thực hiện luân phiên với mỗi He tương ứng ở
ñược giải quyết, khắc phục nhờ các nghiên cứu ñược ñề mỗi vòng lặp. Với việc thực hiện như trên ta ñã trả lại
xuất trong bài báo này. những thông tin về các bit tin bị mất ở vòng lặp trước
và giảm lượng thông tin mất mát với mỗi bít tin. Kết
III. CÁC ðỀ XUẤT MỚI ðỐI VỚI PHƯƠNG
quả mô phỏng ñược trình bày dưới ñây sẽ cho ta những
PHÁP GIẢI MÃ BPA-EH ñánh giá ñịnh lượng những khằng ñịnh trên.
A. ðề xuất ứng dụng phương pháp giải mã BPA-EH
cho kênh pha-ñinh ña ñường IV. KẾT QUẢ MÔ PHỎNG, ðÁNH GIÁ
Trong các hệ thống thông tin vô tuyến, ñể tạo ra tính A. Sơ ñồ mô phỏng hệ thống
ñộc lập thống kê giữa các tia sóng, ở phía thu người ta
ñặt các máy thu RAKE, khi ñó tín hiệu trên các tia nhận
ñược là ñộc lập và có thể ñược xử lý song song. Lợi
dụng tính chất này, bài báo ñề xuất ý tưởng sử dụng
thuật toán giải mã BPA-EH cho kênh pha-ñinh ña ñường
theo phương án sau: Thực hiện giải mã ñộc lập trên mỗi
tia, tại ñó sử dụng tất cả các ma trận H tương ñương,
và kết quả là trên mỗi tia nhận ñược một từ mã
yˆi = yˆ1, yˆ2 ,..., yˆn
, các từ mã này ñược ñưa vào bộ quyết
ñịnh cứng ñể tìm ra từ mã chính xác nhất. Với ý tưởng
này ñã kết hợp ñược tính phân tập trong không gian khi
truyền sóng ña ñường với tính phân tập theo thời gian
khi sử dụng mã một cách tối ña.
B. ðề xuất phương pháp xây dựng ma trận kiểm tra Hình 1. Sơ ñồ mô phỏng hệ thống
tương ñương rút ngắn thời gian giải mã
Trong sơ ñồ này, mã LDPC ñược sử dụng là mã bất
Như ñã trình bày trên ñây, trong [1] thực hiện thuật quy tắc [4]. Thuật toán giải mã dựa trên thuật toán
toán BPA-EH bằng việc sử dụng các ma trận kiểm tra BPA-EH cải tiến. Theo lý thuyết mã tuyến tính, thì từ
tương ñương He , các ma trận này ñược tạo ra bằng ma trận H gốc có thể tạo ra các ma trận He bằng việc
việc thay thế hàng (tương ứng với nút kiểm tra kém tin
thay thế 1 hàng h (a ) bằng tổng modulo-2 hàng h (b ) và
cậy). ðiều này dẫn ñến khối lượng tính toán khi thực
hiện giải mã lớn. Ở ñây bài báo ñề xuất phương án xây h (c ) :
dựng các ma trận kiểm tra mới như sau: Ngoài việc thay H e = H |row(a )=row(b )⊕row(c ),a ≠b ≠c (3)
thế hàng có ñộ tin cậy kém của ma trận H gốc, bên
cạnh ñó ta thực hiện thay một số hàng còn lại bằng hàng Việc lựa chọn các hàng h (a ) , h (b ) , h (c ) ñược
toàn “0” ñiều này sẽ làm giảm khối lượng tính toán và chọn trên việc xét giá trị syndrome mềm [1]:
do ñó dẫn ñến giảm thời gian giải mã ñáng kể. Cơ sở lý )
L(s ) ≈ ∏ sign(L(y )) min | L(y |
)
(4)
luận của ý tưởng này ñược giải thích như sau: Với mã i j j
j ∈V
LDPC, một nút bit ñược nối tới nhiều nút kiểm tra, nên i j ∈V
khi ta bỏ bớt một số nút kiểm tra vẫn ñảm bảo là nút bit i
)
tin cậy dựa vào các bản tin từ nút kiểm tra khác. Mặt | L(s ) |= min | L(s ) |= min | L(y ) |
i j
(5)
min i =1,2...m j =1,2...n
khác, ñiều quan trọng hơn là khi thực hiện thay các
ISBN: 978-604-67-0349-5 423
- Hội thảo quốc gia 2014 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT2014)
Ở ñây smin là nút có giá trị tuyệt ñối của syndrome
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(s min ) 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(s max ) 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 như ở trên, ta còn thực
hiện xóa bỏ (thay thế bằng hàng có tất cả các phần tử
ñều là “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.
B. Kết quả mô phỏng
+ Kết quả mô phỏng ñánh giá chất lượng của thuật
toán giải mã BPA-EH cải tiến cho kênh AWGN: Hình 3. So sánh chất lượng giải mã LDPC bằng thuật
Hình 2 và Hình 3 trình bày kết quả ñánh giá chất toán BPA, BPA-EH, BPA-EH cải tiến với ma trận
lượng mã BPA-EH cải tiến trên kênh AWGN với các H 120×240 trên kênh AWGN.
ma trận H 60×120 và H 120×240 .
Trên Hình 3 ta thấy, khi xóa một số hàng của He
ñồng nghĩa với việc ta phá vỡ 1 hoặc một số vòng kín
ngắn trong nó nhưng khi số hàng bị xóa quá lớn sẽ làm
giảm khả năng kiểm tra với một số bít tin. Vì vậy, việc
sử dụng ma trận H tương ñương kết hợp xóa một số
hàng không những làm giảm sự phức tạp trong quá trình
tính toán cỡ (10%) ñối với bộ mã có ma trận kiểm tra
H 60×120 và 20 % ñối với bộ mã ma trận kiểm tra
H 120×240 , mà còn có khả năng tăng chất lượng giải mã
so với thuật toán BPA-EH trình bày trong [1], thời gian
và chất lượng giải mã sẽ ñược cải thiện hơn ñối với các
mã dài. Tuy nhiên ñể ñảm bảo chất lượng giải mã thì
phải tìm ñược số hàng bị xóa phù hợp với từng mã, ñặc
biệt hơn là tìm ñược các hàng xóa phù hợp.
+ Kết quả mô phỏng ñánh giá chất lượng của thuật
toán giải mã BPA-EH cải tiến cho kênh pha-ñinh:
Hình 2. So sánh chất lượng giải mã LDPC bằng thuật Trên cơ sở kết quả mô phỏng trên kênh AWGN, ta
toán BPA, BPA-EH, BPA-EH cải tiến với ma trận tiến hành thực hiện thuật toán BPA-EH cải tiến trên
H 60×120 trên kênh AWGN. kênh pha-ñinh với bộ mã C 1 ñã xóa 3 hàng và bộ mã
C 2 ñã xóa 20 hàng, các kết quả mô phỏng ñược trình
Từ Hình 2 cho thấy, ñối với bộ mã C 1 sử dụng ma
bày trên Hình 4 và Hình 5.
trận H 60×120 , khi thực hiện thuật toán giải mã BPA-EH Kết quả trên Hình 4 và Hình 5 cho thấy, ñối với
cải tiến (BPA-EH-erase 6 rows - xóa 6 hàng từ ma trận kênh pha-ñinh ña ñường, nếu dùng phương pháp giải
He của BPA-EH) và BPA-EH thì chất lượng giải mã mã BPA-EH và BPA-EH cải tiến cho tín hiệu ñầu vào là
tín hiệu tổng hợp của các tia thì chất lượng của 2 thuật
tương ñương nhau việc này mang lại ñộ lợi mã hóa toán này tương ñương nhau và tốt hơn so với chất lượng
khoảng 0,75 dB ở tỷ lệ lỗi bít Pe = 10−4 so với BPA của thuật toán BPA truyền thống khoảng 1,2 dB.
truyền thống, nhưng nếu tăng số hàng bị xóa lên 7 và 12 Bên cạnh ñó kết quả Hình 4 cũng cho thấy, chất
thì chất lượng giải mã của BPA-EH cải tiến sẽ xấu ñi so lượng của thuật toán giải mã BPA – EH cải tiến với việc
với BPA-EH. ứng dụng ñề xuất giải mã trên kênh pha-ñinh ñã trình
bày ở Mục III.A (trên Hình 4 và Hình 5 ñược chú thích
ISBN: 978-604-67-0349-5 424
- Hội thảo quốc gia 2014 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT2014)
là BPA-EH cải tiến 1) tốt hơn ñáng kể so với thuật toán thời gian khi sử dụng mã một cách tối ña làm cải thiện
BPA ban ñầu cỡ 13 dB và cỡ 9 dB so với thuật toán ñáng kể chất lượng giải mã LDPC, ñiều này mở ra một
BPA – EH ở tỷ lệ lỗi 10-4 . hướng nghiên cứu mới trong việc ứng dụng mã kênh
cho các hệ thống truyền tin bị ảnh hưởng bởi pha-ñinh
ña ñường.
V. KẾT LUẬN
Từ kết quả mô phỏng trình bày trong bài báo, có thể
khẳng ñịnh rằng: Các thuật toán giải mã BPA-EH và
BPA-EH cải tiến cho chất lượng mã LDPC ñược cải
thiện cả trên kênh AWGN và trên kênh pha-ñinh. ðộ lợi
trên kênh AWGN khoảng 0,75dB, trên kênh pha-ñinh
khoảng 1 dB (ở Pe = 10−4 ). Khi chất lượng kênh tốt
lên, thì sử dụng thuật toán BPA-EH cải tiến cho chất
lượng tốt hơn so với thuật toán BPA-EH, nó cho ñộ lợi
mã hóa ≥ 6 dB so với thuật toán BPA thuần túy.
Thuật toán BPA-EH cải tiến cho ñộ lợi về thời gian
mã hóa từ 10%-20% so với thuật toán BPA-EH. ðộ lợi
này tăng lên cùng với kích thước ma trận kiểm tra H .
Hình 4. So sánh chất lượng giải mã LDPC bằng
thuật toán BPA, BPA-EH, BPA-EH cải tiến với ma trận TÀI LIỆU THAM KHẢO
H 60×120 trên kênh pha-ñinh. [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.
Hình 5. So sánh chất lượng giải mã LDPC bằng
thuật toán BPA, BPA-EH, BPA-EH cải tiến với
ma trận H 120×240 trên kênh pha-ñinh.
Cũng tương tự, từ kết quả Hình 5 cho thấy, chất
lượng của thuật toán giải mã BPA – EH cải tiến 1 tốt
hơn ñáng kể so với thuật toán BPA ban ñầu cỡ 9 dB và
cỡ 6 dB so với thuật toán BPA – EH ở tỷ lệ lỗi 10-4.
Sở dĩ có ñược kết quả trên, là do trong quá trình giải
mã ñã thực hiện kết hợp ñược tính phân tập trong không
gian trong truyền sóng ña ñường với tính phân tập theo
ISBN: 978-604-67-0349-5 425
nguon tai.lieu . vn
