多元LDPC碼Min-max自適應(yīng)譯碼算法

陳紫強(qiáng),杜婉瑩,謝躍雷

(桂林電子科技大學(xué) 無(wú)線寬帶通信與信號(hào)處理省部重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

多元LDPC碼Min-max自適應(yīng)譯碼算法

陳紫強(qiáng),杜婉瑩,謝躍雷

(桂林電子科技大學(xué) 無(wú)線寬帶通信與信號(hào)處理省部重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

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

關(guān)鍵詞:多元LDPC；Min-max；自適應(yīng)截短；校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率

為了進(jìn)一步降低Min-max算法復(fù)雜度，本文提出一種多元LDPC碼Min-max(AdaptiveMin-max，AMM)自適應(yīng)譯碼算法。在每次迭代過(guò)程中，以校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率(Check-nodeErrorRate，CER)為調(diào)節(jié)參數(shù)，對(duì)每個(gè)節(jié)點(diǎn)的LLR向量長(zhǎng)度進(jìn)行自適應(yīng)截短。當(dāng)校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率降低到一定程度時(shí)，停止更新已經(jīng)滿足校驗(yàn)關(guān)系的節(jié)點(diǎn)消息，僅對(duì)錯(cuò)誤的節(jié)點(diǎn)進(jìn)行后續(xù)迭代更新，進(jìn)一步降低AMM算法的整體復(fù)雜度。

1Min-max譯碼算法

Min-max算法將EMS譯碼算法[6]中加法運(yùn)算替換為求最大值運(yùn)算，降低了硬件實(shí)現(xiàn)的復(fù)雜度，便于工程應(yīng)用。AMM算法以Min-max算法為基礎(chǔ)，通過(guò)自適應(yīng)截短消息概率向量長(zhǎng)度、自適應(yīng)截短校驗(yàn)節(jié)點(diǎn)更新數(shù)量?jī)煞N處理方法，降低Min-max譯碼算法的譯碼復(fù)雜度。因此，本文首先簡(jiǎn)要介紹Min-max算法實(shí)現(xiàn)流程。

1)初始化

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

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

(1)

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

2)置換步驟

將變量節(jié)點(diǎn)索引值vq與校驗(yàn)矩陣H相應(yīng)位置的取值相乘，得到置換之后的索引值矩陣v′q，即

(2)

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

3)校驗(yàn)節(jié)點(diǎn)更新

(3)

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

4)逆置換步驟

(4)

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

5)變量節(jié)點(diǎn)更新

(5)

(6)

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

(7)

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

6)后驗(yàn)信息計(jì)算

(8)

2AMM譯碼算法

當(dāng)Min-max算法能夠正確譯碼時(shí)，隨著迭代次數(shù)的增加，消息概率向量的數(shù)值會(huì)越來(lái)越集中到可能性較大的前l(fā)項(xiàng)(l

圖1　譯碼中CER與BER關(guān)系

鑒于此，提出了多元LDPC碼AMM算法，在譯碼過(guò)程中引入CER作為調(diào)節(jié)因子，第一步自適應(yīng)地選取下一次迭代過(guò)程中譯碼的消息概率向量的截短長(zhǎng)度，僅更新節(jié)點(diǎn)向量中置信度較高的分量；第二步自適應(yīng)截短校驗(yàn)節(jié)點(diǎn)更新數(shù)量，當(dāng)校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率降低到一定程度時(shí)，提前結(jié)束已經(jīng)正確的校驗(yàn)節(jié)點(diǎn)的更新，僅對(duì)不滿足校驗(yàn)條件的節(jié)點(diǎn)進(jìn)行后續(xù)消息迭代更新。圖2給出了AMM算法的算法流程圖。

圖2　AMM算法流程圖

2.1自適應(yīng)截短節(jié)點(diǎn)向量長(zhǎng)度

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

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

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

(9)

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

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

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

2.2自適應(yīng)截短節(jié)點(diǎn)更新數(shù)量

在AMM算法中，隨著迭代次數(shù)增加，誤碼率逐次下降，不滿足校驗(yàn)關(guān)系的節(jié)點(diǎn)數(shù)越來(lái)越少。此時(shí)提前結(jié)束已正確的校驗(yàn)節(jié)點(diǎn)消息更新，則在后續(xù)譯碼過(guò)程中僅需要對(duì)錯(cuò)誤的節(jié)點(diǎn)信息進(jìn)行更新。可通過(guò)減少參與譯碼的校驗(yàn)節(jié)點(diǎn)數(shù)量來(lái)降低譯碼復(fù)雜度。當(dāng)譯碼迭代次數(shù)較大時(shí)，大部分校驗(yàn)節(jié)點(diǎn)已經(jīng)獲得正確譯碼消息，減少這些節(jié)點(diǎn)消息更新對(duì)誤碼性能影響不大。將上述處理過(guò)程記為步驟8)。設(shè)CERL為校驗(yàn)節(jié)點(diǎn)數(shù)量截短操作的臨界值，AMM譯碼算法步驟8)可分解為：

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

2)找出伴隨式s中非零值所在位置，記為M；跳至步驟2)對(duì)校驗(yàn)矩陣H中M所對(duì)應(yīng)校驗(yàn)節(jié)點(diǎn)和與其相鄰的變量節(jié)點(diǎn)進(jìn)行迭代更新。

