陈为刚 曹 艳 夏晓晓 杨晋生

面向卫星导航系统的多进制LDPC码的构造

陈为刚 曹 艳 夏晓晓 杨晋生

(天津大学电子信息工程学院 天津 300072)

面向卫星导航系统应用，设计一种性能优越且编码复杂度低的多进制低密度奇偶校验(LDPC)码。结合渐进边增长(PEG)算法与准循环扩展的半随机构造法，并优化非零元素的选择，构造与新一代卫星导航系统IS-GPS-800接口标准中参数一致的多进制LDPC码。进一步，通过将校验矩阵转换为重复累加码(RA)码的校验矩阵结构，实现低复杂度编码。仿真结果表明，与卫星导航系统IS-GPS-800接口标准中码长码率相同的二进制LDPC码相比，多进制LDPC码有明显的编码增益，且其编码复杂度较低。

卫星导航系统 多进制低密度奇偶校验码 半随机构造法

0 引 言

卫星导航系统具有全球性、实时性、全天候和高精度的特点，可提供导航、定位与授时服务，在国家安全与人们日常生活中发挥着越来越重要的作用。早期的GPS L1 C/A采用汉明码作为信道编码方案，但仅可以检错并不能纠错。随着前向纠错技术的发展，大多数的现代导航系统采用卷积码作为信道编码，与汉明码相比，卷积码获得了大约5 dB的性能增益。2013年，新一代卫星导航系统IS-GPS-800接口规范中采用了低密度奇偶校验(LDPC)码作为信道编码[1]。LDPC码可获得逼近香农极限的性能，并且复杂度适中。因此，LDPC码将有望取代卷积码而成为未来导航系统中的信道编码方案。

LDPC码校验矩阵的构造直接影响LDPC码的实现复杂度和纠错性能。LDPC码校验矩阵的构造方法主要分为：随机构造方法、结构化构造方法以及半随机构造方法等。随机构造的LDPC码的优点是码长和码率设计灵活，可很好地匹配由密度演化等方法得到的最优度分布，但其编码复杂度往往较高，不利于硬件实现。而结构化的校验矩阵可有效降低编码复杂度，但这种构造方法一般难于根据优化的度分布设计非规则码，译码门限性能较差。半随机构造方法结合了随机构造和结构化构造的优点，是比较实用的LDPC码构造方法，比较常见的半随机构造方法有重复累加(RA)码的构造方法[2]，准循环构造方法[3]等。这些方法，一方面可较好地适合由密度演化等方法得到的度分布，另一方面也具有比较好的结构，编译码复杂度低。因此这类LDPC码已被多种标准采用，例如欧洲第二代卫星数字广播、无线城域网等。

与二进制LDPC码相比，中短码长的多进制LDPC码[4,5]纠错能力更强，且可以有效纠正突发错误，因此受到广泛关注。本文采用基于渐进边增长(PEG)算法结合准循环扩展，并通过优化非零元素选择，构造了一种与新一代卫星导航系统IS-GPS-800接口标准中参数一致的多进制LDPC码。由于构造的多进制LDPC码的校验矩阵可通过行列交织、简单调整后转换为多进制RA码的校验矩阵结构，编码复杂度较低。仿真表明，相较于IS-GPS-800接口标准中的LDPC码，本文所构造的多进制LDPC码有明显编码增益，且其编码复杂度较低。

1 多进制LDPC码的构造

在本文中，设计的多进制LDPC码采用一种多步生成的半随机构造方法，即首先构造一个MB×NB的基矩阵；然后将基矩阵的每个元素扩展为B×B的子矩阵，进而得到M×N的二进制校验矩阵Hb，其中M=MB×B，N=NB×B；最后利用GF(q)上的非零元素替代二进制矩阵Hb中的“1”，得到多进制LDPC码的校验矩阵H。下面详细介绍本设计中多进制LDPC码的构造方法。

步骤1：基矩阵的设计

