北斗卫星导航系统多进制LDPC编码性能评估*

宿晨庚，黄 勤，刘旭楠

(1. 国防科技大学 电子科学学院， 湖南 长沙 410073； 2. 北京跟踪与通信技术研究所， 北京 100094；3. 北京航空航天大学 电子信息工程学院， 北京 100191； 4. 国家海洋局海洋减灾中心， 北京 100194)

北斗卫星导航系统是我国自主建设的卫星导航系统，能够全天时、全天候为全球用户提供定位、导航、授时服务。由于卫星导航系统传输距离遥远、通信环境复杂，卫星导航系统的落地信号功率很低，容易受到干扰，在复杂遮挡环境下可能出现失锁或不能正常定位的问题，因此在导航电文设计中一般采用纠错编码获取编码增益来提升恶劣环境下的解调性能。

目前世界上的全球卫星导航系统主要有美国GPS，欧洲Galileo系统，俄罗斯GLONASS以及中国的北斗系统。随着技术水平的提高，各大系统在现代化升级过程中越来越多地采用性能更优的纠错编码。其中，GPS现代化导航电文使用了码率为1/2的二进制LDPC码；Galileo导航电文采用码率为1/2的卷积码；北斗区域系统导航电文采用了BCH码；新发布的“北斗三号”现代化新信号B1C和B2a信号导航电文采用了64进制LDPC编码。

LDPC码是一类译码性能接近信道极限的线性分组码。1962年，Gallager在他的博士论文中首次提出了LDPC码[1]。1981年，Tanner引入了LDPC码的一种全新解释，即Tanner图表示法[2]。到了20世纪90年代，MacKay等研究人员开始研究图编码和迭代译码，使得LDPC码得到了重新发展和进一步的推广[3-4]。基于置信度传播迭代译码的[5-6]长LDPC码已经被证明能够获得距离香农(Shannon)极限零点几分贝的误码性能。二进制LDPC码已在深空通信、光纤通信、卫星数字视频、数字水印、磁/光/全息存储、移动和固定无线通信、电缆调制/解调器和数字用户线(Digital Subscribe Line,DSL)等领域中得到广泛应用[7]。

多进制LDPC码是继二进制LDPC码后最受关注的一类纠错码。较之二进制LDPC码，其纠错能力更强(尤其对于中、短码长)、错误平台更低、译码收敛更加迅速，且天然地适合高阶调制解调[8-14]。它们不仅是信道编码领域近年来最大的研究热点，更引起了工业界的广泛重视[15-17]。2008年欧洲电信研究所(Eurescom)联合三星公司立项研究了多进制LDPC码在无线通信中的应用。2012年前后，世界存储芯片两大巨头LSI和Marvell都推出了使用多进制LDPC码的硬盘芯片。2013年，美国宇航局(National Aeronautics and Space Administration,NASA)计划在某些任务中使用多进制LDPC码。2014年，我国863计划5G项目组也立项重点研究多进制LDPC码——“5G新型编码调制技术研究开发”。

北斗系统首次在卫星导航系统中采用多进制LDPC编码[18-19]，本文将对北斗B1C和B2a信号采用的多进制LDPC编码方案进行研究，对编译码性能、资源消耗进行分析，并在硬件平台上进行试验验证。

1 多进制LDPC编码原理

与二进制LDPC码相比，多进制LDPC码具有对错误更加敏感，译码信噪比门限更低，译码收敛更加迅速等特点。这些优点使得多进制LDPC码能够为导航星地链路通信提供更高的信噪比增益，以缓解链路预算的紧张。

1.1 编码原理

LDPC码是线性分组码的一种，标准的编码方式就是信息序列m与生成矩阵G相乘。一般多进制LDPC码编码方法就是利用高斯消去法，将译码矩阵化成一个下三角矩阵，然后通过行变换将译码矩阵化成右边为单位阵的形式H=[G|I]，这样就能得到系统型的编码矩阵G=[I|PT]。

1.2 译码原理

