基于结构半随机LDPC码的协同编码通信

陈超然等

摘 要： 低密度奇偶校验码（LDPC码）具有逼近Shannon限的优异纠错性能，在信道编码领域的应用越来越广泛，但是LDPC码的编码复杂性一直是制约其普遍应用的突出问题。奇偶校验矩阵的结构则直接决定着LDPC码的编码复杂度和译码性能。提出一种准双对角线结构的半随机LDPC码奇偶校验矩阵的构造方法，它具有IEEE 802.16e标准LDPC码的优异纠错性能和低编码复杂度，同时在码率、码长、基础校验矩阵和扩展因子等设计方面更具灵活性，能更好地适应工程实践的需要。采用这种构造方法，以（16 384，8 192）LDPC码为例进行快速迭代编码，能够获得优异的译码性能，可以用于实现高速率低复杂度的LDPC译码器设计。

关键词： 低密度奇偶校验码； 半随机； 准双对角线； 快速编码算法

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

Research on semi?random LDPC code structure for fast encoding

CHEN Chao?ran， ZHENG Lin?hua， XIANG Liang?jun， LI Hua

（College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China）

Abstract： Low density parity check （LDPC） code has excellent error correction performance which approaches to Shannon limits， and widely applied in the field of channel encoding. However， the encoding complexity of the LDPC code is the prominent problem which restricts its universal applications. The encoding complexity and decoding performance of LDPC code are determined by the parity check matrix structure directly. The construction method of semi?random LDPC code parity check matrix based on quasi dual?diagonal structure is proposed. It has excellent error correction performance and low encoding complexity of LDPC code fitting with IEEE 802.16e standard， more flexibility design in code rate， code length， basis check matrix， extended factor and so on， and better satisfies the demands of engineering practice. Taking （16384， 8192） LDPC code as an example to proceed fast iterative encoding， the excellent decoding performance is obtained with the proposed construction method. It can be used to realize LDPC decoders design of high speed and low complexity.

Keywords： low density parity check code； semi?random； quasi dual?diagonal； fast encoding algorithm

0 引 言

低密度奇偶校验码（Low Density Parity Check Code，LDPC）是用稀疏校验矩阵或Tanner图定义的线性分组码。作为一种信道编码技术，其性能优异，构造灵活，描述简单，易于理论分析，是迄今为止最接近Shannon限的好码。1962年，R.Gallager博士在他的论文中最先提出了LDPC码，但是受限于当时计算机处理能力和研究条件，没能引起足够关注。直到20世纪90年代中期，对LDPC码理论的研究才开始复兴，随着超大规模集成电路的发展，LDPC码的硬件实现逐渐成为现实。LDPC码被公认为未来通信系统中最重要的纠错编码。

但是，LDPC码编码复杂度高的不利因素一直制约着它的普遍应用。如何寻找低复杂度的编码方法，减少对硬件存储空间的需求，一直是LDPC码应用研究的重要问题。随着学者们对LDPC码结构化构造方法的深入研究，其编码复杂度和所需的存储空间都有了大幅的降低。如IEEE 802.16e标准和DVB?S2标准的LDPC码通过在构造校验矩阵时引入特定的编码结构以此降低编码的复杂度。只要引入的特定结构中无四环或无低码重码，就不会影响码的性能。IEEE 802.16e标准的LDPC码是一种准循环LDPC码，可用[12，][23，][34]和[56]四种码速率，实现码长范围为576～230 4 b、间隔步长为96 b的编码方案。其每一种码速率都对应不同的编码矩阵，记为基础校验矩阵[Hb，]尺寸为[mb×nb。]其中，[nb]都为24，[mb]并不相同。奇偶校验矩阵[H]由基础校验矩阵[Hb]扩展而成。与一般准循环构造方法不同，IEEE 802.16e标准LDPC码的奇偶校验矩阵右半部分具有准双对角线的结构，编码复杂度更低。DVB?S2标准的LDPC码则采用简单的双对角线子矩阵实现迭代编码。由于双对角线子矩阵结构可能会产生低重码字，将带来一定的误码率损伤，而采用准双对角线结构则会避免出现这种情况，译码性能更加优异。

本文提出一种采用准双对角线结构来构造半随机LDPC码奇偶校验矩阵的方法，在IEEE 802.16e标准LDPC码的基础上，对基础矩阵[Hb]和扩展因子[z]的大小不作任何具体限制，可以更加灵活地实现不同码率和码长组合的编码设计。采用这种方法构造出的是一种混合结构的奇偶校验矩阵，矩阵的左半部分是随机构造的基础矩阵，能够确保编码的优异性能；矩阵右半部分采用准双对角线结构，确保了编码的低复杂度。这种构造方法面向快速迭代编码，可以不经高斯消元由校验矩阵[H]直接编码，在大码长高速率的情况下具有更好的译码性能。本文以（16 384，8 192）LDPC码为例进行验证，并给出快速编码算法，以期在LDPC译码器设计中实现低复杂度和高速率。

1 准双对角线结构校验矩阵的构造方法

