衛(wèi)星導(dǎo)航電文的編碼糾錯法── GNSS導(dǎo)航信號的收發(fā)問題之六

劉基余

（武漢大學(xué)測繪學(xué)院，武漢 430079）

為了正確傳送衛(wèi)星導(dǎo)航電文，在編排導(dǎo)航電文時，不僅編排數(shù)據(jù)位，而且需要給出一定的糾錯碼元，致使GNSS導(dǎo)航信號接收機(jī)能夠完整地解譯出衛(wèi)星所發(fā)送的導(dǎo)航電文，而不會發(fā)生錯漏。本文以GPS衛(wèi)星導(dǎo)航電文為例，論述GNSS衛(wèi)星導(dǎo)航電文編碼糾錯編碼的現(xiàn)況與發(fā)展。

1 分組加元糾錯法的不足

從1978年2月的第一顆Block I衛(wèi)星開始，直至Block II，IIA，IIR衛(wèi)星，它們的第一、二GPS導(dǎo)航定位信號（L1，L2）的導(dǎo)航電文，都是采用了“奇偶檢驗(yàn)法”實(shí)施編碼糾錯；我們稱之為“分組加元糾錯法”。它以字碼為單位，即每個字碼的前面24bits為電文碼元（數(shù)據(jù)位），隨后6bits為糾錯碼元（奇偶校驗(yàn)位）。該法的1個字碼示例如表1所示；它們依下述列發(fā)順序傳送給用戶：101011111000100011011110101110。分組加元糾錯法，能夠有效地發(fā)現(xiàn)和糾正長度不大于列元個數(shù)的突發(fā)錯誤，而達(dá)到正確傳送衛(wèi)星導(dǎo)航電文的目的。

表1 分組加元糾錯法示例

從上可見，第一、二GPS導(dǎo)航定位信號（L1，L2）采用的“分組加元糾錯法”，編碼時，需要每24bits就加上6bits糾錯碼；解碼時，在取得信息之前，需要先將6bits糾錯碼從中剝?nèi)ァ＿@種“糾錯碼剝離法”，致使某些原本連續(xù)的信息變得不連續(xù)了；例如，衛(wèi)星軌道長半軸的平方根為32bits，分別位于第2子幀第8字碼的第3字節(jié)和第9字碼的前三個字節(jié)，而導(dǎo)致了的不連續(xù)性。如果從中除去奇偶校驗(yàn)碼，則的編碼表述才是連續(xù)的，編碼和解碼都將變得簡單方便，但不符合分組加元糾錯的編碼規(guī)律，不能夠應(yīng)用。而且，這種24+6bits（24bits電文碼元+6bits奇偶校驗(yàn)）的字碼結(jié)構(gòu)，浪費(fèi)了大量的存儲空間，冗余信息的比例達(dá)到20%之多！為了解決這個問題，GPS第三導(dǎo)航定位信號（L5）的導(dǎo)航電文采用了“循環(huán)冗余糾錯法”（CRC，Cyclic Redundancy Check），CRC是目前在計(jì)算機(jī)網(wǎng)絡(luò)通信及存儲器中應(yīng)用最廣泛的一種差錯控制技術(shù)。它所約定的糾錯規(guī)則是：讓糾錯碼能為某一約定電文代碼所除盡；如果除得盡，表明電文代碼正確；如果除不盡，余數(shù)將指明出錯位所在位置。

2 CRC糾錯編碼原理

CRC糾錯是一種采用多項(xiàng)式的編碼方法，它將一個以二進(jìn)制數(shù)字表示的數(shù)據(jù)系列看成一個多項(xiàng)式，例如，二進(jìn)制數(shù)字序列10101111，它可用下列多項(xiàng)式予以表示：

式中，xi表示代碼的位置，或某個二進(jìn)制數(shù)位的位置；xi前面的系數(shù)ai表示碼的值，若ai是一位二進(jìn)制代碼，則取值是0或1；M(x)稱為信息代碼多項(xiàng)式。多項(xiàng)式乘除法運(yùn)算過程與普通代數(shù)多項(xiàng)式的乘除法相同；多項(xiàng)式的加減法運(yùn)算以2為模，加減時不進(jìn)位或借位，和邏輯異或運(yùn)算一致。

