北斗导航系统中的信道编码研究

蔡建平，树玉泉，何巍巍

(1.北京卫星导航中心，北京 100094； 2.卫星导航系统与装备技术国家重点实验室，河北 石家庄 050081)

北斗导航系统中的信道编码研究

蔡建平1，树玉泉2，何巍巍2

(1.北京卫星导航中心，北京 100094； 2.卫星导航系统与装备技术国家重点实验室，河北 石家庄 050081)

针对卫星导航系统现代化的需求，采用高效的编译码技术有利于提高导航系统的工作性能与可靠性。研究了BCH码、卷积码和低密度奇偶校验码(LDPC)这3种常见的信道编码，对其编译码方案进行了简要介绍，仿真比较了其编码增益，对不同参数配置下编码性能进行了分析与比对。依据仿真结果，综合编译码复杂度、电文设计等需求，提出了适用于北斗RDSS系统现代化发展的信道编码的方案，为北斗系统信号体制设计提供了分析思路和设计参考。

卫星导航；信道编码；LDPC码；卷积码； BCH码

0 引言

北斗导航系统RNSS和RDSS体制的集成应用是我国卫星导航系统的独特优势和核心竞争力，广泛应用于军事和经济社会发展的各个领域。为提高北斗RDSS系统服务性能和用户容量，需要研究新的信号体制，提升用户的易用性，降低用户发射功率。目前用户设备发射信号的功率较大，需采用的功放是10 W左右[1]。为了降低用户设备的发射功率，使用户设备发射信号功率降低到1～2 W，中心站的接收信号的信噪比将大幅度降低，对于RDSS系统中心站接收将是一个巨大的挑战，因此系统采用高增益的编码方案是必要的手段。

在卫星导航系统中BCH码、卷积码和LDPC码是常用的3种编码。BCH码由Hocquenghem于1959年、Bose和Ray-Chaudhuri于1960年分别提出的、纠正多个随机错误的循环码；卷积码由Elias等人于1955年提出的[2]，在编码过程中，使前后的码元之间产生相关性，通过相关性对各码元进行检验。尤其是l967年Viterbi提出了Viterbi译码算法后，卷积码逐渐得到广泛的应用，而后出现的网格编码调制(TCM)技术，使得卷积码可以应用于带宽受限的通信系统中。1962年，Gallage就提出了低密度奇偶校验码(Low Density Parity Check Codes，LDPC)，并提出相应的迭代译码概念[3]。本文将依次对这3种编码方案进行技术分析，对其性能进行仿真并且对比它们之间的性能差异，为北斗RDSS系统新的信号体制设计中的高增益编码方案选取提供参考。

1 BCH码技术分析

BCH码是迄今为止所发现的一类很好的线性纠错码类[4]。它建立在严格的数学基础上，具有很强的纠错能力，特别是在中等码长的情况下，其性能接近理论值，构造方便，编码简单，是目前应用的最为广泛的码类之一。

BCH码是循环码的一个特殊的子集。因此BCH编码的核心问题在于生成多项式的选取，译码的核心问题在于求错误位置多项式。下面针对这两方面进行分析。

1.1 编码特性之生成多项式的选取

在计算生成多项式之前需要确定码长n和纠错能力t。当码长n确定后，BCH码纠错能力t的选择并不是任意的，需要受到一定限制。对于q元BCH码2t个根对应2t个最小多项式，每个最小多项式的次数不应超过m，那么2t个最小多项式的最小公倍式g(x)的次数为deg[g(x)]=n-k≤2tm。对于二元BCH码，t个根对应于t个最小多项式，则它们的最小公倍式g(x)的次数为deg[g(x)]=n-k≤tm。因为xn-1共有n个根，连续幂次根不能超过根的总数，即2t≤n。

设定码长n和纠错能力t后，构造BCH码生成多项式的方法如下：

① 由关系式n=qm-1算出m，查表找到m次本原多项式P(x)，产生一个GF(2m)扩域；

② 在GF(2m)上找一个本原元α，一般情况下，先利用本原多项式P(x)的根，然后分别计算2t个连续幂次根αα2．．．α2t所对应的GF(2m)域中最小多项式m1(x)m2(x)…m2t(x)；

③ 计算这些最小多项式的最小公倍式，得到生成多项式：

g(x)=LCM(m1(x),m2(x),…,m2t(x))。

