2.2.3 密度進化與高斯近似算法

密度進化（density evolution,DE）的基本思想是由Gallager[4]提出的。Richardson等[8-9]和Chung等[10]最早利用密度進化分析LDPC碼采用BP算法的漸近行為。他們的研究表明，對于許多重要的信道，例如加性白高斯噪聲（additive white Gaussian noise,AWGN）信道，當碼長無限長時，針對隨機構造的 LDPC 碼集合，可以用DE算法計算出無差錯譯碼的門限值。因此，DE算法能夠比較與分析LDPC碼的漸近性能，是一種重要的理論分析工具。

1．密度進化

所謂密度進化，就是在Tanner圖上計算與跟蹤LLR的概率密度函數（probability density function,PDF）。假設信道LLR的概率密度函數為p(L)；第l次迭代，變量節點到校驗節點外信息的PDF為p(Ml)，校驗節點到變量節點外信息的PDF為p(El)。隨著迭代次數的增加，外信息的PDF會演化。

DE成立的兩個獨立性假設如下。

（1）信道無記憶，這個假設是指各個接收信號相互獨立，因此互不相關。

（2）Tanner圖不存在長為2l或更短的環，這樣保證了各節點傳遞的外信息相互獨立。

首先，觀察(3,6)規則LDPC碼的BP譯碼過程。以某個檢驗節點為根節點構成的消息傳遞樹如圖2-3所示。

如圖2-3所示，在一次迭代中，作為根節點的校驗節點向連接到它的某個變量節點傳遞信息，這個變量節點接收到兩路校驗節點信息以及信道信息后生成外信息，傳遞到與之相連的下一層的dv-1=2個校驗節點。而這兩個校驗節點又可以進一步擴展 dc-1=5個變量節點。這樣經過兩次迭代，根節點的信息傳遞到了(dv-1)(dc-1)= 2 × 5=10個變量節點。注意，在變量節點處的計算還需要考慮信道信息。

一般地，對于(dv,dc)規則LDPC碼，BP算法的迭代計算式為

對于變量節點向校驗節點傳遞的消息，由于各消息相互獨立，因此外信息的PDF是各個消息PDF的卷積，表示為

其中，*表示卷積運算。由于式（2-32）涉及dv-1個卷積運算，復雜度較高，通常用快速傅里葉變換（fast Fourier transform,FFT）代替，從而降低計算復雜度。

類似地，根據式（2-31），校驗節點向變量節點傳遞的消息可以分解為兩部分，即

其中， 是模2加運算，而是普通的代數求和運算。由于各個變量節點輸入的外信息相互獨立，因此的概率密度函數表示為

上述計算涉及dc-1個卷積運算，也可用FFT代替。

最終，譯碼比特LLR的PDF可表示為

上述規則LDPC碼的PDF計算可以進一步推廣到非規則LDPC碼。此時變量與校驗節點信息的PDF計算式為

由此，DE算法過程可以簡述如下。給定一組度分布(λ(x),ρ(x))，針對B-DMC，利用信道對稱性條件，假設發送全零碼字，給定信道條件，例如二進制輸入加性白高斯噪聲（binary input additive white Gaussian noise, BI-AWGN）信道的均方根噪聲σ，反復進行式（2-27）的概率密度函數迭代運算。當迭代次數充分大時，比特 LLR Λ＜0對應的概率就是譯碼的差錯概率，即。

信噪比（signal-to-noise ratio,SNR）為,BI-AWGN信道下，(3,6)規則LDPC碼p(M l)與p(El)演化結果分別如圖2-4和圖2-5所示。

由圖2-4可知，初始分布p(L)為高斯分布，隨著迭代次數增加，p(Ml)仍然為高斯分布，并且LLR均值逐漸增大，其小于0的拖尾逐步減少，直至趨于0。