采用CRC糾錯時，發(fā)送方和接收方用同一個生成多項(xiàng)式G(x)，并且G(x)的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以生成多項(xiàng)式G(x)去除待發(fā)送數(shù)據(jù)的k階多項(xiàng)式M(x)，得到n-k(n-k

如果一個k位的二進(jìn)制信息代碼序列多項(xiàng)式M(x)，當(dāng)采用CRC糾錯編碼時，就要增加（n-k）位的CRC糾錯碼，它們跟隨在信息代碼之后，而信息代碼在新序列中就表示成為xn-kM(x)，如圖1所示。

圖1 采用CRC糾錯的信息編碼

如果用一個CRC糾錯碼生成多項(xiàng)式G(x)去除代碼多項(xiàng)式xn-kM(x)，所得到的商數(shù)若為Q(x)，而其余數(shù)為R(x)，則知

故有

考慮到模二和多項(xiàng)式的加法和減法的運(yùn)算結(jié)果相同，由式（3）則知，帶CRC糾錯碼的發(fā)送信息多項(xiàng)式可寫成

由式（4）可知，表述經(jīng)過編碼后的信息代碼多項(xiàng)式{xn-kM(x)+R(x)}，是能夠被生成多項(xiàng)式G(x)除盡的，也即，它的余數(shù)為0。接收方在解碼該發(fā)送信息時，以余數(shù)是否為0，判定該發(fā)送信息是否在傳送過程中出錯；若為0，則表明信息傳送無誤；否則，表明信息傳送有誤。研究表明，CRC糾錯能夠保證在bits碼元中只含有一個碼元未被檢測出的錯誤。（詳見羅偉雄，韓力，原東昌，丁志杰.通信原理與電路.北京：北京理工大學(xué)出版社，1999）

3 CRC糾錯編碼方法

CRC糾錯碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)M(x)除以生成多項(xiàng)式G(x)，最后的余數(shù)作為CRC糾錯碼（如表2所示）。其實(shí)現(xiàn)步驟如下：

（1）設(shè)待發(fā)送的數(shù)據(jù)塊是k位的二進(jìn)制多項(xiàng)式M(x)，生成多項(xiàng)式為（n-k）階的G(x)，在數(shù)據(jù)塊的末尾添加（n-k）個0，數(shù)據(jù)塊的長度增加到n位，對應(yīng)的二進(jìn)制多項(xiàng)式為xn-kM(x)。

（2）用生成多項(xiàng)式G(x)去除xn-kM(x)，求得余數(shù)階數(shù)為（n-k-1）的二進(jìn)制多項(xiàng)式R(x)，此二進(jìn)制多項(xiàng)式R(x)就是M(x)經(jīng)過生成多項(xiàng)式G(x)編碼的CRC糾錯碼。

（3）用xn-kM(x)以模2和的方式減去R(x)，得到二進(jìn)制多項(xiàng)式xn-kM'(x)。這個xn-kM'(x)就是包含了CRC糾錯碼的待發(fā)送字符串。

從上述CRC糾錯編碼規(guī)則可見，CRC編碼實(shí)際上是將待發(fā)送的k位二進(jìn)制多項(xiàng)式M(x)轉(zhuǎn)換成了可以被G(x)除盡的n位二進(jìn)制多項(xiàng)式xn-kM(x)；因此，解碼時，可以用接收到的數(shù)據(jù)去除G(x)，如果余數(shù)為0，就表示數(shù)據(jù)在傳輸過程中沒有發(fā)生錯誤；若余數(shù)不為0，則表示數(shù)據(jù)在傳輸過程中肯定發(fā)生了錯誤。

表2 用CRC糾錯的導(dǎo)航電文仿真編碼

