多進(jìn)制低密度奇偶校驗(yàn)碼的擴(kuò)展最小和譯碼算法研究

龐 臣，徐家品

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

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

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

本文簡(jiǎn)要介紹多進(jìn)制LDPC碼的幾種常見譯碼方法，分析各種方法的利弊，并利用多種形式重點(diǎn)介紹擴(kuò)展最小和算法。

1 常見譯碼算法

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

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

圖1 BP算法迭代譯碼過(guò)程

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

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

2 EMS算法

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

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

其中，

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

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

例如：GF（8），nm=4

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

降序排列后：

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

截取到的前nm個(gè)LLR組成的向量U為：

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

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

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

（1）初始化（Initialization）

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

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

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

圖2 置換步驟示意圖

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

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

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

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

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

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

其中，

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

其過(guò)程如圖3所示。其中，黑色實(shí)心圓代表LLR值，空心圓代表對(duì)應(yīng)的GF（q）值。該變量節(jié)點(diǎn)度為dv，故有dv-1個(gè)輸入信息，經(jīng)過(guò)如上計(jì)算規(guī)則計(jì)算以后又恢復(fù)出q個(gè)值，再重新降序排列，截?cái)嗪笤谙乱淮窝h(huán)迭代中初始化（若有可能）。

圖3 變量節(jié)點(diǎn)更新過(guò)程

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

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

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

3 LDPC研究方向

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

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

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

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

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

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

[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è)計(jì)、構(gòu)造與譯碼[D].西安：西安電子科技大學(xué)，2012.

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