多進制低密度奇偶校驗碼的擴展最小和譯碼算法研究

龐 臣，徐家品

（四川大學(xué) 電子信息學(xué)院，四川 成都 610065）

低密度奇偶校驗碼LDPC（Low Density Parity Check）是目前信道編碼領(lǐng)域公認的性能優(yōu)異，形式簡單，應(yīng)用前景廣闊的一種好的線性分組碼。LDPC碼的性能最逼近香農(nóng)限，因此被認為是未來通信領(lǐng)域中最具競爭力的信道編碼。自從1962年GALLAGER R G[1]博士在其學(xué)位論文中首次提出LDPC碼的相關(guān)概念，并用當時條件局限的方法證明了其優(yōu)異的糾錯性能之后，學(xué)術(shù)界就展開了針對LDPC的卓識有效的研究，并取得了極大的成果。至20世紀末，二進制LDPC碼已經(jīng)成為了非常成熟的信道編碼。除了理論方面取得了巨大成就，二進制LDPC在應(yīng)用領(lǐng)域更是大放異彩。歐洲通信標準委員會（ETSI）推出的DVB-S2標準中，信道編碼已經(jīng)采用LDPC碼。2010年10月10日，清華大學(xué)研制的低密度奇偶校驗碼遙測信道編碼試驗按計劃實施，“嫦娥二號”衛(wèi)星上LDPC編碼器以及喀什測控站、青島測控站LDPC遙測譯碼終端狀態(tài)良好、運行正常，遙測數(shù)據(jù)接收解調(diào)正常，試驗取得成功。此次試驗成功是LDPC信道編碼技術(shù)首次應(yīng)用于我國航天領(lǐng)域。LDPC碼優(yōu)異性能成為未來第四代（4G）移動通信系統(tǒng)最強有競爭力的候選標準之一。

1998年，DAVEY M C 和 MACKAY D J C[2]提出了基于 GF（q）域的 LDPC碼，由此開啟了 LDPC碼研究的一個新領(lǐng)域。定義在GF（q）上的多進制LDPC碼的雙向圖與二進制的相似，但變量節(jié)點有q（q=2b）個可能取值，校驗節(jié)點的約束限制也比二進制檢驗節(jié)點更復(fù)雜。在原信道不變的情況下，多進制的一個符號需要b個二進制比特。相比之下，無論是在計算復(fù)雜度，還是存儲容量及傳輸占用時間等方面，多進制LDPC碼都比二進制LDPC碼有更大的難度。盡管如此，由于其具有無可比擬的特性，多進制的研究都是極有理論和工程意義的。

本文簡要介紹多進制LDPC碼的幾種常見譯碼方法，分析各種方法的利弊，并利用多種形式重點介紹擴展最小和算法。

1 常見譯碼算法

LDPC碼有很多種譯碼方法。根據(jù)消息迭代過程中傳送消息的形式不同，可以將LDPC碼的譯碼方法分為硬判決譯碼和軟判決譯碼兩種。硬判決譯碼設(shè)定閾值來判斷輸出，軟判決譯碼通過最大后驗概率信息決定可能的信源值。硬判決譯碼計算簡單，但是誤碼率高；軟判決譯碼計算復(fù)雜，但是性能優(yōu)異。實踐中，傾向于選擇軟判決譯碼。目前，多進制LDPC碼的軟判決譯碼方法主要有信度傳播BP（Belief Propagation）算法、最小和MS（Min-Sum）算法、Normalized BP-based算法以及 LP算法。在此介紹前兩種算法。

信度傳播算法是由MACKAY P J C和NEAL R M[3]共同提出的一種迭代譯碼算法，簡稱BP算法。BP算法迭代過程如圖1所示。BP算法的核心思想在于利用接收到的軟信息在變量節(jié)點和校驗節(jié)點之間進行迭代運算，從而獲得最大編碼增益。該算法在迭代過程中會對結(jié)果作出判決。如果譯碼達到預(yù)定標準，譯碼計算立即結(jié)束而不再繼續(xù)進行固定次數(shù)的迭代，大大節(jié)省了譯碼時間，降低了運算復(fù)雜度。而若算法在到達預(yù)先限定的最大迭代次數(shù)后仍未找到有效的譯碼結(jié)果，譯碼器將宣告譯碼失敗。BP算法是一種并行譯碼算法，在硬件中的并行實現(xiàn)能夠極大地提高譯碼速度。LDPC碼利用BP譯碼算法能夠得到很好的譯碼性能，但是由于大量的乘法運算，采用BP算法的硬件復(fù)雜性較高。

