段琳琳 王忠勇 王 瑋 高向川 肖 巖

?

低復雜度的自適應置信差分迭代譯碼算法

段琳琳*①②王忠勇①王 瑋①高向川①肖 巖①

①(鄭州大學信息工程學院 鄭州 450001)②(解放軍信息工程大學信息系統(tǒng)工程學院 鄭州 450001)

針對中短碼長的低密度奇偶校驗規(guī)則碼(Low Density Parity Check, LDPC)規(guī)則碼，該文采用消息更新規(guī)則改進和因子圖變換方法，提出一種低復雜度差分迭代譯碼算法。在置信傳播算法的基礎上，僅當變量節(jié)點的消息值振蕩時引入差分映射策略，得出一種選擇性的置信差分規(guī)則，自適應地調整校驗節(jié)點消息的歸一化系數(shù)，提高譯碼性能。同時，采用展開校驗節(jié)點的圖變換方法，將計算復雜度從隨節(jié)點度分布指數(shù)性增長降至線性增長。分別在高斯白噪聲信道和瑞利衰落信道下進行仿真實驗，結果表明該算法和基于圖變換的其他低復雜度譯碼算法相比，性能優(yōu)越且復雜度低，和對數(shù)似然比的置信傳播算法(LLR-BP)相比，高信噪比區(qū)域內的性能優(yōu)異，低信噪比區(qū)域內的計算復雜度明顯降低。

低密度奇偶校驗迭代譯碼算法；差分映射機制；因子圖變換；自適應歸一化系數(shù)

1 引言

基于因子圖[1]的置信傳播譯碼算法[2]具有計算并行化和延時短等優(yōu)點，碼長較長時性能可以逼近香農限，因此低密度奇偶校驗(Low Density Parity Check, LDPC)碼引起信道編碼界和通信領域學者的關注和研究熱潮。雖然長碼性能優(yōu)異，但實際應用中，在雙向實時通信或對延時要求較高的環(huán)境下，顯然不能滿足延時要求。此時更適合采用中短碼長的LDPC碼，加之極大規(guī)模集成電路硬件實現(xiàn)技術的支持，碼長度較短的規(guī)則LDPC碼已經(jīng)得到廣泛應用[3]。

在中短碼長的LDPC碼圖中存在短環(huán)、陷阱集和停止集[4,5]，這些因素會引發(fā)迭代譯碼過程中某些變量節(jié)點的消息值即對數(shù)似然比外信息值(extrinsic Logarithm Likelihood Ratio, ex-LLR)的振蕩現(xiàn)象[6]，譯碼算法容易陷入陷阱集，出現(xiàn)錯誤平層，使譯碼性能受到損失。針對上述問題，文獻[6]采用跟蹤振蕩現(xiàn)象和處理外信息值的方法對置信傳播算法進行改進，將當前迭代與前次迭代的外信息值相加，減少振蕩對譯碼性能的影響，所提出的算法和對數(shù)似然比的置信傳播(Logarithm Likelihood Ratio BP, LLR-BP)算法相比性能略有提高。文獻[7]側重于解決陷阱集的問題，在分治(Divide and Concur, DC)算法[8]中引入差分動態(tài)機制，改進變量節(jié)點處的消息更新規(guī)則，提出了差分映射置信傳播譯碼(Difference- Map Belief Propagation, DMBP)算法，它和置信傳播(Belief Pro pagation, BP)算法、DC算法相比性能有所提高。均勻重加權置信傳播(Uniformly ReWeighted Belief Propagation, URW-BP)算法[9]和變量因子出現(xiàn)概率置信傳播(Variable Factor Appearance Probability Belief Propagation, VFAP-BP)算法[10]通過改進因子圖中變量節(jié)點的消息更新規(guī)則和選取優(yōu)化參數(shù)來提高譯碼性能。文獻[11,12]在歸一化的最小和算法基礎上，根據(jù)迭代過程中校驗節(jié)點的狀態(tài)動態(tài)調整歸一化系數(shù)，提出自適應歸一化最小和算法，仿真結果表明，對于DVB-S2 LDPC長碼，這種算法和歸一化最小和算法(Min-Sum Algorithm, MSA)相比，該算法在增加少量計算復雜度的同時可提高性能。此外，還有采用多步驟量化消息[13]和期望傳播[14]等方法降低錯誤平層和提高譯碼性能。

