張福星，許生旺，雷光雄

(1.北京跟蹤與通信技術(shù)研究所，北京 100094；2.中國電子科技集團公司第五十四研究所，河北 石家莊050081)

?

EMS譯碼算法的改進研究

張福星1，許生旺1，雷光雄2

(1.北京跟蹤與通信技術(shù)研究所，北京 100094；2.中國電子科技集團公司第五十四研究所，河北 石家莊050081)

多元LDPC碼具有優(yōu)異的性能，但其譯碼算法的復(fù)雜度很高。EMS算法通過截短迭代消息向量，縮小校驗方程的搜索空間，以一定的性能損失為代價，換取譯碼復(fù)雜度的降低。為了改進EMS算法，研究了EMS算法的截短規(guī)則和震蕩現(xiàn)象抑制措施，提出了新的截短規(guī)則和對震蕩現(xiàn)象的抑制方法。仿真結(jié)果表明，新的截短規(guī)則可以很好地對消息向量進行截短，新的震蕩抑制方法也可以獲得比經(jīng)典方法更好的效果，二者的結(jié)合可以在不損失譯碼性能的條件下，獲得譯碼復(fù)雜度的降低。

信道編碼;多元LDPC碼;EMS算法;算法改進

0　引言

LDPC碼于1963年由Gallager提出[1]。1998年Davey和Mackey[2]擴展和引出了二元LDPC碼的高階形式：多元LDPC碼。多元LDPC碼和二元LDPC碼都可以用校驗矩陣或因子圖來表示，它們主要區(qū)別在于：多元LDPC碼校驗矩陣中的非零元素取自有限域GF(q)(q>2)上的非零域元素，而二元校驗矩陣中的非零元素只能為1。

研究表明[3]，在衰落信道下多元LDPC碼的優(yōu)越性表現(xiàn)非常突出，其在碼字糾錯性上有2點優(yōu)勢：優(yōu)異的碼字糾錯性能和良好的抗突發(fā)錯誤性能。

雖然多元LDPC碼在性能上有明顯的優(yōu)勢，但是在LDPC碼的實用化中，目前仍是以二元LDPC碼為主。限制多元LDPC碼應(yīng)用的最大瓶頸是其譯碼算法的高復(fù)雜度。多元LDPC碼譯碼時每2個節(jié)點間傳遞的消息是q維的，隨著多元域階數(shù)q的增加，多元LDPC碼BP(Belief Propagation)譯碼算法復(fù)雜度以q2的規(guī)模增長[4]。當(dāng)q值很大時，整個譯碼過程所完成的計算量很大，利用傳統(tǒng)的方法幾乎無法做到硬件實現(xiàn)[5]。所以，多元LDPC碼的譯碼算法，尤其是復(fù)雜度降低的譯碼算法，成為多元LDPC碼研究的重點。

2007年D.Declercq和A.Voicila提出了擴展最小和算法[6](Extended MS，簡稱EMS算法)，通過將變量節(jié)點與校驗節(jié)點間傳遞的消息向量長度截短為Nm<

1　EMS譯碼算法

EMS算法的基本思想就是對變量節(jié)點和校驗節(jié)點之間來回傳遞的信息向量做截短處理，進而縮小搜索滿足校驗方程碼字的空間。若變量節(jié)點的度為dv，設(shè)

為該節(jié)點的輸入消息集合，

為此節(jié)點輸出消息的集合。則令下標(biāo)“pv”表示消息從置換節(jié)點傳遞給變量節(jié)點，而“vp”表示與之相反的方向。

