楊衛(wèi)國,鄭 麟

(海軍航空工程學(xué)院,山東 煙臺 264001)

基于斐波那契數(shù)列短碼長QC-LDPC碼的構(gòu)造

楊衛(wèi)國,鄭 麟

(海軍航空工程學(xué)院,山東 煙臺 264001)

設(shè)計了一種QC-LDPC碼的校驗矩陣構(gòu)造方法,矩陣的信息位根據(jù)斐波那契數(shù)列進行構(gòu)造,校驗位根據(jù)IEEE802.16e標準中碼字的校驗矩陣進行構(gòu)造,這樣構(gòu)造的校驗矩陣具有準雙對角線結(jié)構(gòu),在編碼過程中可以采用快速編碼算法,降低了編碼復(fù)雜度，同時節(jié)省了存儲空間。通過仿真,該方法構(gòu)造的碼字在中短碼范圍內(nèi)較Gallager碼性能良好,并且通過改變循環(huán)矩陣的大小,可以獲得碼性能較好的多種碼長的碼字,碼長選擇范圍較大。

QC-LDPC碼; 快速編碼算法; 斐波那契額數(shù)列; IEEE802.16e; 短碼

鄭 麟(1992-),男,碩士研究生。

LDPC碼(低密度奇偶校驗碼)是一種可以逼近香農(nóng)極限的碼,雖然在1962年Gallager博士剛剛提出時并未受到人們的關(guān)注,但在后期的研究發(fā)展過程中,LDPC碼優(yōu)異的性能越來越被人們認可,現(xiàn)在已被廣泛應(yīng)用。LDPC碼目前研究的重點大部分集中在檢驗矩陣的構(gòu)造和改進譯碼算法上,而構(gòu)造性能優(yōu)異的校驗矩陣對于提高碼字性能,降低譯碼復(fù)雜度,都有重要意義。

LDPC碼根據(jù)構(gòu)造方式可分為隨機構(gòu)造法和結(jié)構(gòu)化構(gòu)造法。隨機構(gòu)造法以Gallager隨機構(gòu)造法[1]和Mackay隨機構(gòu)造法[2]為代表,編碼思想簡單,糾錯性能良好,但其編碼復(fù)雜度較高,而結(jié)構(gòu)化構(gòu)造的碼字可以較好地解決編譯碼復(fù)雜度的問題且不失碼字性能。

QC-LDPC碼(準循環(huán)LDPC碼)是目前研究較多的一種結(jié)構(gòu)化構(gòu)造碼,該種碼字占用存儲空間少,編譯碼復(fù)雜度低,糾錯性能良好,已被IEEE802.16e標準采用。本文以IEEE802.16e標準中的編碼方案為基礎(chǔ),利用斐波那契數(shù)列的性質(zhì)構(gòu)造理論上可以適用于多種碼長的QC-LDPC碼(F-QC-LDPC碼)。

1 IEEE802.16e標準中的LDPC碼

IEEE802.16e標準規(guī)定的LDPC碼總共有19種碼長,每種碼長都有4種碼率,具體見表1。

表1 IEEE802.16e標準的三種碼長不同碼率下的信息位長度

QC-LDPC碼的校驗矩陣由基矩陣Hbm×n來表示,基矩陣中每個元素表示z×z的循環(huán)矩陣右移Hb(i,j)位后生成的矩陣。802.16e標準中的基矩陣是固定的,大小為12×24,循環(huán)矩陣的大小z=N/24,N為碼長即擴展后校驗矩陣的列數(shù)。802.16e標準中的基矩陣Hb12×24如表2所示。從表中可以看出,基矩陣Hb右半邊為準雙對角線結(jié)構(gòu),這種結(jié)構(gòu)的校驗矩陣在編碼時采用快速編碼方法,可以不借助生成矩陣直接生成碼字。矩陣中“-1”表示z×z大小的全零矩陣。

2 快速編碼方法

IEEE802.16e標準采用的編碼算法為快速編碼算法,以1/2碼率為例,簡單介紹快速編碼算法的原理。

表2 IEEE802.16e標準中的基矩陣

若編碼后輸出的碼字為C=(c1,c2,…cn),由于碼字為系統(tǒng)碼,所以前n/2項為信息位,后n/2項為校驗位。假設(shè)信息比特S=(s1,s2,…s5),校驗比特為J=(j1,j2,…j5),則編碼輸出為C=[SJ],由于信息比特已知,要求編碼后的碼字就是求校驗比特J。根據(jù)校驗等式H·CT=0可得:

