, ,,2

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院 重慶高校市級光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室,重慶 400065;2.中國電子科技集團(tuán)第四十四研究所,重慶 400065)

0 概述

由于具有逼近Shannon限的糾錯性能[1],且譯碼復(fù)雜度較低,低密度奇偶校驗(yàn)(Low Density Parity Check,LDPC)碼一直是近年來編碼領(lǐng)域的研究熱點(diǎn),并被廣泛應(yīng)用在各類現(xiàn)代通信系統(tǒng)中。根據(jù)構(gòu)造方法的不同,LDPC碼[2]可分為隨機(jī)碼[3]和結(jié)構(gòu)化碼。隨機(jī)LDPC碼的編碼復(fù)雜度與碼長的平方成正比,且校驗(yàn)矩陣的硬件存儲復(fù)雜度高,尤其在碼長較長時不利于實(shí)際應(yīng)用。因此,需要設(shè)計性能優(yōu)越、校驗(yàn)矩陣具有一定結(jié)構(gòu)特性的LDPC碼。作為一種結(jié)構(gòu)化的LDPC碼,基于循環(huán)置換矩陣(Circulant Permutation Matrix,CPM)構(gòu)造的準(zhǔn)循環(huán)(Quasi Cyclic,QC)LDPC碼[4-5]由于其簡單靈活的設(shè)計方法引起了編碼領(lǐng)域的廣泛關(guān)注和研究。

雖然QC-LDPC碼具有存儲復(fù)雜度低、構(gòu)造靈活簡單等優(yōu)點(diǎn),然而傳統(tǒng)QC-LDPC碼的編碼仍然需要通過校驗(yàn)矩陣轉(zhuǎn)化成生成矩陣來實(shí)現(xiàn),由于生成矩陣中子矩陣不一定具備稀疏的特性,因此在硬件編碼實(shí)現(xiàn)時仍會占用大量存儲空間。為了降低QC-LDPC碼的編碼復(fù)雜度,文獻(xiàn)[6]提出了一種將校驗(yàn)矩陣的校驗(yàn)部分設(shè)計成近似下三角結(jié)構(gòu)的構(gòu)造方法,在編碼過程中可直接通過校驗(yàn)矩陣進(jìn)行迭代編碼,從而有效地降低了編碼復(fù)雜度。其中,IEEE 802.16e標(biāo)準(zhǔn)所采用的就是一種典型的采用準(zhǔn)雙對角線近似下三角結(jié)構(gòu)的QC-LDPC碼[7-8]。然而,其校驗(yàn)矩陣右半部分雙對角線上的子矩陣均是單位陣,這些確定性單位陣的存在不僅破壞了這類QC-LDPC碼的隨機(jī)性,使得碼字性能有一定的損失,而且導(dǎo)致一些基于組合設(shè)計、代數(shù)設(shè)計等確定性方法構(gòu)造大圍長QC-LDPC碼存在局限性。

針對上述問題,本文提出一種基于獨(dú)立行列映射序列(Independent Row-column Mapping Sequence,IRCMS)算法以及通過CPM的行列循環(huán)移位和掩碼技術(shù)來構(gòu)造圍長為8、可快速編碼的QC-LDPC碼的方法。該方法采用IRCMS算法構(gòu)造圍長為8的全局校驗(yàn)矩陣,然后通過CPM的行列循環(huán)移位使得校驗(yàn)部分的矩陣具有一定的半隨機(jī)結(jié)構(gòu)特性,最后利用掩碼技術(shù)得到一種改進(jìn)型的半隨機(jī)準(zhǔn)雙對角線結(jié)構(gòu)及可快速編碼的大圍長QC-LDPC碼。

1 大圍長QC-LDPC碼

基于CPM構(gòu)造的規(guī)則(J,L)QC-LDPC碼,列重為J,行重為L,其校驗(yàn)矩陣可表示如下[9]:

(1)

