徐 晉，趙德周，李成軍

(武漢理工大學(xué)信息工程學(xué)院，湖北 武漢 430070)

低密度奇偶校驗(yàn)(low-density parity-check，LDPC)碼是由GALLAGER所提出的一種具有稀疏校驗(yàn)矩陣的線性分組碼[1]，經(jīng)過(guò)幾十年的沉寂，1999年，MACKAY重新發(fā)現(xiàn)LDPC碼是一種性能十分接近香農(nóng)限的好碼[2]。LDPC碼的構(gòu)造可歸為兩類(lèi)，一類(lèi)是基于隨機(jī)或偽隨機(jī)構(gòu)造，另一類(lèi)是基于代數(shù)法構(gòu)造。在構(gòu)造LDPC碼校驗(yàn)矩陣時(shí)，隨機(jī)構(gòu)造方法不利于硬件實(shí)現(xiàn)，于是人們想到利用代數(shù)幾何的方法來(lái)構(gòu)造LDPC碼的校驗(yàn)矩陣，于是產(chǎn)生了準(zhǔn)循環(huán)LDPC碼，即QC-LDPC碼(quasi-cyclic LDPC codes)。基于準(zhǔn)循環(huán)擴(kuò)展QCE(quasi-cyclic extension)技術(shù)設(shè)計(jì)的非規(guī)則RA(irregular repeat-accumulate，IRA)碼，由于設(shè)計(jì)簡(jiǎn)單，編碼快速等優(yōu)勢(shì)已被列入IEEE802.16e標(biāo)準(zhǔn)[3]。

為了適應(yīng)不同的傳輸環(huán)境，滿足不同的服務(wù)質(zhì)量要求，通信系統(tǒng)需要前向糾錯(cuò)編碼的碼率甚至幀長(zhǎng)自適應(yīng)地根據(jù)信道環(huán)境做出相應(yīng)調(diào)整，即自適應(yīng)信道變化的編碼器。DVB-S2中采用的LDPC碼就設(shè)置了兩種編碼長(zhǎng)度以及21種碼率，極大地改善了系統(tǒng)性能[4]。碼率及幀長(zhǎng)的自適應(yīng)變化雖然可以由多個(gè)編碼器和譯碼器實(shí)現(xiàn)，但此舉必然會(huì)導(dǎo)致編譯碼器的復(fù)雜度過(guò)高，故如何設(shè)計(jì)復(fù)雜度較低的速率兼容碼(變碼率變幀長(zhǎng))顯得更加重要，且已成為當(dāng)前編碼領(lǐng)域的研究熱點(diǎn)。

所謂的速率兼容碼(rate-compatible codes)，即較高碼率的碼字的校驗(yàn)比特是嵌套在較低碼率的碼字的校驗(yàn)比特中的。目前常用的速率兼容碼有BCH碼、卷積碼(rate-compatible punctured convolutional code，RCPC)和 Turbo碼(rate-compatible punctured turbo code，RCPT)。發(fā)送端將母碼經(jīng)過(guò)不同的刪除或擴(kuò)展得到不同的碼率，只需要一個(gè)編碼器。接收端已知被刪除比特或增加比特的位置即刪除矩陣或擴(kuò)展矩陣，因此可以按照母碼進(jìn)行譯碼，也只需要一個(gè)譯碼器。也就是說(shuō)，整個(gè)系統(tǒng)中使用一對(duì)編譯碼器便可以完成速率兼容碼的編碼和譯碼。

1 準(zhǔn)循環(huán)LDPC碼(QC-LDPC Codes)

