《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > LZW改進壓縮算法的FPGA實現
LZW改進壓縮算法的FPGA實現
現代電子技術
趙雙龍,郝永生
摘要: LZW算法邏輯簡單,實現速度快,擅長于壓縮重復出現的字符串;無需事先統計各字符的出現概率,一次掃描即可;相對于其他算法,更有利于硬件實現。本文利用FPGA實現了改進的LZW壓縮算法,仿真證明其算法具有很高壓縮率,適合工程的實際應用。
關鍵詞: FPGA LZW
Abstract:
Key words :

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,…。


    傳統的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壓縮算法,仿真證明其算法具有很高壓縮率,適合工程的實際應用。

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 欧美激情人成日本在线视频 | 中文字幕一区二区三 | 免费一级a毛片在线播放视 免费一级a毛片在线播出 | 成人国产精品一级毛片视频 | 成年人免费看 | 男女做www免费高清视频 | 99久久综合 | 999热在线精品观看全部 | 国内毛片视频 | 免费观看日皮视频 | 国产三级a三级三级野外 | 嗯啊在线观看免费影院 | 国产国产精品人在线视 | 国产成人h福利小视频在线观看 | 激情五月婷婷综合网 | 国产不卡高清 | 国产小视频在线观看免费 | 日本在线天堂 | 越南一级毛片免费 | 99v视频国产在线观看免费 | 天堂资源地址在线 | 欧洲成人r片在线观看 | 国产精品日韩欧美一区二区三区 | 黄色毛片免费进入 | 国产91成人 | 天天透天天插 | 黄在线 | 日本免费小视频 | 久久国产成人午夜aⅴ影院 久久国产欧美日韩精品 | 亚洲综合欧美日韩 | 日韩欧美在线综合 | 丰满老妇猛交视频 | 成人午夜性a一级毛片美女 成人午夜小视频 | 国产亚洲欧美日韩在线看片 | 国内视频一区二区三区 | 免费国产成人综合 | 国产综合视频 | 天天爽夜夜爽免费看 | 万部在线视频免费观看 | 重口高h 全肉 文调教bl | 欧美综合区自拍亚洲综合天堂 |