基于Fibonacci-Lucas序列構(gòu)造大圍長(zhǎng)QC-LDPC碼的方法

袁建國(guó)，曾 晶,袁 夢(mèng)，范福卓，劉家齊，鄭德猛

(重慶郵電大學(xué) 光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

生活在當(dāng)今信息時(shí)代，人們?cè)谠S多領(lǐng)域如政治、經(jīng)濟(jì)、軍事、科技方面都需要可靠有效地傳輸信息，現(xiàn)代的數(shù)字通信系統(tǒng)基本上都使用了信道糾錯(cuò)編碼技術(shù)。低密度奇偶校驗(yàn)(low-density parity-check, LDPC)碼是一種誤差糾正技術(shù)，可適用于不同信道范圍。LDPC碼應(yīng)用十分廣泛，諸如無(wú)線局域網(wǎng)通信、深空宇航通信、數(shù)字水印技術(shù)、磁性記錄信道、超高速光纖傳輸?shù)萚1]，其實(shí)際意義和經(jīng)濟(jì)價(jià)值很大。

根據(jù)LDPC碼特點(diǎn)，能從不同的角度進(jìn)行分類，結(jié)構(gòu)化構(gòu)造和隨機(jī)構(gòu)造就是按照其校驗(yàn)矩陣的特性進(jìn)行分類，漸進(jìn)邊增長(zhǎng)(progressive edge growth, PEG)構(gòu)造法是隨機(jī)構(gòu)造中的一種，為了增加其Tanner圖的邊而采用計(jì)算機(jī)搜尋方式，正由于其校驗(yàn)矩陣的隨機(jī)可變，并且有著高的計(jì)算復(fù)雜度，所以實(shí)踐中應(yīng)用并不廣泛。而結(jié)構(gòu)化構(gòu)造LDPC碼，對(duì)比于隨機(jī)構(gòu)造，復(fù)雜度低出很多，同時(shí)十分有利于實(shí)踐應(yīng)用，因而受到廣泛關(guān)注[2-4]。準(zhǔn)循環(huán)LDPC (quasi-cyclic LDPC, QC-LDPC)碼是一種由單位矩陣循環(huán)置換后的矩陣構(gòu)成的陣列，僅僅需要數(shù)量較少的存儲(chǔ)器存儲(chǔ)它們的奇偶校驗(yàn)矩陣，它們的結(jié)構(gòu)性質(zhì)比隨機(jī)性更加容易分析,它們能在實(shí)踐中方便簡(jiǎn)單的實(shí)現(xiàn)[5-7]。LDPC碼Tanner圖的周期結(jié)構(gòu)對(duì)糾錯(cuò)性能有很大影響，其Tanner圖中最小環(huán)長(zhǎng)稱為圍長(zhǎng)，由于小圍長(zhǎng)會(huì)使得譯碼過(guò)程中信息在迭代之后互相關(guān)，影響到了譯碼收斂性能[8-10]，因此，自LDPC研究以來(lái)，就有大量的工作投入用于設(shè)計(jì)較大圍長(zhǎng)的LDPC碼[11]。

本文基于斐波那契-盧卡斯序列并結(jié)合文獻(xiàn)[12]中三角旋轉(zhuǎn)法構(gòu)造出的QC-LDPC碼，計(jì)算復(fù)雜度低且不存在四環(huán)和六環(huán)，硬件實(shí)現(xiàn)簡(jiǎn)單，經(jīng)Matlab軟件仿真后，進(jìn)行對(duì)比分析，表明該碼字性能比基于Fibonacci數(shù)列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造出來(lái)的QC-LDPC碼更好，同時(shí)也好于基于盧卡斯數(shù)列無(wú)四六環(huán)構(gòu)造方法構(gòu)造出來(lái)的QC-LDPC碼[13]和基于等差數(shù)列(arithmetic progression sequence, APS)構(gòu)造的QC-LDPC碼。

1 斐波那契-盧卡斯序列簡(jiǎn)介

1.1 斐波那契-盧卡斯序列的定義

斐波那契序列定義：數(shù)列F(n)分布形式如0，1，1，2，3，5，8，13，21，34，…，其中,n≥0，n∈N，F(xiàn)(0)=0，F(xiàn)(1)=1，則Fibonacci序列被如下遞歸方式定義為F(n)=F(n-1)+F(n-2)(n≥2,n∈N)。

