基于密度進(jìn)化算法的正則LDPC碼噪聲門限

尹曉琦

(淮陰工學(xué)院電子信息工程學(xué)院，江蘇淮安　223003)

?

基于密度進(jìn)化算法的正則LDPC碼噪聲門限

尹曉琦

(淮陰工學(xué)院電子信息工程學(xué)院，江蘇淮安223003)

針對LDPC碼(低密度奇偶校驗碼)的噪聲門限問題，基于置信傳播算法討論密度進(jìn)化算法的實現(xiàn)方法，通過對校驗節(jié)點均值迭代公式的簡化來確定門限值，簡化算法降低了迭代運算的復(fù)雜度，減小了運算量.構(gòu)造了3種不同次數(shù)分布的LDPC碼，對其在高斯白噪聲信道下噪聲方差門限和信噪比門限進(jìn)行了理論計算和仿真，并對結(jié)果進(jìn)行了比較分析.研究結(jié)果表明，隨著列重的增加，LDPC碼的誤碼性能將變差，選擇好的次數(shù)分布能獲得優(yōu)秀的誤碼性能，這對LDPC碼進(jìn)一步的應(yīng)用研究具有指導(dǎo)意義.

LDPC碼；譯碼；密度進(jìn)化；噪聲門限

低密度奇偶校驗碼(low-density-parity-checkcodes，LDPC)是一種逼近香農(nóng)限的線性分組碼，碼率為1/2的LDPC碼在BPSK調(diào)制方式下的誤碼性能距香農(nóng)限僅有0.045dB，是目前距離香農(nóng)限最近的信道編碼[1-2]，它利用監(jiān)督矩陣的低密度特性，降低了譯碼的復(fù)雜度，提高了解碼速度，由于其具有類似隨機(jī)編碼的特征，所以擁有優(yōu)秀的編碼性能.Gallager對LDPC碼在二進(jìn)制對稱信道中的譯碼特性進(jìn)行了研究，發(fā)現(xiàn)LDPC碼在譯碼的過程中存在門限問題[3].當(dāng)LDPC碼的碼長增加時，只要信道的噪聲功率比噪聲門限值低，通過置信傳播算法對LDPC碼進(jìn)行譯碼，仍然能獲得較好的誤碼性能；而當(dāng)噪聲功率比門限值高時，LDPC碼的誤碼率則無法達(dá)到理想狀態(tài)，而是大于某個正的常數(shù).Richardson和Urbanke定義了這個譯碼門限[4]，并且提出了密度進(jìn)化的直接算法，但是這種方法的計算量太大.Elsa等在設(shè)計非二進(jìn)制LDPC碼時，對非二進(jìn)制對稱信道的密度進(jìn)化算法進(jìn)行了優(yōu)化，通過對有限長度編碼的漸進(jìn)性能仿真獲得了編碼的優(yōu)化度分布[5].陳紫強等[6]研究了高斯白噪聲信道下聯(lián)合LDPC碼的密度進(jìn)化算法，結(jié)合譯碼收斂條件和度分布約束關(guān)系，提出聯(lián)合LDPC碼的度分布優(yōu)化問題.由于在AWGN信道中迭代運算的信息分布是相近的，因此在密度進(jìn)化過程中消息的概率密度為近似高斯分布.本文基于高斯近似方法討論LDPC碼密度進(jìn)化算法的實現(xiàn)方法，通過對節(jié)點之間消息密度迭代運算的簡化來確定噪聲門限值.

1　LDPC碼的Tanner圖

LDPC碼作為一種線性分組碼，可以用監(jiān)督矩陣的形式來表示，也可以用Tanner圖來描述.Tanner圖包括變量節(jié)點和校驗節(jié)點2個集合[7]，檢驗節(jié)點對應(yīng)監(jiān)督矩陣的行，變量節(jié)點對應(yīng)監(jiān)督矩陣的列，集合內(nèi)部的各節(jié)點之間沒有連線，而不同集合的各節(jié)點之間可能有連線，ci與vj相連表示矩陣中第i行、第j列的元素為1.例如一個(6,2,3)正則LDPC碼的Tanner圖(如圖1所示)，圖中4個變量節(jié)點構(gòu)成集合{v1,v2,v3,v4}，6個校驗節(jié)點構(gòu)成集合{c1,c2,…，c6}，2個集合內(nèi)部沒有連線，但集合之間根據(jù)校驗矩陣中“1”的分布來連線，其中，H1,1=1表示c1與v1相連.另外，圖論中定義與某個節(jié)點x相連的邊數(shù)為節(jié)點次數(shù)deg(x).在圖1的Tanner圖中，變量節(jié)點vi的節(jié)點次數(shù)deg(vi)為3，校驗節(jié)點cj的節(jié)點次數(shù)deg(cj)為2.

圖1　(6,2,3) LDPC碼Tanner圖Fig.1　Tanner figure of (6,2,3) LDPC codes

2　基于置信傳播算法的密度進(jìn)化算法

2.1置信傳播算法(BP算法)