根据码长和码率，确定基矩阵的大小。然后根据节点的度数和围长的设定要求，依次对每个变量节点选择合适的校验节点进行连边。在本设计中，基矩阵的大小是2×4，行重和列重分别为2和4，即基矩阵是大小为2×4的全1矩阵。

步骤2：采用PEG算法的基矩阵准循环扩展

完成大小为MB×NB的基矩阵的构造后，将基矩阵的每个元素扩展为B×B的子矩阵。在本实现中，采用循环置换矩阵替代基矩阵中的“1”元素，以全零阵替代基矩阵中的“0”元素，并采用PEG算法[6]确保在用B×B的子矩阵替换基矩阵中的元素后校验矩阵仍满足设定的围长要求。

由于置换矩阵的循环性，PEG算法不再是以单个变量节点逐个向Tanner图中添加边，而是以一组变量节点(B个)的形式添加。对于每个变量节点组，只需以第一个变量节点为根进行深度为l的扩展，而其它变量节点所连接的校验节点自动确定[7]。

图1 以变量节点sj为根进行深度为l的扩展

步骤3：非零元素的配置

在采用PEG算法得到扩展的二进制矩阵后，需要对非零元素进行配置。非零元素的配置对多进制LDPC码的性能影响很大，可随机取自集合{α0,α1,…,αq-2}，也可进行优化。Davey和Mackay通过蒙特卡洛法，搜索GF(q)上行重为dc时的最优非零值[4]。而Poulliat C等人利用非零元素的二进制矩阵替代非零元素，得到一个等价的二进制校验矩阵，然后再进行优化分析，该优化方法的基本思想是搜索可使最小码字距离dmin最大的非零值，从而使得校验节点传递给变量节点的消息更可靠[8]。本文采用的优化方法是通过优化非零元素的位置，尽量消除短环上可能形成的低重码字，因此可有效减少低重码字的数量，改善多进制码的性能，尤其是高信噪比下的性能。具体地，对定义在有限域GF(64)上行重dc=4的多进制LDPC码，每一行选择的最优值均为α0、α9、α22和α37。

此外，通过以上方法构造的多进制LDPC码可通过缩短和删余操作对码长和码率进行小的调整。其中，对缩短码，发送端将被缩短的比特设定为一个确定的序列，如全0序列，然后再进行编码，接收端在被缩短比特对应的位置按照确定的序列进行译码。而删余则是有选择地删除编码后码字序列中的若干校验位比特，接收端在删余比特对应位置的信道先验信息为0。

2 多进制LDPC码的编码方案

多进制LDPC码的编码一般有两种方法：基于生成矩阵的编码方法和基于校验矩阵的编码方法。基于生成矩阵的编码方法的运算量和存储量较大，不利于硬件实现，因此多采用基于校验矩阵的编码方法[9]。

