謝 凱，張 偉，伍 鵬

(長江大學(xué)電子信息學(xué)院，油氣信息處理與識別研究所，湖北 荊州 434023)

彭敏放

(湖南大學(xué)電氣與信息工程學(xué)院,湖南 長沙 410082)

基于FPGA的LZW控制器設(shè)計

謝 凱，張 偉，伍 鵬

(長江大學(xué)電子信息學(xué)院，油氣信息處理與識別研究所，湖北 荊州 434023)

彭敏放

(湖南大學(xué)電氣與信息工程學(xué)院,湖南 長沙 410082)

為了實現(xiàn)對大容量數(shù)據(jù)進(jìn)行遠(yuǎn)距離、快速無損傳輸，設(shè)計了一種基于FPGA的LZW實時硬件無損壓縮系統(tǒng)。采用ALTERA公司Cyclone II系列EP2C5Q208C8N，利用VerilogHDL語言實現(xiàn)各模塊的驗證、時序仿真。結(jié)果表明，利用FPGA實現(xiàn)LZW的硬件壓縮，能夠有效的提高數(shù)據(jù)的存儲和傳輸效率。

無損壓縮；LZW；FPGA；VerilogHDL

為了實現(xiàn)信息的有效、快速、大容量傳輸，近年來，關(guān)于數(shù)據(jù)壓縮的方法成為熱點問題。數(shù)據(jù)壓縮分為有損壓縮和無損壓縮[1]，有損壓縮一般應(yīng)用于語音、圖像和視頻數(shù)據(jù)的壓縮，而對數(shù)據(jù)要求比較高，不允許數(shù)據(jù)失真的場合就要用到無損壓縮。筆者的研究來源于對油田數(shù)據(jù)的傳輸處理。為了準(zhǔn)確的了解井下的地質(zhì)狀況，必須對井下采集到的數(shù)據(jù)進(jìn)行無失真?zhèn)鬏?。由于?shù)據(jù)量比較大，對數(shù)據(jù)壓縮成為必要，如何對大量數(shù)據(jù)進(jìn)行無損壓縮傳輸成為急需解決的問題。

很多壓縮、解壓方案都是基于軟件實現(xiàn)，其致命的弱點就是過多地消耗寶貴的CPU 資源，速度慢[2]?；贔PGA實現(xiàn)的壓縮器因其速度快、處理能力強而獲得人們的重視。但在通用數(shù)據(jù)的無損壓縮領(lǐng)域，基于FPGA的硬件壓縮、解壓方案還不多見[3]。下面，筆者探討了一種基于FPGA的LZW 算法的數(shù)據(jù)無損壓縮算法，主要研究了其控制器的設(shè)計方法。

1 系統(tǒng)模型

圖1 LZW算法FPGA實現(xiàn)的模擬框圖

基于FPGA的LZW的設(shè)計主要劃分成數(shù)據(jù)輸入、數(shù)據(jù)處理和數(shù)據(jù)輸出，其中核心在于數(shù)據(jù)處理部分(見圖1)，這幾部分在控制器的控制作用下協(xié)調(diào)運轉(zhuǎn)。

1)數(shù)據(jù)輸入部分 數(shù)據(jù)輸入部分完成所有數(shù)據(jù)的傳輸工作，為了保證異步時鐘源的同步，使用異步FIFO來對被壓縮數(shù)據(jù)進(jìn)行壓縮前的緩存。

2)數(shù)據(jù)處理部分 數(shù)據(jù)處理部分主要包括字典存儲器模塊和算法實現(xiàn)模塊。字典存儲器模塊需要存放字典項編碼、前綴碼、當(dāng)前碼3部分內(nèi)容。算法實現(xiàn)模塊主要實現(xiàn)字符串的查找，判斷字典相應(yīng)地址內(nèi)容是否為空，比較字典地址相應(yīng)內(nèi)容是否匹配或沖突，沖突時重新生成地址，壓縮編碼輸出控制，壓縮結(jié)束控制等功能。

3)數(shù)據(jù)輸出模塊 在數(shù)據(jù)的輸出模塊，外接數(shù)據(jù)寬度為8位,所以壓縮后輸出數(shù)據(jù)位數(shù)需要轉(zhuǎn)換。數(shù)據(jù)轉(zhuǎn)換模塊就是實現(xiàn)壓縮后數(shù)據(jù)由9位向8位的轉(zhuǎn)換。

4)控制部分 控制單元主要完成時鐘的匹配與控制，對個功能模塊分配時鐘，并初始化各使能端信號。根據(jù)外界指令，產(chǎn)生各模塊控制信號，保證系統(tǒng)正確協(xié)調(diào)工作。當(dāng)外部復(fù)位信號有效時，輸入控制器會根據(jù)外界要求對各模塊進(jìn)行復(fù)位操作。當(dāng)使能信號有效時，輸入控制單元會同時對輸入、輸出、字典模塊及輸出控制幾個單元進(jìn)行控制。

