- 相關(guān)推薦
GPS定位數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)
摘要：為了解決嵌入式GPS車載系統(tǒng)存儲空間小、GPS定位數(shù)據(jù)量大的矛盾，根據(jù)GPS定位數(shù)據(jù)的特點(diǎn)，提出了專用于GPS定全數(shù)據(jù)壓縮的改進(jìn)型半字節(jié)壓縮算法。該算法是一種在原半字節(jié)壓縮算法的基礎(chǔ)上改進(jìn)的算法，經(jīng)過實(shí)際測試，壓縮比可達(dá)50%。若將壓縮預(yù)處理也折算法在內(nèi)，總壓縮比可達(dá)80%以上，為車載系統(tǒng)節(jié)省了大量的存儲資源。除此之外，也縮短了GSM信道的占用時(shí)間，大大地緩解了向控制調(diào)度中心上傳數(shù)據(jù)的壓力。關(guān)鍵詞：數(shù)據(jù)壓縮 GPS數(shù)據(jù)格式 壓縮預(yù)處理 半字節(jié)壓縮算法
嵌入式GPS車載系統(tǒng)般體積較小，無存儲量大的硬盤等設(shè)備，系統(tǒng)程序、應(yīng)用程序一般裝在FLASH或ROM中。由于FLASH或ROM等存儲介質(zhì)的價(jià)格相對臺式機(jī)上廣泛使用的硬盤、光盤等來說是非常昂貴的，因此，在開發(fā)嵌入式系統(tǒng)的軟件產(chǎn)品時(shí)必須將軟件所占的存儲空間限制在一定的范圍內(nèi)。
在GPS車載系統(tǒng)的研發(fā)過程中，(范文先生網(wǎng)m.panasonaic.com收集整理)主要需解決的問題是：車載系統(tǒng)為了實(shí)現(xiàn)自導(dǎo)航，必須存儲大量的GPS定位數(shù)據(jù)（每天需要存儲約6MB）；其二是這些數(shù)據(jù)還要通過GSM信道上傳到控制調(diào)度中心（若通過短信業(yè)務(wù)發(fā)送，每次160B，則需要每分上傳6次）。無疑，數(shù)據(jù)壓縮是在不增加硬件成本的前提下，從軟件的角度來充分發(fā)揮系統(tǒng)現(xiàn)有資源的有效辦法。
數(shù)據(jù)壓縮方法種類繁多，可以分為無損壓縮和有損壓縮兩大類。無損壓縮利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮。數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，般為2：1到5：1。這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場合的圖像數(shù)據(jù)（如指紋圖像、醫(yī)學(xué)圖像等）的壓縮。有損壓縮方法利用了人類視覺對圖像中的某些頻率成分不敏感的特性，允許壓縮過程中的損失一定的信息。雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響較小，卻換來了大得多的壓縮比。有損壓縮廣泛應(yīng)用于語音、圖像和視頻數(shù)據(jù)的壓縮。
目前現(xiàn)在的壓縮算法很多，但不能直接用于嵌入式系統(tǒng)當(dāng)中，這完全由嵌入式系統(tǒng)的特點(diǎn)所決定。首先，用于嵌入式系統(tǒng)的數(shù)據(jù)壓縮方法應(yīng)是無損壓縮方法。其次，壓縮代碼和解碼所需的信息代碼必須足夠短，否則就會失去壓縮的意義。還有，嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須結(jié)合具體的數(shù)據(jù)格式的特點(diǎn)，才能進(jìn)一步提高數(shù)據(jù)的壓縮比。除此之外，目前的壓縮程序的啟動執(zhí)行必須人為干擾，不能自動執(zhí)行，因?yàn)樗鼈兪菫槲募到y(tǒng)設(shè)計(jì)的，而嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須能夠自動執(zhí)行。
1 GPS數(shù)據(jù)格式
GPS OEM板由變頻器、信號通道、微處理器和存儲單元等組成。GPS OEM板的型號甚多，性能各異，但大多采用美國國家海洋電子協(xié)會制定的NMEA-0183通信標(biāo)準(zhǔn)格式。本系統(tǒng)選擇的是美國SiRF公司的SiRFstarII OEM板。SiRFstarII OEM板語句的輸入、輸出是通過RS232串行接口完成的，其通信端口的數(shù)據(jù)格式應(yīng)該設(shè)置為8個(gè)數(shù)據(jù)位、1個(gè)起始位和1個(gè)停止位，校驗(yàn)方式選為無奇偶校驗(yàn)，波特率設(shè)置為4800波特。NMEA-0183通信標(biāo)準(zhǔn)的輸出數(shù)據(jù)采用的是ASCII碼，其內(nèi)容包含了緯度、經(jīng)度、高度、速度、日期、時(shí)間、航向以及衛(wèi)星狀況等信息，語句有六種，包括GGA，GLL、GSA、GSV、RMC和VTG。對于不同的用途，選用的語句記錄也不同，例如嵌入式GPS車載系統(tǒng)的使用者只關(guān)心其日期和時(shí)間、糾度、面速度信息，因而可以只選用RMC記錄語句。一條$GPRMC語句包括13個(gè)記錄：語句標(biāo)識頭、世界時(shí)間、定位狀態(tài)、緯度、緯度方位、經(jīng)度、經(jīng)度方位、地面速度、地面路線、日期、磁偏角、校驗(yàn)和和結(jié)束標(biāo)記，它一共占用70個(gè)字節(jié)（其中還包括用于分隔記錄所使用的11個(gè)逗號），例如：
$GPRMC,121530.998,A,4000.0162,N,11619.5476,E,0.00,240.81,160102,,*3B
由此可見，從SiRFstarII OEM板接收下來的數(shù)據(jù)流是文本字符串，根據(jù)GPS數(shù)據(jù)格式的特點(diǎn)，本設(shè)計(jì)中擬采用半字節(jié)法完成壓縮及解壓縮的任務(wù)。該方法屬于無損壓縮技術(shù)，其原理是去除字節(jié)中的冗余位，從而達(dá)到壓縮目的。然而，這種方法只適用于純數(shù)字文本文件的壓縮，顯然GPS定位數(shù)據(jù)并不是純數(shù)字的，還必須在壓縮前進(jìn)行一下壓縮預(yù)處理，最后再利用半字節(jié)壓縮算法完成數(shù)據(jù)的壓縮。
2 壓縮預(yù)處理
仔細(xì)觀察以上各段數(shù)據(jù)記錄，可以發(fā)現(xiàn)語句之間的數(shù)據(jù)段還存在很多冗余。除此之外，這些記錄中所含的信息既有英文字符又有數(shù)字，為了后續(xù)的壓縮，對語句中的各個(gè)記錄應(yīng)做如下的預(yù)處理：
①語句標(biāo)識頭（ID）：因?yàn)槊總�(gè)語句的標(biāo)識頭都一樣，所以該記錄段屬地冗余信息，完全可以去除，在解壓縮時(shí)再在每個(gè)語句前加上該標(biāo)識頭即可。
②世界時(shí)間（UTC）：該信息段以時(shí)、分、秒、毫秒的格式指示出當(dāng)時(shí)世界時(shí)間。轉(zhuǎn)換為北京時(shí)間還需要再加上8小時(shí)。由于車載系統(tǒng)的定位數(shù)據(jù)的采集是以秒為單位的，所以毫秒量級的數(shù)據(jù)對本系統(tǒng)根本無用，是冗余信息，由于世界時(shí)間是按秒增1，定位數(shù)據(jù)也是每委員長更新一次，所以世界時(shí)間可以在程序的一開始采集記錄一下，在解壓縮時(shí)根據(jù)語句的指針值再加上起始時(shí)間便可以復(fù)原，因此該記錄段在第一次存儲后，以后的語句中的該信息全都是冗余信息。
③定位狀態(tài)（A/V）：占用1個(gè)字節(jié)，不進(jìn)行預(yù)處理。由于車載系統(tǒng)處于的地方有可能收不到衛(wèi)星信號（如隧道中），致使定位信息無效，因此盡管該字段發(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語句中的該段信息在中國都是東徑，它是冗余信息，因此也采取程序一開始存儲一次的方法。
⑦緯度指示器（N/S）：占一個(gè)字節(jié)，各個(gè)$GPRMC語句中的該段信息完全一樣，是冗余信息，處理方法與上相同。
⑧地面速度：占用4個(gè)字節(jié)，不進(jìn)行預(yù)處理。
⑨日期：占用6個(gè)字節(jié)，以日、月、年的格式顯示，各個(gè)$GPRMC語句中的該段信息在24小時(shí)內(nèi)完全一樣，是冗余信息，采取程序一開始存儲一次的方法，以后語句中的該段信息全部廢除。
⑩校驗(yàn)和：占用3個(gè)字節(jié)，該數(shù)據(jù)完成校驗(yàn)后便棄之，不保留和進(jìn)行壓縮。
結(jié)束符合占用2個(gè)字節(jié)，只用來判斷語句的有效數(shù)據(jù)范圍，其它記錄段與本系統(tǒng)的設(shè)計(jì)無關(guān)都不保留和進(jìn)行壓縮。
通過以上壓縮預(yù)處理后，保留了四個(gè)數(shù)據(jù)記錄，共占用24個(gè)字節(jié)，如圖1所示。
3 改進(jìn)型半字節(jié)壓縮算法
文本數(shù)據(jù)的壓縮的都是無損壓縮技術(shù)，即還原后的文件應(yīng)該與源文件完全相同。文本文件壓縮的方法有很多種，如HUFFMAN編碼、算術(shù)編碼和字節(jié)壓縮方法等。它們均是無損壓縮方法，都適用于文本數(shù)據(jù)的壓縮。半字節(jié)壓縮方法是針對文本數(shù)據(jù)的特點(diǎn)所設(shè)計(jì)的，主要是去除文本中的字節(jié)中的冗余位，從而達(dá)到減少數(shù)據(jù)文件所占用的存儲空間的目的。在數(shù)據(jù)壓縮技術(shù)中，除壓縮重復(fù)字符外，還可以根據(jù)數(shù)據(jù)本身的特點(diǎn)進(jìn)行壓縮。在計(jì)算機(jī)中，任何數(shù)據(jù)都是以某種代碼的方式存儲的。在些文件中，或許有一些代碼具有某些相似之處，我們可以根據(jù)代碼的特點(diǎn)進(jìn)行特定的操作，壓縮掉這些數(shù)據(jù)的相似部分，或者說壓縮掉這些數(shù)據(jù)的特征部分，半字節(jié)壓縮就是這樣一種方法。半字節(jié)方法主要用于純數(shù)字的文本文件的壓縮，因?yàn)閿?shù)字0～9的ASCII碼的高四位都一樣，是冗余的，因此每一個(gè)數(shù)字完全可以用低四位描述，即每個(gè)字節(jié)的八位編碼可壓縮為四位編碼，壓縮比理論上可趨近50%。
從圖1中可以看出，經(jīng)過預(yù)處理后的數(shù)據(jù)中，包含的文本字節(jié)有：“0～9”十個(gè)數(shù)字符號，“A”、“V”兩個(gè)英文大寫字母和一個(gè)小數(shù)點(diǎn)“.”符號，共13個(gè)字符。“A”、“V”、“.”的ASCII碼的高四位顯然與數(shù)字字節(jié)的不一樣，半字節(jié)壓縮方法不能簡單套用。然而，我們知道四位二進(jìn)制編碼可區(qū)分16種狀態(tài)，用來表示13種不同的字符是足夠的。
壓縮數(shù)據(jù)編碼表如表1的慰，為了充分利用編碼表中的狀態(tài)，在原來13個(gè)字節(jié)的基礎(chǔ)上又新增添了兩個(gè)字符“B”和“W”，其四位編碼分別為1101和1110。這兩個(gè)字符是在壓縮預(yù)處理過程中，用來記錄那些因語句校驗(yàn)和出錯(cuò)而舍棄的語句。因?yàn)槊織l語句的時(shí)間信息全部在預(yù)處理階段被舍棄，在解壓縮時(shí)要恢復(fù)時(shí)間值。該值在正常情況下是根據(jù)時(shí)間的基數(shù)再加上語句的計(jì)數(shù)值（由于每秒接受到一條語句，所以語句計(jì)數(shù)值就是以秒為單位的時(shí)間增量）確定的。當(dāng)發(fā)生語句校驗(yàn)和出錯(cuò)時(shí)，若處于定位有效狀態(tài)，則在定位狀態(tài)記錄上不填寫“A”字符，而填寫“B”字符；若處在定位無效狀態(tài)，則不填寫“V”字符，而填寫“W”字節(jié)。在以后解壓縮時(shí)，若檢測到“A”、“V”字節(jié)，時(shí)間的還原按正常的算法進(jìn)行；若檢測到“B”、“W”字符時(shí)，進(jìn)行的還原除了按正常的算法進(jìn)行以外還要加上秒鐘，這樣才能確保時(shí)間能夠正確的恢復(fù)，這是因?yàn)椤癇”、"W"字節(jié)表示上一條語句發(fā)生錯(cuò)誤已經(jīng)被丟棄，語句的壓縮是非連續(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
定位無效
定位無效，秒增1
通過此編碼表進(jìn)行轉(zhuǎn)換后，原來經(jīng)過壓縮預(yù)處理后的固定24個(gè)字節(jié)第的文本數(shù)據(jù)就可以減小一半（壓縮后為固定的12個(gè)字節(jié)長），壓縮比為50%，若從未經(jīng)過預(yù)處理的文本數(shù)據(jù)算起，則壓縮比可達(dá)到80%。
由圖2可知，實(shí)現(xiàn)半字節(jié)壓縮算法需要解決兩上問題：首先是壓縮對象的計(jì)數(shù)；其次是如何把兩個(gè)數(shù)字的低位合并到一個(gè)字節(jié)中。后一個(gè)問題只要規(guī)定好壓縮后的字節(jié)中奇數(shù)號字符的四位編碼與偶數(shù)號字符的四位編碼的存放次序即可，程序的實(shí)現(xiàn)非常簡單，在此我們規(guī)定編號是奇數(shù)的字符放在高四位，編號為偶數(shù)的字符的編碼放在低四位。假設(shè)壓縮前的數(shù)據(jù)流中的前四個(gè)字節(jié)分別為“1、2、3、4”,則壓縮后的數(shù)據(jù)格式如圖3所示。
半字節(jié)壓縮中需要解決的首要問題是壓縮對象的計(jì)數(shù)問題，解決此問題的方法有兩種：一種是半字節(jié)計(jì)數(shù)器（Half-Byte Counter），另一種是全字節(jié)計(jì)數(shù)器（Full-Byte Counter）。不管那一種方法，它們都要占用字節(jié)，再加上壓縮標(biāo)識也要占用字節(jié)，所以要影響數(shù)據(jù)的壓縮比。改進(jìn)后的半字節(jié)壓縮算法完全解決了此問題，因?yàn)镚PS定位數(shù)據(jù)經(jīng)過壓縮預(yù)處理后的數(shù)據(jù)長度是固定的24個(gè)字節(jié)長，不是動態(tài)可變的，所以不需要解決壓縮對象的計(jì)數(shù)問題。一般來說，任何一種壓縮算法都需要用壓縮指示字符作壓縮數(shù)據(jù)的標(biāo)識，壓縮標(biāo)識符越短越好，因?yàn)檫^長會影響縮效果。然而，由于GPS定位數(shù)據(jù)中的所有字符都進(jìn)行了編碼處理，不存在原樣字符（不進(jìn)行壓縮的字符，在解壓縮時(shí)原樣輸出），因此壓縮標(biāo)識完全可以省略，可進(jìn)一步提高數(shù)據(jù)的壓縮比。壓縮預(yù)處理程序框圖和改進(jìn)后的半字節(jié)壓縮算法框圖如圖4所示。
壓縮文件包括解壓縮所需的重要信息，由釋放參數(shù)信息和依次壓縮了的定長數(shù)據(jù)塊組成。釋放參照信息包含有解壓縮所要使用的時(shí)間基數(shù)信息，它通過語句計(jì)數(shù)器以及錯(cuò)誤代碼號可以將時(shí)間還原。除此之外，釋放參照信息還包括各個(gè)定長數(shù)據(jù)塊在解壓縮時(shí)所需的共同信息，如E/W、N/S、日期，壓縮文件的格式如圖5所示。
嵌入式系統(tǒng)的壓縮是不需要人為干涉、而自動實(shí)時(shí)完成的，具體的實(shí)現(xiàn)方法是通過駐留內(nèi)存（單任務(wù)操作系統(tǒng)中，如DSP）或作為一個(gè)后臺任務(wù)（在多任務(wù)操作系統(tǒng)中，如Windows中）對數(shù)據(jù)完成實(shí)時(shí)壓縮或解壓縮。
表2 改進(jìn)型半字節(jié)壓縮算法的測試結(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)過實(shí)際的驗(yàn)證，壓縮比隨著壓縮數(shù)據(jù)的減小而略有減少，這是因?yàn)閰⒄招畔㈦S著壓縮數(shù)據(jù)的減小其所占的比例在逐漸增加的原故。但示，該壓縮方法在車載系統(tǒng)中使用不僅能節(jié)省存儲空間，而且能減少信道占有時(shí)間及提高數(shù)據(jù)的安全性。由于壓縮程序是針對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
計(jì)算法簡單實(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