Group Shuffled BP算法的密度演進和高斯近似

陳 文， 劉斌彬， 白 棟， 葛啟宏

(國家廣電總局廣播科學(xué)研究院 北京泰美世紀(jì)科技有限公司，北京 100097)

0 引言

低密度校驗（LDPC）碼最早由Gallager提出，是一種校驗矩陣非常稀疏的線性分組碼。Mackey等人的進一步研究表明，LDPC碼的性能在置信傳播（BP）譯碼算法下可以接近Shannon極限，且譯碼復(fù)雜度低于Turbo碼[1]。目前，LDPC碼已經(jīng)被越來越多的用于各種通信系統(tǒng)中。中國的數(shù)字電視地面廣播標(biāo)準(zhǔn)DTTB和移動多媒體廣播標(biāo)準(zhǔn)CMMB均采用了LDPC碼的信道編碼方案。

LDPC碼在應(yīng)用中所面臨的一個問題是譯碼所需的迭代次數(shù)較多，從而影響了譯碼器的數(shù)據(jù)吞吐率[2-3]。為了加快譯碼的收斂速度，Zhang等人提出了Group Shuffled BP譯碼算法[4]。為了合理的設(shè)計譯碼器的算法，首先需要分析譯碼算法的收斂性能。密度演進通過跟蹤迭代過程中各組節(jié)點信息概率密度的變化，可以分析Group Shuffled BP譯碼算法的收斂性能[5]，但計算的復(fù)雜度較高。

為了簡化密度演進計算的復(fù)雜度，本文在證明對稱性條件的基礎(chǔ)上，提出了基于Group Shuffled BP譯碼算法的密度演進的高斯近似。

1 Group Shuffled BP譯碼算法

BP譯碼算法是一種性能最好的消息傳遞（MP）算法[1]。在BP譯碼算法中，信息在變量節(jié)點和校驗節(jié)點之間來回的傳遞。設(shè)為第i次迭代中校驗節(jié)點m傳遞給變量節(jié)點n的信息，為第i次迭代中變量節(jié)點n傳遞給校驗節(jié)點m的信息，為從信道得到的變量節(jié)點n的初始信息。校驗節(jié)點處的信息更新可表示為：

其中N(m) / n表示除變量節(jié)點n之外的所有與校驗節(jié)點m相連的變量節(jié)點的集合。變量節(jié)點處的信息更新可表示為：

其中M(n)/m表示除校驗節(jié)點m之外的所有與變量節(jié)點n相連的校驗節(jié)點的集合。

在Group Shuffled BP譯碼算法中，將變量節(jié)點分為若干組，逐組的對信息進行更新，變量節(jié)點更新和校驗節(jié)點更新交錯的進行[4]。假設(shè)將N個變量節(jié)點分為G組，每組包含N / G =q個變量節(jié)點。對于第g ( 0≤g＜G ) 組中的變量節(jié)點n( g q≤n＜( g + 1) q )，式 (1) 被修改為：

對于校驗節(jié)點信息和變量節(jié)點信息，越多的信息參與對其的更新，其置信度就越高。因此，采用Group Shuffled BP譯碼算法可以大大加快收斂速度。

2 Group Shuffled BP的密度演進

由于在Group Shuffled BP譯碼算法中，變量節(jié)點被分為若干組，在相應(yīng)的密度演進中，也需要逐組的對節(jié)點信息的概率密度進行跟蹤。

對于校驗節(jié)點更新，定義函數(shù)：

則式 (1) 可以通過：

用一種遞歸的方式來計算[6]，其中 l為該校驗節(jié)點的度。因此校驗節(jié)點信息的概率密度為：

考慮Group Shuffled消息傳遞調(diào)度。從式 (3) 可以看出，對于第g組的校驗節(jié)點信息( gq≤n＜(g+1)q)，其值取決于已更新的變量節(jié)點信息(n’＜gq) 和未更新的變量節(jié)點信息(n’≥gq)。為了避免對和所有可能組合的 復(fù)雜運算，定義已更新變量節(jié)點信息的平均概率密度[4]：

定義未更新變量節(jié)點信息的平均概率密度：

對于度為l的校驗節(jié)點m，其傳遞給變量節(jié)點n的信息U(i)mn中共有種可能的組合。對于每一個j(j =0,1,…,l-1)，又有種可能的組合包含 j個已更新的變量節(jié)點信息和l -1- j個未更新的變量節(jié)點信息。考慮到校驗節(jié)點度分布ρl，的概率密度為：

利用式(4)、(8)、(9) 和式(10)，則可以跟蹤迭代過程中變量節(jié)點信息和校驗節(jié)點信息概率密度的變化。

3 密度演進的高斯近似

可以看出，基于Group Shuffled BP譯碼算法的密度演進的計算比較復(fù)雜。我們考慮采用高斯近似對其進行簡化。首先證明信息概率密度的對稱性。

3.1 對稱性條件的證明