譯碼迭代過程中，并不是所有變量節(jié)點的信息值都會發(fā)生振蕩。差分映射雖然是避免譯碼算法陷入陷阱集的一個有效策略，但如果對每個變量節(jié)點均使用差分映射更新消息，可能會因頻繁過度的糾正而產(chǎn)生某些錯誤的軟判決，并沒有合理地發(fā)揮差分映射的優(yōu)勢。此外在對數(shù)概率測度下采用和積規(guī)則更新校驗節(jié)點的消息，計算復雜度和節(jié)點度分布呈指數(shù)性增長關系，復雜度較高。因此本文提出一種低復雜的自適應置信差分傳播算法，在置信傳播算法的基礎上，僅在變量節(jié)點消息值發(fā)生振蕩時引入差分映射動態(tài)機制，進一步提高譯碼性能。同時，通過展開節(jié)點方法變換校驗節(jié)點部分的因子圖，借鑒歸一化方法推導出一種自適應歸一化的消息更新規(guī)則，復雜度和校驗節(jié)點度分布的增長呈線性關系，復雜度大大降低。

2 變換校驗節(jié)點因子圖和改進消息更新規(guī)則

和Tanner因子圖相比，Normal因子圖[14]減少節(jié)點個數(shù)的同時突出地描述變量之間的函數(shù)約束關系，有助于描述分治和DMBP算法中的節(jié)點消息“復制”與“統(tǒng)一”的方法[7,8]。本文采用Normal因子圖描述LDPC碼，為比較低復雜的自適應置信差分傳播算法和BP, DMBP等算法提供統(tǒng)一圖模型，如圖1所示。

圖1 LDPC碼的正規(guī)因子圖模型

如果定義函數(shù)運算

步驟1 更新前向和后向的內部消息

更新前向消息

同時，更新后向消息為

步驟2 更新校驗節(jié)點到變量節(jié)點的消息

步驟3 判決并處理校驗節(jié)點消息

3 改進變量節(jié)點的消息更新規(guī)則

LLR-BP算法[2]中更新變量節(jié)點到校驗節(jié)點的消息

也稱為BP規(guī)則，其中，變量節(jié)點的后驗信息為

差分映射置信傳播(DMBP)算法[7]中消息更新為

也稱為DMBP規(guī)則，其中，變量節(jié)點后驗信息為

在譯碼迭代過程中，振蕩現(xiàn)象只發(fā)生在某些變量節(jié)點處[6]。如果僅采用BP規(guī)則，則沒有考慮振蕩和陷阱集對譯碼性能影響。如果僅采用DMBP規(guī)則，則對所有節(jié)點引入差分方法，雖然可以解決陷阱集問題，但同時也增加了計算量，甚至過度糾錯會造成不必要的性能損失，從而減少譯碼性能提高的幅度。為進一步提高譯碼性能，本文從迭代過程中消息值的振蕩現(xiàn)象入手，根據(jù)對數(shù)概率消息值測度下變量節(jié)點狀態(tài)，選擇性地采用兩種規(guī)則更新變量節(jié)點消息，提出一種置信差分映射(Belief propagation and Difference-map, BD) 消息更新規(guī)則。僅當發(fā)生消息值振蕩時，選擇DMBP規(guī)則更新消息，否則仍保留BP規(guī)則。具體步驟為

步驟2 判斷并選擇更新規(guī)則：若

則用DMBP規(guī)則更新消息，也可以用式(18)和式(19)式得到的等價規(guī)則更新消息：

注意由式(16)和式(17)得到BP規(guī)則為

比較式(20)和式(21)可以看出，BP規(guī)則僅使用先驗信息和當前迭代校驗節(jié)點傳給變量節(jié)點的外信息更新變量消息。而DMBP規(guī)則聯(lián)合先驗信息、當前迭代和前次迭代消息，取最優(yōu)比例系數(shù)獲得性能增益[7]。文獻[7]中明確指出，分治算法中對所有信息比特信息之和取平均值。

表1 3種消息更新規(guī)則的復雜度比較

4 改進的迭代譯碼算法及復雜度分析

基于上述對圖與消息更新規(guī)則的改進，本文提出一種低復雜度的自適應置信差分迭代譯碼算法，(Adaptivly Normalized Low-Complexity Belief propagation and Difference-map, ANLC-BD)算法，具體步驟為：