圖1 BP算法迭代譯碼過程

最小和譯碼算法是由WYMEERSCH H[4]等人根據(jù)BP譯碼算法提出的一種對數(shù)域BP算法，簡稱MS算法。其基本思想與BP算法無異，只是在概率信息的表示形式上采用對數(shù)似然比，將BP算法中的諸多乘法運算轉(zhuǎn)換為對數(shù)域上的加法運算，大大降低了運算復(fù)雜度、減少了運行時間且不需要對信道噪聲進行估計，但其性能也有一定程度的降低。

上述各譯碼雖然在不同的時期不同的應(yīng)用點各自具有很大優(yōu)勢，但復(fù)雜度和實現(xiàn)難度依然很高，研究人員仍然在不斷改進和創(chuàng)新譯碼工作，推動著LDPC學(xué)科整體進展。

2 EMS算法

2007年，DECLERCQ D和FOSSORIER M[5]提出一種擴展最小和 EMS（Extended Min-Sum）算法，簡稱 EMS算法。該算法在最小和譯碼算法基礎(chǔ)上，提出一種縮短傳遞對數(shù)似然比概率信息數(shù)量的譯碼方法，大大降低了計算復(fù)雜度，在現(xiàn)有多進制LDPC碼譯碼算法中受到推崇。

假設(shè)經(jīng)過信道傳輸后在信宿端收到的對數(shù)似然比LLR消息向量是：

其中，

LV表示變量V中符號 αk的對數(shù)似然值，而P（αk）表示其概率測度值。

EMS算法首先將LV按照降序排列，然后順次截取LV中LLR值最大的項，得到處理后的消息向量U，LLR最大值即是U[1]，最小值是U[nm]。用Uq表示向量U對應(yīng)的GF（q）元素值，用γU=U[nm]-δ表示其余域元素對應(yīng)的似然值，其中δ是一個經(jīng)過優(yōu)化的固定偏移值。

例如：GF（8），nm=4

某變量節(jié)點接收到的LLR值為：

降序排列后：

對應(yīng)的 GF（8）元素值為：

截取到的前nm個LLR組成的向量U為：

截取信息后對應(yīng)的 GF（8）元素向量Uq為：

剩余域元素對應(yīng)的似然值γU為：

記UVC變量為節(jié)點V向校驗節(jié)點C傳遞的消息向量，UCV為校驗節(jié)點C向變量節(jié)點V傳遞的消息向量。EMS具體步驟如下：

（1）初始化（Initialization）

將UVC初始化為信道初始消息向量LV中最大的nm項。

（2）置換步驟（Permutation Step）：有限域元素順序通過置換重新排列

將各項與該置換節(jié)點的 GF（q）域元素相乘，從而完成對消息向量的置換，如圖2所示。

圖2 置換步驟示意圖

其中，實心矩形為置換節(jié)點，置換節(jié)點左邊箭頭上實心圓形代表階段后的LLR值對應(yīng)的GF（q）值，同理，右邊為置換后GF（q）值，手繪曲線箭頭所指為實際置換過程。

（3）橫向步驟（Horizontal Step）：檢驗節(jié)點更新

采用前向后向算法，將度為dc的校驗節(jié)點更新分解為2（dc-2）個校驗節(jié)點基本步驟。記校驗節(jié)點基本步驟的輸入消息向量為V和I，輸出消息向量為U，則對應(yīng)的符號索引向量分別為Vq、Iq和Uq。

（4）逆置換步驟（Reverse Permutation Step）：逆置換元素順序

（5）縱向步驟（Vertical step）：變量節(jié)點更新

采用前向后向算法，將度為dv的變量節(jié)點更新分解為2（dv-2）個變量節(jié)點基本步驟。記變量節(jié)點基本步驟的輸入消息向量為和，輸出消息向量為，其對應(yīng)的有限域值為定義長度為 2nm的向量 Y=[Y[0]，Y[1]，…Y[2nm-1]]，

其中，

輸出消息向量則由Y中最大的nm項按降序排列得到。

