目前，北斗卫星导航系统可向中国及其周边区域提供全天候的定位、导航及授时服务，北斗卫星导航接收机的设计与开发也引起了学术界和工业界的广泛兴趣^[1-2]。对于卫星导航接收机而言，导航电文至关重要，其含有的卫星基本导航信息、历书信息以及与其他系统时间同步信息的准确性直接决定了接收机的定位精度。为了增强导航电文的准确性，北斗系统采用了一组循环BCH码作为导航电文的前向纠错码^[3]。因此，设计该BCH码的高效译码方案具有非常重要的意义。当前北斗系统中的BCH译码算法主要分为两类：硬判决译码算法^[4-5]和软判决译码算法^[6-8]。硬判决译码算法具有简单、易于实现的优点，也是北斗系统接口控制文件中推荐的译码算法，但是其译码性能相对较差。针对这一问题，多种软判决译码算法被设计出来。同硬判决译码算法相比，这些算法的性能得到了改善，但由于复杂度的增加，在实现过程中往往会遇到许多困难。

除了这两类算法，擦除译码也是线性分组码(尤其是循环码)的一种重要译码算法^[9-13]。可以验证，北斗系统中的BCH码最小汉明距离为3。由线性分组码的性质可知，擦除译码可以纠正包含有不超过2个擦除位置且其余位置没有错误的任意接收矢量^[14]。基于上述性质，本文提出了一种北斗系统BCH码的高效译码算法。该算法将接收矢量每个位置的可靠性同硬判决矢量相结合，通过用擦除位替换掉硬判决矢量中的两个位置，构造出一组矢量。此后，对每个构造出来的矢量分别采用擦除译码算法进行译码，并根据一定准则选择译码结果中的一个码字作为译码输出。此外，为了提高算法的效率，提出了一种可以减少译码矢量数目的机制。

1 北斗系统BCH码

北斗系统中的前向纠错码采用循环BCH码，码长和信息长度分别为15和11，记为BCH(15, 11) 码^[4]，其生成多项式为

$ g\left( x \right) = {x^4} + x + 1 $

(1)

由于该码是循环码，其编码可以通过线性移位寄存器电路有效实现^[15-16]。具体编码步骤如下：

1) 将待编码的信息多项式m(x)乘以x^r，其中r=deg(g(x))=4。

2) 用x^rm(x)除以生成多项式g(x)，得到余式b(x)。

3) 构造码字c(x)=b(x)+x^rm(x)。

BCH(15, 11) 码的最小汉明距离为3，采用硬判决算法可以纠正出现在接收矢量中任意位置的单个错误。硬判决译码算法可以通过基于校正子的查找表实现，主要包括如下步骤^[4]：

1) 将接收矢量v除以生成多项式g, 得到余式r，余式即该接收矢量对应的校正子。

2) 根据校正子r查表得到相对应的错误图样e。

3) 输出译码码字$\mathit{\boldsymbol{\hat c}} = \mathit{\boldsymbol{v}} + \mathit{\boldsymbol{e}}$。

可以验证，BCH(15, 11) 码是完备码(perfect code)^[14]。也就是说，对于长度为15的任意硬判决接收矢量v，在BCH(15, 11) 码中存在唯一的一个码字c，使得v和c之间的汉明距离不超过1。这时，用硬判决译码算法对接收矢量v进行译码得到的结果即是码字c。这种译码方式的一个缺点是当接收矢量错误数大于1时会出现译码失败。

为了解释上述现象，考虑下面的例子。假定通过信道发送码字[1 1 1 0 0 0 1 0 0 1 0 1 0 0 0]，在接收端的硬判决矢量为[1 1 1 0 1 0 1 1 0 1 0 1 0 0 0]。可以看出，接收矢量在第5和第8两个位置上出现了错误。这时通过硬判决译码算法得到的码字为[1 1 1 0 1 0 1 1 1 1 0 1 0 0 0]。同发送码字相比，译码结果出现了3个错误，比接收矢量还多出一个错误。因此，硬判决译码算法仅在信道噪声相对较低时有效，其编码增益也相对有限。

2 基于可靠性的擦除译码算法

本节提出BCH(15, 11) 码的一种基于可靠性的擦除译码算法，并设计了一种能提高译码算法效率的机制。

2.1 BCH(15, 11) 码错误概率分析

由第1节可知，任意包含有超过1个错误的接收矢量无法通过硬判决译码算法正确纠错。下面分析接收矢量中出现不同错误个数的概率。假定一个BCH(15, 11) 码字经过二进制相移键控(BPSK)调制后通过加性高斯白噪声(AWGN)信道传输。由文献[17]可知每个位置的错误概率为

$ P = Q(\sqrt {2R{E_B}/{n_0}} ) $

(2)

其中

$ Q\left( x \right) = \frac{1}{{\sqrt {2\pi } }}\int_x^\infty {{\rm{exp}}\left( { - \frac{{{y^2}}}{2}} \right){\rm{d}}y} $

(3)

式中：R=11/15为码率，E_b/N₀为信噪比(SNR)。

