基于DSP的實(shí)時(shí)數(shù)據(jù)無(wú)損壓縮實(shí)現(xiàn)方案

2 算法的選擇

無(wú)損壓縮就是對(duì)信源信息進(jìn)行壓縮編碼后在解壓縮時(shí)能夠完全恢復(fù)，也即在壓縮和解壓縮過(guò)程中對(duì)信源信息沒(méi)有絲毫損失。常用的無(wú)損壓縮方法有Shannon- Fano編碼、Huffman編碼、游程(Run-length)編碼、LZW(Lempel-Ziv-Welch)編碼和算術(shù)編碼(ARC)等。對(duì)許多信息而言，沒(méi)必要完全保留全部特征。在允許一定精度損失的情況下，可以獲得更高的壓縮編碼效率。這類(lèi)壓縮編碼方法成為有損壓縮。本設(shè)計(jì)采用無(wú)損壓縮，不再討論有損壓縮。

無(wú)損數(shù)據(jù)壓縮算法可以分為統(tǒng)計(jì)方法和詞典編碼方法。統(tǒng)計(jì)方法當(dāng)以Huffman編碼和算術(shù)編碼(ARC)為代表。這種方法需要統(tǒng)計(jì)信源符號(hào)的概率分布情況，并根據(jù)統(tǒng)計(jì)結(jié)果產(chǎn)生壓縮碼。算術(shù)編碼是一種高效清除字串冗余的算法。仙儂信息論把字符aj出現(xiàn)的自信息量定義為I(aj)=-logpj I(aj)亦稱(chēng)自信息函數(shù)，其含義實(shí)際是隨機(jī)變量X取值為aj時(shí)所攜帶信息的度量。自信息量的概率平均值，即隨機(jī)變量I(aj) 的數(shù)學(xué)期望值，稱(chēng)做信息熵或簡(jiǎn)稱(chēng)熵。算術(shù)編碼從全序列出發(fā)，采用遞推形式連續(xù)編碼。它不是將單個(gè)的信源符號(hào)映射成一個(gè)碼字，而是將整個(gè)輸入符號(hào)序列映射為實(shí)數(shù)軸上[0，1)區(qū)間內(nèi)的一個(gè)小區(qū)間，其長(zhǎng)度等于該序列的概率，再在該小區(qū)間內(nèi)選擇一個(gè)有代表性的二進(jìn)制小數(shù)，而且是一個(gè)介于0和1之間的二進(jìn)制小數(shù)作為實(shí)際的編碼輸出，從而達(dá)到了高效編碼的目的。例如算術(shù)編碼對(duì)某條信息的輸出為1010001111，它表示小數(shù)0.1010001111，也即十進(jìn)制數(shù) 0.64。不論是否為二元信源，也不論數(shù)據(jù)的概率分布如何，其平均碼長(zhǎng)均能逼近信源的熵。算術(shù)編碼的過(guò)程實(shí)際上也就是信源編碼試圖將任意的信息流與0、1 之間的間隔建立一一對(duì)應(yīng)關(guān)系的過(guò)程。這樣要表示的信息流越長(zhǎng)，則表示它的間隔就越小，用于表示這一間隔所需的二進(jìn)制位就越多。

算術(shù)編碼在編碼前要求預(yù)先統(tǒng)計(jì)各信源符號(hào)概率，但無(wú)須排序，只要編、解碼端使用相同的符號(hào)順序即可。建立合理的信源概率模型是進(jìn)行算術(shù)編碼的關(guān)鍵。信源概率模型的建立方法一般有兩種：一種是自適應(yīng)的模型，是在不斷輸入信源的過(guò)程中對(duì)信源符號(hào)出現(xiàn)的概率進(jìn)行統(tǒng)計(jì)，模型是在編碼過(guò)程中逐步建立起來(lái)并不斷更新；另一種是事先統(tǒng)計(jì)的模型，是在編碼前就對(duì)所有輸入信源符號(hào)的出現(xiàn)頻率進(jìn)行事先統(tǒng)計(jì)，而編碼過(guò)程中模型不再改變?；趦煞N模型算法的不同之處：事先統(tǒng)計(jì)模型在編碼之前就己經(jīng)建立，編碼過(guò)程中不再更新，故壓縮效率與輸入字節(jié)數(shù)關(guān)系不大；而自適應(yīng)模型是在編碼過(guò)程中建立并不斷更新，當(dāng)輸入信源的數(shù)據(jù)量較大時(shí)，出現(xiàn)概率大的字符編碼位數(shù)較少的優(yōu)越性才能得以體現(xiàn)。在復(fù)雜度上，由于后者需要不斷對(duì)模型進(jìn)行更新，故運(yùn)算量較大。

