LZW改進壓縮算法的FPGA實現

0 引言
隨著大規模集成電路的發展，在電子設備監控系統中，需要采集與處理的數據量也在急劇增加，從而數據壓縮技術得到廣泛應用。然而很多壓縮、解壓方案都是基于軟件實現，其致命的弱點就是過多地消耗寶貴的CPU資源，速度慢。基于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，…。