对于二元BCH码，由于在GF(2)域上，连续2t个幂次根有一半是另一半的共轭元，在求最大公倍式时不起作用，因此上述第②步可简化，只需列出t个连续奇次幂的根即可。

当确定好g(x)后，将信息组c(x)乘以xn-k变成xn-kc(x)，乘以xn-k的目的是将信息位放在码字的最左侧，用以生成系统码。用生成多项式g(x)除以xn-kc(x)，得到商q(x)和余式r(x)，最终编码结果为xn-kc(x)+r(x)。

1.2 译码算法分析

BCH码有BM、无逆BM和Euclid等译码算法。BM算法是由Berlekamp[5]和Masseey[6]提出的。该算法计算较为简单，适合微处理机和软件实现，但是在计算过程中需要求逆，在硬件实现中较为困难。为此Burton提出了无逆BM算法[7]。Euclid算法[8]与BM算法的区别主要在迭代过程。BM是基于自回归滤波器原理来求解最短反馈链接多项式，而Euclid迭代式基于多项式分解原理来求解多项式最大公因式，后者需要进行除法运算，其译码速度要比BM算法慢。ME算法[9]是一种对Euclid算法的改进，避免了求逆运算。无逆BM算法在实际应用中较为常用。

1.3BCH码性能分析

影响BCH码性能的因素主要有：编码效率、纠错个数和编码长度等。下面利用计算机仿真来对比分析上述因素对BCH码性能的影响。

对纠错能力相同但是编码效率不同的BCH码进行了对比，如图1所示。对码长相同但是纠错个数不同的BCH码进行了对比，如图2所示。对码长相同但是编码效率不同的BCH码进行了对比，如图3所示。对码率相近但是码长不同的BCH码进行了对比，如图4所示。

图1 纠错能力为3 bit的BCH码误比特性能对比

图2 码长均为15纠错个数不同的BCH码误比特性能对比

图3 纠错能力不同码率不同的BCH码误比特性能对比

图4 码率相近纠错能力不同的BCH码误比特性能对比

由图1、图2、图3和图4可以得到如下结论：

① 当纠错能力相同的时候，码率越高的BCH码性能越好(图1)；

② 移动信道以突发错误为主，故纠1个或2个错误对信息的传输并没有多少改进(图2)，而纠错个数多的译码器对性能的改善较大(图3)；

③ 当码率相近的时候，纠错能力越强的BCH码性能越好(图4)；

④ 如图3所示，当信噪比低于3.5dB时，(31，11，5)的性能比(31，26，1)要差，在高信噪比时性能逐渐超过。从理论上分析这是因为在低信噪比时信道容量交叉，码率高的编码性能更好，当信道容量提升之后，纠错能力强的码的优势才开始显露出来；

⑤ 当纠错个数增加到一定程度时，由于码的冗余元达到了一定的长度，致使纠错能力停止增长，反而由于码率的降低性能会变差(图3)。

2 卷积码技术分析

卷积码(n,k,N)的编码器是在任一段规定的时间内输入k个码元产生n个码元，它不仅仅取决于这段时间内的N个信息位，还取决于前(N-1)段规定时间内的信息位，参数N即为卷积码的约束长度，移位寄存器的数目m=N-1。

卷积码的译码器一般情况下使用维特比译码并配合软判决。在这个条件下，随着约束长度的提升，卷积码的性能也有一定的提升，但是考虑到接收端在采用维特比软判决译码的时候要求在进行每次迭代时都必须遍历2k(N-1)个状态，并存储2k(N-1)个幸存路径。约束长度N每增加1，接收端的运算复杂度就会增加1倍。因此卷积码的约束长度并不是越长越好，在留有一定系统余量的情况下应该选择适当的约束长度。

在约束条件确定的情况下，影响卷积码性能的因素还有译码时的软判决量化比特数以及译码时的回溯深度。下面从这2个方面对卷积码进行分析。

2.1 译码特性之软判决量化比特的选择

卷积码译码的判决方式分为软判决和硬判决，软判决的性能要比硬判决好1～1.5dB。因此在实际应用中卷积码的译码方式几乎全部使用软判决。在做软判决时模拟信号难以在数字信号系统中处理，为了实现软判决，要采用多bit量化来逼近模拟信号作为译码器的输入。然而量化会带来量化噪声，因此量化比特数会影响最终的性能。

