衛星導航電文的編碼糾錯法── GNSS導航信號的收發問題之六

劉基余

（武漢大學測繪學院，武漢 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信號的導航電文及其循環冗余糾錯編碼，以便有興趣的讀者依此深入解讀這類導航電文。

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

圖4 B Galileo衛星F/NAV導航電文中的CRC糾錯編碼

[1] 劉基余.GPS衛星導航定位原理與方法.北京：北京科學出版社，2014年1月.

[2] 連宏.循環冗余檢驗法在數據鏈中的應用.導航，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] 王新梅，肖國鎮.糾錯碼－原理與方法.西安：西安電子科技大學出版社，2001.