根據(jù)文獻[5]中)Γ(x的定義，式 (4) 可以寫為：

其中?表示卷積。式 (10) 可以寫為：

文獻[5]中給出了下面的定理：

定理1 假設(shè)發(fā)送的是全零碼，則對數(shù)似然比（LLR）形式的初始信息在二元無記憶對稱信道下是對稱性的。

定理2 對稱信息的卷積仍然是對稱性的。

定理3 函數(shù)()Γx和1()Γx-是對稱的，當(dāng)且僅當(dāng)x是對稱的。

定理4 如果函數(shù)()Γx是對稱的，則它們的卷積也是對稱的。

3.2 高斯近似

其中k為該變量節(jié)點的度。

對于校驗節(jié)點更新，定義函數(shù)：

對式 (1) 兩邊取期望，并考慮到變量節(jié)點度分布kλ，有：

其中l(wèi)為該校驗節(jié)點的度。由于tanh ( μ/2 )為連續(xù)函數(shù)，其均值可以由μ / 2的均值和方差來近似[8]：

采用函數(shù)逼近，式 (16) 可以進一步簡化為：

考慮Group Shuffled消息傳遞調(diào)度。類似的，定義已更新變量節(jié)點信息的平均均值：

定義未更新變量節(jié)點信息的平均均值：

考慮到校驗節(jié)點度分布ρl，的均值為：

利用式 (13)、式(18)、式(19) 和式 (20)，則可以跟蹤迭代過程中變量節(jié)點信息和校驗節(jié)點信息均值的變化。

根據(jù)變量節(jié)點信息的概率密度，可以計算迭代過程中錯誤信息的概率，從而分析Group Shuffled BP譯碼算法的收斂性能。

4 分析與仿真

圖 1為采用密度演進的高斯近似計算得到的信噪比Eb/ N0分別為1.8 dB、2.0 dB、2.2 dB和2.4 dB時，Group Shuffled BP譯碼算法下誤碼率與迭代次數(shù)的關(guān)系。分組數(shù)樣G =36。所選用的碼為碼長N =9216、碼率R =1/2的 (3, 6) 規(guī)則LDPC碼。可以看出，當(dāng)?shù)螖?shù)分別達到5、6、7和8次時，基本上可以實現(xiàn)無錯誤的譯碼。

圖 2為實際仿真得到的相同信噪比條件下，Group Shuffled BP譯碼算法的平均迭代次數(shù)。最大迭代次數(shù)為200次。對比圖1可以看出，兩者幾乎完全一致。也就是說，采用基于Group Shuffled BP的密度演進及其高斯近似，可以比較準(zhǔn)確的分析Group Shuffled BP譯碼算法的收斂性能。

圖1 不同信噪比下誤碼率與迭代次數(shù)的關(guān)系

圖2 不同信噪比下的平均迭代次數(shù)

圖3為采用密度演進的高斯近似計算得到的分組數(shù)G分別為6、9、18和36時，Group Shuffled BP譯碼算法下誤碼率與迭代次數(shù)的關(guān)系。信噪比Eb/ N0=2.0 dB。可以看出，Group Shuffled BP譯碼算法對收斂速度的加快十分明顯。且分組數(shù)越大，收斂速度越快。

圖3 不同分組數(shù)下誤碼率與迭代次數(shù)的關(guān)系

5 結(jié)語

為了分析Group Shuffled BP譯碼算法的收斂性能，同時簡化密度演進計算的復(fù)雜度，本文在證明對稱性條件的基礎(chǔ)上，提出了基于Group Shuffled BP譯碼算法的密度演進的高斯近似。從而將密度演進中計算消息概率密度的無限維問題，簡化為跟蹤高斯分布均值的一維問題。仿真結(jié)果表明，該方法具有較高的精確度，可以有效分析Group Shuffled BP譯碼算法的收斂性能。

[1] MacKay D J C. Good Error-correcting Codes Based on Very Sparse Matrices[J].IEEE Trans. Inform. Theory,1999,45(02):399-431.

[2] 陳燕,蔡燦輝. LDPC碼的譯碼算法研究[J]. 通信技術(shù),2008,41(12):87-91.

[3] 鄭慧娟,童勝.LDPC卷積碼的快速收斂譯碼[J].通信技術(shù),2009,42(07):37-39.

[4] Zhang J, Fossorier M P C. Shuffled Iterative Decoding[J]. IEEE Trans. Commun.,2005,53(02):209-213.

[5] Richardson T J, Urbanke R L. The Capacity of Low-density Parity-check Codes Under Message Passing Decoding[J].IEEE Trans. Inform. Theory,2001,47(02):599-618.

[6] Chung S Y, Forney G D, Richardson T J, et al. On the Design of Low-density Parity-check Codes within 0.0045 dB of the Shannon Limit[J]. IEEE Commun. Lett.,2001,5(02):58-60.

[7] Chung S Y, Richardson T J, Urbanke R L. Analysis of Sum-product Decoding of Low-density Parity-check Codes Using Gaussian Approximation[J].IEEE Trans. Inform.Theory,2001,47(02):657-670.

[8] Asoodeh S, Ramezani H, Samimi H. Gaussian Approximation for LDPC Codes[C]//Proc.IEEE WiCOM.Shanghai:IEEE,2007:1437-1440.