詞典編碼方法則是基于數(shù)據(jù)中許多結(jié)構(gòu)頻繁重復(fù)再現(xiàn)這一事實(shí)，人們可以對(duì)相同符號(hào)串分配同一碼字、通過(guò)索引或者其他諸如此類(lèi)的方法編碼。LZW算法可以在對(duì)數(shù)據(jù)統(tǒng)計(jì)特性一無(wú)所知的前提下，使壓縮率接近己知統(tǒng)計(jì)特性時(shí)所能夠達(dá)到的壓縮率，其運(yùn)算速度快。LZW算法壓縮的原理在于用字典中詞條的編碼代替被壓縮數(shù)據(jù)中的字符串。字典中的詞條越長(zhǎng)越多，壓縮率就越高。所以加大字典的容量可以提高壓縮率。但從字典中查找詞條是算法中最費(fèi)時(shí)的工作，其字典的容量受到計(jì)算機(jī)內(nèi)存限制，且字典也存在被填滿(mǎn)的可能。當(dāng)字典不能再加入新詞條后，過(guò)老的字典就不能保證高的壓縮率。

不同的壓縮算法有不同的優(yōu)點(diǎn)和缺點(diǎn)，不同算法的復(fù)雜性對(duì)空間的要求及壓縮率也不同。壓縮算法不僅僅依賴(lài)于壓縮方法本身，也依賴(lài)于被壓縮文本的特點(diǎn)。在本文中，由于是對(duì)實(shí)時(shí)數(shù)據(jù)的壓縮，對(duì)壓縮過(guò)程的時(shí)間性能要求高，所以采用事先統(tǒng)計(jì)模型的ARC。實(shí)驗(yàn)證明，采用事先統(tǒng)計(jì)模型的ARC，其運(yùn)算速度與LZW算法速度相近。而ARC算法在壓縮速度和壓縮去除率上都優(yōu)于LZW算法。

3 實(shí)驗(yàn)與結(jié)果

在比較字典編碼LZW與算術(shù)編碼ARC時(shí)，從壓縮速度和壓縮去除率上進(jìn)行比較。前端以27Kb/s的速度實(shí)時(shí)采集8位的數(shù)據(jù)，數(shù)據(jù)壓縮后通過(guò)發(fā)送模塊以18Kb/s的速度數(shù)據(jù)傳到外界。對(duì)原始數(shù)據(jù)以2 048B作為分組長(zhǎng)度考察其壓縮去除率及壓縮時(shí)間。

壓縮去除率＝(原始數(shù)據(jù)量－壓縮后數(shù)據(jù)量)/原始數(shù)據(jù)量

這是從空間角度衡量。實(shí)際上，對(duì)壓縮效率而言還必須關(guān)注其時(shí)間效率，本文采用“壓縮速度”的概念，定義如下：

壓縮速度＝原始數(shù)據(jù)量/壓縮所需要的時(shí)間以2 048B的數(shù)據(jù)分組進(jìn)行分析：

1)從壓縮速度方面：完成2 048B的某噪聲數(shù)據(jù)，ARC算法需要5.64ms來(lái)完成，而LZW算法需要6.6ms，可見(jiàn)ARC算法的壓縮速度比較快。

(2)從壓縮效率方面：將某數(shù)據(jù)按照2 048B的長(zhǎng)度進(jìn)行分組并壓縮，從表1中可知ARC算法針對(duì)不同分組段的數(shù)據(jù)壓縮去除率恒定在78%左右，而LZW算法，在該分組段壓縮去除率僅為71%。可見(jiàn)該段數(shù)據(jù)ARC壓縮算法壓縮去除率比較高。

采用ARC算法后，通過(guò)大量的實(shí)驗(yàn)數(shù)據(jù)的平均壓縮去除率為79%，滿(mǎn)足系統(tǒng)所要求的數(shù)據(jù)壓縮去除率大于50%的要求。用ARC算法壓縮2 048B的數(shù)據(jù)需要5.64ms左右。數(shù)據(jù)不同，壓縮時(shí)間會(huì)有所不同。通過(guò)對(duì)控制軟件讀取的數(shù)據(jù)進(jìn)行解包、解壓，證明還原出來(lái)的數(shù)據(jù)與原始數(shù)據(jù)完全一致，實(shí)現(xiàn)了實(shí)時(shí)數(shù)據(jù)的無(wú)損壓縮。