趙勇 夏融 丁彥

摘 要：隨著通信技術(shù)的不斷進步，LDPC碼以其優(yōu)越的糾錯性能和高效譯碼算法成為信道編碼中關(guān)鍵技術(shù)之一，被廣泛應(yīng)用于多種通信標(biāo)準(zhǔn)中。其中，多元LDPC碼在高階調(diào)制下以及突發(fā)錯誤信道中表現(xiàn)更好，尤其是短到中等碼長條件下性能提升明顯，但也存在不足。為了更好協(xié)調(diào)頻帶利用率與誤碼率之間關(guān)系，降低譯碼復(fù)雜度，文章對多元LDPC碼的構(gòu)造與譯碼方面展開論述，主要闡述了其發(fā)展歷程和研究現(xiàn)狀，探討了目前存在的問題以及改進方向。

關(guān)鍵詞：信道編碼，LDPC碼，多元LDPC碼，構(gòu)造，譯碼

0 ? 引言

科技的進步對當(dāng)前通信系統(tǒng)提出了更高要求。一直以來，信道編碼作為數(shù)字通信系統(tǒng)中保證信息可靠傳輸?shù)年P(guān)鍵技術(shù)之一而備受人們關(guān)注，其中低密度奇偶校驗LDPC碼是一種常用的線性分組碼，最早由Gallager在1962年其博士論文中提出，證明具有可以十分接近香農(nóng)極限的糾錯性能，但受當(dāng)時硬件計算能力的限制，直到1995年，LDPC碼才重新引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。

LDPC碼的特點是其校驗矩陣具有稀疏性，矩陣中含有大比例的零元素，結(jié)構(gòu)相對簡單，主要采用軟判決譯碼算法，通過在變量節(jié)點和校驗節(jié)點之間反復(fù)傳遞外信息實現(xiàn)信息收斂，從而正確譯碼。LDPC碼已成為DVB-S2、WiFi等應(yīng)用場景中常用的編碼方式，對比3G和4G移動通信標(biāo)準(zhǔn)中使用的Turbo碼來說，中短碼長下LDPC碼具有較好的瀑布曲線性能以及更靈活豐富的碼長和碼率。2016年，成功作為5G移動通信技術(shù)標(biāo)準(zhǔn)中數(shù)據(jù)業(yè)務(wù)信道的編碼方案。除了目前已經(jīng)廣泛使用的二元LDPC碼，多元LDPC碼的優(yōu)勢明顯，但也存在著阻礙其發(fā)展的難點和挑戰(zhàn)，其多元特點增加了校驗矩陣構(gòu)造的難度，提高了編譯碼復(fù)雜度。本文首先介紹多元LDPC碼的基本概念，闡述LDPC碼的優(yōu)缺點以及實際應(yīng)用場景，針對多元LDPC碼的構(gòu)造和譯碼方面研究展開論述，討論目前常見的構(gòu)造和譯碼方式并分析其優(yōu)勢和不足，最后進行總結(jié)。

1 多元LDPC碼的基本概念

設(shè)GF（q）是包含q個元素的伽羅華域，其中q由素數(shù)的冪得到。定義在有限域GF（q）上的校驗矩陣H=[hi，j]0≤i≤m，0≤j≤N構(gòu)成了一個q元的規(guī)則LDPC碼，該碼具有以下結(jié)構(gòu)性質(zhì)：? ? ? （1）固定的列重和行重;（2）每兩行（或兩列）對應(yīng)位置都不存在相同非零值。如果行重列重不唯一，則稱該碼字為非規(guī)則LDPC碼。

二元LDPC碼的校驗矩陣由“0”和“1”組成，而多元LDPC碼的校驗矩陣則是由有限域中域元素組成，例如在伽羅華域GF（23）下，域元素包括{α﹣∞=0，α0，α1，…，α6}，其中α表示該域下的本原元，用α的多次冪可以表示所有域元素。多元LDPC碼的表示方法主要有兩種，校驗矩陣和Tanner圖。其校驗矩陣中的非零元素在Tanner圖中表示為連接邊上的標(biāo)簽值。定義在GF（23）的多元LDPC碼的Hq見公式（1）：

對應(yīng)的Tanner圖見圖1：

為了降低運算量和硬件存儲空間，在構(gòu)造LDPC碼時采用準(zhǔn)循環(huán)結(jié)構(gòu)，稱為準(zhǔn)循環(huán)低密度奇偶校驗碼（QC-LDPC），其校驗矩陣由多個循環(huán)移位子矩陣構(gòu)成，僅通過循環(huán)移位子矩陣簡單地移位操作便可完成構(gòu)造，結(jié)構(gòu)化的校驗矩陣在保證性能的同時，大大降低了運算量和存儲空間，方便編碼，也加快了譯碼收斂速度。