一般情況下，n-k位生成多項(xiàng)式產(chǎn)生的CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度小于等于n-k的突發(fā)錯誤以及（1-2-（n-k-1））的突發(fā)長度為n-k+1的突發(fā)錯誤和（1-2-n+k）的突發(fā)長度大于n-k+1的突發(fā)錯誤。所以CRC的生成多項(xiàng)式的階數(shù)越高，那么誤判的概率就越小。例如，采用24位CRC糾錯碼，就能檢測出所有突發(fā)長度小于等于24的突發(fā)錯誤以及99.999988%的突發(fā)長度為25的突發(fā)錯誤和99.999994%的突發(fā)長度大于25的突發(fā)錯誤。由此可見，CRC的糾錯能力是很強(qiáng)的。這里的突發(fā)錯誤是指幾乎連續(xù)發(fā)生的一串錯誤，突發(fā)長度就是指從出錯的第一位到出錯的最后一位的長度（但是，中間并不一定每一位都是錯誤）。

由于CRC糾錯的可靠性，CRC糾錯編碼廣泛用于傳輸重要數(shù)據(jù)，而在通信、計(jì)算機(jī)等領(lǐng)域中得到十分廣泛的應(yīng)用。在一些UART通信控制芯片（如MC6582，Intel8273，Z80-SIO）內(nèi)，都采用了CRC糾錯碼進(jìn)行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC差錯控制技術(shù)。

對于xn-kM'(x)，可以視為由M(x)和CRC糾錯碼組合而成，解碼時，將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的n-k位數(shù)據(jù)，即為原始數(shù)據(jù)。

4 CRC糾錯編碼在L5導(dǎo)航電文中應(yīng)用

GPS系統(tǒng)現(xiàn)代化后，GPS衛(wèi)星將增設(shè)第三導(dǎo)航定位信號（L5）。該信號的導(dǎo)航電文，將廢棄L1/L2導(dǎo)航電文所用采用的分組加元糾錯法，而采用CRC差錯控制技術(shù)。L5導(dǎo)航電文保持了現(xiàn)有導(dǎo)航電文的子幀結(jié)構(gòu)：每個子幀各有10個字碼，每個字碼30bits；也即，每個子幀共300bits，占用時間為6s，這樣，便與L1/L2導(dǎo)航電文的子幀時間保持一致。但是，L5導(dǎo)航電文每個子幀的最后24bits為CRC糾錯碼，以致冗余信息的比例僅占8%，相對于L1/L2導(dǎo)航電文結(jié)構(gòu)而言，既節(jié)省了糾錯碼元，又提高了糾錯能力。L5導(dǎo)航電文結(jié)構(gòu)，與GPS外部增強(qiáng)系統(tǒng)（如WAAS）所采用的電文結(jié)構(gòu)極其相似。L5導(dǎo)航電文，按下列方法實(shí)施CRC編碼糾錯：

① 將一個長度為24bits的寄存器內(nèi)容清零；

② 在276位數(shù)據(jù)bits后添加24個0bit組成新的300位數(shù)據(jù)bits；

③ 將寄存器的值左移一位，并將下一個數(shù)據(jù)bits讀入寄存器的最低位（bit0的位置）；

④ 如果第三步從寄存器移出的值為1，則將寄存器的值與生成多項(xiàng)式（最高位不參與運(yùn)算）做異或運(yùn)算，以運(yùn)算結(jié)果更新寄存器內(nèi)容；

⑤ 如果300位數(shù)據(jù)bits沒有全部讀完，則重復(fù)第三和第四步，否則轉(zhuǎn)到第六步；

⑥ 寄存器的內(nèi)容便是我們所要的CRC糾錯碼。

依上述方法，GPS衛(wèi)星播發(fā)的L5導(dǎo)航電文，它的各個子幀是由276個數(shù)據(jù)bits及其隨后附加24bits CRC糾錯碼構(gòu)成的。當(dāng)接收機(jī)接收到L5導(dǎo)航電文時，先按幀提出電文，然后對300bits的電文子幀進(jìn)行CRC糾錯；也即，將接收到的300bits的電文替代上述算法第二步中的300位數(shù)據(jù)bits，按照算法進(jìn)行校驗(yàn)。如果第六步寄存器最終得到的值為零，則說明傳輸無誤，可以進(jìn)行下一步的解碼；否則說明傳輸有錯，則將這幀電文舍棄。

