LDPC碼密度進(jìn)化方法與門限研究

1、    LDPC碼密度進(jìn)化方法與門限研究        徐富兵1,2， 雷 菁1， 李二 時(shí)間:2008年07月21日     字 體: 大 中 小        關(guān)鍵詞:        ? 摘 要：關(guān)鍵詞： LDPC碼? 密度進(jìn)化? 門限值? LDPC碼是Gallager提出的

2、逼近香農(nóng)限的好碼134基于消息傳遞機(jī)制的置信傳播(Belief Propagation)譯碼算法提出了密度進(jìn)化分析(Density Evolution)的思想。通過跟蹤譯碼器中傳遞消息的概率密度函數(shù)在迭代過程中的變化情況，分析譯碼收斂特性，得到特定信道下的門限值。對于研究譯碼過程和碼的設(shè)計(jì)，密度進(jìn)化是一種非常有用的工具。? 在參考文獻(xiàn)4中，Richardson等給出了密度進(jìn)化的直接算法。這種迭代分析方法非常復(fù)雜，計(jì)算量巨大。為此，Sae-Yang Chung57、Hui Jin6等提出了密度進(jìn)化的不同實(shí)現(xiàn)方法，在計(jì)算精度損失可以接受的情況下，極大地提高了分析的效率。本文將基于密度進(jìn)化的基本理論

3、，討論其實(shí)現(xiàn)方法和在門限判決中的應(yīng)用。1 LDPC碼和密度進(jìn)化? LDPC碼是具有稀疏奇偶校驗(yàn)矩陣的線性分組碼。一個(gè)LDPC碼集可以由一個(gè)度分布(,)確定，即由變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的度分布函數(shù)確定：? 其中l(wèi)max和rmax分別表示變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的最大度數(shù)。規(guī)則碼(dv,dc)是一種特殊情形，? LDPC碼最常用的譯碼算法是和積算法(Sum-Product Algorihm)。基于文獻(xiàn)4中的無環(huán)假設(shè)，如果一個(gè)規(guī)則LDPC碼（dv,dc）沒有長度小于或等于2l的環(huán)，則在l次迭代內(nèi)，可以假定所有的消息變量是獨(dú)立的。設(shè)u0表示變量節(jié)點(diǎn)接收信號的對數(shù)似然比(LLR)消息，v和u分別表示變量節(jié)點(diǎn)和校驗(yàn)

4、節(jié)點(diǎn)發(fā)送給各自鄰接節(jié)點(diǎn)的LLR消息2。則變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的消息更新規(guī)則表示為：? ? 在無環(huán)和不同變量節(jié)點(diǎn)初始消息u0i,i=1,2,dv-1和vi,i=1,2,dci和vi的概率密度函數(shù)變得容易。在譯碼第k次迭代時(shí)，vi和ui的概率密度分別表示為Pk和Qk, k=1,2,。P0表示u0的概率密度，? ? ? 在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)進(jìn)行卷積運(yùn)算的域分別為i+(變量節(jié)點(diǎn)域:實(shí)數(shù)域加上+)和GF(2)×0,(校驗(yàn)節(jié)點(diǎn)域:簡稱G域),利用傅立葉變換計(jì)算Qk和Pk時(shí)，在兩個(gè)域之間相互轉(zhuǎn)換，從而使計(jì)算過程相當(dāng)復(fù)雜4。? 密度進(jìn)化的實(shí)現(xiàn)主要包括三部分：變量節(jié)點(diǎn)域卷積、G域卷積和兩個(gè)域之間適合卷積

5、的密度函數(shù)表達(dá)式的相互轉(zhuǎn)換。參考文獻(xiàn)5-7對不同的方法作了闡述，具有各自的特點(diǎn)。2.1 離散密度進(jìn)化(DDE)? 為了計(jì)算機(jī)仿真處理，對第1節(jié)算法中LLR消息、v、u量化處理。設(shè)量化比特為q,量化步進(jìn)為，量化區(qū)間為-N,N, N=2q-1-1。如果消息值在范圍(n-/2,n+/2)，n是一個(gè)整數(shù)，當(dāng)-NnN時(shí)，消息量化為n；當(dāng)n<-N和n>N時(shí)，分別量化為-N和N。? pv和pu分別表示離散消息的概率聚集函數(shù)(pmf)。由于離散消息都是獨(dú)立和均勻分布的隨機(jī)變量，由(1)式易得變量節(jié)點(diǎn)的密度進(jìn)化規(guī)則為：借助于快速傅立葉變換(FFT)能夠有效實(shí)現(xiàn)。? 對校驗(yàn)節(jié)點(diǎn)定義如下的二元運(yùn)算符：?

6、 ? 其中a、b都是離散消息，Q表示量化運(yùn)算。易知是遞歸運(yùn)算，可以推導(dǎo)出校驗(yàn)節(jié)點(diǎn)密度進(jìn)化規(guī)則：(pv)。采用查表法計(jì)算，加速算法實(shí)現(xiàn)。? 對于非規(guī)則LDPC碼，DDE算法是：? ? 該算法適合各種對稱信道，如BSC、BEC、高斯信道等。考慮AWGN信道，LDPC(3,6)規(guī)則碼，信道噪聲方差exact=0.880 913，在不同量化比特情形下求得門限值DDE如表1所示，可見，量化14比特時(shí)，結(jié)果已相當(dāng)精確。?2.2 利用對稱傅立葉變換(SFT)計(jì)算? DDE算法在變量節(jié)點(diǎn)域未能充分利用LLR消息概率密度函數(shù)f的對稱性。在對稱信道上傳輸全1碼字時(shí)，f對稱，從而g(x):=e-1/2x f(x)是

