一種交疊的Shuffled-BP LDPC譯碼算法

范亞楠 王麗沖 姚秀娟 孟 新

?

一種交疊的Shuffled-BP LDPC譯碼算法

范亞楠*①②王麗沖①②姚秀娟①孟 新①

①(中國科學院國家空間科學中心 北京 100190)②(中國科學院大學 北京 100190)

Shuffled-BP(SBP) 譯碼算法是一種基于變量節點的串行消息傳遞譯碼算法，其收斂速度快于原有的置信度傳播譯碼算法，然而由于實際工程實現中的半并行化處理，其收斂速度和誤碼性能均有所降低。為了進一步提高SBP算法的性能，該文提出一種交疊的Shuffled-BP(Overlapped Shuffled-BP, OSBP)譯碼算法。該算法采用若干個相同的子譯碼器以不同的更新順序同時進行更新，對于每個變量節點，在每次迭代更新后選取最可靠的信息參與下一次迭代，以此提高迭代的收斂速度。理論分析和仿真實驗均表明，在不增加額外存儲空間的條件下，OSBP算法相比于SBP算法有著更優的誤碼性能以及更快的收斂速度。此外，提出的OSBP算法對于規則和不規則LDPC碼均有效。

LDPC碼；收斂速度；譯碼算法；Shuffled-BP；交疊的Shuffled-BP

1 引言

LDPC碼以其漸進香農限[1,2]的誤碼性能而被信道編碼界所廣泛關注。由于其校驗矩陣的稀疏性，其譯碼算法的空間復雜度較低，并且相比于Turbo碼有著更低的錯誤平臺。1962年，Gallager在其博士論文[3]里提出了置信度傳播(Belief-Propagation, BP)LDPC譯碼算法，BP算法是一種基于洪水消息傳遞機制的譯碼算法，其收斂速度慢，并且消耗的計算資源和存儲資源均非常巨大。為彌補BP算法的不足，研究人員開始研究基于串行消息傳遞機制的譯碼算法，例如文獻[4,5]中提出的分層譯碼算法以及文獻[6,7]中提出的Shuffled-BP(SBP)譯碼算法。在該類算法中，消息逐節點依次進行更新和傳遞，這樣使得在一次迭代中剛更新過的消息立刻參與到本次迭代的其他消息的更新中去，因而獲得了較BP算法近兩倍的收斂速度。另外，基于SISO的實現方式又節省了大量的存儲空間，同時降低了計算復雜度。

由于SBP算法串行更新的緣故，其譯碼延時比較大。為了降低譯碼延時，實際工程應用中一般需要進行半并行化處理，如文獻[8,9]中所做的那樣。然而并行處理后，各組中更新的信息并沒有被該組其他節點所利用，導致SBP算法的收斂速度和誤碼性能均有所降低。為了進一步提升SBP算法的性能，文獻[10]通過按變量節點度數遞減的順序進行更新，來加快SBP算法的收斂速度，但是該方法只適用于非規則LDPC碼，對于規則LDPC碼并沒有效果；文獻[11,12]引入了殘差幅度(Residual Magnitude, RM)的概念，每次迭代時選擇RM最大的節點進行更新，以此來提高SBP算法的收斂速度和誤碼性能，但是由于該算法每次迭代都要計算RM，計算復雜度相當巨大，在實際工程中并不適用。

鑒于此，本文針對SBP算法提出了一種交疊的Shuffled-BP(OSBP)算法，該算法充分利用SBP算法的特點，將若干個相同的子譯碼器以不同的順序同時進行譯碼。每次迭代后，保留更可靠的變量節點信息參與判決和下一次迭代，進而使得判決更可靠。最終提出的算法在不增加額外存儲空間的條件下，使得SBP算法的誤碼性能和收斂速度均有明顯的提升，并且該算法對于規則和非規則LDPC碼均有效。

本文以下的結構如下：第2節介紹SBP譯碼算法以及該算法的特點；第3節在第2節的基礎上引出了該文提出的交疊的Shuffled-BP算法，并詳細介紹了子譯碼器偏移量和更新順序的選取；第4節利用高斯近似的密度進化對OSBP算法的收斂性進行了理論分析；第5節分別對于規則和不規則LDPC碼給出了相應的仿真結果；第6節對全文進行了總結。

