Xem mẫu
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Đánh giá chất lượng một số thuật toán giải mã
mới cho mã NB-LDPC
Đàm Đức Thuận, Lại Tiến Đệ, Phạm Xuân Nghĩa
Khoa Vô tuyến điện tử
Đại học Kỹ thuật Lê Quý Đôn
Email: thuandd@mta.edu.vn, tiendelai@gmail.com, nghiapx@mta.edu.vn
Abstract - Mã kiểm tra chẵn lẻ mật độ thấp phi nhị một bộ giải mã thích nghi có độ phức tạp thấp dựa
phân (NB-LDPC - Nonbinary Low-Density Parity- trên thuật toán này. Công trình [10] đã kết hợp thuật
Check Codes) cho phẩm chất sửa lỗi tốt hơn so với toán Tổng-tích trên miền Logarit và phép biến đổi
phiên bản mã nhị phân cùng loại. Tuy nhiên, bộ giải FFT nhằm giảm độ phức tạp của bộ giải mã. Tuy
mã NB-LDPC có độ phức tạp rất cao, đặc biệt là quá nhiên, phương pháp này thực hiện giải mã theo thuật
trình xử lý nút kiểm tra. Bài báo này đánh giá chất toán tràn (flooding) khiến bộ giải mã khó thực hiện
lượng sửa lỗi của một số thuật toán giải mã mới cho việc giải mã song song. Các phương pháp thực hiện
mã NB-LDPC trên các trường khác nhau với các mã
có độ dài từ mã khác nhau. Kết quả cho thấy độ lớn
giải mã theo lớp (layered) cho phép giải mã song
của trường hữu hạn và độ dài từ mã sẽ quyết định đến song, giúp giảm yêu cầu tài nguyên phần cứng sẽ
phẩm chất của bộ giải mã. Với độ phức tạp thấp, các được nghiên cứu trong bài báo này. Trong [6], thuật
thuật toán này thể hiện tính khả thi cao trong việc hiện toán Trellis min-max đơn giản hóa (S-TMM -
thực hóa bộ giải mã trên nền tảng phần cứng, có khả Simplified Trellis Min-Max) được đề xuất dựa trên
năng ứng dụng trong các thiết bị thuộc hệ thống nghiên cứu trong [4], không chỉ tăng được thông
truyền thông tiên tiến hay các bộ nhớ đọc ghi tốc độ lượng bộ giải mã mà còn giúp giảm độ phức tạp của
cao. CNU. Bài báo tiến hành đánh giá chất lượng giải mã
Keywords - NB-LDPC, thuật toán giải mã, S-TMM, của hai thuật toán giải mã mới cho mã NB-LDPC là
TEC-TMM. S-TMM và TEC-TMM (Two-Extra- Column Trellis
I. GIỚI THIỆU Min-Max), đánh giá khả năng của các bộ mã NB-
Mã kiểm tra chẵn lẻ mật độ thấp phi nhị phân LDPC với các tham số độ dài và độ lớn của trường
(NB-LDPC) được định nghĩa trên trường GF(q) (q > hữu hạn khác nhau. Các kết quả mô phỏng cho thấy
2) gồm q phần tử được phát triển bởi Davey và phẩm chất giải mã rất tốt của mã NB-LDPC, và sự
MacKay [1]. Mã NB-LDPC tốt hơn dạng nhị phân phụ thuộc của phẩm chất bộ giải mã vào độ lớn
của nó về phẩm chất sửa lỗi và khả năng sửa lỗi cụm trường hữu hạn và độ dài từ mã. Các thuật toán này
khi độ dài từ mã thay đổi. Tuy nhiên, cấu trúc bộ có độ phức tạp giảm đi rất nhiều so với các thuật
giải mã lại có độ phức tạp cao và yêu cầu bộ nhớ toán gốc, kết hợp với khả năng cho phép giải mã
lớn, đặc biệt cho bộ xử lý nút kiểm tra (CNU - phân lớp đã thể hiện tính khả thi cao trong quá trình
Check Node Unit). Điều này làm hạn chế thông hiện thực hóa trên các nền tảng phần cứng.
lượng tối đa và tài nguyên tối thiểu cho cấu trúc bộ Phần tiếp theo của bài báo được trình bày như
giải mã. sau: Mục II giới thiệu tổng quan về mã NB-LDPC
Thuật toán giải mã nguyên bản cho mã NB- và các thuật toán giải mã S-TMM, TEC-TMM.
LDPC là thuật toán tổng tích (QSPA Q-ary Sum- Trong mục III, bài báo trình bày kết quả đánh giá
Product Algorithm) [1] được coi là thuật toán giải phẩm chất một số mã NB-LDPC trên cơ sở sử dụng
mã cho phẩm chất sửa lỗi tối ưu, với trả giá là độ các thuật toán giải mã được trình bày ở Mục II qua
phức tạp cao. Để giảm độ phức tạp giải mã, một số kết quả mô phỏng, cuối cùng là phần Kết luận.
thuật toán xấp xỉ như thuật toán min-sum mở rộng II. KHÁI QUÁT MÃ NB-LDPC VÀ MỘT SỐ
(EMS - Extended Min-Sum) [2] và thuật toán min- THUẬT TOÁN GIẢI MÃ MỚI
max [3] đã được đề xuất nhằm giảm độ phức tạp của 2.1. Giới thiệu mã NB-LDPC
CNU chính là quá trình phức tạp nhất của bộ giải mã
Mã NB-LDPC được xác định bởi một ma trận
NB-LDPC.
kiểm tra H gồm M hàng và N cột. Ma trận H có tính
Thuật toán min-max [3] sử dụng các bộ so sánh chất thưa, nghĩa là phần lớn các vị trí trong ma trận
thay cho các bộ cộng trong [2] nhằm đơn giản hóa có giá trị 0, các phần tử khác không còn lại có giá trị
cấu trúc của CNU cũng như tránh việc tăng các phép hmn thuộc trường GF(q).Gọi dc là trọng lượng
toán số học. Hiện nay, thuật toán Trellis EMS (T- hàng,dv là trọng lượng cột của ma trận H. Mã NB-
EMS) [4], [5] được đề xuất nhằm tăng thông lượng LDPC được phân loại thành mã có quy tắc và mã
cho các bộ giải mã NB-LDPC chấp nhận trả giá về không có quy tắc, trong đó mã có quy tắc là mã có
vùng nhớ lớn hơn, do các bản tin đầu ra của CNU các giá trị dc và dv không đổi. Mã NB-LDPC được
được tạo ra đồng thời. Nghiên cứu [12] đã phát triển biểu diễn thông qua đồ hình Tanner tương ứng với
ISBN: 978-604-80-5076-4 341
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
ma trận H, với các nút biến biểu diễn N cột và các Ratio) của đường là giá trị lớn nhất trong các giá trị
nút kiểm tra biểu diễn M hàng. N(m) và M(n) tương LLR trên đường đó, và phần tử trường tương ứng
ứng biểu diễn tập dc nút biến nối tới nút kiểm tra thứ với mỗi đường là tổng của các phần tử trường trên
m và dv nút kiểm tra nối tới nút biến thứ n. Qm,n(a) đường đó.
và Rn,m(a) là ký hiệu các bản tin trao đổi giữa n nút Với mỗi phần tử trường a khác 0, sẽ tồn tại q/2
biến và m nút kiểm tra (V2C - Variable node to đường có thể có nếu xét tập cấu hình conf(1,2).
Check node) và từ m nút kiểm tra tới n nút biến Đường tối ưu cho mỗi phần tử trường sẽ là đường có
(C2V - Check node to Variable node) cho mỗi ký tự giá trị LLR nhỏ nhất trong số q/2 đường đang xét.
a∈GF(q). Các từ mã đúng là các từ mã thỏa mãn Giá trị LLR của đường tối ưu này sẽ dùng để xây
phương trình kiểm tra chẵn lẻ, thuật toán giải mã lặp dựng giá trị trong cột mở rộng cho phần tử trường a.
là thuật toán được sử dụng phổ biến cho giải mã Thuật toán 2: Thuật toán TEC-TMM [7]
NB-LDPC, bao gồm quá trình xử lý nút biến và quá dc 1
trình xử lý nút kiểm tra, trong đó xử lý nút kiểm tra Initialization : zj GF (q)
j 0
luôn là quá trình có độ phức tạp lớn nhất và sẽ quyết 1: Qmn j ( a z j ) Qmn j (a); 0 j dc
định đến độ phức tạp của thuật toán. dc 1
2 : m1(a), I ( a) Qmn ( a) | k 0
2.2.Một số thuật toán giải mã mới cho mã NB- i
LDPC 3: Q '( a), d1(a ), d 2(a) min max( m1( 'k ( a)))
' k ( a ) conf (1,2) k 1,2
Nghiên cứu [6] đã đề xuất thuật toán S-TMM tạo Q "(a) min 2 max(m1( 'k (a)))
các bản tin đầu ra của nút kiểm tra song song bằng n 'k ( a ) conf (1,2) k 1,2
4 : for j 0 to dc 1 do
cách tạo cột mở rộng ∆Q(a). Thuật toán S-TMM 5 : if ( j d1(a )and j d 2( a)) then
được trình bày trong nội dung Thuật toán 1. Ban 6: Rmn (a )
j
Q '(a)
đầu, véc-tơ dc giá trị từ nút biến Qm,n(a) được chuyển 7 : else
từ miền thường (miền normal) sang miền delta (là 8: Rmn (a ) Q ''( a)
j
việc sắp xếp lại các giá trị độ tin cậy sao cho phần tử 9 : endif
0 có độ tin cậy lớn nhất) bằng biểu thức ∆Qm,n(a+ 10 :endfor
11: Rmn (a zn j ) Rmn ( a), a GF ( q)
zn) = Qm,n(a), với zn là giá trị quyết định cứng thứ n j j
Output : R mn
với độ tin cậy cao nhất, khi đó hàng đầu tiên của
lưới sẽ là đường tối ưu cho phần tử 0 của trường, ký Nghiên cứu [7] đã đề xuất thuật toán TEC-
hiệu là path 0. Tiếp theo, thuật toán tiến hành tìm TMM dựa trên thuật toán S-TMM nhằm giảm độ
bản tin đáng tin cậy nhất, m1(a) cho symbol phức tạp trong kiến trúc phần cứng với chất lượng
a GF (q) , và vị trí tương ứng của chúng trong lưới. gần như tương đương. Thuật toán 2 trình bày các
bước của thuật toán TEC-TMM. Sự khác nhau giữa
Thuật toán 1: Thuật toán S-TMM [6] 2 thuật toán được thể hiện từ tại các bước được in
Input : Qmn , zn arg min Qmn ( a); n Nm đậm trong hai thuật toán. Trong thuật toán này, 2 cột
a GF ( q )
1: Qmn j ( a z j ) Qmn j ( a); 0 j dc mở rộng là ∆Q'(a) và ∆Q''(a)được tạo để cập nhật
dc bản tin đầu ra nút kiểm tra. Cột phụ đầu tiên ∆Q'(a) ,
2: zj GF (q) và các chỉ số độ lệch được xây dựng tương tự như
j 1
3 : m1(a), m1col ( a), m2(a) Qmn (a) |idc1
thuật toán [6]. Đường tối ưu thứ 2 với giá trị LLR
i nhỏ thứ 2 được dùng để xây dựng cột mở rộng thứ 2
4: Q(a), '1 (a), '2 ( a) min max(m1( 'k (a))) là ∆Q''(a). Bản tin đầu ra nút kiểm tra được cập nhật
' k ( a ) conf (1,2) k 1,2
5 : for j 0 to d c 1 do sử dụng giá trị của 2 cột mở rộng này và các chỉ số
6 : if ( j m1col ( '1(a )))and j m1col ( '2(a)) then độ lệch đã tìm ra ở bước trước.
7: Rmn (a) Q(a)
j III. KẾT QUẢ ĐÁNH GIÁ CHẤT LƯỢNG CỦA
8 : elseif ( '1(a) '2(a) then CÁC THUẬT TOÁN GIẢI MÃ MỚI
9: Rmn (a) m2(a)
10 : else
j
3.1 Mô hình mô phỏng
11 : Rmn (a ) m1(a) Thuật toán được viết và chạy mô phỏng trên
j
12 : endif phần mềm để đánh giá chất lượng giải mã. Sơ đồ mô
13 :endfor phỏng được thể hiện trong Hình 1, với mô hình
14 : Rmn (a zn j ) Rmn (a), a GF (q)
j j được là mô hình Monte Carlo để tính lỗi khung
Output : R mn (frame) sử dụng với 1 từ mã được xem là 1 khung.
Đường tối ưu cho các phần tử trường khác 0 sẽ là Chức năng của các khối trong sơ đồ đánh giá chất
các đường chứa ít nhất một phần tử khác 0 với một lượng thuật toán giải mã được trình bày như sau:
giá trị LLR khác 0. Tập cấu hình (configuration set) - Khối tạo bản tin ngẫu nhiên: Sử dụng hàm
được xét là conf(1,2) là một tập gồm các đường khả random để tạo ngẫu nhiên bản tin cần truyền. Vì bộ
thi được tạo từ giá trị tin cậy nhất m1(a) với tối đa 2 mã được xây dựng trên trường GF(q), mỗi một
độ lệch (deviation). Giá trị LLR (Log Likelihood
ISBN: 978-604-80-5076-4 342
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
symbol ứng với log2(q) bits, độ dài bản tin là k nên 1 BPSK. Với chất lượng giải mã tương đương nhưng
bản tin có độ dài k.log2(q) bits. thuật toán TEC-TMM giúp giảm độ phức tạp phần
- Khối mã hóa NB-LDPC: Bản tin được ánh cứng nhờ thay thế các khối tìm giá 2 trị nhỏ nhất
xạ sang thành dạng symbols rồi được mã hóa theo trong S-TMM bằng khối tìm 1 giá trị nhỏ nhất trong
thuật toán đã chọn. TEC-TMM, số lượng bit trao đổi giữa nút biến và
nút kiểm tra cũng được giảm xuống đáng kể [7][9],
đặc biệt đối với các trường lớn, khi dc rất lớn hơn
q/2.
3.3. Đánh giá chất lượng giải mã của thuật toán
TEC-TMM với bộ mã có độ dài khác nhau
Chất lượng giải mã của bộ mã NB-LDPC càng
được thể hiện rõ khi độ dài từ mã càng tăng [1].
Hình 3 thể hiện kết quả mô phỏng chất lượng giải
Hình 1. Sơ đồ mô phỏng đánh giá chất lượng thuật toán giải mã mã của 2 bộ mã NB-LDPC(75,45) và NB-
- Khối điều chế: Bản tin được ánh xạ lại dưới LDPC(120,69) theo thuật toán TEC-TMM trên
dạng bits có độ dài n.log2(q) bits và được đưa vào trường GF(16), các tham số khác của mô hình tương
điều chế BPSK. tự như đã thực hiện với các mô phỏng ở Mục 3.1.
- Kênh truyền: Là kênh AWGN, nhiễu được sinh
ngẫu nhiên theo phân bố Gauss và được cộng trực
tiếp vào tín hiệu.
- Khối giải điều chế: Tính toán xác suất tiên
nghiệm ứng với mỗi symbol của từ mã nhận được.
- Khối giải mã: Đầu vào là xác suất tiên nghiệm
ứng với mỗi symbol của từ mã, sau khi giải mã lặp
theo thuật toán đã chọn, ta thu được từ mã.
- Khối tính lỗi: Kết quả của bộ giải mã sẽ được
loại bỏ các bit kiểm tra, chuyển về dạng bit và so
sánh với chuỗi bit bản tin ban đầu.
3.2 Đánh giá chất lượng giải mã của thuật toán S-
TMM và TEC-TMM
Hình 2 thể hiện kết quả đánh giá chất lượng giải
mã của thuật toán giải mã S-TMM và TEC-TMM
với cùng bộ mã NB-LDPC(35,23) trên trường GF(8)
trên kênh AWGN, với số vòng lặp cực đại là 10. Hình 3. Đánh giá chất lượng của thuật toán TEC-TMM
với hai bộ mã NB-LDPC(75, 45) và NB-LDPC (120,69)
trên trường GF(16)
Từ kết quả nhận được cho thấy, bộ mã có từ mã
dài hơn là NB-LDPC (120,69) có độ dài từ mà
120*4=480 bit cho chất lượng giải mã tốt hơn mã
NB-LDPC (75,45) với độ dài từ mã là 300 bit. Bộ
mã dài hơn cho độ lợi 0.5dB ở mức BER 10-5, và
xấp xỉ 1dB ở mức BER10-7. Bộ mã dài cho độ lợi
7dB ở BER 8.10-6 khi so sánh với việc không sử
dụng mã hóa, trong khi mã ngắn hơn cho độ lợi
5.5dB khi thực hiện so sánh tương tự. Do vậy, với
mã NB-LDPC, bộ mã càng dài sẽ càng cho chất
lượng giải mã tốt hơn, thể hiện rõ ở các vùng SNR
thấp.
3.4. Đánh giá chất lượng giải mã thuật toán TEC-
Hình 2. So sánh chất lượng thuật toán S-TMM và TEC- TMM trên hai trường khác nhau
TMM với bộ mã NB-LDPC(35,23) trên trường GF(8)
Một trong các yếu tố ảnh hưởng tới chất lượng
Từ kết quả nhận được cho thấy thuật toán S-
mã NB-LDPC là trường thể hiện mã, theo [1], chất
TMM và thuật toán TEC-TMM cho phẩm chất giải
lượng của bộ mã trên trường có bậc cao hơn cho
mã là gần như tương đương, với độ lợi 5dB tại BER
chất lượng tốt giải mã tốt hơn so với việc thể hiện
10-3 và 6.2dB tại BER 10-6 khi so sánh với việc
chúng trên các trường bậc thấp, do khi được biểu
không sử dụng mã hóa thể hiện trên đường BER
diễn qua các phần tử khác không của trường, thông
ISBN: 978-604-80-5076-4 343
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
tin không những được chứa trong các symbol này IV. KẾT LUẬN
mà còn được chứa trong từng bit của từng phần tử. Bài báo đã đánh giá và so sánh chất lượng giải
mã của một số thuật toán giải mã mới cho mã NB-
LDPC trên các trường khác nhau, với độ dài từ mã
khác nhau. Kết quả cho thấy với mã NB-LDPC, độ
lớn của trường hữu hạn q và độ dài từ mã sẽ quyết
định tới phẩm chất của bộ mã. Thuật toán S-TMM
và TEC-TMM đều cho chất lượng giải mã rất tốt với
sàn lỗi rất thấp. Với độ phức tạp thấp và khả năng
thực hiện giải mã phân lớp, các thuật toán này rất
phù hợp cho việc triển khai trên phần cứng, thể hiện
tính khả thi cao cho các ứng dụng viễn thông và bộ
nhớ đọc ghi tốc độ cao.
TÀI LIỆU THAM KHẢO
[1] Hllatthew C Davey and David JC MacKay, “Low-density
parity check codes over GF(q),” in Information Theory
Workshop, Jun. 1998, pp. 165–167.
Hình 4. Đánh giá chất lượng thuật toán giải mã TEC-TMM [2] David Declercq and Marc Fossorier, “Decoding algorithms
với bộ mã NB-LDPC(35,23) trên GF(8) và NB- for nonbinary LDPC codes over GF(q),” IEEE Trans. Commun.,
LDPC(120,69) trên GF(16) vol. 55, no. 4, pp. 633–643, Apr. 2007.
[3] Valentin Savin, “Min-max decoding for non binary LDPC
codes,” in Proc. IEEE Int. Symp Inf. Theory, Toronto, ON,
Canada, Jul. 2008, pp. 960–964.
[4] Erbao Li, David Declercq, and Kiran Gunnam, “Trellis based
extended min-sum algorithm for non-binary LDPC codes and its
hardware structure,” IEEE Trans. Commun., vol. 61, no. 7, pp.
2600–2611, Jul. 2013.
[5] Erbao Li, Francisco Garcia-Herrero, David Declercq, Kiran
Gunnam, Jesus O Lacruz, and Javier Valls, “Low latency T-EMS
decoder for non-binary LDPC codes,” in Proc. Conf. Rec. 47th
Asiloma Conf. Signals, Syst. Comput. (ASILOMAR), Nov. 2013,
pp. 831–835.
[6] Jesús O Lacruz, Francisco Garc´ ıa-Herrero, David Declercq,
and Javier Valls, “Simplified trellis min-max decoder architecture
for nonbinary low-density parity check codes,” IEEE Trans. Very
Large Scale Integration (VLSI) Syst., vol. 23, no. 9, pp. 1783–
1792, Sep. 2015.
[7] H. P. Thi and H. Lee, “Two-extra-column trellis min–max
decoder architecture for nonbinary LDPC codes,” IEEE Trans.
Hình 5. Đánh giá chất lượng thuật toán giải mã TEC-TMM Very Large Scale Integration (VLSI) Syst., vol. 25, no. 5, pp.
với bộ mã NB-LDPC(56, 28) trên GF(8) và NB-LDPC(60, 1787–1791, May. 2017.
30) trên GF(16) [8] Bo Zhou, Jingyu Kang, Shumei Song, Shu Lin, Khaled
Abdel-Ghaffar, and Meina Xu, “Construction of non-binary
Khi độ lớn của trường càng lớn, số bit trên một quasi-cyclic LDPC codes by arrays and array dispersions,” IEEE
phần tử trường càng lớn, thông tin chứa trong mỗi Trans. Commun., vol. 57, no. 6, pp. 1652–1662, Jun. 2009.
bit sẽ nhỏ hơn, do đó ảnh hưởng đến chất lượng [9] Nghia Pham Xuan, Huyen Pham Thi, Thuan Dam Duc,
"Reduced-complexity trellis min-max decoderfor non-binary
chuỗi tin sẽ ít hơn khi xảy ra lỗi ở bit đó. Điều này LDPC codes", in Proc. of The National Conference on
được minh họa trên kết quả mô phỏng chất lượng Electronics, Communications and InformationTechnology, pp.
giải mã của hai bộ mã có tốc độ mã xấp xỉ nhau là 89-92, Dec. 2018
NB-LDPC(35,23) trên trường GF(8) và bộ mã NB- [10] Ziyong Wang, Jiahui Meng, Zhibin Deng, Liang
Zhang, Jingpeng Gao, "FPGA Implementation Scheme of Mixed
LDPC(120,69) trên trường GF(16) theo thuật toán Logarithmic Domain FFT-BP Decoding Algorithm Based on
TEC-TMM (Hình 4). Kết quả mô phỏng cho thấy bộ Non-Binary LDPC Codes" in 37th Chinese Control Conference
mã NB-LDPC(120,69) trên trường GF(16) cho chất (CCC), pp. 8459-8464, Jul. (2018).
lượng giải mã tốt hơn nhiều so với mã còn lại, cho [11] Injun Choi, Ji-Hoon Kim, "Memory-Reduced Non-Binary
LDPC Decoding with Accumulative Bubble Check", IEEE
độ lợi xấp xỉ 2 dB tại tỉ lệ lỗi bit BER 8.10-7. Transactions on Circuits and Systems II: Express Briefs, (2017).
Bài báo cũng thực hiện mô phỏng kết quả đánh [12] Min-Ho Kim, Kyeong-Bin Park, Ki-Seok Chung, "A Low-
giá phẩm chất giải mã của hai mã có độ dài xấp xỉ Complexity Adaptive Extended Min-Sum Algorithm for Non-
Binary LDPC Codes", 5th International Conference on
nhau với cùng tốc độ mã 1/2 trên hai trường GF(8) Computational Intelligence and Applications (ICCIA), (2020).
và GF(16). Kết quả mô phỏng trên Hình 5 cũng cho [13] Ángel Álvarez; Víctor Fernández; Balázs Matuz, "An
thấy mã NB-LDPC (60,30) trên GF(16) cho chất Efficient NB-LDPC Decoder Architecture for Space
lượng tốt hơn mã NB-LDPC (56,28) trên trường Telecommand Links", IEEE Transactions on Circuits and
Systems II: Express Briefs, Oct. (2020).
GF(8) với độ lợi 0.7dB tại BER 10-6.
ISBN: 978-604-80-5076-4 344
nguon tai.lieu . vn