利用域間映射的多元QC-LDPC碼構(gòu)造*

洪冰清，劉聰聰，陳海強(qiáng)，3，4，覃新賢，3，4

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004；2.中國(guó)空間技術(shù)研究院 西安分院，西安 710100；3.廣西高校多媒體通信與信息處理重點(diǎn)實(shí)驗(yàn)室(廣西大學(xué))，南寧 530004；4.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室培育基地(廣西大學(xué))，南寧 530004)

?

利用域間映射的多元QC-LDPC碼構(gòu)造*

洪冰清1，劉聰聰2，陳海強(qiáng)**1，3，4，覃新賢1，3，4

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004；2.中國(guó)空間技術(shù)研究院 西安分院，西安 710100；3.廣西高校多媒體通信與信息處理重點(diǎn)實(shí)驗(yàn)室(廣西大學(xué))，南寧 530004；4.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室培育基地(廣西大學(xué))，南寧 530004)

通過(guò)定義有限域間的映射關(guān)系，提出了一種低復(fù)雜度的多元準(zhǔn)循環(huán)奇偶校驗(yàn)碼(QC-LDPC)的構(gòu)造方法。利用這種方法可將較高階數(shù)有限域的校驗(yàn)矩陣映射到指定的較低有限域上，且能保持原矩陣的結(jié)構(gòu)性與稀疏特性。所構(gòu)造的多元LDPC碼不僅具有較低的譯碼復(fù)雜度且具有準(zhǔn)循環(huán)特性，在硬件上也易于用移位寄存器實(shí)現(xiàn)。在高斯白噪聲(AWGN)信道下的仿真結(jié)果表明，所構(gòu)造的多元QC-LDPC碼具有良好的編譯碼性能。當(dāng)誤碼率為10-6時(shí)，碼率為0.765的QC-LDPC碼在目標(biāo)域GF(8)上能獲得0.2 dB的性能增益。

多元LDPC碼；準(zhǔn)循環(huán)；有限域映射；低譯碼復(fù)雜度

1 引 言

低密度奇偶校驗(yàn)(Low Density Parity Check,LDPC)碼是Gallager于1962年提出的一種具有接近香農(nóng)限的優(yōu)秀編碼方案[1]。Mackey和Davey[2]在1998年首次提出了多元的編碼方法，并給出了相應(yīng)的譯碼算法。與二進(jìn)制LDPC碼相比，多元LDPC碼具有更好的編譯碼性能，且具有更高的抗突發(fā)錯(cuò)誤能力。同時(shí)準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼具有更低的實(shí)現(xiàn)復(fù)雜度，且具有與隨機(jī)構(gòu)造多元LDPC碼相似的性能，因此吸引了廣泛的研究。

目前結(jié)構(gòu)化的多元LDPC碼的構(gòu)造方法主要是基于代數(shù)、幾何理論，包括有限域加群、循環(huán)子群以及有限幾何循環(huán)類等結(jié)構(gòu)化構(gòu)造方法。文獻(xiàn)[3]研究了準(zhǔn)循環(huán)矩陣中環(huán)的形成條件；文獻(xiàn)[4]對(duì)校驗(yàn)矩陣中的非零元素進(jìn)行分析，構(gòu)造了一類校驗(yàn)矩陣滿秩的準(zhǔn)循環(huán)多元環(huán)碼；文獻(xiàn)[5-8]基于有限幾何和有限域構(gòu)造了一系列最小距離很大且誤碼平臺(tái)極低的多元準(zhǔn)循環(huán)LDPC碼；文獻(xiàn)[9]基于完美差分集構(gòu)造一種大圍長(zhǎng)多元準(zhǔn)循環(huán)LDPC環(huán)碼；文獻(xiàn)[10-11]提出基于歐氏幾何空間平行束構(gòu)造規(guī)則與非規(guī)則LDPC碼的方法并取得了良好的性能；文獻(xiàn)[12]利用遺傳算法提出一種計(jì)算機(jī)搜索的大圍長(zhǎng)QC-LDPC碼構(gòu)造方法，且取得了一定的凈編碼增益；文獻(xiàn)[13]基于完美差分集的思想提出一種列重為2的循環(huán)置換矩陣構(gòu)造方法，并取得了很好的性能。