2 Shuffled-BP(SBP)算法的基本原理

Zhang和Fossorier在文獻[6]中提出的SBP算法是概念層面的描述，并沒有考慮其具體的實現方式。SBP算法在實際應用中是一種基于SISO的迭代譯碼算法，本文以此方式對SBP算法進行描述，以便于解釋后續本文的算法，同時這樣的描述也可以給實際工程實現提供理論依據。

下面給出SBP算法的具體步驟：

在實際工程實現中，SBP算法可以方便地進行并行處理：設并行度為，變量節點平均分成組，每組個節點，每組各節點并行更行，而不同組之間串行更新，此時在第1步中，對于，每個，以及，式(8)應變為

由于SBP算法是逐變量節點依次進行更新的，所以每列更新的時間不同。列更新的時間越晚，則有越多的更新后的信息參與到該列的更新中去，從而得到的變量節點信息更可靠。如果按升序的順序進行更新，則越大，對應的變量節點信息越可靠，錯誤率越低；相應地，如果按降序的順序進行更新，則越大，對應的變量節點信息越不可靠，錯誤率越高。

圖1表示了在信噪比為3.0 dB時，通過對10000幀(192,96)(3,6)規則LDPC碼編碼數據分別采用升序與降序SBP算法進行仿真，得到的不同比特位置的錯誤比特數。從圖中可以看出越晚更新的變量節點，節點的錯誤比特數越少，其對應的信息越可靠，錯誤率越低。如果將多個相同的子譯碼器以不同的節點順序同時進行迭代，每次迭代后，針對于每一個變量節點在各個子譯碼器中選取最可靠的信息進入到下一次迭代，從而提高判決的可靠性以及譯碼器的收斂速度。基于此，本文提出了交疊的Shuffled- BP算法。

3 交疊的Shuffled-BP(OSBP)譯碼算法

正如第2節分析的那樣，SBP算法中變量節點信息的可靠性隨更新時間增加而提升，為了充分利用可靠度更高的信息，利用多個子譯碼器以不同的更新順序同時進行譯碼。在每次迭代過程中，各子譯碼器生成并相互之間傳遞更可靠的信息，從而提高判決的正確率和譯碼收斂速度，這就是OSBP算法的基本思想。

圖1 采用不同更新順序的SBP算法下各比特位置的錯誤比特數

3.1 OSBP算法

從第2步可以看出，不同于SBP算法，OSBP算法在每次迭代后只保留了最可靠的變量節點信息參與下一次迭代，所以得到了更好的性能。另外在每次迭代后，只需存儲最可靠的信息，而可以方便地由得出，并不需要存儲每個子譯碼器的變量節點信息，因此相比于SBP算法而言，并不需要額外的存儲空間。

每個子譯碼器以不同的更新順序同時進行迭代，每個變量節點都被各子譯碼器在不同的時間進行更新。正如3.2節里圖2將要展示的那樣，各子譯碼器的更新交疊在一起，相互之間傳遞更可靠的信息，故這里將該算法稱之為交疊的Shuffled-BP算法。

與SBP算法一樣，在實際工程實現中OSBP算法也可以方便地進行并行處理：設并行度為，變量節點平均分成組，每組個節點，對于每個子譯碼器而言，每組各節點并行更新，而不同組之間串行更新，此時在第1步中，當時，對于每個子譯碼器，每個，以及，式(14)應變為

3.2最大化譯碼性能的更新順序選取

根據第2節的分析可知，越晚被更新的節點對應的錯誤率越低，所以不失一般性，這里將前向與后向更新順序的錯誤率表示為如式(20)，式(21)的一種線性關系：

由此可見，各個子譯碼器的更新順序直接影響OSBP算法的性能，為了最大化譯碼性能，將平均分成份，，并沿著變量節點等間隔地布置子譯碼器，每個等間隔點前后分別布置兩個子譯碼器，子譯碼器的個數。在等間隔點處，，兩個子譯碼器的偏移量分別為和，對應的更新方向分別為前向和后向更新，然后利用式(18)~式(21)就可以得出各子譯碼器的更新順序和錯誤率。