考虑到RA码的编码器较为简单，可实现线性时间编码[10]，本文设计的LDPC码的校验矩阵经线性变换并略微调整后转换为多进制RA码的校验矩阵结构，因此可直接采用RA编码器进行编码。具体地，对校验矩阵H=[HmHc〗的右侧矩阵Hc(行重和列重都为2)进行行交织和列交织，使非零元素位于双对角线和矩阵的最右上角上，并删除最右上角的元素。在对Hc进行行列交织时，为保证变量节点和校验节点之间的校验关系不变，Hm也要进行相同的行交织。Hc经行列交织和修改后的矩阵结构如下式所示，

(1)

其中αki,j∈GF(q)，i=0，j=1或1≤i≤(M?1)，j=0,1。

假定c=[m p]表示一个码字，其中m和p分别表示信息符号向量和校验符号向量。为方便，修改后的校验矩阵仍记为H=[HmHc]，则有:

H·cT=[Hm,Hc]·[m,p]T

=Hm·mT+Hc·pT=0T

(2)

因此，编码后的校验位向量为:

(3)

由于Hc为双对角线矩阵，则上式中Hc-1为下三角矩阵，因此可采用累加器实现，构造的多进制LDPC码的编码器结构如图2所示，其中αk由矩阵Hc的次对角线与主对角线上的非零值决定。

图2 多进制QC-LDPC码的编码器框图

在编码后，将得到的校验位向量p与信息位向量m一起，构成最终的码字向量c=[m p]。

为设计与IS-GPS-800接口标准中LDPC码的码长和码率一致的多进制LDPC码，本文采用了截短和删余方法微调有关参数。其中，针对IS-GPS-800标准中码长为548，码率为0.5的LDPC码，具体参数设计如下，采用半随机构造法构造了一个定义在有限域GF(64)上的多进制LDPC码，其基矩阵是大小为2×4的全1矩阵，扩展因子为23。基于这些参数，构造的多进制LDPC码的码长为552，码率为0.5。去掉两个信息比特，即在274位信息比特前补充两个0比特，然后再进行编码。编码后，删余两个校验比特。因此传输长度成为548个比特。在译码端，在被缩短比特的对应位置按照确定的0序列进行译码。

3 优化设计与仿真结果

以IS-GPS-800标准中规定的两种码长的LDPC码为参照，本文采用基于PEG算法与准循环扩展的半随机构造法设计了定义在有限域GF(64)上的LDPC码。为与IS-GPS-800标准中码长为1200，码率为0.5的LDPC码进行对比，设计了参数完全相同的多进制LDPC码，其校验矩阵的基矩阵是大小为2×4的全1矩阵，扩展因子为50。同样，为与IS-GPS-800标准中码长548，码率0.5的LDPC码进行对比，构造出的多进制LDPC码的基矩阵也是大小为2×4的全1矩阵，扩展因子为23。两个多进制LDPC码的校验矩阵每一行的非零值均为α0，α9，α22和α37。基于这样的参数构造的LDPC码码长为552。为与标准中LDPC码的码长相同，采用截短和删余操作，使传输码长变为548。

为降低构造的多进制LDPC码的误码平层，采用全局优化方法[8]来避免产生低重码字的环。对于环长为l的环，如果其等价的二进制矩阵是满秩的，则该环不会产生码字，因此该环的存在不会影响LDPC码的性能。为避免环长为l的环产生低重码字，可通过改变校验矩阵对应行的非零元素的值，来确保环长为l的环满足满秩条件。表1和表2分别给出了构造的两种LDPC码的优化结果，包括Tanner图优化后的环个数和非零元素优化后产生低重码字的环个数。

表1 定义在GF(64)上的(274,548)码的优化结果

表2 定义在GF(64)上的(600,1200)码的优化结果

图3和图4分别为构造的多进制LDPC码与IS-GPS-800接口标准中的两种二进制LDPC码采用置信传播(BP)算法时的误比特率和误帧率的性能比较，其中迭代次数为40。从图中可看出，与IS-GPS-800接口标准中码长为1200，码率为0.5的二进制LDPC码相比，在BER为10-7或FER为10-5时，设计的多进制LDPC码可获得约0.25 dB的性能增益。而相较于IS-GPS-800接口标准中码长为548，码率为0.5的二进制LDPC码，在BER为10-7或FER为10-5时，设计的多进制LDPC码可获得约0.6 dB的性能增益。

图3 设计的多进制LDPC码与IS-GPS-800标准中两种二进制LDPC码的误比特率比较

图4 设计的多进制LDPC码与IS-GPS-800标准中两种二进制LDPC码的误帧率比较

4 结 语

在本文中，结合PEG算法与准随机扩展的半随机方法，并对非零元素进行优化，构造了适用于卫星导航系统的多进制LDPC码，给出其高效编码方案。仿真结果表明，相较于卫星导航系统IS-GPS-800接口标准中的二进制LDPC码，设计的多进制LDPC码有明显的性能增益，且编码复杂度较低。由于优化时间的原因，本文中仿真所采用的多进制LDPC码仍存在进一步参数优化的空间，为设计实现适合卫星导航系统应用的多进制LDPC码提供了新的选项。下一步将设计更为高效的优化方法优化多进制LDPC码。

[1] GPS Navstar Joint Program Office.Navstar GPS space segment/user segment L1C interface [S].IS-GPS-800C,2013.

[2] Jin H,Khandekar A.Irregular repeat-accunulate codes [C]// Proc.the 2nd International Smposium on Turbo Codes & Related Topics.Best,France:IEEE Press,2000:1-8.

[3] Li Z,Kumar B.A class of good quasi-cyclic low-densigy parity check codes based on progressive edge growth graph [C]// Proc.Conference Record of the Thirty-Eighth Asilomar Conference on Signals,Systems and Computers.CA,USA:IEEE Press,2004:1990-1994.

[4] Davey M C,MacKay D.Low-density parity-check codes over GF(q) [C]// Proc.IEEE Information Theory Workshop.Killarney,Ireland:IEEE Press,1998:70-71.

[5] Zhang L,Tan L,Zeng F.A novel family of nonbinary LDPC codes over finite fields [C]// Proc.International Conference on Information Science and Control Engineering.Shenzhen,China:IEEE Press,2012:1-5.

[6] Hu X Y,Eleftheriou E,Amold D M.Progressive edge-growth tanner graphs [C]// Proc.IEEE Global Telecommunications Conference.San Antonio,USA:IEEE Press,2001:995-1001.

[7] Healy C T,de Lamare R C.Quasi-cyclic low-desity parity-check codes based on decoder optimised progressive edge growth for short blocks [C]// Proc.IEEE International Conference on Acoustics,Speech and Signal Processing.Kyoto,Japan:IEEE Press,2012:2889- 2992.

[8] Poulliat C,Fossorier M,Declercq D.Design of regular (2,dc)-LDPC codes over GF(q) using their binary images [J].IEEE Transactions on Communications,2008,56(10):1626-1635.

[9] 詹伟,梁俊杰.低编码复杂度不规则LDPC码的构造方法[J].计算机工程与应用,2010,46(28):102-104.

[10] Chen W,Liang C,Guo T,et al.Encoder implementation with FPGA for non-binary LDPC codes [C]// Proc.18th Asia Pacific Conference on Communications.Jeju,Korea:IEEE Press,2012:980-984.

CONSTRUCTING NON-BINARY LDPC CODES FOR SATELLITE NAVIGATION SYSTEMS

Chen Weigang Cao Yan Xia Xiaoxiao Yang Jinsheng

(SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China)

We designed a kind of non-binary low-density parity-check (NB-LDPC) codes with superior performance and low encoding complexity for the application of satellite navigation systems.In our design,we constructed the NB-LDPC codes with same parameters as the binary LDPC codes in IS-GPS-800 interface standard of new generation satellite navigation system by combining the semi-random construction method based on progressive-edge-growth (PEG) algorithm and quasi-cyclic expansion and optimising the non-zero elements selection.Furthermore,by converting parity-check matrix to the check matrix structure of repeat-accumulate (RA) codes,we implemented the low complexity encoding.Simulation results demonstrated that,the designed NB-LDPC codes has noticeable encoding gain and lower encoding complexity compared with the binary LDPC codes in same code length and code rate in IS-GPS-800 interface standard of satellite navigation system.

Satellite navigation system Non-binary LDPC codes Semi-random construction method

2014-10-27。国家自然科学基金项目(61101114)；教育部新世纪优秀人才支持计划项目(NCET-12-0401)；天津市科技兴海项目(KJXp011-2);天津大学自主创新基金项目(60301002,60301014)。陈为刚，副教授，主研领域：高效编码调制，无线网络及应用。曹艳，硕士生。夏晓晓，硕士生。杨晋生，副教授。

TP911.2

A

10.3969/j.issn.1000-386x.2016.04.026