0 引言

    遙測數據種類繁多、數量龐大，給遙測系統帶來了巨大的處理壓力，而遙測數據的冗余度也很大，統計表明標準遙測系統中傳輸的數據冗余度達到90%以上^[1]。為了降低信號空間，緩解數據處理壓力，在遙測系統中采用數據壓縮技術成為必然，而選擇一個好的數據壓縮算法，會起到事半功倍的效果。LZW壓縮算法以其編碼簡單、適用廣、易于軟硬件實現等特點成為數據壓縮算法的首選。但遙測數據數據量大，通用的LZW算法并不能取得良好的壓縮效果，其缺點在于傳統字典的更新方式和字典的查找方式影響數據的壓縮效果。針對存在的這些問題，本文提出了LZW算法的優化方法，并對優化算法進行驗證分析。實驗結果表明，該優化方法提高了系統的壓縮速率和壓縮比，達到遙測數據壓縮系統的指標要求。

1 LZW算法基礎理論

    LZW是一種基于字典編碼的算法。字典編碼就是把先輸入的“前文”編為字典，用來指代后輸入的重復的“下文”，減少重復性的輸出，從而達到數據壓縮的目的^[4]。LZW壓縮算法的基本原理：提取原始文本文件數據中的不同字符，基于這些字符創建一個字典，然后用字典中的字符的索引來替代原始文本文件數據中的相應字符，減少原始數據大小。但應該注意到，這里的字典不是事先創建好的，而是根據原始文件數據動態創建的，解碼時還要從已編碼的數據中還原出原來的字典[5]。其壓縮過程為編碼器逐個輸入字符并累積成一個字符串I，每個輸入字符x首先串接在I后面，然后在字典中重新查找字符串I，找到I則繼續取下一個字符串接在I后面繼續查找過程；否則將其存入字典，輸出指向I的指針，預置I為x，取下一個字符……。算法流程如圖1所示。

2 傳統LZW算法壓縮方法的分析

    假設母節點、索引、字符的長度都為 10 位，即檢索地址指針數據長度為 10 位，則字典節點的個數為 2¹⁰，稱這個字典的大小為 1 K。相對于壓縮數據量而言，字典的空間往往小得多，因為受硬件條件、算法復雜度和實現速度等因素的限制。通常由于壓縮數據任務較大，幾K大小的字典也很快會填滿，傳統LZW算法中當字典填滿時常采用以下處理方式：(1)停止更新字典。(2)將字典清空，用來重新更新。(3)引用次數少的刪除。

    而這三種方式會帶來如下影響：停止更新字典會使字典對之后的輸入數據失去適應性，從而導致壓縮效果差；由于字典由空至滿是字典慢慢適應輸入數據的過程，將字典清空，重新填寫會延長字典對被壓縮數據的適應時間，影響壓縮效果；刪除被引用次數為0或后續出現頻率較少的詞條，保留被引用次數大于0或后續出現頻率較高的詞條。雖然會提高壓縮比，但復雜的字典管理對硬件資源的占用和壓縮時間的消耗是得不償失的。

    傳統LZW算法中的查找字典的方式為順序查表。當需要處理的數據任務量大時，會導致生成的字典項較多，嚴重降低查找字典的速率。

    若只采用順序查表，取字典大小為4 K，則處理4 KB的數據的最大查找長度約為4 096×4 097/2=8 390 656。假設FPGA查找一個詞條需要4個系統時鐘周期，則最壞情況處理4 KB數據需要查找8 390 656×4=33 562 624個時鐘周期；字典填滿后若清空，以4個時鐘周期的單位清零為例，則還需要（4 096-256）×4個時鐘周期，總共用時33 577 984個時鐘周期。以100 MHz的時鐘為例，則系統處理4 KB數據的最大時間為335.78 ms，處理速率約為11.91 KB/s。查找單個詞條的最大時間為（4 096-256）×4個時鐘周期，為153.6 ?滋s。而FPGA對遙測信號的采樣率為32 kHz，量化精度為8 bit，采樣通道數為6，則壓縮系統的輸入數據速率為192 KB/s。顯然采樣這樣的查字典方式的壓縮算法速度過慢，不能滿足實時壓縮需求。

3 LZW算法的優化設計

