FPGA實現(xiàn)滑動平均濾波算法和LZW壓縮算法

陳世海，裴東興，張 琦

（中北大學(xué) 儀器科學(xué)與動態(tài)測試教育部重點實驗室，山西 太原 030051）

在工業(yè)生產(chǎn)、科學(xué)研究過程中常常為觀察一個信號，需要數(shù)據(jù)采集系統(tǒng)對信號進行長時間高速采樣，因此，龐大的數(shù)據(jù)量給數(shù)據(jù)傳輸、存儲和處理帶來極大的挑戰(zhàn)。通過數(shù)據(jù)壓縮技術(shù)可以緩解數(shù)據(jù)傳輸和存儲系統(tǒng)的壓力。數(shù)據(jù)壓縮技術(shù)分為有損壓縮和無損壓縮兩大類。無損壓縮是利用數(shù)據(jù)的冗余度壓縮，壓縮后的數(shù)據(jù)進行重構(gòu)后與原來的數(shù)據(jù)完全相同；有損壓縮壓縮后數(shù)據(jù)進行重構(gòu)與原來的數(shù)據(jù)有所不同。多數(shù)的數(shù)據(jù)采集系統(tǒng)因被測對象的不確定性則需要采用無損數(shù)據(jù)壓縮[1]。由于LZW無損壓縮算法具有自適應(yīng)特性，在對信號統(tǒng)計特性不明確的情況下，仍然有較好的壓縮效果。結(jié)合現(xiàn)場可編程門陣列（FPGA）的高集成度、低功耗、靈活、及能進行并行運算的特性[2]，該設(shè)計采用FPGA以硬件的方式實現(xiàn)LZW算法，以提高系統(tǒng)的實時壓縮能力。同時，考慮到LZW算法自身的特點，為提高壓縮比和減輕上位機對數(shù)據(jù)進行軟件濾波的運算量，采用在對數(shù)據(jù)進行壓縮前進行滑動平均數(shù)字濾波的預(yù)處理方法。

1 滑動平均數(shù)字濾波

為消除采樣系統(tǒng)中的小幅度高頻A/D量化噪聲，平滑采集數(shù)據(jù)曲線，提高后續(xù)壓縮的效能，在系統(tǒng)中采用具有低通特性的滑動平均數(shù)字濾波器?；瑒悠骄鶠V波法是把N個采集數(shù)據(jù)看成一個隊列，隊列的長度固定為N，每進行一次新的采樣，把新的采樣結(jié)果放入隊尾，而去掉原來隊首的一個數(shù)據(jù)，把隊列中的N個數(shù)據(jù)進行算術(shù)平均運算，其結(jié)果就為新的濾波結(jié)果[3]。濾波算法的數(shù)學(xué)模型描述如下：

具體實現(xiàn)時，綜合考慮采樣頻率、信號的截止頻率以及硬件實現(xiàn)的規(guī)模和難易程度，設(shè)定N值為8。模塊采用8級移位寄存器和7個加法器來實現(xiàn)對輸入數(shù)據(jù)的滑動求和。8級移位寄存器即組成一個數(shù)據(jù)隊列，其中的數(shù)據(jù)在每個時鐘沿的推動下移動一次，形成新舊數(shù)據(jù)的移入移出操作。另外用一個固定數(shù)值為8的除法器實現(xiàn)對滑動和求平均的運算。

2 LZW算法及其FPGA的實現(xiàn)

2.1 LZW算法的基本原理

LZW算法是一種基于字典的壓縮算法，該算法的關(guān)鍵是在數(shù)據(jù)的壓縮過程中會根據(jù)輸入的數(shù)據(jù)動態(tài)地建立一個字典。巧妙的是該字典不需要與壓縮數(shù)據(jù)流一道進行傳輸和存儲。在對數(shù)據(jù)進行解壓時也能夠通過壓縮數(shù)據(jù)流重新建立一個字典，來完成解壓縮[4]。LZW算法描述如下[5]：