定义LDPC码的奇偶校验矩阵[H]大小为[m×n]，信息比特长度[k=n-m。]定义基础校验矩阵[Hb]大小为[mb×nb，][Hb]中的元素对应于[H]的子矩阵[P，]则[H]可以表示为：

[H=P0，0P0，1P0，2???P0，nb-2P0，nb-1P1，0P1，1P1，2???P1，nb-2P1，nb-1P2，0P2，1P2，2???P2，nb-2P2，nb-1??????Pmb-1，0Pmb-1，1Pmb-1，2???Pmb-1，nb-2Pmb-1，nb-1]

式中：[Pi，j]是一个[z×z]大小的循环单位矩阵，或是一个[z×z]大小的全零矩阵。[Hb]中的元素扩展后得到[H。]此处，[n=nb×z，][m=mb×z，][z]表示扩展因子。扩展时，将[Hb]中的“1”用一个[z×z]大小的循环单位矩阵[Pi，j]替换，将[Hb]中的“0”用一个[z×z]大小的全零矩阵[Pi，j]替换。

通常循环单位矩阵[Pi，j]都是由单位矩阵简单地循环右移得到的，不同的循环右移矩阵可以用不同的移位步数来表示，得到归一化的基础校验矩阵[Hbm，]其大小和二进制基础校验矩阵[Hb]相同。[Hb]中每一个“0”用“[-1]”替代，表示一个[z×z]的全零矩阵；其中的每一个“1”用一个非负整数的循环移位次数[Pi，j]表示。这样归一化的基础校验矩阵[Hbm]可以直接扩展为奇偶校验矩阵[H。]

[Hb]可以分成两部分，写成[Hb=[Hb1Hb2]]的形式。其中：[Hb1]表示系统比特部分，尺寸为[mb×kb，][kb=nb-mb；][Hb2]表示校验比特部分，尺寸为[mb×mb。][Hb2]可以进一步分解为两部分，[hb]有奇数的重量，[H′b2]是一个双对角线结构，第[i]行第[j]列的矩阵元素满足[i=j]和[i=j+1]时为“1”，其他时候均为“0”。

[Hb2=hbH′b2=hb0hb1?hbm-110111??1101]