其中,1≤j≤J,1≤l≤L,0≤Pj,l

(2)

根據(jù)IRCMS算法[10],Pr,c=f(r,c)=g(r)h(c),其中,g(r)(r=1,2,…,J)和h(c)(c=1,2,…,L)分別為互異的非負(fù)整數(shù)序列。當(dāng)預(yù)先設(shè)定的序列h(c)已知時,只需要根據(jù)IRCMS算法搜索序列g(shù)(r),并且確定P的取值范圍,即可使得所構(gòu)造校驗(yàn)矩陣對應(yīng)Tanner圖[11]的圍長至少為8。

IRCMS算法的步驟如下:

輸入列重J和序列h={h1,h2,…,hL}

輸出序列g(shù)={g1,g2,…,gJ}

初始化g初始化為{0,1},令j=0。

步驟1如果j<(J-2),則轉(zhuǎn)至步驟2;否則結(jié)束,搜索完成。

步驟2令Y=t+1(t等于當(dāng)前g中最后一個元素的值)。

步驟3在當(dāng)前集合g中遍歷地選取任意2個不相同數(shù)g(i)和g(j),如果對于當(dāng)前h中任意3個{hl,hm,hn}∈h都滿足:

(Y-g(i))(hn-hl)=(g(j)-g(i))(hm-hl)

(3)

那么設(shè)置flag=1;否則,設(shè)置flag=0。

步驟4如果flag=1,令Y=Y+1,返回至步驟3;如果flag=0,令g=g∪Y,j=j+1,返回至步驟1。

由上可知,指數(shù)矩陣E可以由IRCMS算法所確定,根據(jù)文獻(xiàn)[12]中的定理1可知,當(dāng)循環(huán)置換矩陣的維數(shù)P滿足:P>gmaxhmax時,所構(gòu)造的QC-LDPC碼對應(yīng)Tanner圖的圍長至少為8。

2 可快速編碼的大圍長QC-LDPC碼設(shè)計

2.1 校驗(yàn)矩陣的構(gòu)造方法

本節(jié)給出一種可快速編碼的大圍長QC-LDPC碼構(gòu)造方法。該方法首先基于IRCMS算法構(gòu)造圍長為8的全局校驗(yàn)矩陣,然后采用CPM的行列循環(huán)移位使得校驗(yàn)部分的子矩陣排列滿足一定的結(jié)構(gòu)特性,最后對所得矩陣進(jìn)行掩碼處理得到具有改進(jìn)型準(zhǔn)雙對角線結(jié)構(gòu)的校驗(yàn)矩陣。

1)基于IRCMS算法構(gòu)造圍長為8的初始校驗(yàn)矩陣,并且將全局校驗(yàn)矩陣分成如下部分:

(4)

其中,Hk由P×P維CPM的行列循環(huán)移位構(gòu)成的M×(N-M)矩陣陣列,對應(yīng)于校驗(yàn)矩陣H的信息位部分,Hp是由P×P的CPM構(gòu)成M×M的矩陣陣列,對應(yīng)于校驗(yàn)矩陣H的校驗(yàn)位部分。

本文所提出的改進(jìn)型雙對角結(jié)構(gòu)Hp矩陣如下:

(5)

其中,hi,j表示校驗(yàn)部分矩陣Hp的第i行、第j列的子矩陣,當(dāng)0

2)對H矩陣的最后三行的CPM向右循環(huán)移位。其中,Sr(i)表示對第i行的CPM同時向右循環(huán)移位Sr(i)位,i=M-2,M-1,M:

(6)

然后,對Hp矩陣第2列至第M-2列的CPM分別同時向左循環(huán)移位。其中,Sc(i)表示對Hp矩陣的第i列CPM同時向左循環(huán)移Sc(i)位,i=2,3,…,M-2:

Sc(i)=Ep(i-1,i)

(7)