盧卡斯序列定義：數(shù)列L(n)分布形式如2,1,3,4,7,11,18,29,47,…,其中,n≥1，n∈N*，L(1)=2，L(2)=1，則Lucas序列被如下遞歸方式定義為L(zhǎng)(n)=L(n-1)+L(n-2)(n≥3,n∈N)。

斐波那契-盧卡斯序列定義：遞增數(shù)列F(n)分布形式如1,3,4,7,11,18,29,47,…，其中,n≥0，n∈N，F(xiàn)(0)=1，F(xiàn)(1)=3，F(xiàn)ibonacci-Lucas序列被如下遞歸方式定義為F(n)=F(n-1)+F(n-2)(n≥2,n∈N)。

1.2 Fibonacci-Lucas序列定理

定理1對(duì)于整數(shù)數(shù)列F(n)，f(n)為數(shù)列中第n個(gè)數(shù)的數(shù)值，若m>n，且m,n,k∈N*有f(m+k)-f(m)>f(n+k)-f(n)[14]。

根據(jù)Fibonacci-Lucas序列中數(shù)字的特性結(jié)合三角旋轉(zhuǎn)法，得到一種圍長(zhǎng)為8的QC-LDPC碼。

2 基于斐波那契-盧卡斯序列的QC-LDPC碼構(gòu)造方法

2.1 基于斐波那契-盧卡斯序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造QC-LDPC碼

步驟1把斐波那契-盧卡斯序列按照如下三角形結(jié)構(gòu)放置，其中，行數(shù)i=1,2,3,…，參數(shù)r的取值影響著碼長(zhǎng)的變化，為了得到長(zhǎng)碼長(zhǎng)則r取較大值，反之得到短碼長(zhǎng)則r取較小值，其中r∈Z+。

i=1F(1+1+r)+1

i=2F(2+2+r)+2F(2+1+r)+2

i=3F(3+3+r)+3F(3+2+r)+3F(3+1+r)+3

iF(2i+r)+iF(2i-1+r)+i…F(i+1+r)+i

步驟2逆時(shí)針旋轉(zhuǎn)45°為

i=1F(1+1+r)+1F(2+1+r)+2F(3+1+r)+3…

i=2F(2+2+r)+2F(3+2+r)+3F(4+2+r)+4…

i=3F(3+3+r)+3F(4+3+r)+4F(5+3+r)+5…

i=4F(4+4+r)+4F(5+4+r)+5F(6+4+r)+6…

步驟3基于以上形式，構(gòu)造出一個(gè)指數(shù)矩陣E(H)，E(H)的維數(shù)為J×L。F(0)為1占滿了指數(shù)矩陣第一行，其后所有行所構(gòu)成的矩陣形式即為45°旋轉(zhuǎn)后所得到的矩陣。于是，指數(shù)矩陣為

(1)

從(1)式中可看出，指數(shù)矩陣E(H)中元素均為正整數(shù)；除第一行元素全為F(0)外，其余每行都是遞增數(shù)列。令0≤i≤J-1，0≤s≤L-1，E(H)中任意一個(gè)元素可表達(dá)為

E(i,s)=F(2i+s+r)+i+s

(2)

步驟4根據(jù)構(gòu)造出來(lái)的指數(shù)矩陣E(H)，為了能充分利用碼長(zhǎng)來(lái)進(jìn)一步優(yōu)化，引入?yún)?shù)k，替換E(H)中尾部元素為E(i,s)+k(k∈N)，使其逼近維數(shù)P，再用維數(shù)為P×P的單位矩陣循環(huán)移位后得到的矩陣去代換E(H)中各元素，其中，循環(huán)移位數(shù)即指數(shù)矩陣E(H)中對(duì)應(yīng)元素，擴(kuò)展因子P即單位矩陣維數(shù)，需滿足表達(dá)式：P≥F(2J+L-3+r)+J+L-1+k，于是，校驗(yàn)矩陣H的構(gòu)造如(3)式所示。

(3)