3.1 字典大小的設計

    字典的大小對算法的執行速度和壓縮比有影響。過小的字典很快會被填滿，且由于存儲的字符串少，數據匹配效果差，影響壓縮比。過大的字典可能會增加查字典的時間，影響了壓縮速度，重要的是大容量字典耗費的存儲空間也大，要充分考慮FPGA芯片內部塊RAM資源。

    在計算機上通過軟件算法試驗找出合適的字典大小，再考慮算法的硬件實現速度。軟件實驗設計的字典大小必須在硬件的可接受范圍。取128 KB的遙測數據作為壓縮數據源，分別設2 K、4 K、6 K、8 K、16 K、32 K的字典空間大小，實驗結果如表1。隨著字典的增大，壓縮比都有一定的增大，對表1進行壓縮比-字典繪圖如圖2所示。字典大小為2 K～4 K時壓縮比增長率較大，字典大小為4 K～16 K區間字典增長率放緩。

    從圖中可以看到4 K字典或8 K字典才是合理的選擇。由于FPGA還要完成其他工作，考慮到整個系統工作量，將其設置為4 K字典。

3.2 查找字典的方式優化

    查找字典的方式對壓縮和解壓的速度有很大的影響。為了加快查找字典的速度，保證壓縮速率，對查找字典的方式進行優化，采用多次散列法作為查找字典的方式。根據散列表思想，通過建立散列函數index=f(K)，在字典的存儲位置index和它的關鍵字K之間建立一個確定的關系，使這些關鍵字與字典中相應的存儲位置一一對應。圖3為采用散列表結構的字典檢索過程示意圖。

    壓縮時采用的散列函數為：

    其中：currentchar為當前輸入數據，prechar為前一個編碼數據，offset為偏移量，tab_size為散列表長，即字典地址為當前輸入數據左移一位再與前一個編碼數據相異或的值。當散列表中地址產生沖突時，字典地址用式(3)計算，如果該式中字典地址小于0,則用式(4)計算字典地址。

    利用MATLAB軟件對采用不同次數散列的壓縮算法進行測試，結果如圖4所示。為了測試結果更準確，每種查表方式都經過多次測試取平均壓縮時間。

    從圖可看出，在散列次數達到15次以上時，壓縮速度有較大的提高；散列次數從15～40時，壓縮速度并不總是提高，而是稍有波動。原因如下:

    (1)與信號源的特性及散列函數有關。

    (2)由于程序設計為多次散列后出現“沖突”則采用順序方法查表，散列方法查過的位置都有可能被重復查找，散列次數越多，可能出現的重復查找次數就越多，這就增加了一定的壓縮時間。

    由此可見，散列次數并不是越多越好，由試驗結果來看可以選擇25~40次之間。從縱向角度來看，在同等條件下，遙測數據比隨機數據壓縮要快。這是因為隨機信號源的各個字符的出現概率幾乎相等，字符間相互獨立，冗余度極小，這就會使程序更頻繁地在查字典和寫詞條，平均處理一個字符的時間較長。由此可以把對隨機數據的壓縮時間估算為實際壓縮的最大時間。

3.3 字典更新方式的設計

    下面通過軟件仿真比較幾種不同的字典更新方式的壓縮效果，從表2中可以看到不能在提高壓縮比的情況下同時提高壓縮速率，意味著壓縮比滿足情況下，壓縮速率受到制約。所以將這幾種字典更新方式的優點綜合起來，即當字典沒有填滿時就將字典全部清除，重新建立字典，這樣可以同時提高壓縮比和壓縮率，并有效地避免了散列地址的沖突。

4 實驗結果分析

    根據上述優化設計方法對FPGA的LZW壓縮算法進行改進，設計查字典散列次數最大為25次，利用Modelsim軟件仿真程序，結果如圖5所示。從圖5可以看出，改進后的壓縮算法沒有出現長時間的查表時間，程序壓縮字符的時間較為均勻。仿真結果表明，當仿真周期為10 ns(100 MHz時鐘)時，硬件程序壓縮64 KB遙測數據用時24.785 ms，平均處理速率約為2 582.2 KB/s；壓縮64 KB的隨機數據用時83.624 ms，平均處理速率約為765.3 KB/s。這兩個速度都遠大于遙測數據輸入流速率192 KB/s。

    通過對LZW算法的分析，總結了算法優化：字典大小設計、表方式設計和字典分別針對這兩個優化點，以MATLAB軟件為主、Modelsim軟件為輔做仿真實驗，為程序優化、提高系統壓縮性能提供依據。

參考文獻

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

[2] 陳晉敏，黃春明，周軍.激光雷達數據無損壓縮的FPGA實現[J].計算機測量與控制，2007，15(1)：100-102.

[3] 李錦明，張文棟，毛海央，等.實時無損數據壓縮算法硬件實現的研究[J].哈爾濱工業大學學報，2006，38(2)：315-317.

[4] 陳哲，涂國防，張燦，等.基于FPGA的CCSDS圖像數據壓縮系統的設計[J].中國科學院研究生院學報，2011，28(1)：101-107.

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