0 引言

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

1 LZW算法基礎(chǔ)理論

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

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

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

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

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

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

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

3.1 字典大小的設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

3.3 字典更新方式的設(shè)計(jì)

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

參考文獻(xiàn)

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

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

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

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

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