定理1基矩陣E中存在序列(p1,p2,…,p2l),其中任意兩相鄰元素pi和pi+1(包括p1和p2l)位于同一行或者同一列,不相鄰元素位于不同行且不同列,則該序列構(gòu)成長度為2l的環(huán)的充分必要條件為[12]:

(8)

引理1如果基于CPM構(gòu)造的QC-LDPC碼沒有四環(huán)、六環(huán)存在,則對其校驗(yàn)矩陣的若干行或列的CPM分別同時循環(huán)移位,若同行或者同列的CPM移位位數(shù)相同,該矩陣無四環(huán)、六環(huán)產(chǎn)生。

證明:

1) 若基于CPM構(gòu)造的QC-LDPC碼的校驗(yàn)矩陣無四環(huán),根據(jù)定理1,對如圖1(a)所示的任意的兩行(i,j)、兩列(m,n),有:

Pi,m-Pi,n+Pj,n-Pj,m≠0(modP)

(9)

對其校驗(yàn)矩陣的若干行或列的CPM分別同時向左或向右循環(huán)移位。首先,對如圖1(a)所示的兩行CPM分別同時進(jìn)行循環(huán)移S1、S2位,則如圖1(b)所示的四環(huán)存在充要條件為:

(Pi,m+S1)-(Pi,n+S1)+(Pj,n+S2)-

(Pj,m+S2)=0(modP)

(10)

即:

Pi,m-Pi,n+Pj,m-Pj,n=0(modP)

(11)

但上式與式(9)矛盾,故四環(huán)存在條件不滿足,即該校驗(yàn)矩陣沒有四環(huán)的存在。同理,對如圖1(a)所示的兩列CPM分別同時進(jìn)行循環(huán)移S1、S2位,則圖1(c)所示的四環(huán)存在條件亦不滿足。故對校驗(yàn)矩陣的若干行或列CPM同時進(jìn)行循環(huán)移位,若同行或者同列的CPM移位位數(shù)相同,不會產(chǎn)生四環(huán)。

圖1 四環(huán)的不存在性示意圖

2) 若基于CPM構(gòu)造的QC-LDPC碼的校驗(yàn)矩陣無六環(huán),則根據(jù)定理1,對圖2(a)所示的任意的三行(i,j,k)、兩列(m,n,l),有:

Pi,m-Pi,n+Pj,n-Pj,l+Pk,l-Pk,m≠0(modP)

(12)

對校驗(yàn)矩陣若干行或列的CPM分別同時進(jìn)行循環(huán)移位,對如圖2(a)所示的三行CPM同時循環(huán)移S1、S2、S3位后,如圖2(b)所示的六環(huán)存在充要條件為:

(Pi,m+S1)-(Pi,n+S1)+(Pj,n+S2)-

(Pj,l+S2)+(Pk,l+S3)-(Pk,m+S3)=

0(modP)

(13)

即:

Pi,m-Pi,n+Pj,n-Pj,l+Pk,l-Pk,m=0(modP)

(14)

但上式與式(12)矛盾,故六環(huán)存在條件不滿足,則校驗(yàn)矩陣沒有六環(huán)。同理,對如圖2(a)所示的三列CPM分別同時進(jìn)行循環(huán)移S1、S2、S3位,則如圖2(c)所示的六環(huán)存在條件亦不滿足。故校驗(yàn)矩陣的若干行或列的CPM分別同時進(jìn)行循環(huán)移位后,若同行或者同列的CPM移位位數(shù)相同,無六環(huán)產(chǎn)生。引理1證畢。

圖2 六環(huán)的不存在性示意圖

由引理1可知,上述行列循環(huán)移位操作不會使得校驗(yàn)矩陣產(chǎn)生四環(huán)、六環(huán),即不改變所構(gòu)造的全局校驗(yàn)矩陣的四環(huán)、六環(huán)特性。