(1)

快速編碼中采用的檢驗矩陣H同樣采用準雙對角線結(jié)構(gòu),因此

(2)

運算在GF(2)上進行,由式(1)和式(2)可得：

(3)

解式(3)得

(4)

由此求得

(5)

3 基于斐波那契數(shù)列的QC-LDPC碼構(gòu)造

3.1 斐波那契數(shù)列的定義

斐波那契數(shù)列又稱黃金分割數(shù)列,該數(shù)列以0、1開始,隨后的數(shù)字是前兩項之和,表現(xiàn)成遞推公式為

F(0)=0,F(1)=1,

F(n)=F(n-1)+F(n-2),(n≥2,n∈N*)

(6)

具體表示為如下數(shù)列:

0,1,1,2,3,5,8,13,21,34,55,89,144,…

斐波那契數(shù)列在現(xiàn)代物理、準晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域都有直接的應(yīng)用,這樣一個完全是自然數(shù)的數(shù)列其通項公式確是無理數(shù)表示,且隨著n的增大,前后項比值趨近黃金分割0.618,而且自然界中好多事物的規(guī)律都趨于這個數(shù)列,鑒于其如此多的優(yōu)良性質(zhì),考慮用其構(gòu)造校驗矩陣。

3.2 基于斐波那契數(shù)列的QC-LDPC碼構(gòu)造方法

以IEEE802.16e標準中的校驗矩陣為基礎(chǔ)構(gòu)造基矩陣的校驗位,并根據(jù)斐波那契數(shù)列合理構(gòu)造基矩陣的信息位,因主要針對中短碼,所以基矩陣的維數(shù)定為5×10,碼率定為1/2,具體方式如下:

1)構(gòu)造基矩陣Hb=[HvHc],其中

(7)

是一個具有準雙對角線結(jié)構(gòu)的矩陣;

2)構(gòu)造Hv,矩陣Hv的第一行全部為0,第一列的數(shù)字為斐波那契數(shù)列的奇數(shù)項,即0,1,3,8,21,除第一行外,每行根據(jù)行首數(shù)字依次向后排列寫出斐波那契數(shù)列,構(gòu)造好的Hv如下所示：

(8)

3)更新矩陣Hv,循環(huán)矩陣的大小z=N/10,N為碼長,當z

4)根據(jù)最后構(gòu)造好的基矩陣Hb,將-1替換為z×z大小的全零矩陣,其他元素替換為z×z大小的單位矩陣向右循環(huán)移動Hb(i,j)位所得到的矩陣,按照快速編碼算法進行編碼。

QC-LDPC碼在存儲過程中主要存儲其校驗矩陣,通過本文提供的編碼方法可知,F-QC-LDPC碼在存儲過程中除了需要完全存儲矩陣Hc外,矩陣Hv只需存儲0和1兩個元素,其他元素均可通過斐波那契數(shù)列的性質(zhì)求得,很大程度上節(jié)省了編碼器的存儲空間,且可以根據(jù)需要任意設(shè)定碼長(碼長是10的倍數(shù),碼率為1/2)。

4 性能分析

本文是為了設(shè)計性能優(yōu)良的中短碼,在仿真中選取碼長為250,此時循環(huán)矩陣的大小z=250/10=25,根據(jù)矩陣構(gòu)造F-QC-LDPC碼,對編碼輸出采用BPSK調(diào)制,傳輸信道選用AWGN信道,譯碼算法采用和積譯碼算法,信噪比從0增加至5,對比碼字采用Gallager隨機構(gòu)造法構(gòu)造,碼長為256,兩種碼字的碼率均取1/2,最大迭代次數(shù)為30次,仿真結(jié)果如圖1所示。

圖1 Gallager碼與F-QC-LDPC碼性能比較

由圖1可見,在信噪比較低的情況下,兩種碼字的性能相差無幾,在信噪比達到3時,F-QC-LDPC碼的誤碼率就比Gallager碼高出將近一個數(shù)量級,在誤碼率為10-5時,F-QC-LDPC碼有將近1dB的增益。