以上幾種準(zhǔn)循環(huán)LDPC碼的構(gòu)造方法都能取得良好編譯碼性能，但校驗(yàn)矩陣的結(jié)構(gòu)并不是很靈活，特別是在構(gòu)造碼率較高的LDPC碼時(shí)，需要基于較高階數(shù)的有限域。同時(shí)，多元LDPC碼的譯碼算法與其階數(shù)密切相關(guān)，階數(shù)越高，其譯碼的復(fù)雜度就越高。文獻(xiàn)[14]基于激光通信的應(yīng)用背景提出了一種基于有限域立體擴(kuò)展的多元LDPC碼構(gòu)造方法，文獻(xiàn)[15]提出了通過(guò)滑動(dòng)窗口構(gòu)造指定有限域上的校驗(yàn)矩陣的方法，提高了編碼構(gòu)造靈活性。本文在此基礎(chǔ)上提出一種基于有限域映射構(gòu)造低譯碼復(fù)雜度的多元準(zhǔn)循環(huán)LDPC碼的方法，所得到的多元LDPC碼不僅具有較低的譯碼復(fù)雜度，同時(shí)也具有較好的編譯碼性能。

2 多元準(zhǔn)循環(huán)LDPC碼

設(shè)m×n維多元LDPC碼的校驗(yàn)矩陣

(1)

式中：Hi,j為GF(q)上k×k的子矩陣，0≤i

3 基于有限域映射的多元準(zhǔn)循環(huán)LDPC碼構(gòu)造方法

設(shè)α是有限域GF(q1)上的一個(gè)本原元，α的冪形式α=0,α0=1,α,…,αq1-2構(gòu)成GF(q1)上的所有元素，同時(shí)αq1-1=1?；贕F(q1)構(gòu)造m×n的基矩陣W：

(2)

W滿足以下結(jié)構(gòu)性質(zhì)：

(1)對(duì)0≤i≤m和0≤k,l

(2)對(duì)0≤i,j

特性1表明W的每一行最多有一個(gè)GF(q1)上的零元素，特性2表明W中的任意兩行都有n-1處不同。特性1和2表明了W的行之間的約束關(guān)系，也被稱為行約束條件1和2。

將W中的非零元素置換為GF(q1)上(q1-1)×(q1-1)的α乘循環(huán)置換矩陣，可得GF(q1)上滿足RC約束條件的準(zhǔn)循環(huán)校驗(yàn)矩陣H：

(3)

矩陣H中的每個(gè)子矩陣Ai,j為具有如下形式的乘α循環(huán)置換矩陣：

(4)