3)對經(jīng)過行列循環(huán)移位后的H矩陣進(jìn)行掩碼處理。掩碼技術(shù)通常被簡單地用來采用一些全零矩陣替換相應(yīng)位置P×P的CPM。對于一個由P×P的CPM所構(gòu)成的M×N矩陣陣列H而言,設(shè)M(M,N)=(mj,l)0≤j

M?H=(mj,l·Hj,l)0≤j

(15)

如果mj,l=1,則mi,j·Hi,j=I(Pi,j);否則mj,l·Hj,l為P×P的I(-1)矩陣,即P×P的零矩陣。

為了使得最終所構(gòu)造的校驗(yàn)矩陣右半部分滿足式(5)所示結(jié)構(gòu),則M矩陣對應(yīng)于Hp部分的Mp如下:

(16)

QC-LDPC碼校驗(yàn)矩陣的較優(yōu)行重分布為近似相等的二三個連續(xù)行重值[13]。由于Mp的行重為近似相等的2個值,因此為了在得到一個稀疏矩陣H的同時,優(yōu)化碼字的度分布,則掩碼矩陣M的左半部分Mk的行重也需近似相等,從而使得所構(gòu)造校驗(yàn)矩陣H的行重為近似相等的二三個數(shù)值。

由于基于IRCMS算法構(gòu)造圍長為8的H矩陣沒有四環(huán)、六環(huán),因此經(jīng)過掩碼處理后的H亦不會有四環(huán)、六環(huán)[14]。所以,本文基于IRCMS算法、行列循環(huán)置換和掩碼技術(shù)構(gòu)造的可快速編碼QC-LDPC碼字保持了大圍長特性。

2.2 快速編碼算法與編碼復(fù)雜度分析

C=[S,P]

(17)

由于編碼向量C為校驗(yàn)矩陣H的零空間,則在GF(2)域中可得:

(18)

根據(jù)式(5)的前M-3行結(jié)構(gòu),首先依次迭代至式(18)的第1行到第M-3行:

(19)

則可得校驗(yàn)位向量Pi(i=2,3,…,M-2):

(20)

然后,迭代至式(18)的第M-2行至第M行:

(21)

將式(21)中3個等式相加,可得:

(22)

將式(22)代入到式(21)中,即可得:

(23)

編碼復(fù)雜度主要關(guān)注編碼過程的運(yùn)算量、運(yùn)算復(fù)雜度和編碼所需存儲的參數(shù),運(yùn)算量即乘法和加法次數(shù),運(yùn)算復(fù)雜度即運(yùn)算量與碼長的變化關(guān)系。QC-LDPC碼的各個子矩陣都是稀疏矩陣,因此按照稀疏矩陣的運(yùn)算方式可大大減小運(yùn)算量。計算式(22)、式(23)中Pi的運(yùn)算量如表1所示。

表1 編碼算法的運(yùn)算量

在表1中,R表示碼率,N表示擴(kuò)展之后的碼長,N=n×p,P表示校驗(yàn)矩陣中CPM的維數(shù)。

從表 1 可明顯地看到,計算各個校驗(yàn)分向量Pi的運(yùn)算復(fù)雜度為O(N),即運(yùn)算復(fù)雜度與碼長呈線性關(guān)系。因此,本節(jié)基于改進(jìn)型準(zhǔn)雙對角結(jié)構(gòu)構(gòu)造的可快速編碼QC-LDPC碼具有完全線性的編碼復(fù)雜度,編碼效率很高。

3 性能仿真與分析

本節(jié)通過仿真將本文構(gòu)造的圍長為8、可快速編碼的QC-LDPC碼,與采用IRCMS算法構(gòu)造圍長為8的規(guī)則QC-LDPC碼、基于PEG算法構(gòu)造的QC-LDPC碼[15-16]和基于改進(jìn)型DVB-S2碼[17]的性能分別做比較。仿真是在加性高斯白噪聲(Additive White GaussNoise,AWGN)信道下進(jìn)行,采用二進(jìn)制相移鍵控(Binary Phase Shift Keying,BPSK)方式進(jìn)行調(diào)制,采用置信傳播(Belief Propagation,BP)算法進(jìn)行譯碼,設(shè)置最大迭代次等于100。

