可快速编码的大围长QC?LDPC码构造

刘原华 何华

摘 要： 为保证LDPC码在低编码复杂度的同时，减少短环对其迭代译码性能的影响，提出一种可快速编码的大围长准循环LDPC码构造方法。该方法将校验矩阵分成两部分，其中右半部分具有准双对角线结构，使其可利用校验矩阵直接进行快速编码，有效降低了LDPC码的编码复杂度；左半部分通过逐个设置其循环置换子矩阵以确保当前矩阵中的短环数最少，有效避免了短环的出现，保证了大围长的特性。仿真结果表明，与IEEE 802.16e中的LDPC码相比，新方法构造的LDPC码具有更大的围长和更少的短环，在低编码复杂度的基础上获得了更优的纠错性能。

关键词： LDPC码； 准循环； 循环置换矩阵； 快速编码； 校验矩阵； 编码复杂度

中图分类号： TN911.22?34 文献标识码： A 文章编号： 1004?373X（2018）11?0001?04

Construction of quasi?cyclic LDPC codes with fast encoding and large girth

LIU Yuanhua， HE Hua

（School of Communication and Information Engineering， Xian University of Posts and Telecommunications， Xian 710121， China）

Abstract： A construction method of quasi?cyclic （QC） LDPC codes with fast encoding and large girth is proposed to reduce the effect of short cycles on the performance of iterative decoding while maintaining the low encoding complexity of LDPC codes. The check matrix is divided into two parts. The right part of the matrix has the quasi?dual?diagonal structure， which can perform the fast encoding directly， and reduce the encoding complexity of LDPC codes effectively. The circulant permutation sub?matrices are set one by one in the left part of the matrix to ensure the minimum number of short cycles， avoid the occurrence of short cycles， and guarantee the characteristic of large girth. The simulation results show that， in comparison with LDPC codes in IEEE 802.16e， the codes constructed with the new method have larger girth and less short cycles， and better error correction performance while maintaining the low encoding complexity.

Keywords： LDPC code； quasi?cycle； circulant permutation matrix； fast encoding； check matrix； encoding complexity

0 引 言

低密度奇偶校验码（LDPC）具有逼近Shannon限的纠错性能[1?8]，近年来成为编码领域的研究热点，目前已得到广泛应用。如欧洲数字视频广播标准（DVB_S2），中国地面数字电视广播标准（DTMB），以及宽带无线接入标准IEEE 802.16e均已采纳LDPC码作为信道纠错编码方式。

LDPC码可分为随机LDPC码和结构化LDPC码。虽然随机构造法能获得较大的围长，设计出性能优异的LDPC码，但由于缺乏一定的结构特性，编码复杂度高，不利于硬件实现，且校验矩阵的硬件存储也较为复杂。而基于代数方法构造的结构化LDPC码虽具有循环或准循环结构，编码复杂度较低，但较难有效消除短环，导致LDPC码迭代译码性能损失。于是不断涌现出很多LDPC码新的构造方法。文献[1]提出一种不包含4环的准循环LDPC码（QC?LDPC码）构造方法，但该方法不能保证消除6环。文献[3]基于原模图构造出具有低编码和译码复杂度的LDPC码，但其未考虑校验矩阵的奇异性。事实上，一般代数方法构造的QC?LDPC码并不能保证校验矩阵满秩，即存在校验矩阵的行相关问题，导致构造生成矩阵非常困难[1]。文献[4]提出一种码率为[12]时的最佳度分布的QC?LDPC码构造方法，但其未考虑围长对迭代译码性能的影响。为确保在低编码复杂度的同时，减少短环对LDPC码迭代译码性能的影响，本文提出一种基于渐进环增长算法来构造大围长和线性编码复杂度的QC?LDPC码的方法。该方法利用渐进环增长算法有效避免了短环的产生，保证了大围长的特性，同时，所构造校验矩阵的右半部分具有准双对角线结构，保证了校验矩阵的奇异性，可直接利用校验矩阵进行快速迭代编码。与IEEE 802.16e标准中的LDPC码相比，本文构造出的QC?LDPC码具有更大的围长和更少的短环，在相同的编码复杂度下具有更优的纠错性能。

1 基于循环置换矩阵的QC?LDPC码

对于基于循环置换矩阵的QC?LDPC码，其校验矩阵[H]是由循环置换矩阵和零矩阵组成的矩阵阵列：

