??? 摘? 要: 為了解決嵌入式GPS車載系統(tǒng)" title="車載系統(tǒng)">車載系統(tǒng)中存儲(chǔ)空間小、GPS定位數(shù)據(jù)量大的矛盾,根據(jù) GPS定位數(shù)據(jù)的特點(diǎn),提出了專用于GPS定位數(shù)據(jù)壓縮" title="數(shù)據(jù)壓縮">數(shù)據(jù)壓縮的改進(jìn)型半字節(jié)壓縮算法" title="壓縮算法">壓縮算法。該算法是一種在原半字節(jié)壓縮算法的基礎(chǔ)上改進(jìn)的算法,經(jīng)過(guò)實(shí)際測(cè)試,壓縮比" title="壓縮比">壓縮比可達(dá)50%。若將壓縮預(yù)處理也折算在內(nèi),總壓縮比可達(dá)80%以上,為車載系統(tǒng)節(jié)省了大量的存儲(chǔ)資源。除此之外,也縮短了GSM信道的占用時(shí)間,大大地緩解了向控制調(diào)度中心上傳數(shù)據(jù)的壓力。?

　　關(guān)鍵詞: 數(shù)據(jù)壓縮? GPS數(shù)據(jù)格式? 壓縮預(yù)處理? 半字節(jié)壓縮算法

?

??? 嵌入式GPS車載系統(tǒng)一般體積較小,無(wú)存儲(chǔ)量大的硬盤等設(shè)備,系統(tǒng)程序、應(yīng)用程序一般裝在FLASH或ROM中。由于FLASH 或 ROM等存儲(chǔ)介質(zhì)的價(jià)格相對(duì)臺(tái)式機(jī)上廣泛使用的硬盤、光盤等來(lái)說(shuō)是非常昂貴的,因此,在開發(fā)嵌入式系統(tǒng)" title="嵌入式系統(tǒng)">嵌入式系統(tǒng)的軟件產(chǎn)品時(shí)必須將軟件所占的存儲(chǔ)空間限制在一定的范圍內(nèi)。?

　　在GPS車載系統(tǒng)的研發(fā)過(guò)程中,主要需解決的問(wèn)題是:車載系統(tǒng)為了實(shí)現(xiàn)自導(dǎo)航,必須儲(chǔ)存大量的GPS定位數(shù)據(jù)(每天需要存儲(chǔ)約6MB);其二是這些數(shù)據(jù)還要通過(guò)GSM信道上傳到控制調(diào)度中心(若通過(guò)短信業(yè)務(wù)發(fā)送,每次160B,則需要每分上傳6次)。無(wú)疑,數(shù)據(jù)壓縮是在不增加硬件成本的前提下,從軟件的角度來(lái)充分發(fā)揮系統(tǒng)現(xiàn)有資源的有效辦法。?

　　數(shù)據(jù)壓縮方法種類繁多,可以分為無(wú)損壓縮和有損壓縮兩大類。無(wú)損壓縮利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮,可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真,但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制,一般為2:1到5:1。這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(如指紋圖像、醫(yī)學(xué)圖像等)的壓縮。有損壓縮方法利用了人類視覺(jué)對(duì)圖像中的某些頻率成分不敏感的特性,允許壓縮過(guò)程中損失一定的信息。雖然不能完全恢復(fù)原始數(shù)據(jù),但是所損失的部分對(duì)理解原始圖像的影響較小,卻換來(lái)了大得多的壓縮比。有損壓縮廣泛應(yīng)用于語(yǔ)音、圖像和視頻數(shù)據(jù)的壓縮。?

　　目前現(xiàn)成的壓縮算法很多,但不能直接用于嵌入式系統(tǒng)當(dāng)中,這完全由嵌入式系統(tǒng)的特點(diǎn)所決定。首先,用于嵌入式系統(tǒng)的數(shù)據(jù)壓縮方法應(yīng)是無(wú)損壓縮方法。其次,壓縮代碼和解碼所需的信息代碼必須足夠短,否則就會(huì)失去壓縮的意義。還有,嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須結(jié)合具體的數(shù)據(jù)格式的特點(diǎn),才能進(jìn)一步提高數(shù)據(jù)的壓縮比。除此之外,目前的壓縮程序的啟動(dòng)執(zhí)行必須人為干預(yù),不能自動(dòng)執(zhí)行,因?yàn)樗鼈兪菫槲募到y(tǒng)設(shè)計(jì)的,而嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須能夠自動(dòng)執(zhí)行。?