2 系統(tǒng)各模塊的設(shè)計

1) 對FIFO模塊的控制設(shè)計 在控制模塊中最難控制的是產(chǎn)生FIFO的讀寫控制邏輯[4]。在一般利用FIFO對數(shù)據(jù)進(jìn)行緩存較理想的狀況下，采用計數(shù)器來分別計讀寫數(shù)據(jù)的個數(shù)然后作出比較即可判斷FIFO的空滿狀態(tài)。由于實際數(shù)據(jù)是16位的，所以FIFO的數(shù)據(jù)寬度設(shè)計為16/8的FIFO，設(shè)計容量為1K，這就需要確定FIFO的深度?？紤]到字典模塊在處理數(shù)據(jù)的過程中可能會產(chǎn)生沖突，這也會影響到對FIFO的控制，因此筆者綜合考慮外部控制信號和FIFO的深度來產(chǎn)生正確的空滿信號。

關(guān)于FIFO的深度問題，已有的FIFO 深度經(jīng)驗公式[5]。文獻(xiàn)[6]基于排隊論的FIFO中，寫分布是參數(shù)為λ的負(fù)指數(shù)分布，讀分布是參數(shù)為μ的負(fù)指數(shù)分布，該模型考慮了周圍環(huán)境因素的變化得出的深度公式為：

(1)

在設(shè)計過程中，寫數(shù)據(jù)速率和讀數(shù)據(jù)速率都是處于一個動態(tài)變化的范圍內(nèi)，一旦讀寫速率在這個范圍內(nèi)確定即可利用式(1)確定其深度。FIFO在接收到控制器發(fā)出的啟動信號后開始進(jìn)行寫數(shù)據(jù)操作，在寫數(shù)據(jù)的過程中同時判斷FIFO是否滿了，當(dāng)?shù)?次FIFO滿時開始進(jìn)行讀數(shù)據(jù)。在讀數(shù)據(jù)的過程中同時進(jìn)行寫數(shù)據(jù)操作，并且利用計數(shù)器比較讀和寫數(shù)據(jù)的個數(shù)，當(dāng)讀寫個數(shù)相等的時候停止讀，寫繼續(xù)，直到FIFO再次滿的時候開始讀數(shù)據(jù)，然后重復(fù)上述操作。讀時鐘受到2個信號的控制：一個是讀使能信號，另一個是字典模塊給出的數(shù)據(jù)壓縮成功信號。由于字典模塊的壓縮速度非常快，在讀使能信號的一個時鐘之內(nèi)便能完成，所以在字典部分正常的壓縮情況下，讀使能信號的時鐘周期能夠與給出壓縮成功標(biāo)準(zhǔn)信號的時鐘周期相匹配。當(dāng)字典在處理沖突的過程中，考慮到處理沖突的時間長短不確定，此時必須關(guān)閉讀信號時鐘的計數(shù)器，以免影響正常的計數(shù)。

2)對字典模塊的控制設(shè)計 LZW編碼的原理如下：讀入第一個字符賦值給C，讀入下一個字符賦值給K，編碼器逐個輸入字符K并累積成一個字符串CK賦給C。每輸入一個新的字符就被串接在C后面，然后在串表中查找C：只要在串表中找到C，該過程就繼續(xù)進(jìn)行；直到在某一點，添加下一個字符K導(dǎo)致搜索失敗，字符串C在字典中，而CK(字符K串接在C后)卻不在，這時編碼器：①輸出指向字符串C的字典指針；②在下一個可用的字典詞條中，存儲字符串CK； ③把字符串CK預(yù)置為C；④循環(huán)重復(fù)上述過程。在每次讀入新字符的時候都需要先判斷讀入是否為空，如果為空則編碼結(jié)束，如果不為空則繼續(xù)。該算法的關(guān)鍵是在數(shù)據(jù)壓縮的過程中會根據(jù)輸入的數(shù)據(jù)動態(tài)的建立一個字典。當(dāng)以后的數(shù)據(jù)同字典中的數(shù)據(jù)相匹配時，則輸出該數(shù)據(jù)在字典中的地址。由于字典索引的比特數(shù)遠(yuǎn)小于數(shù)據(jù)串的比特數(shù)，從而達(dá)到壓縮效果。巧妙的是該字典不需要與壓縮數(shù)據(jù)流一道進(jìn)行傳輸和存儲，并且只需要對數(shù)據(jù)掃描一次，在對數(shù)據(jù)進(jìn)行解壓時也能夠通過壓縮數(shù)據(jù)流重新建立一個字典，來完成解壓縮。