LDPC码的纠错能力很大程度上取决于它的译码算法。LDPC码的译码算法有很多种，主要可分为硬判决算法和软判决算法。硬判决算法实现复杂度比软判决算法要低，但是其译码性能(纠错能力)不及软判决译码算法。

和积算法[5-6](Sum-Product Algorithm，SPA)是LDPC码软判决译码算法中最具有代表性的一种迭代译码算法。它的基本译码原理为从信道获得每一个码字符号的置信软信息，然后通过迭代处理接收符号，基于奇偶校验和(由接收符号的硬判决和LDPC码的稀疏奇偶校验矩阵H计算得到)提高每个译码符号的可信度。

Tanner图是LDPC码校验矩阵的一种二分图表示方法，如图1所示。LDPC码的迭代译码算法就是基于Tanner图的迭代译码算法。

图1 LDPC码的Tanner图Fig.1 Tanner graphs of LDPC codes

Tanner图中的节点被分成了两类，变量节点(Variable Node,VN)和校验节点(Check Node,CN)。其中每一个变量节点VN都代表码字中的一个符号，对应于译码矩阵中的一列；每一个校验节点代表一个校验方程，对应于译码矩阵中的一行；连接变量节点与校验节点之间的线称之为边，对应于译码矩阵中不为0的元素。

从Tanner图上来看，LDPC码可以当作是一组单奇偶校验(Single Parity Check,SPC)码与一组重复(REPetition,REP)码的交错连接，如图2所示。

图2 LDPC码的译码模型Fig.2 Decoding model of LDPC codes

图2中的SPC码和REP码是LDPC码译码的两个基本模型。译码就是置信信息通过边在变量节点与校验节点之间迭代的过程。首先，信道接收到的信息传递给变量节点，每个变量节点向与之相连的每个校验节点发送更新信息，这就是SPC译码模型的工作。每个校验节点通过计算向与之相连的变量节点发送更新信息，这是REP译码模型的工作。整个译码过程从VN开始，不断地重复，直到所有校验方程都满足，或者达到最大迭代次数停止。

和积译码算法(Sum Product Algorithm，SPA)以及Min-Sum译码算法都符合上述原理。只不过Min-Sum译码算法是SPA算法的近似计算，通过稍微牺牲译码性能而将译码的计算复杂度降低为线性复杂度。

多进制LDPC码的实际应用是兼容二进制信息的，相当于它的每一个变量节点又连接着多个小节点，如图3所示。

图3 多进制LDPC码变量节点Fig.3 Variable node of M-ary LDPC codes

在多进制LDPC码的Tanner中校验节点，变量节点以及边上传递的信息都是定义在GF(q)上。为了兼容二进制，变量节点会连接许多小节点，这些小节点每一个代表着比特信息。正是由于多进制LDPC码的结构特点，使得多进制LDPC码相比于二进制LDPC码有更强的错误敏感性，如图4所示。

图4 多进制LDPC码的错误敏感性Fig.4 Typical error pattern of M-ary LDPC codes

图4中，校验节点相连的变量节点都有两个发生了错误。对于二进制LDPC码来说，校验节点的校验运算是基于GF(2)的加法，当有两个比特发生错误时检验结果为0；多进制LDPC码的校验运算是基于GF(q)的加法，当两个变量节点上的两个比特发生错误时，变量节点的值分别变为“2”和 “1”，所以校验的结果为“3”。由此可见，多进制LDPC码对比特错误有更强的敏感性，更容易发现错误并进行纠错。

多进制LDPC码的译码原理与二进制相类似，常用的也是基于Tanner图的置信度信息传播算法，如SPA算法。与二进制不同的是，在多进制SPA译码算法中，迭代不再是比特的置信度信息而是多进制符号的置信度信息。以定义在GF(28)上的多进制LDPC码为例来说明，在译码的初始化过程中，每一个定义在GF(28)上多进制符号的置信度都是由信道中8个比特的置信度获得。这样使得每个多进制符号都有256种状态，从而参与迭代的数据量相比于二进制码大大提高。