[H=Ia11Ia12…Ia1nIa21Ia22…Ia2n????Iam1Iam2…Iamn]

式中：[aij∈{-1，0，1，2，…，q-1}]；[Iaij]為[q×q]的循环置换矩阵，可由单位阵[I]每行向右循环移位[aij]位得到。[H]的零空间即码长为[N=nq]的QC?LDPC码。每个循环置换矩阵均可由其维数[q]和循环移位次数[aij]唯一确定，因此[H]所需的存储空间非常小，只需存储如下[m×n]大小的矩阵[Hb]即可：

[Hb=a11a12…a1na21a22…a2n????am1am2…amn]

式中：[Hb]称为矩阵[H]的基矩阵，将[Hb]中的每个元素[aij]用[q×q]的循环置换矩阵[Iaij]代替，即可得到矩阵[H，]此操作称为矩阵扩展。

2 校验矩阵的构造

2.1 渐进环增长算法

LDPC码的迭代置信传播（BP）译码算法是基于无环图的最优译码算法，以消息的独立性假设为前提，而LDPC码校验矩阵中的短环将会导致其迭代译码时的消息不满足独立性假设，具有一定的相关性，并且环长越短、短环数量越多，消息的相关性越严重，越影响迭代译码的性能。因此，设计LDPC码时必须尽量避免短环（尤其是4环6环）的出现。本文利用渐进环增长算法使得构造出的QC?LDPC码包含尽量少的短环，具有较大的围长。

二进制矩阵[H=（hij）M×N]中长为[2k]的环由满足如下条件的[2k]个[hij=1]的位置构成：

1） 任意相邻两个[hij=1]的位置均在[H]的同一行或者同一列；

2） 每个[hij=1]的位置均互不相同。

循环置换矩阵的每行每列有且仅有一个元素为1，因此对于基于循环置换矩阵的QC?LDPC码来说，环中任意两个相邻的[hij=1]的位置必定处在同一行块或者同一列块的循环置换矩阵中。因此，可以由基矩阵[Hb]中的元素构成的序列[（a1，a2，…，a2k）]来表示大矩阵[H]中长为[2k]的环，其中[ai∈Hb，1≤i≤2k]，[ai≠-1]，任意相邻元素[ai]和[ai+1]均在[Hb]的同一行或者同一列，[ai]和[ai+2]在不同行且不同列。文献[2]研究了[H]中长为[2k]的环的存在条件，满足定理1。

定理1[2]：对于基矩阵[Hb]中的序列[（a1，a2，…，a2k）]，其中[ai]和[ai+1]在同一行或者同一列，[ai]和[ai+2]在不同行且不同列，若满足如下等式：

[i=12k（-1）iai≡0modq] （1）

则该序列使矩阵[H]产生长为[2k]的环。

事实上，满足上述条件的序列[（a1，a2，…，a2k）]将使[H]中产生[q]个长为[2k]的环。对于基于循环置换矩阵的QC?LDPC码来说，只需设计一个维数很小的基矩阵[Hb，]然后通过矩阵扩展即可得到所需的稀疏大矩阵[H]，将其作为QC?LDPC码的校验矩阵。通过选取适当元素来构造[Hb，]使其不满足式（1）的条件，便可以避免甚至消除短环的出现，即可通过构造很小的基矩阵[Hb]来获得具有少量短环的大矩阵[H，]在很大程度上减小了构造QC?LDPC码的复杂度。另一方面，为统计短环的数量，也只需要对基矩阵[Hb]中的元素根据式（1）进行测试，就很容易统计出大矩阵[H]中的短环数目。

下面给出构造基矩阵[Hb]的渐进环增长算法，对于非规则QC?LDPC码来说，将[m]行[n]列的基矩阵[Hb]的第[j]列重记为[dv（j）]，渐进环增长算法构造[Hb]的具体步骤如下：

首先将[Hb]的每个元素初始化为-1， 对于[Hb]的第1列，随机选取[dv（1）]个位置，对于选取的每个位置，从集合[{0，1，2，…，q-1}]中随机选取一个数值作为该位置元素的取值。[Hb]其余元素的设置方法如下：

for j=2 to n

for i=1 to [dv（j）]

选择当前矩阵第j列中行重最小的行，记为第[ki]行

if i=1

从集合[{0，1，2，…，q-1}]中随机选取一个数值作为[Hb（k1，j）]

