基于分層消息傳遞機(jī)制的低復(fù)雜度LDPC譯碼算法*

周 帆，牛琳琳，田秉禾

(沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院， 沈陽(yáng) 110159)

0 引言

LDPC碼是一種優(yōu)異的信道編碼技術(shù)，有效地保障了信息的可靠傳輸，在軍事通信領(lǐng)域中不可或缺，LDPC碼比Turbo碼時(shí)延低，譯碼性能好。在5G標(biāo)準(zhǔn)中， LDPC碼作為其信道編碼技術(shù)被采納。面對(duì)5G通信中對(duì)信道編碼技術(shù)更高的要求，在譯碼算法上，需要具備復(fù)雜度低和性能好的優(yōu)點(diǎn)以滿足5G通信的需求。

LDPC譯碼通常采用軟判決譯碼，軟判決譯碼最大程度的發(fā)掘了原信息的特點(diǎn)，在譯碼性能上具有較好的優(yōu)勢(shì)[1]。文獻(xiàn)[2]用對(duì)數(shù)似然比表示信息概率的對(duì)數(shù)似然比置信傳播(log-likelihood-ratio belief propagation，LLR BP)算法，文獻(xiàn)[3]提出在LLR BP的基礎(chǔ)上對(duì)校驗(yàn)節(jié)點(diǎn)步驟近似處理的最小和(min-sum，MS)算法，文獻(xiàn)[4]提出對(duì)MS算法改進(jìn)的歸一化最小和(normalized minimum sum，NMS)算法。上述算法都是從數(shù)學(xué)運(yùn)算角度降低了復(fù)雜度，基于消息傳遞機(jī)制的角度，文中提出了一種基于分層消息傳遞機(jī)制的低復(fù)雜度LDPC譯碼算法，即分層歸一化最小和(layering normalized minimum sum，LNMS)算法，該算法收斂速度快，且復(fù)雜度低。

1 LDPC碼

LDPC碼中信息位和監(jiān)督位的關(guān)系對(duì)應(yīng)一組線性方程[5]，把線性方程用矩陣形式表示，此矩陣記為校驗(yàn)陣H，因此校驗(yàn)陣H可完全代表LDPC碼。若c9、c8、c7、c6、c5表示信息位，c4、c3、c2、c1、c0表示監(jiān)督位，假設(shè)信息位和監(jiān)督位的關(guān)系對(duì)應(yīng)的線性方程和校驗(yàn)陣用式(1)表示，則碼字c=(c1，c2，c3，c4，c5，c6，c7，c8，c9，c10)∈C，滿足H·cT=0。

(1)

LDPC碼另一種表示方法是Tanner圖[6]。Tanner圖是一種雙向圖，它是由校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)兩部分組成的網(wǎng)格圖，Tanner圖中校驗(yàn)節(jié)點(diǎn)個(gè)數(shù)和檢驗(yàn)陣的行數(shù)匹配，變量節(jié)點(diǎn)的個(gè)數(shù)和檢驗(yàn)陣的列數(shù)對(duì)應(yīng)，Tanner圖間的連線表示檢驗(yàn)矩陣中“1”元素，式(1)中的校驗(yàn)矩陣H5×10用Tanner表示如圖1所示。

圖1 矩陣H對(duì)應(yīng)的Tanner圖

2 分層消息傳遞機(jī)制

分層消息傳遞機(jī)制對(duì)LDPC碼進(jìn)行分層譯碼，改變了傳統(tǒng)譯碼算法的消息傳遞機(jī)制，傳統(tǒng)的LDPC碼譯碼算法的消息傳遞機(jī)制分為水平步驟和垂直步驟，在實(shí)際應(yīng)用中譯碼算法需要大容量的存儲(chǔ)器存儲(chǔ)每次迭代的中間量，而且每次都要等到水平步驟或垂直步驟全部進(jìn)行完才能更新信息。進(jìn)行水平迭代更新時(shí)，變量節(jié)點(diǎn)處于等待狀態(tài)，而垂直迭代更新時(shí)，校驗(yàn)節(jié)點(diǎn)也處于等待狀態(tài)。譯碼過(guò)程中不能利用最新傳遞的可靠消息，降低了譯碼算法收斂速度，造成多次迭代才能譯出正確碼字[7]。分層消息傳遞機(jī)制改變變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)信息相互傳遞順序，使譯碼過(guò)程按校驗(yàn)節(jié)點(diǎn)個(gè)數(shù)分層進(jìn)行，當(dāng)某層完成信息更新，然后立刻將消息傳遞給下一層，分層消息傳遞機(jī)制是對(duì)傳統(tǒng)消息傳遞機(jī)制的改進(jìn)，分層消息傳遞機(jī)制可以圖2表示。

