卫星导航电文的编码纠错法── GNSS导航信号的收发问题之六

2014-05-07刘基余

数字通信世界 2014年6期

刘基余

（武汉大学测绘学院，武汉 430079）

为了正确传送卫星导航电文，在编排导航电文时，不仅编排数据位，而且需要给出一定的纠错码元，致使GNSS导航信号接收机能够完整地解译出卫星所发送的导航电文，而不会发生错漏。本文以GPS卫星导航电文为例，论述GNSS卫星导航电文编码纠错编码的现况与发展。

1 分组加元纠错法的不足

从1978年2月的第一颗Block I卫星开始，直至Block II，IIA，IIR卫星，它们的第一、二GPS导航定位信号（L1，L2）的导航电文，都是采用了“奇偶检验法”实施编码纠错；我们称之为“分组加元纠错法”。它以字码为单位，即每个字码的前面24bits为电文码元（数据位），随后6bits为纠错码元（奇偶校验位）。该法的1个字码示例如表1所示；它们依下述列发顺序传送给用户：101011111000100011011110101110。分组加元纠错法，能够有效地发现和纠正长度不大于列元个数的突发错误，而达到正确传送卫星导航电文的目的。

表1 分组加元纠错法示例

从上可见，第一、二GPS导航定位信号（L1，L2）采用的“分组加元纠错法”，编码时，需要每24bits就加上6bits纠错码；解码时，在取得信息之前，需要先将6bits纠错码从中剥去。这种“纠错码剥离法”，致使某些原本连续的信息变得不连续了；例如，卫星轨道长半轴的平方根为32bits，分别位于第2子帧第8字码的第3字节和第9字码的前三个字节，而导致了的不连续性。如果从中除去奇偶校验码，则的编码表述才是连续的，编码和解码都将变得简单方便，但不符合分组加元纠错的编码规律，不能够应用。而且，这种24+6bits（24bits电文码元+6bits奇偶校验）的字码结构，浪费了大量的存储空间，冗余信息的比例达到20%之多！为了解决这个问题，GPS第三导航定位信号（L5）的导航电文采用了“循环冗余纠错法”（CRC，Cyclic Redundancy Check），CRC是目前在计算机网络通信及存储器中应用最广泛的一种差错控制技术。它所约定的纠错规则是：让纠错码能为某一约定电文代码所除尽；如果除得尽，表明电文代码正确；如果除不尽，余数将指明出错位所在位置。

2 CRC纠错编码原理

CRC纠错是一种采用多项式的编码方法，它将一个以二进制数字表示的数据系列看成一个多项式，例如，二进制数字序列10101111，它可用下列多项式予以表示：

式中，xi表示代码的位置，或某个二进制数位的位置；xi前面的系数ai表示码的值，若ai是一位二进制代码，则取值是0或1；M(x)称为信息代码多项式。多项式乘除法运算过程与普通代数多项式的乘除法相同；多项式的加减法运算以2为模，加减时不进位或借位，和逻辑异或运算一致。

