一種改進(jìn)的碼率兼容QC-LDPC碼構(gòu)造算法

范仁基，趙旦峰

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001)

0 引言

LDPC碼(Low-Density Parity-Check code)[1]是目前最為接近Shannon極限的一種糾錯碼，受到人們極大的重視。近年來，為了更好地適應(yīng)各種通信系統(tǒng)多速率要求，LDPC碼的碼率兼容特性成為了一個研究和實現(xiàn)要點(diǎn)[2]，特別是隨著無人機(jī)被廣泛地應(yīng)用于各領(lǐng)域[3]，研究具有碼率兼容的LDPC碼意義重大。

目前多碼率的實現(xiàn)方法主要有3種：刪余型、擴(kuò)展型和縮短型。刪余型是目前應(yīng)用最為廣泛的碼率兼容形式，通過選取一個性能優(yōu)異的低碼率母碼，然后對校驗位進(jìn)行刪余打孔處理實現(xiàn)多碼率，這樣可以節(jié)省存儲空間，但在刪余打孔時，存在產(chǎn)生大量陷阱集[4-5]導(dǎo)致性能惡化的問題；擴(kuò)展型是通過擴(kuò)展矩陣或校驗節(jié)點(diǎn)分裂方式實現(xiàn)，有效地克服了刪余型存在的問題，但也造成了需要存儲多個校驗矩陣[4]，大量占用硬件資源的問題；縮短型不同于前兩者，是通過對輸入的信息序列進(jìn)行處理實現(xiàn)多碼率，其雖然克服了擴(kuò)展型帶來的矩陣存儲問題，卻也因為需要信息序列預(yù)處理而增加了編譯碼的復(fù)雜度。因此有必要找到一種能夠較好地兼顧多碼率性能以及硬件資源占用的LDPC碼。本文將PEG算法與準(zhǔn)循環(huán)法相結(jié)合[6]，通過正逆向兩次使用PEG算法構(gòu)造具有下三角形式的準(zhǔn)循環(huán)校驗矩陣，在實現(xiàn)多個碼率兼容的同時，各碼率下碼字性能與同參數(shù)下的準(zhǔn)循環(huán)矩陣性能接近，而且其硬件實現(xiàn)較之前的QC-LDPC碼更為簡單，碼率控制更為靈活，尤其適合于硬件資源有限且通信環(huán)境復(fù)雜的無人機(jī)使用。

1 LDPC碼概述

LDPC碼是一種線性分組碼，若其對應(yīng)校驗矩陣為H，則其生成矩陣G唯一確定，其碼長為n，信息序列長為k，校驗矩陣H的維數(shù)為m×n,m=n-k。二元域GF(2)上的一個3×6校驗矩陣可以如圖1所示，當(dāng)存在序列c滿足HcT=0時，c為該LDPC碼的一個碼字。

圖1 3×6校驗矩陣

LDPC碼的另一種描述形式為Tanner圖[7]，一種由變量節(jié)點(diǎn)、校驗節(jié)點(diǎn)以及兩類節(jié)點(diǎn)間的邊構(gòu)成的圖描述，如圖2所示。選取Tanner圖中某一節(jié)點(diǎn)為根節(jié)點(diǎn)，選取與之相連接的節(jié)點(diǎn)作為子節(jié)點(diǎn)并以邊相連，重復(fù)操作，直至沒有新生節(jié)點(diǎn)或出現(xiàn)重復(fù)節(jié)點(diǎn)為止，這樣就可以得到一個樹形展開圖[7]。樹圖可以更為便利地研究LDPC校驗矩陣的特性。

圖2 校驗矩陣的Tanner圖

在Tanner圖中，從某一節(jié)點(diǎn)出發(fā)，經(jīng)過若干節(jié)點(diǎn)后返回此點(diǎn)為一循環(huán)(Cycle)，經(jīng)過的邊的數(shù)目為這一循環(huán)的長度，而這其中最短的環(huán)長記為Girth，如圖2中所列舉的環(huán)，即為6環(huán)。由于LDPC的譯碼通常采用BP譯碼算法或基于BP算法改進(jìn)而來的和積譯碼算法[7]，在譯碼時，某一節(jié)點(diǎn)的信息會經(jīng)過最短的環(huán)路傳回自身，這樣就會破壞節(jié)點(diǎn)更新過程中信息的獨(dú)立傳播特性，導(dǎo)致譯碼收斂速度減慢甚至譯碼失敗。因此在構(gòu)造LDPC碼校驗矩陣時，要盡可能地消除短環(huán)，增大最短環(huán)長Girth。