圖2 分層消息傳遞機(jī)制

3 LDPC譯碼算法

3.1 傳統(tǒng)譯碼算法

LLR BP算法將概率信息用對(duì)數(shù)似然比表示[8]，LLR BP算法的校驗(yàn)節(jié)點(diǎn)更新中含有tanh和artanh函數(shù)，設(shè)a表示校驗(yàn)節(jié)點(diǎn)，b表示變量節(jié)點(diǎn)，具體步驟描述如下：

(2)

該步驟中的tanh和artanh函數(shù)運(yùn)算量大，為降低計(jì)算復(fù)雜度高的問(wèn)題，MS算法將tanh和artanh函數(shù)用近似值代替[9]。MS算法校驗(yàn)節(jié)點(diǎn)更新步驟如下：

(3)

MS算法簡(jiǎn)化了LLR BP算法運(yùn)算量，用近似值代替實(shí)際值造成性能降低，NMS譯碼算法改進(jìn)MS譯碼算法校驗(yàn)節(jié)點(diǎn)更新步驟，該算法通過(guò)乘以α(0<α<1)因子對(duì)MS譯碼算法進(jìn)行矯正[10]。MS譯碼算法校驗(yàn)節(jié)點(diǎn)消息更新公式為：

(4)

其中，α被稱為矯正因子，NMS譯碼算法通過(guò)α因子來(lái)彌補(bǔ)MS譯碼算法的缺陷。

3.2 LNMS譯碼算法

LNMS譯碼算法改變了譯碼算法的消息傳遞機(jī)制，信息在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)間沿著Tanner的邊不斷傳遞更新，經(jīng)過(guò)多次迭代概率消息趨于穩(wěn)定，消息傳遞機(jī)制的不同，直接影響譯碼的收斂速度，譯碼算法的收斂速度影響正確譯碼所需的迭代次數(shù)，減小譯碼所需迭代次數(shù)進(jìn)而降低譯碼復(fù)雜度[11-12]。基于分層消息傳遞機(jī)制角度，提出一種分層歸一化最小和(layering normalized minimum sum，LNMS)算法，該算法是對(duì)NMS算法的改進(jìn)，使譯碼過(guò)程逐層參與，某個(gè)層完成更新后把最新概率信息傳遞給下一層，所有層都完成更新即為一次迭代過(guò)程。該算法的具體流程如下：

1)初始化賦值。判定接收數(shù)據(jù)概率的對(duì)數(shù)似然比L0(qb)，b=1，2，…,n，令檢驗(yàn)節(jié)點(diǎn)L0(rab)的初始化對(duì)數(shù)似然比為0，該公式為：

(5)

2)分層更新。把接收數(shù)據(jù)的對(duì)數(shù)似然比傳給變量節(jié)點(diǎn)，并計(jì)算第一層的校驗(yàn)節(jié)點(diǎn)似然比，該公式為：

(6)

3)一個(gè)校驗(yàn)節(jié)點(diǎn)運(yùn)算完(即第一層處理完)，更新對(duì)應(yīng)的似然值，然后重復(fù)步驟2)，處理下一個(gè)校驗(yàn)節(jié)點(diǎn)，該公式為：

(7)

4)所有的層都處理完，就完成一次迭代，若k不超過(guò)最大迭代次數(shù)，則k=k+1，重復(fù)步驟2)和3)，直到滿足H·cT=0或者達(dá)到最大迭代次數(shù)，則結(jié)束譯碼。

4 仿真結(jié)果及復(fù)雜度分析

為驗(yàn)證基于分層消息傳遞機(jī)制的LNMS譯碼算法的性能，從復(fù)雜度和誤碼率兩個(gè)角度分析，仿真比較LNMS算法、LLR BP算法、MS算法和NMS算法性能。