首先,設(shè)置h={0,1,2,3,4,6,7,8,9,10},J=5。根據(jù)IRCMS算法,產(chǎn)生序列g(shù)={0,1,11,12,25}。由P>gmaxhmax取P=300。然后,根據(jù)式(6)和式(7)對所構(gòu)造的H矩陣進(jìn)行CPM的行列循環(huán)移位。最后,對CPM行列循環(huán)移位后的矩陣進(jìn)行掩碼處理。所采用的掩碼矩陣如下:

(24)

1)當(dāng)設(shè)置P=300時,由上述指數(shù)矩陣E=[Ek,Ep]可構(gòu)造圍長為8、可快速編碼的(3 000,1 500)QC-LDPC碼。本文構(gòu)造的不規(guī)則(3 000,1 500)QC-LDPC碼與文獻(xiàn)[15]中基于IRCMS算法構(gòu)造圍長為8的(3 000,1 500)規(guī)則QC-LDPC碼的誤碼率(Bit Error Rate,BER)和誤幀率(Frame Error Rate,FER)性能對比如圖3所示。

圖3本文所構(gòu)造的碼字與采用IRCMS算法構(gòu)造的規(guī)則QC-LDPC碼的BER和FER性能對比

由圖3可知,本文構(gòu)造的可快速編碼QC-LDPC碼譯碼的性能明顯優(yōu)于基于IRCMS算法構(gòu)造的圍長為8的規(guī)則QC-LDPC碼,在BER為10-5時,在編碼復(fù)雜度更低的基礎(chǔ)上,有0.15 dB左右的編碼增益。

將本文所構(gòu)造的不規(guī)則(3 000,1 500)QC-LDPC碼與基于PEG算法構(gòu)造的相同碼長、碼率、度分布的不規(guī)則QC-LDPC碼和圍長為6的隨機(jī)QC-LDPC碼進(jìn)行比較。由圖4可知,本文所構(gòu)造的碼字與基于PEG算法構(gòu)造的不規(guī)則QC-LDPC碼性能相當(dāng),且本文所構(gòu)造的碼字具有完全線性的編碼復(fù)雜度,編碼復(fù)雜度更低。與圍長為6的隨機(jī)QC-LDPC碼相比,本文所構(gòu)造的碼字具有更加優(yōu)越的性能,在誤碼率達(dá)到10-5時,碼字性能有0.2 dB的提升。

圖4本文所構(gòu)造的碼字與基于PEG算法構(gòu)造的QC-LDPC碼和隨機(jī)QC-LDPC碼的BER性能對比

2)當(dāng)設(shè)置P=540時,可構(gòu)造圍長為8、可快速編碼的(5 400,2 700)QC-LDPC碼,將這種碼字與文獻(xiàn)[17]中改進(jìn)型DVB-S2碼相比,其仿真結(jié)果如圖5所示。

圖5本文所構(gòu)造的碼字與改進(jìn)型DVB-S2碼字的BER性能對比

由圖5可知,與文獻(xiàn)[17]中改進(jìn)型的DVB-S2碼相比,本文所構(gòu)造的可快速編碼的QC-LDPC碼不僅同樣具有可快速編碼特性,而且性能有了一定的提升,在誤碼率達(dá)到10-5時,其碼字性能提高了0.1 dB左右。

4 結(jié)束語

