基于LDPC/Turbo雙模譯碼器的自適應迭代譯碼算法研究

2016-09-16 03:04:46王秀敏洪芳菲殷海兵李正權肖丙剛

浙江大學學報(理學版) 2016年5期

王秀敏, 洪芳菲, 殷海兵, 李正權, 肖丙剛

(中國計量大學信息工程學院，浙江杭州 310018)

王秀敏, 洪芳菲, 殷海兵, 李正權, 肖丙剛

(中國計量大學信息工程學院，浙江杭州 310018)

針對現有WIMAX標準中LDPC/Turbo雙模譯碼器設計在精確計算時未充分考慮迭代次數的問題，提出了一種適用于LDPC和Turbo碼的自適應迭代譯碼算法，可靈活應用于由FPGA技術實現的雙模譯碼器.該算法通過跟蹤中間消息計算錯誤概率，根據多條件判定精確計算迭代次數，從而實現譯碼算法與錯誤概率變化特征的自適應性；通過改進的預判決機制減少平均迭代次數.利用Matlab搭建WIMAX系統測試鏈路，對TDMP多種算法的誤碼性能與迭代次數的關系進行測試，實現了12個SISO處理單元并行的LDPC/Turbo雙模譯碼器.結果表明，所設計的譯碼器減少了算法中冗余的迭代過程，并且完全滿足該標準下最大碼長的要求.

LDPC/Turbo；雙模譯碼器；迭代次數；WIMAX標準；自適應迭代譯碼

Journal of Zhejiang University(Science Edition), 2016,43(5):573-579

低密度奇偶校驗(LDPC,low-density parity-check)[1]碼和卷積Turbo[2]碼是性能接近Shannon極限的糾錯碼，廣泛應用于現代通信系統的各個領域，在多模基帶接收機中都會用到LDPC碼和Turbo碼譯碼器.關于LDPC碼和Turbo碼的研究主要包括：高性能、高吞吐率、低消耗的LDPC/Turbo雙模甚至多模譯碼器[3]設計與實現；具有高性能和低編碼復雜度的LDPC碼和Turbo碼的設計；雙模及多模譯碼器的低復雜度交織器[4]的設計等.

目前國內外都已有實現雙模譯碼器的報道.HUNG等[5]設計了一種基4的8個SISO(soft-input soft-output)譯碼器并行的LDPC/Turbo雙模譯碼器，Turbo碼吞吐率可達333 Mbps，LDPC碼的吞吐率可達800 Mbps.理論上，現有研究都只針對BP和MS算法的改進，例如，文獻[6]在碼長為無限的理想情況下制定了相應的密度演化方程，以預測平均比特錯誤概率.在最優參數分析上，文獻[7]提出利用一種新型的停止準則：根據節點傳遞的后驗概率求解LDPC譯碼器的最大迭代次數.文獻[8]基于同樣的思路，提出一種有效降低LDPC碼解碼復雜度的混合解碼方法.

文獻[5-8]對譯碼算法進行了改進和簡化,計算過程只包含簡單的算術過程和邏輯運算，從而便于在FPGA平臺上實現，但對具體參數，比如數據量化、迭代次數、擴展因子等分析較少.為了進一步研究LDPC碼和Turbo碼的構造并考慮LDPC/Turbo雙模譯碼器的實用性和可操作性，本文在雙模譯碼器優化基礎上，進行迭代次數分析.主要工作如下：

(1)在雙模譯碼器通用算法基礎上,實現了12個SISO處理單元并行的LDPC/Turbo雙模譯碼器.

(2)提出了一種適用于LDPC和Turbo碼的自適應迭代譯碼算法，通過多條件判定，精確計算迭代次數，從而實現譯碼算法與錯誤概率變化特征的自適應.

(3)通過預判決機制的主導作用，減少平均迭代次數.

1　雙模譯碼器結構的實現

目前Turbo碼的譯碼算法主要包括MAP算法、Log-MAP[9]算法、Log-MAP簡化算法以及與滑窗結合的各類算法.LDPC碼的譯碼算法主要包括BP、MS[10]、NMS、TDMP等.本文用TDMP及Log-MAP算法作為LDPC/Turbo雙模譯碼器的譯碼算法.其中LDPC碼和Turbo碼的譯碼核心計算公式都涉及相同的計算函數[11]，因此只要LDPC碼的TDMP[12]算法與Turbo碼的Log-MAP算法，就可以在2種不同模式的譯碼算法LDPC和Turbo間建立關聯.圖1是譯碼器計算單元SISO共享結構圖.SISO共享結構中主要涉及分支度量計算、前后向度量計算、外信息(內信息)和后驗信息計算.

