0 引言

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

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

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

1 LDPC碼的RBP和NWRBP譯碼算法

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

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

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

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

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

2 ENWRBP算法機制描述

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

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

3 仿真結果與討論

    本文中所有的仿真都是在二進制輸入加性高斯白噪聲(BI-AWGN)信道進行的。譯碼方式采用基于剩余度置信傳播(RBP)算法、基于校驗節點的剩余度置信傳播(NWRBP)算法,以及本文提出的基于校驗節點的改進剩余度置信傳播(ENERBP)算法，最大迭代次數設為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算法的譯碼曲線逐漸優于RBP算法，圖3中NWRBP算法和ENWRBP算法依然大致相同，直到SNR值為4.0 dB時，ENWRBP算法開始優于NWRBP算法，圖4中ENWRBP算法在所示SNR范圍內始終優于RBP算法和NWRBP算法，并且這種優勢隨著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的譯碼增益。由此可見，通過增大變量節點初始LLR值置0嘗試次數，可進一步提高ENWRBP譯碼性能。

4 結論

    本文在NWRBP算法的基礎上介紹了一種增強譯碼算法ENWRBP(Enhanced NWRBP)。相比較NWRBP算法，該算法的譯碼性能優于NWRBP，特別是SNR值稍大時尤為明顯。仿真表明，NWRBP在每次迭代過程中，更新次數少的變量節點，其本身或相鄰節點發生誤碼的概率高于其他的變量節點。ENWRBP譯碼算法針對這一點，多次找到更新次數最少的變量節點，然后對該節點的初始化值置0，并重新譯碼，從而提高了NWRBP算法譯碼性能。另外，本文提出的基于節點更新次數最小、置零初始化值的思路也可以運用于其他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，FREY 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.江蘇省大氣環境與裝備技術協同創新中心，江蘇 南京210044；

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