圖2表示了一次迭代中SBP算法與OSBP各子譯碼器更新過程的示意圖：縱軸表示錯誤率，橫軸表示節點位置。斜線上的箭頭指示更新的方向，按箭頭所指的方向進行更新，各斜線所對應橫坐標的位置即為各子譯碼器更新的順序。圖中設子譯碼器的個數，在OSBP算法在每次迭代過程中，當時，各子譯碼器開始存儲當前的信息，即對應于圖2(b)中的陰影部分；而SBP算法在每次迭代中存儲的信息對應于圖2(a)中的陰影部分，可見OSBP算法在每次迭代后錯誤率更低。

圖2 SBP算法與OSBP各子譯碼器更新過程對比示意圖

4 基于密度進化的收斂性分析

本節將采用高斯近似的密度進化理論，針對SBP和OSBP譯碼算法推導了其對應的消息均值進化，并基于該理論定量地分析了SBP算法和OSBP算法的收斂性。

密度進化(DE)是分析基于消息傳遞的迭代譯碼算法性能有效的理論工具，如果信道和譯碼算法均滿足對稱性條件，那么誤碼率與所傳輸的碼字無關，這樣可以假設傳輸碼字均為0，以大大減化DE算法的復雜度。然而即便如此，由于需要精確計算節點消息的概率密度，DE算法的計算量仍然非常巨大，文獻[14]提出了高斯近似的方法，將多維節點消息的DE簡化為1維均值的進化，大大降低了DE的計算量，并且由其計算出來的譯碼門限與精確的DE所得到的結果僅僅相差0.3%~1.2%，保證了分析的有效性。

不同于BP譯碼算法，在SBP算法下，節點的概率密度與比特位置有關。令和分別為第次迭代中對應于第個比特位置的變量消息密度和校驗消息密度的均值，則對于規則LDPC碼來說(其中與分別為變量節點與校驗節點的度數)，第次迭代時變量消息的均值進化與BP譯碼算法下的一致，表示為

參與校驗消息均值進化的變量消息均值的所有可能的組合數為

那么在SBP譯碼算法下，校驗消息均值的進化可以表示為

由SBP譯碼算法下的消息均值進化規則可以方便地得到OSBP算法的消息均值進化規則。由式(10)~式(16)可以看出，OSBP算法中變量消息均值的進化與SBP算法的一致，如式(22)所示，不同之處在于校驗消息均值的進化。由于在OSBP算法中，每次迭代時只保留了對應每個比特位置最可靠子譯碼器的輸出外信息，所以變量消息的均值進化需要加入如式(30)過程：

到SBP算法與OSBP算法下的消息均值進化。在SBP算法下，第次迭代過程中度數為的變量消息均值進化可以表示為

令

那么校驗消息的均值進化可以表示為

圖3描繪了通過密度進化分析所得到的SBP算法和OSBP算法在不同迭代次數下的誤比特率。圖3(a)采用碼率為1/2的(3,6)規則LDPC碼，信噪比為1.2 dB；圖3(b)采用碼率為1/2的非規則LDPC碼，最大變量節點度數為5，其度分布與文獻[15]中的一致，信噪比為0.9 dB。由圖3可知，無論對于規則還是非規則LDPC碼，OSBP算法的收斂速度均快于SBP算法，并且子譯碼器個數越大，OSBP算法的收斂速度越快；在相同的迭代次數下，OSBP算法的誤比特率低于SBP算法，并且誤比特率隨的增大而減小。

密度進化分析的前提是碼長無限長、校驗矩陣中的‘1’隨機分布，故其得到的具體的迭代次數對于實際有限長的LDPC碼來說是一個相對值，并不能反映實際所需的迭代次數。為了得到子譯碼器個數與譯碼延時的關系，這里將OSBP算法的迭代次數相對于SBP算法下的迭代次數進行歸一化：令表示子譯碼器個數為時OSBP算法所需要的迭代次數，表示SBP算法所需要的迭代次數，則OSBP算法的譯碼延時為