算法首先進行字典的初始化，然后輸入第1個字符數(shù)據(jù)賦給變量String（S），數(shù)據(jù)逐個輸入壓縮器中并賦給變量Character（C），S和C生成一個索引與字典中的詞條數(shù)據(jù)進行匹配，如果匹配成功就將S和C的編碼值賦給S，繼續(xù)進行下一輪匹配。如果匹配失敗，則將S輸出，將S和C的編碼值存入字典，并且將C的值賦給S，這一過程一直進行直到結(jié)束。最后，輸出S，輸出結(jié)束標志。由算法描述可見，LZW算法并不復(fù)雜，有利于硬件實現(xiàn)且能夠?qū)崿F(xiàn)對數(shù)據(jù)進行實時的壓縮。仔細分析該算法特性可知，對于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的數(shù)據(jù)，LZW壓縮算法具有很高的壓縮比。在前端數(shù)據(jù)濾波的過程，其不僅能夠起到平滑數(shù)據(jù)曲線的作用，同時也能產(chǎn)生一些連續(xù)重復(fù)出現(xiàn)的數(shù)據(jù)，而這對于算法實現(xiàn)高壓縮比是非常有利的。

2.2 LZW算法的FPGA實現(xiàn)

硬件模塊框圖如圖1所示。為獲得較高的實時壓縮速度，采用FPGA內(nèi)部的RAM塊來構(gòu)造LZW字典。字典中的詞條由編碼值（Code）、字符串（String）及字符（Character） 3 部分構(gòu)成，其中 Code（CO）和 String（S）所占空間分別為 9 bit，而Character（C）為8 bit。每個詞條所占用的存儲空間為9+9+8=26 bit?？梢詷?gòu)造位寬為26位的存儲器作為字典。字典的查找技術(shù)是LZW算法中的一個關(guān)鍵部分，關(guān)系到每進行一次數(shù)據(jù)匹配過程的效率。為提高字典的地址計算速度，采用哈希函數(shù)建立字典索引地址與輸入數(shù)據(jù)之間的關(guān)系。具體的哈希函數(shù)計數(shù)公式如下[5]：

圖1 壓縮模塊內(nèi)部結(jié)構(gòu)框圖

Index為字典索引地址；Tab_size為哈希表的容量大小，考慮FPGA內(nèi)的RAM容量有限，這里選為1 021；Offset為偏移量，是為解決哈希函數(shù)沖突時用到的一個中間量。字典地址等于當前輸入的字符數(shù)據(jù)左移一位后與字符串編碼相異或的值。當哈希表中地址產(chǎn)生沖突時，則字典地址用式（3）計算，如果式（3）計算的字典地址小于0，則字典地址用式（4）計算。隨著壓縮過程的進行，字典將被詞條逐步填滿，考慮到數(shù)據(jù)的局部相關(guān)性，為提高壓縮比，字典清空維護模塊將對存儲滿的字典進行清空操作，使字典能夠自適應(yīng)新輸入的數(shù)據(jù)。狀態(tài)機控制模塊是整個壓縮模塊的時序控制中心，它是根據(jù)其他模塊反饋給它的信號，判斷壓縮的運行狀態(tài)，從而控制其他各個模塊的運行。

3 系統(tǒng)綜合、仿真及調(diào)試

將濾波和壓縮兩個功能模塊整合到一個工程里，以Altera公司的CycloneII系列中的EP2C5T144I8作為目標器件，經(jīng)過QuartusII軟件編譯綜合，得到工程的綜合報告。表1是整個工程的FPGA資源占用情況。

表1 FPGA資源占用情況

由綜合結(jié)果可知，系統(tǒng)能夠穩(wěn)定運行的最高工作頻率是102 MHz，根據(jù)設(shè)計特點，平均每10個時鐘周期壓縮1個數(shù)據(jù)，數(shù)據(jù)輸入的位寬為8 bit，所以整個系統(tǒng)能夠有效的處理能力為：81.6 Mb/s。