不同于ANLC-BD算法，LLR-BP算法在步驟2中按照式(3)更新校驗節(jié)點消息，在步驟3中按照式(16)和式(17)更新變量節(jié)點消息。其他如低復雜度置信傳播(Low Complexity-Belief Propagation, LC-BP)算法、低復雜度均勻重加權置信傳播(Low Complexity-Uniformly ReWeighted belief propagation, LC-URW)算法、低復雜度差分映射置信傳播(Low Complexity-Difference Map Belief Propagation, LC-DMBP)算法和低復雜度置信差分(Low Complexity-Belief propagation and Difference-map, LC-BD)算法是指在步驟2中均采用圖變換方法，在步驟3中分別采用式(16)和式(17)的BP規(guī)則、URW-BP規(guī)則[9]、式(18)和式(19)的DMBP規(guī)則和本文提出的BD規(guī)則更新消息的譯碼算法。在LC-BP算法基礎上再執(zhí)行校驗節(jié)點消息處理步驟，則構成自適應歸一化的低復雜度置信傳播(Adaptivly Normalized Low-Complexity Belief Propagation, ANLC-BP)算法。

5 仿真

在仿真中，選用8PSK格雷映射方式，碼率為1/2的(1008,3,6)LDPC規(guī)則碼，在AWGN信道和瑞利衰落信道下，對所提出的ANLC-BD算法進行性能仿真，=0.85,=0.75/0.85[11],=0.445[7]。同時給出用低復雜度自適應歸一化規(guī)則改進的LLR-BP算法(稱為ANLC-BP算法)的誤碼率特性曲線。LC-URW中仍取=0.55[9], LC-DMBP中仍取=0.445[7]。設最大迭代次數(shù)為100次。

首先，從圖2中和圖3的誤碼率特性曲線可以看出，AWGN和瑞利衰落信道下，低信噪比區(qū)域內，ANLC-BD算法的性能均逼近LLR-BP算法。高信噪比區(qū)域內，AWGN信道下的ANLC-BD算法均優(yōu)于LLR-BP和BP算法，但和最大似然比譯碼算法(Maximum Likelihood Decoding, MLD)之間仍存在性能差異，瑞利衰落信道下的ANLC-BD算法和LLR-BP算法相比略有性能增益。和LC-BP算法相比，LC-URW和LC-DMBP依次提高譯碼性能。僅采用BD規(guī)則的LC-BD算法和僅處理校驗節(jié)點消息的ANLC-BP算法均可以進一步提高譯碼性能。ANLC-BD算法結合兩者優(yōu)勢，獲得是最大的性能增益。

綜合圖2至圖5的結果，在低信噪比區(qū)域，本文所提出的ANLC-BD算法和LLR-BP算法性能相當，復雜度降低；高信噪比區(qū)域內，復雜度相當，性能略有提高。在上述低復雜譯碼算法中，僅處理校驗節(jié)點消息的ANLC-BP算法和僅改進變量節(jié)點更新規(guī)則的LC-BD算法均提高譯碼性能，同時都可以減少實際總迭代次數(shù)，ANLC-BD算法結合兩者優(yōu)勢，獲得是最大的性能增益和最少的實際總迭代次數(shù)。

最后，在AWGN信道各信噪比下，以及瑞利衰落信道E/0=6.5 dB下，仿真本文所提算法取不同值時的性能，圖6結果表明，各種信噪比下均存在=0.445使性能最優(yōu)。

圖2 AWGN信道下，ANLC-BD算法和其他改進算法的性能比較

圖3 瑞利衰落信道下，ANLC-BD算法和其他改進算法的性能比較

圖4 AWGN信道下，ANLC-BD算法和其他改進算法的迭代次數(shù)比較

圖6 AWGN和瑞利衰落信道下，Z的不同取值對ANLC-BD算法性能的影響

6 結束語

本文采用因子圖中圖變換和規(guī)則改進兩類方法，提出一種低復雜度的自適應置信差分譯碼算法。和LLR-BP算法相比，兩種更新規(guī)則的引入實質上是進行了三方面的改進，包括校驗節(jié)點的圖變換和相應更新規(guī)則、處理校驗節(jié)點消息以及變量節(jié)點更新規(guī)則。上述改進方法的結合帶來優(yōu)勢有兩點，一是綜合圖變換方法可以降低每次迭代復雜度和后兩方面改進均可以減少實際總迭代次數(shù)的特點，降低了算法在低信噪比區(qū)域的整體計算復雜度。二是綜合了處理校驗節(jié)點信息和變量節(jié)點更新規(guī)則均能提高性能的特點，提高整體算法高信噪比區(qū)域的性能。仿真結果表明，在AWGN信道和瑞利衰落信道下，本文所提算法和置信傳播算法相比，低信噪比區(qū)域內性能相當，復雜度較低，高信噪?yún)^(qū)域內復雜度相當，性能優(yōu)越。同時性能明顯優(yōu)于低復雜度BP, DMBP和URW-BP譯碼算法。本文提出的方法可以擴展至長碼、多元或不規(guī)則碼等譯碼算法中。