采用CRC纠错时，发送方和接收方用同一个生成多项式G(x)，并且G(x)的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以生成多项式G(x)去除待发送数据的k阶多项式M(x)，得到n-k(n-k

如果一个k位的二进制信息代码序列多项式M(x)，当采用CRC纠错编码时，就要增加（n-k）位的CRC纠错码，它们跟随在信息代码之后，而信息代码在新序列中就表示成为xn-kM(x)，如图1所示。

图1 采用CRC纠错的信息编码

如果用一个CRC纠错码生成多项式G(x)去除代码多项式xn-kM(x)，所得到的商数若为Q(x)，而其余数为R(x)，则知

故有

考虑到模二和多项式的加法和减法的运算结果相同，由式（3）则知，带CRC纠错码的发送信息多项式可写成

由式（4）可知，表述经过编码后的信息代码多项式{xn-kM(x)+R(x)}，是能够被生成多项式G(x)除尽的，也即，它的余数为0。接收方在解码该发送信息时，以余数是否为0，判定该发送信息是否在传送过程中出错；若为0，则表明信息传送无误；否则，表明信息传送有误。研究表明，CRC纠错能够保证在bits码元中只含有一个码元未被检测出的错误。（详见罗伟雄，韩力，原东昌，丁志杰.通信原理与电路.北京：北京理工大学出版社，1999）

3 CRC纠错编码方法

CRC纠错码的编码方法是用待发送的二进制数据M(x)除以生成多项式G(x)，最后的余数作为CRC纠错码（如表2所示）。其实现步骤如下：

（1）设待发送的数据块是k位的二进制多项式M(x)，生成多项式为（n-k）阶的G(x)，在数据块的末尾添加（n-k）个0，数据块的长度增加到n位，对应的二进制多项式为xn-kM(x)。

（2）用生成多项式G(x)去除xn-kM(x)，求得余数阶数为（n-k-1）的二进制多项式R(x)，此二进制多项式R(x)就是M(x)经过生成多项式G(x)编码的CRC纠错码。

（3）用xn-kM(x)以模2和的方式减去R(x)，得到二进制多项式xn-kM'(x)。这个xn-kM'(x)就是包含了CRC纠错码的待发送字符串。

从上述CRC纠错编码规则可见，CRC编码实际上是将待发送的k位二进制多项式M(x)转换成了可以被G(x)除尽的n位二进制多项式xn-kM(x)；因此，解码时，可以用接收到的数据去除G(x)，如果余数为0，就表示数据在传输过程中没有发生错误；若余数不为0，则表示数据在传输过程中肯定发生了错误。

表2 用CRC纠错的导航电文仿真编码

一般情况下，n-k位生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于n-k的突发错误以及（1-2-（n-k-1））的突发长度为n-k+1的突发错误和（1-2-n+k）的突发长度大于n-k+1的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。例如，采用24位CRC纠错码，就能检测出所有突发长度小于等于24的突发错误以及99.999988%的突发长度为25的突发错误和99.999994%的突发长度大于25的突发错误。由此可见，CRC的纠错能力是很强的。这里的突发错误是指几乎连续发生的一串错误，突发长度就是指从出错的第一位到出错的最后一位的长度（但是，中间并不一定每一位都是错误）。

由于CRC纠错的可靠性，CRC纠错编码广泛用于传输重要数据，而在通信、计算机等领域中得到十分广泛的应用。在一些UART通信控制芯片（如MC6582，Intel8273，Z80-SIO）内，都采用了CRC纠错码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC差错控制技术。

对于xn-kM'(x)，可以视为由M(x)和CRC纠错码组合而成，解码时，将接收到的二进制数据去掉尾部的n-k位数据，即为原始数据。

4 CRC纠错编码在L5导航电文中应用

GPS系统现代化后，GPS卫星将增设第三导航定位信号（L5）。该信号的导航电文，将废弃L1/L2导航电文所用采用的分组加元纠错法，而采用CRC差错控制技术。L5导航电文保持了现有导航电文的子帧结构：每个子帧各有10个字码，每个字码30bits；也即，每个子帧共300bits，占用时间为6s，这样，便与L1/L2导航电文的子帧时间保持一致。但是，L5导航电文每个子帧的最后24bits为CRC纠错码，以致冗余信息的比例仅占8%，相对于L1/L2导航电文结构而言，既节省了纠错码元，又提高了纠错能力。L5导航电文结构，与GPS外部增强系统（如WAAS）所采用的电文结构极其相似。L5导航电文，按下列方法实施CRC编码纠错：

① 将一个长度为24bits的寄存器内容清零；

② 在276位数据bits后添加24个0bit组成新的300位数据bits；

③ 将寄存器的值左移一位，并将下一个数据bits读入寄存器的最低位（bit0的位置）；

④ 如果第三步从寄存器移出的值为1，则将寄存器的值与生成多项式（最高位不参与运算）做异或运算，以运算结果更新寄存器内容；

⑤ 如果300位数据bits没有全部读完，则重复第三和第四步，否则转到第六步；

⑥ 寄存器的内容便是我们所要的CRC纠错码。

依上述方法，GPS卫星播发的L5导航电文，它的各个子帧是由276个数据bits及其随后附加24bits CRC纠错码构成的。当接收机接收到L5导航电文时，先按帧提出电文，然后对300bits的电文子帧进行CRC纠错；也即，将接收到的300bits的电文替代上述算法第二步中的300位数据bits，按照算法进行校验。如果第六步寄存器最终得到的值为零，则说明传输无误，可以进行下一步的解码；否则说明传输有错，则将这帧电文舍弃。

5 L5导航电文

L5导航电文，设计了64种电文类型，其中第0号电文为默认电文，当卫星生成导航电文时出现错误，卫星就用默认电文代替错误电文的内容。第6～63号电文保留未定义。目前，只定义了第1～5号电文，也即，目前只使用了下述5种电文：

⊙ 第1帧电文（Message Type 1）：包含用户测距可达精度、健康状况、钟差参数以及卫星星历）；

⊙ 第2帧电文（Message Type 2）：卫星星历；

⊙ 第3帧电文（Message Type 3）：电离层和UTC时间的参数；

⊙ 第4帧电文（Message Type 4）：卫星历书数据；

⊙ 第5帧电文（Message Type 5）：专用电文。

为了与L1/L2导航电文的名称相对应，我们仍称为之第1，2，3，4，5“子帧”。第1，2子帧电文是L1/L2导航电文中第1，2，3子帧信息的浓缩。对于民用而言，L1/L2导航电文中的备用信息（Reserved Data）不是必需的，故L5电文中不包含这些信息。同时原来每个字码的6bits奇偶校验，也更换成为一个子帧的只用24bits CRC纠错码。这样，L1/L2导航电文中第1，2，3子帧中的所有有用信息，加上L5的一些特有信息，就组合成了两个6s的L5子帧电文。

图2 GPS L5采用循环冗余纠错码编制的星历电文

L1/L2导航电文的第4，5子帧的众多页面中也包含了大量的备用信息，而民用用户只需要使用其中的电离层参数、UTC时间参数、卫星历书数据以及专用电文。这样，L1/L2导航电文的第4，5子帧50个页面的信息，就被浓缩在第3，4，5子帧电文中。

L5导航电文的每个子帧电文也像L1/L2子帧一样，以8bits同步码（1 0 0 0 1 0 1 1）作为导引（如图2所示）。接下来是6bits的电文类型识别符和17bits的Z计数（message TOW count，电文星期时间计数），Z计数的值乘以6表示以秒为单位的下一个6s子帧电文的起始时间；然后是一个1bit的告警时标，若其为1，则表示L5用户可达测距精度（URA5）可能比第1子帧电文所给出的还要差，如果用户用该颗卫星进行导航定位测量，则由他们自己承担风险。为了防止跟踪到病态卫星，在第1，3，4，5子帧电文中还包含了一个6bits的PRN序列号（范围为1～37）。

正如前面所述，L5导航电文大致上与L1/L2导航电文相同，所以这里主要讨论不同于L1/L2的电文内容。

在第1子帧电文中，除了包括L1/L2第1子帧中的参数外，还包括了第2，3子帧的一些星历参数，下面列举了一些它们的不同点：

（1）不包含L2的数据和码标志，这些信息包含在第3子帧电文中。

（2）只包含卫星L5的健康状况参数，卫星L1，L2的健康状况参数包含在第3子帧电文中。

（3）URA值表示的只是表达L5的测距精度，而不是L1/L2的测距精度。虽然星钟参数受群时延效应的影响，这些传输参数与L1/L2中的传输参数N所表达的含义是一致的，即相同的传输参数N对应的用户可达测距精度相同。

（4）L1/L5的组合时钟改正参数a05，a15，a25和t05不同于L1/L2的组合时钟改正参数（L1/L5的其他组合参数，如历书参数信息，同样的也不同于L1/L2组合参数）。

（5）L1/L2中的群时延改正参数Tgd，被3个相应的微分群时延参数Tgd15，Tgd25，△Tiq5所代替，其关系如图3所示。

图3 信号群时延关系示意图

我们知道，电磁波通过电离层所产生的传播路径差与电磁波频率fLi（fLi表示第i信号的频率）的平方成反比，依据《GPS卫星导航定位原理与方法》一书第5章中式（5.1.4）测码伪距方程可知：

依此，可用L1/L5伪距观测值的线性组合构造一个无电离层影响的伪距组合观测值（推导方法见《GPS卫星导航定位原理与方法》一书第6章6.4节）：

对只使用L1的用户而言，其L1信号传播时间为：

式中，tL5为L5传播时间观测值。

相类似，对只使用L5的用户而言，L5的传播时间为：

L2-C/A码的改正参数为Tgd25，在导航电文中必须提供，以计算其相对L5 GPS时间系统的时间偏差，由

同样可以计算得到tgd25：

当L1/L2或L2/L5无电离层影响伪距组合观测值时必须施加相应的群时延改正：

式中，

第2子帧电文的内容为L1/L2导航电文第2，3子帧中其余的星历参数。在正常情况下，全部的卫星钟参数和星历数据等每18s播发一次（L1和L2是每30s播发一次），而星历表的数据龄期IODE与第1子帧电文的星钟数据龄期IODC的内容是一致的，同样的只与L1/L2第2，3子帧的最低8bits相反。

第3帧电文提供了单频电离层改正模型和协调世界时（UTC）参数，与L1，L2中第4子帧18页中的信息相对应。第3帧电文还包括上面提到L2数据和码标志以及L1，L2卫星健康状况参数，相应的参数包含在L1，L2的第一子帧中。L5时间与GPS时间的转换参数δA05和δA15也由第3帧电文提供。

第4子帧电文提供L1/L2第4子帧第12，19，20，22，23，24页面和第5子帧第1～24页面所包含的卫星历书参数，还提供第4，5子帧从25页面开始所包含的卫星型号及其L5健康状况。

第5子帧电文提供专用电文，它与L1/L2第4子帧第17页面提供的专用电文有所不同：它包括29个8bits的字符，而不是22个；它也提供了一个4bits的后续专用电文页面码号。

综上所述，L5导航电文，既继承了L1/L2导航电文的主要内容，又优化了它们的编码纠错，而采用了先进的CRC差错控制技术；相对于L1/L2导航电文所用的分组加元纠错而言，CRC纠错法具有下述优点：

⊙ 纠错能力强，CRC纠错可以100%地检测出所有奇数个随机错误和长度小于等于r（r为G(x)的阶数）的突发错误。CRC的生成多项式G(x)的阶数越高，误判的概率就越小。当仅用16位CRC纠错时，可以保证在1014码元中只含有一位未被检测出的错误，从而保证了卫星导航电文的无障碍传输。

⊙ 节省纠错码元，当用分组加元纠错法时，发送一个300bits的子帧电文，需用60bits的分加纠错码元；改用循环冗余纠错法时，发送同样一个300bits的子帧电文，只需用24bits的循冗纠错码元，节省了60%纠错码元；也即，可以增加36bits的电文发送。

⊙ 能够保持编码电文的连续性；只要待编电文参数的长度不大于276bits，就能够确保所编电文字码的连续性，而卫星导航电文基本参数的长度远小于该限值；例如，GPS卫星的轨道参数多为32bits（详如表3所示）。因此，CRC纠错既便于电文编码，又便于电文解码。

值得一提的是，Galileo卫星的导航电文，不仅也采用CRC纠错法编译码，而且采用类似于GPS L5导航电文的形式，其动态已知点也是由开普勒参数及其摄动量算得。因此，本节和前一节所述内容，可供使用Galileo卫星导航定位时参考。

表3 GPS卫星L5电文轨道参数及其长度

6 结束语

“奇偶检验法”是GPS等系统的卫星导航电文长期采用的一种行之有效的编码纠错方法，它能够有效地发现和纠正长度不大于列元个数的突发错误，而达到正确传送卫星导航电文的目的。它的主要缺点是浪费大量的存储空间，且给“长数据”电文解码带来不便。“循环冗余纠错法”（CRC）是目前在计算机网络通信及存储器中应用最广泛的一种差错控制技术，它能够克服“奇偶检验法”的不足，用较少的纠错码元，就能够纠正多种错误；例如，当仅用16位CRC纠错时，可以保证在1014码元中只含有一位未被检测出的错误，从而保证了卫星导航电文的无障碍传输。而被GPS L5信号、GLONASS L3信号和Galileo F/NAV的卫星导航电文所采用，而且三者的子帧都是采用24bits CRC纠错码如图4所示（详见“New Structure for GLONASS Nav Message, November 2, 2013 GPS World”和J. Sanz Subirana et al,“Galileo Navigation Message，http://www.navipedia.net/index.php/”）。本文仅较详细地论述了GPS L5信号的导航电文及其循环冗余纠错编码，以便有兴趣的读者依此深入解读这类导航电文。