基于Hoey序列的QC-LDPC码构造方法

2017-06-19朱继华梁梦琪胡潇月袁建国

重庆邮电大学学报(自然科学版) 2017年3期

关键词：构造方法码率译码

朱继华，梁梦琪，胡潇月，郭乔，袁建国

(重庆邮电大学光电信息感测与传输技术重庆市重点实验室，重庆 400065)

基于Hoey序列的QC-LDPC码构造方法

朱继华，梁梦琪，胡潇月，郭乔，袁建国

(重庆邮电大学光电信息感测与传输技术重庆市重点实验室，重庆 400065)

基于Hoey序列提出了一种列重为3，并环长至少为8的准循环低密度奇偶校验(quasi-cyclic low-density parity-check, QC-LDPC)码的新颖构造方法，该构造方法能避免短环的产生，有较好的纠错性能，可通过改变参数值进而改变码长和码率。对提出的构造方法进行了环长至少为8的证明，用Matlab搭建了通信系统的仿真模型，并在此模型基础上对基于该构造方法构造的QC-LDPC(900,452)码进行了仿真分析，仿真平台是在高斯白噪声(additive white Gaussian noise, AWGN)信道下，调制方式为二进制相移键控(binary phase shift keying, BPSK)调制，译码算法为和积算法(sum product algorithm, SPA)。仿真结果表明，当误码率(bit error rate, BER)相同时，利用该构造方法所构造的QC-LDPC(900,452)码的净编码增益(net coding gain, NCG)比基于等差数列(arithmetic progression sequence, APS)构造的QC-LDPC(896,452)码以及基于最大公约数(greatest common divisor, GCD)构造的QC-LDPC(900,453)码的NCG都提高了，且所有码的码率均为0.5。

准循环低密度奇偶校验(QC-LDPC)码；Hoey序列；误码率(BER)；净编码增益(NCG)

0 引言

低密度奇偶校验(low-density parity-check,LDPC)码作为一种基于稀疏奇偶校验矩阵的线性分组码，易于进行理论分析和研究，它的性能逼近香农限，译码也比较简单且可实行并行操作，适合硬件的实现，是一种具有较好纠错性能的好码[1-2]。准循环低密度奇偶(quasi-cyclic low-density parity-check，QC-LDPC)码是结构化LDPC码里最有潜力的一种分类，有较低的编译码复杂度并在硬件上容易实现，因此，近几年对于QC-LDPC码的研究成为了一个热点[3-5]。

围长是影响QC-LDPC码性能的重要因素，在译码算法为和积算法(sum product algorithm,SPA)时，会因为短环的存在损失一定的性能。比如，围长为4时，相关节点的信息经过2次迭代就能传回给本身，如果消息是错误的，那么就会得到错误传播，进而导致译码产生错误甚至不能进行正确的译码，所以，关于QC-LDPC码围长的研究也变得尤为重要[6-9]。有很多方式来构造围长至少为8的QC-LDPC码，包括直接构造的方式[10]和消除短环的构造方式[11]。直接构造方式就是在构造校验矩阵的时候就避免短环，消除短环构造方式则是在构造好校验矩阵的基础上，采取其他的手段进而消除短环，例如修饰技术。本文采取的是直接构造的方式，在构造校验矩阵的时候避免了四环、六环2种短环，所以，在译码的时候不会因为这2种短环的存在而损失一定的性能，进而具有较好的纠错性能。

基于Hoey序列，本文提出了当列重为3时，围长至少为8的构造方法。此外，构造了列重为3，码率为0.5的QC-LDPC(900,452)码并对其性能进行了仿真，仿真结果表明，其具有较好的纠错性能。

1 Hoey序列的定义

Hoey序列Ai(i=0,1,2,…)是一类特殊的整数序列，有如下特点[12]：Ai中每个元素均为非负整数且不相同；Ai是一个递增序列；Ai中相邻2个元素之差也是一个递增序列；Ai中任意2个元素之和均不相同。

对于i=0,1,…,49,Ai中前20个元素为0,1,3,7,12,20,30,44,65,80,96,122,147,181,203,251,289,360,400,474。

2 Girth-8的成立条件

定理[5]令(a1,a2,…,a2l-1,a2l)是指数矩阵E(H)中的序列，其中，ai和ai+1在同一行或者在同一列，而ai和ai+2在不同行且不同列，若存在最小正整数r使(1)式成立，则序列(a1,a2,…,a2l-1,a2l)使校验矩阵H中存在长度为2lr的环。

(1)

(1)式中，P是指数矩阵E(H)的扩展因子。

假设指数矩阵E(H)的大小为J×L,其中，J是指数矩阵的列重，L是指数矩阵的行重。根据定理不存在girth-4的条件是令0≤i

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))=0modP

