劉基余
(武漢大學(xué)測繪學(xué)院,武漢 430079)
為了正確傳送衛(wèi)星導(dǎo)航電文,在編排導(dǎo)航電文時(shí),不僅編排數(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ā)展。
從1978年2月的第一顆Block I衛(wèi)星開始,直至Block II,IIA,IIR衛(wèi)星,它們的第一、二GPS導(dǎo)航定位信號(L1,L2)的導(dǎo)航電文,都是采用了“奇偶檢驗(yàn)法”實(shí)施編碼糾錯;我們稱之為“分組加元糾錯法”。它以字碼為單位,即每個(gè)字碼的前面24bits為電文碼元(數(shù)據(jù)位),隨后6bits為糾錯碼元(奇偶校驗(yàn)位)。該法的1個(gè)字碼示例如表1所示;它們依下述列發(fā)順序傳送給用戶:101011111000100011011110101110。分組加元糾錯法,能夠有效地發(fā)現(xiàn)和糾正長度不大于列元個(gè)數(shù)的突發(fā)錯誤,而達(dá)到正確傳送衛(wèi)星導(dǎo)航電文的目的。
表1 分組加元糾錯法示例
從上可見,第一、二GPS導(dǎo)航定位信號(L1,L2)采用的“分組加元糾錯法”,編碼時(shí),需要每24bits就加上6bits糾錯碼;解碼時(shí),在取得信息之前,需要先將6bits糾錯碼從中剝?nèi)?。這種“糾錯碼剝離法”,致使某些原本連續(xù)的信息變得不連續(xù)了;例如,衛(wèi)星軌道長半軸的平方根為32bits,分別位于第2子幀第8字碼的第3字節(jié)和第9字碼的前三個(gè)字節(jié),而導(dǎo)致了的不連續(xù)性。如果從中除去奇偶校驗(yàn)碼,則的編碼表述才是連續(xù)的,編碼和解碼都將變得簡單方便,但不符合分組加元糾錯的編碼規(guī)律,不能夠應(yīng)用。而且,這種24+6bits(24bits電文碼元+6bits奇偶校驗(yàn))的字碼結(jié)構(gòu),浪費(fèi)了大量的存儲空間,冗余信息的比例達(dá)到20%之多!為了解決這個(gè)問題,GPS第三導(dǎo)航定位信號(L5)的導(dǎo)航電文采用了“循環(huán)冗余糾錯法”(CRC,Cyclic Redundancy Check),CRC是目前在計(jì)算機(jī)網(wǎng)絡(luò)通信及存儲器中應(yīng)用最廣泛的一種差錯控制技術(shù)。它所約定的糾錯規(guī)則是:讓糾錯碼能為某一約定電文代碼所除盡;如果除得盡,表明電文代碼正確;如果除不盡,余數(shù)將指明出錯位所在位置。
CRC糾錯是一種采用多項(xiàng)式的編碼方法,它將一個(gè)以二進(jìn)制數(shù)字表示的數(shù)據(jù)系列看成一個(gè)多項(xiàng)式,例如,二進(jìn)制數(shù)字序列10101111,它可用下列多項(xiàng)式予以表示:
式中,xi表示代碼的位置,或某個(gè)二進(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為模,加減時(shí)不進(jìn)位或借位,和邏輯異或運(yùn)算一致。
采用CRC糾錯時(shí),發(fā)送方和接收方用同一個(gè)生成多項(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 如果一個(gè)k位的二進(jìn)制信息代碼序列多項(xiàng)式M(x),當(dāng)采用CRC糾錯編碼時(shí),就要增加(n-k)位的CRC糾錯碼,它們跟隨在信息代碼之后,而信息代碼在新序列中就表示成為xn-kM(x),如圖1所示。 圖1 采用CRC糾錯的信息編碼 如果用一個(gè)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í),以余數(shù)是否為0,判定該發(fā)送信息是否在傳送過程中出錯;若為0,則表明信息傳送無誤;否則,表明信息傳送有誤。研究表明,CRC糾錯能夠保證在bits碼元中只含有一個(gè)碼元未被檢測出的錯誤。(詳見羅偉雄,韓力,原東昌,丁志杰.通信原理與電路.北京:北京理工大學(xué)出版社,1999) 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)個(gè)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)。這個(gè)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í),可以用接收到的數(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糾錯碼組合而成,解碼時(shí),將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的n-k位數(shù)據(jù),即為原始數(shù)據(jù)。 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):每個(gè)子幀各有10個(gè)字碼,每個(gè)字碼30bits;也即,每個(gè)子幀共300bits,占用時(shí)間為6s,這樣,便與L1/L2導(dǎo)航電文的子幀時(shí)間保持一致。但是,L5導(dǎo)航電文每個(gè)子幀的最后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編碼糾錯: ① 將一個(gè)長度為24bits的寄存器內(nèi)容清零; ② 在276位數(shù)據(jù)bits后添加24個(gè)0bit組成新的300位數(shù)據(jù)bits; ③ 將寄存器的值左移一位,并將下一個(gè)數(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)航電文,它的各個(gè)子幀是由276個(gè)數(shù)據(jù)bits及其隨后附加24bits CRC糾錯碼構(gòu)成的。當(dāng)接收機(jī)接收到L5導(dǎo)航電文時(shí),先按幀提出電文,然后對300bits的電文子幀進(jìn)行CRC糾錯;也即,將接收到的300bits的電文替代上述算法第二步中的300位數(shù)據(jù)bits,按照算法進(jìn)行校驗(yàn)。如果第六步寄存器最終得到的值為零,則說明傳輸無誤,可以進(jìn)行下一步的解碼;否則說明傳輸有錯,則將這幀電文舍棄。 L5導(dǎo)航電文,設(shè)計(jì)了64種電文類型,其中第0號電文為默認(rèn)電文,當(dāng)衛(wèi)星生成導(dǎo)航電文時(shí)出現(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í)間的參數(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電文中不包含這些信息。同時(shí)原來每個(gè)字碼的6bits奇偶校驗(yàn),也更換成為一個(gè)子幀的只用24bits CRC糾錯碼。這樣,L1/L2導(dǎo)航電文中第1,2,3子幀中的所有有用信息,加上L5的一些特有信息,就組合成了兩個(gè)6s的L5子幀電文。 圖2 GPS L5采用循環(huán)冗余糾錯碼編制的星歷電文 L1/L2導(dǎo)航電文的第4,5子幀的眾多頁面中也包含了大量的備用信息,而民用用戶只需要使用其中的電離層參數(shù)、UTC時(shí)間參數(shù)、衛(wèi)星歷書數(shù)據(jù)以及專用電文。這樣,L1/L2導(dǎo)航電文的第4,5子幀50個(gè)頁面的信息,就被濃縮在第3,4,5子幀電文中。 L5導(dǎo)航電文的每個(gè)子幀電文也像L1/L2子幀一樣,以8bits同步碼(1 0 0 0 1 0 1 1)作為導(dǎo)引(如圖2所示)。接下來是6bits的電文類型識別符和17bits的Z計(jì)數(shù)(message TOW count,電文星期時(shí)間計(jì)數(shù)),Z計(jì)數(shù)的值乘以6表示以秒為單位的下一個(gè)6s子幀電文的起始時(shí)間;然后是一個(gè)1bit的告警時(shí)標(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子幀電文中還包含了一個(gè)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ù)受群時(shí)延效應(yīng)的影響,這些傳輸參數(shù)與L1/L2中的傳輸參數(shù)N所表達(dá)的含義是一致的,即相同的傳輸參數(shù)N對應(yīng)的用戶可達(dá)測距精度相同。 (4)L1/L5的組合時(shí)鐘改正參數(shù)a05,a15,a25和t05不同于L1/L2的組合時(shí)鐘改正參數(shù)(L1/L5的其他組合參數(shù),如歷書參數(shù)信息,同樣的也不同于L1/L2組合參數(shù))。 (5)L1/L2中的群時(shí)延改正參數(shù)Tgd,被3個(gè)相應(yīng)的微分群時(shí)延參數(shù)Tgd15,Tgd25,△Tiq5所代替,其關(guān)系如圖3所示。 圖3 信號群時(shí)延關(guān)系示意圖 我們知道,電磁波通過電離層所產(chǎn)生的傳播路徑差與電磁波頻率fLi(fLi表示第i信號的頻率)的平方成反比,依據(jù)《GPS衛(wèi)星導(dǎo)航定位原理與方法》一書第5章中式(5.1.4)測碼偽距方程可知: 依此,可用L1/L5偽距觀測值的線性組合構(gòu)造一個(gè)無電離層影響的偽距組合觀測值(推導(dǎo)方法見《GPS衛(wèi)星導(dǎo)航定位原理與方法》一書第6章6.4節(jié)): 對只使用L1的用戶而言,其L1信號傳播時(shí)間為: 式中,tL5為L5傳播時(shí)間觀測值。 相類似,對只使用L5的用戶而言,L5的傳播時(shí)間為: L2-C/A碼的改正參數(shù)為Tgd25,在導(dǎo)航電文中必須提供,以計(jì)算其相對L5 GPS時(shí)間系統(tǒng)的時(shí)間偏差,由 同樣可以計(jì)算得到tgd25: 當(dāng)L1/L2或L2/L5無電離層影響偽距組合觀測值時(shí)必須施加相應(yīng)的群時(shí)延改正: 式中, 第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)世界時(shí)(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時(shí)間與GPS時(shí)間的轉(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個(gè)8bits的字符,而不是22個(gè);它也提供了一個(gè)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ù)個(gè)隨機(jī)錯誤和長度小于等于r(r為G(x)的階數(shù))的突發(fā)錯誤。CRC的生成多項(xiàng)式G(x)的階數(shù)越高,誤判的概率就越小。當(dāng)僅用16位CRC糾錯時(shí),可以保證在1014碼元中只含有一位未被檢測出的錯誤,從而保證了衛(wèi)星導(dǎo)航電文的無障礙傳輸。 ⊙ 節(jié)省糾錯碼元,當(dāng)用分組加元糾錯法時(shí),發(fā)送一個(gè)300bits的子幀電文,需用60bits的分加糾錯碼元;改用循環(huán)冗余糾錯法時(shí),發(fā)送同樣一個(gè)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)航定位時(shí)參考。 表3 GPS衛(wèi)星L5電文軌道參數(shù)及其長度 “奇偶檢驗(yàn)法”是GPS等系統(tǒng)的衛(wèi)星導(dǎo)航電文長期采用的一種行之有效的編碼糾錯方法,它能夠有效地發(fā)現(xiàn)和糾正長度不大于列元個(gè)數(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糾錯時(shí),可以保證在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.3 CRC糾錯編碼方法
4 CRC糾錯編碼在L5導(dǎo)航電文中應(yīng)用
5 L5導(dǎo)航電文
6 結(jié)束語