一种改进的码率兼容QC-LDPC码构造算法

范仁基，赵旦峰

(哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001)

0 引言

LDPC码(Low-Density Parity-Check code)[1]是目前最为接近Shannon极限的一种纠错码，受到人们极大的重视。近年来，为了更好地适应各种通信系统多速率要求，LDPC码的码率兼容特性成为了一个研究和实现要点[2]，特别是随着无人机被广泛地应用于各领域[3]，研究具有码率兼容的LDPC码意义重大。

目前多码率的实现方法主要有3种：删余型、扩展型和缩短型。删余型是目前应用最为广泛的码率兼容形式，通过选取一个性能优异的低码率母码，然后对校验位进行删余打孔处理实现多码率，这样可以节省存储空间，但在删余打孔时，存在产生大量陷阱集[4-5]导致性能恶化的问题；扩展型是通过扩展矩阵或校验节点分裂方式实现，有效地克服了删余型存在的问题，但也造成了需要存储多个校验矩阵[4]，大量占用硬件资源的问题；缩短型不同于前两者，是通过对输入的信息序列进行处理实现多码率，其虽然克服了扩展型带来的矩阵存储问题，却也因为需要信息序列预处理而增加了编译码的复杂度。因此有必要找到一种能够较好地兼顾多码率性能以及硬件资源占用的LDPC码。本文将PEG算法与准循环法相结合[6]，通过正逆向两次使用PEG算法构造具有下三角形式的准循环校验矩阵，在实现多个码率兼容的同时，各码率下码字性能与同参数下的准循环矩阵性能接近，而且其硬件实现较之前的QC-LDPC码更为简单，码率控制更为灵活，尤其适合于硬件资源有限且通信环境复杂的无人机使用。

1 LDPC码概述

LDPC码是一种线性分组码，若其对应校验矩阵为H，则其生成矩阵G唯一确定，其码长为n，信息序列长为k，校验矩阵H的维数为m×n,m=n-k。二元域GF(2)上的一个3×6校验矩阵可以如图1所示，当存在序列c满足HcT=0时，c为该LDPC码的一个码字。

图1 3×6校验矩阵

LDPC码的另一种描述形式为Tanner图[7]，一种由变量节点、校验节点以及两类节点间的边构成的图描述，如图2所示。选取Tanner图中某一节点为根节点，选取与之相连接的节点作为子节点并以边相连，重复操作，直至没有新生节点或出现重复节点为止，这样就可以得到一个树形展开图[7]。树图可以更为便利地研究LDPC校验矩阵的特性。

图2 校验矩阵的Tanner图

在Tanner图中，从某一节点出发，经过若干节点后返回此点为一循环(Cycle)，经过的边的数目为这一循环的长度，而这其中最短的环长记为Girth，如图2中所列举的环，即为6环。由于LDPC的译码通常采用BP译码算法或基于BP算法改进而来的和积译码算法[7]，在译码时，某一节点的信息会经过最短的环路传回自身，这样就会破坏节点更新过程中信息的独立传播特性，导致译码收敛速度减慢甚至译码失败。因此在构造LDPC码校验矩阵时，要尽可能地消除短环，增大最短环长Girth。

2 QC-LDPC码校验矩阵的结构和特性

QC-LDPC(Quasi-Cyclic LDPC)码是一种基于循环置换矩阵的LDPC码，由单位阵的循环置换矩阵和零矩阵构成其校验矩阵[8]。以mb×nb维的准循环LDPC码的校验矩阵H为例，可以表示为式(1):

(1)

式中，I(Pij)(1≤i≤m,1≤j≤n)是一个右循环移位的b×b维方阵，可以通过单位阵I的每行经过Pij次右移得到，当Pij=0时，I(Pij)为单位阵，当Pij=-1时，I(Pij)为零矩阵。

由此也可以得到另外两个重要矩阵，即由Pij组成的循环移位参数矩阵(2)以及基矩阵(3)：

(2)

(3)

而当这两个矩阵被确定的同时，LDPC的校验矩阵也随之确定下来。通过对比LDPC校验矩阵H与其基矩阵A，不难发现这二者具有相同的度分布[9,10]，而且其循环移位参数矩阵P具有如下特性：