QC-LDPC碼是LDPC碼的一個(gè)非常重要的子集，屬于構(gòu)造碼。LDPC碼由其奇偶校驗(yàn)矩陣H確定。QC-LDPC碼的奇偶校驗(yàn)矩陣H由一系列相同大小的稀疏循環(huán)矩陣給出，也就是說(shuō)它的奇偶校驗(yàn)矩陣是準(zhǔn)循環(huán)形式的。例如，IEEE802.16e標(biāo)準(zhǔn)中QC-LDPC碼由m×n的矩陣H定義，其中m為校驗(yàn)位的位數(shù)，n為碼長(zhǎng)的位數(shù)。其校驗(yàn)矩陣H是由基礎(chǔ)矩陣(Hb)mb×nb膨脹得到的，其中Hb如式(1)所示，膨脹因子z=n/24，m=mb× z，n=nb× z。

用 pi，j=-1 表示 z× z的全 0 矩陣，pi，j≥0 表示z×z的單位矩陣按列循環(huán)移位pi，j后的矩陣。由全0矩陣替換Hb中的-1，由循環(huán)移位的單位陣替換Hb中的非負(fù)元素，就可以由Hb擴(kuò)展成H矩陣。若將校驗(yàn)矩陣 Hb分成兩部分 Hb=[(Hb1)mb×kb|(Hb2)mb×mb]，Hb1稱為信息子集，Hb2稱為冗余子集，Hb1對(duì)應(yīng)信息比特，Hb2對(duì)應(yīng)校驗(yàn)比特。Hb2被進(jìn)一步分成兩部分，如式(2)所示。hb是非負(fù)的元素為奇數(shù)個(gè)的列向量，對(duì)應(yīng)H中奇數(shù)個(gè)單位方陣循環(huán)右移，H'b2為雙對(duì)角線結(jié)構(gòu)矩陣，對(duì)應(yīng)H的雙對(duì)角線結(jié)構(gòu)。這種結(jié)構(gòu)的碼又稱為重復(fù)累積碼(RA碼)，具有類(lèi)下三角形式，該下三角矩陣具有雙對(duì)角線形式。

這種基于單次擴(kuò)展的重復(fù)累積碼由于其校驗(yàn)矩陣也是稀疏的，因此是LDPC碼的一種，又由于其準(zhǔn)循環(huán)結(jié)構(gòu)，它又屬于QC-LDPC碼。該碼固然有良好的性能，但是在構(gòu)造速率兼容碼時(shí)，為了使較高碼率的校驗(yàn)比特能夠嵌入到較低碼率的碼字中，要求擴(kuò)展的校驗(yàn)陣的右上部分為全0陣。這就要求母碼擁有完全下三角形式。

2 速率兼容QC-LDPC碼的構(gòu)造方案

目前，速率兼容LDPC碼主要是鑿孔和擴(kuò)展構(gòu)成的多碼率LDPC碼，該類(lèi)多碼率LDPC碼的所有碼率的編碼矩陣和校驗(yàn)矩陣都相同，通過(guò)對(duì)信息位的鑿孔實(shí)現(xiàn)碼率的調(diào)整，是一種變碼長(zhǎng)的多碼率的實(shí)現(xiàn)。

顯然IEEE802.16e中的QC-LDPC碼的結(jié)構(gòu)使得在構(gòu)造速率兼容碼時(shí)，無(wú)法對(duì)其進(jìn)行擴(kuò)展。然而，可以在其基礎(chǔ)上進(jìn)行改進(jìn)，得到如下具有完全下三角矩陣的校驗(yàn)陣，作為速率兼容碼的母碼校驗(yàn)矩陣。

