（电路与系统专业论文）数据压缩算法的实现研究.pdf

浙江大学硕士学位论文 摘要 数据的无损压缩在通信、航天、医疗等各个方面获得了普遍的应用。基于 v l s i 实现的压缩器由于其速度快、处理能力强而获得人们的重视，成为一个热 门的研究领域。 本文提出了一种基于l z w 算法的硬件实现的无损压缩器。根据l z w 算法 的特点提出了无损压缩器的体系结构。该体系结构采用了一种并行的字典搜索 策略，极大的提高了字串的搜索速度。同时字典被拆分，字典宽度变长，从而 节省了存储空间，减少了芯片面积。在此体系结构的基础上用c + + 实现了一个 仿真模型，以此模型证明了功能的正确性。然后压缩器被细分到模块级，并用 r t l ( v e r i l o g ) 描述了各个模块。其中层次化的字典模块设计策略使得字典结 构清晰合理，并大大减少了代码量。在压缩器的设计中采用了可配置的寄存器 来控制压缩器的功能，使得控制部分和数据处理部分明确分工，并且有利于功 能的扩展。同时该压缩器体现了d f t 的设计思想，提出了一种基于c r c l 6 比 较的l o g i cb i s t 设计策略，有利于功能的全速测试。 在设计完成后以v c s 基础建立仿真环境，将本压缩器的v e r i l o g 代码进行 了仿真。仿真结果显示，该设计的压缩器可以正确地以l z w 算法实现数据的 压缩。用s y n p l i f y 以x i l i n x 的v i r t e x 4 为目标器件综合了本设计的r t l 代码， 证明资源占用情况是可以接受的。并且压缩器工作频率达到了2 1 0 m h z ，总的 数据处理能力达到7 5 0 m b p s 。处理性能比软件实现的处理能力快了2 0 多倍， 可以同市面上主流的硬件压缩器相媲美。 关键词：无损压缩v l s i 硬件字典压缩d f t 浙江大学硕士学位论文 a b s t r a c t t h ea p p l i c a t i o n so f l o s s l e s sd a t ac o m p r e s s i o ns p r e a dw i d e l yi nc o m m u n i c a t i o n , s p a c e f l i g h t , m e d i c a lt r e a t m e n ta n ds o m eo t h e rf i e l d s n o wt h ec o m p r e s s i o n i m p l e m e n t a t i o nr e a l i z e db yv l s it e c h n o l o g yi sg e t t i n gm o r ea n dm o r es i g h t sd u et o i t sm o r ep o w e r f u lp r o c e s s i n ga b i l i t y a n dt h er e s e a r c ho nv l s ic o m p r e s s i o n t e c h n o l o g yi sb e c o m i n g h o t t h i st h e s i sm a i n l yd e a l sw i t ht h ed e s i g na n di m p l e m e n t a t i o no fal o s s l e s sd a t a c o m p r e s s i o nc o r ei nh a r d w a r e t h ec o m p r e s s i o nc o i sb a s e do nl z wa l g o r i t h m t h et h e s i sr a i s e sas p e x i a la r c h i t e c t u r eo ft h el o s s l e s sd a t ac o m p r e s s i o nc o r e a c c o r d i n gt oc h a r a c t e r i s t i co ft h el z wa l g o r i t h m t h i sa r c h i t e c t u r e1 】s c sap a r a l l e l d i c t i o n a r ys e a r c h i n gs t r a t e g yw h i c hs p e e d su pt h es 血gs e a r c h i n gi nd i c t i o n a r y q u i t e l y m e a n w h i l e ab i gd i c t i o n a r yi ss p l i ti n t o8d i c t i o n a r i e sw i t hd i f f e r e n ts i z e , w h i c hs 口懈t h em e m o r ys p a c 硷a n dr e d u c e st h ec h i pr r e a as i m u l a t i o nm o d e l , w h i c hi su s e dt op r o v et h ec o r r e c t n e s so ft h ef u n c t i o n , i sd e s i g n e dw i t hc + + b a s e d o nt h ea r c h i 撇t h e nt h ec o m p r e s s i o nc o 糟i sd i v i d e dt om o d u l el e v e la n de v e r y m o d u l ei sd e s c r i b e dw i t hr t l l a n g u a g e ( v e r i l o g ) i nt h ed e s i g no ft h ed i c t i o n a r y m o d u l e ，i tu s eah i e r a r c h i c a ld e s i g nm e t h o d o l o g yw h i c hm a k et h ed i c t i o n a r yd e s i g n q u i t ec l e a ra n ds a v em u c hc o d i n ge f f o r t 1 1 艟c o n f i g u r a b l ec o n t r o lr e g i s t e rm o d u l ei s d e s i g n e d 协c o n t r o lv a r i o u sf u n c t i o no ft h ec o m p r e s s i o nc , o r e t h e s ec o n f i g u r a b l e r e g i s t e r sm a k et h ec o n t r o ls u b s y s t e ma n dd a t ap r o c e s s i n gs u b s y s t e ma p a r ta n da l s o i sh e l p f u lf o rt h ee x t e n s i o no ft h ef u n c t i o n 1 1 砖d e s i g no ft h ec o m p r e s s i o nc o r e r e f l e c t st h ed f tt h i n k i n g i td e s i g n sal o g i cb i s ts u - u c t u r ew h i c hb a s e do nt h e c r c l 6c h e c k e r n i sl o g i cb i s tc a nh e l pt h ef u n c t i o nt e s ta tf u l ls p e e d a f t e rt h ed e s i g no ft h ec o m p r e s sc o i ei sf i n i s h e d , t h es i m u l a t i o ne n v i r o n m e n t , w h i c hi sb a s e do nt h ev c ss i m u l a t o r , i se s t a b l i s h e d t h ed e s i g no f t h ec o m p r e s s i o n c o r ei ss i m u l a t e di nt h es i m u l a t i o ne n v i r o n m e n t t h es i m u l a t i o nr e s u l tr e v e a l st h a t t h ec o m p r e s s i o nc o r ec 缸c o m p r e s sd a t ac o r r e c t l ya c c o r d i n gt ot h el z w a l g o r i t h m t h es y n p i i 匆t o o li su s e dt os y n t h e s i st h er t lc o d eo f t h ec o m p r e s s i o nc o r e ，x i l i n x w m e x 4f p g aa st h et a r g e tf p g 九1 1 1 es y n t h e s i sr e s u l tr e v e a l st h a tt h er 髂o u r i s a c c e p t a b l e ，t h em a x i n l u n lf r e q u e n c yi s2 1 0 m h z s ot h et o t a ld a t ap r o c e s s i n ga b i l i t y r e a c h e st o7 5 0 m b p s ，w h i c hi st w e n t yt i m e sl a r g e rt h a ns o f t - w a r ei m p l e m e n t a t i o na n d c a nc o m p a r et o t h eo t h e rh a r d w a r ec o m p r e s s i o nc o r ei nm a r k e t k e y w o r d s ：l o s s l e s sc o m p r e s s i o n ，v l s i ，h a r d w a r e , d i c t i o n a r yc o m p r e s s i o n ，d f t n 一 浙江大学硕士学位论文 表格索引 表格2 - 1 几种无损压缩算法性能对比 表格3 一l 一个通用存储体的输入输出列表 表格3 2 一个存储页端口列表 表格3 - 3 一组四位地址和匹配信号的对应关系 表格3 - 4g e n _ a d d r _ l o w 信号列表 1 4 2 0 2 7 2 8 2 8 3 l 表格3 - 5d i c 2 5 6 _ i n d e xa d d r 模块的端口信号列表 表格3 - 6c o m p r e s s i o nr a t i o n i t s c h a r a o e r ) t 1 9 1 表格3 7 可配置寄存器列表 表格4 1c 抖模型的文件列表 表格4 _ 2d i c t i o n a r yc l a s sm e m b e rv a r i a b l e s 表格4 - 3d i c t i o n a r yc l a s sm e m b e rf u n c t i o n s 表格4 41 k 地址空间的几种典型划分方式 表格4 _ 5l k - 1 划分方式的压缩效果。 表格4 _ 6l k - 2 划分方式的压缩效果 表格4 - 7l k - 3 划分方式的压缩效果。 表格4 8l k - 4 划分方式的压缩效果。 表格4 - 9l k 5 划分方式的压缩效果。 表格4 - 1 0l k - 6 划分方式的压缩效果 表格4 - 1 1l k - 7 划分方式的压缩效果 表格4 - 1 2l k - 8 划分方式的压缩效果 表格5 1 时序分析 表格5 - 2 一组基于软件的处理能力数据 表格5 - 3 同其他硬件压缩器的对比 4 3 4 3 5 3 5 6 5 6 驺弘始仉饥钒铊铊铊铊 浙江大学硕士学位论文 图表索引 图表2 - 1l z w 算法流程刚1 蜘 图表2 - 2j p e g l s 编码流程【1 羽 图表3 1 总体框图d i c i 一第i 个字典 图表3 - 2 数据输入框图 图表3 - 3 字典框图。 图表3 - 4 一个通用e n t r yr t l 网表图 图表3 - 5 一个存储页m _ p a g e 的结构图示 图表3 62 5 6 x 2 字典的图示 图表3 7 地址编码流水线示意图 图表3 - 8 编码状态转换图 2 1 。2 4 图表3 - 9 字典序及c o d e 生成图示 图表3 1 0 可配置寄存器模块框图 图表4 - l 用c h 模型进行功能正确性测试 图表4 - 2 压缩比与字典划分方法的关系图 图表4 - 3 资源占用与字典划分方法的关系图 图表4 4 l f s r 电路结构 图表4 - 5b i s t 在系统中的位置及其构架 2 9 4 0 4 4 图表4 石并行算法生成c r c l 6 原理框图圆 图表5 - 1 验证环境结构图 图表5 - 2d e b u s s yo v e r v i e w t 2 5 l 图表5 3 仿真波形l 图表5 4 仿真波形2 图表5 - 5 仿真波形3 。 4 9 。5 0 图表5 - 6 综合后得到的顶层r 1 几视图 一v l 一 5 1 5 2 5 2 5 2 5 5 浙江大学硕士学位论文 第l 章绪论 1 1 课题研究背景及意义 现代社会是一个信息大爆炸的社会，纷繁复杂的信息导致了人们要面对海 量的数据。所以怎样快速高效的把数据压缩一直是人们追求的目标。 数据压缩广泛应用于各个领域。公司企业的数据的备份需要把大量数据压 缩以减少存储空间。为了充分利用信道，电视信号，流媒体等信息需要压缩。 卫星探测后传输数据需要高效压缩。 数据压缩通常分为无损压缩和有损压缩。对于不是很注重细节的数据如图 像、视频，人们大都采用有损压缩技术，如p e g ，h 2 6 3 ，h 2 6 4 等当今流行 的压缩技术。0 1 1 2 1 1 3 1 而对于像程序，电子档案等类似的重要信息，则必须采用无 损压缩技术。从而数据恢复时不会破坏其完整性。 人们对无损压缩技术的研究由来已久，其中最重要的无损压缩技术当属l z 系列的压缩算法和最小冗余度构造算法h u f f m a n 算法。当今的压缩技术基本基 于这些算法衍生而来。1 4 】1 5 i 6 1 u 1 然而，现在很多压缩解压方案都是基于软件实现。软件压缩解压有个致命 的弱点就是过多地消耗宝贵地c p u 资源、速度慢。特别是对于大批量数据压缩 解压时，其速度和c p u 资源占用率都是令人难以忍受地。虽然现在c p u 处理 速度不断提高达到了几个g ，但是还是不足于提高快速地实时地压缩解压。 现代v l s i 的发展使得用专用硬件的方式来压缩解压成为可能。用专用硬 件提供压缩解压可以解决上述软件压缩解压所存在的缺点。即它可以：l 、提高 了压缩解压的速度，有利于实时性处理；2 、节省了宝贵的c p u 资源。 $ j 1 9 1 1 1 0 1 1 1 1 】1 1 2 1 v l s i 的发展已经促使用于图像、视频等多媒体信息的硬件压缩解压器得到 了飞速的发展。各种手持设备中的多媒体芯片就是硬件解码的实际产品中的运 用。 然而在通用数据的无损压缩领域，基于v l s i 的硬件压缩解压方案还不多 见。而无损压缩恰恰在各个领域得到广泛运用。在医学图像处理、卫星探测， 大型数据备份领域都需要用到无损压缩。因此研究基于v l s i 硬件实现的无损 压缩技术具有很高的应用价值。 本课题就是在这种背景下产生的，它研究了如何实现基于v l s i 的硬件压 缩器，压缩的算法采用有利于硬件实现的l z w 算法。本课题的研究必将有利 于v 1 l 技术( 公司备份数据普遍采用的技术) 的发展，极大提高数据备份速度， 减少所用存储空间；必将有利于卫星探测数据、医用图像等数据的存储、传输。 浙江大学硕士学位论文 1 2 国内外研究现状和发展趋势 无损压缩技术伴随着信息技术的发展，已经称为信息技术中不可或缺的一 门技术，涌现出很多算法。l z 系列算法的优越性很快就在数据压缩领域里体 现了出来，使用l z 系列算法的工具软件数量呈爆炸式增长。u n i x 系统上 最先出现了使用l z w 算法的c o m p r e s s 程序，该程序很快成为了u n i x 世界 的压缩标准。紧随其后的是m s - d o s 环境下的a r c 程序，以及p k w a r e 、 p 豇址屺等仿制品。2 0 世纪8 0 年代，著名的压缩工具l h a r e 和a 1 u 则是 l z 7 7 算法的杰出代表。 今天，l z 7 7 、l z 7 8 、l z w 算法以及它们的各种变体几乎垄断了整 个通用数据压缩领域，我们熟悉的p k z i p 、w m z i p 、w m r a r 、g z i p 等 压缩工具以及z i p 、g i f 、p n g 等文件格式都是l z 系列算法的受益者， 甚至连p g p 这样的加密文件格式也选择了l z 系列算法作为其数据压缩的 标准。 然而目前能够获得的无损数据硬件压缩解压方案并不多，比较有代表性的 是h i f n 的9 6 3 0 芯片，它是基于l z s 算法的压缩解压芯片，也就是说用这个芯 片解压缩的数据必须是用这个芯片压缩的数据，或者是基于l z s 算法的软件压 缩后的数据。对于公司数据备份来说，用该芯片来压缩可以获得较高的压缩比， 减少存储空间，节约成本。然而l z s 算法比较复杂，所需要的硬件规模比较大， 需要用专门的a s i c 来实现。这就妨碍了这种芯片在中小规模客户中的普及。 j p e g l s 也是一种无损压缩的标准算法，然后它是针对连续图像的无损压 缩算法。虽然基于该算法的硬件压缩也有所运用，然而其只针对连续图像的特 点是的这种硬件压缩器运用范围现对狭小。1 1 3 l 基于j p e g 2 0 0 0 的d e m 数据无损压缩算法是一种数字高程模型( 一种应用 十分广泛的地形模型) 的数据压缩。该种算法的硬件实现也有相应的研究然 而类似于j p e g - l s ，它也是针对连续图像的无损压缩。 l z w 则相对要广泛些，它不但可以用于文本的压缩，还能用于图像的压缩。 两个常用的文件压缩格式：用于网站的g i f 图象格式和t i f f 图象格式，都是 用l z w 算法进行压缩的。因此实现基于l z w 的硬件压缩有实用意义。 虚拟磁带库v t l 技术是一种能够让整个系统将磁盘存储设备识别为磁带 设备的技术。它可以分别通过纯软件或软硬件相结合的方式来实现v i l 技术 商主要有n e t a p p ，s e p a t o n 等。目前用于数据备份的v t l 设备的需求庞大， 而y i l 一个重要功能就是整合了硬件压缩解压的功能，极大的提高了数据备份 的速度，提高了磁盘利用率，节省了成本，减少了c p u 占用率。 另一方面，现代社会大量数据需要传播，而信道带宽总是有限的，特别是 无线网络传播越来越重要，高带宽的无限网络技术发展缓慢。这就导致了对高 一2 一 浙江大学硕士学位论文 压缩比的压缩算法的需求不断增大。 在卫星测控方面有时候对于必须注重细节的图像，并不能运用传统的压缩 比较高的有损压缩技术来进行处理为了让卫星能够实时的不失真的传回图像 信息，就必须用压缩比较好的，压缩速度较快的硬件无损压缩技术。因此在卫 星测控方面硬件无损压缩技术也必将得到较好的发展。 基于以上几点的考虑，基于硬件的压缩解压的解决方案一定会越来越受孤 人们的关注和研究。 对于v l s i 实现的压缩器，最主要的是要利用硬件并行工作的提高处理速 度，并行度越高，处理速度就越高 2 0 3 。同时c a m 的运用也采用的主要方法之 一网。在这些设计中很多还采用了低功耗的设计方法嘲。有助于减少芯片封装 面积，并降低成本。 1 3 本文研究的主要内容 本文设计并实现了一种基于v l s i 实现的硬件压缩器，压缩的算法采用 l z w 算法。整个设计包括算法优化，体系结构设计，模块划分和模块的寄存器 传输级实现( 用v e r i l o gh d l 描述) ，b i s t 结构的设计，模块的单独验证，整 体的功能仿真，综合后的时序和面积分析，最后对所设计的硬件压缩器进行性 能上的对比评估。本设计基本涵盖了集成电路前端设计的所有过程。另外在代 码编写方面，本设计总共有v e r i l o g 代码5 8 0 0 行；码1 5 0 0 彳亍，另外还有 几个脚本。这个设计不但使得自己在集成电路前端设计流程的掌握上有了提高， 而且v e r i l o g 、c + + 的代码和脚本的编写方面的能力也得到了提高。 本文的几个创新点归纳如下： 并行的体系结构加快了字典搜索的速度，提高了数据处理能力 字典被拆分，每个字典宽度又是递增的。这样的组织方式丢弃了冗余 的字典空问，极大的减少了字典所占有的存储空间，减小了芯片面积 在综合考虑了实现难度和压缩效果的基础上，选择了字典填满后采用 的f i f o 更新策略，此策略硬件实现简单，且压缩效果中上 字典的设计采用层次化的设计方法，先设计一个具有基本功能的最小 单元，然后以此单元设计比较大的存储页，最后以阵列的形式完成各 个大小字典的设计。设计清晰明了，并且减少了r t l 代码量。 采用面向对象的c h 语言设计了基于l z w 算法和体系结构的仿真模 型，该模型作为压缩器的g o l d e n 模型。在分析由该模型获得的数据 的基础上确定字典的划分策略。同时该模型的数据可用于r t l 代码的 数据对比测试。 一3 一 浙江大学硕士学位论文 论文的结构如下： 第一章，绪论，介绍了论文的研究背景和意义，了解了目前国内外在硬件 压缩解压方面的研究现状，并提出了本论文的基本构架。 第二章，无损压缩的常用算法及其基本原理。介绍了几种常用的无损压缩 技术。分析了各自的特点，最后以列表的形式总结它们之间的差异，从而指出 为什么选择l z w 算法作为硬件加速的算法。 第三章，本压缩器体系结构的设计、模块的划分和具体的模块实现。l 、字 典设计策略，主要介绍8 个字典的设计方法。这里采用结构化的设计方法，从 最小的单元个存储体的设计开始，然后由存储体构成一个存储页，再由 存储页组合成不同大小的字典模块。结构化的设计方法减小了代码量，并且层 次清晰，结构明确。2 、并行的查找方法，指出有别于软件实现的一种并行的字 典搜索策略。3 、字典序和串地址的生成，介绍了如何用匹配标志信号成生字典 序和匹配串的地址，并且最终得到压缩的编码。4 、字典更新策略首先分析了几 种常见的策略，比较他们的复杂度和对压缩率的影响，然后基于他们的特点选 择了硬件易于实现而压缩率达到中上水平的f i f o 式的更新策略。5 ，可配置的 寄存器模块设计，这个设计包括了k g i cb i s t 控制寄存器的设计，数据保护 c r c 控制寄存器的设计和其它的一些控制寄存器的设计。这些控制寄存器的设 计有利于压缩器功能的扩展并且使得控制部分和数据通路的层次清晰明了。 第四章，仿真模型的实现和一些功能方面的测试，介绍了用c + + 实现仿真 模型的思路。在模型完成之后，分析了用模型产生的数据，并在此基础上确定 了字典划分策略，完善了体系结构。并提出了基于d f t 思想的l o g i cb i s t 测 试结构。 第五章，系统仿真和综合结果分析。证实了系统功能上的正确性。并对系 统的时序、面积进行了分析最后分析了本设计的性能并和软件实现的性能、 其他硬件实现的性能做了对比 第六章，总结和展望。概括介绍了全文的基本内容，总结了几个创新点 展望部分提出了几个今后可以改进的方面。 最后是本文所引用的参考文献和致谢。 一4 一 浙江大学硕士学位论文 第2 章基本原理及常用算法 2 1 信息量和信息熵 信息量是信息论的中心概念，信息量是指一个随机事件的不确定性，通常 用熵来度量。把熵最为一个随机事件的不确定性或信息量的度量，奠定了现代 信息论的基础。一个消息的可能性越小，其信息越多；消息的可能性越大，其 信息越少。信息论把一个事件( 如字符x i ) 所携带的信息量定义为： i ( x 1 ) = l 0 9 2 ( 1 以) ) = 一l 0 9 2 p ( x j x b i t ) i = 1 ，2 , 3 j l ( 2 1 ) 【1 4 1 其中p ( 五) 为事件发生( 字符五) 的概率。 信源x 的信息熵( e n t r o p y )日( 幻为 弓木，( ) = 一弓拳l o g p 2 2 lj = t ( 2 2 ) 1 4 1 2 2 有损压缩和无损压缩 有损压缩，也称失真度编码或熵压缩编码。也就是讲解码的数据和原始数 据是有差别的，允许有一定的失真。目前广泛用于图像，视频等多媒体压缩。 相应的标准有：k i p e g 2 ，m p e g 4 ，j p e g 2 0 0 0 ，h 2 6 3 ，h 2 6 4 ，a v s 等 有损压缩编码种类： 预测编码：d p c m ，运动补偿 频率域方法：正文变换编码( 如d c t ) ，子带编码 空间域方法：统计分块编码 模型方法：分形编码，模型基编码 基于重要性：滤波，子采样，比特分配，矢量量化 以h 2 6 4 作为例子来说，它主要包括运动补偿，交换编码，量化和熵编码 几个部分，信息地丢失主要发生在变换编码以后地量化阶段，它把那些人类眼 睛看不到地频率分量丢弃了，导致了信息地损失，从而称为有损压缩。也正是 因为这个信息量地丢失才使得h 2 6 4 有很好的压缩效果。 3 3 1 无损压缩指的是只去除信源中的冗余信息，而不影响信息熵，压缩后的信 息可以被原样恢复。最大限度的去除冗余信息是无损压缩追求的目标。 3 0 l 自从z i v 和l e m p e l 发表顺序数据压缩的通用算法以来，无损压缩技术得 到了飞速反展，各种压缩软件层出不穷各种不同的基于z i v 和l e m p e l 的衍 - - 5 浙江大学硕士学位论文 生算法也很多。我们把这些算法成为l z 系列算法。比较代表性的有1 2 7 7 ，l z 7 9 ， l z s ，l z w 等。无损压缩的另一方面是熵编码，最著名的有h u f f m a n 编码。h u f f m a a 编码是一种变长编码，它把信源中出现几率高的事件变成较短的码，出现几率 低的事件编成较长的码，从而在整体上缩短了信源编码的比特数。算术编码是 另外一种熵编码方法，它甚至能比h u f f i n a a 编码获得更好的压缩比，更大程度 的接近于信息熵的极限。但它的实现方法也更复杂，编码速度更慢。 1 2 7 7 ，l z 7 8 ，l z s - 都是基于字典压缩的类似的算法，有一个固定的滑动窗 口，用来匹配后面数据流中出现的字符串，如果匹配上，则用一个表示在滑动 窗口中的距离和匹配长度的数对来表示该字符串，从而达到数据压缩的效果。 在解压缩是也同样有一个相同大小的滑动窗口，当发现有匹配距离和匹配长度 的字符串时，则在滑动窗口中拷贝出相应的字符串。 l z w ：也是基于字典的压缩，从1 2 7 8 演化而来，然而它更巧妙也更有效率。 它在数据的压缩过程中动态地生成一个串表，以后的数据就可以同串表中的数 据相匹配，如果匹配上，则输出的是串表的索引。由于表示串表的索引所用的 比特数远小于串的比特数，从而达到压缩的效果。这个生成的串表不需要随着 压缩的数据同传输，而是能够根据压缩的数据在解压的时候重新动态的生成 一模一样的串表。 2 3 l z w 算法 2 3 1 优缺点概述 优点： l z w 算法通过对输入码流进行分析，自适应地生成一个包含输入流中 不重复字串地串表，将每一个字串映射为一个独立的码字输出这样， 它就充分利用了相邻输入数据之间地相关性。数字图像数据之间是高 度相关地，表现为存在大量局部相同性或相识性地数据，所以采用l z w 算法在无损压缩领域可以取得令人相当满意地压缩率。 在压缩过程中生成一个字典，当压缩结束后，该字典中的内容不需要 保存和传输，因为在解压的时候可以一模一样的生成压缩时产生的字 典。 相对于其他算法，l z w 算法是比较有利于用硬件来实现的。 缺点： 受缓存容量、计算复杂度和计算速度等因素地限制，串表地项数收到 一定限制。 串表要用m e m o r y 来存储，在面积的限制下，m e m o r y 的大小受到限制 一6 一 浙江大学硕士学位论文 l z w 算法是在字典建满时将其清空，重建，由于重建初期字典中地表 项很少，所以待压缩数据在字典中地匹配概率很低，导致字典重建初 期地压缩效果很差。但这可以通过改进替换策略来改善。 一7 一 浙江大学硕士学位论文 2 3 , 2l z w 算法基本流程图 图表2 - 1l z w 算p 去流程t m t l 日 一8 一 浙江大学硕士学位论文 2 3 3l z w 压缩算法描述 2 3 4l z w 解压缩算法描述 l z w 算法的解压缩需处理一种特殊的情况，并且随着压缩时串的替换策略 不同，解压时处理这种特殊情况的过程也略有不同。 一般情况下解压缩算法描述如下： 一般情况下上述解压缩算法可以很好的解出由l z w 算法压好的数据，然 而有一种情况例外。比如下面这个例子： 一9 一 浙江大学硕士学位论文 原是数据：a a b b b c 压缩后得到的编码用二进制表示为：0 0 0 1 1 0 0 0 0 10 0 0 1 1 0 0 0 0 10 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0o 0 0 1 l o 0 0 1 l 压缩过程中建立的字典： 2 个字符3 个字符 a ab b c a b b b 解压过程如下： 1 ) 获得第一个编码0 0 0 1 1 0 0 0 0 1 。前缀是o o ，所以在第一个字典中 ( d i e 0 ) ：后面8 位为0 1 1 0 0 0 0 1 ，所以输出字符a ( a 的a s c i i 码用二进制表 示为0 1 1 0 0 0 0 1 ) 2 ) 获得第二个编码，也是0 0 0 1 1 0 0 0 0 1 。同样输出字符a ，同时把字串 a a 加入到第二个字典中( d i e 0 。到此为止输出为a a 3 ) 获得第三个编码，为0 0 0 1 1 0 0 0 1 0 。前缀是o o ，所以也在第一个字 典( d i e 0 ) 中；后面8 位为0 1 1 0 0 0 1 0 ，所以输出b ；同时把字串a b 加入到 第二个字典( d i c l ) 中。到此为止，输出为：a a b 字典中的串为： a a 曲 4 ) 获得第四个编码，0 1 0 0 0 0 0 0 1 0 。前缀为o l ，所以在第二个字典中以 地址0 0 0 0 0 0 1 0 ( 当前c o d e 的后八位) 查找，地址为2 。但是我们发现第二 个字典中地址为2 的位置还没有存入字串。这种情况就是l z w 解压是会碰 到的一个特殊情况，这种情况可以通过下面的方法解决：把前一个输出的 字串加上加上前一个字串的第一个字符，作为当前要输出的字串所以输 出b b 。字典的更新也是一样：把前一个输出的字串加上当前输出的字串的 第一个字符加入到相应长度的字典中 所以到此为止输出：a a b b b 字典中的串为： a a a b b b 5 ) 获得第五个编码，0 0 0 1 1 0 0 0 1 1 。前缀为o o ，输出字符c ；同时用b b c l o 浙江大学硕士学位论文 ( 前一个输出字串加上当前输出字串的第一个字符) 更新第三个字典。 到此为止的输出： a a b b b c 字典中的串： 两个字符：三个字符： a ab b c a b b b 6 ) 解压结束 为了处理以上这种特殊的情况，所以修正了解压缩的算法，修正后的算法 描述如下： r o u t i n el z w _ d e c o m p r e s s l l 日 浙江大学硕士学位论文 2 4 l z 7 7 算法 l z 7 7 算法是目前无损压缩的一种主要算法，在z i p 和g z i p 的压缩中，主 要的算法都是d e f l a t e ，而d e f l a t e 算法实际上就是l z 7 7 算法和h u f f r a a n 的组合。 l z 7 7 算法是一种基于滑动窗口或称之为滑动字典的压缩。如果文件中有两 块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块 的内容。所以我们可以用( 两者之间的距离，相同内容的长度) 这样一对信息， 来替换后一块内容。由于( 两者之间的距离，相同内容的长度) 这一对信息的 大小，小于被替换内容的大小，所以文件得到了压缩。川 l z 7 7 从文件的开始处开始，一个字节一个字节地向后进行处理。一个固定 大小的窗口( 在当前处理字节之前，并且紧挨着当前处理字节) ，随着处理的字 节不断的向后滑动。对于文件中的每个字节，用当前处理字节开始的串，和窗 口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指窗口中每个字 节开始的串。如果当前处理字节开始的串在窗口中有匹配串，就用( 之间的距离， 匹配长度) 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一 个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做 改动的输出当前处理字节。 2 5h u f f m a n 编码算法 h u f f m编码是一种常用的编码方式，这里只做简单的介绍。 h u f f m a n 编码是一种可变长编码方式，是由美国数学家d a v i dh u f f m a n 创 立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转 换成长度较短的代码，而使用次数少的可以使用较长的编码，从而使得编码的 总长度最短。并且保持编码的唯一可解性，即h u f f m a n 编码是前缀码。嗍 用h u f f r a a n 算法构造一棵有n 个叶子( 每个叶子具有一个权值) 的二叉树 的过程如下： ( 1 ) 根据n 个权值 w l ，w 2 ，w n 构成n 棵二叉树的集合f - f t l ，t 2 ， t n ，其中每棵二叉树n 中只有一个带权为“的根结点，其左右子树均为空 ( 2 ) 在f 中选取两棵根结点的权值最小的树作为左右子树来构造一棵新 的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权 值之和。 ( 3 ) 在f 中删除这两棵树，同时将新得到的二叉树加入f 中。 重复( 2 ) 和( 3 ) ，直到f 中只含一棵树时为止称这棵树为最优二叉树 ( 或哈夫曼树) 如果约定将每个结点的左分支表示字符。0 ”，右分支表示字符“l ”，则可 一1 2 浙江大学硕士学位论文 以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的 编码。 对于所有可能传输的字符，令每个字符对应一个叶结点，权值为其出现的 频率，那么根据哈夫曼算法构造出二叉树后，就得到了每个字符的二进制编码。 根据构造过程可知，这种编码方案得到的字符的编码长度的数学期望值为 最小，因此这种编码方案是一个最优前缀码。在构造过程中，每次都是选取两 棵最小权值的二叉树进行合并，做出的是贪心选择。 在数据实际的压缩过程中，由于h u f f ：m a n 编码需要对各个字符进行统计， 得到概率分布，所以用硬件实现时需要一个比较大的缓存，且实时性处理比较 难。文献 1 7 】提出了面积充分利用的体系结构来实现h u f f m a n 编码。 2 6j p e g l s 中的l o c o i 算法 j p e g - l s 是i s 0 ，r 1 1 ，制定的针对连续灰度图像无损或近无损压缩的标准。 低复杂度无损图像压缩l o c o - i 是其中心算法。l o c o - i 作为主流的图像无损 压缩算法，在压缩效果上具有一定的优越性，并且复杂度低，适合用f p g a 实 现。 j p e g - l s 对图像的压缩模式主要有两种，即规则模式和游程模式。规则模 式采用的核心算法就是l o c o i ，游程模式会使硬件设计难度和复杂度大大增 加。因此规则模式用的较多。 以下给出了l o c o - i 编码处理步骤。同一般的基于上下文模式的预测编码 一样，l o c o i 编码主要包括3 个部分：预测、上下文建模和熵编码 图表2 - 2 i p e g - l s 编码流程f 1 研 一1 3 一 浙江大学硕士学位论文 2 7 小结 通过以上基本原理的介绍和几个算法的阐述，我们基本可以了解到现在无 损压缩的几个主流算法之间的差异。以下归纳了他们的特点，从而说明本设计 为什么采用l z w 算法进行硬件加速。 表格2 - 1 几种无损压缩算法性能对比 算法实时性 复杂度 存储面积压缩率适用场合 l z w 较好一般字典的面较好任何数据， 积，一般几特别适用 k全局或局 部相关性 好的数据 l z 7 7 较好一般窗口的面较好任何数据， 积，一般几特别适用 k于局部相 关性好的 数据 h u f f m a n需要预处 一般较大，需预很好任何数据 理，实时性存数据 差 j p e g l s 一般高一般较好连续灰度 图像的数 据 由此可见l z w 算法在实时性、复杂度、所需的存储面积、算法的压缩效 果和适用的场合方面都有不错的特点。因此以它作为硬件实现的算法 1 4 - - 浙江大学硕士学位论文 第3 章l z w 算法的基于v l s i 体系结构的设计和模块实 现 3 1 压缩器总体框图 d i c i ：第i 个字典； a d d ru p d a t e ：地址更新； d i cc o n t r o l ：字典控制；p a r a l l e ls e a r c h ：并行搜索； p i p e l i n ee n c o d e ：流水线编码d a t aa l i n e ：数据排列 图表3 - 1 总体框图 3 2 硬件实现和软件实现的区别 l z w 算法软件实现的流程在第二章中已经介绍。该算法中主要的一步是判 断新串是否在已经建立的字典中，即字典的搜索工作。软件中采用了一个基于 h a s h 算法的搜索过程。即将新串执行某一个h a s h 算法，得到一个索引值，用该 索引作为地址去字典的相应位置查找，在这个位置中可能有好几个串，逐个同 这几个串进行比较，如果某一个串同新串匹配上则说明新串在字典中搜索到， 否则新串不在字典中。该算法保证新串能够快速地在字典中搜索，而b a s h 算法 确实提高了搜索速度，但是h a s h 算法也是有缺点地。那就是几个不同地串有可 能算出来的是同一个索引值，而且这个概率很大。这样新串就要同他们线性的、 逐个的比较，大大影响了搜索速度。 以下是软件实现中一个用h a s h 算法查找字串的程序：i l q 一1 5 浙江大学硕士学位论文 可以看到在上面的w h i l e 循环中，它逐个搜索字串，直到找到匹配的。在 硬件实现的方案中采用了并行的查找方法，即新串同时跟字典中所有的串比较。 这是一个组合逻辑，可以在一个时钟周期内完成。得到的是一些匹配标志信号， 再对这些匹配标志信号进行编码处理就可以知道哪个字典中的哪个地址中的串 被匹配上。这个过程在字典序和匹配串地址的生成一节中有详细的介绍。为了 时序上的要求，这个对匹配标志信号的编码过程可以适当地在几个时钟内完成， 但这也比软件的顺序查找快了很多。 软件实现中还有一个影响速度的因素，那就是每次s 啊n g 的更新只接受一 个字符。即 s t r i n g = s t r i n g c h a r a c t e r 这里c h a 捌：i c r 总是代表一个字符 在硬件的实现方案中每次总有8 个字节的数据同时在字典里搜索，依据搜 一1 6 一 浙江大学硕士学位论文 索到的结果用一个b a r r e ls h i f t e r 将匹配到的数据移出。然后未匹配到的数据同 后面的几个数据再组合成一个8 字节的串在字典中搜索。这种处理方法比每次 只增加一个字节的方法快了很多。 在字典的组织结构上，软件实现是在一开始就分配了固定的内存空间，由 于不知道实际的处理情况，所以总是预分配最大可能的内存空间，这种方法往 往会浪费很多的内存。在硬件实现上采用不等长的字典策略很好的节约了存储 空间。这一点将在字典设计策略一节有详细介绍。 3 3 体系结构的划分 该体系结构主要划分为数据输入，数据处理，数据输出三个部分，其中核 心在于数据处理部分。数据输入部分主要是一个缓冲f i f o 和一个移位寄存器； 数据输出部分主要是一个输出存储器；核心部分数据处理部分又可以分为以下 几个部分： 1 ) 字典模块，所有的字串都存储在字典中，共有8 个字典( 一个虚拟字 典) 2 ) 并行搜索部分，并行搜索实际上整合在字典模块中，这里在功能上将 它从字典部分区别开来 3 ) 流水线编码部分