2.2.2 置信傳播譯碼算法

1．算法原理

LDPC碼的譯碼一般采用迭代結(jié)構(gòu)，其譯碼器結(jié)構(gòu)如圖2-2所示。LDPC碼譯碼器包括變量節(jié)點(diǎn)譯碼器與校驗(yàn)節(jié)點(diǎn)譯碼器，通過交織與解交織操作在兩個譯碼器之間傳遞外信息，經(jīng)過多次迭代后，變量節(jié)點(diǎn)譯碼器的輸出進(jìn)行判決，得到最終譯碼結(jié)果。

LDPC碼典型的譯碼算法是置信傳播（belief propagation,BP）算法。BP算法是在變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間傳遞外信息，經(jīng)過多次迭代后算法收斂。它是一種典型的后驗(yàn)概率（a posteriori probability,APP）譯碼算法，經(jīng)過充分迭代逼近最大后驗(yàn)（maximum a posteriori,MAP）譯碼性能。

給定二元離散無記憶對稱信道（B-DMC）W:X →y,X =｛0,1｝→｛±1｝，假設(shè)似然概率為，則信道軟信息為

反解得到兩個似然概率為

定理2.1 比特軟估計值為，其中t 是雙曲正切函數(shù)。

證明 由于采用二進(jìn)制相移鍵控（binary phase-shift keying,BPSK）調(diào)制，因此信號的軟估計值可以表示為

將式（2-8）代入式（2-9），可得

證畢。

另外，利用雙曲正切的反函數(shù)可得

下面分析校驗(yàn)節(jié)點(diǎn)向變量節(jié)點(diǎn)傳遞的外信息。令表示變量節(jié)點(diǎn)i取值為1時第 j個校驗(yàn)方程滿足約束的概率。顯然，這個校驗(yàn)方程如果滿足約束，則剩余的變量節(jié)點(diǎn)有奇數(shù)個比特取值為1。因此，這個概率表示為

其中，Pj,i＇表示變量節(jié)點(diǎn)i＇取值為1時，校驗(yàn)節(jié)點(diǎn) j的估計概率。相應(yīng)地，當(dāng)變量節(jié)點(diǎn)i的取值為0時，滿足校驗(yàn)節(jié)點(diǎn) j的約束的概率為。

設(shè)Ej,i表示當(dāng)變量節(jié)點(diǎn)i取值為1時從校驗(yàn)節(jié)點(diǎn) j到所連接的變量節(jié)點(diǎn)i傳遞的外信息，計算式為

將式（2-12）代入式（2-13）可得

其中，Mj,i＇是變量節(jié)點(diǎn)i＇向校驗(yàn)節(jié)點(diǎn) j傳遞的外信息，其定義為

注意，式（2-14）的連乘中要去掉從變量節(jié)點(diǎn)i傳來的外信息，這樣可以避免自環(huán)。

根據(jù)定理2.1可得

再利用式（2-11），外信息可以進(jìn)一步變換為

或者得到等價變換形式，即

然后，分析變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的外信息。假設(shè)各邊信息相互獨(dú)立，則從變量節(jié)點(diǎn)i向校驗(yàn)節(jié)點(diǎn) j發(fā)送的外信息可以表示為

其中，Li是信道接收的對數(shù)似然比（logarithm likelihood ratio,LLR）信息。需要注意的是，上述外信息計算中，需要去掉從校驗(yàn)節(jié)點(diǎn) j傳來的外信息，這樣不會產(chǎn)生自環(huán)，避免信息之間相關(guān)。

變量節(jié)點(diǎn)對應(yīng)的比特LLR為

相應(yīng)的判決準(zhǔn)則為

注意，比特 LLR Λi需要將信道軟信息與所有校驗(yàn)節(jié)點(diǎn)的外信息疊加。根據(jù)上述描述，BP算法可以總結(jié)如下。

（1）根據(jù)式（2-7）計算信道軟信息Li序列，初始化變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的外信息Mj,i=Li，并傳遞到校驗(yàn)節(jié)點(diǎn)。

（2）在校驗(yàn)節(jié)點(diǎn)處，根據(jù)式（2-17）計算校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)的外信息Ej,i，并傳遞到變量節(jié)點(diǎn)。

（3）在變量節(jié)點(diǎn)處，根據(jù)式（2-19）計算變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的外信息Mj,i，并傳遞到校驗(yàn)節(jié)點(diǎn)。

（4）根據(jù)式（2-20）計算比特 LLR，并利用式（2-21）判決準(zhǔn)則得到碼字估計向量?c。

（5）如果迭代次數(shù)達(dá)到最大值Imax或者滿足校驗(yàn)關(guān)系，則終止迭代；否則，返回第（2）步。