5 L5導(dǎo)航電文

L5導(dǎo)航電文，設(shè)計(jì)了64種電文類型，其中第0號電文為默認(rèn)電文，當(dāng)衛(wèi)星生成導(dǎo)航電文時出現(xiàn)錯誤，衛(wèi)星就用默認(rèn)電文代替錯誤電文的內(nèi)容。第6～63號電文保留未定義。目前，只定義了第1～5號電文，也即，目前只使用了下述5種電文：

⊙ 第1幀電文（Message Type 1）：包含用戶測距可達(dá)精度、健康狀況、鐘差參數(shù)以及衛(wèi)星星歷）；

⊙ 第2幀電文（Message Type 2）：衛(wèi)星星歷；

⊙ 第3幀電文（Message Type 3）：電離層和UTC時間的參數(shù)；

⊙ 第4幀電文（Message Type 4）：衛(wèi)星歷書數(shù)據(jù)；

⊙ 第5幀電文（Message Type 5）：專用電文。

為了與L1/L2導(dǎo)航電文的名稱相對應(yīng)，我們?nèi)苑Q為之第1，2，3，4，5“子幀”。第1，2子幀電文是L1/L2導(dǎo)航電文中第1，2，3子幀信息的濃縮。對于民用而言，L1/L2導(dǎo)航電文中的備用信息（Reserved Data）不是必需的，故L5電文中不包含這些信息。同時原來每個字碼的6bits奇偶校驗(yàn)，也更換成為一個子幀的只用24bits CRC糾錯碼。這樣，L1/L2導(dǎo)航電文中第1，2，3子幀中的所有有用信息，加上L5的一些特有信息，就組合成了兩個6s的L5子幀電文。

圖2 GPS L5采用循環(huán)冗余糾錯碼編制的星歷電文

L1/L2導(dǎo)航電文的第4，5子幀的眾多頁面中也包含了大量的備用信息，而民用用戶只需要使用其中的電離層參數(shù)、UTC時間參數(shù)、衛(wèi)星歷書數(shù)據(jù)以及專用電文。這樣，L1/L2導(dǎo)航電文的第4，5子幀50個頁面的信息，就被濃縮在第3，4，5子幀電文中。

L5導(dǎo)航電文的每個子幀電文也像L1/L2子幀一樣，以8bits同步碼（1 0 0 0 1 0 1 1）作為導(dǎo)引（如圖2所示）。接下來是6bits的電文類型識別符和17bits的Z計(jì)數(shù)（message TOW count，電文星期時間計(jì)數(shù)），Z計(jì)數(shù)的值乘以6表示以秒為單位的下一個6s子幀電文的起始時間；然后是一個1bit的告警時標(biāo)，若其為1，則表示L5用戶可達(dá)測距精度（URA5）可能比第1子幀電文所給出的還要差，如果用戶用該顆衛(wèi)星進(jìn)行導(dǎo)航定位測量，則由他們自己承擔(dān)風(fēng)險(xiǎn)。為了防止跟蹤到病態(tài)衛(wèi)星，在第1，3，4，5子幀電文中還包含了一個6bits的PRN序列號（范圍為1～37）。

正如前面所述，L5導(dǎo)航電文大致上與L1/L2導(dǎo)航電文相同，所以這里主要討論不同于L1/L2的電文內(nèi)容。

在第1子幀電文中，除了包括L1/L2第1子幀中的參數(shù)外，還包括了第2，3子幀的一些星歷參數(shù)，下面列舉了一些它們的不同點(diǎn)：

（1）不包含L2的數(shù)據(jù)和碼標(biāo)志，這些信息包含在第3子幀電文中。

（2）只包含衛(wèi)星L5的健康狀況參數(shù)，衛(wèi)星L1，L2的健康狀況參數(shù)包含在第3子幀電文中。

（3）URA值表示的只是表達(dá)L5的測距精度，而不是L1/L2的測距精度。雖然星鐘參數(shù)受群時延效應(yīng)的影響，這些傳輸參數(shù)與L1/L2中的傳輸參數(shù)N所表達(dá)的含義是一致的，即相同的傳輸參數(shù)N對應(yīng)的用戶可達(dá)測距精度相同。