若在一个循环块边长为b的QC-LDPC校验矩阵的Tanner图中，存在一条长度为2l的环，那么其循环移位参数矩阵P中同样存在这样环的充要条件[10]为:

(4)

根据这一特性，在基矩阵确定的条件下，校验矩阵的最小环长不小于其基矩阵中的最小环长。因此可以通过调整循环移位参数矩阵P中各元素的数值，从而进一步消减短环扩大Girth，提升QC-LDPC校验矩阵的性能。

3 PEG算法

PEG(Progress Edge Growth)算法[6,11-12]是在Tanner图中选取一点为起点，在确保从该点出发的环长最大的条件下，不断向节点之间添加边的一种算法。PEG算法可以很好地保证任意一点的环长尽可能大，从而尽可能地增大Girth。

图3 PEG算法的构造流程

PEG算法的复杂度会随码长增加而急剧增高，因此该算法通常用于中、短码构造，而且构造过程中对于校验矩阵的全局优化不足，容易产生大量公共节点，因其环分布复杂，也会对矩阵性能造成一定降低。特别是由于PEG采用随机构造方法，导致校验矩阵缺乏结构性，硬件实现复杂度高，更不利于在无人机LDPC码中使用。

4 改进的码率兼容QC-LDPC码构造

PEG算法在中、短LDPC码构造上表现优异，其本身最大缺陷在于硬件实现复杂度高，而QC-LDPC码在工程实现性上有很大优势，刚好可以对PEG法进行一定弥补，同时PEG算法也可以为QC-LDPC提供更大的围长，因此可以将两种构造方法相结合，进行联合构造。本文首先采用PEG算法，构造一个高码率校验矩阵的基矩阵，然后在其基础上，进行码率扩展构造出码率兼容的基矩阵。

但由于基本的PEG算法本身并不适用于码率兼容矩阵构造，而在校验矩阵构造时，PEG算法可以有效地控制最短环的长度，这给构造码率兼容的LDPC码校验矩阵奠定了良好基础，因此这里提出一种逆向PEG算法，可以在不改变最短环长的条件下，降低校验矩阵的码率以实现校码率范围的扩展。

图4 逆向PEG算法流程图

通过分析算法流程可知，逆向PEG算法中对于每个新增的校验节点除第一次添加边是直接选择度数最低的变量节点外，都是在进行深度为2l的树展开后，才向新校验节点添加新边，这样可以有效保证新增校验节点与原校验矩阵所组成的环长度均是大于2l的，也从而确保了拓展后的LDPC校验矩阵中Girth保持不变，仅增大校验矩阵的平均环长，来提升校验矩阵的性能。这样就可以通过逆向PEG算法，实现码率兼容基矩阵的构造，最后通过将基矩阵中的各“1”元素和“0”元素分别用循环移位矩阵以及零矩阵进行替换，最终完成码率兼容的QC-LDPC码的构造。

在对基矩阵进行扩展时，从本文第2节循环矩阵特性得知，通过合理地调整各循环移位矩阵的移位参数，可以实现对矩阵结构优化以及码字性能的提升。下面通过Tanner图进一步讨论如何设置循环移位矩阵参数。

结合公式(4)，令：

ΔPiPj(t)=Pi,t-Pj,t

(5)

这样可以得到另外一个重要性质[9]：校验矩阵中H的Girth不小于2(l+1)的重要条件为：

(6)

因此若要使得Girth不小于2(l+1)，需要每次添加循环移位参数时确保式(6)成立，这样才能尽可能消减矩阵内的短环。综上所述，码率兼容QC-LDPC码的构造算法具体步骤如图5所示。

图5 改进的码率兼容QC-LDPC码构造流程图

逆向PEG扩展得到基矩阵是在用PEG构造的高码率基矩阵的基础上得到的，使得基矩阵具备了多码率兼容特性的同时，还确保了基矩阵中的最小环长不发生变化。而循环移位参数矩阵与零矩阵参与的替换过程，使得矩阵中的环长进一步增大，进一步减少了短环数量，提高了码字的纠错性能，也令其硬件可实现性得到很大简化，更加利于资源受限的无人机等设备使用。