本文基于IRCMS算法、CPM的行列循環(huán)移位以及掩碼技術(shù)提出一種圍長為8、可快速編碼的QC-LDPC碼構(gòu)造方法。該方法所構(gòu)造的QC-LDPC碼不僅保持了圍長至少為8的特性,而且還可以利用該改進(jìn)型準(zhǔn)雙對角線結(jié)構(gòu)的校驗(yàn)矩陣直接進(jìn)行簡單快速的編碼,在保證優(yōu)異性能的同時,降低了QC-LDPC碼的編碼復(fù)雜度。仿真結(jié)果表明,本文所構(gòu)造的碼字不僅具有線性的編碼復(fù)雜度,而且性能較優(yōu)。與已有的確定性構(gòu)造方法相比,該方法是一種基于計算機(jī)搜索的構(gòu)造方法,雖然比較靈活,但為滿足各種約束條件,沒有解決碼的存在性問題,存在構(gòu)造失敗的可能性,下一步將針對上述問題進(jìn)行改進(jìn)。

[1] MACKAY D J C,NEAL R M.Near Shannon Limit Performance of Low Density Parity Check Codes[J].Electronics Letters,1996,32(18):1645-1646.

[2] GALLAGER R G.Low-density Parity-check Codes[J].IRE Transactions on Information Theory,1962,8(1):21-28.

[3] MACKAY D J C.Good Error-correcting Codes Based on Very Sparse Matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[4] 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.

[5] 焦新泉,陳建軍,單彥虎.基于 BIBD 和循環(huán)置換矩陣的 LDPC碼[J].計算機(jī)工程,2012,38(2):282-283.

[6] MYUNG S,YANG K,KIM J.Quasi-cyclic LDPC Codes for Fast Encoding[J].IEEE Transactions on Information Theory,2005,51(8):2894-2901.

[7] WANG H,CHEN S,ZHU C,et al.A Novel QC-LDPC Code with Flexible Construction and Low Error Floor[C]//Proceedings of the 16th International Conference on Advanced Communication Technology.Washington D.C.,USA:IEEE Press,2014:431-436.

[8] IEEE.Part 16:Air Interface for Fixed and Mobile Broadband Wireless Access Systems[S].New York,USA:Institute of Electrical and Electronics Engineering,2006.

[9] WANG R,LI Y,ZHAO H,et al.Construction of Girth-eight Quasi-cyclic Low-density Parity-check Codes with Low Encoding Complexity[J].IET Communications,2016,10(2):148-153.

[10] WANG L,ZHANG X,YU F,et al.QC-LDPC Codes with Girth Eight Based on Independent Row-column Mapping Sequence[J].IEEE Communications Letters,2013,17(11):2140-2143.

[11] TANNER R M.A Recursive Approach to Low Complexity Codes[J].IEEE Transactions on Information Theory,1981,27(5):533-547.

[12] 彭 立,朱光喜.QC-LDPC 碼的置換矩陣循環(huán)移位次數(shù)設(shè)計[J].電子學(xué)報,2010,38(4):786-790.

[13] KANG J,HUANG Q,ZHANG L,et al.Quasi-cyclic LDPC Codes:An Algebraic Construction[J].IEEE Transactions on Communications,2010,58(5):1383-1396.

[14] KAMIYA N.Efficiently Encodable Irregular QC-LDPC Codes Constructed from Self-reciprocal Generator Polynomials of MDS Codes[J].IEEE Communications Letters,2010,14(9):1-3.

[15] LI Z,KUMAR K V.A Class of Good Quasi-cyclic Low-density Parity Checks Code Based on Progressive Edge Growth Graph [C]//Proceedings of Conference on Signals,Systems & Computers.Washington D.C.,USA:IEEE Press,2004:1990-1994.

[16] JIANG X,XIA X G,LEE M H.Efficient Progressive Edge-growth Algorithm Based on Chinese Remainder Theorem[J].IEEE Transactions on Communications,2014,62(2):442-451.

[17] 肖 揚(yáng),范 俊,黃 希.DVB-S2標(biāo)準(zhǔn)的LDPC碼改進(jìn)[J].鐵道學(xué)報,2011,33(2):52-59.