Group Shuffled BP算法的密度演進(jìn)和高斯近似

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

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

0 引言

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

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

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

1 Group Shuffled BP譯碼算法

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

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

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

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

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

2 Group Shuffled BP的密度演進(jìn)

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

對(duì)于校驗(yàn)節(jié)點(diǎn)更新，定義函數(shù)：

則式 (1) 可以通過(guò)：

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

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

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

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

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

3 密度演進(jìn)的高斯近似

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

3.1 對(duì)稱性條件的證明

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

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

文獻(xiàn)[5]中給出了下面的定理：

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

定理2 對(duì)稱信息的卷積仍然是對(duì)稱性的。

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

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

3.2 高斯近似

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

對(duì)于校驗(yàn)節(jié)點(diǎn)更新，定義函數(shù)：

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

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

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

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

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

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

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

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

4 分析與仿真

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

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

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

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

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

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

5 結(jié)語(yǔ)

為了分析Group Shuffled BP譯碼算法的收斂性能，同時(shí)簡(jiǎn)化密度演進(jìn)計(jì)算的復(fù)雜度，本文在證明對(duì)稱性條件的基礎(chǔ)上，提出了基于Group Shuffled BP譯碼算法的密度演進(jìn)的高斯近似。從而將密度演進(jìn)中計(jì)算消息概率密度的無(wú)限維問題，簡(jiǎn)化為跟蹤高斯分布均值的一維問題。仿真結(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.