圖1　SISO共享結構Fig.1　The sharing structure of SISO

雙模譯碼器主要分為2部分：由自適應迭代譯碼算法實現的參數配置和基于FPGA技術實現的雙模譯碼器結構.圖2中SISO0-SISO11區域便是本文實現的2種算法共用模塊的中心計算處理單元.此外，本文在簡化雙模譯碼器設計的基礎上，創新性地引入了自適應迭代譯碼算法，指導LDPC/Turbo雙模譯碼器的實現.圖2簡要給出了參數配置與雙模結構系統的關系.從參數配置方面考慮，自適應迭代譯碼算法可以分別對LDPC和Turbo碼進行迭代次數的分析，甄選出最適合的碼率、迭代次數及偏移因子.本文主要研究迭代次數，通過對各節點消息傳遞變化規律的分析，采用預判決停止機制，以提高LDPC碼和Turbo碼的迭代譯碼效率，并且通過仿真，對比不同算法的迭代次數.

圖2　雙模譯碼器結構Fig.2　The structure of the dual-mode decoder

2　自適應迭代譯碼算法

在TDMP算法和Log-MAP算法中，接收到的信道消息經過解調后成為對數似然比值，并經過迭代譯碼運算得到更新后的對數似然比值.從LDPC校驗矩陣H[13]的結構看，該校驗矩陣由n個塊行對應的m個超碼串聯而成.WIMAX標準中,LDPC碼(n,k)的碼長n為2 304,經過數次迭代后譯出一個長為2 304的碼字，而對應的Turbo碼最大碼長為6 144.雙模譯碼器數據流程簡圖如圖3所示.

圖3　LDPC和Turbo碼的消息傳遞流程圖Fig.3　The messaging flowchart of LDPC and Turbo

根據上述LDPC和Turbo碼的消息傳遞過程，以及跟蹤譯碼器中后驗消息錯誤概率的變化情況，分析譯碼收斂特性，得到自適應迭代譯碼算法偽代碼.

(1)初始化

iter=0,M,Pe,n，

最大迭代次數M,目標差錯概率Pe，噪聲功率n；

(2)開始

(3)迭代執行3種情況

迭代次數與期望誤碼率的關系：

(4)結束輸出

迭代過程結束,輸出iter.

圖4　迭代次數分析流程圖Fig.4　The analysis flowchart of iterations

3　譯碼預判決機制

自提出Turbo碼和LDPC碼以來，眾多學者對這2種碼的迭代停止準則進行了分析和研究，主要可歸納為2種：基于譯碼器輸出判決符號，即硬判決準則和基于譯碼器輸出似然比，即軟判決準則.硬判決準則的算法性能比較差，軟判決準則的復雜度較高.改進后的預判決譯碼停止準則充分考慮了平均迭代次數、譯碼性能和譯碼計算復雜度，并進行了良好折中，而且可以在性能損失不大的情況下使譯碼速度得到有效提高.

目前在LDPC/Turbo雙模高速譯碼器實現上，已有較豐碩的成果.但在FPGA平臺上均采用固定最大迭代次數的方法，譯碼過程中迭代次數設置為一個固定值，該固定值的選取一直缺乏有力的數據支持.從LDPC碼和Turbo碼的譯碼誤比特率與迭代次數的關系可以發現，誤比特率隨迭代次數的增加逐漸減小，但當達到一定的迭代次數后，譯碼的性能不再改善，此時繼續迭代只會增加計算的復雜度，造成系統時延.所以在保證譯碼性能的前提下，應盡量減少迭代次數，以降低硬件實現的復雜度.為了解決這一問題，文獻[14]提出了動態最大迭代次數可變的迭代譯碼方法，但其沒有考慮具體的硬件實現.該方法預先將每次LDPC譯碼時實際使用的迭代次數與最大迭代次數的差值累加，將該累加結果作為剩余可用的迭代次數R，根據當前R值與最大迭代次數的初始值，動態調整最大迭代次數.此方法需要先將所有譯碼數據輸入存儲器，然后再進行譯碼，是一種非實時型譯碼，且需要占用大量的存儲空間，在硬件資源受限的系統中不可用.

改進的預判決譯碼停止準則在保證譯碼性能的前提下，避免了類似文獻[17]的冗余譯碼次數問題(即迭代過程中，若結果滿足伴隨式為零，則結束譯碼，否則繼續迭代至所設定的最大迭代次數為止),在兼顧譯碼器性能和計算復雜度的情況下，適當減少了迭代次數.

4　結果分析

