（信号与信息处理专业论文）远程示波器波形实时显示技术研究.pdf

摘要 摘要 随着科技的发展，雷达电子战发展到了一个新的阶段，被动侦测系统在军 用任务中扮演着越来越重要的角色，日益受到各国的广泛关注。在被动侦测系 统中，由于辐射源目标信号越来越复杂，往往需要通过观察辐射源目标的实际 信号波形来进行验证和辅助人工判断，并为下一步数据处理提供依据。中频波 形实时显示是被动侦测系统的一项重要内容，对中频波形实时显示控制技术进 行研究，在工程应用中具有现实意义。 本文正是结合实际要求和现有的技术条件，提出了一种将波形实时传输的 硬件实现方案，并在此基础上完成了系统的设计和联调测试。该系统采用f p g a 为核心控制芯片，主要由视频采集模块、视频存储模块以及视频传输模块组成。 视频采集模块将前端接收的示波器和频谱仪图像经v g a 输出后，通过压缩算法 进行传输带宽的压缩，后端通过视频传输模块与主机以及视频合成系统进行通 讯。 由于采用了l z w 压缩算法，因此硬件实现起来比较方便，本文采用了软硬 件联合仿真技术，加快了软件算法向硬件实现的转换速度，大大加快了工程的 进度。在视频压缩模块中，提出了将c a m 存储器与压缩算法结合起来的码表 搜索方法，极大提高了数据压缩的速率，满足了工程的需要。 本文首先介绍了系统的总体方案设计，然后分别从系统的硬件设计、算法 的优化改进以及f p g a 逻辑设计三部分，详细介绍了视频传输系统的实现方法， 最后给出了系统测试的结果。通过实验证明，该系统实现了波形显示控制的主 要功能，达到了预期目标，具有实际工程应用价值。 关键字：视频数据，实时波形显示，f p g a ，l z w 9c a m ，千兆以太网 南京信息工程大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n i q u e s ，r a d a re l e 圮t r o n i cw a rh a sb e e np r o m o t e dt o an e ws t a g e p a s s i v ed e t e c t i o ns y s t e mp l a y sam o r ea n dm o r ei m p o r t a n tr o l ea ta m i l i t a r ym i s s i o n d u et ot h et a r g e ts i g n a le m i t t e rm o r ea n dm o r ec o m p l i c a t e di nt h e p a s s i v ed e t e c t i o ns y s t e m ，w eo f t e nn e e dt oo b s e r v er a d i a t i n gs i g n a lw a v e f o r mo f t h e a c t u a lt a r g e tt ov e r i f yt h ea u t h e n t i c i t yo ft h et a r g e t , w h i c hp r o v i d e sb a s i sf o rt h en e x t d a t ap r o c e s s i n g r e a l - t i m ed i s p l a yf o ri n t e r m e d i a t ef r e q u e n c yw a v ei np a s s i v er a d a r s y s t e mi sa c c u s e do fa l li m p o r t a n tc o n t e n t , t h es t l l d yo fw h i c hw i l lp r o v i d et h e p r a c t i c a la p p l i c a t i o nv a l u e ， c o m b i n i n gw i t h a c t u a l r e q u i r e m e n t sa n d t h ee x i s t i n gt e c h n o l o g y , t h i s d i s s e r t a t i o np u t sf o r w a r dar e a l - t i m et r a n s m i s s i o ns c h e m ef o rt h ew a v e f o r mb a s e do n h a r d w a r e ，a n dt h i sp r o j e c tc o m p l e t e dj o i n td e b u g g i n ga n dc a m et r u e t h i ss y s t e m b a s e d0 1 1f p g aa st h ec p u ，i sc o m p o s e do fv i d e oc o l l e c t i o nm o d u l e ，v i d e os t o r a g e m o d u l ea n dv i d e ot r a n s m i s s i o nm o d u l e sm a i n l y t h ev i d e oc o l l e c t i o nm o d u l eo u t p u t s t h e i m a g e s o ft h eo s c i l l o s c o p ea n dl 臣e q u e n c y s p e c t r o g r a p h t h ei m a g e sa r e c o m p r e s s e db yt h el z wa n dt r a n s f e r r e dt ot h ec o m p u t e rb yt h ee t h e r n e ta n da n o t h e r v i d e os y n t h e s i sm o d u l eb yt h eo p t i c a lf i b e r i t i sc o n v e n i e n ti nt h eh a r d w a r ei m p l e m e n t a t i o nb e c a u s eo ft h el z w ：t i l i s a r t i c l eu s e st h et e c h n o l o g yo fs o f t w a r ea n dh a r d w a r ec o m b i n e ds i m u l a f i o n ，w h i e l l a c c e l e r a t e dt h er e a l i z a t i o no fc o n v e r s i o nf r o ms o 伺c v v a r ea l g o r i t h mt oh a r d w a r e i m p l e m e n t t h i sp a p e rp u t sf o r w a r dam e t h o dt oa c c e l e r a t et h em e m o r ys e a r c hs p e e d u s i n gt h ec o n t e n ta d d r e s sm e m o r y ( c a m ) ，w h i c h m e e t st h en e e do fe n g i n e e r i n g t l l i sp a p e ri n t r o d u c e st h eo v e r a l ld e s i g no ft h es y s t e ms e p a r a t e l y 鼬t h et h r e e p a r t s ：t h es y s t e mh a r d w a r ed e s i g n , t h el z wa l g o r i t h mo p t i m i z e da n di m p r o v e d , f p g al o g i cd e s i g n i k ss y s t e mr e a l i z e dt h ew a v e f o r md i s p l a ya n dc o n t r o la n d a c h ie v e dt h ee x p e c t e dg o a lw i t hp r a c t i c a le n g i n e e r i n ga p p l i c a t i o nv a l u e k e y w o r d s ：v i d e od a t a , r e a l - t i m ed i s p l a y , f p g a , l z w , c a m ，g i g a b i te t h e a n e t 学位论文独创性声明 本人郑重声明： 1 、坚持以搿求实、创新一的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名：必 日 期： 五纽 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有 关数据库进行检索；有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 作者签名： 日期： 第一章绪论 第一章绪论 1 1 研究背景和意义 本课题是某新型被动侦测系统显示技术研究项目中的一部分。在该系统中，由于辐射 源目标信号越来越复杂，往往需要通过观察辐射源目标的实际信号波形来进行验证和辅助 人工判断，并为下一步数据处理提供依据，同时，由于设备配置的原因，需要实现远端的 信号波形显示u 。因此有必要研究将远程示波器的波形通过光纤传输以及千兆以太网在本 地机上进行实时显示的实现方法，并且实现对远程示波器的控制。 由于科学技术的日益发展，数字示波器要处理的波形数据越来越大，由于数据传输带 宽和存储空间有限，用户不能把重要的波形数据按原样传输和存储下来，需要在传输和存 储前对波形数据进行压缩，以节省带宽和存储空间，因此数据压缩技术在工程上有很大的 需求背景。 目前，数据压缩技术已经广泛的应用到各种软件产品中，譬如w i n z i p z i p - m a g i c 等压 缩解压缩工具，另外，在一些技术规范和影像格式中，数据压缩技术也比比皆是，如浏览 的g i f 和j p e g 压缩格式图片，还有m p 3 格式压缩音乐，可见压缩技术应用时非常广泛的。 尤其在数据率与带宽的矛盾如此尖锐的情况下，压缩技术更是必不可少的拉1 。 数据压缩一般按压缩的可逆性分为有损压缩和无损压缩，对于不注重细节的数据，通 常采用有损压缩，而对于不希望有数据丢失的示波器图像数据，通常采用无损压缩算法。 无损压缩技术的研究由来已久，最为重要的当属l z 系列压缩算法，以及最小冗余度构 造霍夫曼算法。目前常用的压缩技术基本上都是基于这两种算法衍生而来。但是，很多压 缩解压缩方案都是基于软件实现的，是通过软件的后处理实现的。软件实现有两个极大的 缺点，那就是严重消耗宝贵的c p u 资源、执行速度慢，有的算法很难用硬件来实现。当处 理大量数据时，其运行速度和c p u 占用率都让人难以接受。虽然当前c p u 已经进入到了多 核的时代，处理速度不断提高，但对于实现快速实时的压缩解压缩来说还是比较困难。 采用硬件实现数据压缩与软件实现有许多不同之处。用硬件方法实现数据的实时无损 压缩，能够将高速信号变成缓变信号进行传输，降低通信的信道容量，提高数据的可靠性， 具有重要的意义。然而，在当前通用数据无损压缩领域中，采用硬件实现的方案还不多见。 鉴于无损压缩技术在各个领域中的广泛应用，研究基于硬件实现的通用数据无损压缩器具 有很重要的意义h 1 。 本课题为解决这一问题：示波器和频谱仪的波形数据进行无损压缩经过以太网和光纤 传输给后端操控显控台，压缩和解压过程中速度快且不要消耗太大的临时存储空间，采用 有利于硬件实现的l z w 算法，立足于现有成熟技术，结合原有的工程背景，对示波器和频 谱仪波形实时显示控制技术进行了深入研究，并且利用f p g a 的结构设计出一种并行查询结 南京信息工程大学硕士学位论文 构的存储器，能够满足工程的实时性要求。 1 2 论文的工作内容安排 本文在研究被动侦测系统中频信号波形实时显示控制基础上，设计出了一种基于f p g a 和以太网以及光纤的波形数据传输系统，主要内容有： ( 1 ) 完成了包括视频传输模块，视频合成模块，前端操控显控台，后端操控显控台的总 体方案的设计，采用a l t i u md e s i g n2 0 0 8 实现了视频传输模块功能。 ( 2 ) 完成了l z w 算法的m a t l a b 仿真，证明其压缩率可满足其工程的需要，并利用l i n k f o rm o d e l s i s 完成了软硬件的联合仿真。 ( 3 ) 对l z w 算法进行改进，使其更适合硬件实现。并且利用硬件资源设计出基于c a m 的快速查表方法，满足了数据传输的实时性要求。 ( 4 ) 完成了模块的调试，验证了a d 采集，视频压缩，以太网，以及光纤传输模块的功 能，示波器和频谱的图像最终能够达到l ：3 0 和l ：5 0 的压缩比。 1 3 论文的结构安排 论文具体研究了示波器和频谱仪波形图像数据的压缩和传输，共分七章，基本结构如 下： ( 1 ) 第一章为绪论，概括了本文研究背景和实际意义，介绍了作者的主要研究工作和 论文章节结构安排。 ( 2 ) 第二章为模块的总体方案设计，介绍了模块基本工作原理功能和技术指标要求。 ( 3 ) 第三章为视频传输系统的硬件设计，介绍了系统各模块器件的选择和硬件电路搭 接。 ( 4 ) 第四章为l z w 算法的详细介绍，首先介绍其基本原理，然后根据其硬件设计的基 本特点完成对l z w 算法的改进，并且在码表的构成方式，码表的刷新方式以及码表的查询 方式上提出来新的见解。 ( 5 ) 第五章为c a m 的详细介绍，提出了一种在硬件基础上加快码表查询速度的切实有 效的办法，使其能够满足工程实时性要求。 ( 6 ) 第六章为l z w 算法的软硬件联合仿真以及硬件设计中各个模块v h d l 程序的实现， 给出整个系统的联合调试情况和结果。 ( 7 ) 第七章为总结和展望，介绍了论文研究所取得的成果以及还存在的不足，并且对 压缩率方面的改进提出了新的想法。 2 南京信息i 程太学硕士学位论文 第二章总体方案设计 2 1 系统基本工作原理 蕃：p 刊i _ _ i ! i i i i i ； ：；： ：；：蜊卜。 #i 仁函 二幂磐 占占 。丛二画馏 图2 - 1 系统基本原理框图 整个波形实时显示原理框图如图2 - 1 所示，其工作流程为：将从示波器和频谱仪采集 到数据一路经由信号显示机柜中的视频传输模块通过网络传递给后端操控显控台。另外一 路通过光纤传输给前端操控显控台，然后将得到的视频数据与显示器数据进行叠加，最终 返回到前端操控显控台界面，完成视频数据的台成。 示波器采用d s 0 5 0 3 2 a 性能如下 4 ： ( 带宽3 0 0 删z ，通道数为两路，最高采样率为2 g s a s ，存储深度最高达i m p t s ， 每通道5 0 0 k p t s ； ( 2 ) 标准接口为u s b 20 高速设别接口两个u s b l1 主机端口，1 0 1 0 0 一b a s e t l a n 网 络接口，i e e e 4 8 82 g p i b ，x g a 视频输出接口； ( 3 ) 外形尺寸：宽3 854 c m 高1 88 c m 十深1 74 c m ( 有手柄) ，净重4 1 k g ； ( 4 ) 最高功率1 1 0 w ，工作温度为一i o c 至+ 5 5 ，工作湿度为9 5 础。 频谱仪主要接收数控计算机的控制完成对微波信号的采样显示，并通过网络将数据送 操控计算机进行波形显示性能如下： ( 1 ) 频率范围：9 k h z 至3 g h z ，a c 耦台，设置分辨翠为l o o k h z 至3 g h z ： ( 2 ) 频率扫宽范围：i o o h z 至3 g h z ，分辨率1 h z ，幅度测量范围：i o m h z 一3 g h z ； ( 3 ) 显示至+ 3 0 d b m 的平均噪声级：1 m h z l o 4 z ：d a n l 达2 3 d b m ；9 k h z1 e 4 z ：d a n l 达 2 0 d b m ，输入衰减器范围为o d b 至7 0 d b ，以1 d b 步进； 第二章系统的总体方案设计 ( 4 ) 标准接口是u s b 接口、l a n t c p i p 接口、v g a 输出模拟r g b 屏幕，电源功耗 p i * i ( x o = 一 r 宰i o g p ； ( 1 2 ) _ 一 一 一 ，= li = 1 信源经常由于事件相关或概率分布不均匀等原因，而使实际的熵小于其最大墒，这样 南京信息工程大学硕士学位论文 就产生了信息的冗余。冗余度r 定义为 月：1 一生四： h m a x ( x ) ( 1 - 3 例如英文2 6 个字母，其出现的频率差异很大。字母e 和空格的频率最高，而字母x 和 z 出现次数得最少。据字频统计表可算出英文每个享母所携带的平均信息量为 爿似) = 一y p i l o g p i = 4 0 3 ( 位字母) ： ( 1 4 ) r 英文由2 6 个字母和一个空格组成。它的最大熵为： h m a x ( x ) = l o g n = 1 0 9 2 7 = 47 6 ( 位字母) 。 ( 1 - 5 ) 4 2 压缩算法分类 数据压缩的分类方法繁多，仔细分可达3 0 至4 0 种，到目前为止尚未统一。多数学者 认同的比较一致的分类方法，就是将数据压缩分为在某种程度上可逆的与实际上不可逆的 两类，这样更能说明它们的本质区别。 ( 1 ) 可逆压缩 可逆压缩也叫做无损编码或无噪声编码，而不同专业的文献作者还采用了另外一些术 语，比如冗余度压缩、熵编码等等。香农在创立信息论时，提出把数据看作是信息和冗余 度的组合。冗余度压缩的工作机理是去除那些可能是后来插入数据中的冗余度，因而始 终是一个可逆过程。无损编码一般包括霍夫曼编码、游程编码、算术编码和l z 编码，主要 用于对数据要求高，不允许失真的场合。霍夫曼编码理论压缩比最高，但压缩和解压时间 长，适用于大量数据的压缩。相对于有损压缩，无损压缩技术只是去除信源中存在的冗余 信息，而不破坏信息熵，压缩后的数据进行解压缩时可以按原样恢复。最大限度的去除冗 余信息，而不是丢弃有用的数据。 ( 2 ) 不可逆压缩 不可逆压缩就是有损编码，信息论中叫熵压缩。主要用于图形和音频信号的压缩，压 缩率较高，但不能完全无失真的恢复出原始数据。压缩后的数据给人感觉与原始数据相差 不大，利用了人娄生理上视觉、听觉等的分辨能力不高的缺点。 图4 - 1b m p 与g i f 图像比较 3 0 第四章压缩算法 如上图所示，虽然两幅图看起来差别不大，但是两幅图所包含的数据量具有很大的差 别。第一幅图像的大小为3 3 k ，而第二幅图像的大小只为1 5 k ，通过人的肉眼很难分别出两 幅图像的差别，正式因为第二幅图像去除了人眼不太敏感的高频部分数据。 目前较为实用的数据压缩技术有： ( 1 ) 预测编码：d p c i l ： ( 2 ) 运动补偿模型方法：分形编码模型基编码： ( 3 ) 频率域方法：正文变换编码( 如d u r ) ，子带编码； ( 4 ) 空间域方法：统计分块编码。 4 3 几种压缩算法的介绍与比较 ( 1 ) h u f f m a n 编码：h u f f m a n 码是一种变长编码，它把信源中出现概率高的信息编成较 短的码，出现概率的信息编成较长的码，从而在整体上缩短了信源编码的比特数。这种方 法首先把所有的字符按概率降序排列，建立列表。然后由上至下构造一棵树，每片叶子放 一个字符。具体做法是：每一步都找出两个概率最小者相加用一个辅助符号表示，置于该 子树的顶部，同时把这两个字符从列表中删去；如此继续，直到列表中只剩一个辅助符号 ( 代表所有字符) ，这样就完成了树的构造。然后由树来决定每个字符码字。 优点：是压缩率高，实时性好，运算快，易于硬件实现。压缩率受缓存容量、计算发 杂度和计算速度等因素的限制。适应于任何数据，特别是全局或局部相关性好的数据。它 是整数编码的一种最佳码，即它的平均码长在具有相同输入概率的前提下，比其它任何一 种唯一译码都短。同时它也是一种前缀码，具有唯一可解性。 缺点：其一是不同的信源中，信源符号的概率分布有可能相差甚远，很难用一或几张 码表来编译不同的信源。 ( 2 ) 算术编码：是一种高效高性能的熵编码方式，其思想是用区域划分来表示信源输 出序列。信源输出的任何一种组合都与 0 ，1 ) 区间的某一区域对应。其基本原理就是从一 个初始区间 0 ，1 ) 开始，逐次扫描符号序列，根据信源符号出现的概率划分区间而得到新 的起始区间，如此反复，最终得到一个小的区域，该区域和信源输出对应，可在该区域中 任取一点，其二进制小数就代表了最后的信源编码，且这个编码是唯一可解。算术编码也 是一种嫡编码方法，它能够获得比h u f f m a n 编码更好的压缩比，最大程度的接近信息熵的 极限。 优点：是压缩率接近压缩的理论极限。 缺点：是需要浮点乘法器，计算量比较复杂，不利于硬件实现。适用于由相同的重复 序列组成的文件。 ( 3 ) 游程编码：对压缩的数据进行动态扫描，即要先将压缩的数据进行存储，然后将 具有相同数据的代码段用相同数据的个数加数据量来表示。 3 1 南京信息工程大学硕士学位论文 优点：算法简单，适合于硬件实现。 缺点：压缩速度慢。实时性差，适用于较多相邻重复的数据结构，更大的缺点还包括 在压缩之前，为了不对压缩的数据造成混叠，这就要求对大于某个值的数据用两个个字节 来表示，无形中加大了数据量，所以游程算法在压缩率方面并不是很理想。 ( 4 ) 基于小波变换的数据压缩：小波编码是一种特殊的子带编码方法。子带编码方法 使用不同类型的一维或二维线j 型数字滤波器，对数据进行整体的分解，然后根据信号特 性和人类视觉特性对不同频段的数据进行租细不同的量化处理，以达到更好的压缩效果。 由于子带编码是对整个信号进行的，因此不存在方块效应。在此方法中，合理地选择和设 计正交镜像滤波器组( q 灯) 是实现中的关键。小波变换( w t ) 和子带分解的根本区别是小波滤 波器是正则的，具有一定的光滑性。 优点：压缩率高，适合于图像和视频压缩。 缺点：算法比较复杂，硬件实现起来难度很大。 ( 5 ) 基于神经网络的编码：神经网络法是模仿人脑处理问题的方法，通过各种人工神 经元网络模型对数据进行非线性压缩。人工神经网络是一个非线性动态网络，工作过程一 般分训练和工作两个阶段。训练阶段就是使用一些训练图像和训练算法，调整网络的权重， 使重建图像的误差最小。目前直接用于图像压缩编码的神经网络主要有反向误差传播( b p ) 型和自组织映射( k o h o n e n ) 型。 优点：具有良好的容错性、自组织和自适应性，适用于图像压缩。 缺点：不同特征图像压缩差别较大。 本文研究的是视频传输系统中采集到的示波器和频谱仪的数据，一方面，由于视频的 分辨率和刷新率都比较高，模拟信号经过a d c 后输出的位数比较宽，因此需要采集压缩的 数据量比较大；另一方面，采集到的数据前后相关性比较强，而且对传输的数据进行压缩 处理后，还要无失真的恢复出原始数据。所以本文应采用无损数据压缩算法进行数据压缩。 在各种无损压缩算法中，既要满足具有较高的压缩比，又要算法复杂度低且便于f p g a 硬件 实现。通过上表比较，在诸多数据压缩方法中，基于字典的l z w 无损数据压缩算法比较适 合于本课题的要求嵋“。 4 。4l z w 压缩编码的发展历史及其算法介绍 自从z i v 和l e m p e l 发布顺序数据压缩的通用算法以来，无损压缩技术得到了飞速广泛 地反展，各种相应软件也层出不穷，由此演变而来的不同的基于z i v 和l e m p e l 的衍生算法 也很多。比较著名的有l z 7 7 ，l z 7 8 ，l z s ，l z w 等，这些并称为l z 系列算法。 l z 7 7 ，l z 7 8 ，l z s 都是基于字典压缩的类似的算法，它们有一个固定的滑动窗口字典， 用来匹配在后面数据流中出现的字符串。如果匹配上，则用一个表示在滑动窗口中距离和 匹配长度的数对来表示该字符串，从而达到数据压缩的效果。在解压缩时也同样有一个相 同大小的滑动窗口，当发现有匹配距离和匹配长度的字符串时，则在滑动窗口中拷贝出相 第四章压缩算法 应的字符串。l z w 也是基于字典的压缩算法，从l z 7 8 演化而来，但是它更巧妙也更有效率。 它在数据的压缩处理过程中动态地生成一个串表，需要压缩的数据同字符串表中的数据进 行匹配比较。如果匹配上，则输出串表的索引。由于表示串表索引所用的比特数远小于字 符串的比特数，从而达到很好的压缩效果。生成的串表不需要随着压缩的数据一同传输， 而是根据压缩的数据在解压的时候重新动态的生成一模一样的串表。 对于通用数据的压缩，初始化串表时，0 2 5 5 ( o f f h ) 存放单个字节所有可能的取 值( 即8 位的a s c i i 字符集) ，2 5 6 ( 1 0 0 h ) 作为开始码。l z w 算法的字典是自适应生成的， 在实际应用中，若无限制地增大字典的容量，虽然可能获得更好的压缩率，但进行字符串 匹配时查找的时间会变长，并且随着编码的码字位数增加，有时可能会导致压缩效率降低， 影响压缩速率，因此字典的容量要受一定的限制。下图4 2 为l z w 算法的压缩流程图： 图j ：上缩流程图 l z w 编码算法的具体实现过程如下； i n i t i a l ：将所有的单字符串放入字符串表； 读第一个输入字符到前缀p ： s t e p ：读入下一个输入字符c ； i f 没有这样的c ( 输入已穷尽) ： 码字p 输出； 结束； i f 字符串p + c 已存在与字符串表中： p + c 赋给p ； r e p e a ts t e p ； e l s ep + c 不在字符串表中： 码字p 输出； p + c 加入串表； c 赋给p ： r e p e a ts t e p 。 3 3 南京信息工程大学硕士学位论文 由于本项目中所用到的数据是将从示波器和频谱仪传出来的视频数据经过a d 采样后 变为8 位数字信号，大小为0 至2 5 5 ，同时将2 5 6 作为压缩开始的标志位，因此码表中索 引项为2 5 6 的位置不存储数据，而是从索引项为2 5 7 的位置开始存储字符串。 举例说明：o l h ，0 2 h ，0 2 h ，0 2 h ，0 3 h ，0 3 h ，o l h ，0 2 h ，0 2 h ，0 2 h ，0 4 h 建立的码表如下表4 - 2 步骤输入表项索引字符串表输出 0 0 ho o h o l h 0 l h 0 2 h0 2 h 0 3 h0 3 h lo l h 20 2 h 1 0 l ho l h 0 2 h 0 1 h 30 2 h1 0 2 h0 2 h 0 2 h0 2 h 40 2 h 50 3 h1 0 3 h0 2 h 0 2 h 0 3 h1 0 2 h 60 3 h1 0 4 h0 3 h 0 3 h0 3 h 7o l h1 0 5 h0 3 h o l h 0 3 h 80 2 h 90 2 h1 0 6 ho l h 0 2 h 0 2 h1 0 l h 1 00 2 h l l0 4 h1 0 7 h0 2 h 0 2 h 0 4 h1 0 2 h 表4 - 2l z w 压缩码表与输入输出数据 由此可见，输入码流经过压缩后输出的码流为：0 1 h ，0 2 h ，1 0 2 h ，0 3 h ，0 3 h ，1 0 1 h ， 1 0 2 h ，而压缩所需的字典是在压缩过程中自适应生成的。实际生成的字典如下表4 3 字典 o 2 5 62 5 72 5 82 5 92 6 02 6 12 6 2 项 2 5 5 字典 0 l ，22 ，22 ，2 ，3 ，33 ，l1 ，2 ，2 词条 2 5 53 表4 3l z w 压缩动态形成的字典条目 下图4 3 为解压缩算法流程图； 第四章压缩算法 图4 - 3l z w 解压缩流程图 初始化：将所有单字符串放入字符串表； 读入编码数据流中的第一个码字给一 c w ( 当前码字) ； 与四对应的字符串输出一 输出； s t e p ：使p w ( 先前码字) = c w ： 读入编码数据流的下一个码字一 c w ； i f 与c w 对应的字符串在字符串表中： 将该字符串一 输出； 该字符串的第一个字符- g 与p w 对应的字符串- p ； p + c 一 串表； e l s e 与四对应的字符串不在字符串表中： 与p w 对应的字符串- p ； 与p w 对应的字符串的第一个字符一 c ； p + c 一 串表： p + c 输出； 编码数据流中还有码字吗? y e s ：r e p e a ts t e p ： n o ：结束。 同样以刚剐经过压缩后的数据流为例子进行解压缩，下表4 4 为解压缩过程中形成的 码表： 南京信息工程大学硕士学位论文 步骤输入 表项索引字符串表输出 o o ho o h o l h0 1 h 0 2 h0 2 h 0 3 h0 3 h 0 4 h0 4 h 1o l h o l h 2 0 2 h1 0 1 ho l h0 2 h0 2 h 3 1 0 2 h1 0 2 h0 2 h0 2 h0 2 h0 2 h 4 0 3 h1 0 3 h0 2 h 0 2 h 0 3 h0 3 h 50 3 h1 0 4 h0 3 h 0 3 h0 3 h 6l o l h1 0 5 h 0 3 h o l h0 1 h0 2 h 71 0 2 h 1 0 6 ho l h 0 2 h 0 2 h0 2 h0 2 h 表4 - 4l z w 解压缩码表与输入输出数据 通过解压缩程序可以看出，如果输入为0 1 h ，0 2 h ，1 0 2 h ，0 3 h ，0 3 h ，1 0 1 h ，1 0 2 h 则可以自动还原出原始的字符串为o l h ，0 2 h ，0 2 h ，0 2 h ，0 3 h ，0 3 h ，o l h ，0 2 h ，0 2 h ，0 2 h ， 可见，解压缩程序能够无损解压出原有的字符串，解码程序和编码程序动态生成了相同的 字典( 解压缩形成的字典如表4 - 5 ) ，这给程序的编写带来了极大的方便。但是有一个问 题值得注意，解压缩程序比压缩程序晚一个字符，这需要输入下一个代码才能够还原出原 字符串来。 字典项 0 2 5 62 5 72 5 82 5 92 6 02 6 12 6 2 2 5 5 字典 o 1 ，2 2 ，22 ，2 ，33 ，33 ，1l ，2 ， 词条 2 5 52 表4 - 5l z w 解压缩动态形成的字典条目 4 5l z w 压缩算法的优缺点及其改进 4 5 1l z w 算法优点 第四章压缩算法 ( 1 ) 通过对输入码流进行分析，能够自适应地生成一个包含输入流中不重复的字符串 表，然后将每一个字串加入字典，映射为一个独立的码字输出，因此充分利用了相邻数据 的相关性。数字图像数据是高度相关的，存在大量的局部相同或相似性数据，所以采用该 算法在通用数据压缩领域，尤其是数字图像方面，可以取得相当好的压缩率。 ( 2 ) 算法在压缩过程中动态生成一个字典，当压缩结束后，字典中的内容不需要保存 和传输，在解压的时候可以生成与压缩时一模一样的字典，非常的方便。另外，字典信息 是完全包含在压缩后的数据中的，解压程序可以动态的从压缩过的数据中构造出来，因此 解压过程也非常类似于压缩过程。 ( 3 ) l z w 算法逻辑简单，实现速度快，擅长于压缩重复出现的字符串。无须事先统计 各字符的出现概率，一次扫描即可。相对与其他算法，更有利于用硬件实现。 4 5 2l z w 算法缺点： ( 1 ) 算法生成的串表要用额外存储器，在面积的限制下，存储m e m o r y 的容量受到一 定限制； ( 2 ) 需要压缩的数据流中存在大量简单字符，需要设置额外存储，增加了字典开销； ( 3 ) 算法受到字典容量、数据复杂度和计算速度等因素的限制，串表的项数比较有限； ( 4 ) 算法通常是在字典满时将其清空、重建，由于字典建立初期的字符串表很少，需 要压缩的数据与字典中字串的匹配率很低，导致字典重建初期压缩效果很差，需要改进字 典替换策略； ( 5 ) 对较大的文件进行压缩编码时，频繁的查找字典、磁盘读写访问会降低数据编码 的速度： ( 6 ) 一般信源所具有的局部平稳性随缓存容量加大，当数据流相对杂乱无章时，该算 法压缩效果比较一般。 4 5 3l z w 压缩算法的改进： ( 1 ) 字典词条长度的改进： l z w 的理论算法采用的字典项中的字典词条是非定长的，这给利用硬件实现带来了一 定的困难。如果采用的存储宽度小于字典词条的长度，就会引起压缩错误，而如果在硬件 中开辟大容量的存储空间，势必会造成资源的浪费。为了硬件编程的方便，要对序列的长 度进行改进： + 举例说明：0 1 h ，0 2 h ，0 2 h ，0 2 h ，0 3 h ，0 3 h ，o l h ，0 2 h ，0 2 h ，0 2 h ，0 4 h 3 7 南京信息工程大学硕士学位论文 下表4 - 6 为改进过后的字典词条存储方式： 字符对 p c 代码 o l h 0 2 h0 1 h 0 2 hl o l h 0 2 t l0 2 h0 2 h 0 2 h1 0 2 h 1 0 2 h0 3 h1 0 2 h 0 3 h1 0 3 h 0 3 h 0 3 h0 3 h0 3 h1 0 4 h 0 3 h o l h0 3 ho l h1 0 5 h l o l h 0 2 h 1 0 l h0 2 h1 0 6 h 1 0 2 h0 4 h1 0 2 h0 4 h 1 0 7 h 表4 6 字典词条p + c 表 由此可以看出字典词条的大小可以开辟为两个字符的长度，为硬件中字典词条存储空 间的开辟带来了方便。 ( 2 ) 字典词条搜索速度的改进： 传统压缩过程中，根据l z w 算法编码规则，每次读入数据，都要同之前字典中所有字 串相比较。如果能够匹配，就继续读下一个字节，如果不能，就输出最后匹配的段号，并 把这个新段号加入到字典中。于是，每读一个字节就要查找一遍字典，导致编码所需要时 间随文件长度增加呈指数增长。一些方案中用的哈希表办法，将字符串分类，按类查找。 这样可以降低查找的个数，减少时间。但是由于要压缩数据通常很大，效果不够理想。 在这里提出了一种反向存储的方法，从而真正的实现零查找，后者称为反向字典存储 列表。将每个字串是否被用过、被哪个段用过给记录下来。在这里依然是利用表4 - 6 改进 过后的字典词条存储方式，但是另外增加了p r e f i x 项，改进过后的字典存储方式如下表 4 - 7 ： 字符对 pc 代码 p r e f i x 0 l h 0 2 h0 l h0 2 h1 0 l h o l h p r e f i x = l o l h 0 2 h 0 2 h0 2 h 0 2 h1 0 2 h 0 2 h p r e f i x = l0 2 h 1 0 2 h 0 3 h1 0 2 h0 3 h1 0 3 h 10 2 h p r e f i x = l0 3 h 第四章压缩算法 0 3 h e f h0 3 h0 3 h 1 0 4 h 0 3 h p r e f i x = 10 4 h 0 3 h o l h0 3 ho l h1 0 5 h 0 3 h p r e f t x = 1 0 4 h ，1 0 5 h 】 l o l h0 2 h 1 0 1 h0 2 h1 0 6 h l o l h p r e f i x = 1 0 6 h 1 0 2 h0 4 h1 0 2 h0 4 h1 0 7 h 1 0 2 h p r e f i x = i o t a 表4 7 字典词条p + c + p r e f i x 表 如果输入的数据为0 1 h ，则根据o l h 的p r e f i x 找到索引号1 0 1 h ，然后第二个数据，如 果相同，则继续比较第三个数据，之后的步骤与前面介绍的相同，但可以看到的一点是查 找字典的速度极大提高，不需要逐项搜索每一条字典记录，而是直接可以搜索定位到的字 典记录。但是这种方法如果用硬件实现起来需要占用大量的存储资源。例如一副示波器图 像通过m a t l a b 仿真，得到的p r e f i x 项有8 项之多，如果码表的大小为1 0 2 4 项，那么每一 项都要给l o b i t 的话，那么码表的宽度将会达到1 8 + 8 0 = 9 8 b i t ，这样的码表占用资源将会 太多，看来还是要从f p g a 本身的并行结构上来想办法，下面将介绍基于c a m 并行思想在硬 件资源中构造码表的方法。 第五章基于c a m 的l z w 算法实现 第五章基于c a m 的l z w 算法实现 5 1c a m 原理 为了解决码表搜索速度的问题，本系统引入了新型的存储器c a m ( 如图5 - 1 ) 作为码表 的存储单元。c a m 基于内容寻址，通过硬件电路实现快速匹配。c a m 的并行处理特性使得它 在数据分选领域倍受青睐，被广泛应用于以太网网址搜寻、数据压缩、模式识别、高速缓 存、高速数据处理、数据安全和数据加密等。另外，c a m 的出现也为军用信号处理( 尤其 是雷达截获系统信号处理) 提供了新的思路。但是，由于c a m 的实现是以牺牲硬件资源为 代价的，常规的f p g a 器件只能实现很小规模的c a m 。因此，以前的c a m 都是专用器件且规 模较小，使用灵活性较低。随着f p g a 器件门数的增加和结构的改进以及i p 库的不断丰富， 基于f p g a 的c a m 实现已成为可能。尤其是1 9 9 9 年底和2 0 0 0 底初，a l t e r a 公司和x i l i n x 公司相继推出了a p e x 和v l r t e x 系列超大规模f p g a ，使得利用f p g a 实现大规模c a m 的时 机趋于成熟1 。 m 咄 a d d r _ i n 卜 m a t c h a d d r 莎 w r i t c c p c a m - 。 m a t c ho k 。1 k 卜 哪 域 嗲 图5 - 1c a m 模型图 c a m 是一种专门为快速查找数据地址而设计的存储器。c a m 通过把输入数据与其内所存 数据相比较，能快速确定输入数据是否与其内部某个数据或某几个数据相匹配。c a m 的数 据寻址方式因应用要求不同而不同，最快方式仅需要一个时钟周期便可完成对所有数据的 寻址。 与r a m 一样，c a m 也是采取阵列式数据存储( 如下图5 - 2 ) 。其数据的写入方式与r a m 差不多，但c a m 的数据读取方式却与r a m 不同。在r a m 中，输入的是数据地址，输出的是 数据；而在c a m 中，输入的是所要查询的数据，输出的是数据地址和匹配标志( m a t c h ) 。 若匹配( 即数据搜寻到) ，则输出数据地址。在p a m 中，r a m 的存储容量由地址线宽度确 定。例如，l o b i t 宽地址总线的r a m 存储容量为2 1 0 = 1 0 2 4 个字节，c a m 却没有这个限制，因 此它不是采用传统的通过地址读取数据的方式。如若从1 0 2 4 个字节中查询某一数据，输入 数据宽度为8 b i t ，数据存在则输出匹配标志和l o b i t 宽的数据地址。因此c a m 不是采用传 4 0 南京信息工程大学硕士学位论文 统的地址线模式读取数据，存储空间可以很容易地扩展，输入数据线宽度只由需查询的数 据位数决定。 r m d c u t 7 ：o 】 扩1 0 2 4 - _ _ - _ _ _ i - _ - - c a m 里竺旦翌 8 1 0 2 4 图5 - 2r a m 和c a m 比较 显然，c a m 的数据查询速度远远高于r a m 。因此，c a m 大量应用于需要高速数据处理的 系统之中。c a m 的出现加快了一些系统和技术的应用，如大型数据库管理、数据链接、模 式识别等在图像识别、语音识别中的应用。c a m 的核心为存储单元阵列和存储单元与输入 数据之间的比较器。不同的应用对c a m 的速度、密度有不同的要求，而且c