0 引言

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

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

1 LZW算法的選擇

　　1.1 遙測數據壓縮的可行性

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

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

　　1.2 3種壓縮算法的比較

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

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

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

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

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

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

2 LZW算法的優化設計

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

　　2.1 字典大小的優化設計

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

　　2.2 查找方式的優化設計

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

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

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

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

　　2.3 字典更新方式的優化設計

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

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

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

3 邏輯功能的實現

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

　　用硬件邏輯語言實現優化后的LZW算法，具體的流程圖如圖6所示。I表示經過壓縮處理的數據串，X表示采集到的數據，P表示檢索指針。優化后的LZW算法壓縮過程為：

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

　　(2)取下一個數據x；

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

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

4 結果分析

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

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

　參考文獻

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

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

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

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

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

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