循環(huán)置換子矩陣維數(shù)可連續(xù)取值，擴(kuò)展后的校驗(yàn)矩陣維數(shù)為JP×LP。

2.2 圍長(zhǎng)至少為8的性質(zhì)證明

首先，定義y(i,s)為指數(shù)矩陣中第i行，第s列的元素，其中，0≤i≤J-1,0≤s≤L-1且i,s∈N。QC-LDPC碼中存在的2K環(huán)可以用表達(dá)式表達(dá)為y(i0,s0)，y(i0,s1)，y(i1,s1)，…，y(ik-1,sk-1)，y(ik-1,s0)，y(i0,s0)。為了使得基于Fibonacci-Lucas序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造QC-LDPC碼無(wú)2K環(huán)，則應(yīng)使得(4)式成立。即

(4)

(4)式中：iv≠iv+1；sv≠sv+1。

從2個(gè)方面分別進(jìn)行說(shuō)明，無(wú)四環(huán)及無(wú)六環(huán)。

不存在四環(huán)證明：根據(jù)(4)式可知要得到無(wú)四環(huán)即使得(5)式成立，即

y(i0,s0)-y(i1,s0)+y(i1,s1)-y(i0,s1)≠0 modp

(5)

令i0

y(i0,s0)-y(i1,s0)+y(i1,s1)-y(i0,s1)=

F(2i0+s0+r)+i0+s0-(F(2i1+s0+r)+i1+s0)+

F(2i1+s1+r)+i1+s1-(F(2i0+s1+r)+i0+s1)

由定理1可推得

F(2i1+s1+r)+i1+s1-(F(2i1+s0+r)+i1+s0)>

F(2i0+s1+r)+i0+s1-(F(2i0+s0+r)+i0+s0)，

0

由上式推導(dǎo)可知構(gòu)造的校驗(yàn)矩陣無(wú)四環(huán)的存在。

無(wú)六環(huán)證明：在Tanner圖中，六環(huán)存在的形式有6種如圖1所示。

圖1 六環(huán)的6種形式Fig.1 Six pattern of the girth-6

可將圖1中6種六環(huán)結(jié)構(gòu)分為2類：①圖1所示的前4種形式，若已推得其中一種形式，另外3種則可由其變形推導(dǎo)而得；②圖1所示后2種形式，也可以相互變形推導(dǎo)。因此，每一類只需推導(dǎo)其中一種形式即可。

根據(jù)(4)式可知要得到無(wú)六環(huán)即需(6)式成立，即

y(i,s)-y(i,t)+y(j,t)-y(j,g)+

y(k,g)-y(k,s)≠0 modp

(6)

對(duì)于圖1第1類，當(dāng)i=0時(shí)可能出現(xiàn)如圖2所示的情形，下面證明圖2中六環(huán)第1類中的第1種形式，其他情況同理可推得。

由(2)式和(6)式可得

y(i,s)-y(i,t)+y(j,t)-y(j,g)+y(k,g)-y(k,s)=

1-1+F(2j+t+r)+j+t-(F(2j+g+r)+j+g)+

F(2k+g+r)+k+g-(F(2k+s+r)+k+s)=

F(2j+t+r)+j+t-(F(2j+g+r)+j+g)+

F(2k+g+r)+k+g-(F(2k+s+r)+k+s)

圖2 六環(huán)的形式一Fig.2 Type-1 of the girth-6

令s=g-m,t=g-n且m>n，則上式可化為

y(i,s)-y(i,t)+y(j,t)-y(j,g)+y(k,g)-y(k,s)=

F(2j+g-n+r)+j+g-n-(F(2j+g+r)+j+g)+

F(2k+g+r)+k+g-(F(2k+g-m+r)+k+g-m)=

F(2j+g-n+r)-n-F(2j+g+r)+

F(2k+g+r)-(F(2k+g-m+r)-m)

(7)

又由定理1可得

F(2k+g+r)-(F(2k+g-m+r)-m)>F(2j+g+r)-

(F(2j+g-n+r)-n)

則：0<(7)式

當(dāng)i≠0：

y(i,s)-y(i,t)+y(j,t)-(y(j,g)+y(k,g)-y(k,s))>

y(i,s)-y(i,t)+y(j,t)-(y(j,g)+y(j,g)-y(j,s))=