5 仿真结果与分析

本设计以信息序列长为288 bit，码率涵盖3/4、2/3、1/2进行仿真分析。以3/4码率为母矩阵进行扩展构造，并使用MATLAB对矩阵性能进行仿真，得出该LDPC 码分别在几个不同码率下的误码率性能，仿真曲线如图6所示。此外，在1/2码率下将本设计与IEEE 802.16e标准的LDPC码(q=24，即信息序列长为288 bit) 以及DVB-S2标准的LDPC缩短码(信息序列长为300 bit)进行性能对比研究，仿真曲线如图7所示。为了便于比较，输入信号为二进制伪随机序列，编码器采用BPSK调制，信道为AWGN信道，最大迭代次数为25，均采用最小和MS译码算法。

图6 信息位长288 bit码字性能

图7 1/2码率下LDPC码性能对比

由图6可见，本设计生成的码率兼容QC-LDPC码在其所涵盖的3种码率下都具有较为优秀的误码率性能，在BER=10-6时，3/4码率与1/2码率的LDPC码的性能差异在1 dB左右。由图7可知，相近码长情况下，1/2码率的码率兼容QC-LDPC码性能略差于DVB-S2标准的LDPC缩短码，但是在归一化信噪比为3.5 dB时二者性能一致。而与IEEE 802.16e标准的LDPC码相比，在误码率为10-4～10-6的区间下，码率兼容QC-LDPC码的性能始终有着约0.5 dB的差距。综上所述，本设计生成的QC-LDPC码在保证性能优异的同时实现了多码率兼容，具有良好的实用性。

6 结论

本文提出一种基于PEG算法的QC-LDPC码构造方法，通过该方法可以构造出具有下三角结构的、兼容多个码率及码长的、且易于硬件实现的QC-LDPC码。该构造方法通过正反向PEG算法来实现码率兼容，并通过优化循环移位参数的设计，弥补PEG算法自身存在的问题，更进一步消除构造矩阵中存在的短环。仿真结果表明了该方法构造出来的QC-LDPC码在几种码率下都具有较为突出的性能，且因为具有下三角结构，更加便于硬件实现，尤其适合于硬件资源受限条件下，这为无人机今后在多种传输条件下的广泛应用提供了可能性。

[1] GALLAGER R G. Low-density parity-check codes[M].M.I.T. Press, 1963.

[2] 王琪，谢求亮，王昭诚.定码长多码率QC-LDPC码的构造[J].清华大学学报(自然科学版)，2013(3)：394-398.

[3] 朱铁林，秦凡，李凤翔,等.应用于无人机测控传输系统的多元LDPC码[J].电讯技术，2014(12)：1622-1626.

[4] LI J, NARAYANAN K R. Rate-compatible low density parity check codes for capacity-approaching ARQ scheme in packet data communications[C]//IASTED International Conference on Communications, 2002: 201-206.

[5] YAZDANI M R, BANIHASHEMI A H. On construction of rate-compatible low-density parity-check codes[J]. Communications Letters IEEE, 2004,8(3):159-161.

[6] 张建斌.基于PEG算法的准循环LDPC码构造研究[J].电子器件，2012，35(6)：647-651.

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

[8] VASIC B, DJORDJEVIC I B. Quasicyclic low-density parity check codes[C]//International Conference on Telecommunications in Modern Satellite, 2005: 417-420.

[9] FOSSORIER M. Quasicyclic low density parity check codes[C].Proceedings in IEEE International Symposium on Information Theory, Yokohama, Japan, 2003: 150-151.

[10] 管武，项海格.具有大码间距和大环路的QC-LDPC码的构造[J].新能源进展，2011，16(4)：1-5.

[11] XIAO H, BANIHASHEMI A H. Improved progressive-edge-growth (PEG) construction of irregular LDPC codes[C]//Global Telecommunications Conference, 2004. GLOBEC, 2004: 489-492.

[12] HU X Y, ELEFTHERIOU E, ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs[J]. IEEE Transactions on Information Theory, 2005, 51(1): 386-398.