利用域间映射的多元QC-LDPC码构造*

2016-12-20 08:49洪冰清刘聪聪陈海强覃新贤
电讯技术 2016年7期
关键词:构造方法广西大学码率

洪冰清,刘聪聪,陈海强,3,4,覃新贤,3,4

(1.广西大学 计算机与电子信息学院,南宁 530004;2.中国空间技术研究院 西安分院,西安 710100;3.广西高校多媒体通信与信息处理重点实验室(广西大学),南宁 530004;4.广西多媒体通信与网络技术重点实验室培育基地(广西大学),南宁 530004)



利用域间映射的多元QC-LDPC码构造*

洪冰清1,刘聪聪2,陈海强**1,3,4,覃新贤1,3,4

(1.广西大学 计算机与电子信息学院,南宁 530004;2.中国空间技术研究院 西安分院,西安 710100;3.广西高校多媒体通信与信息处理重点实验室(广西大学),南宁 530004;4.广西多媒体通信与网络技术重点实验室培育基地(广西大学),南宁 530004)

通过定义有限域间的映射关系,提出了一种低复杂度的多元准循环奇偶校验码(QC-LDPC)的构造方法。利用这种方法可将较高阶数有限域的校验矩阵映射到指定的较低有限域上,且能保持原矩阵的结构性与稀疏特性。所构造的多元LDPC码不仅具有较低的译码复杂度且具有准循环特性,在硬件上也易于用移位寄存器实现。在高斯白噪声(AWGN)信道下的仿真结果表明,所构造的多元QC-LDPC码具有良好的编译码性能。当误码率为10-6时,码率为0.765的QC-LDPC码在目标域GF(8)上能获得0.2 dB的性能增益。

多元LDPC码;准循环;有限域映射;低译码复杂度

1 引 言

低密度奇偶校验(Low Density Parity Check,LDPC)码是Gallager于1962年提出的一种具有接近香农限的优秀编码方案[1]。Mackey和Davey[2]在1998年首次提出了多元的编码方法,并给出了相应的译码算法。与二进制LDPC码相比,多元LDPC码具有更好的编译码性能,且具有更高的抗突发错误能力。同时准循环结构的LDPC码具有更低的实现复杂度,且具有与随机构造多元LDPC码相似的性能,因此吸引了广泛的研究。

目前结构化的多元LDPC码的构造方法主要是基于代数、几何理论,包括有限域加群、循环子群以及有限几何循环类等结构化构造方法。文献[3]研究了准循环矩阵中环的形成条件;文献[4]对校验矩阵中的非零元素进行分析,构造了一类校验矩阵满秩的准循环多元环码;文献[5-8]基于有限几何和有限域构造了一系列最小距离很大且误码平台极低的多元准循环LDPC码;文献[9]基于完美差分集构造一种大围长多元准循环LDPC环码;文献[10-11]提出基于欧氏几何空间平行束构造规则与非规则LDPC码的方法并取得了良好的性能;文献[12]利用遗传算法提出一种计算机搜索的大围长QC-LDPC码构造方法,且取得了一定的净编码增益;文献[13]基于完美差分集的思想提出一种列重为2的循环置换矩阵构造方法,并取得了很好的性能。

以上几种准循环LDPC码的构造方法都能取得良好编译码性能,但校验矩阵的结构并不是很灵活,特别是在构造码率较高的LDPC码时,需要基于较高阶数的有限域。同时,多元LDPC码的译码算法与其阶数密切相关,阶数越高,其译码的复杂度就越高。文献[14]基于激光通信的应用背景提出了一种基于有限域立体扩展的多元LDPC码构造方法,文献[15]提出了通过滑动窗口构造指定有限域上的校验矩阵的方法,提高了编码构造灵活性。本文在此基础上提出一种基于有限域映射构造低译码复杂度的多元准循环LDPC码的方法,所得到的多元LDPC码不仅具有较低的译码复杂度,同时也具有较好的编译码性能。

2 多元准循环LDPC码

设m×n维多元LDPC码的校验矩阵

(1)

式中:Hi,j为GF(q)上k×k的子矩阵,0≤i

3 基于有限域映射的多元准循环LDPC码构造方法

设α是有限域GF(q1)上的一个本原元,α的幂形式α=0,α0=1,α,…,αq1-2构成GF(q1)上的所有元素,同时αq1-1=1。基于GF(q1)构造m×n的基矩阵W:

(2)

W满足以下结构性质:

(1)对0≤i≤m和0≤k,l

(2)对0≤i,j

特性1表明W的每一行最多有一个GF(q1)上的零元素,特性2表明W中的任意两行都有n-1处不同。特性1和2表明了W的行之间的约束关系,也被称为行约束条件1和2。

将W中的非零元素置换为GF(q1)上(q1-1)×(q1-1)的α乘循环置换矩阵,可得GF(q1)上满足RC约束条件的准循环校验矩阵H:

(3)

矩阵H中的每个子矩阵Ai,j为具有如下形式的乘α循环置换矩阵:

(4)

