0 引言

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

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

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

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

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

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

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

    若只采用順序查表，取字典大小為4 K,，則處理4 KB的數(shù)據(jù)的最大查找長(zhǎng)度約為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對(duì)遙測(cè)信號(hào)的采樣率為32 kHz,，量化精度為8 bit,，采樣通道數(shù)為6，則壓縮系統(tǒng)的輸入數(shù)據(jù)速率為192 KB/s,。顯然采樣這樣的查字典方式的壓縮算法速度過(guò)慢,，不能滿足實(shí)時(shí)壓縮需求。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    根據(jù)上述優(yōu)化設(shè)計(jì)方法對(duì)FPGA的LZW壓縮算法進(jìn)行改進(jìn)，設(shè)計(jì)查字典散列次數(shù)最大為25次,，利用Modelsim軟件仿真程序,，結(jié)果如圖5所示。從圖5可以看出,，改進(jìn)后的壓縮算法沒(méi)有出現(xiàn)長(zhǎng)時(shí)間的查表時(shí)間,，程序壓縮字符的時(shí)間較為均勻。仿真結(jié)果表明,，當(dāng)仿真周期為10 ns(100 MHz時(shí)鐘)時(shí),，硬件程序壓縮64 KB遙測(cè)數(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)大于遙測(cè)數(shù)據(jù)輸入流速率192 KB/s,。

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

參考文獻(xiàn)

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

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

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

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

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