由概率论可知^[17]：

$ P\left( {E = i} \right) = C_{15}^i{p^i}{\left( {1 - p} \right)^{15 - i}},i = 0,1, \ldots ,15 $

(4)

式中：E表示硬判决矢量中出现错误的个数。表 1列出了在不同信噪比下，硬判决矢量中错误个数分别为0、1、2和大于2四种情况的概率。由表 1可以看出错误数大于1的情况是不能忽略的，且错误数为2的概率要远高于错误数大于2的概率。因此，如果在设计译码算法时考虑到这一情形，则可以改善纠错性能。

2.2 算法设计

对于最小汉明距离为d_min的BCH码，擦除译码算法可以纠正含有e个擦除位置且其余位置没有错误的所有组合，需要满足如下关系^[14]：

$ e + 1 \le {d_{{\rm{min}}}} $

(5)

由于BCH(15, 11) 码的最小汉明距离为3，擦除译码算法可以纠正包含有2个擦除位置且其余位置没有错误的接收矢量。这说明任意包含有两个错误的硬判决矢量在准确得到其错误位置的情况下，可以通过擦除译码算法得到纠正。文献[14]中给出了擦除译码算法的主要步骤:1) 通过在一个矢量的两个位置上用擦除位替换掉原先的值构造一个新的矢量；2) 分别设置擦除位的值为00和11后各自采用硬判决译码算法进行两次译码，得到两个码字；3) 统计这两个码字在非擦除位置上的值与之前构造出的矢量对应位置上的值相同的个数，选取相同个数多的码字作为译码结果输出。

在实际中，由于错误位置无法提前获得，从而限制了上述译码方法的应用。但是，北斗系统可以提供不同位置的可靠性信息，该信息由导航接收机中的跟踪通道实时获得。接收机完成某颗卫星的捕获后，转入跟踪状态，相应卫星的跟踪通道经过解旋、解扩、积分累加等数字信号处理算法后得到当前卫星信号上调制的数据比特观测值。这一观测值通常不是仅有两个电平0或1的硬判决量，而是可量化为具有一定位宽的多个电平值。对每个数据比特，其观测值取符号位即得到硬判决结果，而每个观测值的绝对值大小则反映了该判决的可靠性。观测值越大，表明该比特的判决结果越可靠；反之，表明判决结果越不可靠。因此，可以将可靠性信息与擦除译码相结合，设计出一种高效的译码算法。

该算法首先选择接收矢量中的L(L≥2) 个不可靠位置。然后，每次选取这L个位置中的任意两个位置当作擦除位置来构造一个新的矢量。最后，对每个构造出的矢量采用上述的擦除译码算法进行译码。不难看出，构造的矢量和需要译码的矢量数目分别为N和2N，其中

$ N = C_L^2 = L\left( {L - 1} \right)/2 $

(6)

为便于实现，假定N个位置按照其可靠性进行字典排序^[18]。

记某个译码矢量为v_k^(l)，其中l=0表明擦除位被设置为00，l=1表明擦除位被设置为11，k=1, 2, …, N。这2N个译码矢量依次为v₁⁽⁰⁾、v₁⁽¹⁾、v₂⁽⁰⁾、v₂⁽¹⁾、…、v_N⁽⁰⁾、v_N⁽¹⁾，进行硬判决译码后得到2N个码字，分别为c₁⁽⁰⁾、c₁⁽¹⁾、c₂⁽⁰⁾、c₂⁽¹⁾、…、c_N⁽⁰⁾、c_N⁽¹⁾。记符号A(c_k^(l), v_k^(l))表示在非擦除位置上c_k^(l)与v_k^(l)值相同的个数，其中k=1, 2, …, N，l=0, 1。算法选取A(c_k^(l), v_k^(l))具有最大值的c_k^(l)作为输出码字。

可以看出，译码矢量的总数2N与L的呈平方关系增加，为了减少译码矢量的个数，本文进一步设计了一种终止机制(termination mechanism, TM)。在擦除译码过程中，若错误位置正好与擦除位置一致时，那么在非擦除位置的译码结果与接收矢量应是完全相同的^[14]。

假定对所有2N个构造出的矢量进行顺序译码。对某一个构造出的矢量v_k^(l)，如果译码得到的码字c_k^(l)与v_k^(l)在所有13个非擦除位置上的值完全一致，即A(c_k^(l), v_k^(l))=13，这时认为译码输出码字为c_k^(l)，同时终止译码过程。这种终止机制的有效性将在下一节中通过仿真进行验证。

综上所述，基于可靠性的北斗系统BCH(15, 11) 码的擦除译码步骤描述如下：

输入：硬判决矢量v；每个位置的可靠性信息R；参数L。

输出：译码码字${\mathit{\boldsymbol{\hat c}}}$。

1) 根据硬判决矢量v中每个位置的可靠性信息R选择L个不可靠位置。

2) 构造一组矢量v_k^(l)(k=1, 2, …, N; l=0, 1)。

