多元LDPC碼Min-max自適應譯碼算法

陳紫強,杜婉瑩,謝躍雷

(桂林電子科技大學 無線寬帶通信與信號處理省部重點實驗室，廣西 桂林 541004)

多元LDPC碼Min-max自適應譯碼算法

陳紫強,杜婉瑩,謝躍雷

(桂林電子科技大學 無線寬帶通信與信號處理省部重點實驗室，廣西 桂林 541004)

摘要:為了降低多元低密度奇偶校驗(Low-density parity check，LDPC)碼Min-max譯碼算法的運算量，提出一種自適應Min-max(Adaptive Min-max，AMM)譯碼算法。該方法以Min-max算法為基礎，以每次迭代后的校驗節點錯誤率(Check-node Error Rate，CER)為調節參數，采用自適應算法對變量節點的向量長度進行截短，去除置信度較低的分量，僅對置信度較高的分量進行更新。當CER降低到一定程度時，對校驗節點個數進行自適應截短，僅對不滿足校驗方程的校驗節點進行消息迭代更新，進一步降低AMM算法的復雜度。仿真結果表明，在相同誤碼性能條件下，AMM算法運算量較固定長度截短的Min-max算法減少20%。

關鍵詞:多元LDPC；Min-max；自適應截短；校驗節點錯誤率

為了進一步降低Min-max算法復雜度，本文提出一種多元LDPC碼Min-max(AdaptiveMin-max，AMM)自適應譯碼算法。在每次迭代過程中，以校驗節點錯誤率(Check-nodeErrorRate，CER)為調節參數，對每個節點的LLR向量長度進行自適應截短。當校驗節點錯誤率降低到一定程度時，停止更新已經滿足校驗關系的節點消息，僅對錯誤的節點進行后續迭代更新，進一步降低AMM算法的整體復雜度。

1Min-max譯碼算法

Min-max算法將EMS譯碼算法[6]中加法運算替換為求最大值運算，降低了硬件實現的復雜度，便于工程應用。AMM算法以Min-max算法為基礎，通過自適應截短消息概率向量長度、自適應截短校驗節點更新數量兩種處理方法，降低Min-max譯碼算法的譯碼復雜度。因此，本文首先簡要介紹Min-max算法實現流程。

1)初始化

γj(a)=log(Pr(xj=sj)/Pr(xj=a))，

vi,j(a)=γj(a)

(1)

式中：sj代表xj中最大概率的取值。在Min-max譯碼算法中，初始化步驟前須對參與譯碼的消息概率向量進行降序排序，并選取消息概率較大的前Nm項作為譯碼過程中的初始消息。

2)置換步驟

將變量節點索引值vq與校驗矩陣H相應位置的取值相乘，得到置換之后的索引值矩陣v′q，即

(2)

式中：a=hi,j(×)b，0≤hi,j,a,b≤q-1，符號“(×)”表示GF(q)域上的乘法。

3)校驗節點更新

(3)

其中 a∈{0,1，…,q-1}。

4)逆置換步驟

(4)

式中：a=b(/)hi,j，0≤hi,j,a,b≤q-1。符號“(/)”表示GF(q)域上除法。

5)變量節點更新

(5)

(6)

vi,j(a)=vi,j(a)-x

(7)

變量節點更新中，為了防止式(5)中加法運算結果溢出，對每次變量節點更新運算后進行歸一化處理，對其減去運算結果中最小值，如式(7)所示。

6)后驗信息計算

(8)

2AMM譯碼算法

當Min-max算法能夠正確譯碼時，隨著迭代次數的增加，消息概率向量的數值會越來越集中到可能性較大的前l項(l

圖1　譯碼中CER與BER關系

鑒于此，提出了多元LDPC碼AMM算法，在譯碼過程中引入CER作為調節因子，第一步自適應地選取下一次迭代過程中譯碼的消息概率向量的截短長度，僅更新節點向量中置信度較高的分量；第二步自適應截短校驗節點更新數量，當校驗節點錯誤率降低到一定程度時，提前結束已經正確的校驗節點的更新，僅對不滿足校驗條件的節點進行后續消息迭代更新。圖2給出了AMM算法的算法流程圖。

圖2　AMM算法流程圖

2.1自適應截短節點向量長度

每次迭代結束后，AMM算法需根據當前CER的變化對消息LLR向量長度進行截短。設第i次迭代時，CER值為CERi，AMM算法中消息LLR向量截短為ti。對Min-max算法增加步驟7)，每次完成迭代更新后，計算當前CER的變化率即ΔCERi=CERi-CERi-1，再根據ΔCERi的大小自適應修正下一次迭代消息LLR向量長度ti+1。隨著迭代譯碼的進行，正確的消息越來越集中到消息LLR向量較小的前幾項(對應概率值較大項)中，排列靠后的項對譯碼結果貢獻不大，因此迭代中所需要的消息LLR向量可進行逐步的截短。將ti+1與ΔCERi之間的關系用如下的線性函數表示，即

