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

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

1 引言

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

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

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

2.1 BP譯碼算法[5]

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

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

2.2 RBP譯碼算法[6]

圖1 BP譯碼算法流程圖

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

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

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

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

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

盡管RBP算法是一種有效的動態(tài)調(diào)度方案，由Vila casado等人應用到LDPC碼上，但在誤碼率性能和復雜度方面不甚理想。RBP算法因其貪婪特性[5]會產(chǎn)生新的錯誤，這在非動態(tài)的譯碼方案中不會出現(xiàn)。在復雜度方面，當一個校驗節(jié)點到變量節(jié)點更新時，mc→v不必重新計算信息量，因為在r（mc→v）確定時其值已經(jīng)確定。另外，在譯碼算法最后，每個邊緣殘余被計算時，殘余信息序列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）獲得與變量節(jié)點j相連的除去i節(jié)點的校驗節(jié)點的集合 ca∈N（vj）ci；8）得到 mvj→ca迭代傳遞；9）獲得校驗節(jié)點j相連的除去i節(jié)點的變量節(jié)點集合vb∈N（ca）vj；10）計算 r（mca→vb），重新排序 Q；11）若c＾·HT≠0，返回步驟4）。

2.3 VC-RBP譯碼算法[6]

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

因此，VC-RBP 譯碼算法流程為：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）確認 r（mc→v）最大值；4）確認mvi→cj節(jié)點；5）設(shè)置 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要優(yōu)于RBP。RBP首先把信息傳遞給不太可靠的變量節(jié)點，因為包含最大殘余的信息僅僅基于一個校驗方程，這樣的貪婪特性會產(chǎn)生新的錯誤，而糾錯需要大量的信息更新。VC-RBP首先傳遞包含最大殘余的信息時是基于全部校驗方程的，通過更新以表示校驗方程的校驗節(jié)點和變量節(jié)點的信息，從而有效地解決了更新校驗節(jié)點時的差錯平底。

3 仿真結(jié)果

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

4 小結(jié)

研究了VC-RBP與RBP和一般的BP譯碼算法相比具有的優(yōu)越性能。在同一信噪比的情況下，VC-RBP譯碼算法性能最優(yōu)，使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]楊知行，林之初，王軍，等.準循環(huán)LDPC碼的半并行譯碼器設(shè)計[J].電視技術(shù)，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.