2 QC-LDPC碼校驗矩陣的結(jié)構(gòu)和特性

QC-LDPC(Quasi-Cyclic LDPC)碼是一種基于循環(huán)置換矩陣的LDPC碼，由單位陣的循環(huán)置換矩陣和零矩陣構(gòu)成其校驗矩陣[8]。以mb×nb維的準(zhǔn)循環(huán)LDPC碼的校驗矩陣H為例，可以表示為式(1):

(1)

式中，I(Pij)(1≤i≤m,1≤j≤n)是一個右循環(huán)移位的b×b維方陣，可以通過單位陣I的每行經(jīng)過Pij次右移得到，當(dāng)Pij=0時，I(Pij)為單位陣，當(dāng)Pij=-1時，I(Pij)為零矩陣。

由此也可以得到另外兩個重要矩陣，即由Pij組成的循環(huán)移位參數(shù)矩陣(2)以及基矩陣(3)：

(2)

(3)

而當(dāng)這兩個矩陣被確定的同時，LDPC的校驗矩陣也隨之確定下來。通過對比LDPC校驗矩陣H與其基矩陣A，不難發(fā)現(xiàn)這二者具有相同的度分布[9,10]，而且其循環(huán)移位參數(shù)矩陣P具有如下特性：

若在一個循環(huán)塊邊長為b的QC-LDPC校驗矩陣的Tanner圖中，存在一條長度為2l的環(huán)，那么其循環(huán)移位參數(shù)矩陣P中同樣存在這樣環(huán)的充要條件[10]為:

(4)

根據(jù)這一特性，在基矩陣確定的條件下，校驗矩陣的最小環(huán)長不小于其基矩陣中的最小環(huán)長。因此可以通過調(diào)整循環(huán)移位參數(shù)矩陣P中各元素的數(shù)值，從而進(jìn)一步消減短環(huán)擴(kuò)大Girth，提升QC-LDPC校驗矩陣的性能。

3 PEG算法

PEG(Progress Edge Growth)算法[6,11-12]是在Tanner圖中選取一點(diǎn)為起點(diǎn)，在確保從該點(diǎn)出發(fā)的環(huán)長最大的條件下，不斷向節(jié)點(diǎn)之間添加邊的一種算法。PEG算法可以很好地保證任意一點(diǎn)的環(huán)長盡可能大，從而盡可能地增大Girth。

圖3 PEG算法的構(gòu)造流程

PEG算法的復(fù)雜度會隨碼長增加而急劇增高，因此該算法通常用于中、短碼構(gòu)造，而且構(gòu)造過程中對于校驗矩陣的全局優(yōu)化不足，容易產(chǎn)生大量公共節(jié)點(diǎn)，因其環(huán)分布復(fù)雜，也會對矩陣性能造成一定降低。特別是由于PEG采用隨機(jī)構(gòu)造方法，導(dǎo)致校驗矩陣缺乏結(jié)構(gòu)性，硬件實現(xiàn)復(fù)雜度高，更不利于在無人機(jī)LDPC碼中使用。

4 改進(jìn)的碼率兼容QC-LDPC碼構(gòu)造

PEG算法在中、短LDPC碼構(gòu)造上表現(xiàn)優(yōu)異，其本身最大缺陷在于硬件實現(xiàn)復(fù)雜度高，而QC-LDPC碼在工程實現(xiàn)性上有很大優(yōu)勢，剛好可以對PEG法進(jìn)行一定彌補(bǔ)，同時PEG算法也可以為QC-LDPC提供更大的圍長，因此可以將兩種構(gòu)造方法相結(jié)合，進(jìn)行聯(lián)合構(gòu)造。本文首先采用PEG算法，構(gòu)造一個高碼率校驗矩陣的基矩陣，然后在其基礎(chǔ)上，進(jìn)行碼率擴(kuò)展構(gòu)造出碼率兼容的基矩陣。

