（测试计量技术及仪器专业论文）基于分组的变长解码器设计及其vlsi实现结构.pdf

上海人学硕士学位论文 摘要 近年来，随着微电子技术的高速发展和压缩编码技术的逐渐成熟，实时图 像处理在多媒体、h d t v ( h i g hd e f i n i t i o nt e l e v i s i o n ) 、图像通信等领域有着越来 越广泛的应用，视频压缩解压的i c 芯片设计成为了多媒体技术的核心。 变长编码是一种在视频压缩系统中广泛应用的压缩技术，它的主要作用是 依据数据的统计特性能使编码的平均长度最小，它已被许多数据压缩标准，如 j p e g ，m p e g 2 和h 2 6 3 等作为编码方法，但由于解码过程中的循环依赖性， 限制了解码吞吐率。本文介绍了一种基于分组的变长解码器，它利用了变长码 的冗余信息。结果表明，这种方法能非常有效的减小占用的逻辑资源，并能快 速的解码。该方法首先把变长解码器分成两个功能模块：v l c 检测模块和查找 表( l o o k - u p - t a b l e ，l u t ) 模块。v l c 检测模块采用并行处理方法，这样在相同 时钟频率下，比串行处理能提供更高的码字输出率。l u t 根据v l c 码字本身 特点和m p e g 标准，本文提出了一种新的基于变长码前缀及相向前缀码字个数 的分组查找方法，并对地址产生电路进行了优化。 整个设计及其各个模块都在a l t e r a 公司的e d a 工具q u a r t u si i 平台上进行 了逻辑综合及功能和时序仿真。结果表明基于分组的变长解码结构在速度和资 源利用率方面均有很好的性能，可满足实时解码的要求。 关键词：变长码；变长解码器；码表分割；m p e g - 2 - 海人学硕士学位论文 a b s t r a c t i nr e c e n t y e a r s ，w i t ht h e f a s td e v e l o p m e n to fe l e c t r o n i c t e c h n o l o g ya n d c o m p r e s s i o nt e c h n o l o g y ，r e a l t i m ei m a g ep r o c e s s i n gi sw i d e l yu s e di nt h ef i e l do f m u l t i m e d i a , h d t v ( r i g hd e f i n i t i o nt e l e v i s i o n ) a n di m a g ec o m m u n i c a t i o n a tt h e s a m et i m e ，t h ei c so fi m a g ev i d e oc o m p r e s s i o n d e c o m p r e s s i o nb e c o m et h ec o r eo f m u l t i m e d i at e c h n i q u e s v a r i a b l el e n g t hc o d i n gi saw i d e l yu s e dt e c h n i q u ei nd i g i t a lv i d e oc o m p r e s s i o n s y s t e m s t h em a i n i d e a o fv a r i a b l el e n g t hc o d i n gi st om i n i m i z et h ea v e r a g e c o d e w o r dl e n g t hb ye x p l o i t i n gt h es t a t i s t i c so ft h ed a t a i ti st h em o s tp o p u l a r d a t a - c o m p r e s s i o nt e c h n i q u e ，w h i c hh a sb e e nu s e di nm a n yd a t ac o m p r e s s i o n s t a n d a r d s ，s u c ha sj p e g ，m p e g - 2 ，a n dh 2 6 3 t h er e c u r s i v ei t e r a t i o no f t h ed e c o d i n g p r o c e s sl i m i t s t h ea c h i e v a b l ed e c o d i n gt h r o u g h p u t t h i sw o r kp r e s e n t sav a r i a b l e l e n g t hd e c o d e rb a s e do nt a b l ep a r t i t i o n i n g , w h i c he x p l o i t st h es i g n a ls t a t i s t i c so f v a r i a b l el e n g t hc o d e s t h em e t h o di ss h o w nt ob ee x t r e m e l ye f f i v c i e u ti nt h em e m o r y r e a n i r e m e n ta n df a s ti n s e a r c h i n gf o rt h ed e s i r e ds y m b o l s f i r s tt h ev a r i a b l el e n g t h d e c o d e r ( v l d ) w a sd e c o m p o s e di n t oi t sf u n c t i o n a lu n i t s ：t h ev l cd e t e c t o ra n dt h e l o o k u pt a b l e ( l u n ap a r a l l e lm e t h o dw a sc h o s e nf o rt h ev l cd e t e c t o r i th a s a d v a n t a g eo v e rt h es e r i a lm e t h o di nt h a ti tp r o d u c e sh i g h e rc o d e w o r do u t p u tr a t ea t t h es a m es y s t e mc l o c kf r e q u e n c y a c c o r d i n gt ot h ec h a r a c t e r i s t i c so f v l ca n dm p e g s t a n d a r d ，an e wd e s i g nm e t h o df o rl u to fv l ca n da d d r e s sc o d i n gi sg i v e n , w h i c h b a s e do nt h ev l c sp r e f i xa n di t sl e n g t h t h ef u l ld e s i g na n de a c hm o d u l ea r es y n t h e s i z e di nl o g i c ，t h e nr r cs i m u l a t e di n f u n c t i o na n dt i m i n go nq u a r t u si ie d at o o l - d e s ko fa l t e r ac o r p t h er e s u l ti n d i c a t e s t h a tt h ev l db a s e do nt a b l ep a r t i t i o n i n gc a ng i v eab e t t e rp e r f o r m a n c eo ns p e e da n d r e s o u r c eu s i n gw i t l ll e s sh a r d w a r er e s o u r c ea n da h i g hf r e q u e n c y a n dc a nm e e tt h e r e q u i r e m e n to f r e a l - t i m ea p p l i c a t i o no f d e c o d i n g k e yw o r d s ：v a r i a b l el e n g t hc o d e ( v l c ) ；v a r i a b l el e n g t hd e c o d e r ( v l d ) ；t a b l e p a r t i t i o n i n g ； m p e g - 2 v l 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送 交论文复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：f 亟芏鱼导师签名：z 鱼堑! 鱼 日期：二矿，氧l t k 上海大学硕士学位论文 第一章绪论 1 1 引言 随着多媒体和通信技术的发展，图形、图像和视频信息在许多领域中得到 广泛的应用。同时，人们对图像的质量和分辨率的要求也越来越高，这就导致 了更高的数据率和更加复杂的数据类型。所以要求有效的压缩技术，能够满足 各种应用要求，节省传输带宽和存储空间。一种经典的数据压缩技术是变长码 f v a r i a b l e 1 e n g t hc o d e ，v l c ) ，也叫h u f f m a n 码。它是一种最优编码，其平均码 字长度接近于信息源的熵。v l c 是最流行的无损压缩技术，被许多图像和视频 国际标准，如m p e g 、j p e g 、h 2 6 3 推荐作为熵编码方法。所以，v l c 在多媒 体和通信领域有极其重要的地位。 变长编码可以通过查表和流水线满足高速处理的要求。然而，变长码的解 码只能串行完成。因为码字长度是可变的，解码器在确定当前码字长度之前， 不能开始下一个码字的解码，使得解码器很难采用流水线或并行的方法实现。 所以，尽管变长码对数据压缩来说是最优的，但由于解码过程对码长的循环依 赖性，限制了解码吞吐率。因此研究高性能的变长码的解码算法及其v l s i 实 现结构，一直是研究变长码的重点和难点，也是其发展方向。 变长码的解码算法和结构己在许多文献中被讨论2 8 】【3 6 1 1 2 3 1 。基于变长码的码 树结构，采用从根到叶的搜索算法，一个时钟周期可以译出一位。这种方法十 分不适应高速应用，因为对长的码字来说，解码周期长。同时，操作周期的改 变使缓冲器和u o 设计变得复杂。为了减少解码时间，人们设计了几种使用并 行或流水线结构的解码器。通过查表方式使当前输入的比特流并行的匹配所有 可能的码字，一个时钟周期可以译出一个码字。但是这种方法对大码表来说， 非常不实际，因为硬件复杂性迅速增加，并且由于逻辑电路的本身特性使得速 度下降很多。 近年来，已有学者提出了基于分组的v l c 解码算法1 2 8 1 1 3 2 1 。应用码字特征 进行分组查找，可以实现固定的操作时间，降低硬件开销，从而提高系统性能， 减少控制复杂性。本课题将在此基础上，研究出一种通用的变长解码结构，提 上海大学硕士学位论文 出一种新的分组方法，减小器件占用的逻辑资源，并且能满足高速实时解码应 用的需要。 1 2 变长解码器设计的研究现状 1 2 1v l c 简介 霍夫曼( h r 斌m a u ) 编码，也叫变长码，是一种常用的压缩编码方法，是 h u f f m a n 于1 9 5 2 年为压缩文本文件建立的。它是统计独立信源达到最小平均码 长的编码方法，具有惟一可译性。它的基本原理是：按信源符号出现的概率大 小进行排序，出现概率大的分配短码，出现概率小的则分配长码。v l c 效率高， 运算速度快，实现方式灵活，从2 0 世纪6 0 年代至今，在数据压缩领域得到了 广泛的应用。例如在m p e g - 1 ( i s o i e c l l 7 2 ) 和m p e g - 2 ( i s o i e c l 3 8 1 8 ) 这两个标 准的关键技术中17 】【3 ”1 ，都采用了d c t 变换和v l c 等技术进行数据压缩。在 第二章中将专门介绍一下v l c 编码过程。 1 2 2 变长码解码算法综述 近年来，在一些实时应用场合中，人们对变长解码芯片的解码速度的要求 越来越高，解码算法的研究也逐渐引起了人们的注意。尤其在一些嵌入式系统 中，变长解码模块往往成为限制系统速度的瓶颈。这主要是由于v l c 是交长的， 压缩后产生的码字长度不固定，传统的解码方法需要对码字的每个比特进行处 理，逐位读入码流，先判断码字长度，再进行解码，效率相对较低，而且逐个 比特处理方式一般难以达到实时解码的要求。 目前针对硬件实现的变长码解码算法主要有以下四种： 1 ) 遍历二叉树，是很早提出的传统算法，也是最基本的算法【2 9 】，适用于需 要临时生成码表的解码算法。但由于h u f f m a n 树的各个叶节点深度不同，内存 大小的要求又是由叶节点的最大深度来决定，所以造成内存中存储了大量冗余 的数据。一般来说，若h u f f m a n 码字最长k 位，则内存的大小接近2 0 字节。 2 ) 前n 位的快速解码【4 】f 2 0 1 ，是从码流中读取最前面的n 位，当被解码码字 的实际长度小于n 时，能一次解码i 反之则从n + 1 位开始按传统方式解码。该 l 海人坚硕士学位论文 出一种新的分组方法，减小器件占用的逻辑资源，并且能满足高速实时解码应 用的需要。 1 2 变长解码器设计的研究现状 1 2 1v l c 简介 霍夫曼( h u f f m a n ) 编码，也叫变长码，是一种常用的压缩编码方法，是 h u f f m a n 于1 9 5 2 年为压缩文本文件建立的。它是统计独立信源达到最小平均码 长的编码方法，具有惟一可译性。它的基本原理是：按信源符号出现的概率大 小进行排序，出现概率大的分配短码，出现概率小的则分自d 长码。v l c 效率高， 运算速度快，实现方式灵活，从2 0 世纪6 0 年代至今，在数据压缩领域得到了 广瑟的应用。例如在m p e g 一1 ( i s o i e c l l 7 2 ) 和m p e g 一2 ( 1 s o f i e c l 3 8 1 8 ) 这两个标 准的关键技术中” ，都采用了d c t 变换和v l c 等技术进行数据压缩。在 第二章中将专门介绍一下v l c 编码过程。 1 2 2 变长码解码算法综述 近年来，在一些实时应用场合中，人们对变长解码芯片的解码速度的要求 越来越高，解码算法的研究也逐渐引起了人们的注意。尤其在一些嵌入式系统 中，变长解码模块往往成为限制系统速度的瓶颈。这主要是由于v l c 是变长的， 压缩后产生的码字长度不固定，传统的解码方法需要对码字的每个比特进行处 理，逐位读入码流，先判断码字长度，再进行解码，效率相对较低，而且逐个 比特处理方式一般难咀达到实时解码的要求。 目前针对硬件实现的变长码解码算法主要有以下四种： 1 ) 遍历二叉树，是很早提出的传统算法，也是最基本的算法【”，适用于需 要临时生成码表的解码算法。但由于h u f f m a n 树的各个叶节点深度不同，内存 大小的要求又是由叶节点的最大深度来决定，所以造成内存中存储了大量冗余 的数据。一般来说，若h u f f r a a n 码字最长k 位，则内存的大小接近2 。字节。 2 ) 前n 位的快速解码 4 1 1 2 0 ，是从码流中读取最前面的n 位，当被解码码字 的实际长度小于n 时，能一次解码，反之则从n + 1 位开始按传统方式解码。该 的实际长度小于n 时，能一次解码，反之则从n + 1 位开始按传统方式解码。该 e 海大学硕士学位论文 算法对于短码字解码速度快，但是短码字是叶节点深度差别较大的部分，用前 n 位建立查找表，需要内存2 ”字节，内存中的冗余数据仍然很多，并且h u f f m a n 码字字长还要另行计算。对于长码字，虽然出现的概率比较小，但是由于其解 码速度没有改善，对整体的解码速度还是有一定影响。解码的时候，每次先读 入码流最前面的n 比特信息，按查找表进行试解码如果查表结果不是码长大 于n 的标志，则表示试解码成功，系统输出查表得到的符号，并截去码流最前 面的l e n 位信息( 1 e n 是查表得到的码长) ；如果查表得到码长大于n 的标志，则 试解码失败，应采用传统的解码方式继续解码。此时前n 位已经确定，所以 采用传统方式解码时可以直接从码长等于n + l 的地方开始操作。解码流程如 图1 1 所示。 图1 1 前n 位的快速解码流程图 3 ) 分组查找表解码2 q 30 1 ，将h u f f m a n 码字按一定字长f l 进行分割，一次 读入n 位查表，再读入下n 位查对应的表，往复循环，最后输出结果为码字所 一t 海人学硕士学位论文 代表的类别，码字字长则通过每次累加得到，这样大大提高了速度，并且通过 分组提高了内存利用率。但是在内存中，仍然存有相当大的冗余，当码字较长 时，分组的个数较多，还是需要很大的内存，而且查表过程序要反馈循环，速 度不是很快。 4 ) 分组与模式匹配【1 6 1 ，是将h u f f m a n 码字按照连续0 或连续1 的个数分 组，每组产生一个子码表，并快速计算出h u f f x n a n 码码长，再根据码字、码长 和组别计算出子码表的查找矢量，按照矢量查子码表，得到解码结果。 码长信号变长码码长信号变长码 20 00 020 00 0 2o lo l2o lo l 40 2i 0 0 040 21 0 0 0 40 31 0 0 140 31 0 0 l 40 41 0 1 0 4 0 41 0 1 0 40 51 0 l l40 51 0 l l 40 61 1 0 040 61 1 0 0 40 71 1 0 l40 7 1 1 0 l 50 81 1 1 0050 8儿1 00 l 6 0 9 1 1 1 0 1 0 60 91 1 1 0 染 6 0 a 1 1 1 0 l l6 o al l l o 6o b1 1 l l0 06o b1 1 l l 7o c1 1 l l0 1 07 0 c1 1 1 1 牝 7o d1 1 l l0 1 17o d1 1 1 l 8o e1 1 1 1l o g08o el i l l 冀 8 o f 1 l 儿1 0 0l8o f1 1 1 1 81 01 1 1 11 0 1 081 0l l l l 81 l1 1 1 l1 0 ll8i l1 1 1 1 8 1 21 1l l1 1 0 08 1 21 1 1 1 91 3l l l l1 1 0 1 091 3 1 1 1 l 1 1 0 1 1 0l 91 41 1 1 11 1 01 191 41 l l l 1 1 0 山 91 51 1 l ll l l0 091 51 1 1 11 1 1 0 - t 0 i i 01 6l l l l 1 1 0 1 0 1 01 61 l l l 1 i ! 0 1 1 0l 1 01 7l l l ll l ：0 l l l o1 71 1 l l 浏 1 01 81 1 1 ll l1 0 01 01 81 1 i i 1 0 1 91 1 1 1l l i 0 1 1 0 1 9l l l l i 0t ai i i i1 1 1i i 01 01 al l l l 1 2l b1 l l ll lll 1 0 (1 2i b儿l l11 1 1 1 1 0 1 0 l 1 2l c1 1 1 11 l1 1 1 0 11 2l c1 1 1 l 1 1 l l ”w 1 2 i dl l l l1 l 1 l l l ( 1 2 i d 1 1 1 l 1 1 1 1 1 1 1 1 0 l 1 3 l e 1 l l l 1 l l l l l i01 3l el l l l 1 1 1 1 1 1 1 1 l o l 1 3i f1 1 1 11 l ：1 l l l l11 3i fl l l l 1 1 1 1 1 1 1 1 u ( a ) 基于固定长度的分组( b ) 基于前缀的分组 图1 2 基于固定长度分组和基于前缀分组的倒子 图l 2 举出了鼯个分组实例，( a ) 对应于算法3 ，( b ) 对应于算法4 。如果 完全按照图中的算法，两种分组方法分别需要的存储空间是1 6 2 和4 6 ，由此可 上海人学碗j j 学位论文 以看出后者的占用的逻辑资源更小。 但我们注意到，原始码表的个数是3 2 个，利用上述两种方法都有冗余的存 储空间，因此如果找到更为有效的分组方法，那么它的器件消耗还能再小一些。 1 3 本课题的主要研究内容 通过比较，本文采用的基于分组的解码结构，因此如何找到一种高效的分 组方法是本课题的主要研究内容，主要包括两个方面： 1 分组和存储映射的研究 研究利用v l c 码字本身的特征，设计有效的分组方法，使其不但易于分组 识别，而且利于硬件实现；根据分组方法优化码表的存储映射，使其不但节省 存储空间，而且寻址简单。 2 分组搜索方法的研究 对于定长度的二进制比特流，分组方法应该能够立即确定其分组并给出 分组信息。分组以后，对码字信号进行存储查找时，需要一个地址产生电路产 生对应的地址信息，如何设计这个地址产生电路，即分组搜索方法的研究是本 课题的重点。地址产生电路可以用一个多路选择器实现，也可以利用数据本身 通过简单的逻辑电路实现。选用恰当的地址产生电路，不仅可以缩小器件占用 的逻辑资源，还能使地址产生电路模块产生较小的时间延迟，提高器件的整体 运行速度。 为了提高解码速率，基于分组的v l c 解码器拟采用并行结构。先进先出堆 栈以恒定的码率接收输入码流，为解码做准备。v l c 检测模块根据当前解出的 码字长度，确定下一次解码的位置。由分组搜索单元组成的变长解码器查找表 是根据分组搜索算法实现的。对于给定的一定长度的码流，v l c 检测模块立即 给出分组信息。 3 研究出解码算法后，根据研究内容将系统实现的功能分解成子模块， 采用自上而下( t o p d o w n ) 设计方法，分别用v h d l 写出解码算法的r t l 级描 述，仿真综合成逻辑网表后下载到f p g a ，验证其功能。 上海大学硕士学位论文 第二章e d a 与变长编码原理 2 1电子设计自动化技术( e d a ) 的发展 人类社会已进入到高度发达的信息化社会犯】【9 j ，信息社会的发展离不开电子 产品的进步。现代电子产品在性能提高、复杂度增大的同时，价格却一直呈下 降趋势，而且产品更新换代的步伐也越来越快，实现这种进步的主要原因就是 生产制造技术和电子设计技术的发展。前者以微细加工技术为代表，目前已进 展到深亚微米阶段，可以在几平方厘米的芯片上集成数千万个晶体管；后者的 核心就是e d a ( e l e c t r o n i cd e s i g n a u t o m a t i o n ) 技术。e d a 是指以计算机为工作平 台，融合了应用电子技术、计算机技术、智能化技术最新成果而研制成的电子 c a d 通用软件包，主要能辅助进行三方面的设计工作：i c 设计，电子电路设计 以及p c b 设计。没有e d a 技术的支持；想要完成上述超大规模集成电路的设 计制造是不可想象的，反过来，生产制造技术的不断进步又必将对e d a 技术提 出新的要求。 回顾近4 0 年来电子设计技术的发展历程，可将e d a 技术分为三个阶段【拍1 。 1 ) c a d 阶段( 2 0 世纪6 0 年代8 0 年代初) ，这一阶段人们开始用计算机 辅助进行i c 版图编辑和p c b 布局布线，取代了手工操作，产生了计 算机辅助设计的概念。 2 ) c a e 阶段( 2 0 世纪8 0 年代一9 0 年代初) ，与c a d 相比，除了纯粹的 图形绘制功能外，又增加了电路功能设计和结构设计，并且通过电气 连接网络表将两者结合在一起，以实现工程设计，这就是计算机辅助 工程的概念。c a e 的主要功能是：原理图输入，逻辑仿真，电路分析， 自动布局布线，p c b 后分析。 3 ) e s d a ( e l e c t r o n i cs y s t e md e s i g na u t o m a t i o n ) 阶段( 2 0 世纪9 0 年代以 来) 。尽管c a d c a e 技术取得了巨大的成功，但并没有把人从繁重的 设计工作中彻底解放出来。在整个设计过程中，自动化和智能化程度 还不高，各种e d a 软件界面千差万别，学习使用困难，并且互不兼容， 直接影响到设计环节间的衔接。基于以上不足，人们开始追求贯彻整 r 海大学硕十学位论文 个设计过程的自动化，这就是e s d a 即电子系统设计自动化。 e s d a 代表了当今电子设计技术的最新发展方向，它的基本特征是：设计 人员按照”自顶向下”的设计方法，对整个系统进行方案设计和功能划分，系统 的关键电路用一片或几片专用集成电路( a s i c ) 实现，然后采用硬件描述语言 ( h d l ) 完成系统行为级设计，最后通过综合器和适配器生成最终的目标器件， 这样的设计方法被称为高层次的电子设计方法。 2 2自顶向下的设计和自底向上的设计 集成电路的设计方法从整体和局部的先后顺序上分为自顶向下( t o p d o w n ) 的设计和自底向上( b o t t o m - u p ) 的设计【1 0 1 。所谓自底向上的设计，就是设计者 首先选择具体的逻辑单元进行逻辑电路设计，得到系统需要的独立的功能模块， 然后再把这些模块连接起来，组装成整个系统。所谓自顶向下的设计，就是由 设计者首先从整体上规划整个系统的功能，然后对系统进行划分，分解为规模 较小、功能较为简单的局部模块，并确立它们的相互关系，这种划分过程可以 不断地进行下去，直到划分得到的单元可以映射到物理实现。图2 1 描述了自 项向下设计的流程。 自底向上的设计方法是从传统的手工设计发展而来的。这种设计过程的缺 点是在进行底层设计时，缺乏对系统整体性能的把握，如果在整个系统完成后 发现性能还需要改进，则修改起来比较困难。 自顶向下的设计方法是随着硬件描述语言( h d l ) 和e d a 工具同步发展起 来的。硬件描述语言可以在各个抽象层次上对电子系统进行描述，而且借助于 e d a 设计工具，可以自动实现从高层次到低层次的转换。采用这种设计方法的 优点显而易见，由于整个系统是从系统顶层开始的。结合模拟手段，可以从一 开始就掌握实现系统的性能状况，结合应用领域的具体要求，在开始阶段就可 以调整方案，进行性能优化或折中取舍。随着设计层次向下进行，系统性能参 数将得到进一步的细化和确认，并随时可以根据需要加以调整，从而保证了设 计结果的正确性，缩短了设计周期。自顶向下的设计方法的缺点是需要先进的 e d a 设计工具和精确的工艺库支挣。 上海大学硕十学位论文 图2 1 自顶向下设计的流程困 2 3 硬件描述语言v h d l 硬件描述语言( h d l - h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 是一种用于设计硬件 电子系统的计算机语言【1 4 】，它用软件编程的方式来描述电子系统的逻辑功 能、电路结构和连接形式，与传统的门级描述方式相比，它更适合大规模系统 的设计。例如一个3 2 位的加法器，利用图形输入软件需要输入5 0 0 至1 0 0 0 个 门，而利用v h d l 语言只需要书写一行a = b + c 即可，而且v h d l 语言可读性 强，易于修改和发现错误。早期的硬件描述语言，如a b e l h d l 、a h d l ，是 由不同的e d a 厂商开发的，互相不兼容，而且不支持多层次设计，层次间翻译 工作要由人工完成。为了克服以上缺陷，1 9 8 5 年美国国防部正式推出了 v h d l ( v e r yh i g hs p e e di n t e g r a t e dc i r c u i th d l ) 语言，1 9 8 7 年i e e e 采纳v h d l 为硬件描述语言标准( i e e es t d 1 0 7 6 ) 。 v h d l 是一种全方位的硬件描述语言，包括系统行为级、寄存器传输级和 逻辑门级多个设计层次，支持结构、数据流、行为三种描述形式的混合描述，因 此v h d l 几乎覆盖了以往各种硬件描述语言的功能，整个自顶向下或自底向上 上海大学硕士学位论文 的电路设计过程都可以用v h d l 来完成。另外，v h d l 还具有以下优点： v h d l 的宽范围描述能力使它成为高层次设计的核心，将设计人员的工作 重心提高到了系统功能的实现与调试，只需花较少的精力用于物理实现。 v h d l 可以用简洁明确的代码描述来进行复杂控制逻辑的设计，灵活且方 便，而且也便于设计结果的交流、保存和重用。 v h d l 的设计不依赖于特定的器件，方便了工艺的转换。 除了v h d l 外，原先在工业界己应用很广的另一个硬件描述语言v e r i l o g ， 也成为i e e e 的硬件描述语言标准。大多数e d a 软件都支持v h d l 和v e f i l o g 两种语言。本课题主要采用v h d l 语言。 一个完整的v h d l 语言程序通常包含实体( e n t i t y ) 、构造体( a r c h i t e c t u r e ) 、 配置( c o n f i g u r a t i o n ) 、包集合( i j a c k a g e ) 和库( 1 i b r a r y ) 5 个部分。前4 部分是 可分别编译的源设计单元。实体用于描述所设计的系统的外部接口信号；构造 体用于描述系统内部的结构和行为；包集合存放各设计模块都能共享的数据类 型、常数和子程序等：配置用于从库中选取所需单元来组成系统设计的不同版 本：库用于存放已经编译的实体、构造体、包集合和配置。库可由用户生成或 由a s i c 芯片制造商提供，以便于在设计中被设计人员共享。 2 4 变长编码技术 数据压缩的理论基础是信息论【1 5 】，数据压缩的理论极限是信息熵。那么， 我们首先要明确信息熵的概念，这个概念很重要，它是数据压缩编码技术的一 个最基本的概念。统计编码的基本思想是：主要针对无记忆信源，根据信息码 字出现概率的分布特征而进行压缩编码，寻找概率与码字长度间的最优匹配。 常用的统计编码有游程编码、v l c 和算术编码三种。 2 4 1 信息与信息量 信息论的创始人香农( c l a u d ee s h a n o n ) 从通信系统理论的角度把信息定 义为用来减少随机不确定性( u n c e r t a i n t y ) 的东西。也就是说，信宿( 信息接受 方) 未收到消息前不知道信源( 信息产生方) 发出什么信息，只有在收到消息 f - 海人学硕士学位论文 后才能消除信源的不确定性。如果没有干扰，信宿得到的信息量与信源的不确 定性相等。要注意理解这个概念中的”不确定性”，也就是说当你收到一条消息 ( 一定内容) 之前，某一事件处于不确定的状态中，当你收到消息后，分解除 不确定性从而获得信息，因此去除不确定性的多少就成为信息的度量。一个 消息的可能性愈小，其信息含量愈大：反之，消息的可能性愈大，其信息含量 愈小。 信息量是指从n 个相等的可能事件中选出一个事件所需要的信息度量和含 量。定义如下： 设从n 个随机事件中选定任一个事件x 的概率为p ( x ) ，假定任选一个数的 概率都相等，即p ( x ) = i n ，则信息量i ( x ) 可定义为： 1 i = l o ga n = 一l o g 。一一t o g 。p y 上式可随对数所用”底”的不同而取不同的值，因而其单位也就不同。设底 取大于l 的整数d ，考虑一般物理器件的二态性，通常a 取2 ，相应的信息量 单位为比特( b i t ) ；当d = e ，相应的信息量单位为奈特( n a t ) ；当n = 1 0 ，相应 的信息量单位为哈特( h a r t ) ； 显然，当随机事件x 发生的先验概率p ( x ) 大时，算出的i ( x ) 小，那么这个 事件发生的可能性大，不确定性小，事件一旦发生后提供的信息量也少。必然 事件的p ( x ) 等于1 ，i ( x ) 等于0 。 2 4 2 信息熵 信息量计算的是一个信源的某一个事件( x ) 的自信息量，而一个信源若 由n 个随机事件组成，1 1 个随机事件的平均信息量就定义为熵( e n t r o p y ) 。熵的 准确定义是：信源x 发出的x j 0 = 1 ，2 ，n ) ，共n 个随机事件的自信息统计平均 ( 求数学期望) ，即 月 h h ( ) ( ) 2 e i ( x j ) ) 2 e ( x ，( x ，) = 一p ( x ，) - 呼e ( x ：o j = i j - 1 h ( x ) 在信息论中称为信源x 的”熵”( e n t r o p y ) ，它的含义是信源x 发出任 意一个随机变量的平均信息量。更详细的说，一般在解释和理解信息熵时，有 上海大学硕士学位论文 4 种样式：当处于事件发生之前，h ( x ) 是不确定性的度量；当处于事件发生之 时，是一种惊奇性的度量；当处于事件发生之后，是获得信息的度量；还可以 理解为是事件随机性的度量。 例如：以信源x 中有8 个随机事件，即n = 8 。每一个随机事件的概率都相 等，即p ( x 1 ) = p ( x 2 ) = p ( x 3 ) p ( x 8 ) - 去，计算信源x 的熵。 6 应用”熵”的定义可得 h ( ) ( ) 2 一荟户( x ，) l o g op ( x ，) _ 一善吉1 0 9 ：；- 3 加 如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持 编码又叫做熵保存编码，或者叫熵编码。熵编码是无失真数据压缩，用这种编 码结果经解码后可无失真地恢复出原图像。v l c 是一种最常用的熵编码。 2 5 变长编码技术 熵编码中的最佳编码方法是v l c 。v l c 方法于1 9 5 2 年问世，是 d a h u f f r n a n 在他的论文”最小冗余度代码的构造方法( am e t h o df o rt h e c o n s t r u c t i o no f m i n i m u mr e d u n d a n c yc o d e s ) ”中提出来的。迄今为止，已广泛应 用于各种数据压缩技术中，且仍不失为熵编码中的最佳编码方法。 2 5 1 v l c 实现 v l c 的码长是变化的，是变长码的一种。对于出现频率高的信息，编码的 长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的 总码长一定小于或等于实际信息的符号长度。v l c 属于无失真编码，它经过解 码后能得到与原来完全一样的信息。为更好理解v l c ，下面先介绍一些二叉树 的基本知识，然后给出v l c 的实现步骤，说明v l c 的特点。 首先我们考虑带权的二叉树。 假如给定一个有n 个权值的集合 w 1 ，w 2 ，w n ) ，其中w i ， o ( 1 i n ) 。 若t 是一棵有n 个叶子的二叉树，而且将权w 1 ，w 2 ，w n 分别赋给t 的n 个叶子，那么我们称t 是权w l ，w 2 ，w n 的二叉树。叶子的带权路径长度 上海大学硕十学位论文 为t 的根到该叶子之间的路径长度与该叶子中权的乘积。n 个叶子的二叉树的 带权路径长度定义为： n p 工：yw f f f j l _ 一 f _ 1 其中：w i 为叶子i 的权，f f 为根结点到叶子i 之间的路径长度。在权w ，w 2 ， w 。的二叉树中，其w p l 最小的二叉树称为最优树。 、 、1 0 f 9 。 ，f3 ：。6t 88 9 _ 1 0 ， ( a ) 一 fjr ： ， r 。 一一i - 、 8 i9 jr1 f 1 0 一一一 f3 j 6j 61 f 3 ， 一一 ( b ) ( c ) 图2 2 具有不同带权路径长度的二又树 例如，图2 2 所示的3 棵二叉树都是权值3 、6 、8 、9 、1 0 的二叉树，它们 的带权路径长度分别为： w p l ( a ) = w t f = 9 x 3 + 1 0 3 + 3 x 2 + 6 2 + 8 x 2 = 9 1 1 = i w p l ( b ) te w f ，= 1 0 1 + 9 x 2 + 8 x 3 + 6 4 + 3 x 4 = 8 8 w p l ( c ) = w - z = 8 2 + 9 2 + 3 x 3 + 6 3 + 1 0 x 2 = 8 1 i = 1 其中，( c ) 的带权路径长度最小。可以验证在以权值3 、6 、8 、9 、1 0 为 叶子的所有二叉树中，最小的带权路径长度为8 1 ，因此图2 2 ( c ) 所示的二叉 树是最优树。如何构造权集合的最优树，h u f f - m a n 提出了一个很好的算法，我 们称之为霍夫曼算法，v l c 的步骤如下： 1 ) 将输入符号按出现的概率由大到小顺序排列( 相同概率的符号可以任意 颠倒排列位置) 。 2 ) 将最小的两个概率相加，形成一个新的概率集合。再按第一步的方法重 j ：海大学硕上学位论文 新排列。如此重复直到只有两个概率为止。 3 ) 分配码字。码字分配从最后一步开始反向进行，对最后两个概率，一个 赋予“o ”码，一个赋予“l ”码。 依据这样的步骤构造出来的编码树一定是最优二叉树。于是，最优树又称 为h u f f m a n 树。 以下以一个例子说明h u f f m a n 树的构造过程，介绍v l c 步骤，例如：对信 源数据x 数据 x 1x 2x 3x 4x 5x 6 l l 概率 o 2 5o 2 50 2 0o 1 5o 1 00 0 5 1 进行v l c 的过程如图2 _ 3 所示。 符号x 1 x 2x 3x 4x 5x 6 概率0 2 50 2 50 2 00 1 50 1 00 0 5 1 5 0 1 1 l1 00 0 10 0 0 10 0 0 0 图2 3 霍夫曼编码 丙= 2 x 2 0 2 5 + 2 0 2 0 + 3 x 0 1 5 + 4 0 1 + 4 0 0 5 = 2 4 5 h 。- - ( 2 0 2 5 1 0 9 2 0 2 5 + 0 2 x l 0 9 2 0 2 + 0 1 5 l o g a 0 1 5 + 0 1 x l 0 9 2 0 1 + 0 0 5 1 0 9 2 0 0 5 1 = 2 4 2 由以上运算可知，平均码长接近于熵值。 2 5 2v l c 特点 v l c 具有一些明显的特点： 1 ) 编出来的码都是异字头码，保证了码的唯一可译性。 2 ) 由于编码长度可变。因此解码时间较长，使得v l c 的还原相当费时。 3 ) 编码长度不统一，编码时可以通过流水线或并行方式实现很高的编码速 度，但是解码时由于v l c 长度不固定，在当前码字没有解出之前，不能开始下 一个码字的解码，因此实现解码时有难度。 r 海大学硕士学位论文 4 ) 对不同信号源的编码效率不同，当信号源的符号概率为2 的负幂次方时， 达到1 0 0 的编码效率。 由于0 与”1 ”的指定是任意的，故由上述过程编出的最佳码不是唯一的， 但其平均码长是一样的，故不影响编码效率与数据压缩性能。 2 6 游程编码 m p e g 2 标准a t ”，v l c 编码分为两步，第一步把量化系数转换成可变长 度码( v l c ) 和可变长度整数( v l i ) 的过渡符号序列。第二步把过渡符号转 换成数据流，在这个数据流中，符号就不再有形式上可识别的边界，对d c 系 数和a c 系数分别采用不同的v l c 方法。因为在连续色调的图象中，本数据块 与前一数据块的d c 系数的差值多半比原值小，对差值进行编码所需的位数会 比对原值进行编码所需的位数少许多，因此d c 采用一种称为差值脉冲编码调 制( d p c m ) 的差值编码法，也就是在同一图像分量中取每个d c 值与前一个 d c 值的差值来编码。 在m p e g 应用s t l 2 】1 2 2 1 ，需要传送的是经过量化的d c t 系数，m 砂，它是 二维数据，需要将二维数据按照一定次序排成一维数据。一个有效的方法叫 z i g z a g 扫描法，如图2 4 所示。利用z i g - z a g 扫描的好处是可以使块中零系数 连续长度比较长，因为一个8 8 的信息组有6 3 个a c 系数，进行量化后许多 a c 系数都为零，零值数据一般出现在高频区域，并且集中在右下角，所以， 为了让零值数据能够连续出现，a c 系数在编码时按照之字形扫描，也叫z i g - z a g 扫描，在这个基础上作游程编码( r u n - l e n g t hc o d i n g ) 效率高。 下面图2 4 所展示的就是一个z i g - z a g 扫描和v l c 的实例。其直流系数d c 值是4 0 ，假设前一块的d c 值是