??? 摘 要： 詳細(xì)描述了密度進(jìn)化（DE）方法的基本原理，比較和分析了離散密度進(jìn)化(DDE)、對稱傅立葉變換" title="傅立葉變換">傅立葉變換(SFT)和高斯" title="高斯">高斯近似(GA)等三種具體算法的特點，并求出AWGN信道下一些度分布的門限值。這對LDPC碼理論分析和應(yīng)用研究具有重要指導(dǎo)作用。
??? 關(guān)鍵詞： LDPC碼? 密度進(jìn)化? 門限值
?
??? LDPC碼是Gallager提出的逼近香農(nóng)限的好碼[1]。當(dāng)碼長較長、碼型設(shè)計適當(dāng)時，其性能甚至優(yōu)于Turbo碼。Gallager發(fā)現(xiàn)了LDPC碼的門限現(xiàn)象：若信道噪聲" title="信道噪聲">信道噪聲小于某個固定的門限值，只要碼長趨于無窮，則可以達(dá)到任意小的誤碼概率。Richardson等[3][4]基于消息傳遞機(jī)制的置信傳播(Belief Propagation)譯碼算法提出了密度進(jìn)化分析(Density Evolution)的思想。通過跟蹤譯碼器中傳遞消息的概率密度函數(shù)在迭代過程中的變化情況，分析譯碼收斂特性，得到特定信道下的門限值。對于研究譯碼過程和碼的設(shè)計，密度進(jìn)化是一種非常有用的工具。
??? 在參考文獻(xiàn)[4]中，Richardson等給出了密度進(jìn)化的直接算法。這種迭代分析方法非常復(fù)雜，計算量巨大。為此，Sae-Yang Chung[5][7]、Hui Jin[6]等提出了密度進(jìn)化的不同實現(xiàn)方法，在計算精度損失可以接受的情況下，極大地提高了分析的效率。本文將基于密度進(jìn)化的基本理論，討論其實現(xiàn)方法和在門限判決中的應(yīng)用。
1 LDPC碼和密度進(jìn)化
??? LDPC碼是具有稀疏奇偶校驗矩陣的線性分組碼。一個LDPC碼集可以由一個度分布(λ,ρ)確定，即由變量節(jié)點和校驗節(jié)點的度分布函數(shù)確定：
??? 
其中l(wèi)max和rmax分別表示變量節(jié)點和校驗節(jié)點的最大度數(shù)。規(guī)則碼(dv,dc)是一種特殊情形，
??? LDPC碼最常用的譯碼算法是和積算法(Sum-Product Algorihm)?；谖墨I(xiàn)[4]中的無環(huán)假設(shè)，如果一個規(guī)則LDPC碼（dv,dc）沒有長度小于或等于2l的環(huán)，則在l次迭代內(nèi)，可以假定所有的消息變量是獨立的。設(shè)u0表示變量節(jié)點接收信號的對數(shù)似然比(LLR)消息，v和u分別表示變量節(jié)點和校驗節(jié)點發(fā)送給各自鄰接節(jié)點的LLR消息[2]。則變量節(jié)點和校驗節(jié)點的消息更新規(guī)則表示為：
??? 
??? 在無環(huán)和不同變量節(jié)點初始消息u0服從獨立均勻分布(i.i.d.)的假設(shè)條件下，易知，ui,i=1,2,…,dv-1和vi,i=1,2,…,dc也是i.i.d.分布的。這樣計算ui和vi的概率密度函數(shù)變得容易。在譯碼第k次迭代時，vi和ui的概率密度分別表示為Pk和Qk, k=1,2,…。P0表示u0的概率密度，
??? 基于上述的i.i.d.特性，對于k≥1，從(1)式可得:
??? 
??? 
??? 在變量節(jié)點和校驗節(jié)點進(jìn)行卷積運算的域分別為i+(變量節(jié)點域:實數(shù)域加上+∞)和GF(2)×[0,∞](校驗節(jié)點域:簡稱G域),利用傅立葉變換計算Qk和Pk時，在兩個域之間相互轉(zhuǎn)換，從而使計算過程相當(dāng)復(fù)雜[4]。
2 密度進(jìn)化算法" title="進(jìn)化算法">進(jìn)化算法的實現(xiàn)
??? 密度進(jìn)化的實現(xiàn)主要包括三部分：變量節(jié)點域卷積、G域卷積和兩個域之間適合卷積的密度函數(shù)表達(dá)式的相互轉(zhuǎn)換。參考文獻(xiàn)[5-7]對不同的方法作了闡述，具有各自的特點。
2.1 離散密度進(jìn)化(DDE)
??? 為了計算機(jī)仿真處理，對第1節(jié)算法中LLR消息、v、u量化處理。設(shè)量化比特為q,量化步進(jìn)為Δ，量化區(qū)間為[-N,N], N=2q-1-1。如果消息值在范圍(nΔ-Δ/2,nΔ+Δ/2)，n是一個整數(shù)，當(dāng)-N≤n≤N時，消息量化為n；當(dāng)n<-N和n>N時，分別量化為-N和N。
??? pv和pu分別表示離散消息的概率聚集函數(shù)(pmf)。由于離散消息都是獨立和均勻分布的隨機(jī)變量，由(1)式易得變量節(jié)點的密度進(jìn)化規(guī)則為：
借助于快速傅立葉變換(FFT)能夠有效實現(xiàn)。
??? 對校驗節(jié)點定義如下的二元運算符Φ：
??? 
??? 其中a、b都是離散消息，Q表示量化運算。易知Φ是遞歸運算，可以推導(dǎo)出校驗節(jié)點密度進(jìn)化規(guī)則：
(pv)。采用查表法計算Φ，加速算法實現(xiàn)。
??? 對于非規(guī)則LDPC碼，DDE算法是：
??? 
??? 該算法適合各種對稱信道，如BSC、BEC、高斯信道等?？紤]AWGN信道，LDPC(3,6)規(guī)則碼，信道噪聲方差σexact=0.880 91[3]，在不同量化比特情形下求得門限值σDDE如表1所示，可見，量化14比特時，結(jié)果已相當(dāng)精確。
?
?
2.2 利用對稱傅立葉變換(SFT)計算
??? DDE算法在變量節(jié)點域未能充分利用LLR消息概率密度函數(shù)f的對稱性。在對稱信道上傳輸全1碼字時，f對稱，從而g(x):=e-1/2x f(x)是偶函數(shù)。定義傅立葉變換
假設(shè)f取值于kδ，k=-K,…,0,1,…,K，對e-1/2 x f(x)填充0，進(jìn)行22m點離散傅立葉變換(2m+1>K)。實際中，F(xiàn)g(jw)比Ff(jw)更有優(yōu)勢。首先，前者是實數(shù)和關(guān)于w的偶函數(shù)，便于乘積計算；其次，函數(shù)g的尾值呈指數(shù)級減少，極大地降低了FFT計算時的混疊現(xiàn)象。這樣，不必在每對卷積之后返回實數(shù)域，只要在變量節(jié)點域卷積結(jié)束時返回即可，節(jié)省了大量計算。
??? 在校驗節(jié)點域，即G域，傅立葉變換定義為：Ff(v):=
取值于實數(shù)[0,Kδ]U+∞。那么傅立葉變換：
??? 
??? 現(xiàn)在的難題是如何量化v。根據(jù)文獻(xiàn)[6]，實際采用v=eα(1+jw)。依照δ對α量化，取w=0 將降低復(fù)雜度。
??? 這種算法比DDE更為接近原始的密度進(jìn)化原理，但達(dá)到同樣精度需要少得多的計算量。對于規(guī)則LDPC(3,6)碼，不同量化間隔時的噪聲門限σSFT如表2所示。
?
?
2.3 高斯近似
??? 如果信道是AWGN，消息的概率密度是近似高斯分布" title="高斯分布">高斯分布的。Wiberg[8]通過仿真首先發(fā)現(xiàn)這個事實。由于LLR消息的分布是相近的，利用對數(shù)正態(tài)的性質(zhì)，可以證明在密度進(jìn)化過程中消息是近似高斯分布的。利用對稱條件f(x)=exf(-x)，高斯分布的LLR消息服從N(μ0,2μ0)。假設(shè)AWGN信道噪聲均值為0，方差為σ2，傳輸全0碼字，易知μ0=2/σ2。只要確定?滋0就能完整描述概率密度函數(shù)。
??? mv和mu分別表示v和u的均值，則(1)、(2)式兩邊取均值，化簡變換可得：
??? 
??? 其近似計算方法是：
??? 
??? 用高斯近似算法求得規(guī)則LDPC(4,6)碼的噪聲門限為σGA=1.003 6，相應(yīng)的信噪比Eb/N0=1.729 9。對于不同信噪比的消息概率密度的均值變化如圖1所示。當(dāng)Eb/N0大于門限，k→∞時，均值趨于無窮大，意味著誤碼率趨于0；當(dāng)Eb/N0小于門限，k→∞時，均值趨于一個有限固定值，意味著誤碼率不可能趨于0。Eb/N0值越大，正確譯碼需要的迭代次數(shù)越少。當(dāng)Eb/N0=1.76時，概率密度分布如圖2所示。隨著迭代次數(shù)的增長，概率分布向正向移動，譯碼器幾乎能夠正確譯碼。
?
?
3 仿真和結(jié)論
??? 前面討論的三種密度進(jìn)化算法各有特點。根據(jù)實際需要，選擇合適的算法對LDPC碼進(jìn)行研究。表3給出了不同碼率的規(guī)則LDPC碼采用不同密度進(jìn)化算法求出的門限值、σGA與σDDE的距離ΔGA、σSFT與σDDE的距離ΔSFT以及σDDE與香農(nóng)限σC的距離Δσ。DDE和SFT兩種方法的精度差別不多；高斯近似的精度稍微差些，但其計算量少很多。
?
?
??? 表3中Δσ表明，規(guī)則碼的門限值距離香農(nóng)限還較遠(yuǎn)。LDPC碼研究重點之一就是利用密度進(jìn)化算法優(yōu)化度分布(λ,ρ)設(shè)計好的非規(guī)則碼，獲得距離香農(nóng)限更近的門限。參考文獻(xiàn)[5]中設(shè)計出了Δσ=0.004 5dB的非規(guī)則碼，與香農(nóng)限的距離已經(jīng)很小了。
??? 密度進(jìn)化方法是現(xiàn)代高級編碼研究的重要工具,不僅適用于LDPC碼，也可用于Turbo碼、MN碼等的分析和設(shè)計。這種方法的提出，促進(jìn)了現(xiàn)代高效糾錯編碼的發(fā)展。
參考文獻(xiàn)
[1] GALLAGER 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 decoding. 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 parity -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. IEEE Trans. Inform. Theory,2001,47(2):657-670.
[8]?WIBERG N. Codes and decoding on general graphs. Ph.D. Dissertation,? Department? of Electrical Engineering, Linkoping?University, 1996.