ti+1=「ti+C×ΔCERi?=

「ti+C×(CERi-CERi-1)?

(9)

式中：t1表示首次迭代所截短消息LLR向量長度，記為A；C表示消息LLR向量長度隨著ΔCER的變化速度；「·?表示向上取整。A與C的取值大小決定了AMM算法的譯碼性能和運算復雜度，因此需要通過實驗找出誤碼性能與運算復雜度折中的A與C的值。AMM譯碼算法步驟7)可分解為：

2)計算CERi，即s中非零值比例。

3)ti+1=「ti+C×ΔCERi?。

2.2自適應截短節點更新數量

在AMM算法中，隨著迭代次數增加，誤碼率逐次下降，不滿足校驗關系的節點數越來越少。此時提前結束已正確的校驗節點消息更新，則在后續譯碼過程中僅需要對錯誤的節點信息進行更新。可通過減少參與譯碼的校驗節點數量來降低譯碼復雜度。當譯碼迭代次數較大時，大部分校驗節點已經獲得正確譯碼消息，減少這些節點消息更新對誤碼性能影響不大。將上述處理過程記為步驟8)。設CERL為校驗節點數量截短操作的臨界值，AMM譯碼算法步驟8)可分解為：

1)比較CERi與CERL大小，若CERi≤CERL，跳至2)；否則跳至3)。

2)找出伴隨式s中非零值所在位置，記為M；跳至步驟2)對校驗矩陣H中M所對應校驗節點和與其相鄰的變量節點進行迭代更新。

3)跳至步驟2)對校驗矩陣H中的所有節點進行譯碼。

3仿真結果分析

AMM算法中的誤碼性能和譯碼復雜度由A值、C值和CERL值這3個參數決定。下面通過實驗仿真確定A、C值以及CERL，再對AMM算法和Min-max算法的運算量進行比較。仿真條件如下：信道條件為高斯白噪聲(AWGN)信道，調制方式為16QAM調制；采用GF(16)域上碼率為0.5，碼長為1 056，PEG(ProgressiveEdgeGrowth)構造下NB-LDPC碼，碼元度分布為λ(x)=0.458 3x3+0.333 4x4+0.208 3x7；仿真時最小幀數設為1 000幀，最小錯誤幀數設為20幀，最大迭代次數設為12，信噪比設為5dB。

3.1A、C參數選取

圖3給出了A、C取不同值情況下AMM算法的誤碼性能。

圖3　AMM算法誤碼率

圖3可以看出，AMM算法的誤碼率隨著C值增加而增加，隨著A值增加而下降。當A值為14、15時，AMM算法的誤碼性能達到了10-5。AMM算法在每次迭代中的消息LLR向量長度值ti隨著ΔCERi的值動態變化，采用ti的加權平均值tv作為分析該算法譯碼復雜度的因子。tv取值越小譯碼復雜度越低。參數A與C的值決定了tv的取值，同時也影響著AMM算法的性能。將圖3中誤碼率接近10-5時，AMM算法中A與C的值列出，如表1所示。

表1誤碼率為10-5時A，C，tv以及BER對比情況

A,C15,815,915,1014,815,1114,915,1214,10tv10.56410.1439.6559.3849.2489.1258.9928.887BER1.218×10-52.083×10-52.535×10-53.409×10-53.788×10-54.380×10-55.523×10-55.924×10-5

表1可以看出，tv越大AMM算法的誤碼性能越好。而tv越小所對應的運算復雜度越低。因此綜合考慮誤碼性能和復雜度，在以下仿真中AMM算法A選定為14，C選定為10。

3.2CERL參數選取

在AMM算法中，隨著迭代次數的增加，譯碼判決后CER越來越小。當CER的值小于臨界值CERL時，自適應減少迭代中校驗節點數量。圖4給出了CER下降到CERL后，AMM算法平均每幀所需要的運算量。

圖4　CERL不同值下的每幀平均運算量