y(i,s)-y(i,t)+y(j,t)-y(j,s)>0

y(i,s)-y(i,t)+y(j,t)-(y(j,g)+y(k,g)-y(k,s))<

y(k,s)-y(i,t)+y(j,t)-(y(j,g)+y(k,g)-

y(k,s))=y(j,t)-y(i,t)+y(k,g)-y(j,g)<

y(j,g)+y(k,g)-y(j,g)=y(k,g)

夾逼定理定義：F(x)與G(x)連續(xù)且存在同樣的極限Α，即x→X0時(shí)，limF(x)=limG(x)=Α，則若函數(shù)f(x)在X0的某鄰域內(nèi)，恒有F(x)≤f(x)≤G(x)，則當(dāng)x趨近X0，有l(wèi)imF(x)≤limf(x)≤limG(x)即Α≤limf(x)≤Α，故limf(X0)=Α。

根據(jù)夾逼定理可以得到：原式≠0 modp。

對(duì)于圖1第2類中第1個(gè)形式，當(dāng)i=0：

y(i,s)-y(i,t)+y(k,t)-(y(k,g)+y(j,g)-

y(j,s))=1-1+F(2k+t+r)+k+t-(F(2k+g+r)+

k+g)+F(2j+g+r)+j+g-(F(2j+s+r)+j+s)=

F(2k+t+r)+k+t-(F(2k+g+r)+k+g)+

F(2j+g+r)+j+g-(F(2j+s+r)+j+s)

令s=g-m,t=g-n且m>n，則上式可化為

y(i,s)-y(i,t)+y(k,t)-(y(k,g)+y(j,g)-y(j,s))=

F(2k+g-n+r)-n-F(2k+g+r)+

F(2j+g+r)-(F(2j+g-m+r)-m)

(8)

由定理1可推得

F(2j+g+r)-(F(2j+g-m+r)-m)<

F(2k+g+r)-(F(2k+g-n+r)-n)

則：-P<(7)式<0，即原式≠0 modp。

當(dāng)i≠0：

y(i,s)-y(i,t)+y(k,t)-(y(k,g)+y(j,g)-y(j,s))<

y(j,s)-y(j,t)+y(k,t)-(y(k,g)+y(j,g)-y(j,s))=

y(j,g)-y(j,t)+y(k,t)-y(k,g)<0

y(i,s)-y(i,t)+y(k,t)-(y(k,g)+y(j,g)-y(j,s))>

y(i,g)-y(j,t)+y(k,t)-y(k,g)>y(k,t)-y(k,g)>-p

根據(jù)夾逼定理可以得到：原式≠0 modp。

由以上分析可得，6種六環(huán)形式是不可能出現(xiàn)的，所以，當(dāng)P≥F(2J+L-3+r)+J+L-1時(shí)，無(wú)四環(huán)及六環(huán)，圍長(zhǎng)至少為8的性質(zhì)得以證明。

3 仿真性能分析

基于斐波那契-盧卡斯序列結(jié)合三角旋轉(zhuǎn)法構(gòu)造出1個(gè)QC-LDPC碼，列重為J=3，行重L=6，參數(shù)r=2，其指數(shù)矩陣為

(9)

P的取值為：P≥E(J-1,L-1)+1=430，本文選擇P=450和P=430，那么碼長(zhǎng)分別為2 700和2 580。最終可分別得到行重為6，列重為3，碼率為0.5的F-LQC-LDPC(2 700,1 352)碼和F-L-QC-LDPC(2 580,1 292)碼。

基于斐波那契-盧卡斯序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造的QC-LDPC碼，對(duì)其使用Matlab軟件進(jìn)行仿真，設(shè)置在白色高斯信道，同時(shí)進(jìn)行二進(jìn)制相移鍵控調(diào)制，且使用BP譯碼算法，譯碼迭代次數(shù)選取為50次，再將F-L-QC-LDPC碼仿真圖分別與同碼長(zhǎng)同碼率基于Fibonacci序列結(jié)合三角旋轉(zhuǎn)法構(gòu)造出來(lái)的QC-LDPC碼、基于盧卡斯數(shù)列構(gòu)造的無(wú)四六環(huán)QC-LDPC碼和基于等差數(shù)列構(gòu)造的QC-LDPC碼進(jìn)行對(duì)比分析，如圖3所示。

