趙勇 夏融 丁彥

摘 要：隨著通信技術(shù)的不斷進(jìn)步，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)狀，探討了目前存在的問題以及改進(jìn)方向。

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

0 ? 引言

科技的進(jìn)步對當(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)勢和不足，最后進(jìn)行總結(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：

為了降低運(yùn)算量和硬件存儲空間，在構(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)化的校驗矩陣在保證性能的同時，大大降低了運(yùn)算量和存儲空間，方便編碼，也加快了譯碼收斂速度。

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

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

多元LDPC碼定義在有限域上，利用域元素直接編譯碼，具有一定性能增益，其優(yōu)點如下：（1）糾錯性能優(yōu)異，由于多元LDPC碼用一個多元字符代替多個二元比特，可以掩蓋中小環(huán)的存在，在譯碼過程中可以減少重復(fù)迭代的可能，提高糾錯性能;（2）抗突發(fā)錯誤能力強(qiáng)，對于同時發(fā)生隨機(jī)和突發(fā)錯誤的通信和數(shù)據(jù)存儲信道，多元LDPC碼可以將二元比特的突發(fā)錯誤合并成少量的多元符號錯誤，具有很強(qiáng)的抗突發(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ù)雜度很高，目前也一直致力于尋找糾錯能力強(qiáng)，譯碼過程簡單的譯碼算法;（3）性能分析困難。運(yùn)用密度演進(jìn)算法等分析工具進(jìn)行性能分析時復(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ù)可以帶來頻帶利用率的提升，但弊端是使得譯碼門限提高，即達(dá)到相同的誤碼率時需要更高的信噪比。由于多元LDPC碼直接對符號進(jìn)行編譯碼，適合與高階調(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成功證明了基于有限域隨機(jī)構(gòu)造出來的LDPC碼性能優(yōu)于二元LDPC碼，在高斯白噪聲（AWGN）信道和二元擦除信道（BEC）上都具有良好的迭代譯碼性能。

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

利用代數(shù)理論、有限幾何知識以及矩陣運(yùn)算理論為主的結(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)，進(jìn)一步提升編碼器吞吐量。有限幾何知識是構(gòu)造LDPC碼的重要方式之一，最早，利用點和線之間關(guān)系可以得到最小距離和陷阱集較優(yōu)的碼字結(jié)構(gòu)，具有非常低的錯誤平層。矩陣運(yùn)算理論中掩模技術(shù)使用較多，掩模技術(shù)主要通過將已知結(jié)構(gòu)的校驗矩陣與某一掩模矩陣相乘，改變原有矩陣結(jié)構(gòu)，在降低短環(huán)數(shù)目的同時使其度分布更好，稀疏性更強(qiáng)。

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

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

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

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

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

4 結(jié)語

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

[參考文獻(xiàn)]

[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.

（編輯 王永超）