由圖4可知，臨界值CERL在一定程度上影響著迭代譯碼過程中AMM算法的整體運算復雜度，可以看出CERL越大AMM算法的運算量越小。通過實驗仿真，結合誤碼性能選取合適的CERL取值。下面對CERL取不同值時AMM譯碼算法的誤碼性能進行分析，仿真結果如圖5所示。

圖5　不同CERL值下AMM算法誤碼率

圖5可以看出，AMM算法的誤碼性能隨著CERL增大而變差，當CERL≤1,取10-2數量級時誤碼達到10-5數量級。這是因為在譯碼過程中，當大部分碼字都譯碼正確(對應CER較小)時，減少譯碼節點數量才不會影響到算法的整體誤碼性能，因此CERL的取值不宜過大。由圖4中可知，CERL越大AMM算法運算復雜度越低。綜合考慮誤碼率 (10-5數量級)和譯碼復雜度，在AMM算法中，CERL值選取為0.04可以獲得誤碼率和譯碼復雜度的折中。

3.3AMM算法復雜度改進

由于AMM譯碼算法中采用了CER作為調節參數，減少譯碼過程中參與運算的節點數量，平均消息向量的截短長度tv不能精確地反應該算法相對于Min-max算法的改進程度。因此，本文對兩種算法譯碼過程中每幀的平均運算量進行統計。為了對比AMM算法相對于Min-max的復雜度優化情況，對這兩種算法在相同實驗條件下進行仿真，并對二者誤碼率大致相同條件下的算法運算量的進行對比，將AMM算法、Min-max算法每幀的平均運算量分別記為N1、N2，對比結果如表2所示。

表2Min-max算法與AMM算法復雜度對比

條件誤碼率AMMMin-maxN1N2N1/N2條件13.2197×10-53.0384×10-57999711079972.20%條件24.7348×10-54.7602×10-5759569666278.58%條件31.4394×10-41.1932×10-4711598950179.51%條件42.2159×10-42.3485×10-4680438387881.12%

表2中給出了AMM算法和Min-max算法在4種誤碼率大致相同情況下運算量對比，其中前兩種情況下，兩種算法的誤碼率達到10-5數量級；第3、4種情況下，兩種算法的誤碼率達到了10-4數量級。綜合4種誤碼率相同情況下運算量的對比可以看出，與Min-max譯碼算法相比，在相同的誤碼性能條件下，AMM譯碼算法運算量降低了大約20%。

4總結

本文提出了一種低譯碼復雜度的多元LDPC碼AMM譯碼算法。在譯碼迭代過程中，以校驗節點錯誤率為調節參數，自適應地截短參與運算的消息概率向量長度，在確保一定誤碼性能的前提下盡可能降低運算量；同時當校驗節點錯誤率下降到一定程度時，停止對滿足校驗關系的節點更新，通過減少參與消息更新的校驗節點數量進一步降低AMM算法復雜度。仿真結果驗證了本文方法的有效性。

參考文獻：

[1]GALLAGERR.Low-densityparity-checkcodes[J].IREtransactionsoninformationtheory, 1962, 8(1): 21-28.

[2]DAVEYMC,MACKAYD.Low-densityparitycheckcodesoverGF(q)[J].IEEEcommunicationsletters, 1998, 2(6): 165-167.

[3]MACKAYDJ.Gooderror-correctingcodesbasedonverysparsematrices[J].IEEEtransactionsoninformationtheory, 1999, 45(2): 399-431.

[4]WYMEERSCHH,STEENDAMH,MOENECLAEYM.Log-domaindecodingofLDPCcodesoverGF(q)[C]//Proc. 2004IEEEInternationalConferenceonCommunications. [S.l.]：IEEE，2004:772-776.

[5]DECLERCQD,FOSSORIERM.Extendedmin-sumalgorithmfordecodingLDPCcodesoverGF(q)[C]//Proc. 2005InternationalSymposiumontheInformationTheory. [S.l.]：ISIT，2005:1015-1018.

[6]DECLERCQD,FOSSORIERM.DecodingalgorithmsfornonbinaryLDPCcodesoverGF[J].IEEEtransactionsoncommunications, 2007, 55(4): 633-643.

[7]GUANXuan,FEIYunsi.AdaptiveExtendedMin-SumAlgorithmforNonbinaryLDPCDecoding[C]//Proc.GlobalTelecommunicationsConference(GLOBECOM2011).Houston，TX，US：IEEE, 2011：1-6.

[8]SAVINV.Min-maxdecodingfornonbinaryLDPCcodes[C]//Proc. 2008IEEEInternationalSymposiumonInformationTheory.Toronto：IEEE，2008：960-964.