設(shè)β為GF(q2)(q2

定義1：設(shè)α,β分別為GF(q1)和GF(q2)的一個(gè)本原元，集合A={α0,α1,…,αq1-2}和集合B={β0,β1,…,βq2-2}為有限域GF(q1)和GF(q2)上的所有非零元素的集合，定義集合A到集合B的一種映射f：Ai,j→Bi,j?{f:αk→βkmod(q2-1)},0≤k

通過(guò)所定義的有限域映射關(guān)系可將基于GF(q1)的循環(huán)置換矩陣Ai,j映射到基于GF(q2)的置換矩陣Bi,j：

(5)

置換矩陣Bi,j中的所有非零元素均在映射域GF(q2)上。可知Bi,j具有以下結(jié)構(gòu)性質(zhì)：Bi,j中每行每列有且只有一個(gè)非零元素；Bi,j的每一行均為其上一行的右循環(huán)移位并乘以β，第一行為其最后一行的右循環(huán)移位并乘以β，即Bi,j為GF(q2)上的(q1-1)×(q1-1)維乘β循環(huán)置換矩陣。將H中的所有子矩陣Ai,j通過(guò)映射變換置換為乘β循環(huán)置換矩陣Bi,j可得GF(q2)上滿足RC約束準(zhǔn)則的準(zhǔn)循環(huán)校驗(yàn)矩陣Hf：

(6)

引理1：將準(zhǔn)循環(huán)校驗(yàn)矩陣H通過(guò)有限域映射得到的校驗(yàn)矩陣Hf所定義的LDPC碼為多元準(zhǔn)循環(huán)LDPC碼。

(7)

(8)

由矩陣Hf各子矩陣的循環(huán)特性可知

(9)

則式(8)有

(10)

即v(l)也為校驗(yàn)矩陣Hf所定義的碼字。所以校驗(yàn)矩陣Hf所定義的LDPC碼為多元準(zhǔn)循環(huán)LDPC碼。命題得證。

對(duì)任意整數(shù)對(duì)(γ,ρ),1≤γ≤m,1≤ρ≤n,令Hf(γ,ρ)是Hf的γ×ρ維子矩陣，則矩陣Hf(γ,ρ)為GF(q2)上的γ(q1-1)×ρ(q1-1)維矩陣?；贕F(q2)的矩陣Hf(γ,ρ)的解空間定義了q2進(jìn)制的準(zhǔn)循環(huán)LDPC碼Cqc,f，其碼長(zhǎng)為ρ(q1-1)，碼率至少為(ρ-γ)/ρ。如果矩陣Hf(γ,ρ)有固定的列重和行重γ和ρ，則Cqc,f是(γ,ρ)規(guī)則QC-LDPC碼，其最小距離為γ+1；否則，Cqc,f為非規(guī)則QC-LDPC碼。

4 復(fù)雜度和仿真分析

本文仿真環(huán)境如下：信道為高斯白噪聲(Additive White Gaussian Noise,AWGN)信道，調(diào)制方式為BPSK調(diào)制，譯碼最大迭代次數(shù)均為50，使用QSPA譯碼算法。為了進(jìn)一步分析不同有限域映射對(duì)多元LDPC 碼性能的影響，本節(jié)構(gòu)造了基于不同有限域階上的多元LDPC碼，并對(duì)其譯碼性能進(jìn)行了分析。

例1：設(shè)q1=32,q2=4,8,16?；贕F(q1)構(gòu)造基矩陣W，并將W中的非零元素置換為乘α循環(huán)置換矩陣，取γ=4、ρ=8構(gòu)造基于GF(32)的LDPC碼C0,碼長(zhǎng)n=248，碼率R=0.552。通過(guò)文中定義的映射關(guān)系構(gòu)造基于GF(4)、GF(8)、GF(16)的多元LDPC碼C1、C2、C3。4種多元LDPC碼的仿真性能曲線如圖1和圖2所示。

圖1 (248,137 )LDPC碼在各有限域上的誤符號(hào)率

Fig.1 Symbol error performance of(248,137)LDPC code over different finite fields

圖2 (248,137 )LDPC碼在各有限域上的誤比特率

Fig.2 Bit error performance of(248,137)LDPC code over different finite fields

分析可知，在低信噪比時(shí)，通過(guò)文中提出的算法得到的具有低譯碼復(fù)雜度的LDPC碼的性能均優(yōu)于原有的LDPC碼。隨著信噪比的增加，4元LDPC碼的瀑布區(qū)表現(xiàn)不夠明顯，在低誤碼率時(shí)性能不如GF(32)LDPC碼，但基于GF(8)與GF(16)的LDPC碼均具有較好的誤碼性能。在誤符號(hào)率為10-5時(shí)，8元LDPC碼相比于原LDPC碼約有0.15 dB的性能增益。

例2：為分析算法對(duì)不同碼率多元LDPC碼的影響，設(shè)q1=64,q2=4、8,16。取γ=4、ρ=16構(gòu)造基于GF(64)的LDPC碼C0,碼長(zhǎng)n=1 008，碼率R=0.765。通過(guò)有限域映射關(guān)系構(gòu)造基于GF(4)、GF(8)、GF(16)的LDPC碼C1、C2、C3，其仿真性能如圖3和圖4所示。

圖3 (1 008,771)LDPC碼在各有限域上的誤符號(hào)率

Fig.3 Symbol error performance of(1 008,771)LDPC code over different finite fields

圖4 (1 008,771)LDPC碼在各有限域上的誤比特率

Fig.4 Bit error performance of(1 008,771)LDPC code over different finite fields

由圖可知，在此碼率下，8元LDPC碼的性能最好，具有較好的編譯碼性能和較低的誤碼平層；4元LDPC碼的瀑布區(qū)性能有所提升；經(jīng)過(guò)映射變換的3種LDPC碼的編譯碼性能均優(yōu)于原LDPC碼，且在低信噪比時(shí)性能提升較為明顯；當(dāng)誤符號(hào)率為10-5或誤比特率為10-6時(shí)均約有0.2 dB的性能增益，并且經(jīng)過(guò)映射變換的多元LDPC碼具有更低的譯碼復(fù)雜度。相比于例1的仿真結(jié)果可知，利用本文的方法構(gòu)造出的高碼率多元LDPC碼表現(xiàn)更優(yōu)秀。

5 結(jié)束語(yǔ)

本文提出了一種以降低多元LDPC譯碼復(fù)雜度為目的LDPC碼構(gòu)造方法，利用有限域映射關(guān)系，將高階有限域元素投影到指定的目標(biāo)域上來(lái)構(gòu)造多元LDPC碼，能有效降低多元LDPC碼的譯碼復(fù)雜度。與目前已有的構(gòu)造方法相比，本文提出的方法能夠方便地將LDPC碼從大域映射到指定的小域，但在結(jié)構(gòu)上依舊滿足準(zhǔn)循環(huán)特性，可用簡(jiǎn)單的移位寄存器實(shí)現(xiàn)，節(jié)約硬件資源，因此具有一定的實(shí)用價(jià)值。仿真結(jié)果表明，本文所構(gòu)造的多元LDPC碼在中低信噪比范圍內(nèi)具有更好的譯碼性能，當(dāng)映射目標(biāo)域的階數(shù)大于4時(shí)，基本觀察不到錯(cuò)誤平層(在誤比特率約為10-6時(shí))。下一步可在有限域的映射關(guān)系以及硬件實(shí)現(xiàn)架構(gòu)等方面展開(kāi)進(jìn)一步的研究。

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

[2] DAVEY M C,MACKAY D.Low-density parity check codes over GF(q)[J]. IEEE Communications Letters,1998,2(6):165-167.

[3] MYUNG S,YANG K,KIM J. Quasicyclic LDPC codes for fast encoding[J].IEEE Transactions on Information Theory,2005,51(8): 2894-2901.

[4] PENG R H,CHEN R R. Design of non-binary quasi-cyclic LDPC cycle codes[C]//Proceedings of 2007 IEEE Information Theory Workshop.California:IEEE,2007:13-18.

[5] LIN S,SONG S M,LAN L. Algebraic constructions of non-binary quasi-cyclic LDPC codes[C]//Proceedings of 2006 IEEE International Conference on Communications,Circuits and Systems.Guilin:IEEE,2006: 1303-1308.

[6] ZHOU B,KANG J Y,HUANG Q,et al.High performance non-binary quasi-cyclic LDPC codes on Euclidean geometries[J]. IEEE Transactions on Communications,2009,57(5): 1298-1311.

[7] ZENG L Q,LAN L,TAI Y Y,et al. Construction of non-binary cyclic,quasi and regular LDPC codes: a finite geometry approach[J].IEEE Transactions on Communications,2008,56(3):378-387.

[8] SONG S M,ZHOU B,LIN S,et al. A unified approach to the construction of binary and non-binary quasi-cyclic LDPC codes based on finite fields[J]. IEEE Transactions on Communications,2009,57(1): 84-93.

[9] CHEN C,BAI B M. Construction of non-binary quasi-cyclic LDPC cycle codes based on singer perfect difference sets[J].IEEE Communications Letters,2010,14(2): 181-183.

[10] JIANG X,LEE M H. Large girth non-binary LDPC codes based on finite fields and Euclidean geometries[J]. IEEE Signal Processing Letters,2009,16(6):521-524.

[11] JIANG X ,LEE M H. Design of irregular quasi-cyclic LDPC codes based on euclidean geometries[C]//Proceedings of 2009 IEEE Fourth International Workshop on Signal Design and its Applications in Communications.Fukuoka,Japan:IEEE,2009: 141-144.

[12] 鄭丹玲,穆攀,田凱,等. 利用遺傳算法構(gòu)造QC-LDPC碼[J].電訊技術(shù),2015,55(4):355-359. ZHENG Danling,MU Pan,TIAN Kai,et al.Construction of QC-LDPC codes with genetic algorithm[J]. Telecommunication Engineering,2015,55(4):355-359.(in Chinese)

[13] ZHANG L J,LI B,LUNG C L. Construction of Type-II QC-LDPC codes based on perfect cyclic difference set[J].Chinese Journal of Electronics,2015,24(1):146-151.

[14] 黃勝,田凱,何麗,等.光通信中一種準(zhǔn)循環(huán)非二進(jìn)制LDPC碼的新穎構(gòu)造方法[J].光電子·激光,2014,25(1):56-60. HUANG Sheng,TIAN Kai,HE Li,et al.A novel construction method of quasi-cyclic non- binary LDPC codes in optical communi- cation[J]. Journal of Optoelectronics·Laser,2014,25(1):56-60.(in Chinese)

[15] CHEN H Q,LIU Y Y,QIN T F,et al. Construction of structured q-ary LDPC codes over small fields using sliding-window method[J]. Journal of Communications and Networks,2014,16(5):479- 484.

[16] TANNER R,SRIDHARA D.LDPC block and convolutional codes based on circulant matrices[J]. IEEE Transactions on Information Theory,2004,50(12):2966-2984.

[17] ARABACI M，DJORDJEVIC B.High-rate nonbinary regular quasi cyclic LDPC codes for optical communications[J]. Journal of Lightwave Technology,2009,27(23): 5261-5267.

洪冰清(1990—),女，河南永城人，現(xiàn)為廣西大學(xué)碩士研究生，主要研究方向?yàn)樾l(wèi)星導(dǎo)航基帶信號(hào)處理算法、編碼理論；

