王秀敏, 洪芳菲, 殷海兵, 李正權(quán), 肖丙剛

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院， 浙江 杭州 310018)

?

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

王秀敏, 洪芳菲, 殷海兵, 李正權(quán), 肖丙剛

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院， 浙江 杭州 310018)

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

LDPC/Turbo；雙模譯碼器；迭代次數(shù)；WIMAX標(biāo)準(zhǔn)；自適應(yīng)迭代譯碼

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

低密度奇偶校驗(yàn)(LDPC,low-density parity-check)[1]碼和卷積Turbo[2]碼是性能接近Shannon極限的糾錯(cuò)碼，廣泛應(yīng)用于現(xiàn)代通信系統(tǒng)的各個(gè)領(lǐng)域，在多?；鶐Ы邮諜C(jī)中都會(huì)用到LDPC碼和Turbo碼譯碼器.關(guān)于LDPC碼和Turbo碼的研究主要包括：高性能、高吞吐率、低消耗的LDPC/Turbo雙模甚至多模譯碼器[3]設(shè)計(jì)與實(shí)現(xiàn)；具有高性能和低編碼復(fù)雜度的LDPC碼和Turbo碼的設(shè)計(jì)；雙模及多模譯碼器的低復(fù)雜度交織器[4]的設(shè)計(jì)等.

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

文獻(xiàn)[5-8]對(duì)譯碼算法進(jìn)行了改進(jìn)和簡(jiǎn)化,計(jì)算過(guò)程只包含簡(jiǎn)單的算術(shù)過(guò)程和邏輯運(yùn)算，從而便于在FPGA平臺(tái)上實(shí)現(xiàn)，但對(duì)具體參數(shù)，比如數(shù)據(jù)量化、迭代次數(shù)、擴(kuò)展因子等分析較少.為了進(jìn)一步研究LDPC碼和Turbo碼的構(gòu)造并考慮LDPC/Turbo雙模譯碼器的實(shí)用性和可操作性，本文在雙模譯碼器優(yōu)化基礎(chǔ)上，進(jìn)行迭代次數(shù)分析.主要工作如下：

(1)在雙模譯碼器通用算法基礎(chǔ)上,實(shí)現(xiàn)了12個(gè)SISO處理單元并行的LDPC/Turbo雙模譯碼器.

(2)提出了一種適用于LDPC和Turbo碼的自適應(yīng)迭代譯碼算法，通過(guò)多條件判定，精確計(jì)算迭代次數(shù)，從而實(shí)現(xiàn)譯碼算法與錯(cuò)誤概率變化特征的自適應(yīng).

(3)通過(guò)預(yù)判決機(jī)制的主導(dǎo)作用，減少平均迭代次數(shù).

1　雙模譯碼器結(jié)構(gòu)的實(shí)現(xiàn)

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

圖1　SISO共享結(jié)構(gòu)Fig.1　The sharing structure of SISO

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

圖2　雙模譯碼器結(jié)構(gòu)Fig.2　The structure of the dual-mode decoder

2　自適應(yīng)迭代譯碼算法

在TDMP算法和Log-MAP算法中，接收到的信道消息經(jīng)過(guò)解調(diào)后成為對(duì)數(shù)似然比值，并經(jīng)過(guò)迭代譯碼運(yùn)算得到更新后的對(duì)數(shù)似然比值.從LDPC校驗(yàn)矩陣H[13]的結(jié)構(gòu)看，該校驗(yàn)矩陣由n個(gè)塊行對(duì)應(yīng)的m個(gè)超碼串聯(lián)而成.WIMAX標(biāo)準(zhǔn)中,LDPC碼(n,k)的碼長(zhǎng)n為2 304,經(jīng)過(guò)數(shù)次迭代后譯出一個(gè)長(zhǎng)為2 304的碼字，而對(duì)應(yīng)的Turbo碼最大碼長(zhǎng)為6 144.雙模譯碼器數(shù)據(jù)流程簡(jiǎn)圖如圖3所示.

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

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

(1)初始化

iter=0,M,Pe,n，

最大迭代次數(shù)M,目標(biāo)差錯(cuò)概率Pe，噪聲功率n；

(2)開(kāi)始

(3)迭代執(zhí)行3種情況

迭代次數(shù)與期望誤碼率的關(guān)系：

(4)結(jié)束輸出

迭代過(guò)程結(jié)束,輸出iter.

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

3　譯碼預(yù)判決機(jī)制

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

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

改進(jìn)的預(yù)判決譯碼停止準(zhǔn)則在保證譯碼性能的前提下，避免了類似文獻(xiàn)[17]的冗余譯碼次數(shù)問(wèn)題(即迭代過(guò)程中，若結(jié)果滿足伴隨式為零，則結(jié)束譯碼，否則繼續(xù)迭代至所設(shè)定的最大迭代次數(shù)為止),在兼顧譯碼器性能和計(jì)算復(fù)雜度的情況下，適當(dāng)減少了迭代次數(shù).

4　結(jié)果分析

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

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

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

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

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

圖5　LDPC碼不同算法的迭代次數(shù)對(duì)比Fig.5　Iterative times of LDPC codes of different algorithms

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

圖6　Turbo碼不同算法的迭代次數(shù)對(duì)比Fig.6　Iterative times of Turbo codes of different algorithms

上述結(jié)果顯示，如果能在技術(shù)上優(yōu)化硬件的關(guān)鍵路徑，提高譯碼器的時(shí)鐘頻率，本譯碼器將非常有競(jìng)爭(zhēng)力.

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

5　結(jié)　論

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

[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]李剛，黑勇，周玉梅，等．動(dòng)態(tài)調(diào)整最大迭代次數(shù)的奇偶校驗(yàn)碼迭代譯碼方法：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]韓國(guó)軍, 劉星成. LDPC碼的信道自適應(yīng)迭代譯碼算法[J].電路與系統(tǒng)學(xué)報(bào)，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最大迭代次數(shù)可

變的LDPC譯碼器設(shè)計(jì)[J].空間電子技術(shù),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

2015-12-10.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61379027,6157118,615721449)；浙江省公益技術(shù)應(yīng)用研究計(jì)劃國(guó)際合作項(xiàng)目(2015C34006).

王秀敏(1963-)，ORCID:http://orcid.org/0000-0003-4735-9777，女，碩士，教授，主要從事電子信息與通信研究，E-mail:wxm6341@163.com.

10.3785/j.issn.1008-9497.2016.05.014

TN 919.3

A

1008-9497(2016)05-573-07