一種可快速編碼的QC-LDPC碼構(gòu)造新方法

劉原華 ,張美玲

(西安郵電大學(xué)通信與信息工程學(xué)院,西安710121)

1 引 言

低密度奇偶校驗(yàn)碼(LDPC碼)具有逼近Shannon限的糾錯(cuò)性能,近年來成為編碼領(lǐng)域的研究熱點(diǎn),目前已廣泛應(yīng)用于深空通信、光纖通信和衛(wèi)星數(shù)字視頻廣播等領(lǐng)域。根據(jù)構(gòu)造方法的不同,可將LDPC碼分為兩大類:隨機(jī)LDPC碼和結(jié)構(gòu)化LDPC碼。隨機(jī)LDPC碼的編碼復(fù)雜度與碼長的平方成正比,且校驗(yàn)矩陣的硬件存儲(chǔ)也較為復(fù)雜,這已成為LDPC碼實(shí)用化的一個(gè)瓶頸。為了實(shí)用的目的,需要設(shè)計(jì)性能優(yōu)良、校驗(yàn)矩陣具有一定結(jié)構(gòu)特性的 LDPC碼?；谘h(huán)置換矩陣的QC-LDPC碼[1-2]是一種結(jié)構(gòu)化LDPC碼,已經(jīng)得到編碼領(lǐng)域?qū)W者的研究和關(guān)注。

基于循環(huán)置換矩陣的QC-LDPC碼的校驗(yàn)矩陣由循環(huán)置換矩陣構(gòu)成,通過恰當(dāng)?shù)剡x擇循環(huán)置換矩陣可以避免相應(yīng)Tanner圖中的短環(huán)。文獻(xiàn)[3]和[4]分別利用歐氏幾何和有限域的特性構(gòu)造出了不包含4環(huán)的性能優(yōu)異的QC-LDPC碼。值得注意的是,該類碼的設(shè)計(jì)不僅需要避免短環(huán),還需要考慮校驗(yàn)矩陣的行相關(guān)問題。文獻(xiàn)[5]在提出了一種QC-LDPC碼構(gòu)造方法的同時(shí)分析了校驗(yàn)矩陣的行相關(guān)問題。一般設(shè)計(jì)的QC-LDPC碼并不能保證校驗(yàn)矩陣的滿秩,即存在行相關(guān)問題,而校驗(yàn)矩陣的行相關(guān)問題將會(huì)導(dǎo)致構(gòu)造生成矩陣非常困難[6]。為解決行相關(guān)問題,IEEE 802.16e標(biāo)準(zhǔn)中采用具有特殊結(jié)構(gòu)的QCLDPC碼,其校驗(yàn)矩陣的右半部分具有準(zhǔn)雙對角線結(jié)構(gòu),滿足非奇異性,即滿秩,并且可直接利用校驗(yàn)矩陣進(jìn)行編碼,具有很低的編碼復(fù)雜度。然而,IEEE 802.16e標(biāo)準(zhǔn)中的LDPC碼校驗(yàn)矩陣右半部分雙對角線上的子矩陣均是單位陣,限制得較為嚴(yán)格,使很多好碼被排除在外。綜合考慮以上兩方面,本文利用已有的基于循環(huán)置換矩陣的QC-LDPC碼,通過打孔和行置換,獲得了一大類性能優(yōu)異且可實(shí)現(xiàn)快速編碼的QC-LDPC碼。與IEEE 802.16e標(biāo)準(zhǔn)中的LDPC碼相比,本文構(gòu)造出的QC-LDPC碼具有相同的編碼復(fù)雜度,且具有更優(yōu)的糾錯(cuò)性能。

2 基于循環(huán)置換矩陣的QC-LDPC碼

基于循環(huán)置換矩陣的QC-LDPC碼的校驗(yàn)矩陣H由循環(huán)置換矩陣和零矩陣組成:

式中,aij∈{-1,0,1,2,…,n-1},Iaij為一個(gè)n×n的循環(huán)置換矩陣,可由單位陣 I每行向右循環(huán)移位aij位得到,I-1表示全零矩陣。H的零空間即為碼長為N=nρ的QC-LDPC碼。每個(gè)循環(huán)置換矩陣均可由其維數(shù)n和循環(huán)移位次數(shù)aij唯一確定,因此 H所需的存儲(chǔ)空間非常小。矩陣 H的基矩陣Hb定義為如下γ×ρ矩陣:

將 Hb中的aij用n×n的循環(huán)置換矩陣Iaij代替,即可得到矩陣H,稱為矩陣擴(kuò)展。

Tanner等在文獻(xiàn)[1]中構(gòu)造的LDPC碼就是一種基于循環(huán)置換矩陣的QC-LDPC碼,對任意素?cái)?shù) p,選取域GF(p)中的非零元素a和b,a和b的階分別為k和j,Tanner構(gòu)造的QC-LDPC碼的基矩陣如式(3),校驗(yàn)矩陣可由基矩陣擴(kuò)展得到,即將基矩陣中的每一元素用對應(yīng)的p×p的循環(huán)置換矩陣代替。

3 可快速編碼的QC-LDPC碼設(shè)計(jì)

IEEE 802.16e標(biāo)準(zhǔn)中的QC-LDPC碼是一種基于循環(huán)置換矩陣的QC-LDPC碼,校驗(yàn)矩陣可由其基矩陣擴(kuò)展得到,且校驗(yàn)矩陣的右半部分具有準(zhǔn)雙對角線結(jié)構(gòu),保證了校驗(yàn)矩陣的滿秩,同時(shí)可直接利用校驗(yàn)矩陣進(jìn)行編碼。然而,IEEE 802.16e標(biāo)準(zhǔn)中QC-LDPC碼的校驗(yàn)矩陣右半部分雙對角線上的子矩陣均是單位陣,要求比較嚴(yán)格,很多好碼被排除在外。事實(shí)上,可以證明,若校驗(yàn)矩陣的右半部分具有準(zhǔn)雙對角線結(jié)構(gòu),則只要保證雙對角線上同一塊列的子矩陣相同,即可使校驗(yàn)矩陣滿秩,并可直接利用校驗(yàn)矩陣進(jìn)行低復(fù)雜度的迭代編碼。由此,提出了一種具有如此結(jié)構(gòu)的校驗(yàn)矩陣的設(shè)計(jì)方法,從而獲得可實(shí)現(xiàn)低編碼復(fù)雜度的QC-LDPC碼。下面進(jìn)行詳細(xì)說明。

將具有上述結(jié)構(gòu)的校驗(yàn)矩陣分成兩部分:

其中,H1的維數(shù)為m×k(m=pmb,k=pkb),H2的維數(shù)為m×m,且 H2具有式(5)形式,其中 Ix在H2的第r塊行,可以證明H2滿秩。

定理1 具有式(5)形式的矩陣是滿秩的。

證明:以塊為單位,從下往上將分塊矩陣H2的各塊行與其后的所有塊行進(jìn)行模2加得到一個(gè)新的塊行,該變換實(shí)際上是對矩陣H2做初等行變換:

許多文獻(xiàn)[1-4]提出了基于循環(huán)置換矩陣的QCLDPC碼的構(gòu)造方法,構(gòu)造出的校驗(yàn)矩陣是非滿秩的,致使由校驗(yàn)矩陣構(gòu)造生成矩陣非常困難。為降低LDPC碼的編碼實(shí)現(xiàn)復(fù)雜度,本文提出了一種新的可實(shí)現(xiàn)快速編碼的QC-LDPC碼構(gòu)造方法,該方法在原始校驗(yàn)矩陣的基礎(chǔ)上利用打孔和行置換操作,使校驗(yàn)矩陣的右半部分具有式(5)的形式,從而保證所構(gòu)造的校驗(yàn)矩陣滿秩,可直接利用校驗(yàn)矩陣進(jìn)行低復(fù)雜度編碼。圖1給出了新構(gòu)造方法的實(shí)現(xiàn)流程圖。

圖1 新構(gòu)造方法的流程圖Fig.1 Flowchart of the new design method

以M為校驗(yàn)矩陣,其零空間即為可快速編碼的QC-LDPC碼。其中第一步中,可利用已有的各種基于循環(huán)置換矩陣的QC-LDPC碼構(gòu)造方法來獲得原始矩陣H。