圖2是LZW模塊的壓縮仿真圖，圖中的OUTPUT是9位的輸出，Dataout是最終的8位結(jié)果，可見LZW模塊仿真的結(jié)果無誤。

系統(tǒng)調(diào)試時，由信號發(fā)生器產(chǎn)生相應(yīng)的信號，經(jīng)A/D轉(zhuǎn)換后數(shù)據(jù)分為兩路，其中一路傳送給FPGA，F(xiàn)PGA對數(shù)據(jù)進行濾波和壓縮，然后將處理過的數(shù)據(jù)傳給電腦并保存為數(shù)據(jù)文件。另一路數(shù)據(jù)不經(jīng)過FPGA處理直接傳給電腦，在電腦上用軟件實現(xiàn)對數(shù)據(jù)進行濾波和壓縮運算，將運算結(jié)果同樣保存為文件。2個文件經(jīng)對比后，其中的數(shù)據(jù)內(nèi)容完全一致，說明整個硬件濾波和壓縮電路能夠正確無誤的實現(xiàn)功能。同時，用專用軟件打開濾波前后的數(shù)據(jù)，觀察波形后可知信號經(jīng)過濾波后衰減很小，波形中的高頻A/D量化噪聲被有效的抑制，曲線的平滑度較好，這也說明濾波器的設(shè)計達到預(yù)期的效果。

圖2 壓縮模塊的仿真結(jié)果

為了評估LZW系統(tǒng)的壓縮效果，選取Canterbury文件集合進行測試[6]，表2是測試的部分結(jié)果。由于在FPGA內(nèi)部實現(xiàn)LZW字典，其容量有限，造成對文本類的數(shù)據(jù)壓縮效果較差。相比文本數(shù)據(jù)，對傳真圖像類的數(shù)據(jù)有著較好的壓縮效果。對實際由A/D轉(zhuǎn)換回來的數(shù)據(jù)進行測試，壓縮率約為25%，說明本設(shè)計可以應(yīng)用于實際的數(shù)據(jù)采集系統(tǒng)中。

表2 Canterbury文件測試部分結(jié)果

4 結(jié)論

本設(shè)計通過FPGA從硬件上實現(xiàn)了滑動濾波算法和LZW無損壓縮算法。經(jīng)過實際測試驗證，該系統(tǒng)能夠正確無誤的對數(shù)據(jù)進行濾波和壓縮運算。壓縮效果較好，能夠有效緩解采集系統(tǒng)中的數(shù)據(jù)傳輸及存儲的壓力。同時，81.6 Mb/s的壓縮速度可以滿足大部分數(shù)據(jù)采集系統(tǒng)的實時要求。若用外部RAM存儲器實現(xiàn)LZW字典，將能大幅度地擴大字典容量，顯著改善數(shù)據(jù)的壓縮效果。

[1]靳 鴻，裴東興，祖 靜.無損數(shù)據(jù)壓縮在數(shù)據(jù)采集系統(tǒng)中的應(yīng)用探討[J].華北工學(xué)院學(xué)報，2003，24（1）：69-71.

[2]李雷定，馬鐵華.利用FPGA實現(xiàn)LZW算法的研究[J].電子測量技術(shù)，2008，31（10）：170-172.

[3]黃凱明.滑動平均數(shù)字濾波參數(shù)研究[J].集美大學(xué)學(xué)報，2006，11（4）：381-384.

[4]朱 鋼，臧亞琴，劉 方.壓縮技術(shù)在數(shù)據(jù)采集系統(tǒng)中的應(yīng)用[J].數(shù)據(jù)采集與處理，1997，12（1）：69-71.

[5]NelsonMark.LZWdatacompression[EB/OL].1989.http：//marknelson.us/1989/10/01/lzw-data-compression/

[6]David salomon.數(shù)據(jù)壓縮原理與應(yīng)用[M].吳樂南，等譯.北京：電子工業(yè)出版社，2003.