0 引言
隨著大規模集成電路的發展，在電子設備監控系統中，需要采集與處理的數據量也在急劇增加，從而數據壓縮技術得到廣泛應用。然而很多壓縮、解壓方案都是基于軟件實現，其致命的弱點就是過多地消耗寶貴的CPU資源，速度慢?；?a class="innerlink" href="http://www.cowatch.cn/tags/FPGA" title="FPGA" target="_blank">FPGA實現的壓縮器因其速度快、處理能力強而獲得人們的重視。現代FPGA的發展使得只用專用硬件的方式來實現壓縮、解壓成為可能，可以解決上述軟件實現方式所存在的缺點。但在通用數據的壓縮領域，基于FPGA的硬件壓縮、解壓方案還不多見，所以研究基于FPGA硬件實現的數據壓縮技術具有很高的應用價值。
當前數據壓縮技術分為有損壓縮和無損壓縮，算術編碼、游程編碼、霍夫曼和LZW壓縮是傳統的數據壓縮方法，屬于無損數據壓縮；而基于小波變換的數據壓縮和基于神經網絡的編碼方式是近年來新發展起來的現代數據壓縮方法，屬于有損數據壓縮。本研究主要探討一種基于LZW算法的數據無損壓縮硬件實現。
1 LZW算法及其改進算法
LZW壓縮算法在壓縮的過程中自適應建立一個字典，以后的數據同字典中的數據相匹配，匹配上則輸出字典的索引。由于表示字典的索引所用的比特數遠小于字符的比特數，從而達到壓縮的效果。這個生成的字典不需要隨著壓縮的數據一同傳輸，而是能夠根據壓縮的數據在解壓時重新動態生成一模一樣的字典。
LZW編碼原理如圖1所示，在進行壓縮時首先把字典中的前256(0～255)項初始為全部的256個8位字符，分別為十進制數0～255。當輸入第一個字符時，總是在字典中可以找到，直到新的字符X不在字典詞條中時，便將字符串IX加入到字典的第256項，以此類推。以字符串流5，6，7，8，9，5，5，6，6，7，8，9，5，…為例，表1給出了字典存儲的物理結構和壓縮過程中字典項的讀寫示意。壓縮后編碼輸出為5，6，7，8，9，5，256，257，259，…。
傳統的LZW壓縮算法采用8位數據輸入，固定長度編碼輸出，隨著字典內容的不斷增多，輸出編碼的位數不斷增加勢必造成資源的浪費，也會損失壓縮率。另外，由于字典的容量有限，隨著壓縮過程的進行，字典會被填滿，若是簡單的不再向字典中增加內容，那么后面的壓縮率就會降低，而如果將字典全部清除重新建立字典，在字典建立初期壓縮率也是很低的。針對以上不足，文獻對LZW算法做以下改進：采用12位數據作為壓縮輸入，變長度的碼字輸出。
壓縮字典最多可容納16 384個碼，共分為三部分，其中0～4 095為12位輸出，4 096～8 191為13位，8 192～16 383為14位。每當輸出長度變化時，同時輸出一個變長標識，便于解碼器解碼。
2 LZW算法FPGA實現
2．1 算法實現硬件結構
LZW數據壓縮算法的FPGA硬件實現，其內部功能模塊劃分如圖2所示。
2．2 各功能模塊說明
輸入／輸出數據緩存模塊完成FPGA所有數據傳輸工作，為了保證異步時鐘域數據同步，使用FPGA片內的Block RAM構成一個FIFO對輸入數據進行緩存。
字典存儲器模塊需要存放字典項的三部分內容：字典項編碼、前綴碼、當前碼。將存儲器的容量設計為1K。采用FPGA內部宏單元lpm-ram-dp(單口RAM)設計字典存儲器。
算法實現模塊要實現匹配串的查找、判斷字典相應地址內容是否為空、比較字典地址相應內容是否匹配或沖突、沖突時重新生成地址、壓縮編碼輸出控制、壓縮結束控制等功能。
外接閃存數據寬度為8位，所以壓縮后輸出數據位數需要轉換。數據轉換模塊就是實現壓縮后數據由13位向8位的轉換。
時鐘處理與控制模塊主要完成時鐘的匹配與控制，對各個功能模塊分配時鐘，并初始化各使能端信號。
2．3 仿真結果
清空字典存儲器模塊，初始化信號，將可能出現的單字符存入字典，壓縮時新傳續存地址為4096，新字符串輸入時產生相應的哈希表地址與偏移量；然后讀字典存儲器相應地址的內容，如內容為空則輸出輸入的數據，并把相應內容存入字典，如內容匹配，則繼續輸入下一數據，否則(即發生沖突)產生新的哈希表地址，重新讀取字典，進行判斷、比較。仿真時序如圖3所示。
仿真結果：輸入數據為5，6，7，8，9，5，6，7，8，9，5，6，7，…；輸出數據為5，6，7，8，9，4 098，4 100，4 102，…。仿真結果與理論計算值一致。
3 結 論
LZW算法邏輯簡單，實現速度快，擅長于壓縮重復出現的字符串；無需事先統計各字符的出現概率，一次掃描即可；相對于其他算法，更有利于硬件實現。本文利用FPGA實現了改進的LZW壓縮算法，仿真證明其算法具有很高壓縮率，適合工程的實際應用。