HONG Bingqing was born in Yongcheng,Henan Province,in 1990.She is now a graduate student. Her research concerns baseband signal processing algorithm of satellite navigation and coding theory.

Email:hongbingqing20@163.com

劉聰聰(1991—),男,河南開(kāi)封人,碩士研究生；

LIU Congcong was born in Kaifeng,Henan Province,in 1991. He is now a graduate student.

Email:Lcc1202@126.com

陳海強(qiáng)(1976—)，男，廣西蒼梧人，2011年于中山大學(xué)獲博士學(xué)位，現(xiàn)為廣西大學(xué)教授、碩士生導(dǎo)師，主要研究方向?yàn)榫幋a理論和中繼系統(tǒng)等；

CHEN Haiqiang was born in Cangwu,Guangxi Zhuangzu Autonomous Region,in 1976. He received the Ph.D. degree from Sun Yat-sen University in 2011. He is now a professor and also the instructor of graduate students.His research concerns coding theory and relay system.

Email:haiqiang@gxu.edu.cn

覃新賢(1963—)，男，廣西柳州人，教授、碩士生導(dǎo)師，主要研究方向?yàn)樾l(wèi)星導(dǎo)航基帶信號(hào)處理算法、無(wú)線通信系統(tǒng)。

QIN Xinxian was born in Liuzhou,Guangxi Zhuangzu Autonomous Region,in 1963. He is now a professor and also the instructor of graduate students. His research concerns baseband signal processing algorithm of satellite navigation and wireless communications.