第二步中打孔矩陣Z的構(gòu)造方法如下:若矩陣H為由子矩陣組成的γ×ρ的矩陣陣列,則打孔矩陣Z=[zij]為GF(2)上的 γ×ρ矩陣,將Z分成兩部分Z=[Z1Z2],其中 Z2為具有式(8)的形式的 γ×γ矩陣,第一列中間的1在第 r行,Z1為全1矩陣。

第三步中的打孔過程可以看作是一種特殊的矩陣乘法運(yùn)算,矩陣陣列H的打孔定義為GF(2)上的打孔矩陣Z與H的乘積:

若 zij=1,則zijHij=Hij;若 zij=0,則 zijHij=0 為全零矩陣。可以看出,如果 Z中含有0元素,則打孔后的矩陣M更稀疏;如果 H不包含四環(huán),則 M也不包含四環(huán)。

下面給出如何對M 進(jìn)行循環(huán)移位使其右半部分具有式(5)的形式。記矩陣M=[M1M2]的右半部分M2第 i行j列的子矩陣為M2(i,j),以塊為單位,將M的第i塊行向左循環(huán)移S(i)位,其中S(1)=0,S(i)=M2(i,i)-M2(i-1,i)+S(i-1),2≤i≤γ,同時(shí)令 M2(γ,1)=M2(1,1),則可使 M2具有式(5)的形式,即可保證矩陣M滿秩,并可直接利用M進(jìn)行迭代編碼。由于M的子矩陣為循環(huán)置換矩陣,這樣的循環(huán)移位僅相當(dāng)于對M 做行置換,將循環(huán)移位前后的M作為校驗(yàn)矩陣所獲得的QC-LDPC碼的糾錯(cuò)性能完全相同。

下面給出如何直接利用M進(jìn)行簡單快速編碼。對于系統(tǒng)碼,碼字向量可表示為c=[s p],其中s=[s1s2…skb]為信息向量,p=[p1p2…pmb]為校驗(yàn)向量,且 si和pi的長度均為p。由M·cT=0可得M1·sT=M2·pT。記Mb1為 M1的基矩陣,第 i行第j列的元素為Mb1(i,j),則

上式展開可得含mb個(gè)等式的方程組,各式相加可得

將式(11)代入式(10)中的每個(gè)等式可得

式(11)～(13)為計(jì)算pi的迭代公式,從而得到校驗(yàn)向量 p。下面考慮編碼復(fù)雜度,矩陣Ia為循環(huán)置換矩陣,每行每列僅有一個(gè)1,因此式(11)～(13)的主要計(jì)算量在于,由此可知,求校驗(yàn)向量的計(jì)算量與802.16e標(biāo)準(zhǔn)中求校驗(yàn)向量的計(jì)算量相同。

4 仿真結(jié)果

本節(jié)采用BPSK調(diào)制下的加性高斯白噪聲信道(AWGN),仿真比較新方法構(gòu)造的QC-LDPC碼和IEEE 802.16e標(biāo)準(zhǔn)中的QC-LDPC碼在置信傳播(BP)譯碼算法下的糾錯(cuò)性能,BP算法的最大迭代次數(shù)均設(shè)為50次。

圖2顯示了1/2碼率的新方法構(gòu)造碼與IEEE 802.16e中的碼的BER性能。新構(gòu)造方法的第一步選用文獻(xiàn)[1]中的構(gòu)造方法,碼(696,348)的構(gòu)造參數(shù)如下:p=29,a=2,b=3,a和b的階均為28,由此可構(gòu)造出子矩陣組成的28×28的矩陣陣列,選前12行24列子矩陣作為碼(696,348)的原始矩陣 H。碼(2328,1164)的構(gòu)造參數(shù)如下:p=97,a=2,b=3,a和b的階均為48,由此可構(gòu)造出48×48的矩陣陣列,選前12行24列子矩陣作為碼(2328,1164)的原始矩陣 H。為增強(qiáng)可比性,打孔矩陣 Z的構(gòu)造如下:將1/2碼率的IEEE 802.16e碼的基矩陣中的-1用0代替,非-1用1代替得到的矩陣為打孔矩陣Z。打孔后得到具有準(zhǔn)雙對角線結(jié)構(gòu)的滿秩矩陣M。然后以塊為單位,將M的第i塊行向左循環(huán)移S(i)位,最后令M2(γ,1)=M2(1,1)。M 的零空間即為構(gòu)造的QC-LDPC碼。

