摘  要： 綜述了多進制LDPC碼的幾種常用譯碼算法，重點講解分析了其中的擴展最小和算法，并采用對比的方法證明其優越性。
關鍵詞： 多進制；低密度奇偶校驗碼（LDPC）；擴展最小和算法（EMS）；譯碼算法

　低密度奇偶校驗碼LDPC（Low Density Parity Check）是目前信道編碼領域公認的性能優異，形式簡單，應用前景廣闊的一種好的線性分組碼。LDPC碼的性能最逼近香農限，因此被認為是未來通信領域中最具競爭力的信道編碼。自從1962年GALLAGER R G[1]博士在其學位論文中首次提出LDPC碼的相關概念，并用當時條件局限的方法證明了其優異的糾錯性能之后，學術界就展開了針對LDPC的卓識有效的研究，并取得了極大的成果。至20世紀末，二進制LDPC碼已經成為了非常成熟的信道編碼。除了理論方面取得了巨大成就，二進制LDPC在應用領域更是大放異彩。歐洲通信標準委員會（ETSI）推出的DVB-S2標準中，信道編碼已經采用LDPC碼。2010年10月10日，清華大學研制的低密度奇偶校驗碼遙測信道編碼試驗按計劃實施，“嫦娥二號”衛星上LDPC編碼器以及喀什測控站、青島測控站LDPC遙測譯碼終端狀態良好、運行正常，遙測數據接收解調正常，試驗取得成功。此次試驗成功是LDPC信道編碼技術首次應用于我國航天領域。LDPC碼優異性能成為未來第四代（4G）移動通信系統最強有競爭力的候選標準之一。
　1998年，DAVEY M C和MACKAY D J C[2]提出了基于GF（q）域的LDPC碼，由此開啟了LDPC碼研究的一個新領域。定義在GF（q）上的多進制LDPC碼的雙向圖與二進制的相似，但變量節點有q（q=2b）個可能取值，校驗節點的約束限制也比二進制檢驗節點更復雜。在原信道不變的情況下，多進制的一個符號需要b個二進制比特。相比之下，無論是在計算復雜度，還是存儲容量及傳輸占用時間等方面，多進制LDPC碼都比二進制LDPC碼有更大的難度。盡管如此，由于其具有無可比擬的特性，多進制的研究都是極有理論和工程意義的。
　本文簡要介紹多進制LDPC碼的幾種常見譯碼方法，分析各種方法的利弊，并利用多種形式重點介紹擴展最小和算法。
1 常見譯碼算法
　LDPC碼有很多種譯碼方法。根據消息迭代過程中傳送消息的形式不同，可以將LDPC碼的譯碼方法分為硬判決譯碼和軟判決譯碼兩種。硬判決譯碼設定閾值來判斷輸出，軟判決譯碼通過最大后驗概率信息決定可能的信源值。硬判決譯碼計算簡單，但是誤碼率高；軟判決譯碼計算復雜，但是性能優異。實踐中，傾向于選擇軟判決譯碼。目前，多進制LDPC碼的軟判決譯碼方法主要有信度傳播BP（Belief Propagation）算法、最小和MS（Min-Sum）算法、Normalized BP-based算法以及LP算法。在此介紹前兩種算法。
　信度傳播算法是由MACKAY P J C和NEAL R M[3]共同提出的一種迭代譯碼算法，簡稱BP算法。BP算法迭代過程如圖1所示。BP算法的核心思想在于利用接收到的軟信息在變量節點和校驗節點之間進行迭代運算，從而獲得最大編碼增益。該算法在迭代過程中會對結果作出判決。如果譯碼達到預定標準，譯碼計算立即結束而不再繼續進行固定次數的迭代，大大節省了譯碼時間，降低了運算復雜度。而若算法在到達預先限定的最大迭代次數后仍未找到有效的譯碼結果，譯碼器將宣告譯碼失敗。BP算法是一種并行譯碼算法，在硬件中的并行實現能夠極大地提高譯碼速度。LDPC碼利用BP譯碼算法能夠得到很好的譯碼性能，但是由于大量的乘法運算，采用BP算法的硬件復雜性較高。

　最小和譯碼算法是由WYMEERSCH H[4]等人根據BP譯碼算法提出的一種對數域BP算法，簡稱MS算法。其基本思想與BP算法無異，只是在概率信息的表示形式上采用對數似然比，將BP算法中的諸多乘法運算轉換為對數域上的加法運算，大大降低了運算復雜度、減少了運行時間且不需要對信道噪聲進行估計，但其性能也有一定程度的降低。
　上述各譯碼雖然在不同的時期不同的應用點各自具有很大優勢，但復雜度和實現難度依然很高，研究人員仍然在不斷改進和創新譯碼工作，推動著LDPC學科整體進展。
2 EMS算法
　2007年，DECLERCQ D和FOSSORIER M[5]提出一種擴展最小和EMS（Extended Min-Sum）算法，簡稱EMS算法。該算法在最小和譯碼算法基礎上，提出一種縮短傳遞對數似然比概率信息數量的譯碼方法，大大降低了計算復雜度，在現有多進制LDPC碼譯碼算法中受到推崇。
　假設經過信道傳輸后在信宿端收到的對數似然比LLR消息向量是：

　隨后，VOICILA A等人[6]從實現角度對EMS算法進行了改進，將譯碼的實數加法運算復雜度進一步下降。如今，譯碼算法界眾多研究人員依然致力于對此算法的研究，希望有所突破。
　當前，EMS在多進制LDPC碼譯碼算法中具有舉足輕重的地位，所有最新的研究成果均是圍繞此算法進行的改進和實現。無論誰想要在多進制LDPC譯碼算法上有所作為，都必須深刻研究EMS算法。由此可見，EMS算法的影響力有多么泛和深刻。
3 LDPC研究方向
　當前，對LDPC碼的研究主要集中在檢驗矩陣的構造、譯碼算法的優化、性能分析和改進以及在實際系統中的應用4個方面。即便如此，LDPC仍然有許多研究方向。
?。?）多進制LDPC碼的校驗矩陣的構造方法依然存在很大的難度?，F有眾多方法應用范圍過于狹窄，往往是滿足了一方面的要求，而在其他地方則差強人意。無論是結構化構造還是隨機構造，對于硬件實現總有不理想之處。追求完善、系統的檢驗矩陣的構造方法是學術界的動力。
?。?）多進制LDPC碼的譯碼方法對于EMS算法依賴過于嚴重，人們的認知眼界和研究思路很難從中跳出，長期以往，很難有大的突破和創新。如何能夠將譯碼復雜度降下來，讓性能提升，依然是永恒的愿景。
　（3）多進制LDPC編碼系統的聯合優化設計，將編碼技術與調制技術、空時編碼技術、OFDM技術結合進行性能優化是當前及將來的發展方向之一。
?。?）盡快將更多的研究成果轉化為實際應用，諸如深空衛星通信、第四代（4G）移動通信系統及深海通信等。
　本文介紹了多進制LDPC常見的兩種譯碼算法，然后依據原算法以及個人的理解，利用圖解的方式重點分析了EMS算法的具體步驟以及需要注意的問題。通過分析，就能夠理解EMS在存儲和計算復雜度中較其他算法具有明顯優勢。最后對多進制LDPC碼的研究方向進行了簡要分析和預測。
參考文獻
[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，FOSSORIER 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碼：設計、構造與譯碼[D].西安：西安電子科技大學，2012.
[8] 袁東風，張海剛.LDPC碼理論與應用[M].北京：人民郵電出版社，2008.