0 引言

    碼率為R=(N-M)/N的低密度奇偶校驗(Low-Density Parity-Check，LDPC)碼是一種線性分組碼^[1-2]。LDPC碼因其優(yōu)異的譯碼性能，已經受到了越來越多的關注，并且日前在深空通信、光纖通信、衛(wèi)星數(shù)字視頻、音頻廣播等領域已經得到了廣泛的應用^[3]。

    LDPC碼的傳統(tǒng)迭代譯碼算法flooding^[4-6]，又稱為兩相的消息傳遞，是最簡單的譯碼方式。flooding算法這種在一次迭代中順序更新所有節(jié)點的方式，導致其譯碼的收斂速度較慢，并且需要大量的迭代次數(shù)才能達到想要的譯碼效果。為了減少迭代的次數(shù)和收斂速度, 時序置信傳播譯碼算法^[7-8]（Belief-Propagation，BP）被提出。在時序譯碼算法中，假設校驗節(jié)點被分成p個子集，在一次迭代過程中，第一個子集中從變量節(jié)點到校驗節(jié)點的信息被更新，然后從校驗節(jié)點到相鄰的變量節(jié)點的信息要被更新并傳播，同樣其他p-1個校驗節(jié)點的子集也同時相應地被更新。很明顯，一次迭代過程也涉及到所有變量節(jié)點以及所有的校驗節(jié)點的子集，因此，每次譯碼迭代，時序譯碼算法的計算復雜度和傳統(tǒng)flooding相同，但是其收斂速度對比flooding算法，要快過兩倍。盡管置信傳播算法有很好的譯碼性能，但為了進一步提高譯碼性能，其不是最好的選擇，最終，Casado等人將剩余度概念運用到了置信傳播^[9-10]，并提出了兩種時序算法：基于剩余度置信(Residual Belief Propagation，RBP)傳播譯碼算法、基于校驗節(jié)點的剩余度置信傳播(Node-Wise RBP，NWRBP)譯碼算法^[11-12]。

    RBP算法和NWRBP算法這種迭代機制會導致有的變量節(jié)點很少有機會去將它們本身的消息傳播到整個譯碼過程中，所以，其譯碼算法不會達到最好的譯碼效果。為了減少這種情況帶來的誤差，本文提出了一種改進型NWRBP(Enhanced NWRBP，ENWRBP)算法，在迭代譯碼過程中，如果NWRBP算法譯碼沒有成功，則依次將更新最少次數(shù)的變量節(jié)點的初始化對比似然數(shù)值(Log-Likelihood Radio，LLR)設置為0，并重新譯碼，直到譯碼正確或達到最大測試次數(shù)。本算法最多測試T個變量節(jié)點。該算法改變了校驗節(jié)點的更新順序，均衡了變量節(jié)點的更新次數(shù)，從而提高了LDPC碼的譯碼性能。

1 LDPC碼的RBP和NWRBP譯碼算法

    對于規(guī)則(N，J，K)LDPC碼，N表示碼長，J和K分別表示校驗矩陣H行和列的重量。LDPC碼可以用Tanner圖表示。Tanner圖由變量節(jié)點、校驗節(jié)點以及連接變量節(jié)點和校驗節(jié)點的邊組成。變量節(jié)點c_i對應矩陣H中的第i列，校驗節(jié)點v_j對應矩陣H中的第j行。如果h_ij=1，表明Tanner圖中節(jié)點v_j和c_i由一條邊相連，否則不相連。圖1所示為規(guī)則(6，2，3)LDPC碼的Tanner圖，校驗節(jié)點和變量節(jié)點分別用方框和圓表示。每個節(jié)點連接的邊的個數(shù)稱之為該節(jié)點的度，圖1所示LDPC碼的校驗節(jié)點和變量節(jié)點的度分別為3和2^[13]。