设β为GF(q2)(q2

定义1:设α,β分别为GF(q1)和GF(q2)的一个本原元,集合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

通过所定义的有限域映射关系可将基于GF(q1)的循环置换矩阵Ai,j映射到基于GF(q2)的置换矩阵Bi,j:

(5)

置换矩阵Bi,j中的所有非零元素均在映射域GF(q2)上。可知Bi,j具有以下结构性质:Bi,j中每行每列有且只有一个非零元素;Bi,j的每一行均为其上一行的右循环移位并乘以β,第一行为其最后一行的右循环移位并乘以β,即Bi,j为GF(q2)上的(q1-1)×(q1-1)维乘β循环置换矩阵。将H中的所有子矩阵Ai,j通过映射变换置换为乘β循环置换矩阵Bi,j可得GF(q2)上满足RC约束准则的准循环校验矩阵Hf:

(6)

引理1:将准循环校验矩阵H通过有限域映射得到的校验矩阵Hf所定义的LDPC码为多元准循环LDPC码。

(7)

(8)

由矩阵Hf各子矩阵的循环特性可知

(9)

则式(8)有

(10)

即v(l)也为校验矩阵Hf所定义的码字。所以校验矩阵Hf所定义的LDPC码为多元准循环LDPC码。命题得证。

对任意整数对(γ,ρ),1≤γ≤m,1≤ρ≤n,令Hf(γ,ρ)是Hf的γ×ρ维子矩阵,则矩阵Hf(γ,ρ)为GF(q2)上的γ(q1-1)×ρ(q1-1)维矩阵。基于GF(q2)的矩阵Hf(γ,ρ)的解空间定义了q2进制的准循环LDPC码Cqc,f,其码长为ρ(q1-1),码率至少为(ρ-γ)/ρ。如果矩阵Hf(γ,ρ)有固定的列重和行重γ和ρ,则Cqc,f是(γ,ρ)规则QC-LDPC码,其最小距离为γ+1;否则,Cqc,f为非规则QC-LDPC码。

4 复杂度和仿真分析

本文仿真环境如下:信道为高斯白噪声(Additive White Gaussian Noise,AWGN)信道,调制方式为BPSK调制,译码最大迭代次数均为50,使用QSPA译码算法。为了进一步分析不同有限域映射对多元LDPC 码性能的影响,本节构造了基于不同有限域阶上的多元LDPC码,并对其译码性能进行了分析。

例1:设q1=32,q2=4,8,16。基于GF(q1)构造基矩阵W,并将W中的非零元素置换为乘α循环置换矩阵,取γ=4、ρ=8构造基于GF(32)的LDPC码C0,码长n=248,码率R=0.552。通过文中定义的映射关系构造基于GF(4)、GF(8)、GF(16)的多元LDPC码C1、C2、C3。4种多元LDPC码的仿真性能曲线如图1和图2所示。

图1 (248,137 )LDPC码在各有限域上的误符号率

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

分析可知,在低信噪比时,通过文中提出的算法得到的具有低译码复杂度的LDPC码的性能均优于原有的LDPC码。随着信噪比的增加,4元LDPC码的瀑布区表现不够明显,在低误码率时性能不如GF(32)LDPC码,但基于GF(8)与GF(16)的LDPC码均具有较好的误码性能。在误符号率为10-5时,8元LDPC码相比于原LDPC码约有0.15 dB的性能增益。

例2:为分析算法对不同码率多元LDPC码的影响,设q1=64,q2=4、8,16。取γ=4、ρ=16构造基于GF(64)的LDPC码C0,码长n=1 008,码率R=0.765。通过有限域映射关系构造基于GF(4)、GF(8)、GF(16)的LDPC码C1、C2、C3,其仿真性能如图3和图4所示。

图3 (1 008,771)LDPC码在各有限域上的误符号率

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码的瀑布区性能有所提升;经过映射变换的3种LDPC码的编译码性能均优于原LDPC码,且在低信噪比时性能提升较为明显;当误符号率为10-5或误比特率为10-6时均约有0.2 dB的性能增益,并且经过映射变换的多元LDPC码具有更低的译码复杂度。相比于例1的仿真结果可知,利用本文的方法构造出的高码率多元LDPC码表现更优秀。

5 结束语

本文提出了一种以降低多元LDPC译码复杂度为目的LDPC码构造方法,利用有限域映射关系,将高阶有限域元素投影到指定的目标域上来构造多元LDPC码,能有效降低多元LDPC码的译码复杂度。与目前已有的构造方法相比,本文提出的方法能够方便地将LDPC码从大域映射到指定的小域,但在结构上依旧满足准循环特性,可用简单的移位寄存器实现,节约硬件资源,因此具有一定的实用价值。仿真结果表明,本文所构造的多元LDPC码在中低信噪比范围内具有更好的译码性能,当映射目标域的阶数大于4时,基本观察不到错误平层(在误比特率约为10-6时)。下一步可在有限域的映射关系以及硬件实现架构等方面展开进一步的研究。

[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] 郑丹玲,穆攀,田凯,等. 利用遗传算法构造QC-LDPC码[J].电讯技术,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] 黄胜,田凯,何丽,等.光通信中一种准循环非二进制LDPC码的新颖构造方法[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—),女,河南永城人,现为广西大学硕士研究生,主要研究方向为卫星导航基带信号处理算法、编码理论;

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—),男,河南开封人,硕士研究生;

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

Email:Lcc1202@126.com

陈海强(1976—),男,广西苍梧人,2011年于中山大学获博士学位,现为广西大学教授、硕士生导师,主要研究方向为编码理论和中继系统等;

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—),男,广西柳州人,教授、硕士生导师,主要研究方向为卫星导航基带信号处理算法、无线通信系统。

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

洪冰清,刘聪聪,陈海强,等.利用域间映射的多元QC-LDPC码构造[J].电讯技术,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

国家自然科学基金资助项目(61102090,61362010);广西自然科学基金资助项目(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

猜你喜欢
构造方法广西大学码率
面向可靠性预计的软件运行时行为模型构造方法
一种基于HEVC 和AVC 改进的码率控制算法
基于FPGA的多码率卷积编码器设计与实现
基于状态机的视频码率自适应算法
广西大学为毕业生制作今昔对比照
广西大学广西创新发展研究院简介
《梦溪笔谈》“甲子纳音”构造方法的数学分析
广西大学学报(自然科学版)2016年第41卷总目次
几乎最佳屏蔽二进序列偶构造方法
权力控制:权力清单制度背后的公法思维