0 引言

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

　　為了使LZW算法易于在遙測硬件壓縮系統(tǒng)上實現(xiàn)，利用MATLAB仿真找出傳統(tǒng)LZW壓縮算法的不足與優(yōu)化方向，從LZW壓縮算法的字典空間設置、查表方式設計、字典更新方法等方面改進算法的壓縮性能。尤其使用了多次散列的查表方法，并通過MATLAB仿真確定了最終采用的散列次數(shù)，極大地提高了壓縮算法的執(zhí)行速率。同時，根據(jù)字典使用的特點，簡化了字典的結構，節(jié)省了硬件資源。最后，通過采用刪除后續(xù)出現(xiàn)次數(shù)較少詞條的字典更新方法，提高了數(shù)據(jù)壓縮比。對壓縮后輸出的數(shù)據(jù)流進行漢明碼校驗，提高了系統(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ù)的采樣率遠大于緩變參數(shù)，而且速變參數(shù)采集量也遠大于緩變參數(shù)的量。實測表明，速變參數(shù)傳輸通道約占系統(tǒng)通道總量的10%，但采集的數(shù)據(jù)卻占總數(shù)據(jù)量的80%左右。對速變參數(shù)的實測結果表明，速變參數(shù)具有“短期活躍，長期穩(wěn)定”的特點，其活躍期占飛行過程不到20%，并分散在整個飛行過程中，這說明遙測數(shù)據(jù)中的速變參量存在較大的壓縮空間[2-3]。

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

　　1.2 3種壓縮算法的比較

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

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

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

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

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

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

2 LZW算法的優(yōu)化設計

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

　　2.1 字典大小的優(yōu)化設計

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

　　2.2 查找方式的優(yōu)化設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結果分析

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

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

　參考文獻

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

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

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

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

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

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