(2)

而(2)式不成立则可推导为(3)，(4)式。

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))≠0

(3)

P≥|(E(i,t)+E(j,s))-(E(i,s)+E(j,t))|+1

(4)

不存在girth-6的条件：令0≤i

(5)

同样(5)式不成立可推导为(6)，(7)式。

综上所述，指数矩阵E(H)满足(3)，(4)式，则其不存在girth-4；指数矩阵E(H)满足(6)，(7)式，则其不存在girth-6。

3 基于Hoey序列的QC-LDPC码的构造方法

3.1 列重为3的QC-LDPC码构造方法

首先构造一个指数矩阵E(H)，其维数为3×L。它的第1行为全0元素，第2行和第3行元素依次从上到下错位排列，第2行和第3行元素分别为Ai(i=0,1,2,…)序列中的A0,A1,A3,…,A2L-3和A2,A4,A6,…,A2L-1。也就是说，第2行元素(除去第1个元素A0)为序列中排列序号为奇数的元素；第3行元素(除去最后1个元素A2L-1)为排列序号为偶数的元素。指数矩阵E(H)的构造为

(8)

从(8)式中可看到，指数矩阵E(H)有2个特点：除第1行元素外，它的每行、每列都是递增数列以及它的第3行中两元素之差的绝对值是大于第2行中与其同列的两元素之差的绝对值，这是由Hoey序列中相邻2个元素之差是一个递增序列这一特点得到。

然后对所构造的指数矩阵E(H)进行填充，E(H)中的0元素用P×P的单位矩阵替换，Ai则用相应的单位矩阵右循环移位Ai位所得到的矩阵进行替换，最终构成校验矩阵H。其中，P的取值为P≥max(A2L-1,A2L-2+A2L-3-A2-A2L-5,A2L-1+A1-A4-A0)+1，校验矩阵H的构造为

(9)

(9)式中：I0表示单位矩阵；IAi则表示单位矩阵右循环移位Hoey序列中的Ai位所得到的矩阵。从(9)式可看出，通过改变行重L和扩展因子P的值，可以改变QC-LDPC码的码长及码率。

3.2 环长至少为8的性质证明

为了证明H对应的Tanner图中的环长至少为8，要依次证明Tanner图中没有girth-4和girth-6。

3.2.1 不存在girth-4的性质证明

对于girth-4，只有一种形式，其中，0≤it(s

证明：如果girth-4是存在第1行与第2行之间或第1行与第3行之间，如图1a所示，且由指数矩阵E(H)的定义可知，第1行元素为全0元素，所以，(3)，(4)式可推导为(10)，(11)式：

E(j,s)-E(j,t)≠0

(10)

P≥|E(j,s)-E(j,t)|+1

(11)

又由Hoey序列Ai中每个元素均为非负整数且不相同的特点可知(10)式是成立的。在指数矩阵中除第1行元素外，每行、每列都是递增数列，所以

|E(j,s)-E(j,t)|

(12)

而在指数矩阵中,E(j,s)的最大值为A2L-1，所以

|E(j,s)-E(j,t)|+1

(13)

则(11)式可推导为

P≥A2L-1+1

(14)

而上面所提出的构造方法中P的取值满足(14)式，所以，(11)式成立。

如果girth-4是存在第2行与第3行之间，girth-4如图1b所示，那么由Hoey序列Ai中任意2个元素之和均不相同的特点可知，(3)式是成立的。同样，因为指数矩阵E(H)中除第1行元素外，每行、每列都是递增数列，所以，E(i,s)>E(i,t)，从而可得到

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))

(15)

由指数矩阵的第3行中两元素之差的绝对值大于第2行中与其同列的两元素之差的绝对值这一特点可得

(E(j,s)-E(j,t))-(E(i,s)-E(i,t))>0

(16)

所以，可推导出(17)式

(17)

而在指数矩阵中,E(j,s)的最大值为A2L-1，所以

(18)

则(4)式也可推导为(14)式。上面所提出的构造方法中P的取值满足(14)式，所以，(4)式成立。

证毕。

综上所述，本文提出列重为3的QC-LDPC码的构造方法是不存在girth-4的。

图1 girth-4的形式Fig.1 Types of girth-4

3.2.2 不存在girth-6的性质证明

对于girth-6，有6种存在形式，如图2所示。其中，i=0,k=1,j=2，0≤s,t,r≤L-1，在下面的证明中，假设s

图2 girth-6的6种形式Fig.2 Six types of girth-6

证明：第1行元素都为0，所以，对于第1种girth-6形式，(6)，(7)式分别可推导为

(E(j,s)+E(k,r))-(E(j,r)+E(k,t))≠0

(19)

(20)