1 GPS數(shù)據(jù)格式?

　　GPS OEM板由變頻器、信號(hào)通道、微處理器和存儲(chǔ)單元等組成。GPS OEM板的型號(hào)甚多,性能各異,但大多采用美國(guó)國(guó)家海洋電子協(xié)會(huì)制定的NMEA-0183通信標(biāo)準(zhǔn)格式。本系統(tǒng)選擇的是美國(guó)SiRF公司的SiRFstarII OEM板。SiRFstarII OEM板語(yǔ)句的輸入、輸出是通過(guò)RS232串行接口完成的，其通信端口的數(shù)據(jù)格式應(yīng)該設(shè)置為8個(gè)數(shù)據(jù)位、1個(gè)起始位和1個(gè)停止位，校驗(yàn)方式選為無(wú)奇偶校驗(yàn)，波特率設(shè)置為4800波特。NMEA-0183通信標(biāo)準(zhǔn)的輸出數(shù)據(jù)采用的是ASCII碼，其內(nèi)容包含了緯度、經(jīng)度、高度、速度、日期、時(shí)間、航向以及衛(wèi)星狀況等信息，語(yǔ)句有六種，包括GGA、GLL、GSA、GSV、RMC和 VTG。對(duì)于不同的用途,選用的語(yǔ)句記錄也不同,例如嵌入式GPS車載系統(tǒng)的使用者只關(guān)心其日期和時(shí)間、經(jīng)緯度、地面速度信息,因而可以只選用RMC記錄語(yǔ)句。一條＄GPRMC語(yǔ)句包括13個(gè)記錄:語(yǔ)句標(biāo)識(shí)頭、世界時(shí)間、定位狀態(tài)、緯度、緯度方位、經(jīng)度、經(jīng)度方位、地面速度、地面路線、日期、磁偏角、校驗(yàn)和和結(jié)束標(biāo)記,它一共占用70個(gè)字節(jié)(其中還包括用于分隔記錄所使用的11個(gè)逗號(hào)),例如:

??? ＄GPRMC，121530.998，A，4000.0162，N，11619.5476，E，0.00，240.81，160102，,*3B?

??? 由此可見,從SiRFstarII OEM板接收下來(lái)的數(shù)據(jù)流是文本字符串,根據(jù)GPS數(shù)據(jù)格式的特點(diǎn),本設(shè)計(jì)中擬采用半字節(jié)法完成壓縮及解壓縮的任務(wù)。該方法屬于無(wú)損壓縮技術(shù),其原理是去除字節(jié)中的冗余位,從而達(dá)到壓縮目的。然而,這種方法只適用于純數(shù)字文本文件的壓縮,顯然GPS定位數(shù)據(jù)并不是純數(shù)字的,還必須在壓縮前進(jìn)行一下壓縮預(yù)處理,最后再利用半字節(jié)壓縮算法完成數(shù)據(jù)的壓縮。?

2 壓縮預(yù)處理?

　　仔細(xì)觀察以上各段數(shù)據(jù)記錄,可以發(fā)現(xiàn)語(yǔ)句之間的數(shù)據(jù)段還存在很多冗余。除此之外,這些記錄中所含的信息既有英文字符又有數(shù)字,為了后續(xù)的壓縮,對(duì)語(yǔ)句中的各個(gè)記錄應(yīng)做如下的預(yù)處理:?

　?、僬Z(yǔ)句標(biāo)識(shí)頭(ID):因?yàn)槊總€(gè)語(yǔ)句的標(biāo)識(shí)頭都一樣,所以該記錄段屬于冗余信息,完全可以去除,在解壓縮時(shí)再在每個(gè)語(yǔ)句前加上該標(biāo)識(shí)頭即可。?

　?、谑澜鐣r(shí)間(UTC):該信息段以時(shí)、分、秒、毫秒的格式指示出當(dāng)時(shí)的世界時(shí)間。轉(zhuǎn)換為北京時(shí)間還需要再加上8小時(shí)。由于車載系統(tǒng)的定位數(shù)據(jù)的采集是以秒為單位的,所以毫秒量級(jí)的數(shù)據(jù)對(duì)本系統(tǒng)根本無(wú)用,是冗余信息,將其去除后,世界時(shí)間完全可以用6個(gè)字節(jié)表示。然而,由于世界時(shí)間是按秒增1,定位數(shù)據(jù)也是每秒更新一次,所以世界時(shí)間可以在程序的一開始采集記錄一下,在解壓縮時(shí)根據(jù)語(yǔ)句的指針值再加上起始時(shí)間便可以復(fù)原,因此該記錄段在第一次存儲(chǔ)后,以后的語(yǔ)句中的該信息全都是冗余信息。?