由圖3分析可知，在BER為10-6時(shí)，基于Fibonacci-Lucas序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造的F-L-QC-LDPC(2 700,1 352)碼相較于文獻(xiàn)[12]中基于Fibonacci數(shù)列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造的同碼長(zhǎng)同碼率F-QC-LDPC(2 700,1 352)碼，圍長(zhǎng)增大到至少為8，凈編碼增益改善了大約1.0 dB，相較于文獻(xiàn)[13]中使用盧卡斯序列填充指數(shù)矩陣構(gòu)造的同碼長(zhǎng)同碼率L-QC-LDPC(2 700,1 353)碼，雖然同樣避免了四六環(huán)，但Fibonacci-Lucas序列同時(shí)巧妙結(jié)合了三角旋轉(zhuǎn)法使得其他碼比特對(duì)信息計(jì)算提供了更大的幫助，提高了糾錯(cuò)性能，凈編碼增益改善了大約1.6 dB，同樣在BER為10-6時(shí)，基于Fibonacci-Lucas序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造的F-L-QC-LDPC(2 580,1 292)與文獻(xiàn)[9]中基于等差數(shù)列構(gòu)造的APS-QC-LDPC(2 580,1 292)碼相比，凈編碼增益提高了約1.0 dB。從編碼復(fù)雜度角度來(lái)看，可從2個(gè)方面進(jìn)行分析，一個(gè)是運(yùn)算復(fù)雜度；另一個(gè)是編碼所需存儲(chǔ)的參數(shù)，其中，運(yùn)算復(fù)雜度是運(yùn)算量和碼長(zhǎng)的變化關(guān)系。本文提出的構(gòu)造方法相比于文獻(xiàn)[12]中基于Fibonacci數(shù)列構(gòu)造的F-QC-LDPC碼和文獻(xiàn)[13]中使用盧卡斯序列構(gòu)造的L-QC-LDPC碼具有相同碼長(zhǎng)和碼率，且都是通過(guò)生成矩陣進(jìn)行編碼，運(yùn)算量均與碼長(zhǎng)的平方呈線性關(guān)系，因此，運(yùn)算復(fù)雜度一樣大。而本文提出的構(gòu)造方法，其指數(shù)矩陣尺寸為J行L列，其中第一行全為元素1，因此，所需存儲(chǔ)的參數(shù)為(J-1)×L+1個(gè)，與文獻(xiàn)[12]和文獻(xiàn)[13]中構(gòu)造J行L列指數(shù)矩陣對(duì)比，所需存儲(chǔ)參數(shù)個(gè)數(shù)相同，從編碼復(fù)雜度來(lái)看三者一樣。綜合分析可得，本文提出的構(gòu)造方法與文獻(xiàn)[12]和文獻(xiàn)[13]中構(gòu)造方法對(duì)比，在復(fù)雜度相同的情況下，糾錯(cuò)性能得到改善。

圖3 F-L-QC-LDPC碼與其他碼的糾錯(cuò)性能仿真圖Fig.3 Simulation diagram of the error-correction performance among theF-L-QC-LDPC code and other codes

4 結(jié) 論

基于Fibonacci-Lucas序列并結(jié)合三角旋轉(zhuǎn)法構(gòu)造QC-LDPC碼，能避免四環(huán)和六環(huán)的產(chǎn)生，有較好的糾錯(cuò)性能，循環(huán)置換子矩陣維數(shù)可連續(xù)取值，另外設(shè)置相應(yīng)的參數(shù)可得到不同的碼長(zhǎng)和碼率。用此構(gòu)造方法構(gòu)造的F-L-QC-LDPC碼，仿真結(jié)果表明，其糾錯(cuò)性能優(yōu)于基于Fibonacci序列結(jié)合三角旋轉(zhuǎn)法構(gòu)造的同碼長(zhǎng)同碼率F-QC-LDPC碼也同樣優(yōu)于使用盧卡斯序列填充指數(shù)矩陣的同碼長(zhǎng)同碼率L-QC-LDPC碼和基于等差數(shù)列構(gòu)造的APS-QC-LDPC碼。