定義

(1)

定義

(2)

置信傳播算法步驟如下：

(3)

2)判斷迭代次數(shù)k是否大于設(shè)定值，如果成立，則結(jié)束譯碼，否則繼續(xù)；

3)更新校驗節(jié)點cm傳遞給vi的對數(shù)似然比

(4)

4)計算變量節(jié)點vn的對數(shù)似然比

(5)

5)更新變量節(jié)點vn傳遞給cj的對數(shù)似然比

(6)

2.2密度進(jìn)化算法

在BP算法中，如果是高斯白噪聲信道，則信息迭代的對數(shù)似然比L(q)、L(r)服從近似高斯分布，所以迭代時可通過均值μ、方差σ2得到節(jié)點信息的概率密度f(x)，節(jié)點之間信息迭代可簡化為

(7)

(8)

其中，dv和dc分別為變量節(jié)點和校驗節(jié)點的最大度數(shù).

利用節(jié)點概率密度的對稱條件f(x)=f(-x)ex，對數(shù)似然比信息服從N(μ,2μ)的高斯分布，則方差μ=2/σ2，此時由均值μ就可以確定消息的概率密度.

假設(shè)LDPC碼的Tanner圖中沒有閉合環(huán)路，信息未被重復(fù)更新，則可認(rèn)為不同節(jié)點之間的對數(shù)似然比是獨立同分布的.定義

(9)

(10)

根據(jù)式(7)和(8)，推導(dǎo)節(jié)點之間對數(shù)似然比的數(shù)學(xué)期望的迭代式為

(11)

(12)

(13)

對于式(11)可推導(dǎo)如下

(14)

定義

(15)

(16)

Sae[9]給出了φ(x)的上界和下界的近似表達(dá)式

(17)

φ(x)在x不是很大的情況下，可以進(jìn)一步簡化計算為

(18)

3　密度進(jìn)化算法的門限與仿真結(jié)果的比較

為了進(jìn)行計算機(jī)仿真運算，對算法中的變量節(jié)點和校驗節(jié)點的對數(shù)似然比信息進(jìn)行量化處理.設(shè)量化間隔為δ，量化比特為m，量化范圍為[-N,N]，N=2m-1-1.如果對數(shù)似然比信息是在以nδ為中點的量化區(qū)間里，則量化值為n；當(dāng)n<-N時，量化值為-N；當(dāng)n>N時，量化值為N.

對于碼長為504、碼率為1/2的LDPC碼，分別構(gòu)造次數(shù)分布為(3,6)、(4,8)和(5,10)的正則碼，量化比特為12，利用密度進(jìn)化算法分別計算噪聲方差門限σ2和信噪比門限SNR，結(jié)果見表1.

表1　不同次數(shù)分布正則碼的門限值Tab.1　Thresholds of different drgree distribution regular codes

由表1可以看出，采用了密度進(jìn)化算法簡化運算后的噪聲方差門限要略小于簡化前的門限值，次數(shù)分布為(3,6)的LDPC碼的噪聲方差門限值大于次數(shù)分布為(4,8)、(5,10)的門限值，而信噪比門限中(3,6)碼的值最小，但與香農(nóng)限都還有一定距離.當(dāng)最大迭代次數(shù)設(shè)為50時，3種次數(shù)分布的LDPC碼在BP算法下的誤碼率性能仿真結(jié)果見圖2，算法簡化前后平均迭代次數(shù)的統(tǒng)計見圖3.

圖2　不同次數(shù)分布正則碼誤碼率性能Fig.2　Error performance of different degree distribution regular codes

圖3　平均迭代次數(shù)的統(tǒng)計Fig.3　Statistics of mean iteration times

由圖2可知，次數(shù)分布為(3,6)的正則LDPC碼的誤碼性能最好，而次數(shù)分布為(5,10)的性能最差，與密度進(jìn)化算法迭代計算的結(jié)果一致，說明隨著列重的增加，LDPC碼的誤碼性能會變差.在誤碼率為10-4時，(3,6)、(4,8)和(5,10)的正則碼對應(yīng)的信噪比分別約為2.95、3.40和3.83dB，信噪比差值為0.45、0.43dB；而由表1的結(jié)果得到的信噪比差值為0.44、0.42dB，與仿真結(jié)果中的信噪比差值近似相等.

由圖3可以看出，算法簡化后的平均迭代次數(shù)逼近簡化前，而從迭代運算復(fù)雜度來看，當(dāng)對變量節(jié)點和校驗節(jié)點的對數(shù)似然比信息進(jìn)行迭代更新時,簡化算法將雙曲正切函數(shù)與指數(shù)函數(shù)乘積的積分運算簡化為指數(shù)運算，大大減少了譯碼的運算量，降低了譯碼的復(fù)雜度.另外，誤碼率性能仿真結(jié)果與用密度進(jìn)化算法迭代計算的結(jié)果都不是離香農(nóng)限很近，這是因為所用的LDPC碼的長度不是足夠大，相應(yīng)的監(jiān)督矩陣中“1”不是足夠稀疏的，且列重增加也會進(jìn)一步降低校驗矩陣的稀疏性，導(dǎo)致編碼的Tanner圖中出現(xiàn)大量的短環(huán)，使得置信傳播算法的誤碼性能下降.