Email:xinxianqin@163.com

Construction of Q-ary QC-LDPC Codes with Galois Filed Mapping

HONG Bingqing1,LIU Congcong2,CHEN Haiqiang1,3,4,QIN Xinxian1,3,4

(1.School of Computer and Electronic Information,Guangxi University,Nanning,530004,China;2.China Academy of Space Technology(Xi′an),Xi′an 710100,China;3.Guangxi Colleges and Universities Key Laboratory of Multimedia Communications and Information Processing,Nanning 530004,China;4.Guangxi Key Laboratory of Multimedia Communications and Network Technology(Cultivating Base),Guangxi University,Nanning 530004,China)

An approach to construct Q-ary quasi-cyclic(QC) low density parity check(LDPC) codes with low decoding complexity is presented by defining a mapping relationship over Galois field.With this method,the parity check matrix over a higher order Galois field can be mapped to a designated Galois field,which can keep its structural property and density degree.Codes constructed by this method have low decoding complexity and quasi-cyclic characteristic，which can be easily implemented by shift registers.Simulation results show that the constructed codes have good performance over additive white Gaussian noise(AWGN) channel.Compared with the original codes,QC-LDPC codes with rate 0.765 at targeted field GF(8) can achieve a performance gain about 0.2 dB around 10-6bit error rate(BER).

Q-ary LDPC codes;quasi-cyclic;Galois field mapping;low decoding complexity

10.3969/j.issn.1001-893x.2016.07.002

洪冰清，劉聰聰，陳海強(qiáng),等.利用域間映射的多元QC-LDPC碼構(gòu)造[J].電訊技術(shù)，2016,56(7):724-728.[HONG Bingqing,LIU Congcong,CHEN Haiqiang,et al.Construction of Q-ary QC-LDPC codes with Galois filed mapping[J].Telecommunication Engineering,2016,56(7):724-728.]

2016-01-22；

2016-04-19 Received date:2016-01-22；Revised date：2016-04-19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61102090,61362010)；廣西自然科學(xué)基金資助項(xiàng)目(2012GXNSFAA053217,2014GXNSFBA118276)

Foundation Item:The National Natural Science Foundation of China(No.61102090,61362010); The Natural Science Foundation of Guangxi(2012GXNSFAA053217,2014GXNSFBA118276)

TN911.21

A

1001-893X(2016)07-0724-05

**通信作者：haiqiang@gxu.edu.cn Corresponding author：haiqiang@gxu.edu.cn