3)跳至步驟2)對(duì)校驗(yàn)矩陣H中的所有節(jié)點(diǎn)進(jìn)行譯碼。

3仿真結(jié)果分析

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

3.1A、C參數(shù)選取

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

圖3　AMM算法誤碼率

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

表1誤碼率為10-5時(shí)A，C，tv以及BER對(duì)比情況

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越小所對(duì)應(yīng)的運(yùn)算復(fù)雜度越低。因此綜合考慮誤碼性能和復(fù)雜度，在以下仿真中AMM算法A選定為14，C選定為10。

3.2CERL參數(shù)選取

在AMM算法中，隨著迭代次數(shù)的增加，譯碼判決后CER越來(lái)越小。當(dāng)CER的值小于臨界值CERL時(shí)，自適應(yīng)減少迭代中校驗(yàn)節(jié)點(diǎn)數(shù)量。圖4給出了CER下降到CERL后，AMM算法平均每幀所需要的運(yùn)算量。

圖4　CERL不同值下的每幀平均運(yùn)算量

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

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

圖5可以看出，AMM算法的誤碼性能隨著CERL增大而變差，當(dāng)CERL≤1,取10-2數(shù)量級(jí)時(shí)誤碼達(dá)到10-5數(shù)量級(jí)。這是因?yàn)樵谧g碼過(guò)程中，當(dāng)大部分碼字都譯碼正確(對(duì)應(yīng)CER較小)時(shí)，減少譯碼節(jié)點(diǎn)數(shù)量才不會(huì)影響到算法的整體誤碼性能，因此CERL的取值不宜過(guò)大。由圖4中可知，CERL越大AMM算法運(yùn)算復(fù)雜度越低。綜合考慮誤碼率 (10-5數(shù)量級(jí))和譯碼復(fù)雜度，在AMM算法中，CERL值選取為0.04可以獲得誤碼率和譯碼復(fù)雜度的折中。

3.3AMM算法復(fù)雜度改進(jìn)

由于AMM譯碼算法中采用了CER作為調(diào)節(jié)參數(shù)，減少譯碼過(guò)程中參與運(yùn)算的節(jié)點(diǎn)數(shù)量，平均消息向量的截短長(zhǎng)度tv不能精確地反應(yīng)該算法相對(duì)于Min-max算法的改進(jìn)程度。因此，本文對(duì)兩種算法譯碼過(guò)程中每幀的平均運(yùn)算量進(jìn)行統(tǒng)計(jì)。為了對(duì)比AMM算法相對(duì)于Min-max的復(fù)雜度優(yōu)化情況，對(duì)這兩種算法在相同實(shí)驗(yàn)條件下進(jìn)行仿真，并對(duì)二者誤碼率大致相同條件下的算法運(yùn)算量的進(jìn)行對(duì)比，將AMM算法、Min-max算法每幀的平均運(yùn)算量分別記為N1、N2，對(duì)比結(jié)果如表2所示。

表2Min-max算法與AMM算法復(fù)雜度對(duì)比

條件誤碼率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種誤碼率大致相同情況下運(yùn)算量對(duì)比，其中前兩種情況下，兩種算法的誤碼率達(dá)到10-5數(shù)量級(jí)；第3、4種情況下，兩種算法的誤碼率達(dá)到了10-4數(shù)量級(jí)。綜合4種誤碼率相同情況下運(yùn)算量的對(duì)比可以看出，與Min-max譯碼算法相比，在相同的誤碼性能條件下，AMM譯碼算法運(yùn)算量降低了大約20%。

4總結(jié)

本文提出了一種低譯碼復(fù)雜度的多元LDPC碼AMM譯碼算法。在譯碼迭代過(guò)程中，以校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率為調(diào)節(jié)參數(shù)，自適應(yīng)地截短參與運(yùn)算的消息概率向量長(zhǎng)度，在確保一定誤碼性能的前提下盡可能降低運(yùn)算量；同時(shí)當(dāng)校驗(yàn)節(jié)點(diǎn)錯(cuò)誤率下降到一定程度時(shí)，停止對(duì)滿足校驗(yàn)關(guān)系的節(jié)點(diǎn)更新，通過(guò)減少參與消息更新的校驗(yàn)節(jié)點(diǎn)數(shù)量進(jìn)一步降低AMM算法復(fù)雜度。仿真結(jié)果驗(yàn)證了本文方法的有效性。

參考文獻(xiàn)：

[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的多進(jìn)制LDPC碼譯碼算法[J]. 電子與信息學(xué)報(bào), 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.

陳紫強(qiáng) (1973— )，副教授，碩士生導(dǎo)師，主研信道編碼、協(xié)作通信；

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

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

責(zé)任編輯：薛京

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

中圖分類(lèi)號(hào)：TN911.22

文獻(xiàn)標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.04.018

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61451015;61371186;61261032;41201479);廣西自然基金項(xiàng)目(2013GXNSFFA019004；2014JJ70068);廣西教育廳重點(diǎn)項(xiàng)目(ZD2014052)

作者簡(jiǎn)介：

收稿日期：2015-08-27

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

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