圖2 新方法構(gòu)造碼與IEEE 802.16e碼的BER性能Fig.2 Performance of the new codes and the codesin IEEE 802.16e

由仿真結(jié)果可以看出,新方法構(gòu)造的碼BER性能略優(yōu)于IEEE 802.16e中的碼。由上一小節(jié)中編碼實(shí)現(xiàn)的分析可知,新方法構(gòu)造的碼與IEEE 802.16e中的碼具有相同的編碼復(fù)雜度,即新方法構(gòu)造的碼在保證低編碼復(fù)雜度的基礎(chǔ)上獲得了更優(yōu)的糾錯(cuò)性能。同時(shí)需要指出的是,IEEE 802.16e標(biāo)準(zhǔn)中的碼結(jié)構(gòu)限制得較為嚴(yán)格,使很多好碼被排除在外,新方法可以在任意已有的基于循環(huán)置換矩陣的構(gòu)造方法基礎(chǔ)上進(jìn)行打孔和行置換操作,從而可以構(gòu)造出一大類性能優(yōu)異的可實(shí)現(xiàn)快速編碼的QC-LDPC碼。

5 結(jié)束語

本文研究了基于循環(huán)置換矩陣的QC-LDPC碼構(gòu)造方法,發(fā)現(xiàn)已有的大部分設(shè)計(jì)方法構(gòu)造的QCLDPC碼存在校驗(yàn)矩陣的行相關(guān)問題,導(dǎo)致編碼復(fù)雜度較高。由此,提出了一種新的可快速編碼的QCLDPC碼構(gòu)造方法,在已有的各種基于循環(huán)置換矩陣的QC-LDPC碼構(gòu)造方法基礎(chǔ)上,通過打孔和行置換,使校驗(yàn)矩陣具有準(zhǔn)雙對角線結(jié)構(gòu),可以利用校驗(yàn)矩陣直接進(jìn)行簡單快速的編碼,在保證優(yōu)異性能的同時(shí),降低了LDPC碼的硬件實(shí)現(xiàn)復(fù)雜度。同時(shí)給出了簡單快速編碼的具體實(shí)現(xiàn)方法,并分析比較了編碼實(shí)現(xiàn)復(fù)雜度。仿真結(jié)果表明,與IEEE 802.16e標(biāo)準(zhǔn)中的LDPC碼相比,新方法構(gòu)造出的QC-LDPC碼在保證低編碼復(fù)雜度的基礎(chǔ)上獲得了更優(yōu)的糾錯(cuò)性能。

[1]Tanner R M,Sridhara D,Sridharan A,et al.LDPC block and convolutional codes based on circulant matrices[J].IEEE Transactions on Information Theory,2004,50(12):2966-2984.

[2]Fossorier M P C.Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J].IEEE Transactions on Information Theory,2004,50(8):1788-1793.

[3]Liu Yuanhua,Niu Xinliang,Wang Xinmei,et al.Design of quasi-cyclic LDPC codes based on Euclidean geometries[J].Journal of Electronics(China),2010,27(3):340-344.

[4]Zhang L,LinS,Abdel-Ghaffar K,et al.Quasi-cyclic LDPC codes on cyclic subgroups of finite fields[J].IEEE Transactions on Communications,2011,59(9):2330-2336.

[5]Liu K,Huang Q,LinS,et al.Quasi-cyclic LDPC codes:Construction and rank analysis of their parity-check matrices[C]//Proceedings of 2012Information Theory and Applications Workshop(IT A).San Diego,CA:IEEE,2012:227-233.

[6]Zhao Ying,Xiao Yang.The necessary and sufficient condition of a class of quasi-cyclic LDPC codes without girth four[J].IEICE Transactions on Communications,2009,92(1):306-309.