以(2，1，11)卷积码为例，如图5所示。译码时选择的回溯深度均为7N也就是70，采用3、4和5bit量化的软判决性能要远远好于2bit量化。同时4bit量化相对于5bit量化性能几乎没有区别，而都要明显好于3bit量化。软判决需要用A/D转换来实现，随着bit数的增加，A/D转换器的复杂度明显增大。综合考虑，建议在实际应用中选用3bit量化。

图5 不同量化比特下卷积码误比特性能对比

2.2 译码特性之回溯深度的选择

编码后的信息长度很大，接收机不能等到所有的信息都接收完了之后再去译码，而是接收一段译一段。此接收长度即为回溯深度。

不同回溯深度下卷积码误比特性能对比如图6所示，仍然以(2，1，11)卷积码为例，当回溯深度为50～100的时候性能变化并不大，但是都要明显好于回溯深度为30的时候。一般选择回溯深度为5N～10N，N为编码器寄存器数。

图6 不同回溯深度下卷积码误比特性能对比

采用硬件实现维特比译码时必须要考虑储存器容量的问题。假设回溯深度为L，每一级由2k(N-1)个状态，每个状态由kbit的分支取值，那么总的储存量为L×k×2k(N-1)bit，相应的路长和路径值在最小距离译码下每个分支最多要求log(n)bit。所以最终需要的存储容量为L×(k+log(n))×2k(N-1)。所以深度越大性能越好，但是延时越大，并且接收端需要的储存器容量也越大。最终综合考虑性能和实现难度，卷积码译码时的回溯深度应选择为5N左右比较合适。

3 LDPC码技术分析

LDPC码是一种码长非常大的线性分组码，码长一般是成百上千，甚至更长。其校验矩阵也很大，并且具有一个重要特征是矩阵中的非零元素非常少，即为稀疏矩阵，也就是非零元素的个数占总元素个数的比率非常小，故称之为低密度奇偶校验码。

LDPC码具有以下优点：具有非常接近香农理论界限的性能；能够实现快速编码；在不同信道上都表现出良好的性能；不需要深度交织就能获得好的误码性能，所以系统的时延比Turbo码短；错误平层大大降低。

影响LDPC编码性能的因素有以下2种：校验矩阵的构造以及译码方式的选取。

3.1 编码特性之校验矩阵的选择

因为LDPC码是基于稀疏校验矩阵的线性分组码，并且在实际应用中普遍使用校验矩阵H直接进行编码。因此构造LDPC码实际上就是构造校验矩阵H。H的结构决定了LDPC码的性能。构造H的方法大致可以分为2类：随机构造法和结构化构造法。

在实际应用中，出于对编码复杂度以及译码速度等方面的考虑，一般都采用结构化构造校验矩阵H。为了便于在实际应用中储存和编码，普遍的做法是选用准循环LDPC码(QC_LDPC)以及双对角结构。在这方面最具有代表性的是802.16E标准中的LDPC码。符合802.16E标准的LDPC码在硬件实现上较为容易。802.16E标准的LDPC码码长均为24的倍数，通过改变循环矩阵的维度来改变码长。该标准在实际中有广泛的应用。

准循环校验矩阵H的设计思路在于首先设计出基校验矩阵Hb，然后将基校验矩阵Hb的每个元素替换为L阶单位矩阵的循环右移矩阵。

以802.16E中规定的(2304，1152)LDPC码为例，其校验矩阵表达式为：

式中，子矩阵Hb1的维数为12×12；子矩阵Hb2的维数为12×1；子矩阵Hb3的维数为12×11。循环矩阵的阶数L=96。Hb中的每个元素代表循环右移的次数，其中-1代表全0矩阵，0代表单位矩阵。

矩阵Hb1通过相应的算法得到，而Hb3和Hb2具有固定的结构。

矩阵Hb3的结构如下式所示，为双条对角矩阵，每个非零子矩阵均为单位矩阵。

矩阵Hb2的表达式为

802.16E标准中对不同长度的LDPC码做了比较，对于LDPC码，编码长度越长，性能越好。LDPC码的优异性能如图7所示。

当码长超过2 000时，满足误比特率低于10-5仅仅需要不到2 dB。图中还体现出来在编码长度相近的情况下LDPC码的误比特性能是相近的。在实际应用中选取LDPC编码长度时，其性能可以参考802.16E标准中码长相近的LDPC码的性能。

图7 不同长度LDPC码性能比较