4　結(jié)論

LDPC碼是一種逼近香農(nóng)限的高效糾錯編碼，但是在譯碼過程中存在門限問題.本文主要討論了一種基于置信傳播算法的密度進(jìn)化算法,能夠通過對消息密度的迭代運算來確定噪聲門限和信噪比門限的值，為LDPC碼尋找最優(yōu)的次數(shù)分布對提供了方法，這對LDPC碼進(jìn)一步的應(yīng)用研究具有指導(dǎo)意義.

[1]MCKAYDJC.Gooderror-correctingcodesbasedonverysparsematrices[J].IEEETransInformTheory,1999,45(3):399-431.DOI:10.1109/18.748992.

[2]王蘭勛,王貴貴,尹超,等.基于HMM信源估計和LDPC的聯(lián)合信源信道譯碼[J].河北大學(xué)學(xué)報(自然科學(xué)版),2008,28(2)：209-213.

WANGLanxun，WANGGuigui，YINChao，etal.Jointsource-channeldecodingbasedonHMMandLDPC[J].JournalofHebeiUniversity(NaturalScienceEdition),2008,28(2)：209-213.

[3]GALLAGERRG.Low-densityparity-checkcodes[D].Cambridge,MA:MITPress,1963.DOI:10.1109/TIT.1962.1057683.

[4]RICHARDSONTJ,URBANKER.Thecapacityoflow-densityparitycheckcodesundermessagepassingdecoding[J].IEEETransInformTheory,2001,47(2):599-618.DOI:10.1109/18.910577.

[5]DUPRAZELSA,SAVINV,KIEFFERM,etal.Densityevolutionforthedesignofnon-binarylowdensityparitycheckcodesforSlepian-Wolfcoding[J].IEEETransactionsonCommunications,2015,63(1):25-36.DOI:10.1109/TCOMM.2014.2382126.

[6]陳紫強,歐陽繕,肖海林,等.半雙工中繼信道下聯(lián)合LDPC碼設(shè)計[J].通信學(xué)報,2013,34(3):134-140.DOI:10.3969/j.issn.1000-436x.2013.03.017.

CHENZiqiang,OUYANGShan,XIAOHailin,etal.JointedLDPCcodesdesignforhalf-duplexrelaychannels[J].JournalonCommunications,2013,34(3):134-140.DOI:10.3969/j.issn.1000-436x.2013.03.017.

[7]TANNERRM,SRIDHARAD,SRIDHARANA,etal.LDPCblockandconvolutionalcodesbasedoncirculantmatrices[J].IEEETransactionsonInformationTheory,2004,50(12):2966-2984.DOI:10.1109/TIT.2004.838370.

[8]PEARLJ.Probabilisticreasoninginintelligentsystems:networksofplausibleinference[M].SanFrancisco,CA,USA:MorganKaufmannPublishersInc,1988:552.

[9]CHUNGSY,RICHARDSONTJ,URBANKER.Analysisofsum-productdecodingoflow-densityparity-checkcodesusingagaussianapproximation[J].IEEETransactionsonInformationTheory,2001,47(2):657-670.DOI:10.1109/18.910580.

(責(zé)任編輯：王蘭英)

ThresholdsofregularLDPCcodesbasedondensityevolutionalgorithm

YINXiaoqi

(FacultyofElectronicInformationEngineering，HuaiyinInstituteofTechnology，Huai’an223003,China)

TodealwiththenoisethresholdsofLDPCcodes,thedensityevolutionaryalgorithmbasedonbeliefpropagationalgorithmisdiscussedtodeterminethethresholdsthroughsimplifyingthemessageiterativearithmeticonthemeansofthechecknodeswhichcanreducethecomputingcomplexityandtheamountofcomputation.ThreedifferentdegreedistributionLDPCcodeshavebeenconstructed,andthetheoreticalcalculationandsimulationhavebeencarriedontodeterminethenoisevariancethresholdsandtheSNRthresholdsunderAWGNchannel,theresultshavebeencompared.Itshowsthatwiththeincreaseofthecolumnweight,theperformanceofLDPCcodesbecomesworse.Excellentperformancecanbeobtainedifwechoosegoodnumbersofdegreedistribution,thathasguidingsignificanceforfurtherapplicationresearchofLDPCcodes.

LDPCcodes；decoding；densityevolution；noisethresholds

10.3969/j.issn.1000-1565.2016.03.018

2015-06-12

國家星火科技計劃項目(2012GA690304)；淮安市科技支撐計劃項目(HAS2012046)

尹曉琦(1975-)，女，江蘇淮安人，淮陰工學(xué)院副教授，主要從事無線通信與信號處理研究.

E-mail:kittyyin@hyit.edu.cn

TN

A