但由于基本的PEG算法本身并不適用于碼率兼容矩陣構(gòu)造，而在校驗矩陣構(gòu)造時，PEG算法可以有效地控制最短環(huán)的長度，這給構(gòu)造碼率兼容的LDPC碼校驗矩陣奠定了良好基礎(chǔ)，因此這里提出一種逆向PEG算法，可以在不改變最短環(huán)長的條件下，降低校驗矩陣的碼率以實現(xiàn)校碼率范圍的擴(kuò)展。

圖4 逆向PEG算法流程圖

通過分析算法流程可知，逆向PEG算法中對于每個新增的校驗節(jié)點(diǎn)除第一次添加邊是直接選擇度數(shù)最低的變量節(jié)點(diǎn)外，都是在進(jìn)行深度為2l的樹展開后，才向新校驗節(jié)點(diǎn)添加新邊，這樣可以有效保證新增校驗節(jié)點(diǎn)與原校驗矩陣所組成的環(huán)長度均是大于2l的，也從而確保了拓展后的LDPC校驗矩陣中Girth保持不變，僅增大校驗矩陣的平均環(huán)長，來提升校驗矩陣的性能。這樣就可以通過逆向PEG算法，實現(xiàn)碼率兼容基矩陣的構(gòu)造，最后通過將基矩陣中的各“1”元素和“0”元素分別用循環(huán)移位矩陣以及零矩陣進(jìn)行替換，最終完成碼率兼容的QC-LDPC碼的構(gòu)造。

在對基矩陣進(jìn)行擴(kuò)展時，從本文第2節(jié)循環(huán)矩陣特性得知，通過合理地調(diào)整各循環(huán)移位矩陣的移位參數(shù)，可以實現(xiàn)對矩陣結(jié)構(gòu)優(yōu)化以及碼字性能的提升。下面通過Tanner圖進(jìn)一步討論如何設(shè)置循環(huán)移位矩陣參數(shù)。

結(jié)合公式(4)，令：

ΔPiPj(t)=Pi,t-Pj,t

(5)

這樣可以得到另外一個重要性質(zhì)[9]：校驗矩陣中H的Girth不小于2(l+1)的重要條件為：

(6)

因此若要使得Girth不小于2(l+1)，需要每次添加循環(huán)移位參數(shù)時確保式(6)成立，這樣才能盡可能消減矩陣內(nèi)的短環(huán)。綜上所述，碼率兼容QC-LDPC碼的構(gòu)造算法具體步驟如圖5所示。

圖5 改進(jìn)的碼率兼容QC-LDPC碼構(gòu)造流程圖

逆向PEG擴(kuò)展得到基矩陣是在用PEG構(gòu)造的高碼率基矩陣的基礎(chǔ)上得到的，使得基矩陣具備了多碼率兼容特性的同時，還確保了基矩陣中的最小環(huán)長不發(fā)生變化。而循環(huán)移位參數(shù)矩陣與零矩陣參與的替換過程，使得矩陣中的環(huán)長進(jìn)一步增大，進(jìn)一步減少了短環(huán)數(shù)量，提高了碼字的糾錯性能，也令其硬件可實現(xiàn)性得到很大簡化，更加利于資源受限的無人機(jī)等設(shè)備使用。

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

本設(shè)計以信息序列長為288 bit，碼率涵蓋3/4、2/3、1/2進(jìn)行仿真分析。以3/4碼率為母矩陣進(jìn)行擴(kuò)展構(gòu)造，并使用MATLAB對矩陣性能進(jìn)行仿真，得出該LDPC 碼分別在幾個不同碼率下的誤碼率性能，仿真曲線如圖6所示。此外，在1/2碼率下將本設(shè)計與IEEE 802.16e標(biāo)準(zhǔn)的LDPC碼(q=24，即信息序列長為288 bit) 以及DVB-S2標(biāo)準(zhǔn)的LDPC縮短碼(信息序列長為300 bit)進(jìn)行性能對比研究，仿真曲線如圖7所示。為了便于比較，輸入信號為二進(jìn)制偽隨機(jī)序列，編碼器采用BPSK調(diào)制，信道為AWGN信道，最大迭代次數(shù)為25，均采用最小和MS譯碼算法。

