基于FPGA的LZW控制器設計

謝 凱，張 偉，伍 鵬

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

彭敏放

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

基于FPGA的LZW控制器設計

謝 凱，張 偉，伍 鵬

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

彭敏放

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

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

無損壓縮；LZW；FPGA；VerilogHDL

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

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

1 系統模型

圖1 LZW算法FPGA實現的模擬框圖

基于FPGA的LZW的設計主要劃分成數據輸入、數據處理和數據輸出，其中核心在于數據處理部分(見圖1)，這幾部分在控制器的控制作用下協調運轉。

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

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

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

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

2 系統各模塊的設計

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

關于FIFO的深度問題，已有的FIFO 深度經驗公式[5]。文獻[6]基于排隊論的FIFO中，寫分布是參數為λ的負指數分布，讀分布是參數為μ的負指數分布，該模型考慮了周圍環境因素的變化得出的深度公式為：

(1)

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

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

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

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

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

3 綜合仿真結果及分析

將FIFO模塊、字典模塊、數據輸出模塊3部分綜合起來進行控制，得到的功能仿真波形圖如圖2所示，狀態轉換如圖3所示。圖3中，s0表示整個系統開始工作；s1表示開始進行寫數據并判斷FIFO是否寫滿，并在寫滿的時候將寫的計數器信號清；s2表示開始讀數據，并判斷是否讀空；s3表示字典對數據進行壓縮處理，出現沖突時停止讀回到狀態s1只寫信號狀態。

圖2 綜合功能仿真波形圖 圖3 綜合狀態轉換圖

圖4 FPGA資源占用情況

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

4 結 語

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

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

[2]繆志宏.數據壓縮算法的實現研究[D].杭州：浙江大學，2007.

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

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

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

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

[編輯] 洪云飛

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

TN791

A

1673-1409(2012)12-N120-03