為了減少運算量，EMS算法中的信息向量Vpv和Uvp按降序排列存儲了原來向量的前Nm(

EMS譯碼算法步驟如下[7]：

① 初始化

② 變量節(jié)點信息更新

③ 變量節(jié)點輸出消息的置換或重排

根據(jù)校驗矩陣H對變量節(jié)點的輸出信息進行置換或重排，即

βUpic[k]=hiβUvpi[k],k={0,1,…，Nm-1}。

式中的乘法運算是基于有限域GF(q)上進行的。

④ 校驗節(jié)點信息更新

⑤ 校驗節(jié)點輸出消息的置換或重排

根據(jù)校驗矩陣H對變量節(jié)點的輸出信息進行置換或重排，即

式中的乘法運算是基于有限域GF(q)上進行的。

2　改進思路

2.1截短規(guī)則

在EMS算法中，截短長度參數(shù)Nm和譯碼性能之間存在著矛盾，參數(shù)Nm影響著譯碼算法的復(fù)雜度。若參數(shù)Nm過小則會對性能造成較大損失，參數(shù)Nm過大則又使譯碼算法復(fù)雜度過高。為了調(diào)和譯碼復(fù)雜度和譯碼性能，需對Nm的選擇進行優(yōu)化。

最初Nm的選擇為固定值，稱為M-EMS[8]。隨后出現(xiàn)T-EMS[9]、D-EMS[10]、u-EMS[11]和A-EMS[12]等對Nm的選擇進行優(yōu)化的改進算法。它們的出發(fā)點主要為：利用可變的門限值選擇Nm或者在迭代中動態(tài)的改變Nm值。

消息向量中的值是置信度值，對消息向量的截短將導(dǎo)致性能的損失。因此，從譯碼算法的性能出發(fā)，希望在保持較低的譯碼復(fù)雜度的同時，在截短后的消息向量中保存盡可能多的信息?？梢远康挠嬎憬囟毯蟮南⑾蛄块L度，令原始消息向量為：

U0=[L(0)L(1)…L(q-1) ]，

截短后的消息向量為：

Us=[L(0)L(1)…L(Nm-1) ]，

則截短向量占全部向量的比例可以定義為：

式中，L(i)為降序排列的消息向量值；Z為截短的消息向量的長度；u表示在截短長度為Z時截短后保留的消息值占所有消息值和的比例。顯然，截短后損失的消息向量值應(yīng)該越小越好，即截短后保留消息值占用的比例越大越好。因此，可以引入新的截短規(guī)則

Nm{z∈Fq|u(z)≥u}。

對比例值u的選擇將直接的影響著消息向量截短后的長度Nm，而且只要選定了合適的u值，在譯碼算法迭代中就可以自動的選擇Nm值。

2.2譯碼震蕩的抑制

震蕩是部分對數(shù)域算法特有的性質(zhì)[13]，文獻[14]中對“ex-LLR(Extrinsic Log-likelihood ratio)值震蕩給出了明確定義”，即在相鄰2次迭代中，如果變量節(jié)點信息L(m←n)的符號發(fā)生變化，就稱該過程的ex-LLR值發(fā)生了一次震蕩。

EMS算法是對LLR-BP算法的改進，算法的變量節(jié)點更新過程與LLR-BP算法相一致，因此同樣可能存在震蕩現(xiàn)象。在震蕩較為嚴(yán)重的情況下，迭代多次后的譯碼結(jié)果甚至比迭代一次或幾次的結(jié)果包含的錯誤更多。

令Ls(m←n)和Ls-1(m←n)分別表示前后2次變量節(jié)點信息，當(dāng)sign(Ls(m←n))≠sign(Ls-1(m←n))時，發(fā)生振蕩。由于此時并不知道2次迭代的更新值中哪個是正確的，但可以肯定的是其中一個信息值必然是錯誤的。因此，可以通過多種方式將更新數(shù)值的幅度減小，降低震蕩對整個譯碼過程的影響程度。

現(xiàn)有研究有以下幾種對震蕩錯誤的抑制方法[13-15]：

Ls(m←n)=Ls(m←n)+Ls-1(m←n),

Ls(m←n)=λLs(m←n)+(1-λ)Ls-1(m←n),

這些抑制震蕩錯誤的方法都是將前后2次符號不一致的消息值加權(quán)疊加得到，可能會改變的消息值的符號。認(rèn)為迭代出的消息值的符號，不應(yīng)發(fā)生改變，為了抑制震蕩現(xiàn)象的影響，發(fā)生震蕩的消息值可以保持符號不變而只降低其幅值大小。即引入幅度削減因子γ對發(fā)生震蕩的消息值進行處理。

對于幅度衰減因子γ的取值，將其與消息向量的截短長度掛鉤。在截短消息向量長度較大時，對幅度做更輕程度的削減。具體可以將衰減因子取為：

γ1=Nm,γ2=q/Nm。

3　仿真結(jié)果

對提出的改進EMS算法進行仿真驗證，校驗矩陣H為MacKay隨機構(gòu)造方法構(gòu)造的400×700矩陣，碼率為3/7，仿真最大迭代次數(shù)為20，仿真停止條件為50個錯誤比特，信道條件為AWGN，調(diào)制方式選擇BPSK。

3.1截短規(guī)則

新的截短規(guī)則中截短后的消息長度與選定的占取比例參數(shù)直接相關(guān)。截短后的消息向量長度直接影響著譯碼的性能，根據(jù)占取比例的不同，截短消息長度會自動計算出。當(dāng)計算出的Nm值小于固定的Nm值時，會降低譯碼的復(fù)雜度，但同時也會造成一定的譯碼性能損失。

自動選擇Nm值的計算公式為：

選擇u=0.85、u=0.9和u=0.99三種參數(shù)與固定Nm值4種情況進行對比，4種情況不同信噪比下的截短長度對比如表1所示。

表1　3種情況下選擇出的截短長度對比

在這4種情況下的性能如圖1所示，可以看出，在u=0.85、u=0.9和u=0.99下性能都有所下降，這是因為與nm=8的固定情況相比，此時選擇出的Nm值更小、復(fù)雜度更低的緣故。對nm的選取是一個雙向的過程，只要性能在滿足需要的范圍內(nèi)即可。此時，只有u=0.99時自動選擇出的Nm值不會造成過大的性能損失，說明提出的新截短規(guī)則是可行的。根據(jù)仿真結(jié)果，本文在后續(xù)仿真中將u值設(shè)為0.99。

圖1　3種情況下的譯碼性能

3.2譯碼震蕩的抑制

圖2　震蕩抑制算法性能

可以看出，后3種對震蕩現(xiàn)象的抑制算法都能獲得性能上的改善。在這些算法中，確保迭代消息值符號不變的改進算法能獲得比經(jīng)典震蕩抑制算法更好的性能。當(dāng)λ=q/Nm時，獲得了4種情況下的最優(yōu)性能，與未進行震蕩抑制的EMS算法相比有0.15dB左右的優(yōu)勢。

3.3改進的EMS算法性能

消息向量截短長度的自動選擇有可能導(dǎo)致性能的下降，而對震蕩現(xiàn)象的遏制可以改善譯碼算法的性能。綜合2種改進思路，仿真二者共同作用下的譯碼算法。選取了單獨仿真中的2個最優(yōu)條件(u=0.99和λ=q/Nm)與原EMS算法進行對比，仿真結(jié)果如圖3所示。

圖3　改進后的EMS算法譯碼性能

由圖3可以看出，雖然自動選擇截短長度會使性能下降，但是在另一方面，震蕩的抑制處理所帶來的性能提升可以彌補這一部分的性能下降。所以改進的EMS譯碼算法與原EMS算法相比，在復(fù)雜度得到降低的條件下，性能并沒有明顯的惡化。

4　結(jié)束語

EMS算法是目前已發(fā)展的多元LDPC碼譯碼算法中復(fù)雜度最低的譯碼算法，對其的改進一直是多元LDPC碼譯碼研究的熱點。本文在經(jīng)典EMS譯碼算法的基礎(chǔ)上，分析研究了EMS算法的截短規(guī)則和震蕩現(xiàn)象，提出了新的截短規(guī)則和對震蕩現(xiàn)象的抑制方法，改進了EMS算法。仿真結(jié)果表明，新的截短規(guī)則可以很好地對消息向量進行截短，新的震蕩抑制方法也可以獲得比經(jīng)典方法更好的效果，兩者的結(jié)合更是可以在不損失譯碼性能的條件下，獲得譯碼復(fù)雜度的降低。

[1]GALLAGER R G.Low-Density Parity-Check Codes[M].Cambridge M A；MIT Press，1963.

[2]DAVEY D，MACKAY D.Low-density Parity Check Codes over GF(q)[J].IEEE Communications Letters，1998，2(6): 165-167.

[3]李丹，白寶明.多元LDPC碼與二元LDPC碼的性能比較[J].無線通信技術(shù)，2007，16(3): 1-6.

[4]WYMEERSCH H，STEENDAM H，MOENECLAEY M A.Computational Complexity and Quantization Effects of Decoding Algorithms for Non-binary LDPC Codes[C]∥IEEE International Conference on Speech and Signal Processing.Montreal: IEEE，2004: 669-672.

[5]張譽.多進制LDPC碼譯碼算法的研究[D].長沙：國防科學(xué)技術(shù)大學(xué)， 2011.

[6]VOICILA A，DECLERCQ D，VERDIER F，et al.Low-Complexity Decoding for Non-Binary LDPC Codes in High Order Fields[J].IEEE Transactions on Communications，2010，58(5):1 365-1 375.

[7]史治平.多元LDPC碼及其在無線通信中的應(yīng)用[M].北京：國防工業(yè)出版社，2012.

[8]BOUTILLON E，CANENCIA L.Bubble Check：A Simplified Algorithm for Elementary Check Node Processing in Extended Min-sum Non-binary LDPC Decoders[J].Elect.Letter，2010,46(9):633-634.

[9]LI E，DECLERCQ D，GUNNAM K.Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure[J].IEEE Transactions on Communications，2013，61(7):2 600-2 611.

[10]林偉，白寶明，王雪鵬.多元LDPC碼的動態(tài)擴展最小和譯碼算法[J].西安電子科技大學(xué)學(xué)報(自然科學(xué)版),2012,39(2):59-65.

[11]ZHAO Shang-cheng，LU Zhi-fei，MA Xiao，et al.A Variant of the EMS Decoding Algorithm for Nonbinary LDPC Codes[J].IEEE Communications Letters，2013,17(8):1 640-1 643.

[12]GUAN X ，F(xiàn)EI Y.Adaptive Extended Min-Sum Algorithm for Nonbinary LDPC Decoding[C]∥USA:IEEE Globecom Proceedings,2011.

[13]DI C，PROIETTI D，TELATAR I E,et al.Finite-length Analysis of Low-Density Parity Check Codes on the Binary Erasure Channel[J].IEEE Transactions on Information Theory，2002，48(6) :1 570-1 579.

[14]LECHNER G，SAYIR J.On The Convergence of Log-Likelihood Values in Iterative Decoding[C]∥Germany:Proceedings of Mini-Workshop on Topics in Information Theory，2002:1-4.

[15]周偉.減少振蕩的改進多進制LDPC碼譯碼方法[J].北京郵電大學(xué)學(xué)報，2008，31(1)：45-50.

張福星男，(1992—)，碩士研究生。主要研究方向：信道編碼。

許生旺男,(1964—)，研究員。主要研究方向：圖像通信。

Research on Modified EMS Decoding Algorithm

ZHANG Fu-xing1，XU Sheng-wang1，LEI Guang-xiong2

(1.BeijingInstituteofTrackingandTelecommunicationTechnology,Beijing100094,China;2.The54thResearchInstituteofCETC，ShijiazhuangHebei050081,China)

Non-binary LDPC codes have great performance，but their complexity of decoding algorithm is also high.Extended-MS decoding algorithm can achieve decrease in complexity at the cost of performance.To find better decoding algorithm，the message truncation rules and the method to resist shock in ex-LLR are researched，and a new truncation rule as well as a new method to resist shock phenomenon are proposed.Simulation result shows that the new truncation rule works well in shortening message，and the proposed method of resisting shock achieves better performance than traditional methods.

channel coding；non-binary LDPC codes；EMS algorithm；algorithm modification

10.3969/j.issn.1003-3106.2016.10.05

2016-06-15

TN911.22

A

1003-3106(2016)10-0020-04

引用格式：張福星，許生旺，雷光雄.EMS譯碼算法的改進研究[J].無線電工程,2016,46(10):20-23.