單獨比較F-QC-LDPC碼在不同碼長情況下的譯碼性能,仍然采用BPSK調(diào)制,傳輸信道為AWGN信道,譯碼算法為最大迭代次數(shù)30的和積譯碼算法,碼長分別取80,150,300進行仿真,仿真結(jié)果如圖2所示。從圖中可以看出,利用本文方法構(gòu)造的LDPC碼在碼長為80的超短碼時性能并不是特別理想,但中短碼性能比較好,碼長300時在信噪比較大的情況下,誤碼率就可以達到10-7數(shù)量級。

圖2 不同碼長F-QC-LDPC碼性能比較

當F-QC-LDPC碼碼長達到2000,z=200時,同樣在BPSK調(diào)制下通過AWGN信道,與IEEE802.16e標準下的QC-LDPC碼選取其固定碼長2016,碼率1/2的情況下進行比較,經(jīng)過30次迭代的和積譯碼后的仿真結(jié)果如圖3所示。

圖3 碼長2000的F-QC-LDPC碼與碼長2016的IEEE802.16e標準碼性能比較

如圖3所示,F-QC-LDPC碼與IEEE802.16e標準碼在碼性能上存在一定差距,分析其原因主要是因為F-QC-LDPC碼的校驗矩陣并未進行消環(huán)處理,校驗矩陣中存在一定數(shù)量的4環(huán)和6環(huán),影響了F-QC-LDPC碼的譯碼性能,但差距并不是特別大,在誤碼率為10-5時,兩者僅相差約0.3dB。比較圖1和圖3就會發(fā)現(xiàn),本文所提出的碼在未消環(huán)的情況下仍能獲得比Gallager碼更優(yōu)異的碼性能。

5 結(jié)束語

本文提出了一種基于斐波那契數(shù)列構(gòu)造的QC-LDPC碼的基矩陣,該碼可以采用IEEE802.16e標準的快速編碼方案進行編碼,編碼速度快,同時由于矩陣中元素存在數(shù)列性質(zhì),很大程度上節(jié)省了存儲空間,通過仿真結(jié)果表明,用此種方法構(gòu)造的LDPC碼在不消環(huán)的情況下,中短碼就擁有比較優(yōu)異的性能,且碼長可選范圍較大,具有一定的研究參考價值,在此方法基礎(chǔ)上,如果可以消除短環(huán)將會獲得更加優(yōu)良的碼性能。

[1] Gallager R G.Low-density parity-check codes[J].IEEE Transactions on Information Theory,1962,8(1):21-28.

[2] MacKay D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[3] 黃勝,穆攀,張睿,等.基于大衍數(shù)列的規(guī)則QC-LDPC碼構(gòu)造方法[J].電視技術(shù),2016,40(9):77-80,94.

[4] 易旭,杜昊陽.LDPC碼的研究進展和應(yīng)用展望[J].通信技術(shù),2016,49(1):1-6.

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

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

[7] Gallager R.Low-Density Parity-Check Codes[M],Cambridge,M A:MIT Press,1963.

[8] MA Ke-xiang,ZHANG Peng.Low-Delay Loop Detection Algorithm for LDPC Codes[J].Journal of CAEIT,2015(4):341-343.

[9] Chen X,Kang J,Lin s,et al.Memory System Optimization for FPGA-Based Implementation of Quasi-Cyclic LDPC Codes Decoders[J].Circuits and Systems I:Regular Papers,IEEE Transactions,2011(58):98-111.

[10] Ardakani M,and Kschischang F R.A More Accurate One-Dimensional Analysis and Design of Irregular LDPC codes[J].IEEE Transactions on Communications,2004:52(12):2106-2114.

A Construction Method of QC-LDPC Codes Based on the Fbonacci Sequence

YANG Wei-guo,ZHENG Lin

(Navy Aeronautics and Astronautics University,Yantai 264001,China)

This paper presents a construction method of quasi-cyclic low-density party-check(QC-LDPC) codes,whose information parts are based on the Fbonacci sequence while the check parts are based on IEEE802.16e standard.Because of the quasi dual-diagonal structure,it can lower the complexity and save the memory space through fast encoding algorithm.Simulation results show that the proposed codes is better than Gallager codes when the code length is shorter.Besides,there are many good codes at a lot of length by changing the size of the cyclic matrix.

QC-LDPC codes; fast encoding algorithm; Fbonacci sequence; IEEE802.16e; short codes

TN911.22；E96

A

10.3969/j.issn.1673-3819.2017.05.027

1673-3819(2017)05-0130-04

2017-06-26

2017-08-06

楊衛(wèi)國(1987-),男,山東煙臺人,碩士研究生,研究方向為信道編碼。