扩展最小和(Extended Min Sum，EMS)算法是二进制Min-Sum算法的多进制推广算法。它的基本思想是通过置信度排序，舍弃置信度较低的符号软信息，从而达到降低传递数据的目的。

2 北斗系统多进制LDPC编码方案

根据北斗系统空间信号接口控制文件B1C和B2a(1.0版)，北斗系统新信号将采用64进制LDPC编码方案。

2.1 B1C信号编码方案

B1C信号电文格式命名为B-CNAV1，电文数据调制在B1C数据分量上。每帧电文长度为1800符号位，符号速率为100 帧/s，播发周期为18 s。基本的帧结构定义如图5所示。

图5 B-CNAV1帧结构Fig.5 B-CNAV1 frame structure

其中，子帧2采用64进制LDPC(200,100)编码，其每个码字符号由6 bits构成，定义于本原多项式为p(x)=1+x+x6的有限域GF(26)。信息长度k=100码字符号，即600 bits。其校验矩阵是一个100×200稀疏矩阵H100,200，前100×100部分对应信息符号，后100×100部分对应校验符号。

子帧3采用64进制LDPC(88,44)编码，其每个码字符号同样由6 bits构成，定义于本原多项式为p(x)=1+x+x6的有限域GF(26)。信息长度k=44码字符号，即264 bits。其校验矩阵是一个44×88的稀疏矩阵H44,88，前44×44部分对应信息符号，后44×44部分对应校验符号。

2.2 B2a信号编码方案

B2a信号导航电文格式命名为B-CNAV2，电文数据调制在B2a数据分量上。每帧电文长度为600符号位，符号速率为200 帧/s，播发周期为3 s。基本的帧结构定义如图6所示。

B-CNAV2导航电文采用64进制LDPC(96,48)编码，其每个码字符号同样由6 bits构成，定义于本原多项式为p(x)=1+x+x6的有限域GF(26)。信息长度k=48码字符号，即288 bits。其校验矩阵是一个48×96稀疏矩阵H48,96，前48×48部分对应信息符号，后48×48部分对应校验符号。

图6 B-CNAV2帧结构Fig.6 B-CNAV2 frame structure

3 北斗系统多进制LDPC编码性能分析

本节主要就北斗采用的多进制LDPC编码方案和GPS采用的二进制LDPC编码方案的编译码性能、资源消耗进行对比分析。定义北斗多进制LDPC编码方案64进制LDPC(96,48)、64进制LDPC(200,100)、64进制LDPC(88,44)分别为多进制LDPC码A、B、C，设计相应长度的二进制LDPC编码方案作为参考，分别为二进制(576, 288)、二进制(1200, 600)和二进制(528, 264)。

3.1 性能仿真分析

在加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道下采用二进制相移键控(Binary Phase Shift Keying，BPSK)调制，利用非全零随机码字分别对二进制和多进制LDPC码进行了仿真。

3.1.1 多进制LDPC码A

多进制LDPC码A与二进制(576, 288)码有相同的码长和编码效率，其纠错性能对比分析如图7所示。

(a) 多进制LDPC码A与二进制(576, 288)码性能对比(a) Performance comparison between 64-ary LDPC code A and binary (576, 288) code

(b) 多进制LDPC码A与二进制(576, 288)码和Turbo码性能对比(b) Performance comparison between 64-ary LDPC code A, binary (576, 288) code and Turbo code图7 多进制LDPC码A与二进制(576, 288)码在AWGN信道下性能对比Fig.7 Performance comparison between 64-ary LDPC code A and binary (576, 288) code in AWGN channel

1)在误码率为10-5时，多进制LDPC码A优于二进制(576, 288)码约0.5 dB，优于Turbo码约0.3 dB；

2)在误码率为10-6时，多进制LDPC码A优于二进制(576, 288)码约0.7 dB，优于Turbo码约0.4 dB。