　?、鄱ㄎ粻顟B(tài)(A/V):占用1個(gè)字節(jié),不進(jìn)行預(yù)處理。由于車載系統(tǒng)處于的地方有可能收不到衛(wèi)星信號(hào)(如隧道中),致使定位信息無(wú)效,因此盡管該字段發(fā)生變化的概率較小,又與其它信息段不相關(guān),在此仍不能做預(yù)處理。?

　　④緯度:占用9個(gè)字節(jié),不進(jìn)行預(yù)處理。?

　?、萁?jīng)度:占用10個(gè)字節(jié),不進(jìn)行預(yù)處理。?

　?、藿?jīng)度指示器(E/W):占一個(gè)字節(jié),它指示出經(jīng)度是東經(jīng),還是西經(jīng)。由于各個(gè)＄GPRMC語(yǔ)句中的該段信息在中國(guó)都是東經(jīng),它是冗余信息,因此也采取程序一開始存儲(chǔ)一次的方法。?

　　⑦緯度指示器(N/S):占一個(gè)字節(jié),各個(gè)＄GPRMC語(yǔ)句中的該段信息完全一樣,是冗余信息,處理方法與上相同。?

　?、嗟孛嫠俣?占用4個(gè)字節(jié),不進(jìn)行預(yù)處理。?

　?、崛掌?占用6個(gè)字節(jié),以日、月、年的格式顯示,各個(gè)＄GPRMC語(yǔ)句中的該段信息在24小時(shí)內(nèi)完全一樣,是冗余信息,采取程序一開始存儲(chǔ)一次的方法,以后語(yǔ)句中的該段信息全部廢除。?

　　⑩校驗(yàn)和:占用3個(gè)字節(jié),該數(shù)據(jù)完成校驗(yàn)后便棄之,不保留和進(jìn)行壓縮。?

　　結(jié)束符占用2個(gè)字節(jié),只用來(lái)判斷語(yǔ)句的有效數(shù)據(jù)范圍,其它記錄段與本系統(tǒng)的設(shè)計(jì)無(wú)關(guān)都不保留和進(jìn)行壓縮。?

　　通過(guò)以上壓縮預(yù)處理后,保留了四個(gè)數(shù)據(jù)記錄,共占用24個(gè)字節(jié),如圖1所示。?

?

?

3 改進(jìn)型半字節(jié)壓縮算法?

　　文本數(shù)據(jù)的壓縮所使用的都是無(wú)損壓縮技術(shù),即還原后的文件應(yīng)該與源文件完全相同。文本文件壓縮的方法有很多種,如HUFFMAN編碼、算術(shù)編碼和字典壓縮方法等。它們均是無(wú)損壓縮方法,都適用于文本數(shù)據(jù)的壓縮。半字節(jié)壓縮方法是針對(duì)文本數(shù)據(jù)的特點(diǎn)所設(shè)計(jì)的,主要是去除文本中的字節(jié)中的冗余位,從而達(dá)到減少數(shù)據(jù)文件所占用的存儲(chǔ)空間的目的。在數(shù)據(jù)壓縮技術(shù)中,除壓縮重復(fù)字符外,還可以根據(jù)數(shù)據(jù)本身的特點(diǎn)進(jìn)行壓縮。在計(jì)算機(jī)中,任何數(shù)據(jù)都是以某種代碼的方式存儲(chǔ)的。在一些文件中,或許有一些代碼具有某些相似之處,我們可以根據(jù)代碼的特點(diǎn)進(jìn)行特定的操作,壓縮掉這些數(shù)據(jù)的相似部分,或者說(shuō)壓縮掉這些數(shù)據(jù)的特征部分,半字節(jié)壓縮就是這樣一種方法。半字節(jié)方法主要用于純數(shù)字的文本文件的壓縮,因?yàn)閿?shù)字0～9的ASCII碼的高四位都一樣,是冗余的,因此每一個(gè)數(shù)字完全可以用低四位描述,即每個(gè)字符的八位編碼可壓縮為四位編碼,壓縮比理論上可趨近50%。?

