0 引言

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

1 LZW算法基礎理論

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

2 傳統(tǒng)LZW算法壓縮方法的分析

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

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

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

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

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

3.1 字典大小的設計

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

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

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

3.2 查找字典的方式優(yōu)化

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

    壓縮時采用的散列函數(shù)為：

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

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

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

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

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

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

3.3 字典更新方式的設計

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

4 實驗結果分析

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

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

參考文獻

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

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

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

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

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