摘  要： 綜述了多進(jìn)制LDPC碼的幾種常用譯碼算法，重點(diǎn)講解分析了其中的擴(kuò)展最小和算法，并采用對(duì)比的方法證明其優(yōu)越性。
關(guān)鍵詞： 多進(jìn)制；低密度奇偶校驗(yàn)碼（LDPC）；擴(kuò)展最小和算法（EMS）；譯碼算法

　低密度奇偶校驗(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ù)界就展開(kāi)了針對(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碼，由此開(kāi)啟了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碼的幾種常見(jiàn)譯碼方法，分析各種方法的利弊，并利用多種形式重點(diǎn)介紹擴(kuò)展最小和算法。
1 常見(jiàn)譯碼算法
　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)稱(chēng)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ù)雜性較高。

　最小和譯碼算法是由WYMEERSCH H[4]等人根據(jù)BP譯碼算法提出的一種對(duì)數(shù)域BP算法，簡(jiǎn)稱(chēng)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)稱(chēng)EMS算法。該算法在最小和譯碼算法基礎(chǔ)上，提出一種縮短傳遞對(duì)數(shù)似然比概率信息數(shù)量的譯碼方法，大大降低了計(jì)算復(fù)雜度，在現(xiàn)有多進(jìn)制LDPC碼譯碼算法中受到推崇。
　假設(shè)經(jīng)過(guò)信道傳輸后在信宿端收到的對(duì)數(shù)似然比LLR消息向量是：

　隨后，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算法。由此可見(jiàn)，EMS算法的影響力有多么泛和深刻。
3 LDPC研究方向
　當(dāng)前，對(duì)LDPC碼的研究主要集中在檢驗(yàn)矩陣的構(gòu)造、譯碼算法的優(yōu)化、性能分析和改進(jìn)以及在實(shí)際系統(tǒng)中的應(yīng)用4個(gè)方面。即便如此，LDPC仍然有許多研究方向。
?。?）多進(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)力。
?。?）多進(jìn)制LDPC碼的譯碼方法對(duì)于EMS算法依賴(lài)過(guò)于嚴(yán)重，人們的認(rèn)知眼界和研究思路很難從中跳出，長(zhǎng)期以往，很難有大的突破和創(chuàng)新。如何能夠?qū)⒆g碼復(fù)雜度降下來(lái)，讓性能提升，依然是永恒的愿景。
?。?）多進(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ā)展方向之一。
?。?）盡快將更多的研究成果轉(zhuǎn)化為實(shí)際應(yīng)用，諸如深空衛(wèi)星通信、第四代（4G）移動(dòng)通信系統(tǒng)及深海通信等。
　本文介紹了多進(jìn)制LDPC常見(jiàn)的兩種譯碼算法，然后依據(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è)。
參考文獻(xiàn)
[1] GALLAGER R G. Low-density parity-check codes[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 J C， NEAL R M． Near Shannon limit performance of low density parity check codes[J]． Electronic Letters，1996，32（18）.
[4] WYMEERSCH H， STEENDAM H， MOENECLAEY M. 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. Low-complexity decoding for non-binary LDPC codes in high order fields[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.