0 引言

　　傳統(tǒng)的ARC算法雖然已經(jīng)在遙測數(shù)據(jù)上實(shí)現(xiàn)了無損壓縮，但其運(yùn)算極其復(fù)雜，而且ARC算法特別依賴信源統(tǒng)計(jì)的模型，更重要的是要預(yù)先知道信源的概率分布必須通過大量的測試與分析，因此ARC算法用硬件實(shí)現(xiàn)起來仍然比較困難[1]。相對而言，LZW編碼簡單，壓縮/解壓速度快，壓縮效果比較好，適用廣、易于軟硬件實(shí)現(xiàn)，適合實(shí)時(shí)壓縮。

　　為了使LZW算法易于在遙測硬件壓縮系統(tǒng)上實(shí)現(xiàn)，利用MATLAB仿真找出傳統(tǒng)LZW壓縮算法的不足與優(yōu)化方向，從LZW壓縮算法的字典空間設(shè)置、查表方式設(shè)計(jì)、字典更新方法等方面改進(jìn)算法的壓縮性能。尤其使用了多次散列的查表方法，并通過MATLAB仿真確定了最終采用的散列次數(shù)，極大地提高了壓縮算法的執(zhí)行速率。同時(shí)，根據(jù)字典使用的特點(diǎn)，簡化了字典的結(jié)構(gòu)，節(jié)省了硬件資源。最后，通過采用刪除后續(xù)出現(xiàn)次數(shù)較少詞條的字典更新方法，提高了數(shù)據(jù)壓縮比。對壓縮后輸出的數(shù)據(jù)流進(jìn)行漢明碼校驗(yàn)，提高了系統(tǒng)可靠性。

1 LZW算法的選擇

　　1.1 遙測數(shù)據(jù)壓縮的可行性

　　遙測數(shù)據(jù)中模擬量參數(shù)根據(jù)參數(shù)的頻帶范圍可分為緩變參數(shù)和速變參數(shù)，緩變參數(shù)的頻帶范圍為0～10 Hz，速變參數(shù)頻帶范圍為10～8 000 Hz。通常情況下速變參數(shù)的采樣率遠(yuǎn)大于緩變參數(shù)，而且速變參數(shù)采集量也遠(yuǎn)大于緩變參數(shù)的量。實(shí)測表明，速變參數(shù)傳輸通道約占系統(tǒng)通道總量的10%，但采集的數(shù)據(jù)卻占總數(shù)據(jù)量的80%左右。對速變參數(shù)的實(shí)測結(jié)果表明，速變參數(shù)具有“短期活躍，長期穩(wěn)定”的特點(diǎn)，其活躍期占飛行過程不到20%，并分散在整個(gè)飛行過程中，這說明遙測數(shù)據(jù)中的速變參量存在較大的壓縮空間[2-3]。

　　圖1為一組遙測數(shù)據(jù)的波形及相應(yīng)波形的概率分布。圖1(a)為隨機(jī)抽取的4 500個(gè)字節(jié)經(jīng)MATLAB繪制出的波形圖，圖1(b)為與波形圖相對應(yīng)的概率分布圖。從圖中可以看出，這組隨機(jī)抽取的遙測數(shù)據(jù)在100～150之間出現(xiàn)的概率最大且為非等概率分布，具有一定的壓縮空間。

　　1.2 3種壓縮算法的比較

　　在采集遙測數(shù)據(jù)的壓縮系統(tǒng)工作條件下，衡量是否適合遙測硬件系統(tǒng)壓縮編碼應(yīng)根據(jù)以下3點(diǎn)：

　　(1)壓損比，壓縮比與采用的算法有直接關(guān)系，而遙測數(shù)據(jù)屬于非等概率分布相似度小，故不適合算術(shù)編碼。壓縮比定義如式(1)，m表示變量個(gè)數(shù)，L表示編碼的平均長度，CR表示數(shù)據(jù)壓縮比：

