基于LZW算法的數據無(wú)損壓縮硬件實(shí)現

當前數據壓縮技術(shù)分為有損壓縮和無(wú)損壓縮，算術(shù)編碼、游程編碼、霍夫曼和LZW壓縮是傳統的數據壓縮方法，屬于無(wú)損數據壓縮;而基于小波變換的數據壓縮和基于神經(jīng)網(wǎng)絡(luò )的編碼方式是近年來(lái)新發(fā)展起來(lái)的現代數據壓縮方法，屬于有損數據壓縮。本研究主要探討一種基于LZW算法的數據無(wú)損壓縮硬件實(shí)現。

　　1 LZW算法及其改進(jìn)算法

　　LZW壓縮算法在壓縮的過(guò)程中自適應建立一個(gè)字典，以后的數據同字典中的數據相匹配，匹配上則輸出字典的索引。由于表示字典的索引所用的比特數遠小于字符的比特數，從而達到壓縮的效果。這個(gè)生成的字典不需要隨著(zhù)壓縮的數據一同傳輸，而是能夠根據壓縮的數據在解壓時(shí)重新動(dòng)態(tài)生成一模一樣的字典。

　　LZW編碼原理如圖1所示，在進(jìn)行壓縮時(shí)首先把字典中的前256(0～255)項初始為全部的256個(gè)8位字符，分別為十進(jìn)制數0～255。當輸入第一個(gè)字符時(shí)，總是在字典中可以找到，直到新的字符X不在字典詞條中時(shí)，便將字符串IX加入到字典的第256項，以此類(lèi)推。以字符串流5，6，7，8，9，5，5，6，6，7，8，9，5，…為例，表1給出了字典存儲的物理結構和壓縮過(guò)程中字典項的讀寫(xiě)示意。壓縮后編碼輸出為5，6，7，8，9，5，256，257，259，…。

　　傳統的LZW壓縮算法采用8位數據輸入，固定長(cháng)度編碼輸出，隨著(zhù)字典內容的不斷增多，輸出編碼的位數不斷增加勢必造成資源的浪費，也會(huì )損失壓縮率。另外，由于字典的容量有限，隨著(zhù)壓縮過(guò)程的進(jìn)行，字典會(huì )被填滿(mǎn)，若是簡(jiǎn)單的不再向字典中增加內容，那么后面的壓縮率就會(huì )降低，而如果將字典全部清除重新建立字典，在字典建立初期壓縮率也是很低的。針對以上不足，文獻對LZW算法做以下改進(jìn)：采用12位數據作為壓縮輸入，變長(cháng)度的碼字輸出。

　　壓縮字典最多可容納16 384個(gè)碼，共分為三部分，其中0～4 095為12位輸出，4 096～8 191為13位，8 192～16 383為14位。每當輸出長(cháng)度變化時(shí)，同時(shí)輸出一個(gè)變長(cháng)標識，便于解碼器解碼。