　　從圖1中可以看出,經(jīng)過(guò)預(yù)處理后的數(shù)據(jù)中,包含的文本字符有:“0～9”十個(gè)數(shù)字符號(hào),“A”、“V”兩個(gè)英文大寫字母和一個(gè)小數(shù)點(diǎn)“.”符號(hào),共13個(gè)符號(hào)?！癆、“V”、“.”的ASCII碼的高四位顯然與數(shù)字字符的不一樣,半字節(jié)壓縮方法不能簡(jiǎn)單套用。然而,我們知道四位二進(jìn)制編碼可區(qū)分16種狀態(tài),用來(lái)表示13種不同的字符是足夠的。?

　　壓縮數(shù)據(jù)編碼表如表1所示,為了充分利用編碼表中的狀態(tài),在原來(lái)13個(gè)字符的基礎(chǔ)上又新增添了兩個(gè)字符“B”和“W″,其四位編碼分別為1101和1110。這兩個(gè)字符是在壓縮預(yù)處理過(guò)程中,用來(lái)記錄那些因語(yǔ)句校驗(yàn)和出錯(cuò)而舍棄的語(yǔ)句。因?yàn)槊織l語(yǔ)句的時(shí)間信息全部在預(yù)處理階段被舍棄,在解壓縮時(shí)要恢復(fù)時(shí)間值。該值在正常情況下是根據(jù)時(shí)間的基數(shù)再加上語(yǔ)句的計(jì)數(shù)值(由于每秒接受到一條語(yǔ)句,所以語(yǔ)句計(jì)數(shù)值就是以秒為單位的時(shí)間增量)確定的。當(dāng)發(fā)生語(yǔ)句校驗(yàn)和出錯(cuò)時(shí),若處于定位有效狀態(tài),則在定位狀態(tài)記錄上不填寫“A”字符,而填寫“B”字符;若處在定位無(wú)效狀態(tài),則不填寫“V”字符,而填寫“W”字符。在以后解壓縮時(shí),若檢測(cè)到“A”、“V”字符,時(shí)間的還原按正常的算法進(jìn)行;若檢測(cè)到“B”、“W”字符時(shí),時(shí)間的還原除了按正常的算法進(jìn)行以外還要加上一秒鐘,這樣才能確保時(shí)間能夠正確的恢復(fù),這是因?yàn)椤癇”、“W”字符表示上一條語(yǔ)句發(fā)生錯(cuò)誤已經(jīng)被丟棄,語(yǔ)句的壓縮是非連續(xù)的,有斷句現(xiàn)象發(fā)生。?

?

?

　　通過(guò)此編碼表進(jìn)行轉(zhuǎn)換后,原來(lái)經(jīng)過(guò)壓縮預(yù)處理后的固定24個(gè)字節(jié)長(zhǎng)的文本數(shù)據(jù)就可以減小一半(壓縮后為固定的12個(gè)字節(jié)長(zhǎng)),壓縮比為50%,若從未經(jīng)過(guò)預(yù)處理的文本數(shù)據(jù)算起,則壓縮比可達(dá)到80%。?

　　由圖2可知,實(shí)現(xiàn)半字節(jié)壓縮算法需要解決兩個(gè)問(wèn)題:首先是壓縮對(duì)象的計(jì)數(shù);其次是如何把兩個(gè)數(shù)字的低位合并到一個(gè)字節(jié)中。后一個(gè)問(wèn)題只要規(guī)定好壓縮后的字節(jié)中奇數(shù)號(hào)字符的四位編碼與偶數(shù)號(hào)字符的四位編碼的存放次序即可,程序的實(shí)現(xiàn)非常簡(jiǎn)單,在此我們規(guī)定編號(hào)是奇數(shù)的字符放在高四位,編號(hào)為偶數(shù)的字符的編碼放在低四位。假設(shè)壓縮前的數(shù)據(jù)流中的前四個(gè)字符分別為“1、2、3、4”,則壓縮后的數(shù)據(jù)格式如圖3所示。?

?

?

?