字典存儲器容量設(shè)計為1K,則其地址寬度為10位。當(dāng)前碼為8位，前綴項編碼為9位，字典項編碼也為9位，則字典存儲器總的數(shù)據(jù)寬度為26位。為了防止字典滿時重建清空字典，設(shè)計2個相同的字典存儲器，使2個字典存儲器交替工作，來提高壓縮速度。

對字典模塊的外部控制主要有以下幾個方面：算法實現(xiàn)模塊主要實現(xiàn)字符串的查找，判斷字典相應(yīng)地址內(nèi)容是否為空，比較字典地址相應(yīng)內(nèi)容是否匹配或沖突，沖突時要對沖突進(jìn)行處理。

3)對輸出模塊的控制 輸出模塊的輸入數(shù)據(jù)寬度是9位，輸出數(shù)據(jù)是8位，輸出模塊重點是完成數(shù)據(jù)位的轉(zhuǎn)換。當(dāng)數(shù)據(jù)在字典部分被成功的壓縮之后，控制器會給輸出部分一個輸出信號，當(dāng)字典部分給控制器的是字符的信號，則輸出部分將數(shù)據(jù)放入寄存器進(jìn)行正常的數(shù)據(jù)轉(zhuǎn)換，即輸出有效；如字典給出的是清空信號，則輸出部分不作任何響應(yīng)；如字典部分給出的是結(jié)束信號，則輸出部分結(jié)束。

3 綜合仿真結(jié)果及分析

將FIFO模塊、字典模塊、數(shù)據(jù)輸出模塊3部分綜合起來進(jìn)行控制，得到的功能仿真波形圖如圖2所示，狀態(tài)轉(zhuǎn)換如圖3所示。圖3中，s0表示整個系統(tǒng)開始工作；s1表示開始進(jìn)行寫數(shù)據(jù)并判斷FIFO是否寫滿，并在寫滿的時候?qū)懙挠嫈?shù)器信號清；s2表示開始讀數(shù)據(jù)，并判斷是否讀空；s3表示字典對數(shù)據(jù)進(jìn)行壓縮處理，出現(xiàn)沖突時停止讀回到狀態(tài)s1只寫信號狀態(tài)。

圖2 綜合功能仿真波形圖 圖3 綜合狀態(tài)轉(zhuǎn)換圖

圖4 FPGA資源占用情況

圖2仿真結(jié)果說明了功能上的正確性，同時說明在時序上電路也是符合性能要求的。該設(shè)計的優(yōu)點是可以對代碼進(jìn)行綜合分析生成RTL圖，從RTL模型中可以直觀看出不同寄存器直接的數(shù)據(jù)傳輸。該硬件壓縮電路的核心是使用Verilog HDL語言進(jìn)行描述設(shè)計的FPGA芯片實現(xiàn)的功能模塊，以QuartusⅡ為軟件開發(fā)平臺。FPGA芯片資源占用情況如圖4所示。在圖4中，Total logic elements 16/4608(<1%):該芯片中共有4608個LE資源，其中的16個資源在這個工程的編譯中得到使用；Total combinational functions 16/4608(<1%):該芯片的4608個LE資源中，16個資源用于實現(xiàn)組合邏輯；Dedicated logic registers 8/4608(<1%):該芯片的4608個LE資源中，8個用于實現(xiàn)寄存器，即時序邏輯。從而可以看出該系統(tǒng)占用的邏輯資源較少。

4 結(jié) 語

經(jīng)過相關(guān)的仿真和驗證發(fā)現(xiàn)，筆者所設(shè)計的無損壓縮系統(tǒng)占用的邏輯資源較少，可移植性強，功能擴展容易，有效的提高了數(shù)據(jù)的存儲和傳輸效率，特別在大容量數(shù)據(jù)采集和傳輸系統(tǒng)中應(yīng)用前景廣闊。并且利用LZW壓縮重復(fù)出現(xiàn)的字符串，無需事先統(tǒng)計各字符的出現(xiàn)概率，一次掃描即可，相對于其他算法，更有利于硬件實現(xiàn)。

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

[2]繆志宏.數(shù)據(jù)壓縮算法的實現(xiàn)研究[D].杭州：浙江大學(xué)，2007.

[3]劉洪慶，王新才，沈海斌.一種基于LZW算法的數(shù)據(jù)無損壓縮硬件實現(xiàn)[J].計算機應(yīng)用，2008,25(8)：1-4.

[4]魏欣，王勇.一種高效的異步FIFO設(shè)計方法[J].儀器儀表學(xué)報,2009，16(1): 102-103.

[5]陳征.FIFO 緩沖存儲器的結(jié)構(gòu)及其應(yīng)用[J].汕頭大學(xué)學(xué)報(自然科學(xué)版)，1998，13(1): 85-89.

[6]宋宇鯤，王銳，胡永華，等.使用排隊論模型對FIFO深度的研究[J].儀器儀表學(xué)報，2006，27(6)：2486-2487.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.12.039

TN791

A

1673-1409(2012)12-N120-03