PEG－GLDPC碼設(shè)計(jì)與性能分析

王 平 朱宏鵬 李廣俠

（解放軍理工大學(xué)通信工程學(xué)院衛(wèi)星通信重點(diǎn)實(shí)驗(yàn)室，南京，210007）

引 言

在深空通信中，由于通信距離的大幅增加，通信信號(hào)的自由空間傳播損耗很大，接收信號(hào)的信噪比極低，通信系統(tǒng)所處理的信號(hào)強(qiáng)度極其微弱。因此，提高系統(tǒng)的功率利用效率是深空通信系統(tǒng)設(shè)計(jì)需要考慮的最重要問(wèn)題之一，而信道編碼則是一種有效提高功率利用率的方法。低密度奇偶校驗(yàn)（Low density parity check，LDPC）是一類(lèi)具有稀疏校驗(yàn)矩陣的線性分組糾錯(cuò)碼，目前已被許多衛(wèi)星通信標(biāo)準(zhǔn)采納，并應(yīng)用到深空通信領(lǐng)域。例如，國(guó)際空間數(shù)據(jù)系統(tǒng)咨詢委員會(huì)（Consultative committee for space data systems，CCSDS）推薦采用ARA LDPC用于深空通信系統(tǒng)，我國(guó)嫦娥二號(hào)探月任務(wù)中采用了LDPC編碼，LDPC首次應(yīng)用于我國(guó)深空探測(cè)領(lǐng)域。然而隨著深空探測(cè)距離的增大和數(shù)據(jù)傳輸速率的提高，LDPC碼將不能滿足未來(lái)深空通信中高信道編碼增益的需求，具有簡(jiǎn)單編碼結(jié)構(gòu)的QC－LDPC［1］也難以獲得逼近信道容量極限的譯碼性能。

廣義低密度奇偶校驗(yàn)（Generalized LDPC，GLDPC）碼由 Lentmaier［2］和Boutros［3］于1999年分別獨(dú)立提出，在迭代譯碼下具有優(yōu)越的糾錯(cuò)性能。在GLDPC的Tanner圖中，校驗(yàn)節(jié)點(diǎn)為一個(gè)線性分組碼的約束，而不是單奇偶校驗(yàn)碼，因此稱(chēng)GLDPC的校驗(yàn)節(jié)點(diǎn)為廣義校驗(yàn)節(jié)點(diǎn)，該線性分組碼被稱(chēng)為GLDPC的子碼。最近有不少學(xué)者采用不同的子碼（如BCH，RS，RM）對(duì)GLDPC進(jìn)行了研究［4－7］。上述研究均以Gallager方法構(gòu)造的LDPC為基矩陣，基矩陣存在大量的短環(huán)，從而影響了GLDPC的譯碼性能，無(wú)法滿足深空通信高編碼增益的要求。本文從低信噪比通信系統(tǒng)的設(shè)計(jì)需求出發(fā)，以提高GLDPC譯碼性能為目標(biāo)，采用按邊增大（Progressive edge－growth，PEG）算法構(gòu)造規(guī)則LDPC碼，然后以BCH為子碼對(duì)其進(jìn)行擴(kuò)展，構(gòu)造出 PEG－GLDPC 碼。PEG－GLDPC 結(jié)構(gòu)靈活，可根據(jù)系統(tǒng)設(shè)計(jì)需要靈活選擇相應(yīng)的碼長(zhǎng)和恰當(dāng)?shù)淖哟a。采用基于比特柵格和BP算法的迭代聯(lián)合譯碼機(jī)制，獲得了較好的譯碼性能。

1 GLDPC介紹

傳統(tǒng)GLDPC奇偶校驗(yàn)矩陣的構(gòu)造可以分為兩個(gè)步驟：首先采用Gallager方法構(gòu)造低密度奇偶校驗(yàn)基矩陣Hb（N，J，n），其中N為碼長(zhǎng)，J為列重，n為行重，如圖1（a）所示；然后選取子碼C0（n，k），k為子碼信息位長(zhǎng)度，并將Hb每一行中的“1”用子碼的校驗(yàn)矩陣H0的某一列替換，“0”用全零列矢量替換，如圖1（b）所示。若校驗(yàn)矩陣為滿秩，則構(gòu)造的GLDPC碼率為