5 仿真結果及分析

為了驗證本文所提出OSBP算法的性能，本文以兩種碼率為1/2的LDPC碼為例：(1)文獻[16]中準循環構造算法構造的環長為8、碼長為192的(3,6)規則LDPC碼，這里稱之為C1碼；(2)文獻[15]中變量節點度分布為，并采用文獻[17]中改進的PEG算法構造的碼長為1024的非規則LDPC碼，這里稱之為C2碼。在AWGN和BPSK調制的條件下，采用蒙特卡洛仿方法，對OSBP算法與SBP算法的性能做了對比仿真實驗。

圖4分別表示了C1碼和C2碼在采用OSBP算法和SBP算法下的誤比特率。其中C1碼的信噪比為3.0 dB; C2碼的信噪比為2.0 dB; OSBP算法的子譯碼器個數分別取2, 4, 8。由圖4可知，在相同的迭代次數和信噪比的條件下，本文算法的誤比特率相比于SBP算法降低了一半以上，并且當增加時，誤比特率會進一步有小幅度的降低，且越大，降低的幅度越小。

圖5分別表示了C1碼和C2碼在采用兩種譯碼算法下的誤碼曲線。其中OSBP算法的子譯碼器個數為4。由圖5可以看出在相同的最大迭代次數下，相比于SBP算法，本文提出的OSBP算法有著更優的誤碼性能，最大迭代次數越少，這種優勢越明顯。對于C1碼而言，在誤比特率等于的條件下，誤碼性能提升了大約0.3 dB。對于C1碼和C2碼來說，當最大迭代次數分別大于5次和10次的條件下，本文提出的OSBP算法仍然保持有略微的優勢。

圖3通過密度進化分析得到的不同迭代次數下的誤比特率

圖4 OSBP算法與SBP算法?????圖5 OSBP算法與SBP?????圖6 OSBP算法與SBP算

在特定信噪比下的誤比特率?????算法誤碼性能的比較仿真?????法平均迭代次數的比較仿真

6 結束語

本文為了進一步提升Shuffled-BP(SBP)算法的性能提出了一種交疊的Shuffled-BP(OSBP)迭代譯碼算法，通過充分利用SBP算法中變量節點信息的可靠性隨更新時間增加而提升的特點，采用若干個相同的子譯碼器同時交疊地對LDPC碼進行更新迭代，相互之間生成并傳遞更可靠的信息，從而進一步提高SBP算法的收斂速度和誤碼性能。基于密度進化理論對提出的算法進行了分析，證明了OSBP算法的誤碼性能和收斂速度均優于SBP算法。仿真實驗表明，本文的算法對于規則LDPC碼和非規則LDPC碼均有效，在不增加額外存儲空間的條件下，OSBP算法的誤碼性能優于SBP，并且其誤比特率隨著子譯碼器個數的增加而降低，尤其在中高信噪比區間下，誤碼性能較SBP算法提升約1倍。除此之外，相比于SBP算法，OSBP算法有著更快的收斂速度，并且其收斂速度隨著碼長和子譯碼器個數的增加而增加，所以在實際工程應用中，OSBP算法可以帶來更大的編碼增益和更低的譯碼延時。

[1] SHANNON C E. A mathematical theory of communi- cation[J]., 2001, 5(1): 3-55.

[2] MACKAY D J C and NEAL R M. Near Shannon limit performance of low density parity check codes[J]., 1996, 32(18): 1645-1646.

[3] GALLAGER R G. Low-density parity-check codes[J]., 1962, 8(1): 21-28.

[4] HOCEVAR, D. A reduced complexity decoder architecture via layered decoding of LDPC codes[C]. IEEE Workshop on Signal Processing Systems (SIPS), Austin, TX, USA, 2004: 107-112.

[5] ZHANG Xinmiao and TAI Ying. High-speed multi-block-row layered decoding for Quasi-cyclic LDPC codes[C]. IEEE Global Conference on Signal and Information Processing (GlobalSIP), Atlanta, GA, USA, 2014: 11-14.

[6] ZHANG J and FOSSORIER M. Shuffled belief propagation decoding[C]. Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 2002, 1: 8-15.

