LZW改進(jìn)壓縮算法的FPGA實(shí)現(xiàn)

0 引言
隨著大規(guī)模集成電路的發(fā)展，在電子設(shè)備監(jiān)控系統(tǒng)中，需要采集與處理的數(shù)據(jù)量也在急劇增加，從而數(shù)據(jù)壓縮技術(shù)得到廣泛應(yīng)用。然而很多壓縮、解壓方案都是基于軟件實(shí)現(xiàn)，其致命的弱點(diǎn)就是過多地消耗寶貴的CPU資源，速度慢?；?a class="contentlabel" href="http://www.butianyuan.cn/news/listbylabel/label/FPGA">FPGA實(shí)現(xiàn)的壓縮器因其速度快、處理能力強(qiáng)而獲得人們的重視?，F(xiàn)代FPGA的發(fā)展使得只用專用硬件的方式來實(shí)現(xiàn)壓縮、解壓成為可能，可以解決上述軟件實(shí)現(xiàn)方式所存在的缺點(diǎn)。但在通用數(shù)據(jù)的壓縮領(lǐng)域，基于FPGA的硬件壓縮、解壓方案還不多見，所以研究基于FPGA硬件實(shí)現(xiàn)的數(shù)據(jù)壓縮技術(shù)具有很高的應(yīng)用價(jià)值。
當(dāng)前數(shù)據(jù)壓縮技術(shù)分為有損壓縮和無損壓縮，算術(shù)編碼、游程編碼、霍夫曼和LZW壓縮是傳統(tǒng)的數(shù)據(jù)壓縮方法，屬于無損數(shù)據(jù)壓縮；而基于小波變換的數(shù)據(jù)壓縮和基于神經(jīng)網(wǎng)絡(luò)的編碼方式是近年來新發(fā)展起來的現(xiàn)代數(shù)據(jù)壓縮方法，屬于有損數(shù)據(jù)壓縮。本研究主要探討一種基于LZW算法的數(shù)據(jù)無損壓縮硬件實(shí)現(xiàn)。

1 LZW算法及其改進(jìn)算法
LZW壓縮算法在壓縮的過程中自適應(yīng)建立一個(gè)字典，以后的數(shù)據(jù)同字典中的數(shù)據(jù)相匹配，匹配上則輸出字典的索引。由于表示字典的索引所用的比特?cái)?shù)遠(yuǎn)小于字符的比特?cái)?shù)，從而達(dá)到壓縮的效果。這個(gè)生成的字典不需要隨著壓縮的數(shù)據(jù)一同傳輸，而是能夠根據(jù)壓縮的數(shù)據(jù)在解壓時(shí)重新動(dòng)態(tài)生成一模一樣的字典。
LZW編碼原理如圖1所示，在進(jìn)行壓縮時(shí)首先把字典中的前256(0～255)項(xiàng)初始為全部的256個(gè)8位字符，分別為十進(jìn)制數(shù)0～255。當(dāng)輸入第一個(gè)字符時(shí)，總是在字典中可以找到，直到新的字符X不在字典詞條中時(shí)，便將字符串IX加入到字典的第256項(xiàng)，以此類推。以字符串流5，6，7，8，9，5，5，6，6，7，8，9，5，…為例，表1給出了字典存儲(chǔ)的物理結(jié)構(gòu)和壓縮過程中字典項(xiàng)的讀寫示意。壓縮后編碼輸出為5，6，7，8，9，5，256，257，259，…。