LZW改进压缩算法的改进压缩算法的FPGA实现实现
LZW算法逻辑简单,实现速度快,擅长于压缩重复出现的字符串;无需事先统计各字符的出现概率,一次扫描
即可;相对于其他算法,更有利于硬件实现。本文利用FPGA实现了改进的LZW压缩算法,仿真证明其算法具有
很高压缩率,适合工程的实际应用。
0 引言引言
随着大规模集成电路的发展,在电子设备监控系统中,需要采集与处理的数据量也在急剧增加,从而数据压缩技术得到广
泛应用。然而很多压缩、解压方案都是基于软件实现,其致命的弱点就是过多地消耗宝贵的CPU资源,速度慢。基于
当前数据压缩技术分为有损压缩和无损压缩,算术编码、游程编码、霍夫曼和
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 算法实现硬件结构算法实现硬件结构
评论0