- 相關(guān)推薦
GPS定位數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)
摘要：為了解決嵌入式GPS車載系統(tǒng)存儲(chǔ)空間小、GPS定位數(shù)據(jù)量大的矛盾，根據(jù)GPS定位數(shù)據(jù)的特點(diǎn)，提出了專用于GPS定全數(shù)據(jù)壓縮的改進(jìn)型半字節(jié)壓縮算法。該算法是一種在原半字節(jié)壓縮算法的基礎(chǔ)上改進(jìn)的算法，經(jīng)過(guò)實(shí)際測(cè)試，壓縮比可達(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)的軟件產(chǎn)品時(shí)必須將軟件所占的存儲(chǔ)空間限制在一定的范圍內(nèi)。
在GPS車載系統(tǒng)的研發(fā)過(guò)程中，(范文先生網(wǎng)325224.com收集整理)主要需解決的問(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)行壓縮。數(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í)行必須人為干擾，不能自動(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í)間、糾度、面速度信息，因而可以只選用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
由此可見(jiàn)，從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ù)處理：
①語(yǔ)句標(biāo)識(shí)頭（ID）：因?yàn)槊總�(gè)語(yǔ)句的標(biāo)識(shí)頭都一樣，所以該記錄段屬地冗余信息，完全可以去除，在解壓縮時(shí)再在每個(gè)語(yǔ)句前加上該標(biāo)識(shí)頭即可。
②世界時(shí)間（UTC）：該信息段以時(shí)、分、秒、毫秒的格式指示出當(dāng)時(shí)世界時(shí)間。轉(zhuǎn)換為北京時(shí)間還需要再加上8小時(shí)。由于車載系統(tǒng)的定位數(shù)據(jù)的采集是以秒為單位的，所以毫秒量級(jí)的數(shù)據(jù)對(duì)本系統(tǒng)根本無(wú)用，是冗余信息，由于世界時(shí)間是按秒增1，定位數(shù)據(jù)也是每委員長(zhǎng)更新一次，所以世界時(shí)間可以在程序的一開始采集記錄一下，在解壓縮時(shí)根據(jù)語(yǔ)句的指針值再加上起始時(shí)間便可以復(fù)原，因此該記錄段在第一次存儲(chǔ)后，以后的語(yǔ)句中的該信息全都是冗余信息。
③定位狀態(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ù)處理。
⑤緯度：占用10個(gè)字節(jié)，不進(jìn)行預(yù)處理。
⑥經(jīng)度指示器（E/W）：占一個(gè)字節(jié)，它指示出經(jīng)度是東經(jīng)，還是匹配。由于各個(gè)$GPRMC語(yǔ)句中的該段信息在中國(guó)都是東徑，它是冗余信息，因此也采取程序一開始存儲(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ù)編碼和字節(jié)壓縮方法等。它們均是無(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è)字節(jié)的八位編碼可壓縮為四位編碼，壓縮比理論上可趨近50%。
從圖1中可以看出，經(jīng)過(guò)預(yù)處理后的數(shù)據(jù)中，包含的文本字節(jié)有：“0～9”十個(gè)數(shù)字符號(hào)，“A”、“V”兩個(gè)英文大寫字母和一個(gè)小數(shù)點(diǎn)“.”符號(hào)，共13個(gè)字符�！癆”、“V”、“.”的ASCII碼的高四位顯然與數(shù)字字節(jié)的不一樣，半字節(jié)壓縮方法不能簡(jiǎn)單套用。然而，我們知道四位二進(jìn)制編碼可區(qū)分16種狀態(tài)，用來(lái)表示13種不同的字符是足夠的。
壓縮數(shù)據(jù)編碼表如表1的慰，為了充分利用編碼表中的狀態(tài)，在原來(lái)13個(gè)字節(jié)的基礎(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”字節(jié)。在以后解壓縮時(shí)，若檢測(cè)到“A”、“V”字節(jié)，時(shí)間的還原按正常的算法進(jìn)行；若檢測(cè)到“B”、“W”字符時(shí)，進(jìn)行的還原除了按正常的算法進(jìn)行以外還要加上秒鐘，這樣才能確保時(shí)間能夠正確的恢復(fù)，這是因?yàn)椤癇”、"W"字節(jié)表示上一條語(yǔ)句發(fā)生錯(cuò)誤已經(jīng)被丟棄，語(yǔ)句的壓縮是非連續(xù)的，有繼句現(xiàn)象發(fā)生。
表1 壓縮數(shù)據(jù)編碼表
1
2
3
4
5
6
7
8
9
.
A
B
V
W 00110000
00110001
00110010
00110011
00110100
00110101
00110110
00110111
00111000
00111001
00101110
01000001
01000010
01010110
01010111 0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1101
1100
1110
定位有效
定位有效，秒值1
定位無(wú)效
定位無(wú)效，秒增1
通過(guò)此編碼表進(jìn)行轉(zhuǎn)換后，原來(lái)經(jīng)過(guò)壓縮預(yù)處理后的固定24個(gè)字節(jié)第的文本數(shù)據(jù)就可以減小一半（壓縮后為固定的12個(gè)字節(jié)長(zhǎng)），壓縮比為50%，若從未經(jīng)過(guò)預(yù)處理的文本數(shù)據(jù)算起，則壓縮比可達(dá)到80%。
由圖2可知，實(shí)現(xiàn)半字節(jié)壓縮算法需要解決兩上問(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è)字節(jié)分別為“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所示。
壓縮文件包括解壓縮所需的重要信息，由釋放參數(shù)信息和依次壓縮了的定長(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)中，如DSP）或作為一個(gè)后臺(tái)任務(wù)（在多任務(wù)操作系統(tǒng)中，如Windows中）對(duì)數(shù)據(jù)完成實(shí)時(shí)壓縮或解壓縮。
表2 改進(jìn)型半字節(jié)壓縮算法的測(cè)試結(jié)果
文件大小（B） 預(yù)處理后 改進(jìn)型半字節(jié)壓縮 壓縮比
1035k=69×15000
103.5k=69×1500
10.36k=69×150
36KB+23B
3.6KB+23B 180KB+23B
18KB+23B
1.8KB+23B 0.8260
0.8259
0.8239
GPS定位數(shù)據(jù)的壓縮算法經(jīng)過(guò)實(shí)際的驗(yàn)證，壓縮比隨著壓縮數(shù)據(jù)的減小而略有減少，這是因?yàn)閰⒄招畔㈦S著壓縮數(shù)據(jù)的減小其所占的比例在逐漸增加的原故。但示，該壓縮方法在車載系統(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)都是GPS廠家所執(zhí)行的規(guī)范標(biāo)準(zhǔn)都是NMEA-0183，其數(shù)據(jù)的輸出格式略有差別。
【GPS定位數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)】相關(guān)文章：
車載GPS智能終端的設(shè)計(jì)與實(shí)現(xiàn)08-06
GPS高精度的時(shí)鐘的設(shè)計(jì)和實(shí)現(xiàn)08-06
DES算法實(shí)現(xiàn)過(guò)程分析08-06
計(jì)算法簡(jiǎn)單實(shí)現(xiàn)crc校驗(yàn)08-06
3-DES算法的FPGA高速實(shí)現(xiàn)08-06
固定幾何結(jié)構(gòu)的FFT算法及其FPGA實(shí)現(xiàn)08-06
基于GPS的時(shí)標(biāo)系統(tǒng)實(shí)現(xiàn)方法探究08-06