2 ? 多元LDPC碼的優(yōu)缺點及應(yīng)用場景

LDPC碼在碼長趨于無窮時，性能可以逼近香農(nóng)極限，但在實際應(yīng)用中多使用中短碼長進行傳輸。由于接收端必須接收完整的碼塊后才能進行譯碼，因此當(dāng)碼長較長時延更大，不利于在時延要求高的場景下使用，因此提升中短碼長性能是十分重要的。此外，隨著碼率增大，編碼序列中包含有用信息位數(shù)增大，校驗位數(shù)減少，糾錯能力下降。

多元LDPC碼定義在有限域上，利用域元素直接編譯碼，具有一定性能增益，其優(yōu)點如下：（1）糾錯性能優(yōu)異，由于多元LDPC碼用一個多元字符代替多個二元比特，可以掩蓋中小環(huán)的存在，在譯碼過程中可以減少重復(fù)迭代的可能，提高糾錯性能;（2）抗突發(fā)錯誤能力強，對于同時發(fā)生隨機和突發(fā)錯誤的通信和數(shù)據(jù)存儲信道，多元LDPC碼可以將二元比特的突發(fā)錯誤合并成少量的多元符號錯誤，具有很強的抗突發(fā)錯誤的能力;（3）傳輸速率范圍大，它可以使用于高階調(diào)制通信中，提供更高的數(shù)據(jù)傳輸速率和更大的頻譜效率。

基于上述優(yōu)勢，多元LDPC碼值得學(xué)術(shù)界更多的關(guān)注，但研究多元LDPC碼也要考慮幾個方面的難點：（1）構(gòu)造難度大。其校驗矩陣具有多元特點意味著構(gòu)造時需要考慮合適的有限域和本原元，基矩陣的度分布以及非零元素的選擇等因素，構(gòu)造時可以借鑒許多二元LDPC構(gòu)造方法;（2）譯碼復(fù)雜度高。多元LDPC碼的譯碼算法中譯碼復(fù)雜度很高，目前也一直致力于尋找糾錯能力強，譯碼過程簡單的譯碼算法;（3）性能分析困難。運用密度演進算法等分析工具進行性能分析時復(fù)雜度更高。

由于不同應(yīng)用場景下信道條件不同，對LDPC碼的要求也不同。對于移動通信信道來說，隨著用戶數(shù)量的增加，要求具有更高傳輸速率以及更大信道容量。而對于衛(wèi)星信道來說，其傳輸帶寬較窄，需要較高的頻帶利用率以及更好的抗干擾能力。高階調(diào)制技術(shù)的使用可以提高頻帶利用率，目前主要的高階調(diào)制技術(shù)有正交幅度調(diào)制技術(shù)QAM和相移鍵控PSK調(diào)制技術(shù)等。更高階數(shù)的調(diào)制技術(shù)可以帶來頻帶利用率的提升，但弊端是使得譯碼門限提高，即達到相同的誤碼率時需要更高的信噪比。由于多元LDPC碼直接對符號進行編譯碼，適合與高階調(diào)制技術(shù)結(jié)合。多元LDPC碼可用一個符號代表多個比特，可以克服突發(fā)錯誤，帶來了性能提升?；谏鲜鰞?yōu)勢，多元LDPC碼值得學(xué)術(shù)界更多的關(guān)注，但研究多元LDPC碼也存在構(gòu)造、譯碼以及性能分析等方面的難點，優(yōu)化多元LDPC碼的碼字結(jié)構(gòu)、降低譯碼復(fù)雜度以及分析碼字性能具有一定實際意義。

3 ? 多元LDPC碼的構(gòu)造與譯碼研究

20世紀(jì)60年代左右，Gallager在提出二元LDPC碼的同時開始利用有限域構(gòu)造多元LDPC碼，但只是從思想上提出多元碼。直到1998年，Mackay和Davey成功證明了基于有限域隨機構(gòu)造出來的LDPC碼性能優(yōu)于二元LDPC碼，在高斯白噪聲（AWGN）信道和二元擦除信道（BEC）上都具有良好的迭代譯碼性能。