　　從式(1)中可以看出，變量個(gè)數(shù)越多，壓縮比相對也會(huì)越大，但霍夫曼壓縮編碼不適合處理大批量的數(shù)據(jù)壓縮[4]。

　　(2)信源，遙測數(shù)據(jù)不僅包含圖像數(shù)據(jù)，還包含各種工況信息，例如：工作電壓參數(shù)、沖擊量、環(huán)境溫度等，而行程編碼適合圖像數(shù)據(jù)的有損壓縮，不適合遙測數(shù)據(jù)的無損壓縮[5]。

　　(3)復(fù)雜度，ARC算術(shù)編碼運(yùn)算非常復(fù)雜，這額外增加了硬件的成本開銷[6]。

　　綜上3點(diǎn)所述，LZW不僅適合處理大批量數(shù)據(jù)，而且無需知道信源的數(shù)據(jù)模型，運(yùn)算簡單，適合實(shí)時(shí)壓縮。因此從硬件上考慮，選擇LZW壓縮算法作為遙測硬件壓縮系統(tǒng)的核心算法是最好的選擇。

2 LZW算法的優(yōu)化設(shè)計(jì)

　　為了使LZW算法更適用于遙測硬件上，通過對遙測數(shù)據(jù)的科學(xué)分析及軟件仿真分別從字典大小、查找方式、字典更新方法三個(gè)方面對LZW算法進(jìn)行優(yōu)化設(shè)計(jì)。

　　2.1 字典大小的優(yōu)化設(shè)計(jì)

　　本設(shè)計(jì)采用的FPGA為XC3S1400AN，其內(nèi)部可使用的RAM為72K×8bit=576 Kbit，為了縮小硬件系統(tǒng)的尺寸，通過FPGA內(nèi)部給字典分配的空間，考慮到整個(gè)系統(tǒng)的工作量，可為字典分配的空間為2K，4K，6K，8K，16K，32K。通過軟件實(shí)驗(yàn)分析結(jié)果繪制的曲線圖如圖2所示，從圖中可以看出，分配空間為2K～4K時(shí)壓縮比有明顯的變化，而超過4K后壓縮比變化較平緩。采用母節(jié)點(diǎn)、目錄、字符結(jié)構(gòu)的字典方案，4K的字典所需的空間為2×4K×12 bit+4K×8 bit=128 Kbit。綜合考慮，給字典分配的空間為4K。

　　2.2 查找方式的優(yōu)化設(shè)計(jì)

　　LZW算法的關(guān)鍵在于字典的檢索，這一步驟關(guān)系到整個(gè)壓縮算法的執(zhí)行速率和壓縮效果，目前較為有效的檢索方法是構(gòu)建散列表。合適的散列函數(shù)可使散列值均勻分布，通過散列值可快速查找記錄，從而縮小檢索時(shí)間。

　　查找字典的方式對數(shù)據(jù)壓縮的速率影響很大。字典空間長度為4K，若只采用順序查表，在最壞的情況下處理4 KB的數(shù)據(jù)需查找4 096×4 097/2=8 390 656的數(shù)據(jù)長度。遙測系統(tǒng)晶振以100 MHz為例，查找一個(gè)詞條一般需4個(gè)系統(tǒng)時(shí)鐘周期，字典填滿后若清空，則還需要(4 096-256)×4個(gè)時(shí)鐘周期，所以極端情況下處理4K數(shù)據(jù)用時(shí)約為：[4 096×4 097/2+（4 096-256）×4]×10 ns≈335.78 ms，轉(zhuǎn)換成速率約為11.91 KB/s，而壓縮系統(tǒng)要求對遙測信號的采樣率192 KB/s遠(yuǎn)高于該速率，顯然只采用順序查表的查字典方式的壓縮算法不能滿足遙測硬件實(shí)時(shí)壓縮的需求。