圖1 GLDPC校驗(yàn)矩陣的構(gòu)造

若LDPC的低密度校驗(yàn)矩陣采用Gallager分層構(gòu)造方法，也將每一層的N／n個(gè)分量碼的直和稱(chēng)為一個(gè)超碼。包含3個(gè)超碼的LDPC（12，3）的Tanner圖如圖2所示，以Gallager方法為基矩陣的GLDPC的Tanner圖如圖3所示。需要指出的是，若低密度校驗(yàn)矩陣采用其他的方法構(gòu)造，GLDPC碼未必可以分解為若干超碼。

圖2 Gallager LDPC（12，3）的 Tanner圖

圖3 GLDPC的Tanner圖

J＝2的GLDPC在最小距離意義上是漸近最優(yōu)的［3］，因此目前構(gòu)造的GLDPC多以J＝2的基矩陣構(gòu)造。然而當(dāng)J＝2時(shí)，由Gallager方法構(gòu)造的規(guī)則LDPC碼存在一定數(shù)量的4環(huán)，環(huán)長(zhǎng)特性差，影響譯碼性能。改進(jìn)基矩陣的環(huán)長(zhǎng)特性則可進(jìn)一步提高GLDPC的性能。PEG算法構(gòu)造LDPC碼時(shí)，在增加邊的同時(shí)可盡力拉大最小環(huán)長(zhǎng)，由PEG算法構(gòu)造的中長(zhǎng)LDPC碼可將4環(huán)完全消除［8］。因此，本文選取PEG算法生成GLDPC的基矩陣。

2 PEG－GLDPC碼構(gòu)造

構(gòu)造PEG－LDPC的過(guò)程就是獲得其校驗(yàn)矩陣的過(guò)程，PEG－GLDPC的校驗(yàn)矩陣可以通過(guò)以下3個(gè)步驟獲?。海?）根據(jù)PEG算法構(gòu)造規(guī)則LDPC的校驗(yàn)矩陣，以其為基矩陣；（2）選取子碼；（3）用子碼校驗(yàn)矩陣的列向量替換LDPC校驗(yàn)矩陣中的“1”。

2.1 回退型PEG算法

PEG算法又稱(chēng)按邊增長(zhǎng)算法，它增加邊的方法是在可選集中選擇具有最少連接邊的校驗(yàn)節(jié)點(diǎn)進(jìn)行連接，最終構(gòu)造的LDPC變量節(jié)點(diǎn)度分布一致，而校驗(yàn)節(jié)點(diǎn)度分布有所波動(dòng)，并非嚴(yán)整意義上的規(guī)則LDPC。在GLDPC中，基矩陣的校驗(yàn)節(jié)點(diǎn)要求有完全一致的度分布。因此，為構(gòu)造規(guī)則LDPC碼Hb（N，J，n），本文提出一種回退型PEG算法?；赝诵蚉EG算法對(duì)傳統(tǒng)PEG算法進(jìn)行了修改，其主要特點(diǎn)是在增加新邊時(shí)遵循以下兩個(gè)原則：

（1）若可選集最少連接邊的校驗(yàn)節(jié)點(diǎn)已達(dá)到校驗(yàn)節(jié)點(diǎn)度分布數(shù)，則選擇次少連接邊的校驗(yàn)節(jié)點(diǎn)；

（2）若可選集中所有校驗(yàn)節(jié)點(diǎn)都已達(dá)到校驗(yàn)節(jié)點(diǎn)度分布數(shù)，則回退一層。

2.2 PEG－GLDPC校驗(yàn)矩陣構(gòu)造

下面舉例給出（14，12）PEG－GLDPC的構(gòu)造過(guò)程。如圖4所示，首先采用回退型PEG算法構(gòu)造（14，2，7）規(guī)則LDPC碼作為基矩陣，然后將校驗(yàn)矩陣每行中的“1”隨機(jī)用（7，4）BCH校驗(yàn)矩陣的列替換，“0”用三維全零列矢量替換。基矩陣同一列中的“1”需用子碼校驗(yàn)矩陣不同的列來(lái)替換。

