低復雜度多進制LDPC碼譯碼算法研究＊

楊雪飛 李 瑞

（海軍裝備研究院1） 北京 100161）（海軍裝備部2） 北京 100161）

1 引言

自從LDPC（Low-Density Parity-Check）碼被重新發現以后，它就以接近香農限的優越性能受到極高的重視［1］。多進制LDPC碼比RS碼更勝一籌之處在于它的FFT-QSPA譯碼算法比RS碼的AHD BM （Algebraic Hard-Decision Berlekamp－Massey）算法和 ASD KV（Algebraic Soft-Decision Kotter-Vardy）算法更有效率。RS碼由于構造簡單、代數結構已知、良好的最小距離，仍然是最好的一類多進制碼型。不過目前仍然沒有一種有效的軟判決譯碼算法在實際應用的復雜度內達到較大的編碼增益。本文針對低復雜度的多進制LDPC碼編譯系統給出了一種聯合構造—編碼—譯碼的方案，即使用準循環結構的校驗矩陣，由此帶來編碼的優勢—只需采用簡單的循環移位累加寄存器（CSRAA）單元來進行編碼，其復雜度與碼字的校驗比特成正比；譯碼采用性能和復雜度折衷的FFT-QSPA算法。

2 具有準循環結構的多進制LDPC碼的構造

多進制LDPC碼的構造主要是校驗矩陣H的設計與構造，本文介紹有限域法，這種方法構造的碼具有循環或者準循環結構［7～11］。

令α為GF（q）域本原元，那么α－∞＝0，α0＝1，α，…，αq－2是 GF（q）域的全部元素。非零元素αi（0≤i≤q－2）的位置向量z（αi）＝（z0，z1，…，zq－2），其中zi＝αi，其余q－2個元素為0。

在GF（q）域下，用有限幾何和有限域方法構造多進制LDPC碼需要構造一個基矩陣W。

W須滿足乘α－行約束1）和2）：1）對于0≤i＜m，0≤k，l＜q－1并且，k≠l，αkwi與αlwi至少有n－1個位置不同；2）對于0≤i，j＜m，i≠j，且0≤k，l＜q－1，αkwi與αlwj至少n－1個位置不同。

對W的每一個wi，j進行水平和垂直方向的擴展［13］，得到 Ai，j：

從而得到校驗矩陣m（q－1）×n（q－1）維矩陣H：

使用有限域構造滿足乘α－行約束1）和2）的基矩陣時，可以用加群、乘群和循環群來構造。以加群構造為例，令α為GF（q）域本原元，構造如下基矩陣W：

3 低復雜度多進制LDPC譯碼算法

3.1 基本概念與初始化過程

如圖1所示，多進制LDPC譯碼因子圖包含變量節點（頂部圓塊）、校驗節點（底部圓塊）、置換節點和重排節點。其中置換節點將置信度向量進行循環移位，重排節點將置信度向量按照對應的a∈GF（q）遞增順序排列。

圖1 多進制LDPC譯碼因子圖

定義如下變量：｛Vpv｝v＝1，…，dv表示進入度為dv的變量節點的置信度，｛Uvp｝v＝1，…，dv表示從這一變量節點出來的置信度。下標pv表示置信度由轉置節點傳遞到變量節點，vp則表示其反方向；同樣｛Upc｝c＝1，…，dc表示進入度為dc的校驗節點的置信度，｛Vcp｝c＝1，…，dc表示進入這一校驗節點的置信度。

其中vi，c，vi，s是兩個獨立的高斯白噪聲。

其中ki＝P（si）／2πσ2P（yi），為一常數。

當采用BPSK調制時，映射方式是si＝2ci－1（i＝1，…，N），初始化概率為：

3.2 低復雜度的FFT-QSPA算法

采用BPSK調制時，根據接收信道值yi計算信道的轉移概率，得到初始化概率：

其中ak是a二進制表示的第k個比特，置信度L＝（L1，L2，…，LN）。

令 U［i1，…，ip］為p維張量，其中（i1，…，ip）∈｛0，1｝p。U［i1，…，ip］在 GF（2p）中 FFT 運算規則如式（9）所示：

張量乘法Z＝U×kF定義如式（11）和式（12）所示：

采用對數域運算的FFT-QSPA算法具體步驟如下：

第一步：初始化

令Uvp＝L，其中L元素的取值由式（8）得到；

第二步：校驗節點更新

（S1）：移位步驟

Ph（x）實際上就是將所有的值進行循環移位。對于反方向的移位步驟，可以用P－1h（x）表示；

（S2）：重排

將置信度按照對應的a∈GF（q）遞增順序排列；

（S3）：FFT

第三步：變量節點更新

第四步：嘗試譯碼

此時硬判決

3.3 復雜度分析

對于（N，K）規則 GF（q）-LDPC碼，使用本文給出的基于查找表法的低復雜度多進制LDPC的FFT-QSPA譯碼算法時，乘除運算均轉化為加法運算，每次迭代的每一步驟運算量如表1所示。

表1 每次迭代運算量

4 仿真與分析

本文的仿真基于AWGN信道，發送端采用BPSK調制，所構造的多進制LDPC碼與RS碼在碼率和碼長相當的情況下進行比較，多進制LDPC碼使用給出的低復雜度FFT-QSPA算法進行譯碼，最大迭代次數為50次，RS碼采用硬判決算法進行譯碼。