事實上，多元LDPC碼的構(gòu)造方法可以分為兩類，即隨機化構(gòu)造方法和結(jié)構(gòu)化構(gòu)造方法。PEG算法是一種常用的隨機構(gòu)造法之一，已知度分布下可逐步建立起校驗節(jié)點和變量節(jié)點之間的連接，用于建立較大環(huán)長的多元LDPC碼的Tanner圖。近似環(huán)外消息度（ACE）算法也是著名的基于計算機的隨機構(gòu)造算法之一，它在考慮環(huán)的基礎(chǔ)上，增加了重疊環(huán)對譯碼的影響，以此來提高譯碼迭代時外信息的流通性。上述隨機構(gòu)造法需要進行大量的計算機搜索運算，構(gòu)造的碼字毫無規(guī)律，雖然隨機構(gòu)造的LDPC碼具有良好的性能，但編碼復(fù)雜度很高。

利用代數(shù)理論、有限幾何知識以及矩陣運算理論為主的結(jié)構(gòu)化構(gòu)造法可用于構(gòu)造一類校驗矩陣具有規(guī)律結(jié)構(gòu)的多元LDPC碼。通過利用特殊結(jié)構(gòu)的集合，例如完美差分集、素數(shù)集和好碼等可以構(gòu)造一類具有規(guī)律性結(jié)構(gòu)的LDPC碼，有效地改善了瀑布區(qū)性能，帶來一定的性能提升。構(gòu)造多元LDPC碼時可以結(jié)合“好”碼帶來結(jié)構(gòu)上的優(yōu)化，包括廣義RS碼（GRS）和非規(guī)則重復(fù)累加碼（IRA）等。通過結(jié)合其他碼字特性，優(yōu)化多元LDPC碼的校驗矩陣，使其可以高效編碼，易于硬件實現(xiàn)，進一步提升編碼器吞吐量。有限幾何知識是構(gòu)造LDPC碼的重要方式之一，最早，利用點和線之間關(guān)系可以得到最小距離和陷阱集較優(yōu)的碼字結(jié)構(gòu)，具有非常低的錯誤平層。矩陣運算理論中掩模技術(shù)使用較多，掩模技術(shù)主要通過將已知結(jié)構(gòu)的校驗矩陣與某一掩模矩陣相乘，改變原有矩陣結(jié)構(gòu)，在降低短環(huán)數(shù)目的同時使其度分布更好，稀疏性更強。

此外，衡量碼字優(yōu)劣的指標(biāo)很多，包括環(huán)分布、最小距離、陷阱集等，上述幾種結(jié)構(gòu)化構(gòu)造方法也從這些衡量指標(biāo)出發(fā)。其中對于環(huán)的存在，特別是短環(huán)，易帶來變量節(jié)點之間的相關(guān)性，使得外信息僅傳遞幾次就回到自身節(jié)點，不利于準(zhǔn)確譯碼，如PEG算法專注于設(shè)計環(huán)長較大的碼字。最小距離則反映了編碼后碼字在受到噪聲干擾時變?yōu)橄噜彺a字的難易程度，最小距離越大則受噪聲影響越小，也越容易譯碼，也是影響譯碼門限和性能曲線瀑布區(qū)的關(guān)鍵因素之一。由于多元LDPC碼定義在有限域上，其校驗矩陣由域內(nèi)元素組成，因此從優(yōu)化系數(shù)集的角度，可實現(xiàn)對環(huán)等衡量指標(biāo)的優(yōu)化。

除了構(gòu)造方面對于提升LDPC碼性能帶來好處外，復(fù)雜度較低的譯碼算法也十分重要，不僅可以降低對硬件的要求，也可擴大編碼應(yīng)用場景。對于多元LDPC碼來說，譯碼復(fù)雜度較高，是限制它在現(xiàn)實應(yīng)用場景的范圍的主要原因之一，因此降低其譯碼復(fù)雜度是很有意義的。降低計算量和復(fù)雜度的主要解決途徑包括簡化每次迭代時有限域上的加法運算和乘法運算復(fù)雜度，保證糾錯性能的前提下，盡可能降低迭代次數(shù)等。

目前，復(fù)雜度較高的多元和積譯碼算法（QSPA）依舊是目前性能最優(yōu)的譯碼算法，但不適用于實際，隨后又產(chǎn)生了基于傅里葉變換的FFT-QPSA，進一步基于對數(shù)域提出了Log-FFT-QSPA，避免了實數(shù)乘法運算。雖然上述各種算法在一定程度上降低了譯碼復(fù)雜度，但是依舊不利于實際應(yīng)用。因此采用消息截短和排序方法來進一步降低復(fù)雜性和內(nèi)存需求，同樣其復(fù)雜度主要集中在校驗節(jié)點的更新處理上。2007年，擴展最小和（EMS）算法出現(xiàn)了，是一種通過犧牲性能降低復(fù)雜度的算法，也是目前應(yīng)用最廣泛的多元譯碼算法之一。EMS算法將輸入節(jié)點更新的外信息減少，但是輸出并存儲的值仍不變，這無形中增大了對存儲器的要求，因此為節(jié)省內(nèi)存，文獻[1]提出與對兩類節(jié)點都進行了截短處理，用補償因子解決因截短外信息引起的性能下降問題，結(jié)果表明在每次譯碼迭代中顯著降低了復(fù)雜度，將譯碼器的外信息截短到有限的數(shù)值，可以減少對內(nèi)存的需求，是一種較好的硬件實現(xiàn)方案，但是對截掉的部分采用相同值替代可能會帶來一些誤差。