3.1.2 多进制LDPC码B

多进制LDPC码B与二进制(1200, 600)码有相同的码长和编码效率，其纠错性能对比分析如图8所示。

1)在误码率为10-5时，多进制LDPC码B优于二进制(1200, 600)码约0.4 dB；

2)在误码率为10-6时，多进制LDPC码B优于二进制(1200, 600)码约0.6 dB。

图8 多进制LDPC码B与二进制(1200, 600)码在AWGN信道下性能对比Fig.8 Performance comparison between 64-ary LDPC code B and binary (1200, 600) code in AWGN channel

3.1.3 多进制LDPC码C

多进制LDPC码C与二进制(528, 264)码有相同的码长和编码效率，其纠错性能对比分析如图9所示。

1)在误码率为10-5时，多进制LDPC码C优于二进制(528, 264)码约0.6 dB；

2)在误码率为10-6时，多进制LDPC码C优于二进制(528, 264)码约0.8 dB。

图9 多进制LDPC码C与二进制(528, 264)码在AWGN信道下性能对比Fig.9 Performance comparison between 64-ary LDPC code C and binary (528, 264) code in AWGN channel

3.2 资源消耗分析

3.2.1 编码器

由于星上资源比较紧缺，而导航应用对编码器的吞吐量要求并不高，因此选择资源占用较低的串行结构二进制LDPC码译码器实现方案进行分析比较。在FPGA下设计并实现的一个(1200,600)、(576,288)、(528,264)三合一的二进制LDPC码编码器占用资源情况如表1所示，逻辑资源的消耗小于1%，Block RAM资源约占7%。

表1 (1200,600)、(576,288)、(528,264)三合一二进制LDPC码编码器硬件资源使用列表Tab.1 Hardware resource requirements list of encode for (1200,600)、(576,288)、(528,264) binary LDPC encoder

多进制LDPC码和二进制LDPC码的编码计算量基本一致，区别在于多进制LDPC码编码器中进行的是多元域加法与乘法运算，单个计算单元较二进制LDPC码复杂一些。但是与此同时由于多进制LDPC码将多个比特的信息视作一个符号，矩阵大小比同等长度的二进制LDPC码小且运算次数比同等长度的二进制LDPC码少，在逻辑资源占用增加的同时存储资源占用减少，吞吐量上升。

采用串行结构的多进制LDPC码编码器基本上可以忽视计算单元带来的影响，编码器整体硬件资源消耗小于现有的二进制LDPC码的编码器硬件资源消耗，能够在现有的硬件系统实现。在相同FPGA下设计并实现的一个64-ary (1200,600)、(576,288)、(528,264)三合一多进制LDPC码的编码器，可以通过一个信号随时切换编码器。多进制LDPC码编码器的硬件资源在指定的FPGA下，逻辑资源的消耗小于1%，Block RAM资源约占5%，其资源使用情况如表2所示。

表2 64-ary (1200,600)、(576,288)、(528,264)三合一多进制LDPC码编码器硬件资源使用列表Tab.2 Hardware resource requirements list of encoder for 64-ary(1200,600)、(576,288)、(528,264) LDPC encoder

3.2.2 译码器

二进制LDPC码译码方案选择了目前最常用的Min-Sum译码算法，在SNR为3.5 dB时误码率达到10-6。该算法是一种逐符号的、软输入输出的译码算法，它迭代处理接收符号，基于奇偶校验和(由接收符号的硬判决和LDPC码的稀疏奇偶校验矩阵H计算得到)提高每个译码符号的可信度。每个译码符号可信度的量度可以采用边沿后验概率对数似然比(Log-Likelihood Ratio，LLR)或者对应的接收符号值。每次译码迭代结束时得到的码符号的可信度度量计算结果将被用作下一次迭代的输入。译码迭代过程持续进行，直到满足停止条件。最后，由码符号的可信度度量的计算结果做出硬判决。