3) 对这些构造出来的矢量顺序地进行硬判决译码，得到译码码字c_k^(l)。

4) 若某一个译码的码字c_k^(l)满足A(c_k^(l), v_k^(l))=13，则令${\mathit{\boldsymbol{\hat c}}}$= c_k^(l)，同时终止译码过程。

5) 选择A(c_k^(l), v_k^(l))具有最大值的c_k^(l)，令${\mathit{\boldsymbol{\hat c}}}$= c_k^(l)。

2.3 复杂度分析

基于可靠性的北斗系统BCH(15，11) 码的擦除译码算法的复杂度主要集中在步骤1) 到步骤3)。在步骤1) 中，找到L个不可靠位置需要进行15L次比较。在步骤3) 中，复杂度正比于译码矢量的平均数目。通常情况下译码矢量数目为L(L-1)，但应用设计的终止机制后，能有效减少译码矢量的数目。在下一节可以看到，在合适的信噪比范围内，采用终止机制后的平均译码矢量的数目很少。例如，当L=4时，算法中的译码矢量数目不会超过2个，同传统的硬判决译码算法相比较，本文提出的算法仅多增加60次比较操作和1次硬判决译码操作，因此该算法具有低复杂度的优点。

3 仿真结果及分析

通过仿真确定参数L的取值，并评估设计的终止机制。仿真中每个位置上的可靠性信息采取6 bit均匀量化^[17]。为了进行比较，本文同时仿真了北斗系统接口控制文件中推荐的硬判决译码算法和文献[8]中的最大似然软判决译码算法的译码性能。

图 1给出了参数L取不同值时，提出的基于可靠性的擦除译码算法的性能。从图 1中可以看出，提出的译码算法的性能随着L取值的增加而获得改善。特别地，当L=4时算法的性能相对于L=2和L=3时的性能有较大改善，而当L=5时算法的性能相对于L=4时的性能改善相对较小。因此，在实际中建议参数L取值为4。

图 2对比了BCH(15, 11) 码采用不同译码算法的性能。

可以看出，本文提出的算法译码性能明显优于传统的硬判决译码算法。例如，对任意的译码算法，总会存在一个编码阈值，当低于这个阈值时，编码无效。对于实际系统，应当设计译码算法，使得编码阈值尽量地低^[18-19]。由图 2中可以看出，本文提出的算法相对于传统硬判决译码算法的编码阈值性能得到了改善。如传统的硬判决译码算法的编码阈值约为4 dB，而当选取L=4时本文提出的算法的编码阈值约为2.2 dB。

为了提供首次定位服务，要求导航电文的误比特率必须小于10^-3[20]。从图 2中可以看出，在满足误比特率小于10^-3条件下，当选取L=4时，提出的算法同传统的硬判决译码算法和未编码BPSK相比，性能分别提升0.8 dB和1.8 dB左右。

另外，本文提出的算法在性能上接近最大似然软判决译码算法(即在BCH(15, 11) 码中选择码字c，使得内积$\left\langle {r, c} \right\rangle $的值最大，其中r为接收软判决向量)。从图 2中可以看出，当L=4时，误比特率为10^-3，本文的算法同最大似然软判决算法之间性能差距小于0.5 dB。但是，最大似然软判决译码算法非常复杂。由于BCH(15, 11) 码包含2 048个码字，因此若采用直接实现，需要约2 048×(15-1)=28 672次加法操作和2 047次比较操作。文献[8]中的给出了BCH(15, 11) 码最大似然软判决译码的一种有效实现方案。若采用该方案，也至少需要额外的240次加法操作和135次比较操作。与此相比，本文提出的译码算法基于硬判决译码实现，仅需要增加少量的逻辑运算。

图 3对比了采用终止机制和不采用终止机制时提出的译码算法的性能。从图中可以看出，采用了终止机制后，算法的性能几乎没有任何损失。表 2给出了在不同信噪比下的译码矢量的平均数目。可以看出，提出的算法的译码矢量的平均数目不多，并且随着信噪比的提高，译码矢量的平均数目减少。这说明了采用终止机制后算法的平均复杂度会很低，从而验证了终止机制的有效性。

综上所述，本文提出的基于可靠性的擦除译码算法是实际导航接收机的良好选择。

4 结论

1) 基于可靠性的高效擦除译码算法在增加少量复杂度的基础上能明显改善译码性能，避免了传统硬判决译码算法性能相对较差以及软判决译码算法复杂度高的缺点。

2) 对算法的参数L进行了仿真，结果表明L取4时能最大程度平衡性能提升与复杂度增加之间的矛盾，是一个合理的选择。

3) 本文提出的译码算法在性能上同传统的硬判决译码算法和未编码BPSK相比有明显提升，同最大似然软判决译码算法相比性能接近。

4) 提出了一种译码算法终止机制，使得在算法性能几乎没有任何损失的条件下有效减少译码矢量数目。

5) 复杂度分析表明，本文提出的算法操作简单，易于通过软硬件加以实现，非常适合在北斗系统导航接收机(特别是低成本接收机)中应用。