7、偶函數(shù)。定義傅立葉變換假設(shè)f取值于k，k=-K,0,1,K，對e-1/2 x f(x)填充0，進(jìn)行22m點(diǎn)離散傅立葉變換(2m+1>K)。實(shí)際中，F(xiàn)g(jw)比Ff(jw)更有優(yōu)勢。首先，前者是實(shí)數(shù)和關(guān)于w的偶函數(shù)，便于乘積計(jì)算；其次，函數(shù)g的尾值呈指數(shù)級減少，極大地降低了FFT計(jì)算時(shí)的混疊現(xiàn)象。這樣，不必在每對卷積之后返回實(shí)數(shù)域，只要在變量節(jié)點(diǎn)域卷積結(jié)束時(shí)返回即可，節(jié)省了大量計(jì)算。? 在校驗(yàn)節(jié)點(diǎn)域，即G域，傅立葉變換定義為：Ff(v):=取值于實(shí)數(shù)0,KU+。那么傅立葉變換：? ? 現(xiàn)在的難題是如何量化v。根據(jù)文獻(xiàn)6，實(shí)際采用v=e(1+jw)。依照對量化，取w=0 將降低復(fù)雜度。?

8、這種算法比DDE更為接近原始的密度進(jìn)化原理，但達(dá)到同樣精度需要少得多的計(jì)算量。對于規(guī)則LDPC(3,6)碼，不同量化間隔時(shí)的噪聲門限SFT如表2所示。?2.3 高斯近似8通過仿真首先發(fā)現(xiàn)這個(gè)事實(shí)。由于LLR消息的分布是相近的，利用對數(shù)正態(tài)的性質(zhì)，可以證明在密度進(jìn)化過程中消息是近似高斯分布的。利用對稱條件f(x)=exf(-x)，高斯分布的LLR消息服從N(0,20)。假設(shè)AWGN信道噪聲均值為0，方差為2，傳輸全0碼字，易知0=2/2。只要確定?滋0就能完整描述概率密度函數(shù)。? mv和mu分別表示v和u的均值，則(1)、(2)式兩邊取均值，化簡變換可得：? ? 其近似計(jì)算方法是：? ? 用高斯

9、近似算法求得規(guī)則LDPC(4,6)碼的噪聲門限為GA=1.003 6，相應(yīng)的信噪比Eb/N0=1.729 9。對于不同信噪比的消息概率密度的均值變化如圖1所示。當(dāng)Eb/N0大于門限，k時(shí)，均值趨于無窮大，意味著誤碼率趨于0；當(dāng)Eb/N0小于門限，k時(shí)，均值趨于一個(gè)有限固定值，意味著誤碼率不可能趨于0。Eb/N0值越大，正確譯碼需要的迭代次數(shù)越少。當(dāng)Eb/N0=1.76時(shí)，概率密度分布如圖2所示。隨著迭代次數(shù)的增長，概率分布向正向移動(dòng)，譯碼器幾乎能夠正確譯碼。?3 仿真和結(jié)論? 前面討論的三種密度進(jìn)化算法各有特點(diǎn)。根據(jù)實(shí)際需要，選擇合適的算法對LDPC碼進(jìn)行研究。表3給出了不同碼率的規(guī)則LDPC

10、碼采用不同密度進(jìn)化算法求出的門限值、GA與DDE的距離GA、SFT與DDE的距離SFT以及DDE與香農(nóng)限C的距離。DDE和SFT兩種方法的精度差別不多；高斯近似的精度稍微差些，但其計(jì)算量少很多。? 表3中表明，規(guī)則碼的門限值距離香農(nóng)限還較遠(yuǎn)。LDPC碼研究重點(diǎn)之一就是利用密度進(jìn)化算法優(yōu)化度分布(,)設(shè)計(jì)好的非規(guī)則碼，獲得距離香農(nóng)限更近的門限。參考文獻(xiàn)5中設(shè)計(jì)出了=0.004 5dB的非規(guī)則碼，與香農(nóng)限的距離已經(jīng)很小了。? 密度進(jìn)化方法是現(xiàn)代高級編碼研究的重要工具,不僅適用于LDPC碼，也可用于Turbo碼、MN碼等的分析和設(shè)計(jì)。這種方法的提出，促進(jìn)了現(xiàn)代高效糾錯(cuò)編碼的發(fā)展。參考文獻(xiàn)1 GALL

11、AGER R G. Low-Density Parity-Check codes.Cambridge, MA:MIT Press, 1963.2?MACKAY D J C. Good? error-correcting codes based on very sparse matrices. IEEE Trans, Inf. Theory, 1999,45(3):399-431.3?RICHARDSON T J, URBANKE R L. The capacity of? low-density? parity-check? codes? under message-passing decod

12、ing. IEEE? Trans. Information Theory, 2001,47(2):599-618.4? RICHARDSON T, SHOKROLLAHI A,URABANKE R. Design of capacity- approaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory, 2001,47(2):619-637.5?CHUNG S Y, FORNEY G D, RICHARDSON J,et al. On the design of low-density parit

13、y -check codes within 0.0045 db of the Shannon limit. IEEE Communications Letters, 2001,5(2):58-60.6?JIN H, RICHARDSON T. A new fast density evolution.IEEE Information Theory Workshop, Punta del Este, Uruguay, 2006:13-17.7?CHUNG S Y, RICHARDSON T J, URBANKE R L. Analysis of sum-product decoding of low-density paritycheck codes using a Gaussian approximation.