的取值。

else

对于每个[l

[q-1}]中的元素，并根据定理1统计每个取值对应的当前矩

阵4环的数量。

if存在多个取值对应无4环

统计其中每个元素对应的6环数量，对6环数最少的元 素统计其对应的8环数量。选择8环数最少的元素作为

[Hb（ki，j）]的取值。若存在多个元素对应最少的8环，则随

机选择其中一个作为[Hb（ki，j）]的取值。

else显示失败并退出

end

end

end

end

可以看出，渐进环增长算法通过逐个设置基矩阵的元素以确保当前矩阵中的短环数最少，可有效避免短环的出现，从而保证迭代译码的性能。通过适当选取[m，n]和[q]的取值，可以构造出各种码长和码率的QC?LDPC码。对于给定的行重和列重，该方法也可设计出对应的规则QC?LDPC码。

2.2 可快速编码的大围长QC?LDPC码构造

在构造LDPC码时还需考虑其编码复杂度问题。一般的编码方法是先由校验矩阵获得生成矩阵，再根据生成矩阵进行编码，其运算复杂度与码长的平方成正比。为解决编码复杂度问题，使其更易于硬件实现，IEEE 802.16e标准中采用具有特殊结构的QC?LDPC码，其校验矩阵的右半部分具有准双对角线结构，可以在保证校验矩阵满秩的同时直接利用校验矩阵进行快速迭代编码，具有较低的编码复杂度。由此，提出具有类似结构的校验矩阵的设计方法，进而获得可实现低编码复杂度的大围长QC?LDPC码。

将QC?LDPC码的校验矩阵及其基矩阵分成两部分：[H=[H1 H2]]，[Hb=[Hb1 Hb2]]，其中[H1]的维数为[mq×kq]，[H2]的维数为[mq×mq]，且[H2]的基矩阵具有式（2）的形式，其中[a1，a2，…，am，x]的取值从集合[{0，1，2，…，q-1}]中随机选取，第1列的元素[x]在[Hb2]的第[r]行，可以证明[H2]满秩[8]。根据[Hb1]每列的度分布参数，利用渐进环增长算法逐列构造[Hb1，]以确保当前矩阵中的短环数最少。

[Hb2=a1a2-1a2a3?a3a4-1-1a4?x??-1?am-2?-1am-2am-1-1am-1ama1am] （2）

2.3 快速编码算法

对于纠错码的系统码，可将码字向量分为两部分[c=[s p]]，其中第一部分[s=[s1 s2 … sk]]为信息向量；第二部分[p= [p1 p2 … pm]]为校验向量。对于QC?LDPC码的系统码来说，码字向量每一部分的子向量[si]和[pi]的长度均为[q]。由校验关系[H?cT=0]可得，[H1?sT=H2?pT]。将校验矩阵的左半边矩阵的基矩阵[Hb1]第i行第j列的元素记为[Hb1（i，j）]，则：

[Ia1Ia2I-1Ia2Ia3?Ia3Ia4I-1I-1Ia4?Ix??I-1?Iam-2?I-1Iam-2Iam-1I-1Iam-1IamIa1Iam?p1p2?pm=IHb1（1，1）IHb1（1，2）…IHb1（1，k）IHb1（2，1）IHb1（2，2）…IHb1（2，k）????IHb1（m，1）IHb1（m，2）…IHb1（m，k）?s1s2?sk （3）]

将式（3）展开可得到包含[m]个等式的方程组，将各式相加可得求解校验向量第一个子向量如下：

[p1=I-1x?i=1mj=1kIHb1（i，j）?sj] （4）

然后将式（3）中的[m]个等式逐个迭代可得计算校验向量其余子向量[pi]的迭代公式：

[pi=I-1ai?j=1kIHb1（i-1，j）?sj+Iai-1?pi-1， i=2，3，…，r，r+2，r+3，…，m] （5）

[pr+1=I-1ar+1?j=1kIHb1（r，j）?sj+Iar?pr+Ix?p1] （6）

从而得到码字向量[c=[s p]]。可以看出，该编码算法与IEEE 802.16e标准中编码算法的复杂度相同。

3 仿真结果

下面在加性高斯白噪声信道（AWGN）下采用BPSK调制方式，对利用新方法构造的QC?LDPC码和IEEE 802.16e标准中的QC?LDPC码的纠错性能进行仿真比较，采用置信传播（BP）译码算法，译码算法的最大迭代次数均设为100次。