圖6 信息位長288 bit碼字性能

圖7 1/2碼率下LDPC碼性能對比

由圖6可見，本設(shè)計生成的碼率兼容QC-LDPC碼在其所涵蓋的3種碼率下都具有較為優(yōu)秀的誤碼率性能，在BER=10-6時，3/4碼率與1/2碼率的LDPC碼的性能差異在1 dB左右。由圖7可知，相近碼長情況下，1/2碼率的碼率兼容QC-LDPC碼性能略差于DVB-S2標(biāo)準(zhǔn)的LDPC縮短碼，但是在歸一化信噪比為3.5 dB時二者性能一致。而與IEEE 802.16e標(biāo)準(zhǔn)的LDPC碼相比，在誤碼率為10-4～10-6的區(qū)間下，碼率兼容QC-LDPC碼的性能始終有著約0.5 dB的差距。綜上所述，本設(shè)計生成的QC-LDPC碼在保證性能優(yōu)異的同時實現(xiàn)了多碼率兼容，具有良好的實用性。

6 結(jié)論

本文提出一種基于PEG算法的QC-LDPC碼構(gòu)造方法，通過該方法可以構(gòu)造出具有下三角結(jié)構(gòu)的、兼容多個碼率及碼長的、且易于硬件實現(xiàn)的QC-LDPC碼。該構(gòu)造方法通過正反向PEG算法來實現(xiàn)碼率兼容，并通過優(yōu)化循環(huán)移位參數(shù)的設(shè)計，彌補(bǔ)PEG算法自身存在的問題，更進(jìn)一步消除構(gòu)造矩陣中存在的短環(huán)。仿真結(jié)果表明了該方法構(gòu)造出來的QC-LDPC碼在幾種碼率下都具有較為突出的性能，且因為具有下三角結(jié)構(gòu)，更加便于硬件實現(xiàn)，尤其適合于硬件資源受限條件下，這為無人機(jī)今后在多種傳輸條件下的廣泛應(yīng)用提供了可能性。

[1] GALLAGER R G. Low-density parity-check codes[M].M.I.T. Press, 1963.

[2] 王琪，謝求亮，王昭誠.定碼長多碼率QC-LDPC碼的構(gòu)造[J].清華大學(xué)學(xué)報(自然科學(xué)版)，2013(3)：394-398.

[3] 朱鐵林，秦凡，李鳳翔,等.應(yīng)用于無人機(jī)測控傳輸系統(tǒng)的多元LDPC碼[J].電訊技術(shù)，2014(12)：1622-1626.

[4] LI J, NARAYANAN K R. Rate-compatible low density parity check codes for capacity-approaching ARQ scheme in packet data communications[C]//IASTED International Conference on Communications, 2002: 201-206.

[5] YAZDANI M R, BANIHASHEMI A H. On construction of rate-compatible low-density parity-check codes[J]. Communications Letters IEEE, 2004,8(3):159-161.

[6] 張建斌.基于PEG算法的準(zhǔn)循環(huán)LDPC碼構(gòu)造研究[J].電子器件，2012，35(6)：647-651.

[7] 賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

[8] VASIC B, DJORDJEVIC I B. Quasicyclic low-density parity check codes[C]//International Conference on Telecommunications in Modern Satellite, 2005: 417-420.

[9] FOSSORIER M. Quasicyclic low density parity check codes[C].Proceedings in IEEE International Symposium on Information Theory, Yokohama, Japan, 2003: 150-151.

[10] 管武，項海格.具有大碼間距和大環(huán)路的QC-LDPC碼的構(gòu)造[J].新能源進(jìn)展，2011，16(4)：1-5.

[11] XIAO H, BANIHASHEMI A H. Improved progressive-edge-growth (PEG) construction of irregular LDPC codes[C]//Global Telecommunications Conference, 2004. GLOBEC, 2004: 489-492.

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