尹曉琦

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

?

基于密度進化算法的正則LDPC碼噪聲門限

尹曉琦

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

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

LDPC碼；譯碼；密度進化；噪聲門限

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

1　LDPC碼的Tanner圖

LDPC碼作為一種線性分組碼，可以用監(jiān)督矩陣的形式來表示，也可以用Tanner圖來描述.Tanner圖包括變量節(jié)點和校驗節(jié)點2個集合[7]，檢驗節(jié)點對應監(jiān)督矩陣的行，變量節(jié)點對應監(jiān)督矩陣的列，集合內(nèi)部的各節(jié)點之間沒有連線，而不同集合的各節(jié)點之間可能有連線，ci與vj相連表示矩陣中第i行、第j列的元素為1.例如一個(6,2,3)正則LDPC碼的Tanner圖(如圖1所示)，圖中4個變量節(jié)點構成集合{v1,v2,v3,v4}，6個校驗節(jié)點構成集合{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　基于置信傳播算法的密度進化算法

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

定義

(1)

定義

(2)

置信傳播算法步驟如下：

(3)

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

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

(4)

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

(5)

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

(6)

2.2密度進化算法

在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，此時由均值μ就可以確定消息的概率密度.

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

(9)

(10)

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

(11)

(12)

(13)

對于式(11)可推導如下

(14)

定義

(15)

(16)

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

(17)

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

(18)

3　密度進化算法的門限與仿真結果的比較

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

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

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

由表1可以看出，采用了密度進化算法簡化運算后的噪聲方差門限要略小于簡化前的門限值，次數(shù)分布為(3,6)的LDPC碼的噪聲方差門限值大于次數(shù)分布為(4,8)、(5,10)的門限值，而信噪比門限中(3,6)碼的值最小，但與香農(nóng)限都還有一定距離.當最大迭代次數(shù)設為50時，3種次數(shù)分布的LDPC碼在BP算法下的誤碼率性能仿真結果見圖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)的性能最差，與密度進化算法迭代計算的結果一致，說明隨著列重的增加，LDPC碼的誤碼性能會變差.在誤碼率為10-4時，(3,6)、(4,8)和(5,10)的正則碼對應的信噪比分別約為2.95、3.40和3.83dB，信噪比差值為0.45、0.43dB；而由表1的結果得到的信噪比差值為0.44、0.42dB，與仿真結果中的信噪比差值近似相等.

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

4　結論

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

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

[2]王蘭勛,王貴貴,尹超,等.基于HMM信源估計和LDPC的聯(lián)合信源信道譯碼[J].河北大學學報(自然科學版),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碼設計[J].通信學報,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.

(責任編輯：王蘭英)

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-)，女，江蘇淮安人，淮陰工學院副教授，主要從事無線通信與信號處理研究.

E-mail:kittyyin@hyit.edu.cn

TN

A