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

楊衛(wèi)國,鄭 麟

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

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

楊衛(wèi)國,鄭 麟

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

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

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

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

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

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

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

1 IEEE802.16e標(biāo)準(zhǔn)中的LDPC碼

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

表1 IEEE802.16e標(biāo)準(zhǔn)的三種碼長不同碼率下的信息位長度

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

2 快速編碼方法

IEEE802.16e標(biāo)準(zhǔn)采用的編碼算法為快速編碼算法,以1/2碼率為例,簡單介紹快速編碼算法的原理。

表2 IEEE802.16e標(biāo)準(zhǔn)中的基矩陣

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

(1)

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

(2)

運(yùn)算在GF(2)上進(jìn)行,由式(1)和式(2)可得：

(3)

解式(3)得

(4)

由此求得

(5)

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

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

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

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

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

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

(7)

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

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

(8)

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

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

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

4 性能分析

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

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

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

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

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

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

圖3 碼長2000的F-QC-LDPC碼與碼長2016的IEEE802.16e標(biāo)準(zhǔn)碼性能比較

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

5 結(jié)束語

本文提出了一種基于斐波那契數(shù)列構(gòu)造的QC-LDPC碼的基矩陣,該碼可以采用IEEE802.16e標(biāo)準(zhǔn)的快速編碼方案進(jìn)行編碼,編碼速度快,同時(shí)由于矩陣中元素存在數(shù)列性質(zhì),很大程度上節(jié)省了存儲空間,通過仿真結(jié)果表明,用此種方法構(gòu)造的LDPC碼在不消環(huán)的情況下,中短碼就擁有比較優(yōu)異的性能,且碼長可選范圍較大,具有一定的研究參考價(jià)值,在此方法基礎(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碼的研究進(jìn)展和應(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-),男,山東煙臺人,碩士研究生,研究方向?yàn)樾诺谰幋a。