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

傳統的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)標識，便于解碼器解碼。

2 LZW算法FPGA實(shí)現
2．1 算法實(shí)現硬件結構
LZW數據壓縮算法的FPGA硬件實(shí)現，其內部功能模塊劃分如圖2所示。

2．2 各功能模塊說(shuō)明
輸入／輸出數據緩存模塊完成FPGA所有數據傳輸工作，為了保證異步時(shí)鐘域數據同步，使用FPGA片內的Block RAM構成一個(gè)FIFO對輸入數據進(jìn)行緩存。
字典存儲器模塊需要存放字典項的三部分內容：字典項編碼、前綴碼、當前碼。將存儲器的容量設計為1K。采用FPGA內部宏單元lpm-ram-dp(單口RAM)設計字典存儲器。
算法實(shí)現模塊要實(shí)現匹配串的查找、判斷字典相應地址內容是否為空、比較字典地址相應內容是否匹配或沖突、沖突時(shí)重新生成地址、壓縮編碼輸出控制、壓縮結束控制等功能。
外接閃存數據寬度為8位，所以壓縮后輸出數據位數需要轉換。數據轉換模塊就是實(shí)現壓縮后數據由13位向8位的轉換。
時(shí)鐘處理與控制模塊主要完成時(shí)鐘的匹配與控制，對各個(gè)功能模塊分配時(shí)鐘，并初始化各使能端信號。
2．3 仿真結果
清空字典存儲器模塊，初始化信號，將可能出現的單字符存入字典，壓縮時(shí)新傳續存地址為4096，新字符串輸入時(shí)產(chǎn)生相應的哈希表地址與偏移量；然后讀字典存儲器相應地址的內容，如內容為空則輸出輸入的數據，并把相應內容存入字典，如內容匹配，則繼續輸入下一數據，否則(即發(fā)生沖突)產(chǎn)生新的哈希表地址，重新讀取字典，進(jìn)行判斷、比較。仿真時(shí)序如圖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算法邏輯簡(jiǎn)單，實(shí)現速度快，擅長(cháng)于壓縮重復出現的字符串；無(wú)需事先統計各字符的出現概率，一次掃描即可；相對于其他算法，更有利于硬件實(shí)現。本文利用FPGA實(shí)現了改進(jìn)的LZW壓縮算法，仿真證明其算法具有很高壓縮率，適合工程的實(shí)際應用。