??? 摘 要： 詳細描述了密度進化（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碼集可以由一個度分布(λ,ρ)確定，即由變量節點和校驗節點的度分布函數確定：

???

其中l_max和r_max分別表示變量節點和校驗節點的最大度數。規則碼(d_v,d_c)是一種特殊情形，

??? LDPC碼最常用的譯碼算法是和積算法(Sum-Product Algorihm)。基于文獻[4]中的無環假設，如果一個規則LDPC碼（d_v,d_c）沒有長度小于或等于2l的環，則在l次迭代內，可以假定所有的消息變量是獨立的。設u₀表示變量節點接收信號的對數似然比(LLR)消息，v和u分別表示變量節點和校驗節點發送給各自鄰接節點的LLR消息^[2]。則變量節點和校驗節點的消息更新規則表示為：

???

??? 在無環和不同變量節點初始消息u₀服從獨立均勻分布(i.i.d.)的假設條件下，易知，u_i,i=1,2,…,d_v-1和v_i,i=1,2,…,d_c也是i.i.d.分布的。這樣計算u_i和v_i的概率密度函數變得容易。在譯碼第k次迭代時，v_i和u_i的概率密度分別表示為P_k和Q_k, k=1,2,…。P₀表示u₀的概率密度，

??? 基于上述的i.i.d.特性，對于k≥1，從(1)式可得:

???

???

??? 在變量節點和校驗節點進行卷積運算的域分別為i⁺(變量節點域:實數域加上+∞)和GF(2)×[0,∞](校驗節點域:簡稱G域),利用傅立葉變換計算Q_k和P_k時，在兩個域之間相互轉換，從而使計算過程相當復雜[4]。
2 密度進化算法" title="進化算法">進化算法的實現
??? 密度進化的實現主要包括三部分：變量節點域卷積、G域卷積和兩個域之間適合卷積的密度函數表達式的相互轉換。參考文獻[5-7]對不同的方法作了闡述，具有各自的特點。
2.1 離散密度進化(DDE)
??? 為了計算機仿真處理，對第1節算法中LLR消息、v、u量化處理。設量化比特為q,量化步進為Δ，量化區間為[-N,N], N=2^q-1-1。如果消息值在范圍(nΔ-Δ/2,nΔ+Δ/2)，n是一個整數，當-N≤n≤N時，消息量化為n；當n<-N和n>N時，分別量化為-N和N。
??? p_v和p_u分別表示離散消息的概率聚集函數(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，進行2^2m點離散傅立葉變換(2^m+1>K)。實際中，F_g(jw)比F_f(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)=e^xf(-x)，高斯分布的LLR消息服從N(μ₀,2μ₀)。假設AWGN信道噪聲均值為0，方差為σ²，傳輸全0碼字，易知μ₀=2/σ²。只要確定?滋0就能完整描述概率密度函數。
??? m_v和m_u分別表示v和u的均值，則(1)、(2)式兩邊取均值，化簡變換可得：

???

??? 其近似計算方法是：

???

??? 用高斯近似算法求得規則LDPC(4,6)碼的噪聲門限為σ_GA=1.003 6，相應的信噪比E_b/N₀=1.729 9。對于不同信噪比的消息概率密度的均值變化如圖1所示。當E_b/N₀大于門限，k→∞時，均值趨于無窮大，意味著誤碼率趨于0；當E_b/N₀小于門限，k→∞時，均值趨于一個有限固定值，意味著誤碼率不可能趨于0。E_b/N₀值越大，正確譯碼需要的迭代次數越少。當E_b/N₀=1.76時，概率密度分布如圖2所示。隨著迭代次數的增長，概率分布向正向移動，譯碼器幾乎能夠正確譯碼。

?

?