[1] Loeliger H A. An introduction to factor graphs[J]., 2004, 21(1): 28-41.

[2] Chen Jinghu and Fossorier M P C. Near optimum universal belief propagation based decoding of low-density parity check codes[J]., 2002, 50(3): 406-414.

[3] Hu Zi-xia and Liu Hui. A low-complexity LDPC decoding algorithm for hierarchical broadcasting: design and implementation[J]., 2013, 62(4): 1843-1849.

[4] Laendner S and Milenkovic O. LDPC codes based on latin squares: cycle structure, stopping set, and trapping set analysis[J]., 2007, 55(2): 303-312.

[5] Milenkovic O, Soljanin E, and Whiting P. Asymptotic spectra of trapping sets in regular and irregular LDPC code ensembles[J]., 2007, 53(1): 39-55.

[6] Gounai S, Ohtsuki T, and Kaneko T. Modified belief propagation decoding algorithm for low-density parity check code based on oscillation[C]. Proceedings of the IEEE 63rd Vehicular Technology Conference,Melbourne vic, 2006, 3: 1467-1471.

[7] Yedidia J S, Wang Yige, and Draper S C. Divide and concur and difference-map BP decoders for LDPC codes[J]., 2011, 57(2): 786-802.

[8] Gravel S and Elser V. Divide and concur: a general approach to constraint satisfaction[J]., 2008, 78(3): 1-4.

[9] Wymeersch H, Penna F, and Savic V. Uniformly reweighted belief propagation for estimation and detection in wireless networks[J]., 2012, 11(4): 1587-1595.

[10] Liu Jing-jing and de Lamare R C. Low-latency reweighted belief propagation decoding for LDPC codes[J]., 2012, 16(10): 1660-1663.

[11] Wu Xiao-fu, Song Yue, Jiang Ming,.. Adaptive- normalized/ offset min-sum algorithm[J]., 2010, 14(7): 667-669.

[12] Fan Li-wen, Pan Chang-yong, Peng Ke-wu,.. Adaptive normalized min-sum algorithm for LDPC decoding[C]. 2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC), Sardinia, Italy, 2013: 1081-1084.

[13] Tolouei S and Banihashemi A H. Lowering the error floor of LDPC codes using multi-step quantization[J]., 2014, 18(1): 86-89.

[14] Loeliger H A, Dauwels J, Hu Jun-li,.. The factor graph approach to model-based signal processing[J]., 2007, 95(6): 1295-1322.

[15] Henk W. Iterative Receiver Design[M]. Cambridge: Cambridge University Press, 2007: 153-154.

段琳琳： 女，1974年生，博士生，研究方向為基于圖模型的無線通信信號處理.

王忠勇： 男，1965年生，教授，研究方向為無線通信、數(shù)字通信和嵌入式系統(tǒng).

王 瑋： 女，1974年生，博士生，研究方向為信號處理.

高向川： 男，1981年生，博士，研究方向為3G&4G無線通信、信號處理、干擾對齊技術.

肖 巖： 男，1978年生，博士生，研究方向為無線通信信號處理.

An Adaptive Belief Propagation Difference-map Iterative Decoding Algorithm with Low Complexity

Duan Lin-lin①②Wang Zhong-yong①Wang Wei①Gao Xiang-chuan①Xiao Yan①

①(,,450001,)②(,,450001,)

In this paper, an adaptive belief difference-map propagation algorithm with low complexity is proposed for short and middle length LDPC regular codes by modifying message update rules and transforming factor graph. To improve decoding performance, a new selective belief propagation difference-map message update rule is introduced by borrowing the difference-map strategy for variable node messages oscillation, and the normalized factor is adjusted adaptively. Meanwhile, the computational complexity exponential in the degree of check node is decreased into linear in degree by opening the check node. The simulation results illustrate that the proposed algorithm has better performance and lower complexity than other iterative decoding algorithms based on the modified factor graphs. Compared to the LLR-BP, it better performance at high/0and the computational complexity is apparently downgraded at low/0.

LDPC iterative decoding algorithm; Difference-Map (DM) strategy; Transforming factor graph; Adaptive normalized factor

TN911.23

A

1009-5896(2014)11-2640-06

10.3724/SP.J.1146.2014.00234

段琳琳 llduan@126.com

2014-02-24收到，2104-06-26改回

國家自然科學基金(61172086, 61201251)，國家自然科學基金聯(lián)合基金(U1204607)和博士后科研啟動基金(2011012)資助課題