其過程如圖3所示。其中，黑色實心圓代表LLR值，空心圓代表對應(yīng)的GF（q）值。該變量節(jié)點度為dv，故有dv-1個輸入信息，經(jīng)過如上計算規(guī)則計算以后又恢復(fù)出q個值，再重新降序排列，截斷后在下一次循環(huán)迭代中初始化（若有可能）。

圖3 變量節(jié)點更新過程

（6）將變量V判決為消息符號索引向量Uq首項，校驗方程滿足或到達最大迭代次數(shù)則結(jié)束譯碼，否則返回步驟（2）。

隨后，VOICILA A等人[6]從實現(xiàn)角度對EMS算法進行了改進，將譯碼的實數(shù)加法運算復(fù)雜度進一步下降。如今，譯碼算法界眾多研究人員依然致力于對此算法的研究，希望有所突破。

當前，EMS在多進制LDPC碼譯碼算法中具有舉足輕重的地位，所有最新的研究成果均是圍繞此算法進行的改進和實現(xiàn)。無論誰想要在多進制LDPC譯碼算法上有所作為，都必須深刻研究EMS算法。由此可見，EMS算法的影響力有多么泛和深刻。

3 LDPC研究方向

當前，對LDPC碼的研究主要集中在檢驗矩陣的構(gòu)造、譯碼算法的優(yōu)化、性能分析和改進以及在實際系統(tǒng)中的應(yīng)用4個方面。即便如此，LDPC仍然有許多研究方向。

（1）多進制LDPC碼的校驗矩陣的構(gòu)造方法依然存在很大的難度。現(xiàn)有眾多方法應(yīng)用范圍過于狹窄，往往是滿足了一方面的要求，而在其他地方則差強人意。無論是結(jié)構(gòu)化構(gòu)造還是隨機構(gòu)造，對于硬件實現(xiàn)總有不理想之處。追求完善、系統(tǒng)的檢驗矩陣的構(gòu)造方法是學(xué)術(shù)界的動力。

（2）多進制 LDPC碼的譯碼方法對于 EMS算法依賴過于嚴重，人們的認知眼界和研究思路很難從中跳出，長期以往，很難有大的突破和創(chuàng)新。如何能夠?qū)⒆g碼復(fù)雜度降下來，讓性能提升，依然是永恒的愿景。

（3）多進制 LDPC編碼系統(tǒng)的聯(lián)合優(yōu)化設(shè)計，將編碼技術(shù)與調(diào)制技術(shù)、空時編碼技術(shù)、OFDM技術(shù)結(jié)合進行性能優(yōu)化是當前及將來的發(fā)展方向之一。

（4）盡快將更多的研究成果轉(zhuǎn)化為實際應(yīng)用，諸如深空衛(wèi)星通信、第四代（4G）移動通信系統(tǒng)及深海通信等。

本文介紹了多進制LDPC常見的兩種譯碼算法，然后依據(jù)原算法以及個人的理解，利用圖解的方式重點分析了EMS算法的具體步驟以及需要注意的問題。通過分析，就能夠理解EMS在存儲和計算復(fù)雜度中較其他算法具有明顯優(yōu)勢。最后對多進制LDPC碼的研究方向進行了簡要分析和預(yù)測。

[1]GALLAGER R G.Low-densityparity-checkcodes[D].Cambridge， Massachusetts： M.I.T.Press， 1963.

[2]DAVEY M C，MACKAY D J C.Low density parity check codes over GF（q）[C].Information Theory Workshop， 1998：70-71.

[3]MACKAY D JC， NEALR M．NearShannonlimit performance of low density parity check codes[J]．Electronic Letters，1996，32（18）.

[4]WYMEERSCHH， STEENDAMH， MOENECLAEYM.Log-domain decoding of LDPC codes over GF（q）[C].2004 IEEE International Conference on Communications，2004（2）：772-776.

[5] DECLERCQ D，F(xiàn)OSSORIER M.Decoding algorithms for nonbinary LDPC codes over GF（q）[J].IEEE Transactions on Communication， 2007，55（4）：633-643.

[6]VOICILA A， DECLERCQ D， VERDIER F， et al.Lowcomplexity decoding for non-binary LDPC codes in high orderfields[J].IEEE Transactions on Communication，2010，58（5）：365-1375.

[7]林偉.多元LDPC碼：設(shè)計、構(gòu)造與譯碼[D].西安：西安電子科技大學(xué)，2012.

[8]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用[M].北京：人民郵電出版社，2008.