[9]ZHANGX,CAIF,LINS.Low-complexityreliability-basedmessage-passingdecoderarchitecturesfornon-binaryLDPCcodes[J].IEEEtransactionsonverylargescaleintegration(VLSI)systems, 2012, 20(11): 1938-1950.

[10]LINJ,YANZY.Efficientshuffleddecoderarchitecturefornonbinaryquasi-cyclicLDPCcodes[J].IEEEtransactionsonverylargescaleintegration(VLSI)systems, 2013, 21(9): 1756-1761.

[11]LINJ,YANZY.Adecodingalgorithmwithreducedcomplexityfornon-binaryLDPCcodesoverlargefields[C]//Proc. 2013IEEEInternationalSymposiumonCircuitsandSystems(ISCAS). [S.l.]：IEEE，2013：1688-1691.

[12]YANGL,LIUF,LIH.Min-maxdecodingfornon-binaryLDPCcodes[C]//Proc. 2012InternationalConferenceonInformationTechnologyandSoftwareEngineering. [S.l.]：IEEE，2012，108-112.

[13]楊威, 張為. 一種基于分層譯碼和Min-max的多進制LDPC碼譯碼算法[J]. 電子與信息學報, 2013, 35(7): 1677-1681.

[14]GARCIA-HERREROF,ERBAOL,DECLERCQD,etal.Multiple-Votesymbol-flippingdecoderfornonbinaryLDPCcodes[J].IEEEtransactionsonverylargescaleintegration(VLSI)systems, 2014, 22(11): 2256-2267.

[15]LACRUZJO,GARCIA-HERREROF,VALLSJ.ReductionofcomplexityfornonbinaryLDPCdecoderswithcompressedmessages[J].IEEEtransactionsonverylargescaleintegration(VLSI)systems, 2015,23(11): 2676-2679.

[16]LUYC,GUIFENT,GOTOS.Anefficientdecoderarchitectureforcyclicnon-binaryLDPCcodes[C]//Proc. 2014IEEEInternationalSymposiumonCircuitsandSystems(ISCAS).MelbourneVIC：IEEE，2014：397-400.

[17]LACRUZJO,GARCIA-HERREROF,VALLSJ,etal.Oneminimumonlytrellisdecoderfornon-binarylow-densityparity-checkcodes[J].IEEEtransactionsoncircuitsandsystemsI:regularpapers, 2015, 62(1): 177-184.

陳紫強 (1973— )，副教授，碩士生導師，主研信道編碼、協作通信；

杜婉瑩 (1991— )，女，碩士生，主研信道編碼；

謝躍雷 (1975— )，副教授，碩士生導師，主研通信信號處理、陣列信號處理。

責任編輯：薛京

AdaptiveMin-maxalgorithmfornon-binaryLDPCdecoding

CHENZiqiang,DUWanying,XIEYuelei

(Key Laboratory of Wireless Wideband Communication and Signal Processing, Guilin University of Electronic Technology, Guangxi Guilin 541004, China)

Abstract:In this paper, an adaptive Min-max(AMM)algorithm for non-binary LDPC decoding is proposed to reduce the computational complexity of the Min-max decoding algorithm. Using the error rate of check-nodes as an adjusting parameter to truncate the message vector in decoding iteration adaptively, the computation complexity of AMM algorithm is greatly reduced with little performance loss. When the error rate of check-nodes decreases to a certain small value, stop updating the messages of the correct checked nodes. By reducing the number of nodes participated in updating adaptively, the computation complexity of AMM algorithm is further reduced. The simulation results show that the computation complexity of AMM algorithm is reduced by 20% compared with the fixed message truncation Min-max algorithm given the same bit error rate.

Key words:non-binary low density parity check codes; Min-max; adaptive truncation; check-node error rate

中圖分類號：TN911.22

文獻標志碼：A

DOI：10.16280/j.videoe.2016.04.018

基金項目：國家自然科學基金項目(61451015;61371186;61261032;41201479);廣西自然基金項目(2013GXNSFFA019004；2014JJ70068);廣西教育廳重點項目(ZD2014052)

作者簡介：

收稿日期：2015-08-27

文獻引用格式：陳紫強,杜婉瑩,謝躍雷.多元LDPC碼Min-max自適應譯碼算法[J].電視技術，2016，40(4)：85-89.

CHENZQ,DUWY,XIEYL.AdaptiveMin-maxalgorithmfornon-binaryLDPCdecoding[J].Videoengineering，2016，40(4)：85-89.