同样，由Hoey序列Ai中任意2个元素之和均不相同的特点可得到(19)式是成立的，其他4种girth-6的证明与其一样。但是要满足(7)式成立，这里需将girth-6的6种形式分类讨论。

对于1，2，5，6这4种girth-6的形式，它们的证明是一样的，如图3所示。只证明第1种girth-6，其形式见图3a。

图3 girth-6的3种形式Fig.3 Three types of girth-6

因为指数矩阵E(H)中除第1行元素外，每行、每列都是递增数列，第3行中两元素之差的绝对值大于第2行中与其同列的两元素之差的绝对值。所以，根据第1个特点以及结合以上2个特点可以分别推出

E(k,r)>E(k,t)

(21)

(E(j,r)-E(j,s))-(E(k,r)-E(k,t))>0

(22)

从而可推导出

有数据显示，在美国每天就有5亿支吸管被遗弃（这意味着每人每天大约1.5支的消耗量）。有专门负责清理海滩垃圾的环保组织在一项研究中声称，美国各地的海滩上每年废弃的吸管大约有75亿支之多。

(23)

而在指数矩阵中,E(j,r)的最大值为A2L-1，所以

(24)

则(20)式可推导为(14)式，上面，所提出的构造方法P的取值满足(14)式，所以(20)式成立，进而(7)式也成立。

对于3，4这2种girth-6的形式，首先将(7)式分别转化成(25)、(26)式：

由于指数矩阵E(H)中的第3行中两元素之差的绝对值大于第2行中与其同列的两元素之差的绝对值，那么，2种形式的证明都用到取极限值的方法，将第3行中差值的绝对值取到最大，如图3b，图3c所示，这样就使(25)、(26)式中P的最小值取到最大，分别为A2L-1+A1-A4-A0+1、A2L-2+A2L-3-A2-A2L-5+1，所以，可推导出

P≥A2L-1+A1-A4-A0+1

(27)

P≥A2L-2+A2L-3-A2-A2L-5+1

(28)

上面所提出的构造方法中P的取值满足(27)，(28)式，则(7)式成立。

证毕。

综上所述，本文提出列重为3的QC-LDPC码的构造方法是不存在girth-6的。

4 仿真及性能分析

首先利用本文的构造方法构造一个QC-LDPC码，列重为J=3，行重L=6，其指数矩阵为

(29)

P的选值为

所以本文选取P=150，则码长为900，则校验矩阵为

(30)

(30)式中：I0表示单位矩阵；IAi则表示单位矩阵右循环移位Hoey序列中的Ai位所得到的矩阵，单位矩阵的大小为150×150，最终可得到行重为6，列重为3，码率为0.5的QC-LDPC(900, 452)码。

本文对所构造的QC-LDPC(900, 452)码进行仿真时的仿真环境具体如下：仿真工具为Matlab，仿真平台是在高斯白噪声(additive white Gaussian noise, AWGN)信道下，调制方式为二进制相移键控(binary phase shift keying,BPSK)调制，译码算法为SPA算法。迭代次数取16次，因为虽随着迭代次数的增加，其纠错性能逐渐变好，但当迭代次数由16增加到32时，其纠错性能只是稍有改善。因而综合考虑译码复杂度及译码性能，本文在对QC-LDPC码进行仿真时选取迭代次数为16。

再将QC-LDPC(900, 452)码与同码率的基于等差数列构造[6]的QC-LDPC(896,452)码、基于最大公约数构造[7]的QC-LDPC(900,453)码进行对比分析，如图4所示。从图4可知，在误码率为10-5时，本文所构造的QC-LDPC(900,452)码与基于等差数列构造的QC-LDPC(896,452)码以及基于最大公约数构造的QC-LDPC(900,453)码的编码增益分别为0.66 dB和2.64 dB。

图4 QC-LDPC(900,452)码与其他码的纠错性能仿真图Fig.4 Comparison graph of the error correction performances among the QC-LDPC(900,452) code and the other codes

5 结论

本文提出了一种基于Hoey序列构造QC-LDPC码的新颖方法，能避免四环、六环2种短环的产生，在译码时不会因这2种短环的存在而损失一定的性能，因此具有较好的纠错性能，并可通过改变参数L的值进而改变码长和码率，但本文只提出了列重为3的构造方法，所以，相较于列重较大的构造方法，码率的选择不够全面，因为对于相同的行重，随着列重的增加，码率的选择也会增加，争取在以后的研究中完善这一点，提出列重较大的构造方法。另外，构造了列重为3的QC-LDPC(900,452)码，仿真结果表明，它的纠错性能优于同码率的基于等差数列构造的QC-LDPC码以及基于最大公约数构造的QC-LDPC码。