由圖2-5可知，在迭代早期，例如第1次迭代，p(El)并不是高斯分布，但隨著迭代次數增大，函數形狀越來越接近高斯分布，并且隨著LLR均值逐漸增大，小于0的拖尾趨于消失。

利用密度進化算法，我們可以針對特定度分布計算其譯碼無差錯的噪聲門限。

定義2.3 對于BI-AWGN，噪聲門限定義為

仍然以(3,6)規則LDPC碼為例，在BI-AWGN信道下，不同信噪比的誤碼率（bit error ratio,BER）性能如圖2-6所示。當（σ=0.881）時，隨著迭代次數的增加，誤碼率不收斂；而當（σ=0.879）時，迭代次數超過100后，誤碼率已經趨于0。由此可見，噪聲門限必然滿足0.879＜σ*＜0.881。我們可以通過DE算法確定其精確值為σ*=0.88（）。

碼率，反解BI-AWGN信道容量，可以得到極限信噪比，相應的噪聲門限σ*=0.978 69。由此可知，(3,6)規則LDPC碼的噪聲門限與信道容量極限還有很大差距。這種碼性能受限的關鍵原因是度分布過于規則，為了逼近信道容量極限，需要對變量節點、校驗節點的度分布進行優化，設計高度不規則的 LDPC 碼。研究者借助密度進化工具，采用差分演化或迭代線性規劃算法，得到了高性能的度分布。其中最著名的是Chung等[10]基于DE算法得到的優化分布，如式（2-38）所示，其變量節點度分布為2～8 000，具有高度不規則性。

上述分布對應的信噪比，噪聲門限σ*=0.978 186 9，與信道容量極限的差距為0.004 5 dB。

需要注意的是，上述分析的是碼長與迭代次數趨于無窮大的極限信噪比，即N→∞,l→∞。從漸近性能來看，即使碼長無限長、迭代次數無限大，這種不規則LDPC碼仍與信道容量極限有0.004 5 dB的差距，因此這種不規則LDPC碼只能逼近BI-AWGN信道的容量極限，但嚴格意義上講是容量不可達的。從有限碼長性能來看，Chung等[10]構造了最大度為100與200的不規則LDPC碼，碼長N=107，迭代2 000次，誤比特率為10-6，距離香農限約0.04 dB，遠未達到信道容量極限。

盡管如此，基于DE算法構造漸近性能優越的度分布為設計逼近信道容量極限的 LDPC 碼提供了完整的理論框架。沿著這一思路，人們構造了眾多的高性能的LDPC碼。

2．高斯近似

密度進化是一個良好的理論工具，能夠精確分析給定度分布的漸近性能，但其計算結果的準確性依賴于LLR分布的量化精度。一般而言，只有高量化精度才能獲得準確的門限值估計，但即使采用FFT，計算復雜度仍然巨大。

作為一種替代分析工具，高斯近似（Gaussian approximation,GA）[11]雖然犧牲了一些準確性，但顯著降低了計算復雜度。高斯近似假設變量節點與校驗節點的外信息近似服從高斯分布，因此這些信息的方差是均值的一半，它們的概率密度函數完全由均值決定。這樣我們只要在迭代過程中跟蹤外信息的均值，就能夠預測漸近性能。

對于(dv,dc)規則的LDPC碼，假設變量節點v與校驗節點u消息的均值分別為mv與mu，則第l次迭代變量節點消息的均值遞推式為

其中，第0次迭代（即初始分布）對應的校驗節點消息均值為0，即。

而校驗節點消息的均值遞推式為

其中，函數?(x)定義為

在實際應用中，函數?(x)涉及復雜的數值積分，一般采用兩段近似公式，即

對于度分布為(λ(x),ρ(x))的非規則LDPC碼，其變量節點消息的遞推式為

而校驗節點消息的遞推式為

綜上所述，密度進化與高斯近似是兩種分析迭代譯碼漸近性能的理論工具，不僅可以用于 LDPC碼的性能分析與優化設計，也可用于 Turbo碼的性能分析與設計。