[7] WU Sheng, JIANG Xiaobo, and NIE Zhenghua. Alternate iteration of shuffled belief propagation decoding[C]. International Conference on Communications and Mobile Computing (CMC), Shenzhen, China, 2010, 2: 278-281.

[8] LAOUINI N, BEN Hadj Slama L, and BOUALLEGUE A. An optimized min-sum variable node layering for LDPC decoding[C]. International Conference on Multimedia Computing and Systems (ICMCS), Marrakech, Morocco, 2014: 794-799.

[9] SUN Yang and CAVALLARO J R. VLSI architecture for layered decoding of QC-LDPC codes with high circulant weight[J].(), 2013, 21(10): 1960-1964.

[10] ASLAM C A, GUAN Yongliang, and CAI Kui. Improving the belief-propagation convergence of irregular LDPC codes using column-weight based scheduling[J]., 2015, 19(8): 1283-1286.

[11] LIU Xingcheng, ZHANG Yuanbin, and RU Cui. Variable-node-based dynamic scheduling strategy for belief-propagation decoding of LDPC codes[J]., 2015, 19(2): 147-150.

[12] LI Jia, YANG Gaigai, and ZHAO Zhiqiang. An improved-performance decoding algorithm of LDPC codes for layered decoding[C]. IEEE International Conference on Communication Problem-Solving (ICCP), Beijing, China, 2014: 318-321.

[13] HAGENAUER J, OFFER E, and PAPKE L. Iterative decoding of binary block and convolutional codes[J]., 1996, 42(2): 429-445.

[14] CHUNG Saeyoung, RICHARDSON T J, and URBANKE R L. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation[J]., 2001, 47(2): 657-670.

[15] RICHARDSON T J, SHOKROLLAHI M A, and URBANKE R L. Design of capacity-approaching irregular low-density parity-check codes[J]., 2001, 47(2): 619-637.

[16] ZHANG Yi and DA Xinyu. Construction of girth-eight QC-LDPC codes from arithmetic progression sequence with large column weight[J]., 2015, 51(16): 1257-1259.

[17] JIANG Xueqin, XIA Xianggen, and LEE Moonho. Efficient progressive edge-growth algorithm based on Chinese remainder rheorem[J]., 2014, 62(2): 442-451.

An Overlapped Shuffled-BP LDPC Decoding Algorithm

FAN Yanan①②WANG Lichong①②YAO Xiujuan①MENG Xin①

①(,,100190,)②(,100190,)

Shuffled-BP (SBP) decoding algorithm is a variable-node-based serial decoding algorithm, which converges faster than the original Belief-Propagation (BP) decoding algorithm. However, due to the semi-parallel processing, there is a decrease in terms of convergence speed and error performance. An Overlapped Shuffled-BP(OSBP) decoding algorithm is proposed to enhance further the performance of the Shuffled-BP algorithm. In this algorithm, more than one sub-decoders are used to execute simultaneously, every sub-decoder has different updating order from each other. Regarding each variable node, the most reliable messages are kept and used for the next iteration, thus a faster convergence can be provided. Both theoretical analysis and simulation results show that, compared with SBP algorithm, OSBP algorithm possesses a better error performance as well as a higher convergence speed and introduces no extra storage requirement. Moreover, the proposed algorithm is effective for both regular and irregular LDPC codes.

Low Density Parity Check (LDPC) code; Convergence speed; Decoding algorithm; Shuffled-BP; Overlapped Shuffled-BP

TN911.22

A

1009-5896(2016)11-2908-08

10.11999/JEIT151477

2015-12-29；改回日期：2016-06-03；

2016-07-19

范亞楠 fanyanan_99@163.com

中國科學院創新基金(CXJJ14S126)

CAS Innovation Foundation (CXJJ14S126)

范亞楠： 男，1991年生，博士生，研究方向為星間通信系統中的信道編譯碼技術.

王麗沖： 女，1990年生，碩士生，研究方向為分布式衛星組網建模與仿真.

姚秀娟： 女，1977年生，研究員，研究方向為衛星組網通信與模式識別技術.