LDPC碼中一種基于節點殘余的BP譯碼算法*

王興成，王中訓，郭 棟，于心喬

（煙臺大學 光電信息科學技術學院，山東 煙臺 264005）

1 引言

低密度奇偶校驗（LDPC）碼[1-3]是性能接近香農極限的糾錯編碼，因而得到廣泛關注，對于無線通信有著至關重要的作用。在LDPC碼譯碼時，校驗節點與變量節點之間有大量的信息傳送，因此降低LDPC碼譯碼復雜度與譯碼器的功率消耗，關鍵在于減少信息傳送的運算量。

在眾多優秀的譯碼算法中，殘余信息的LDPC碼BP譯碼算法（RBP）[4]是一種有效動態調度的譯碼算法，在迭代次數較少情況下與無調度的譯碼算法相比譯碼速度較快，但誤碼率和復雜度較高。筆者研究的VC-RBP譯碼算法與RBP譯碼算法相比，具有優良的誤碼率性能，復雜度較低，同樣具有快速譯碼的性能，不同之處在于殘留信息的計算。RBP算法的殘余信息的計算在校驗節點傳向變量節點信息更新前后，而VC-RBP算法的殘余信息的計算在變量節點傳向校驗節點信息更新前后。

2 LDPC碼中的BP譯碼算法及其改進

2.1 BP譯碼算法[5]

消息傳遞算法的信道輸出符號集和譯碼過程中發送信息的符號集相同，都是實數集，也就是說采用連續性的消息時，適當地選擇信息映射函數，就能把人工智能中的置信傳播（BP）算法運用于LDPC碼，從而形成LDPC碼的現代譯碼方案。

該算法的主要思想在于利用接收到的軟信息在變量節點和校驗節點之間進行迭代運算，從而獲得最大的編碼增益，因此具有很好的性能。BP譯碼算法的迭代過程分為校驗節點的信息更新和變量節點的信息更新。如圖1所示，H為校驗矩陣，t為迭代次數，完成一次迭代過程時，按照“若校驗節點傳遞到變量節點的信息mc→v>0，則c＾=1，否則c＾=0”的規則進行譯碼判決。 在此迭代過程中，如果譯碼成功，譯碼過程立即結束而不是進行固定次數的迭代，有效地減少了算法的迭代次數，降低了運算復雜度。而且如果算法在預先限定的最大迭代次數tmax到達后仍未找到有效的譯碼結果，譯碼器將報錯，這時的譯碼錯誤為“可檢測的”。同時由于BP算法是一種并行算法，在硬件中的并行實現能夠極大地提高譯碼速度。

2.2 RBP譯碼算法[6]

圖1 BP譯碼算法流程圖

LDPC譯碼的置信傳播算法是通過變量節點和校驗節點之間的消息迭代來實現的。設一個碼長為N的LDPC 碼，碼字 V={v1，v2，v3，…，vN}表示一組信息節點{vj:j=1，2，3，…，N}，{ci:i=1，2，3，…，M}表示一組校驗節點，節點間傳遞的信息為m，mk為傳遞的第k個信息。任意的校驗節點ci與其相鄰的變量節點vj傳遞信息的方程為

式中：CvJ=ln（p（yj|vj=1）/p（yj|vj=0）），為變量節點 vj的對數似然比，yi是信號譯碼器的接收序列。

RBP譯碼算法是一種動態調度的譯碼算法[7]，節點開始迭代時的最大殘余隨著迭代次數的增加逐漸減小至零，因此殘余的值越大說明此消息還未被收斂，先處理這樣的消息會加速譯碼。對于消息mk來說，其殘余為

式中：fk（m）為變量節點k在更新后的對數似然比。

RBP算法可以概括為以下3個步驟：1）假設mci→vj的殘余最大，則首先對mci→vj進行更新，此時設置該信息殘余為零。 2）計算 mvj→ca的殘余 r（mvj→ca），此時 ca∈N（vj）ci。3）計算 mca→vb的殘余 r（mca→vb），此時 vb∈N（ca）vj，然后根據校驗節點傳向變量節點的信息更新前后的差異對將要更新的信息進行排序。

盡管RBP算法是一種有效的動態調度方案，由Vila casado等人應用到LDPC碼上，但在誤碼率性能和復雜度方面不甚理想。RBP算法因其貪婪特性[5]會產生新的錯誤，這在非動態的譯碼方案中不會出現。在復雜度方面，當一個校驗節點到變量節點更新時，mc→v不必重新計算信息量，因為在r（mc→v）確定時其值已經確定。另外，在譯碼算法最后，每個邊緣殘余被計算時，殘余信息序列Q都會被重新排序，這樣就增加了譯碼復雜度。