圖4 （14，2）PEG－GLDPC校驗(yàn)矩陣的構(gòu)造過(guò)程

3 聯(lián)合譯碼算法

PEG－GLDPC碼的譯碼分為兩個(gè)層次：（1）子碼的軟譯碼，（2）基矩陣的迭代譯碼。受GLDPC碼率和基矩陣行重的限制，GLDPC碼的子碼多為短碼且具有高碼率，可采用基于比特柵格的最大后驗(yàn)概率譯碼（Maximum a posteriori probability，MAP）算法或基于似然碼字列表的Chase算法［9］進(jìn)行譯碼。Chase算法雖然復(fù)雜度低但是次優(yōu)的，為提高譯碼準(zhǔn)確性本文選取MAP算法對(duì)子碼進(jìn)行譯碼。基矩陣的迭代譯碼選取BP算法，BP算法是一種基于似然信息傳播機(jī)制的迭代譯碼算法。采用BCH比特柵格譯碼與BP迭代算法聯(lián)合譯碼機(jī)制對(duì)PEG－GLDPC進(jìn)行譯碼過(guò)程中，信息傳遞機(jī)制如圖5所示。

圖5 PEG－GLDPC迭代譯碼中的信息傳遞機(jī)制

3.1 子碼BCH的Log－MAP譯碼

MAP算法根據(jù)對(duì)數(shù)似然比函數(shù)（Log likehood ratio，LLR）判決每個(gè)碼比特vi的值［10］，LLR定義如下

為去除式（2）中的大量乘法運(yùn)算，本文采用Log－MAP譯碼算法，Log－MAP算法依據(jù)式（3）對(duì)式（2）進(jìn)行了簡(jiǎn)化，變乘法為加法，在譯碼準(zhǔn)確性下降不大的同時(shí)可降低復(fù)雜度。

3.2 PEG－GLDPC的聯(lián)合譯碼機(jī)制

假設(shè)發(fā)送的信息為v＝（v0，v1，…，vN－1），采用BPSK調(diào)制后，對(duì)應(yīng)的雙極性信號(hào)表示為c＝（c0，c1，…，cN－1），ci＝1－2vi＝±1。經(jīng)過(guò) AWGN 信道后，譯碼端收到的軟判決信息為r＝（r0，r1，…，rN－1），r＝c＋u，其中u為均值為0、方差為σ2的高斯白噪聲。變量節(jié)點(diǎn)的初始LLR信息可通過(guò)式（4）計(jì)算得到

式中：Γ（i）為與變量節(jié)點(diǎn)vi相連的廣義校驗(yàn)節(jié)點(diǎn)的集合，Λ（j）為與廣義校驗(yàn)節(jié)點(diǎn)cj相連的變量節(jié)點(diǎn)的集合，φki（j）和ηkj（i）分別為變量節(jié)點(diǎn)vi向廣義校驗(yàn)節(jié)點(diǎn)cj和廣義校驗(yàn)節(jié)點(diǎn)cj向變量節(jié)點(diǎn)vi傳輸?shù)腖LR信息，其中t為當(dāng)前迭代次數(shù)。基于Log－MAP的BP算法可以表述如下：

步驟1 初始化。通過(guò)式（4）計(jì)算每個(gè)變量節(jié)點(diǎn)的初始LLR信息L0（i）＝Lch（i），變量節(jié)點(diǎn)向廣義校驗(yàn)節(jié)點(diǎn)發(fā)送初始信息值φ0i（j）＝L0（i），作為子碼Log－MAP譯碼時(shí)的輸入信息。

步驟2 子碼Log－MAP譯碼。更新第t次廣義校驗(yàn)節(jié)點(diǎn)cj對(duì)應(yīng)的子碼經(jīng)Log－MAP譯碼后傳輸給與其相連的變量節(jié)點(diǎn)vi的外信息