為了構(gòu)造速率兼容的LDPC碼，筆者使用順序刪除和擴(kuò)展檢驗(yàn)矩陣的方法[5]。以上述mb=12，nb=24的矩陣為母碼的校驗(yàn)矩陣，母碼的速率R=1/2。膨脹因子 z=96，故為(2304，1152)碼。通過(guò)對(duì)母碼校驗(yàn)矩陣的擴(kuò)展來(lái)構(gòu)造較低碼率的碼字，相對(duì)的，通過(guò)對(duì)母碼校驗(yàn)矩陣的順序刪除來(lái)得到較高碼率的碼字。無(wú)論是對(duì)校驗(yàn)矩陣進(jìn)行刪除還是擴(kuò)展，都保持校驗(yàn)矩陣信息子集不變，都為kb=nb-mb=12。通過(guò)對(duì)校驗(yàn)矩陣進(jìn)行順序擴(kuò)展來(lái)得到較低碼率的碼字，如圖1所示;將校驗(yàn)矩陣沿對(duì)角線方向進(jìn)行擴(kuò)展，擴(kuò)展矩陣B1，B2是具有完全下三角形式的r×r的方陣，如圖2所示。擴(kuò)展后的校驗(yàn)矩陣右上方是全零元素，左下方C1和C2是稀疏矩陣。C1和C2可采用PEG方法構(gòu)造，且避免使校驗(yàn)矩陣出現(xiàn)圍長(zhǎng)為4的短環(huán)。PEG算法[6]的基本思想就是通過(guò)展開(kāi)Tanner圖，找到距離變量節(jié)點(diǎn)最遠(yuǎn)的校驗(yàn)節(jié)點(diǎn)，然后在它們之間添加所需要的邊，這樣新添加的邊對(duì)Tanner圖影響最小，得到的Tanner圖具有最大的圍長(zhǎng)?？梢?jiàn)，經(jīng)擴(kuò)展后的碼率為Rn=(nb-mb)/(nb+r)，當(dāng) r=2 時(shí)，Rn=0.46。

圖1 順序擴(kuò)展方案

圖2 B1、B2具有完全下三角的擴(kuò)展矩陣

順序刪除校驗(yàn)矩陣的最下面r行和最右邊r列，這樣既能得到較高碼率的碼字又能保證高碼率的碼字包含在低碼率的碼字之中，所得到的新碼字的碼率為R'=(nb-mb)/(nb-r)?？梢?jiàn)，當(dāng)r=2時(shí)，碼率R'=0.55;當(dāng)r=4時(shí)，碼率R'=0.6。

3 LDPC碼的線性時(shí)間編碼

RU分解算法給出了線性編碼的方法，首先將校驗(yàn)矩陣進(jìn)行分塊[7]:

其中，T為下三角矩陣，則H可轉(zhuǎn)化為如圖3所示的近似下三角校驗(yàn)矩陣。

圖3 近似下三角校驗(yàn)矩陣

對(duì)于所使用的RC-QC-LDPC碼來(lái)說(shuō)，B=C=D=E=φ，因此，分塊矩陣可以進(jìn)一步簡(jiǎn)化成如圖4所示的完全下三角校驗(yàn)矩陣。在圖4中，A為m×k階的矩陣，T為m×m階的具有完全下三角形式的矩陣。將輸入編碼器的信息比特以z比特為一組，即 vi=[vi1，vi2，…，viz]，則輸入的信息比特可表示為 V=[v1，v2，…，vk]T，同樣將校驗(yàn)比特以 z比特為一組，即 pi=[pi1，pi2，…，piz]，則編碼器得到的校驗(yàn)比特可表示成P=[p1，p2，…，pm]T。由線性分組碼的編碼可知:

即A·V+T·P=0，式中所有的求和均為模

圖4 完全下三角的校驗(yàn)矩陣

得到 p1=u1，p2=u1+u2，p3=u1+u2+u3，

因此關(guān)鍵的計(jì)算量在于求解矩陣A·V，由于A的元素是由單位矩陣循環(huán)移位置換而得到的，故A·V可以在線性時(shí)間內(nèi)編碼，從而實(shí)現(xiàn)QC-LDPC碼的線性時(shí)間編碼，編碼的復(fù)雜度為O(n)。矩陣A·V可以通過(guò)移位寄存器電路和模二和電路來(lái)實(shí)現(xiàn)，硬件電路簡(jiǎn)單。

4 LDPC碼的解碼