研究不同譯碼算法與迭代次數的相互關系.在Matlab仿真平臺上以WIMAX標準的碼率為1/2，碼長為2 304的LDPC碼和碼長為6 144的Turbo碼為例，對BP算法、MS算法、NMS算法、OMS算法、TDMP算法、TDMP-NMS算法、Log-MAP算法和Log-MAP滑窗算法的誤碼率和平均迭代次數進行了分析，信道模型為AWGN，采用2BPSK的調制方式.NMS算法中歸一化因子α=0.9，OMS算法的β=0.125，均為該情況下的最優校正因子.用本文方法進行仿真，各譯碼性能曲線如圖5和6所示.

圖5表明，在相同噪聲功率下，并且在最大迭代次數內可以達到期望誤碼率時，TDMP和TDMP-NMS算法的迭代次數僅為其他4種算法的1/2，這也說明TDMP和TDMP-NMS算法比其他算法的收斂速度約快一倍.從收斂速度上亦可說明，采用TDMP作為雙模譯碼器中LDPC碼的譯碼算法是可行的.

表1列舉了各種算法在信噪比SNR為2.0，即對應的噪聲n=0.631 0時的仿真數據.表2中的迭代次數是通過取大量樣本點(本文采用1 000個樣本點)最后求平均值得到.

仿真圖圖6比較了Log-MAP滑窗算法和Log-MAP算法的性能,仿真期望誤碼率分別為Pe=0.1，0.01，0.001和0.000 2,實驗中碼率R為1/2,碼長為6 144.可以看到，隨著PNO(噪聲功率)的增大，迭代次數隨之增大，但是PNO達到某一值時，誤碼率無法達到期望誤碼率pe，此時將譯碼次數設定為-1(如果不設為-1，那么迭代次數就是最大迭代次數M).

用本文提出的自適應迭代譯碼算法實現了LDPC/Turbo雙模譯碼.上述仿真結果中當SNR為2時(設定期望誤碼率為0.000 5和0.000 2)，TDMP和Log-MAP算法對應的迭代次數分別為6和3.采用Cyclone IV系列的FPGA EP4CE115F29C7作為目標器件，綜合結果顯示，雙模譯碼器共消耗邏輯單元個數為5.94 k，最大工作頻率為68 MHz，表2為本文譯碼器與其他雙模譯碼結構的吞吐率與迭代次數.從表2可以看出，本譯碼器在綜合時鐘頻率較低的情況下依然獲得了很高的吞吐率，同時，因為減少了迭代次數，其譯碼延時也較短.

圖5　LDPC碼不同算法的迭代次數對比Fig.5　Iterative times of LDPC codes of different algorithms

表1　不同誤碼率下各算法的迭代次數

圖6　Turbo碼不同算法的迭代次數對比Fig.6　Iterative times of Turbo codes of different algorithms

上述結果顯示，如果能在技術上優化硬件的關鍵路徑，提高譯碼器的時鐘頻率，本譯碼器將非常有競爭力.

表2　雙模譯碼器迭代次數和性能比較

5　結　論

提出了一種應用于LDPC/Turbo雙模譯碼器的自適應迭代次數分析算法，該算法通過跟蹤譯碼器中間消息的錯誤概率變化情況，分析譯碼收斂特性，結合改進的預判決機制，得到了特定信道下不同算法的迭代次數.在沒有增加任何運算復雜度的情況下，避免了冗余的迭代過程，有效減少了平均迭代次數，適用于硬件資源受限條件下高速譯碼器的設計.此外，本文設計的LDPC/Turbo雙模譯碼器可實現多碼長、多通信高速譯碼.

[1]GALLAGER R G. Low-density parity-check codes[J]. IEEE Information Theory,1962,8(1):21-28.

[2]BERROU C, GLAVIEUX A, THITIMAJSHIMA P. Near Shannon limit error-correcting coding and decoding: Turbo-codes[C]// IEEE ICC’93. Geneva：IEEE,1993:1064-1070.

[3]SUN Y, JOSEPH R C. A flexible LDPC/Turbo decoder architecture[J]. J Sign Process Syst,2011,64(1):1-16.

[4]FONSEKA J P, DOWLING E M, BROWN T K, et al. Constrained interleaving of Turbo product codes[J]. IEEE Communications Letters,2012,16(9):58-63.

[5]HUNG L C, SHIANG Y C. Multi-mode radix-4 SISO kernel design for Turbo/LDPC decoding[J]. IEEE Very Large Scale Integration(VLSI) Systems,2015,23(10):2256-2267.

[6]ALEXIOS B S, ANDREAS B. Density evolution for Min-Sum decoding of LDPC codes under unreliable message storage[J]. IEEE Communications Letters,2014,18(5):849-852.