（4）L1/L5的組合時鐘改正參數(shù)a05，a15，a25和t05不同于L1/L2的組合時鐘改正參數(shù)（L1/L5的其他組合參數(shù)，如歷書參數(shù)信息，同樣的也不同于L1/L2組合參數(shù)）。

（5）L1/L2中的群時延改正參數(shù)Tgd，被3個相應(yīng)的微分群時延參數(shù)Tgd15，Tgd25，△Tiq5所代替，其關(guān)系如圖3所示。

圖3 信號群時延關(guān)系示意圖

我們知道，電磁波通過電離層所產(chǎn)生的傳播路徑差與電磁波頻率fLi（fLi表示第i信號的頻率）的平方成反比，依據(jù)《GPS衛(wèi)星導(dǎo)航定位原理與方法》一書第5章中式（5.1.4）測碼偽距方程可知：

依此，可用L1/L5偽距觀測值的線性組合構(gòu)造一個無電離層影響的偽距組合觀測值（推導(dǎo)方法見《GPS衛(wèi)星導(dǎo)航定位原理與方法》一書第6章6.4節(jié)）：

對只使用L1的用戶而言，其L1信號傳播時間為：

式中，tL5為L5傳播時間觀測值。

相類似，對只使用L5的用戶而言，L5的傳播時間為：

L2-C/A碼的改正參數(shù)為Tgd25，在導(dǎo)航電文中必須提供，以計(jì)算其相對L5 GPS時間系統(tǒng)的時間偏差，由

同樣可以計(jì)算得到tgd25：

當(dāng)L1/L2或L2/L5無電離層影響偽距組合觀測值時必須施加相應(yīng)的群時延改正：

式中，

第2子幀電文的內(nèi)容為L1/L2導(dǎo)航電文第2，3子幀中其余的星歷參數(shù)。在正常情況下，全部的衛(wèi)星鐘參數(shù)和星歷數(shù)據(jù)等每18s播發(fā)一次（L1和L2是每30s播發(fā)一次），而星歷表的數(shù)據(jù)齡期IODE與第1子幀電文的星鐘數(shù)據(jù)齡期IODC的內(nèi)容是一致的，同樣的只與L1/L2第2，3子幀的最低8bits相反。

第3幀電文提供了單頻電離層改正模型和協(xié)調(diào)世界時（UTC）參數(shù)，與L1，L2中第4子幀18頁中的信息相對應(yīng)。第3幀電文還包括上面提到L2數(shù)據(jù)和碼標(biāo)志以及L1，L2衛(wèi)星健康狀況參數(shù)，相應(yīng)的參數(shù)包含在L1，L2的第一子幀中。L5時間與GPS時間的轉(zhuǎn)換參數(shù)δA05和δA15也由第3幀電文提供。

第4子幀電文提供L1/L2第4子幀第12，19，20，22，23，24頁面和第5子幀第1～24頁面所包含的衛(wèi)星歷書參數(shù)，還提供第4，5子幀從25頁面開始所包含的衛(wèi)星型號及其L5健康狀況。

第5子幀電文提供專用電文，它與L1/L2第4子幀第17頁面提供的專用電文有所不同：它包括29個8bits的字符，而不是22個；它也提供了一個4bits的后續(xù)專用電文頁面碼號。

綜上所述，L5導(dǎo)航電文，既繼承了L1/L2導(dǎo)航電文的主要內(nèi)容，又優(yōu)化了它們的編碼糾錯，而采用了先進(jìn)的CRC差錯控制技術(shù)；相對于L1/L2導(dǎo)航電文所用的分組加元糾錯而言，CRC糾錯法具有下述優(yōu)點(diǎn)：

⊙ 糾錯能力強(qiáng)，CRC糾錯可以100%地檢測出所有奇數(shù)個隨機(jī)錯誤和長度小于等于r（r為G(x)的階數(shù)）的突發(fā)錯誤。CRC的生成多項(xiàng)式G(x)的階數(shù)越高，誤判的概率就越小。當(dāng)僅用16位CRC糾錯時，可以保證在1014碼元中只含有一位未被檢測出的錯誤，從而保證了衛(wèi)星導(dǎo)航電文的無障礙傳輸。