總的來說，EMS算法復(fù)雜度比QSPA低，但有較大的性能損失，為縮小兩者之間的性能差距，在校驗節(jié)點更新中采用改進的檢泡算法，包括動態(tài)EMS算法、基于動態(tài)檢泡的EMS算法和聯(lián)合解調(diào)EMS算法，性能上有所提升。文獻[2]提出了一種基于組合優(yōu)化的簡化最小和算法，利用校驗節(jié)點處理的近似方法實現(xiàn)復(fù)雜性和性能之間的權(quán)衡。文獻[3]在MSA中利用可靠性估計提高誤碼性能，相比位翻轉(zhuǎn)算法（BF）具有更大的優(yōu)勢，主要應(yīng)用于實時譯碼和糾錯場景下的性能提升，具有更高的安全性。文獻[4]則通過大量仿真分析了EMS算法中碼率、迭代次數(shù)、排序個數(shù)以及修正因子對譯碼性能帶來的影響，歸納總結(jié)其中的譯碼規(guī)律。

除上述算法外，一種用于多元碼譯碼的低復(fù)雜度準(zhǔn)優(yōu)化迭代算法被提出，即Min-Max算法，將EMS算法中的加法運算簡化為最大值運算，降低了譯碼復(fù)雜度。隨后，提出了一種自適應(yīng)Min-Max算法，在原有算法基礎(chǔ)上，利用校驗和中非零元素存在的比例作為自適應(yīng)調(diào)節(jié)變量節(jié)點長度的依據(jù)，進而降低復(fù)雜度。同樣，在原有Min-Max算法基礎(chǔ)上提出改進措施，在譯碼過程中主要傳遞可靠度較高的校驗節(jié)點信息以提高糾錯效率。由于多元碼字可由二元比特表示，直接對比特進行譯碼可以簡化譯碼難度，故提出一種基于擴展矩陣的Min-Max算法，將多元的節(jié)點擴展為二元節(jié)點進行運算處理，它不僅降低了高斯消元法的計算復(fù)雜度，而且提高了誤差性能，但是運算時間會增加。

綜上所述，對于多元LDPC碼的構(gòu)造問題，核心目標(biāo)是對衡量碼字結(jié)構(gòu)的指標(biāo)進行優(yōu)化，從而快速準(zhǔn)確地構(gòu)造一個結(jié)構(gòu)良好的校驗矩陣，有利于接收端準(zhǔn)確譯碼。而對于多元LDPC碼的譯碼問題，需要分析兩類節(jié)點譯碼規(guī)律，在盡可能不降低糾錯性能的同時，降低兩類節(jié)點更新過程中的運算量。

4 結(jié)語

本文針對信道編碼中常用的線性分組碼—LDPC碼進行討論，多元LDPC碼在中短碼長下具有更好的性能增益而引起人們的注意，但也存在一些問題有待解決。先介紹了多元LDPC碼的基本概念，其次探討了其優(yōu)缺點以及應(yīng)用場景，最后從構(gòu)造和譯碼兩個方面對目前多元LDPC碼的研究現(xiàn)狀進行論述，從優(yōu)化校驗矩陣結(jié)構(gòu)以及降低譯碼復(fù)雜度這兩個優(yōu)化方向上對相關(guān)研究進行綜述，對優(yōu)化多元LDPC碼具有一定的指導(dǎo)意義。

[參考文獻]

[1]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（5）：1365-1375.

[2]Wang C L，Chen X，Li Z，et al.A simplified min-sum decoding algorithm for non-binary LDPC codes[J].IEEE Transactions on Communications，2013（1）：24-32.

[3]Babu J C，Reddy C C，Prasad M N G.Generation and decoding of non-Binary LDPC codes using MSA decoding algorithm[C].Singapore：Micro-Electronics Springer，2018.

[4]蔡蓉燕.非二元低密度奇偶校驗碼LDPC譯碼性能研究[D].成都：西南交通大學(xué)，2016.

（編輯 王永超）