[1] HUANG Qin, DIAO Qiuju, LIN Shu, et al. Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets[J]. IEEE Transactions on Information Theory, 2012, 58(5):2648-2671.

[2] 袁建国，刘飞龙，杨松.一种光通信中基于LDPC码的新颖级联码[J].半导体光电，2014,35(2):293-295,299. YUAN Jianguo, LIU Feilong, YANG Song. A Novel Concatenated Code Based on LDPC Codes for Optical Communications[J]. Semiconductor Optoelectronics, 2014, 35(2):293-295, 299.

[3] LI Juane, LIU Keke, LIN Shu, et al. Algebraic Quasi-Cyclic LDPC Codes: Construction, Low Error-Floor, Large Girth and a Reduced-Complexity Decoding Scheme[J]. IEEE Transactions on Communications, 2014, 62(8): 2626-2637.

[4] 翟云云,包小敏,邓伦治,等.基于QC-LDPC码的信息协调协议[J].西南大学学报:自然科学版,2013,35(9):161-165. QU Yunyun. BAO Xiaomin, DENG Lunzhi, et al. An Information Reconciliation Protocol Based QC-LDPC cade[J]. Journal of Southwest University: Natural Science Edition, 2013, 35(9): 161-165.

[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] ZHANG Yi, DA Xinyu. Construction of girth-eight QC-LDPC codes from arithmetic progression sequence with large column weight[J]. IET Electronics Letters , 2015, 51(16):1257-1259.

[7] ZHANG Guohua,RONG Sun,WANG Xinmei.Construction of Girth-Eight QC-LDPC Codes from Greatest Common Divisor[J].IEEE Communications Letters,2013,17(2):369-372.

[8] ZHANG Jiahua, ZHANG Guohua. Deterministic Girth-Eight QC-LDPC Codes with Large Column Weight[J]. IEEE Communications Letters, 2014, 18(4):656-659.

[9] WANG Juhua, ZHANG Guohua. Coset-based QC-LDPC codes without small cycles[J]. IET Electronics Letters, 2014 50(22):1597-1598.

[10] YANG L, LIU H. Code construction and FPGA implementation of a low-error-floor multi-rate low-density parity-check code decoder[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2006, 53(4): 892-904.

[11] WANG Y, YEDIDIA J S. Construction of high-girth QC-LDPC codes[C]//Turbo Codes and Related Topics, IEEE 5th International Symposium on. Lausanne, Switzerland: IEEE Press, 2008:180-185.

[12] GE X, XIA S T. Structured non-binary LDPC codes with large girth[J]. IET Electronics Letters, 2007, 43(22): 1220-1221.

(编辑：刘勇)

s：The National Natural Science Foundation of China (61472464); The Natural Science Foundation of Chongqing Science and Technology Commission (cstc2015jcyjA0554)； The Undergraduate Science Research Training Project for Chongqing University of Posts and Telecommunications in 2016 (A2016-61).

Novel construction method of QC-LDPC codes based on Hoey sequences

ZHU Jihua, Liang Mengqi, HU Xiaoyue, Guo Qiao, Yuan Jianguo
(Chongqing Key Laboratory of Photoelectronic Information Sensing and Transmitting Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

A novel construction method of quasi-cyclic low-density parity-check(QC-LDPC) codes with girth of at least eight and the column weight of the constructed QC-LDPC code is 3 based on Hoey sequence is proposed. The novel construction method can avoid short-girth and has better error-correction performance. Moreover, the code length and the code rate can be adjusted by selecting different parameters. Firstly, the girth of at least eight in the proposed novel construction method is proved, and then the simulation model of communication system is established by Matlab program. And based on the model, the QC-LDPC(900,452) code constructed by the proposed construction method is emulated and analyzed. The simulation environments are addictive white Gaussian noise(AWGN) channel, binary phase shift keying(BPSK) modulation method and the decoding algorithm of the sum product algorithm(SPA). The simulation results show when the bit error rate (BER) is the same, the net coding gain(NCG) of the QC-LDPC(900,452) code is more than those of the QC-LDPC(896,452) code constructed by the construction method based on the arithmetic progression sequence(APS) and the QC-LDPC(900,453) code constructed by the construction method based on the greatest common divisor(GCD). Furthermore, all the codes have the same code rate of 50%.

quasi-cyclic low-density parity-check(QC-LDPC)code;Hoey sequence;bit error rate(BER);net coding gain(NCG)

2015-12-08

2016-10-15 通讯作者：袁建国 yuanjg@cqupt.edu.cn

国家自然科学基金(61472464)；重庆市基础与前沿研究计划项目(cstc2015jcyjA0554);2016年重庆邮电大学大学生科研训练计划项目(A2016-61)

10.3979/j.issn.1673-825X.2017.03.009

TN911

1673-825X(2017)03-0341-05