其中，n_i是服從均值為0、方差為δ²的高斯白噪聲(表示為n_i～N(0，δ²))，且它們之間相互獨立。E_b/N_o表示信噪比(Signal-to-Noise Ratio，SNR)，E_b表示發(fā)送前每個信息比特的能量，N_o表示發(fā)送前噪聲功率譜密度以及δ²=N_o/2。在開始進行譯碼前，對于通過一個BPSK AWGN信道的碼字，最終接收序列的每個碼字的先驗概率的對數(shù)似然比(LLR)初始化為：

    式(3)和式(4)描述了譯碼過程中LDPC碼變量節(jié)點和校驗節(jié)點之間的消息更新和傳遞規(guī)律。RBP和NWRBP算法是將剩余度值作為度量去調整更新順序的兩種主要算法機制。剩余度是消息更新之前和之后差值的絕對值。在LDPC譯碼中，剩余度值的定義值為：  

    作為RBP的擴展和延伸，RBP算法和NWRBP算法兩者的區(qū)別是：RBP動態(tài)選擇最大剩余度所在的邊進行更新，而NWRBP動態(tài)選擇最大剩余度所在的校驗節(jié)點進行更新。NWRBP詳細步驟見算法1。

    算法1：LDPC碼的NWRBP算法譯碼流程

2 ENWRBP算法機制描述

    由于RBP譯碼算法和NWRBP譯碼算法每次通過一條邊或是一個校驗節(jié)點去更新傳播消息，這樣會形成一個個相對獨立彼此沒有影響的子集合，經過數(shù)次迭代后，可能就會導致忽略掉已經被正確修改的錯誤比特節(jié)點，再一次出現(xiàn)錯誤，所以，RBP算法和NWRBP算法都具有一定的貪婪性。而NWRBP譯碼算法根據(jù)節(jié)點更新消息，每個子集合范圍較大，其貪婪性相對較弱。因此，經過大量的迭代譯碼后，NWRBP算法的譯碼性能會優(yōu)于RBP算法譯碼性能。然而，這兩種算法的性能受限于陷井集(trapping sets)的影響，導致一些錯誤的變量節(jié)點(即誤碼)在迭代多次后很難被發(fā)現(xiàn)。經研究發(fā)現(xiàn)，NWRBP在譯碼過程中，節(jié)點更新的次數(shù)并不均衡，存在某些節(jié)點更新次數(shù)少的現(xiàn)象，而相對于更新次數(shù)較多的變量節(jié)點，更新次數(shù)較少的變量節(jié)點不能為相鄰節(jié)點提供足夠的有用信息，亦或該節(jié)點無法從相鄰節(jié)點獲得有用信息，導致相鄰節(jié)點或其本身發(fā)生錯誤的概率更大。本文正是利用此思想來減少帶來的誤差，在NWRBP譯碼算法的基礎上提出一種改進算法Enhanced NWRBP(ENWRBP)。在NWRBP譯碼算法的一次譯碼過程中，如果達到最大的迭代次數(shù)仍然不滿足譯碼成功條件，那么就尋找到在迭代過程中更新最少次數(shù)的變量節(jié)點v_min，并且將最初經高斯白噪聲信道接收到的序列對應的初始對數(shù)似然數(shù)r_min設置為0。隨后，重新用NWRBP進行譯碼，直到譯碼成功或連續(xù)重復T上述過程，即更新T次最少的變量節(jié)點。ENWRBP算法過程描述如圖2，詳細步驟見算法2。

    算法2：LDPC碼的ENWRBP算法譯碼流程

3 仿真結果與討論

    本文中所有的仿真都是在二進制輸入加性高斯白噪聲(BI-AWGN)信道進行的。譯碼方式采用基于剩余度置信傳播(RBP)算法、基于校驗節(jié)點的剩余度置信傳播(NWRBP)算法,以及本文提出的基于校驗節(jié)點的改進剩余度置信傳播(ENERBP)算法，最大迭代次數(shù)設為100，調制方式為BPSK，具體的仿真結果如圖3~圖6所示。

    圖3和圖4中T=10時，可以觀察到ENWRBP算法的譯碼性能要好于NWRBP和RBP算法。在SNR值較低時，圖3中SNR值為2.5～3 dB，圖4中為2.5～2.7 dB，誤碼率BER和誤幀率FER的曲線三者大致相同。隨著SNR值的增加，ENWRBP算法和NWRBP算法的譯碼曲線逐漸優(yōu)于RBP算法，圖3中NWRBP算法和ENWRBP算法依然大致相同，直到SNR值為4.0 dB時，ENWRBP算法開始優(yōu)于NWRBP算法，圖4中ENWRBP算法在所示SNR范圍內始終優(yōu)于RBP算法和NWRBP算法，并且這種優(yōu)勢隨著SNR值增大而逐漸擴大。例如：如圖4所示，在FER=2×10^-4時，相比RBP和NWRBP，ENWRBP的FER分別得到0.3 dB和0.18 dB的譯碼增益；同樣，在BER=2×10^-5時，相比RBP和NWRBP，ENWRBP的BER分別得到0.28 dB和0.16 dB的譯碼增益。

    通過圖5和圖6 ENWRBP譯碼性能的比較，可以觀察到，T=10時的曲線要低于T=5時的曲線，并且這種趨勢隨著SNR值的增大而增大。例如：如圖6所示，在FER=1×10^-4時，相比T=5，T=10得到0.8 dB的譯碼增益；同樣，在BER=1×10^-5時，相比T=5，T=10得到1.2 dB的譯碼增益。由此可見，通過增大變量節(jié)點初始LLR值置0嘗試次數(shù)，可進一步提高ENWRBP譯碼性能。