在Xilinx Virtex5的典型型号FPGA下设计并实现的一个(1200,600)、(576,288)、(528,264)三合一二进制LDPC码的译码器，逻辑资源占用19.3%左右，Block RAM资源约占15%，其资源使用情况如表3所示。

表3 (1200,600)、(576,288)、(528,264)三合一二进制LDPC码译码器硬件资源使用列表Tab.3 Hardware resource requirements list of decoder for (1200，600)、(576，288)、(528，264) binary LDPC decoder

多进制LDPC码原始的多进制和积译码算法(Q-ary Sum Product Algorithm,QSPA)性能最好，但是复杂度高，难以实现，目前比较热门的是扩展最小和算法，在SNR为2.7 dB时误码率达到10-6。北斗系统空间信号接口控制文件中给出EMS算法[20]和固定路径译码(Fixed Path Algorithm,FPA)[21]两种参考译码方案。固定路径译码算法可以达到硬件资源消耗略高于二进制LDPC码译码器的情况下，在误码率为10-6时比二进制LDPC码有0.5 dB的性能增益，这意味着地面接收机系统可以在没有性能损失的情况下以更低的功率运行。固定路径译码算法主要改进了多进制LDPC码译码过程中校验节点的计算，通过研究校验节点输入信息向量的分布规律，选取固定的计算路径，可以不经过排序比较也能确保可信度高的符号包含在输出信息向量中，并使输出信息向量大致有序，对迭代计算中变量节点的运算及判决几乎不造成影响。

在Xilinx Virtex5典型型号FPGA下设计并实现的一个64-ary (1200,600)、(576,288)、(528,264)三合一多进制LDPC码译码器，逻辑资源占用20%左右，Block RAM资源约占10%，其资源使用情况如表4所示。

表4 64-ary (1200,600)、(576,288)、(528,264)三合一多进制LDPC码译码器硬件资源使用列表Tab.4 Hardware resource requirements list of decoder for (1200,600)、(576,288)、(528,264) 64-ary LDPC decoder

二进制Min-Sum算法以及多进制QSPA算法、EMS算法和固定路径算法的性能对比和平均迭代次数如图10和图11所示。多进制译码算法平均迭代次数低于二进制译码算法。

图10 二进制和多进制译码算法性能比较Fig.10 Performance comparison of binary and M-ary LDPC decoding algorithms

图11 二进制和多进制译码算法平均迭代次数比较Fig.11 Comparison of the average iterations of binary and M-ary LDPC decoding algorithms

3.3 试验平台测试

为进一步分析比较多进制LDPC码与二进制LDPC码的编译码器的可靠性与纠错能力，按照接口控制文件给出的方案，搭建了以下试验平台，从发射到接收实际测试了编译码的性能。试验平台框图如图12所示。

图12 试验平台框图Fig.12 Block diagram of test platform

本文得到实测环境下的二进制LDPC和多进制LDPC的译码性能曲线如图13所示，与仿真结果一致。

图13 试验平台性能测试曲线Fig.13 Performance test curve based on test platform

4 结论

本文在研究北斗系统空间信号接口控制文件的基础上，对北斗全球系统采用的多进制LDPC编码方案进行了研究和硬件实现，与相同长度的二进制编码方案的编译码性能和资源消耗情况进行了仿真分析和试验平台测试，得到主要结论如下：

1)多进制LDPC性能优于二进制LDPC，有0.4～0.8 dB的额外编码增益，纠错能力更强、错误平台更低、平均迭代次数较少；

2)多进制LDPC编码复杂度与二进制LDPC相当，整体资源消耗小于二进制；

3)多进制LDPC译码复杂度略高于二进制LDPC；

4)存在多种译码算法可实现不同应用场景下硬件资源和译码性能的折中。在高信噪比应用场景下，可以不对导航电文进行译码；在中等信噪比应用场景下，可以采取与二进制LDPC资源消耗相当的译码算法实现相当的译码性能；在低信噪比应用场景下，可以采取资源消耗略高的译码算法实现更高的译码性能。