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