低復(fù)雜度的自適應(yīng)置信差分迭代譯碼算法

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

?

低復(fù)雜度的自適應(yīng)置信差分迭代譯碼算法

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

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

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

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

1 引言

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

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

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

2 變換校驗(yàn)節(jié)點(diǎn)因子圖和改進(jìn)消息更新規(guī)則

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

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

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

步驟1 更新前向和后向的內(nèi)部消息

更新前向消息

同時(shí)，更新后向消息為

步驟2 更新校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)的消息

步驟3 判決并處理校驗(yàn)節(jié)點(diǎn)消息

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

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

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

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

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

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

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

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

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

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

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

4 改進(jìn)的迭代譯碼算法及復(fù)雜度分析

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

不同于ANLC-BD算法，LLR-BP算法在步驟2中按照式(3)更新校驗(yàn)節(jié)點(diǎn)消息，在步驟3中按照式(16)和式(17)更新變量節(jié)點(diǎn)消息。其他如低復(fù)雜度置信傳播(Low Complexity-Belief Propagation, LC-BP)算法、低復(fù)雜度均勻重加權(quán)置信傳播(Low Complexity-Uniformly ReWeighted belief propagation, LC-URW)算法、低復(fù)雜度差分映射置信傳播(Low Complexity-Difference Map Belief Propagation, LC-DMBP)算法和低復(fù)雜度置信差分(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算法基礎(chǔ)上再執(zhí)行校驗(yàn)節(jié)點(diǎn)消息處理步驟，則構(gòu)成自適應(yīng)歸一化的低復(fù)雜度置信傳播(Adaptivly Normalized Low-Complexity Belief Propagation, ANLC-BP)算法。

5 仿真

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

首先，從圖2中和圖3的誤碼率特性曲線可以看出，AWGN和瑞利衰落信道下，低信噪比區(qū)域內(nèi)，ANLC-BD算法的性能均逼近LLR-BP算法。高信噪比區(qū)域內(nèi)，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算法和僅處理校驗(yàn)節(jié)點(diǎn)消息的ANLC-BP算法均可以進(jìn)一步提高譯碼性能。ANLC-BD算法結(jié)合兩者優(yōu)勢，獲得是最大的性能增益。

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

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

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

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

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

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

6 結(jié)束語

本文采用因子圖中圖變換和規(guī)則改進(jìn)兩類方法，提出一種低復(fù)雜度的自適應(yīng)置信差分譯碼算法。和LLR-BP算法相比，兩種更新規(guī)則的引入實(shí)質(zhì)上是進(jìn)行了三方面的改進(jìn)，包括校驗(yàn)節(jié)點(diǎn)的圖變換和相應(yīng)更新規(guī)則、處理校驗(yàn)節(jié)點(diǎn)消息以及變量節(jié)點(diǎn)更新規(guī)則。上述改進(jìn)方法的結(jié)合帶來優(yōu)勢有兩點(diǎn)，一是綜合圖變換方法可以降低每次迭代復(fù)雜度和后兩方面改進(jìn)均可以減少實(shí)際總迭代次數(shù)的特點(diǎn)，降低了算法在低信噪比區(qū)域的整體計(jì)算復(fù)雜度。二是綜合了處理校驗(yàn)節(jié)點(diǎn)信息和變量節(jié)點(diǎn)更新規(guī)則均能提高性能的特點(diǎn)，提高整體算法高信噪比區(qū)域的性能。仿真結(jié)果表明，在AWGN信道和瑞利衰落信道下，本文所提算法和置信傳播算法相比，低信噪比區(qū)域內(nèi)性能相當(dāng)，復(fù)雜度較低，高信噪?yún)^(qū)域內(nèi)復(fù)雜度相當(dāng)，性能優(yōu)越。同時(shí)性能明顯優(yōu)于低復(fù)雜度BP, DMBP和URW-BP譯碼算法。本文提出的方法可以擴(kuò)展至長碼、多元或不規(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年生，博士生，研究方向?yàn)榛趫D模型的無線通信信號(hào)處理.

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

王 瑋： 女，1974年生，博士生，研究方向?yàn)樾盘?hào)處理.

高向川： 男，1981年生，博士，研究方向?yàn)?G&4G無線通信、信號(hào)處理、干擾對(duì)齊技術(shù).

肖 巖： 男，1978年生，博士生，研究方向?yàn)闊o線通信信號(hào)處理.

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改回

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