4 結論

    本文在NWRBP算法的基礎上介紹了一種增強譯碼算法ENWRBP(Enhanced NWRBP)。相比較NWRBP算法，該算法的譯碼性能優(yōu)于NWRBP，特別是SNR值稍大時尤為明顯。仿真表明，NWRBP在每次迭代過程中，更新次數(shù)少的變量節(jié)點，其本身或相鄰節(jié)點發(fā)生誤碼的概率高于其他的變量節(jié)點。ENWRBP譯碼算法針對這一點，多次找到更新次數(shù)最少的變量節(jié)點，然后對該節(jié)點的初始化值置0，并重新譯碼，從而提高了NWRBP算法譯碼性能。另外，本文提出的基于節(jié)點更新次數(shù)最小、置零初始化值的思路也可以運用于其他LDPC譯碼算法中。

參考文獻

[1] Li Hua，Zheng Linhua.Efficient puncturing scheme for irregular LDPC codes based on serial schedules[J].IEEE Communications Letters，2015，19(9)：1508-1511.

[2] 白寶明，孫成，陳佩瑤，等.信道編碼技術新進展[J].無線電通信技術，2016，42(6)：1-8.

[3] MACKAY D J C，NEAL R.Near Shannon limit performance of low density parity check codes[J].IEEE Electronics Letters，1998，33(6)：457-458.

[4] 鄭偉，馬曉越，趙成晨.一種改進的LDPC碼BP譯碼算法[J].河北大學學報(自然科學版)，2016，36(5)：547-553.

[5] 張福星，許生旺.一種改進的多元LDPC碼譯碼算法[J].無線通訊技術，2016，42(6)：56-81.

[6] GOLOV O，AMRANI O.Edge-based scheduled BP in LDPC codes[C].IEEE International Symposium on Information Theory，2007：2376-2380.

[7] SAEJOON K，KARAM K.Two-staged informed dynamic scheduling for sequential belief propagation decoding of LDPC codes[J].IEEE Communication Letters，2009，13(3)：193-195.

[8] LEE H C，UENG Y L，YEH S M，et al.Two informed dynamic scheduling strategies for iterative LDPC decoders[J].IEEE Transactions on Communications，2013，61(3)：886-896.

[9] CASADO A I V，GRIOT M，WESEL R D.LDPC decoders with informed dynamic scheduling[J].IEEE Transactions on Communications，2010，58(12)：3470-3479.

[10] Song Lingyan，Hou Shujuan.Improved decoding of LDPC codes by variable-to-check residual belief propagation[C].International Conference on Communications & Networking in China，2015：163-166.

[11] Liu Xingcheng，Zhang Yuanbin，Cui Ru.Variable-node-based dynamic scheduling strategy for belief-propagation decoding of LDPC codes[J].IEEE Communications Letters，2015，19(2)：147-150.

[12] Han Guojun，Liu Xingcheng.An efficient dynamic schedule for layered belief-propagation decoding of LDPC codes[J].IEEE Communications Letters，2009，13(13)：193-195.

[13] KSCHISCHANG F R，F(xiàn)REY B J，LOELIGER H A.Factor graphs and the sum-product algorithm[J].IEEE Transactions on Information Theory，2001，47(2)：498-519.

作者信息：

周  華1，2，3，翁少輝1，3，馮  姣1，3

(1.南京信息工程大學，江蘇 南京210044；2.江蘇省大氣環(huán)境與裝備技術協(xié)同創(chuàng)新中心，江蘇 南京210044；

3.江蘇省氣象探測與信息處理重點實驗室，江蘇 南京210044)