当LDPC码对应的Tanner图中存在短环时，某一节点发出的信息经过一个环长的传递会被传回本身，从而造成自身信息的叠加，破坏了独立性的假设，会影响迭代译码的效果。另外，在高信噪比的情况下，环的存在使变量节点和校验节点之间传递的信息在经过较少的迭代次数即产生相关性，从而准确性下降形成“错误平层”。因此，消除短环是LDPC校验矩阵设计中优先考虑的问题。由Tanner图的结构可以知道，环长最小为4。Mackay等指出消除长度为4的环对码的性能有很大提高，继续消除其他长度的短环对提高码的性能的效果越来越不明显。不包含4环是LDPC校验矩阵的基本要求。

3.2 译码方式的选择

按照普通线性分组码的译码方式，译码的基本思路是先求伴随式，再根据伴随式求可纠正的错误图样。假如码长n=1 000，信息长度k=500，不同的伴随式的个数将有2n-k=2500之多，以现有的技术是不能够实现的。因此LDPC码的译码是基于Tanner图的迭代译码：

① 首先变量节点接收到来自信道的初始概率信息，并将这些信息传送给与其相连的校验节点；

② 校验节点接收到来自与其相连的不同变量节点的信息并进行处理，再将处理后的信息传送给与其相连的变量节点；

③ 变量节点对校验节点传送来的信息处理并进行硬判决。判断是否达到最大迭代次数或者与校验矩阵正交，二者满足其一则停止迭代，输出判决结果，否则重复执行步骤②和步骤③。

迭代算法主要有置信传播译码(BP)[10]、对数似然比BP译码算法(Log-BP)[11]、最小和译码算法(Min-Sum)[12]以及归一化最小和译码算法(NormalizedBP-based)[13]等。普通的BP译码算法需要大量的乘法运算，运算复杂度较高；对数似然比译码算法把大量的乘法运算变为加法运算，减少了运算时间[14]，由于需要对数运算，实现复杂度仍然很大；最小和译码算法是将对数似然比算法中的复杂的对数运算简化成了比较运算，大大降低了译码复杂度，但性能有一定的损失；归一化最小和译码算法在最小和译码算法的基础上增加了一些乘法运算，使其性能有了明显的提升[15]。

不同译码方式性能比较如图8所示，最小和算法虽然运算量小，但是相较于对数似然比算法性能有较大的差距，归一化最小和的性能比最小和算法有了大约0.5dB的提升，与对数似然比算法的性能非常接近。综上所述归一化最小和算法是比较理想的译码算法，在误比特性能，复杂度上都比较合适。

图8 不同译码方式性能比较

4 信道编码性能对比

不同的信道编码有各自的特点和适用场景，LDPC码的性能要优于BCH码和卷积码，但是其编译码复杂度也会高很多。因此选择一种合适的信道编码是非常重要的。

(2，1，N)卷积码在维特比软判决译码下的性能如图9所示。在不同码长下，码率为1/2下的LDPC编码的性能如图10所示。

图9 不同约束长度的卷积码性能比较

图10 不同长度的LDPC码的性能比较

对比图9和图10可知，在误比特率pe≤10-5的条件下，若采用(2，1，11)的卷积码，其解调Eb/N0门限约为3.5dB。若采用LDPC编码，在信息长度小于192bit时，其解调Eb/N0门限高于3.5dB，在信息长度为192bit左右时，其解调Eb/N0门限约为3.5dB。当信息长度达到504bit左右时，其解调Eb/N0门限可降低至2.25dB以下。

BCH码和LDPC码的性能比较如图11所示。可以看出，BCH码的误比特性能较低，但与其他2种编码方式相比，BCH编码的编译码算法都相对简单，更加容易实现。适用于对误比特性能要求不高，需要硬件设备简单的情况。

图11 BCH码和LDPC码的性能比较

在考虑RDSS系统新体制中，当用户机的发射信号功率为1W(0dBW)时，预估入站接收系统的处理信号的载噪比为35dB-Hz左右。当选择信息速率Rb=1 kbps时，对应的Eb/N0计算如下：

显然，此时选择(2，1，11)卷积编码便可满足系统误码率需求。但是，当信息长度较大时，选择LDPC编码能获得更大的编码增益。

综合考虑纠错性能、编译码复杂度、系统实现成本等因素，建议的编码方案为：当信息长度小于192 bit时，采用(2，1，11)卷积码，当信息长度大于等于192 bit时，采用LDPC编码。

5 结束语