⊙ 節(jié)省糾錯碼元，當(dāng)用分組加元糾錯法時，發(fā)送一個300bits的子幀電文，需用60bits的分加糾錯碼元；改用循環(huán)冗余糾錯法時，發(fā)送同樣一個300bits的子幀電文，只需用24bits的循冗糾錯碼元，節(jié)省了60%糾錯碼元；也即，可以增加36bits的電文發(fā)送。

⊙ 能夠保持編碼電文的連續(xù)性；只要待編電文參數(shù)的長度不大于276bits，就能夠確保所編電文字碼的連續(xù)性，而衛(wèi)星導(dǎo)航電文基本參數(shù)的長度遠(yuǎn)小于該限值；例如，GPS衛(wèi)星的軌道參數(shù)多為32bits（詳如表3所示）。因此，CRC糾錯既便于電文編碼，又便于電文解碼。

值得一提的是，Galileo衛(wèi)星的導(dǎo)航電文，不僅也采用CRC糾錯法編譯碼，而且采用類似于GPS L5導(dǎo)航電文的形式，其動態(tài)已知點(diǎn)也是由開普勒參數(shù)及其攝動量算得。因此，本節(jié)和前一節(jié)所述內(nèi)容，可供使用Galileo衛(wèi)星導(dǎo)航定位時參考。

表3 GPS衛(wèi)星L5電文軌道參數(shù)及其長度

6 結(jié)束語

“奇偶檢驗(yàn)法”是GPS等系統(tǒng)的衛(wèi)星導(dǎo)航電文長期采用的一種行之有效的編碼糾錯方法，它能夠有效地發(fā)現(xiàn)和糾正長度不大于列元個數(shù)的突發(fā)錯誤，而達(dá)到正確傳送衛(wèi)星導(dǎo)航電文的目的。它的主要缺點(diǎn)是浪費(fèi)大量的存儲空間，且給“長數(shù)據(jù)”電文解碼帶來不便?！把h(huán)冗余糾錯法”（CRC）是目前在計(jì)算機(jī)網(wǎng)絡(luò)通信及存儲器中應(yīng)用最廣泛的一種差錯控制技術(shù)，它能夠克服“奇偶檢驗(yàn)法”的不足，用較少的糾錯碼元，就能夠糾正多種錯誤；例如，當(dāng)僅用16位CRC糾錯時，可以保證在1014碼元中只含有一位未被檢測出的錯誤，從而保證了衛(wèi)星導(dǎo)航電文的無障礙傳輸。而被GPS L5信號、GLONASS L3信號和Galileo F/NAV的衛(wèi)星導(dǎo)航電文所采用，而且三者的子幀都是采用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/”）。本文僅較詳細(xì)地論述了GPS L5信號的導(dǎo)航電文及其循環(huán)冗余糾錯編碼，以便有興趣的讀者依此深入解讀這類導(dǎo)航電文。

圖4 A GLONASS衛(wèi)星L3OC第20子幀中歷書電文的CRC糾錯編碼

圖4 B Galileo衛(wèi)星F/NAV導(dǎo)航電文中的CRC糾錯編碼

[1] 劉基余.GPS衛(wèi)星導(dǎo)航定位原理與方法.北京：北京科學(xué)出版社，2014年1月.

[2] 連宏.循環(huán)冗余檢驗(yàn)法在數(shù)據(jù)鏈中的應(yīng)用.導(dǎo)航，Vol.41,No.2,2005,P.106~110.

[3] Van Dierendonck, A.J. The New L5 Civil GPS signal GPS World, Sep.2000, Vol. 11 Issue 9, p64~71.

[4] Interface Specif i cation IS-GPS-200 Revision D, 7 December 2004.

[5] 王新梅，肖國鎮(zhèn).糾錯碼－原理與方法.西安：西安電子科技大學(xué)出版社，2001.