式中：fLog－MAP為子碼 Log－MAP譯碼公式，θ為修正因子（θ＞1），用以修正Log－MAP輸出的外信息值。修正因子θ目前沒(méi)有既成公式，表1給出了不同的修正因子取值對(duì)碼長(zhǎng)為960的PEG－GLDPC誤碼率的影響。在實(shí)際應(yīng)用中，需根據(jù)碼長(zhǎng)和信道條件選取恰當(dāng)?shù)摩戎?，進(jìn)行自適應(yīng)調(diào)整。

表1 修正因子對(duì)誤碼率的影響

步驟3 廣義校驗(yàn)節(jié)點(diǎn)更新。變量節(jié)點(diǎn)vi向廣義校驗(yàn)節(jié)點(diǎn)cj傳輸?shù)耐庑畔?/p>

步驟4 判決。經(jīng)過(guò)第t次迭代后，變量節(jié)點(diǎn)vi獲得的后驗(yàn)對(duì)數(shù)似然比為

根據(jù)Lt（i）得到第t次迭代的輸出序列，如果Lt（i）≥0，ci＝0；否則ci＝1。如果輸出序列滿足校驗(yàn)方程，譯碼成功，終止迭代，否則t＝t＋1，跳轉(zhuǎn)至步驟2。

4 仿真結(jié)果與分析

在AWGN信道條件下，對(duì)PEG－GLDPC進(jìn)行仿真，并與LDPC碼和基于Gallager算法構(gòu)造的傳統(tǒng)GLDPC進(jìn)行比較。本文選取規(guī)則GLDPC為研究對(duì)象，需要指出的若研究非規(guī)則GLDPC，需進(jìn)行度分布優(yōu)化設(shè)計(jì)，在用EXIT圖法設(shè)計(jì)GLDPC的度分布時(shí)，需同時(shí)考慮LDPC碼和子碼的EXIT函數(shù)。

用PEG 算法構(gòu)造（420，2，15）規(guī)則 LDPC碼，并用（15，11，3）BCH碼作子碼進(jìn)行擴(kuò)展，產(chǎn)生的PEG－GLDPC碼長(zhǎng)為420，碼率0.467。誤碼率曲線如圖6所示，PEG－GLDPC性能優(yōu)于PEG算法構(gòu)造的LDPC和文獻(xiàn)［3］中構(gòu)造的傳統(tǒng)GLDPC。同樣用（15，11，3）BCH 碼作子碼，對(duì)PEG算法構(gòu)造的（960，2，15）規(guī)則LDPC碼進(jìn)行擴(kuò)展，得到碼長(zhǎng)960，碼率0.467的PEG－GLDPC。誤碼率曲線如圖7所示，與文獻(xiàn)［2］中構(gòu)造的傳統(tǒng)GLDPC相比，PEG－GLDPC的誤碼性能明顯改善。采用文獻(xiàn)［11］中的度分布構(gòu)造1／2碼率的PEGGLDPC，碼長(zhǎng)為1 000 000的誤碼率曲線如圖8所示，與 PEG 算法構(gòu)造的 LDPC，QC－LDPC，傳統(tǒng)GLDPC相比，PEG－GLDPC碼的譯碼性能最佳，與香農(nóng)限（0.184dB）距離最近。

表2給出了上述兩種碼字基矩陣的環(huán)長(zhǎng)特性對(duì)比，通過(guò)表2不難發(fā)現(xiàn)，較之傳統(tǒng)GLDPC，碼長(zhǎng)為960的PEG－GLDPC性能改善較大，是由于基矩陣完全消除了4環(huán)和6環(huán)，提高了BP譯碼的準(zhǔn)確度。實(shí)際上，消除4環(huán)可以大幅提高譯碼準(zhǔn)確度，消除6環(huán)也可以提高譯碼準(zhǔn)確度，然而環(huán)長(zhǎng)越大對(duì)譯碼準(zhǔn)確度的影響越小，所以盡管碼長(zhǎng)為960的PEG－GLDPC基矩陣含有大量8環(huán)，但對(duì)譯碼準(zhǔn)確度的影響已經(jīng)不大。

圖6 （420，196）GLDPC碼性能曲線

