Đánh giá chất lượng một số thuật toán giải mã mới cho mã NB-LDPC

Nội dung text: Đánh giá chất lượng một số thuật toán giải mã mới cho mã NB-LDPC

1. 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
2. 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:QazQajd ( ) ( ); 0 mnjj j mn c định đến độ phức tạp của thuật toán. dc 1 2 :1(),()maIa Qmk ()| a 0 ni 2.2.Một số thuật toán giải mã mới cho mã NB- 3 :Qad '( ), 1( ad ), 2( a ) min max( m 1( 'k ( a ))) LDPC '()k a conf (1,2) k 1,2 Nghiên cứu [6] đã đề xuất thuật toán S-TMM tạo Qa"( ) min 2 max( m 1( 'k ( a ))) n'() a conf (1,2) k 1,2 các bản tin đầu ra của nút kiểm tra song song bằng k 4:forjd0toc 1 do cách tạo cột mở rộng ∆Q(a). Thuật toán S-TMM 5: if (jda 1( )and jda 2( )) then được trình bày trong nội dung Thuật toán 1. Ban 6 :()'()Ram Qa n j đầu, véc-tơ dc giá trị từ nút biến Qm,n(a) được chuyển 7: else 8 :()''()Ram Qa từ miền thường (miền normal) sang miền delta (là n j việc sắp xếp lại các giá trị độ tin cậy sao cho phần tử 9: endif 10: endfor 0 có độ tin cậy lớn nhất) bằng biểu thức ∆Qm,n(a+ 11:Rmnm ( a z ) R ( a ), a GF ( q ) z ) = Q (a), với z là giá trị quyết định cứng thứ n njnjj n m,n n Output : R với độ tin cậy cao nhất, khi đó hàng đầu tiên của mn 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 aGFq (), 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,zQanN n argmin mn ( ); m a GF() q đậm trong hai thuật toán. Trong thuật toán này, 2 cột 1:QazQajd ( ) ( ); 0 mở rộng là ∆Q'(a) và ∆Q''(a)được tạo để cập nhật mnjj j mn c dc bản tin đầu ra nút kiểm tra. Cột phụ đầu tiên ∆Q'(a) , 2: zGFq ( ) j và các chỉ số độ lệch được xây dựng tương tự như j1 dc thuật toán [6]. Đường tối ưu thứ 2 với giá trị LLR 3:mam1( ), 1col ( am ), 2( a ) Q m ( a ) | i1 ni nhỏ thứ 2 được dùng để xây dựng cột mở rộng thứ 2 4:Qa(),'(),'()12 a a min max(1('())) m 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 sử dụng giá trị của 2 cột mở rộng này và các chỉ số 5 : forjd0toc 1 do 6 : if(jm 1col ( '1( a )))and jm 1 col ( '2( a )) then độ lệch đã tìm ra ở bước trước. 7: Ram () Qa () n j III. KẾT QUẢ ĐÁNH GIÁ CHẤT LƯỢNG CỦA 8 : elseif( '1(aa ) '2( ) then CÁC THUẬT TOÁN GIẢI MÃ MỚI 9: Ramam ( ) 2( ) nj 10 : else 3.1 Mô hình mô phỏng 11: Ramam () 1() n j Thuật toán được viết và chạy mô phỏng trên 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 :Ramnm ( z ) RaaGFq ( ), ( ) njnjj đượ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
3. 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
4. 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, chuỗi tin sẽ ít hơn khi xảy ra lỗi ở bit đó. Điều này "Reduced-complexity trellis min-max decoderfor non-binary 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 LDPC(120,69) trên trường GF(16) theo thuật toán Zhang, Jingpeng Gao, "FPGA Implementation Scheme of Mixed 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 -7 LDPC Decoding with Accumulative Bubble Check", IEEE độ lợi xấp xỉ 2 dB tại tỉ lệ lỗi bit BER 8.10 . 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 GF(8) với độ lợi 0.7dB tại BER 10-6. Systems II: Express Briefs, Oct. (2020). ISBN: 978-604-80-5076-4 344