[7]XIA Tian, WU H C, HUANG S C H. A new stopping criterion for fast low-density parity-check decoders[C]//IEEE Global Communications Conference (GLOBECOM).Atlanta:IEEE,2013:3661-3666.

[8]WANG Hua, FAN Guangrong, KUANG Jingming. A hybrid low complexity decoding of LDPC codes[C]//Wireless, Mobile and Multimedia Networks (ICWMNN 2010), IET 3rd International.Beijing:IET，2010: 108-112.

[9]CHEN Jienan, HU Jianhao. High throughput stochastic Log-MAP Turbo-decoder based on low bits computation[J]. IEEE Signal Processing Letters,2013,20(11):1098-1101.

[10]WIBERG N, LOELIGER H A, KOTTER R. Codes and iterative decoding on general graphs[C] //IEEE Information Theory. Whistler:IEEE,1995:468.

[11]CONDO C, MARTINA M, MASERA G. VLSI implementation of a multi-mode Turbo/LDPC decoder architecture[J]. IEEE Transactions on Circuits and Systems I-Regular Papers, 2013,60(6):1441-1454.

[12]ZHAO Ming, ZHANG Xiaolin, ZHAO Ling, et al. Design of a high-throughput QC-LDPC decoder with TDMP scheduling[J]. IEEE Circuits and Systems-II: Express Briefs,2015,62(1):14-25.

[13]MARCO B, FRANCO C. Optimization of the parity-check matrix density in QC-LDPC code-based MCEliece cryptosystems[C]//Communications Workshops (ICC), 2013 IEEE International.Budapest:IEEE，2013:707-711.

[14]李剛，黑勇，周玉梅，等．動態調整最大迭代次數的奇偶校驗碼迭代譯碼方法：CN200710177791.5[P].2009-05-27.

LI Gang, HEI Yong, ZHOU Yumei, et al. Iterative Decoding Method for Dynamically Adjusting the Maximum Iteration Number of Parity Check Code:CN200710177791.5[P].2009-05-27.

[15]韓國軍, 劉星成. LDPC碼的信道自適應迭代譯碼算法[J].電路與系統學報，2010，15(1):102-107.

HAN Guojun, LIU Xingcheng. An adaptive data hiding algorithm in wavelet domain based on texture analysis[J]. Journal of Circuits and Systems,2010,15(1):102-107.

[16]LIU C H, YEN S W. CHEN C L, et al. An LDPC decoder chip based on self-routing network for IEEE 802.16e applications[J]. IEEE Journal of Solid Circuits,2008，43(3)：684-694.

[17]WANG Wenjun, WU Xiaoguang, ZHU Xiaoxuan. A 223Mbps FPGA implementation of (10 240, 5 120) irregular structured low density parity check decoder[C]//IEEE Vehicular Technology Conference.Singapore:IEEE，2008：761-771.

[18]謝天嬌，袁瑞佳，陳超.基于FPGA最大迭代次數可

變的LDPC譯碼器設計[J].空間電子技術,2015，12(2):68-71.

XIE Tianjiao, YUAN Ruijia, CHEN Chao. A max iterative variable LDPC decoder based on FPGA[J]. Space Electronic Technology,2015,12(2):68-71.

[19]MURUGAPPA P, BAZIN J N, BAGHDADI A, et al. FPGA prototyping and performance evaluation of multi-standard Turbo/LDPC encoding and decoding[C]//Rapid System Prototyping (RSP), 2012 23rd IEEE International. Tampere:IEEE，2012:143-148.

Research on adaptive iterative decoding algorithm based on LDPC/Turbo dual-mode decoder.

WANG Xiumin, HONG Fangfei, YIN Haibing, LI Zhengquan, XIAO Binggang

(CollegeofInformationEngineering,ChinaJiliangUniversity,Hangzhou310018,China)

In view of the shortcoming that the design of LDPC/Turbo dual-mode decoder does not fully consider the precise calculation of iteration number, we propose a adaptive iterative decoding algorithm which is suitable for LDPC and Turbo codes. The algorithm is used to calculate the error probability by tracking the middle messages, and to calculate the number of iterations according to multi-conditions, thus we can achieve the self-adaptability of the variation of the decoding algorithm according to the error probability. We reduce the average number of iterations by applying an improved predecision mechanism, and build the test link of WIMAX system on Matlab platform to test the relationship between the BER performance of the multi-algorithms and iteration number, and implement the LDPC/Turbo dual-mode decoder with 12 SISOs parallel processing units. The result shows that the design of the decoder fully satisfies the requirement of the maximum code length under the standard, and can reduce the redundant iterative process.

LDPC/Turbo; dual-mode decoder; iteration number; WIMAX standard; adaptive iterative decoding