图1显示了码长为2 304，码率分别为[12，23]以及[34]的QC?LDPC码的BER性能比较。为增大可比性，本文所提方法构造码的度分布与IEEE 802.16e中相同码率码的度分布完全相同，循环置换子矩阵的参数均为[q=96]。由仿真结果可以看出，与IEEE 802.16e中的码相比，新方法构造的各种码率的QC?LDPC码具有略优的BER纠错性能。

表1给出了码长为2 304的新方法构造码与IEEE 802.16e中码的短环统计结果。可以看出，码率为[12]和[23]时，新方法构造的QC?LDPC码围长均为8，而相同码率的IEEE 802.16e码的围长均为6；[34]码率的新方法构造码的围长为6，而该码率的IEEE 802.16e码的围长为4。统计结果显示，与同码长、同码率的IEEE 802.16e中的码相比，新方法构造的QC?LDPC码具有更大的围长和更少的短环。

4 结 语

本文研究了基于循环置换矩阵的QC?LDPC码构造方法，提出一种可快速编码的大围长QC?LDPC码构造方法。校验矩阵具有准双对角线结构，可利用校验矩阵直接进行简单快速编码，降低了硬件实现复杂度。利用渐进环增长算法逐个设置校验矩阵左半部分基矩阵的元素以确保当前矩阵中的短环数最少，有效避免了短环的出现。同时给出了简单快速编码的具体实现方法。仿真结果表明，与IEEE 802.16e标准中的LDPC码相比，新方法構造出的QC?LDPC码具有更大的围长和更少的短环，在低编码复杂度的基础上获得了更优的纠错性能。

参考文献

[1] ZHAO Y， XIAO Y. The necessary and sufficient condition of a class of quasi?cyclic LDPC codes without girth four [J]. IEICE transactions on communications， 2009， 92（1）： 306?309.

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

[3] DIVSALAR D， DOLINAR S， JONES C. Short protograph?based LDPC codes [C]// Proceedings of IEEE 2007 MIL Conference. [S.l.]： IEEE Press， 2007： 1387?1392.

[4] 周水红，端木春江，黄志亮，等.高性能准循环LDPC码构造方法的改进[J].计算机工程，2010，36（1）：277?279.

ZHOU S H， DUANMU C J， HUANG Z L， et al. Improvement of high?performance quasi?cyclic LDPC code construction method [J]. Computer engineering， 2010， 36（1）： 277?279.

[5] ZHANG L， LIN S， ABDEL?GHAFFAR K， et al. Quasi?cyclic LDPC codes on cyclic subgroups of finite fields [J]. IEEE transactions on communications， 2011， 59（9）： 2330?2336.

[6] LIU Y， ZHANG M， FAN J. Quasi?cyclic LDPC codes with high?rate and low error floor based on Euclidean geometries [J]. Journal of China Universities of Posts and Telecommunications， 2012， 19（2）： 96?99.

[7] LIU K， HUANG Q， LIN S， et al. Quasi?cyclic LDPC codes： construction and rank analysis of their parity?check matrices [C]// Proceedings of 2012 Information Theory and Applications Workshop. San Diego， CA： IEEE， 2012： 227?233.

[8] 朱磊基，汪涵，施玉松，等.QC?LDPC码基矩阵构造方法[J].现代电子技术，2012，35（5）：68?70.

ZHU L J， WANG H， SHI Y S， et al. Construction methods of basis matrix for QC?LDPC code [J]. Modern electronics technique， 2012， 35（5）： 68?70.

[9] 刘蕾，孙书龙，常亮，等.无短环不规则QC_LDPC码的快速编码及联合译码[J].现代电子技术，2015，38（17）：34?37.

LIU L， SUN S L， CHANG L， et al. Fast coding and joint decoding of irregular QC?LDPC codes without short?cycle [J]. Modern electronics technique， 2015， 38（17）： 34?37.

[10] 张轶，达新宇，苏一栋.任意列重大围长QC?LDPC码的确定性构造[J].电子学报，2016，44（8）：1814?1819.

ZHANG Y， DA X Y， SU Y D. Deterministic construction of QC?LDPC codes for any column weight with a large girth [J]. Acta electronica sinica， 2016， 44（8）： 1814?1819.