4.1 誤碼率性能仿真分析

為了驗(yàn)證改進(jìn)的LNMS算法能否加快譯碼收斂速度，仿真在高斯信道下，對(duì)IEEE802.16e標(biāo)準(zhǔn)的碼率1/2，碼長(zhǎng)576 bit的LDPC碼進(jìn)行譯碼，對(duì)比LNMS算法和NMS算法的收斂速度，分析兩種譯碼算法誤碼率隨著迭代次數(shù)的變化曲線，仿真結(jié)果如圖3所示。

仿真結(jié)果可以看出：基于分層消息傳遞機(jī)制的LNMS譯碼算法比傳統(tǒng)NMS譯碼算法收斂速度快，在誤碼率為10-3左右情況下，LNMS譯碼算法所需迭代次數(shù)為9次，NMS譯碼算法所需的迭代次數(shù)為17次，在迭代次數(shù)為1到17情況下，LNMS算法和NMS算法誤碼率曲線變化明顯，在迭代次數(shù)較大的情況下，誤碼率曲線變化緩慢。LNMS算法能夠加快譯碼收斂速度，降低迭代次數(shù)，從而減少譯碼復(fù)雜度。

為了驗(yàn)證LNMS算法和LLR BP算法、MS、LNMS算法誤碼率性能，仿真中采用IEEE802.16e標(biāo)準(zhǔn)的碼率都為1/2，碼長(zhǎng)576 bit的LDPC碼，在高斯信道下，令迭代次數(shù)為10，對(duì)比分析不同譯碼算法誤碼率隨著信噪比變化曲線，仿真結(jié)果如圖4所示。

圖4 不同譯碼算法性能比較

仿真結(jié)果表明：隨著信噪比的增大，LNMS算法和LLR BP算法、MS、NMS算法誤碼率都降低，迭代次數(shù)為10的情況下，基于分層消息傳遞機(jī)制的LNMS算法誤碼率最低，MS算法復(fù)雜度低但性能最差，LLR BP性能介于LNMS算法的和NMS算法之間，在迭代次數(shù)較少的情況下，LNMS算法能加快收斂，性能最優(yōu)。

4.2 復(fù)雜度分析

為了比較LNMS算法、LLR BP譯碼算法、MS譯碼算法和NMS譯碼算法復(fù)雜度性能，在EEE802.16e標(biāo)準(zhǔn)的碼率都為1/2，碼長(zhǎng)576 bit的LDPC碼，對(duì)4種譯碼算法的復(fù)雜度進(jìn)行對(duì)比分析，假設(shè)校驗(yàn)陣的行數(shù)為m，列數(shù)為n，行重為wr，列重為wc，一次迭代中計(jì)算復(fù)雜度如表1所示。

表1 算法復(fù)雜度分析

由表1可知，LLR BP 算法運(yùn)算量大復(fù)雜度高；MS算法只有加法運(yùn)算，復(fù)雜度最低； LNMS算法和NMS算法比MS算法多一步乘法運(yùn)算，復(fù)雜度稍高，但還是遠(yuǎn)遠(yuǎn)低于LLR BP算法，一次迭代時(shí)LNMS算法和NMS算法復(fù)雜度相同，但基于分層消息傳遞機(jī)制的LNMS算法具有加快譯碼收斂速度的優(yōu)勢(shì)，降低了正確譯碼所需的迭代次數(shù)，進(jìn)而降低譯碼復(fù)雜度。

5 結(jié)論

從消息傳遞機(jī)制角度分析，提出基于分層消息傳遞機(jī)制的LNMS算法，該算法改變傳統(tǒng)譯碼算法的消息傳遞機(jī)制，加快了譯碼收斂速度，使正確譯碼所需迭代次數(shù)大大減少，從而降低了復(fù)雜度，仿真結(jié)果表明，和傳統(tǒng)譯碼算法相比，LNMS算法收斂速度快且復(fù)雜度低，在迭代次數(shù)少的情況下譯碼性能也較好，從復(fù)雜度和誤碼率兩個(gè)角度來(lái)說(shuō)，基于分層消息傳遞機(jī)制的低復(fù)雜度LDPC譯碼算法更具有實(shí)際應(yīng)用價(jià)值。