式中：[hb]有固定的[hb0=1，][hbmb-1=1]及[hbj=1，][0

下面，选定[12]码率的（16 384，8 192）LDPC码采用上述准双对角线结构构造出它的奇偶校验矩阵[H。]首先设定扩展因子[z=1 024，]则基础校验矩阵[Hb]的尺寸为[8×16，]即[mb=8，][nb=16。]其中的元素为[1 024×1 024]的循环单位矩阵或全零矩阵。将[Hb]中的所有元素进行[z×z]矩阵的替换，就得到[12]码率（16 384，8 192）LDPC码的奇偶校验矩阵[H，]如图1所示。

2 快速迭代编码算法

利用上述构造方法中LDPC码基础校验矩阵[Hb]的准双对角线结构，直接由校验矩阵[H]进行迭代编码，可以简化编码复杂度，具体步骤描述如下：

首先，将奇偶校验矩阵[H]的基础校验矩阵写成[Hb=[Hb1Hb2]]的形式。定义其中的矩阵[Zq，]即若[q]为非负整数，[Zq]是大小为[z×z]的置换矩阵，由单位矩阵右移[q]位得到，若[q]为[-1]，则[Zq]为全零矩阵。其中[Hb2]除第一列外，其余部分是双对角线结构。

[Hb1=ZHb1（1，1）ZHb1（1，2）…ZHb1（1，kb）ZHb1（2，1）ZHb1（2，2）…ZHb1（2，kb）????ZHb1（mb，1）ZHb1（mb，2）…ZHb1（mb，kb）]

[Hb2=Zh（1）Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zh（r）??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0Zh（mb）Z0]

定义编码器输出行向量为[c，]其长度为[n=k+m，]信息位向量为[s，]校验位向量为[p，]则[c=sp]。

将[sT]和[pT]进行分段，每段长度为[z]，则有：

[sT=[sT1sT2…sTkb]pT=[pT1pT2…pTmb]]

其中，

[si=si-1z+1si-1z+2…sizT，i=1，2，…，kb] [pi=pi-1z+1pi-1z+2…pizT，i=1，2，…，mb] 根据校验等式[H?cT=0]，可得[H2?pT=H1?sT。]定义基础校验矩阵[Hb]的子矩阵[Hb1]中位于[i，j]位置的元素为[Hb1i，j，]根据[Zq]的定义和[Hb2]的形式可得：

[Zh1Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zhr??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0ZhmbZ0?p1p2?pmb]

[=ZHb11，1ZHb11，2…ZHb11，kbZHb12，1ZHb12，2…ZHb12，kb????ZHb1mb，1ZHb1mb，2…ZHb1mb，kb?s1s2?skb]

展开后可以推得：

[p1=（Zh（1）+Zh（r）+Zh（mb））-1?i=1mbj=1kbZHb1（i，j）?sTj]

将[p1]代回到上式，可得：

[p2=j=1kbZHb1（1，j）?sj+Zh（1）?p1]

以此方法类推，可得出求[p]各个分量[pi]的迭代公式：

[pr+1=pr+j=1kbZHb1（r，j）?sTj+Zh（r）?p1pi=pi-1+j=1kbZHb1（i-1，j）?sTj，i=3，4，…，r，r+2，r+3，…，mb]

对于选定的（16 384，8 192）LDPC码，其奇偶校验矩阵[H]为[16 384×8 192]的准循环矩阵，由8×16个1 024×1 024的循环子矩阵构成，每个子矩阵是单位循环移位矩阵或全零矩阵。

首先，将待编码的大小为1×8 192的信息向量[s]分成8个1×1 024的子向量[s=s1…s8。]

然后，由[pi]的迭代公式依次计算出[p1～p8，]如下面的式子所示，由此得出[p=p1…p8。]

[p1=i=18j=18ZHb1（i，j）?sTjp2=j=18ZHb1（1，j）?sj+Zh（1）?p1p3=p2+j=18ZHb1（2，j）?sTjp4=p3+j=18ZHb1（3，j）?sTjp5=p4+j=18ZHb1（4，j）?sTj+Zh（4）?p1p6=p5+j=18ZHb1（5，j）?sTjp7=p6+j=18ZHb1（6，j）?sTjp8=p7+j=18ZHb1（7，j）?sTj]

最后，组合[s]和[p，]得到码字[c，]完成编码。

由于在编码的过程中只涉及到向量的移位运算和加法运算，故在存储校验矩阵[H]时不需要存储整个矩阵，只需存储一个[8×16]的基础校验矩阵[Hb，]简化了编码复杂度。

3 译码性能仿真

在对准双对角线结构LDPC码的构造方法和快速迭代编码算法描述的基础上，本节主要通过系统仿真验证采用这种构造方法的LDPC码的纠错性能，为下一步译码器的硬件设计提供理论依据。

首先，通过仿真对采用准双对角线结构的IEEE 8.2.16e标准LDPC码和采用简单的双对角线结构的DVB?S2标准LDPC码的误码性能进行分析比较。选取码长为16 200、码率为[12]的LDPC码，采用归一化最小和（NMS）算法进行译码，设置最大迭代次数为15次，归一化因子[α]取0.85。性能仿真图如图2所示。

由图2可以看出，IEEE 802.16e标准LDPC码的误码率性能要远远好于DVB?S2标准LDPC码，采用准双对角线结构能获得更加优异的误码性能。

以下仿真主要以本文选取的（16 384，8 192）LDPC码为例进行误码性能的分析验证。

从图3可以看出，在误比特率为[10-6]时，采用准双对角线结构的（16 384，8 192）LDPC码的性能与无编码时相比有9.5 dB的增益，具有优异的误码率性能。同时，与图2的结果对比可知，本文所描述的LDPC码构造方法与IEEE 802.16e标准中的构造方法具有同样优异的误码率性能，而且能够在实际设计中增加灵活性，为LDPC译码器硬件实现提供了更多的设计方案。

4 结 语

本文介绍了一种采用准双对角线结构构造半随机LDPC码奇偶校验矩阵的方法，并以（16 384，8 192）LDPC码为例完成了快速迭代编码。通过对IEEE 802.16e标准LDPC码编码方法的改进，增强了译码器设计的灵活性，确保了低编码复杂度和高译码性能。最后，基于归一化最小和译码算法进行了仿真验证，得到了理想的译码性能。通过本文的研究，以期在下一步LDPC译码器硬件实现中获得更优异的译码性能和更低的译码复杂度。

参考文献

[1] RICHARDSON T J， URBANKE R L. The capacity of low density parity check codes under message passing decoding [J]. IEEE Transactions on Information Theory， 2001， 47（2）： 599?618.

[2] KOU Yu， LIN Shu， FOSSORIER M P C. Low?density parity?check codes based on finite geometries： a rediscovery and new results [J]. IEEE Transactions on Information Theory， 2001， 47（7）： 2711?2736.

[3] 贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.

[4] 肖扬.Turbo与LDPC编解码及其应用[M].北京：人民邮电出版社，2010.

[5] 袁东风，张海刚.LDPC码理论与应用[M].北京：人民邮电出版社，2008.

[6] 张仲明.高速数传中LDPC码关键技术研究[D].长沙：国防科学技术大学，2009.

[7] 雷菁，高永强，王建辉，等.基于串行消息传递机制的QC?LDPC码快速译码算法研究[J].电子与信息学报，2008，30（12）：2938?2942.

[8] 张庆林，文思群，胡旭洋，等.基于CCSDS标准的LDPC编译码应用技术研究[J].计算机光盘软件与应用，2013（15）：65?66.

[9] 孙钰林，吴增印，王菊花.CCSDS中LDPC码编码器的FPGA设计与实现[J].空间电子技术，2011（3）：30?34.

[10] 兰天.一种CCSDS深空标准的LDPC码高效实现[J].飞行器测控学报，2012（6）：41?46.