　　只采用順序查表的方法已經(jīng)不能滿足要求，而采用一次散列很難找到合適的散列函數(shù)使散列值非常發(fā)散。為了加快查字典的速度，保證壓縮速度，考慮采用多次散列法。利用MATAB軟件對采用不同次數(shù)散列的壓縮算法進(jìn)行測試，結(jié)果統(tǒng)計(jì)繪制的曲線圖如圖3所示。為了測試結(jié)果更準(zhǔn)確，每種查表方式都經(jīng)過多次測試后取平均壓縮時(shí)間。為了更客觀地分析測試結(jié)果，在相同條件下加入了隨機(jī)數(shù)據(jù)壓縮結(jié)果作為參考標(biāo)準(zhǔn)，圖中虛線表示隨機(jī)數(shù)據(jù)壓縮時(shí)間與散列次數(shù)的關(guān)系，實(shí)線表示實(shí)測遙測數(shù)據(jù)壓縮時(shí)間與散列次數(shù)的關(guān)系。從圖中客觀的分析可知，散列次數(shù)在15次以上時(shí)，壓縮時(shí)間大幅度縮短；散列次數(shù)在15～40之間時(shí)，壓縮時(shí)間雖稍有縮短，但有波動(dòng)?？傊?，散列次數(shù)并不是越多越好。根據(jù)遙測數(shù)據(jù)壓縮曲線圖，本設(shè)計(jì)選擇散列次數(shù)為25次。

　　仿真時(shí)鐘周期為10 ns(100 MHz時(shí)鐘)時(shí)，通過仿真可計(jì)算出硬件程序壓縮64 KB遙測數(shù)據(jù)理論用時(shí)24.785 ms，平均處理速率約為2 582 KB/s，壓縮64 KB的隨機(jī)數(shù)據(jù)用時(shí)83.624 ms，平均處理速率約為765 KB/s。由于這兩個(gè)速率都遠(yuǎn)大于對遙測數(shù)據(jù)的采集速率192 KB/s，所以25次散列完全可以滿足壓縮系統(tǒng)的硬件要求。

　　2.3 字典更新方式的優(yōu)化設(shè)計(jì)

　　為了調(diào)試出易于硬件設(shè)計(jì)的字典更新方式，利用MATLAB繪制出了當(dāng)字典首次填滿時(shí)各詞條的使用情況，結(jié)果如圖4所示。經(jīng)統(tǒng)計(jì)分析可知，除去字典前256個(gè)位置引用次數(shù)為0的詞條數(shù)為2 529，占總詞條數(shù)(4 096)的61.74%。因此可從引用次數(shù)為0的詞條進(jìn)行優(yōu)化設(shè)計(jì)：每次字典寫滿后，保留被引用次數(shù)大于0而刪除被引用次數(shù)為0或引用次數(shù)最少的詞條，然后繼續(xù)添加新的詞條直到再次填滿字典空間，以此進(jìn)行循環(huán)更新。

　　通過軟件仿真將3種傳統(tǒng)的字典更新方式與優(yōu)化后的字典更新方式進(jìn)行壓縮效果對比，得到表1的數(shù)據(jù)結(jié)果。從表中數(shù)據(jù)不難看出，優(yōu)化后的設(shè)計(jì)壓縮時(shí)間明顯增加很多，但數(shù)據(jù)的壓縮比同樣得到明顯的提高。

　　為了驗(yàn)證優(yōu)化后的設(shè)計(jì)易于硬件壓縮系統(tǒng)的實(shí)現(xiàn)，將優(yōu)化后的設(shè)計(jì)應(yīng)用在FPGA的壓縮模塊中，系統(tǒng)時(shí)鐘為100 MHz，經(jīng)軟件仿真得出壓縮64 KB遙測數(shù)據(jù)用時(shí)77.159 ms，平均壓縮速率約為830 KB/s；壓縮64 KB隨機(jī)數(shù)據(jù)的時(shí)間為152.580 ms，平均壓縮速率約為419 KB/s。因這兩個(gè)壓縮速率遠(yuǎn)大于遙測數(shù)據(jù)的輸入速率192 KB/s，所以優(yōu)化后的方法可以應(yīng)用于遙測壓縮系統(tǒng)的硬件設(shè)計(jì)中。

