袁建國，曾 晶,袁 夢，范福卓，劉家齊，鄭德猛

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

0 引 言

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

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

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

1 斐波那契-盧卡斯序列簡介

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(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對于整數(shù)數(shù)列F(n)，f(n)為數(shù)列中第n個數(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)法，得到一種圍長為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的取值影響著碼長的變化，為了得到長碼長則r取較大值，反之得到短碼長則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逆時針旋轉(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)造出一個指數(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)中任意一個元素可表達為

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

(2)

步驟4根據(jù)構(gòu)造出來的指數(shù)矩陣E(H)，為了能充分利用碼長來進一步優(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)中對應(yīng)元素，擴展因子P即單位矩陣維數(shù)，需滿足表達式：P≥F(2J+L-3+r)+J+L-1+k，于是，校驗矩陣H的構(gòu)造如(3)式所示。

(3)

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

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

首先，定義y(i,s)為指數(shù)矩陣中第i行，第s列的元素，其中，0≤i≤J-1,0≤s≤L-1且i,s∈N。QC-LDPC碼中存在的2K環(huán)可以用表達式表達為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碼無2K環(huán)，則應(yīng)使得(4)式成立。即

(4)

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

從2個方面分別進行說明，無四環(huán)及無六環(huán)。

不存在四環(huán)證明：根據(jù)(4)式可知要得到無四環(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)造的校驗矩陣無四環(huán)的存在。

無六環(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)式可知要得到無六環(huán)即需(6)式成立，即

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

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

(6)

對于圖1第1類，當(dāng)i=0時可能出現(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時，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。

對于圖1第2類中第1個形式，當(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時，無四環(huán)及六環(huán)，圍長至少為8的性質(zhì)得以證明。

3 仿真性能分析

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

(9)

P的取值為：P≥E(J-1,L-1)+1=430，本文選擇P=450和P=430，那么碼長分別為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碼，對其使用Matlab軟件進行仿真，設(shè)置在白色高斯信道，同時進行二進制相移鍵控調(diào)制，且使用BP譯碼算法，譯碼迭代次數(shù)選取為50次，再將F-L-QC-LDPC碼仿真圖分別與同碼長同碼率基于Fibonacci序列結(jié)合三角旋轉(zhuǎn)法構(gòu)造出來的QC-LDPC碼、基于盧卡斯數(shù)列構(gòu)造的無四六環(huán)QC-LDPC碼和基于等差數(shù)列構(gòu)造的QC-LDPC碼進行對比分析，如圖3所示。

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

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