本文从北斗导航RDSS系统提高信号编解码处理增益的需要出发，分别介绍了BCH码、卷积码和LDPC码等3种常见的信道编码方案，仿真比较了各编码方案的解码性能。仿真结果表明，对于北斗RDSS现代化系统而言，根据电文长度采用自适应卷积码和LDPC的编码方案，在电文长度较短时采用卷积码，电文长度较长时采用LDPC编码，在提高纠错能力、增强信号接收的载噪比，优化抗干扰能力的同时，能够有效减小编码器复杂度，降低硬件复杂度，是切实可行的卫星导航系统信道编解码方案。

[1] 郑晶茹，郑 萍，冯林刚.北斗卫星导航系统及其应用[J].西部资源，2012(6)：155-157．

[2] 周炯磐，庞沁华，续大我，等.通信原理(第3版)[M].北京：北京邮电大学出版社，2008.

[3] GALLAGER R G.Low-Density Parity-Check Codes[J].IRE Trans.Inform.Theory,1962,8(1):21-28.

[4] WILSON S G.Digital Modulation and Coding[M].Beijing:Publishing House of Electronic Industy,1998.

[5] BERLEKAM E R.Algebraic Coding Theory[J].Trans.Comput,1968(34):393-403.

[6] MASSEY J L.Shift-register Synthesis and BCH Decoding[J].IEEE Trans,1969(15):122-127.

[7] BURTON H O.Inversionless Decoding of Binary BCH Codes[J].IEEE Trans,1971,17(4):464-466.

[8] SUGIYAMA Y,KASAHARA Y,HIRASAWAS M.A Method for Solving Key Equation for Decoding Goppa Codes[J].Inf & Control,1975(27):87-99.

[9] SHAO H M,DEUTSEH L J,YUENANDI J H,et al.A VLSI Design of a Pipeline Reed-Solomon Decoder[J].IEEE Trans,1985(34):393-403.

[10] FORNEY J G D.The Forward-backward Algorithm[C]∥ Proc.34th Allerton Conf.Communication,Control and Computing,1996:432-445.

[11] 张亚林，蔚保国，范广伟.IEEE802.16e标准下LDPC码译码性能分析[J].无线电工程，2013，43(11)：8-10.

[12] CHEN Jin-hu,MARC P C.Density Evolution for Two Improved BP-based Decoding Algorithms of LDPC Codes[J].IEEE Communications Letters,2002,6(5):256-259.

[13] BRACK T,ALLES M,LEHNIGK-Emden.Low Complexity LDPC Code Decoders for Next Generation Standards Design[C]∥Automation & Test in Europe Conference & Exhibition,2007:1-6.

[14] TANNER R M.A Recursive Approach to Low Complexity Codes[J].IEEE Transactions on Information Theory,1981,27(5):533-547.

[15] 雷 婷,张建志.LDPC编译码算法分析[J].无线电工程，2012，42(10)：8-9.

蔡建平 男，(1964—)，硕士，高级工程师。主要研究方向：卫星导航。

何巍巍 女，(1979—)，硕士，高级工程师。主要研究方向：卫星导航。

Research on Channel Coding in Beidou Navigation System

CAI Jian-ping1,SHU Yu-quan2,HE Wei-wei2

(1.BeijingSatelliteNavigationCenter,Beijing100094,China; 2.StateKeyLaboratoryofSatelliteNavigationSystemandEquipmentTechnology,ShijiazhuangHebei050081,China)

In view of the demand of satellite navigation system modernization,the application of high-efficiency codec technology is favourable to improve the operation performance and reliability of navigation system.This paper studies such three common channel coding methods as BCH code,convolutional code and LDPC code.The codec scheme of these three methods is introduced briefly,the coding gain is simulated and the coding performance in different parameter configuration is analyzed and compared.Based on simulation results and combined with codec complexity and message design,this paper proposes a channel coding scheme suitable for Beidou RDSS system modernization and provides analysis idea and design reference for Beidou system signal system design.

satellite navigation;channel coding;LDPC code;convolutional code;BCH code

10.3969/j.issn.1003-3106.2017.05.12

蔡建平,树玉泉,何巍巍.北斗导航系统中的信道编码研究[J].无线电工程,2017,47(5):47-53.[CAI Jianping,SHU Yuquan,HE Weiwei.Research on Channel Coding in Beidou Navigation System[J].Radio Engineering,2017,47(5):47-53.]

2017-01-10

地理信息工程国家重点实验室开放基金资助项目(SKLGIE2014-M-2-4)。

TN911

A

1003-3106(2017)05-0047-07