　　半字節(jié)壓縮中需要解決的首要問(wèn)題是壓縮對(duì)象的計(jì)數(shù)問(wèn)題,解決此問(wèn)題的方法有兩種:一種是半字節(jié)計(jì)數(shù)器(Half-Byte Counter),另一種是全字節(jié)計(jì)數(shù)器(Full-Byte Counter)。不管那一種方法,它們都要占用字節(jié),再加上壓縮標(biāo)識(shí)也要占用字節(jié),所以要影響數(shù)據(jù)的壓縮比。改進(jìn)后的半字節(jié)壓縮算法完全解決了此問(wèn)題,因?yàn)镚PS定位數(shù)據(jù)經(jīng)過(guò)壓縮預(yù)處理后的數(shù)據(jù)長(zhǎng)度是固定的24個(gè)字節(jié)長(zhǎng),不是動(dòng)態(tài)可變的,所以不需要解決壓縮對(duì)象的計(jì)數(shù)問(wèn)題。一般來(lái)說(shuō),任何一種壓縮算法都需要用壓縮指示字符作為壓縮數(shù)據(jù)的標(biāo)識(shí),壓縮標(biāo)識(shí)符越短越好,因?yàn)檫^(guò)長(zhǎng)會(huì)影響壓縮效果。然而,由于GPS定位數(shù)據(jù)中的所有字符都進(jìn)行了編碼處理,不存在原樣字符(不進(jìn)行壓縮的字符,在解壓縮時(shí)原樣輸出),因此壓縮標(biāo)識(shí)完全可以省略,可進(jìn)一步提高數(shù)據(jù)的壓縮比。壓縮預(yù)處理程序框圖和改進(jìn)后的半字節(jié)壓縮算法框圖如圖4所示。?

?

?

　　壓縮文件包括解壓縮所需的重要信息,由釋放參照信息和依次壓縮了的定長(zhǎng)數(shù)據(jù)塊組成。釋放參照信息包含有解壓縮所要使用的時(shí)間基數(shù)信息,它通過(guò)語(yǔ)句計(jì)數(shù)器以及錯(cuò)誤代碼號(hào)可以將時(shí)間還原。除此之外,釋放參照信息還包括各個(gè)定長(zhǎng)數(shù)據(jù)塊在解壓縮時(shí)所需的共同信息,如E/W、N/S、日期,壓縮文件的格式如圖5所示。?

?

?

　　嵌入式系統(tǒng)的壓縮是不需要人為干涉、而自動(dòng)實(shí)時(shí)完成的,具體的實(shí)現(xiàn)方法是通過(guò)駐留內(nèi)存(單任務(wù)操作系統(tǒng)中,如DOS)或作為一個(gè)后臺(tái)任務(wù)(在多任務(wù)操作系統(tǒng)中,如Windows中)對(duì)數(shù)據(jù)完成實(shí)時(shí)壓縮或解壓縮。?

　　GPS定位數(shù)據(jù)的壓縮算法經(jīng)過(guò)實(shí)際的驗(yàn)證,壓縮比隨著壓縮數(shù)據(jù)的減小而略有減少,這是因?yàn)閰⒄招畔㈦S著壓縮數(shù)據(jù)的減小其所占的比例在逐漸增加的原故。但總的壓縮比不低于82%,達(dá)到了預(yù)期的效果,如表2所示。該壓縮方法在車載系統(tǒng)中使用不僅能節(jié)省存儲(chǔ)空間,而且能減少信道的占有時(shí)間及提高數(shù)據(jù)的安全性。由于壓縮程序是針對(duì)GPS數(shù)據(jù)格式編寫的,因此其壓縮比大但通用性不強(qiáng)。盡管如此,該程序略做修改可移植到其它系統(tǒng)中,因?yàn)楦鱾€(gè)GPS廠家所執(zhí)行的規(guī)范標(biāo)準(zhǔn)都是NMEA-0183,其數(shù)據(jù)的輸出格式略有差別。?

?

?

參考文獻(xiàn)?

1 楊宏業(yè)，張 躍，呂 芳.一種新的GPS出租車調(diào)度系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).電子技術(shù)應(yīng)用, 2002;28(6).?

2 袁 玫，袁 文.數(shù)據(jù)壓縮技術(shù)及其應(yīng)用.北京:電子工業(yè)出版社，1995.12?

3 黃 超， 周綺麗.智能遙測(cè)終端中壓縮數(shù)據(jù)的方法.測(cè)控技術(shù),1998(1)?

4 邵方武，張金標(biāo)，張麗萍.GPS定位信息的計(jì)算機(jī)顯示.天津理工學(xué)院學(xué)報(bào), 1996(9)