BP算法在變量節(jié)點(diǎn)的計算是累加所有的信道信息與外信息；而在校驗(yàn)節(jié)點(diǎn)的計算則是將所有基于外信息得到的軟估計值相乘，再求解反雙曲正切函數(shù)。因此，BP算法也稱為和積算法。

BP算法在校驗(yàn)節(jié)點(diǎn)處的計算式（2-17）可以簡化。首先，將Mj,i＇分解為兩項(xiàng)，即

其中，sgn(x)是符號函數(shù)。利用這一分解，可以得到

這樣，式（2-17）可以寫為

可以將式（2-24）中的連乘改寫為求和，推導(dǎo)如下。

定義函數(shù)

由于該函數(shù)滿足，因此可知θ(x)=θ-1(x)。代入式（2-25），可得

這樣，符號連乘可以用每個變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的外信息Mj,i＇的硬判決模2加得到，而函數(shù)θ(x)可以查表得到。

上述校驗(yàn)節(jié)點(diǎn)外信息計算式還可以進(jìn)一步簡化。考慮到最小項(xiàng)決定了乘積結(jié)果，因此式（2-27）可近似為

這種算法在變量節(jié)點(diǎn)涉及求和運(yùn)算，在校驗(yàn)節(jié)點(diǎn)只涉及最小化運(yùn)算，因此被稱為最小和（minimum sum,MS）算法。與標(biāo)準(zhǔn)BP算法相比，最小和算法性能稍有損失，但外信息計算得到了大幅簡化。

對于BP算法或MS算法，由于外信息都是沿變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)的連邊傳遞，因此，單次迭代的計算量為

一般地，LDPC碼的平均度分布為，則BP算法的計算復(fù)雜度為O(ImaxNlog 2 N)。

BP算法和MS算法是軟信息譯碼算法，如果只考慮硬判決信息，可以進(jìn)一步簡化為比特翻轉(zhuǎn)算法。這時算法復(fù)雜度更低，但性能損失較大。

2．消息傳遞機(jī)制

從實(shí)用化角度來看，BP算法的消息傳遞機(jī)制非常重要。一般而言，BP算法的消息傳遞機(jī)制可分為4種，簡述如下。

（1）全串行譯碼

全串行譯碼是標(biāo)準(zhǔn)的 BP 譯碼，在一次迭代過程中，變量節(jié)點(diǎn)按順序啟動，等所有外信息都計算完成后，再按照連邊順序在校驗(yàn)節(jié)點(diǎn)按順序計算相應(yīng)外信息。基于這種方法的硬件譯碼器只需要一個計算單元就能夠完成譯碼，但需要存儲所有外信息，空間資源消耗大。

（2）全并行譯碼

全并行譯碼也稱為洪泛調(diào)度，需要采用硬件電路實(shí)現(xiàn)全部的計算單元，這樣每個變量節(jié)點(diǎn)、校驗(yàn)節(jié)點(diǎn)都可以單獨(dú)啟動，快速計算與傳遞外信息。這種譯碼器結(jié)構(gòu)能夠獲得最高的吞吐量，但硬件資源開銷大，并且碼長很長時，Tanner圖連邊非常多，芯片內(nèi)部單元間的布局非常復(fù)雜。

（3）部分并行譯碼

部分并行譯碼是全串行譯碼和全并行譯碼的折中，采用硬件電路實(shí)現(xiàn)一組譯碼單元，每次迭代時，同時讀取一組變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)信息，并行運(yùn)算并相互傳遞外信息。這種機(jī)制能夠達(dá)到譯碼性能與吞吐量、硬件資源開銷的較好折中，是LDPC碼譯碼器常用的消息傳遞機(jī)制。

（4）洗牌譯碼

LDPC碼的洗牌譯碼方案[7]與Turbo碼類似，它的基本思想是校驗(yàn)節(jié)點(diǎn)盡早利用變量節(jié)點(diǎn)更新后的外信息計算輸出信息。令分別表示第l次與第l 1- 次迭代變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的外信息，表示第l次迭代校驗(yàn)節(jié)點(diǎn)向變量節(jié)點(diǎn)傳遞的外信息。則校驗(yàn)節(jié)點(diǎn)外信息計算式修正為

顯然，式（2-30）中，變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的外信息按序號分為了兩組，即i＇＜i與i＇＞i。前者外信息已經(jīng)更新，因此采用第l次迭代結(jié)果；而后者由于外信息還未更新，因此采用前一次，即第l-1次迭代的結(jié)果。由于用到了最新的外信息計算結(jié)果，這種機(jī)制可以與前3種機(jī)制組合，加速譯碼收斂。