圖7 （960，448）GLDPC碼性能曲線

圖8 1／2碼率、1 000 000碼長(zhǎng)的GLDPC碼性能曲線

表2 基矩陣的環(huán)長(zhǎng)特性

5 結(jié)束語(yǔ)

本文基于PEG算法構(gòu)造了GLDPC碼，并提出了適用于該碼字的譯碼算法。對(duì)不同碼長(zhǎng)的PEG－GLDPC進(jìn)行了仿真，結(jié)果表明，PEG－GLDPC的譯碼性能優(yōu)于LDPC和傳統(tǒng)GLDPC，適用于深空通信等點(diǎn)對(duì)點(diǎn)低信噪比通信系統(tǒng)。究其原因，GLDPC碼采用子碼校驗(yàn)，而不是LDPC碼的單奇偶校驗(yàn)，因此其比LDPC碼具有更強(qiáng)的糾錯(cuò)能力。而與傳統(tǒng)GLDPC相比，PEG－GLDPC的基矩陣具有更好的環(huán)長(zhǎng)特性，因此，其譯碼性能在三者中最優(yōu)。本文主要從環(huán)長(zhǎng)特性方面對(duì)GLDPC進(jìn)行了改進(jìn)，后續(xù)工作將研究如何從外信息、陷阱集等方面對(duì)GLDPC進(jìn)行改進(jìn)。

［1］ 傅婷婷，吳湛擊，王文博.基于PEG算法的準(zhǔn)循環(huán)LDPC碼的編碼構(gòu)造方法［J］.數(shù)據(jù)采集與處理，2009，24（S1）：190－194.Fu Tingting，Wu Zhanji，Wang Wenbo.PEG－based construction method for 1uasi－cyclic LDPC［J］.Journal of Data Acquisition and Processing，2009，24（S1）：190－194.

［2］ Lentmaier M，Zigangirov K S.On generalized lowdensity parity check codes based on Hamming component codes［J］.IEEE Communications Letter，1999，3（8）：248－250.

［3］ Boutros J，Pothier O，Zkmort G.Generalized lowdensity（Tanner）codes［C］∥Proceeding IEEE ICC.Vancouver：Curran Associates Inc.，1999：441－445.

［4］ Chilappagari S K，Nguyen D V，Vasic B，et al.On trapping sets and guaranteed error correction capability of LDPC codes and GLDPC codes［J］.IEEE Transactions on Information Theory，2010，56（4）：1600－1611.

［5］ Bocharova I E，Hug F，Johannesson R，et al.Double－Hamming based QC LDPC codes with large minimum distance［C］∥2011IEEE International Symposium on Information Theory Proceedings.Saint－Petersburg：IEEE Express Conference Publishing，2011：923－927.

［6］ Yue Guosen，Ping Li，Wang Xiaodong.Generalized low－density parity－check codes based on Hadamard constraints［J］.IEEE Transactions on Information Theory，2007，53（3）：1058－1079.

［7］ Abu－Surra S，Divsalar D，Ryan W E.On the typical minimum distance of generalized LDPC convolutional codes based on protographs［C］∥ISIT 2010.Texas：IEEE Express Conference Publishing，2010：709－713.

［8］ Hu Xiaoy，Eleftheriou E，Arnold D M.Regular and irregular progressive edge－growth Tanner graphs［J］.IEEE Transactions on Information Theory，2005，51（1）：386－398.

［9］ 鄭賀，陸佩忠，胡捍英.基于二分圖的乘積碼迭代譯碼算法［J］.電子與信息學(xué)報(bào)，2006，28（1）：86－91.Zheng He，Chen Peizhong，Hu Hanying.Iterative decoding algorithm for product codes based on bipartite graphs［J］.Journal of Electronics ＆Information Technology，2006，28（1）：86－91.

［10］Lin S，Costello D J.Error control coding［M］.Landon：Prentice Hall，2007：711－715.

［11］Wang Yige，F(xiàn)ossorier M.Doubly generalized LDPC codes over the AWGN channel［J］.IEEE Transactions on Information Theory，2009，57（5）：1312－1319.