LDPC碼譯碼算法中，普遍采用置信傳播BP算法和對(duì)數(shù)似然比置信傳播LLR-BP算法[8-10]。它們是基于LDPC碼的圖論模型，在比特節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間所傳遞的是信息位和校驗(yàn)方程的可靠性信息。迭代譯碼方法可以采用并行結(jié)構(gòu)實(shí)現(xiàn)。由于BP算法的實(shí)現(xiàn)復(fù)雜度較高，實(shí)時(shí)性不好，人們提出改進(jìn)的算法，典型的就是最小和MS算法及其改進(jìn)算法。最小和算法是在LLR-BP算法的基礎(chǔ)上進(jìn)行簡(jiǎn)化得到的，即利用gallager函數(shù)φ(x)的單調(diào)遞減性及φ-1(x)=φ(x)。

實(shí)現(xiàn)最小和算法的步驟為:

(1)初始化 L(0)(qij)=L(pi)=2yi/σ2。

(5)做判決，若 L(qi)＞0則判 ci=0，否則ci=1。

如果c·H'=0或到達(dá)最大迭代次數(shù)，則譯碼結(jié)束，否則令t=t+1跳回步驟(2)繼續(xù)迭代。

5 仿真結(jié)果及性能分析

在加性高斯白噪聲信道下，信號(hào)采用BPSK調(diào)制，采用最小和積算法，最大迭代次數(shù)30次，對(duì)構(gòu)造出的速率兼容碼進(jìn)行仿真。對(duì)于以下的碼字(2304，1152)，(2112，1152)，(1920，1152)，(2496，1152)仿真結(jié)果如圖5所示。

圖5 速率兼容碼的誤碼率性能

從圖5可以看出，對(duì)母碼矩陣(碼率1/2)進(jìn)行擴(kuò)展后得到碼率為0.46的碼字，誤碼性能明顯變好，當(dāng)誤碼率為10-3時(shí)，約有0.5 dB的信噪比增益。添加檢驗(yàn)比特可以提高誤碼性能，對(duì)母碼進(jìn)行刪除之后得到碼率為0.55和0.60的碼字，誤碼性能變差，當(dāng)誤碼率為10-3時(shí)，分別約有0.5 dB和1.0 dB的信噪比損失，打孔會(huì)造成性能變差。

6 結(jié)論

筆者通過(guò)仿真驗(yàn)證了實(shí)現(xiàn)線性時(shí)間解碼和復(fù)雜度較低的解碼，以及通過(guò)順序刪除和順序擴(kuò)展構(gòu)造速率兼容的QC-LDPC碼的可行性，同時(shí)證實(shí)了該方法具有一定的廣泛性，并為L(zhǎng)DPC碼在自適應(yīng)編碼中的應(yīng)用提供了參考依據(jù)。

[1] GALLAGER R G.Low density parity check codes[J].IRE Transactions on Information Theory，1962，8(1):21-28.

[2] MACKAY D J C.Good error correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory ，1999，45(2):399-431.

[3] IEEE802.16e:part 16.Air interference for fixed and mobile broadband access system[S].

[4] ALBERTO M，VITTORIA M.DVB-S2:the second generation standard for satellite broad-band services[J].Proceedings of the IEEE，2006 ，94(1):210-216.

[5] JOEHONG K.The design of efficently-encodable rate-compatible LDPC codes [J].IEEE Transaction on Communications，2009，57(2):365-375.

[6] HU X Y，ELEFTHERIOU E.Regular and irregular progressive edge-growth tanner graphs[J].IEEE Transactions on Information Theory，2005，51(1):386-398.

[7] RICHARDSON T，URBANKE R.Efficient encoding of low-density parity-check codes[J].IEEE Transactions on Information Theory，2001，47(2):638-656.

[8] CHEN J H，F(xiàn)OSSORIER M.Near optimum university belief propagation based decoding of low density parity check codes[J].IEEE Transactions on Communications，2002，50(3):406-414.

[9] 吳湛擊，王文博.現(xiàn)代信道編碼與調(diào)制:理論與應(yīng)用[M].北京:人民郵電出版社，2008:232-236.

[10] 文紅，符初生.LDPC碼原理與應(yīng)用[M].成都:電子科技大學(xué)出版社，2006:55-63.