用有限幾何方法在GF（28）下構造校驗矩陣H，選取dv＝dv＝16，那么H的零空間給出碼率為0.68、最小距離為17的（255，175）QC-LDPC碼。由圖2可以看出，在BER為10－5處，（255，175）GF（28）-LDPC碼比（255，175）RS碼有1.55dB的編碼增益；在BLER為 10－2處，（255，175）GF（28）-LDPC 碼 比（255，175）RS碼有1.76dB的編碼增益。

圖2 （255，175）GF（28）-LDPC碼與（255，175）RS碼的性能曲線

用有限域方法在GF（24）下構造校驗矩陣H，選取dv＝3、dc＝6，那么H的零空間給出碼率為0.57、最小距離為4的（90，51）QC-LDPC碼。由圖3可以看出，在 BER 為10－5處，（90，51）GF（24）-LDPC碼比（90，50）RS碼有3dB的編碼增益；在BLER為10－2處，（90，51）GF（24）-LDPC碼比（90，50）RS碼有2.79dB的編碼增益。

圖3 （90，51）GF（24）-LDPC碼與（90，50）RS碼的性能曲線

從圖2和圖3可以清楚地看到，多進制LDPC碼與RS碼在具有相同碼率，相同比特幀長的情況下，性能均要比RS碼優越。

表2 每次迭代的計算次數

GF（qm）-LDPC碼使用FFT-QSPA譯碼算法時，由表1可知每次迭代的計算次數為o（Ndvqmlogqm）。表2給出了多進制LDPC碼與RS碼譯碼時每次迭代的計算次數。5次迭代時（255，175）RS碼每次迭代的計算次數是（255，175）LDPC碼的2.5倍，（90，50）RS碼是（90，51）LDPC碼的24倍。50次迭代時，（90，50）RS碼每次迭代的計算次數是（90，51）LDPC碼的2.4倍。50次迭代時，（255，175）LDPC采用有限幾何方法在 GF（28）域下構造，行重較大，因此計算量大于（255，175）RS碼，可以通過減少迭代次數來降低計算次數，當迭代次數下降到5次時，仿真表明其性能損失較小且仍然比RS碼性能優越。因此，譯碼算法的復雜度還與校驗矩陣H的構造有關，N與dv也是制約其復雜度的因素。如果要獲得低復雜度，譯碼算法不但要考慮譯碼本身的復雜度，還要考慮校驗矩陣H的構造，才能得到一種低復雜度的譯碼算法。

5 結語

多進制LDPC碼譯碼算法復雜度是制約其實用的一個重要因素，為了降低多進制準循環低密度奇偶校驗（QC-LDPC）碼譯碼的復雜度，給出了一種低復雜度多進制LDPC碼的譯碼算法，其準循環結構校驗矩陣的構造采用的是基于有限域和有限幾何的方法，這些方法可以實現多進制LDPC的線性編碼。通過仿真驗證本文構造的多進制QCLDPC碼不但明顯優于相同參數的RS碼，更重要的是復雜度大大降低。

［1］R.G.Gallager.Low density parity check codes［J］.IRE Trans.Inform.Theory.，1962，1（8）：21～28

［2］M.C.Davey，D.J.C.Mackay.Low-density parity check codes over GF（q）［J］.IEEE Commun.Lett.，1998，2（6）：165～167

［3］D.J.C.Mackay，M.C.Davey.Evaluation of Gallager codes of short block length and high rate applications［J］.Proc.IMA International Conf.Mathematics its Applications：Codes，systems Graphical Models，2000：113～130

［4］H.Song，J.R.Cruz.Reduced-complexity decoding of Q-ary LDPC codes for magnetic recording［J］.IEEE Trans.Magn.，2003，39（3）：1081～1087

［5］H.Wymeersch，H.Steendam，M.Moeneclaey.Logdomain decoding of LDPC codes over GF（q）［J］.Proc.IEEE Int.Conf.Commun.，2004：772～776

［6］D.Declercq，M.Fossorier.Decoding algorithms for nonbinary LDPC codes over GF（q）［J］.IEEE Trans.Commun.，2007，55（4）：633～643

［7］Lingqi Zeng，Lan Lan，Ying Yu Tai，et al.Construction of Nonbinary Quasi-Cyclic LDPC Codes：A Finite Field Approach［J］.IEEE Trans.Commun.，2008，56（4）：545～554

［8］Shumei Song，Bo Zhou，Shu Lin，et al.A Unified Approach to the Construction of Binary and Nonbinary Quasi-Cyclic LDPC Codes Based on Finite Fields［J］.IEEE Trans.Commun.，2009，57（1）：84～93

［9］Lingqi Zeng，Lan Lan，Ying Yu Tai，et al.Construction of Nonbinary Cyclic，Quasi-Cyclic and Regular LDPC Codes：A Finite Geometry Approach［J］.IEEE Trans.Commun.，2008，56（3）：378～387

［10］Bo Zhou，Jingyu Kang，Ying Yu Tai，et al.High Performance Non-Binary Quasi-Cyclic LDPC Codes on Euclidean Geometries［J］.IEEE Trans.Commun.，2009，57（5）：1298～1311