3 邏輯功能的實(shí)現(xiàn)

　　本設(shè)計(jì)的LZW壓縮算法的數(shù)據(jù)結(jié)構(gòu)由傳統(tǒng)的三部分構(gòu)成：母節(jié)點(diǎn)（parent）、目錄（index）和字符（symbol）。首先，根據(jù)FPGA并行執(zhí)行的特點(diǎn)，配置3個(gè)RAM塊分別存儲字典的三個(gè)部分，并用統(tǒng)一的地址進(jìn)行讀/寫操作，頂層圖如圖5所示。

　　用硬件邏輯語言實(shí)現(xiàn)優(yōu)化后的LZW算法，具體的流程圖如圖6所示。I表示經(jīng)過壓縮處理的數(shù)據(jù)串，X表示采集到的數(shù)據(jù)，P表示檢索指針。優(yōu)化后的LZW算法壓縮過程為：

　　(1)逐一輸入數(shù)據(jù)累積成I；

　　(2)取下一個(gè)數(shù)據(jù)x；

　　(3)在字典中檢索數(shù)據(jù)串Ix。若數(shù)據(jù)串Ix在字典中，則檢索成功，置I為檢索地址并輸入下一個(gè)要壓縮的數(shù)據(jù)x；如果數(shù)據(jù)串Ix不在字典中，則檢索失敗，輸出I在字典中的存儲指針，然后在字典中存儲Ix，設(shè)字典指針為p，最后置I=x并輸入下一個(gè)要壓縮的數(shù)據(jù)x；

　　(4)判斷字典是否已滿，滿了即將字典清空。

4 結(jié)果分析

　　結(jié)合shannon信息論可知，信源各符號間若相互獨(dú)立，則信源為等概率分布時(shí)其熵值最大，冗余度為零，因此無損壓縮的本質(zhì)可以理解為：使信源趨于等概率分布，降低信源的冗余度。由此理論分析，從概率上來看數(shù)據(jù)壓縮后與壓縮前相比概率分布圖應(yīng)更為平穩(wěn)、均勻。為保持結(jié)論的客觀性，將優(yōu)化后的LZW壓縮算法應(yīng)用在硬件系統(tǒng)中，將前文隨機(jī)抽取的遙測數(shù)據(jù)進(jìn)行壓縮對比，同樣利用MATLAB軟件畫出壓縮后的波形圖與概率分布圖，結(jié)果如圖7所示。經(jīng)對比可知，經(jīng)壓縮后的遙測數(shù)據(jù)概率分布呈現(xiàn)出明顯的平滑曲線，同時(shí)表明，數(shù)據(jù)的冗余度明顯降低，可壓縮空間更是接近于極限。最終壓縮比為1.832:1。

　　本設(shè)計(jì)沒有從優(yōu)化LZW壓縮算法的數(shù)據(jù)結(jié)構(gòu)入手，而且最終優(yōu)化的結(jié)果僅適用于遙測硬件數(shù)據(jù)壓縮系統(tǒng)，因此該設(shè)計(jì)存在局限性，仍然有很大的提升空間。

　參考文獻(xiàn)

　　[1] 凌偉.基于ARC算法的數(shù)據(jù)壓縮技術(shù)與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2013(8)：84-87.

　　[2] 劉文怡.遙測速變數(shù)據(jù)無損壓縮時(shí)空性能優(yōu)化設(shè)計(jì)及應(yīng)用[D].太原：中北大學(xué)，2009.

　　[3] 劉鑫.基于遙測數(shù)據(jù)的壓縮算法設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2008，34(11)：79-81.

　　[4] 葉芝慧，沈克勤.信息論與編碼[M].北京：電子工業(yè)出版社，2011.

　　[5] 陳昌主.數(shù)據(jù)壓縮算法研究與設(shè)計(jì)[D].長沙：中南大學(xué)，2010.

　　[6] 曾尚春.SAR數(shù)據(jù)壓縮算法研究[D].南京：南京航空航天大學(xué)，2007.