因此，RBP 譯碼算法流程為：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）計算 r（mc→v）和生成 Q；4）mci→vj為Q 的首次傳遞信息；5）得到mci→vj迭代傳遞；6）令 r（mvj→ci）=0，重新排序Q；7）獲得與變量節點j相連的除去i節點的校驗節點的集合 ca∈N（vj）ci；8）得到 mvj→ca迭代傳遞；9）獲得校驗節點j相連的除去i節點的變量節點集合vb∈N（ca）vj；10）計算 r（mca→vb），重新排序 Q；11）若c＾·HT≠0，返回步驟4）。

2.3 VC-RBP譯碼算法[6]

VC-RBP譯碼算法在貪婪特性方面要優于RBP譯碼算法，主要區別在于VC-RBP的殘余是根據變量節點傳向校驗節點更新信息前后的差異計算出來。與RBP譯碼算法相比，VC-RBP譯碼算法的程序少了一步。第一步，VC-RBP 選擇相應的邊緣最大值r（mvi→cj）并設置為零，然后更新所選邊緣連接的校驗節點。第二步，先更新mcj→va，va∈N（cj）vi；接著更新mva→cb，cb∈N（Va）cj，根據更新信息的差異計算出 r（mva→cb），與RBP相比可減少譯碼復雜度。

因此，VC-RBP 譯碼算法流程為：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）確認 r（mc→v）最大值；4）確認mvi→cj節點；5）設置 r（mvi→cj）=0；6）獲得 va∈N（cj）vi；7）得到mcj→va迭代傳遞；8）獲得 cb∈N（va）cj；9）得到 mva→cb迭代傳遞；10）計算 r（mva→cb）；11）若c＾·HT≠0，返回步驟 3）。

在糾錯性能方面，VC-RBP要優于RBP。RBP首先把信息傳遞給不太可靠的變量節點，因為包含最大殘余的信息僅僅基于一個校驗方程，這樣的貪婪特性會產生新的錯誤，而糾錯需要大量的信息更新。VC-RBP首先傳遞包含最大殘余的信息時是基于全部校驗方程的，通過更新以表示校驗方程的校驗節點和變量節點的信息，從而有效地解決了更新校驗節點時的差錯平底。

3 仿真結果

采用Matlab工具對提出的LDPC改進譯碼算法的性能進行了仿真驗證，采用IEEE802.16e標準設計的QCLDPC碼，在AWGN信道下碼長為1024，碼率為1/2，迭代次數為10的仿真結果如圖2所示。隨著信噪比的增大，RBP譯碼算法和VC-RBP譯碼算法均比傳統的BP譯碼算法性能優越。迭代次數為10的VC-RBP在誤碼率為10-4時，與RBP相比有0.28 dB的增益。

4 小結

研究了VC-RBP與RBP和一般的BP譯碼算法相比具有的優越性能。在同一信噪比的情況下，VC-RBP譯碼算法性能最優，使LDPC譯碼算法收斂得更快。

[1]GALLAGER R G.Low-density-parity-check codes[EB/OL].[2010-03-05].http：//www.rle.mit.edu/rgallager/documents/ldpc.pdf.

[2]IEEE802.16e-2005，IEEE standard for Local and me2tropolitan area networks，part 16：air interface for fixed and mobile broadband wireless access systems[S].2006.

[3]楊知行，林之初，王軍，等.準循環LDPC碼的半并行譯碼器設計[J].電視技術，2006，30（2）：24-26.

[4]ELIDAN G，MCGRAW I，KOLLER D.Residual belief propagation:informed scheduling for asynchronous message passing[C]//Proc.22 Conf.Uncertainty in Artificial Intelligence.Cambridge：[s.n.]，2006：165-173.

[5]MACKAY D J C，NEAL R M.Near Shannon limit performance of low density parity check codes[J].Electronics Letters，1996，32（18）：1645-1646.

[6]CASADO A I V，GRIOT M，WESEL R D.Improving LDPC decoders via informed dynamic scheduling[EB/OL].[2010-03-06].http：//www.ee.ucla.edu/～csl/files/publications/Improving_LDPC_Decoders_IT-W2007.pdf.

[7]CASADO A I V，GRIOT M，WESEL R D.Informed dynamic scheduling for belief-propagation decoding of LDPC codes[C]//Proc.IEEE ICC 2007.Glasgow，Scotland：IEEE Press，2007：208-213.