（微电子学与固体电子学专业论文）基于分组的变长码解码算法及硬件实现结构研究.pdf

上海大学硕士学位论文 摘要 随着多媒体技术的迅猛发展，人们面临的最大问题就是信息量的爆炸性增长， 因此需要进行数据压缩，以提高数据传输效率、信道频带利用率和节省数据存储 空间。变长码( v a r i a b l e l e n g t hc o d e ，v l c ) 作为一种经典的数据压缩技术，因其 编码效率高，因此被许多图像和视频标准如：j p e g 、m p e g 、h2 6 x 等推荐作为 熵编码标准。 变长码编码可以用流水线结构提高编码的速度，但变长码的解码却很困难。 这是由于变长码的码长是变化的，在前一个码字的码长没有确定之前，不能知道 下一个码字的起始位置。这种数据相关的递归性使其解码难以采用流水线结构来 提高解码速度。 本文研究基于分组的可编程变长码解码算法及其实现结构。通过对码表分组、 排序，采用并行的解码结构，用算术运算方式实现码组搜索及码字的存储地址。 针对不同的应用场合，它可以方便地更换变长码码表而不用修改硬件结构。码表 分组可以有效的节约码字的存储资源；算术运算搜索方式可以方便地更换码表获 得可编程能力；并行的结构能够在每个时钟周期解出一个码字。本文同时给出了 这种算法的实现结构，分析并解决了硬件实现时所遇到的问题，如：缩短关键路 径上的延时等。 本文所设计的变长码解码器采用a l t e r a 公司a p e x 2 0 k 2 0 0 e 器件进行下载验 证。最后，解码器采用s m i co 2 5 n 工艺库综合，共占用4 8 3 1 c e l l s 。实验结果表明， 本文设计的解码器能够在8 0 m h z 的时钟频率下正常工作，满足变长码解码实时处 理的要求。 关键词：变长码，可编程，码表分组，m p e g 一2 v 上海大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fm u l t i m e d i at e c h n o l o g y ，t h ep r o b l e mp e o p l ef a c e di st h e e x p l o s i v e l yi n c r e a s i n gi n f o r m a t i o n i no r d e rt or a i s et h ed a t at r a n s m i s s i o nr a t e ，i n c r e a s e t h eu t i l i z a t i o nr a t i oo fc h a n n e la n ds a v et h es t o r a g er e s o u r c e ，m u l t i m e d i ad a t am u s tb e c o m p r e s s e d v a r i a b l el e n g t hc o d e ( v l c ) ，k n o w na sac l a s s i c a ld a t ac o m p r e s s i o n t e c h n o l o g y ，h a sb e e nr e c o m m e n d e dt ob et h es t a n d a r do fe n t r o p ye n c o d i n gb yl o t so f i m a g ea n dv i d e os t a n d a r d ss u c ha sj p e g 、m p e ga n dh 2 6 xe t c ，d u et oi t sh i g hc o d i n g e f f i c i e n c y v l ce n c o d i n gc a nb er e a l i z e db yt h el o o ku pt a b l e ( l u t ) w i t ht h ep i p e l i n et o m e e tt h en e e df o rh i g hs p e e d b u ti ti sd i f f i c u l tt oa d o p tt h ep i p e l i n ef o rt h ev l c d e c o d i n g ，b e c a u s et h ec o d e l e n g t ho fv l c i sv a r i a b l ea n dt h ec o d e w o r db o u n d a r yc a l l n o tb ed e t e r m i n e du n t i lt h el a s tc o d e w o r d sh a v eb e e nd e c o d e d t h i sr e c u r s i v e d a t a d e p e n d e n tl i m i t st h ed e c o d i n gt h r o u g h p u ta n de n h a n c e st h ec o m p l i c a t i o no ft h e d e c o d e rd e s i g n t h ep a p e rm a i n l ys t u d i e st h ea l g o r i t h ma n dt h ei m p l e m e n ta r c h i t e c t u r eo ft h e p r o g r a m m a b l ev a r i a b l el e n g t hd e c o d e rb a s e do nw o r d t a b l ep a r t i t i o n a f t e rp a r t i t i o n i n g t h ew o r d t a b l ea n dr e o r d e r i n gt h ec o d e w o r d e s ，ab i t p a r a l l e la r i t h m e t i ci sa d o p t e dt o s e a r c hf o ra d d r e s so fc o r r e s p o n d i n gg r o u p sa n dc o d e w o r d si na r i t h m e t i cw a y i tc a n a l t e r n a t et h ew o r d t a b l ec o n v e n i e n t l yi n s t e a do fm o d i f y i n gh a r d w a r e ，a d a p t i n gt o d i f f e r e n to c c a s i o n s t h ew o r d t a b l ep a r t i t i o ns a v et h es t o r a g er e s o u r c ee f f e c t i v e l y ；t h e a r i t h m e t i cs e a r c h i n gw a y r e p l a c ew o r d t a b l ec o n v e n i e n t l ya n dg e tt h ep r o g r a m m a b i l i t y ； t h eb i t - p a r a l l e la r i t h m e t i cd e c o d eo n ec o d e w o r dp e rc y c l e a tt h es a m et i m e ，t h ep a p e r p r e s e n t st h eh a r d w a r ea r c h i t e c t u r eo ft h i sa l g o r i t h m ，a n ds o l v e st h ep r o b l e mm e ti n h a r d w a r ei m p l e m e n t a t i o n ，s u c ha s ：r e d u c i n gd e l a yi nt h ec r u c i a lp a t he t c t h ed e s i g ni sd o w n l o a d e da n dv e r i f i e di na p e x 2 0 k 2 0 0 ep r o v i d e db ya l t e r a w h e ns y n t h e s i z et h ep r o p o s e dd e s i g na t8 0 m h z ，t h eh a r d w a r ec o s ti sa b o u t4 8 31c e l l s u n d e rs m i c0 2 5 p mc m o st e c h n o l o g y ，t h ed e c o d e rc a nw o r ka c c u r a t e l ya n dm e e tt h e r e a l t i m ep r o c e s s i n gd e m a n d s k e yw o r d s ：v l c ，p r o g r a m m a b l e ，w o r d t a b l ep a r t i t i o n ，m p e g 一2 v 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其它人己发表 或撰写过的研究成果。参与同一工作的其它同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：二批日期：2 1 必 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：鲤导师签名：丝墨竺日期： 】i 上海大学硕：b 学位论文 第一章绪论 本章回顾了视频压缩编码的基本方法和视频压缩国际标准，对变长码编码及解 码原理作了简要介绍，总结了变长码的解码算法及其结构和研究成果，分析了各种 解码算法和结构的特点，并简要介绍了本论文所做的研究工作。最后，给出了全文 的结构安排。 i i 课题研究的目的及意义 随着存储、通信等技术的快速发展，用户对多媒体业务的需求不断增长，多媒 体不再局限于文本、语音和图片，视频图像为用户提供了功能更强大、更完善的服 务。由于数字视频在存储、编辑、传输等各个方面均明显优于模拟视频，因此被广 泛地应用于视频会议、可视电话、电子商务、广播电视等多个领域。然而，推广数 字视频应用的最大的困难是直接表达数字图像需要巨大的数据量，同时，人们对图 像的质量和分辨率的要求也越来越高，这就导致了更高的数据率和更加复杂的数据 类型，使得用来描述图像和视频信息的数据爆炸性的增长。这些图像和视频信息在 存储时占有的容量大，在传输时占用的信道宽，在实时应用中要求处理的速度快 【1 ，2 。为了存储、传输和处理图像和视频数据，这就要求有效的数据压缩技术，以 压缩形式存储和传输数据，既节约了存储空间，又提高了传输效率。一种经典的数 据压缩技术是变长码( v a r i a b l el e n g t hc o d e ，v l c ) 编码，也称哈夫曼编码( h u f f m a n c o d e ) ，它是一种最佳无损编码，因其编码效率高，因此被许多图像和视频标准如： j p e g 、m p e g 、l l _ 2 6 3 、h 2 6 4 等推荐作为熵编码标准p j 。 在数学上，v l c 的编码过程是一个从定长码集合到另一个v l c 集合的映射过程， 而解码过程则相反。v l c 编码可以通过查表法来实现，采用流水线结构来满足高速 处理的要求【4 。但是，v l c 解码( v a r i a b l el e n g t hd e c o d e ，v l d ) 难以用流水线结 构来提高解码速度，这是因为v l c 码字长度是变化的，码字之间又没有明显的界限， 只有在当前码字长度确定以后才能够进行下一码字的解码。由于解码过程中的这种 对码长的递归依赖性，限制了解码的速率口o l 。显然，v l c 的解码要比编码复杂得多。 上海大学硕：f ：学位论文 因此，研究高性能的v l c 解码算法及其a s i c 实现结构，一直是多媒体和通信 领域中研究的重点和热点，具有极其重要的经济、社会效率和理沦意义。例如，以 多媒体视频图像处理技术为核心的数字电视、移动视频、网络流媒体、手机媒体、 视频会议等将在我国及全世界相关产业拥有巨大的市场前景。据预测，到2 0 1 0 年， 我国多媒体产业产值将达到1 5 0 0 0 亿元。 1 2 课题的研究背景 1 2 1 视频压缩编码的基本方法 未经压缩的数字视频信号数据量非常大，同时，这些数字视频信号又有很强的 相关性，含有大量的冗余信息。因此可以采取有效措施降低视频信号的数据量和数 码率，去除冗余信息，也就是说要设法对数字视频信号进行压缩，通常将这一过程 称为信源编码。信源编码按其压缩编码原理可分为：预测编码、变换编码和熵编码 1 7 , 8 。 1 ) 预测编码 预测编码基于图像信息的空间和时间相关性，用相邻的已知像素( 或图像块) 来预测当前像素( 或图像块) 的值，并传输实际信号与预测信号差值。信号相关性 越强，预测精度越高，实际信号与预测信号的差值就越小，对其编码后的比特数可 相应减少。 预测编码分线性预测和非线性预测两类。它们可以在一幅图像内进行( 帧内预 测编码) ，也可以在多幅图像之问进行( 帧问预测编码) 。 线性预测编码又称为差分脉冲编码调制( d i f f e r e n t i a lp u l s ec o d e m o d u l a t i o n ，d p c m ) 。d p c m 系统具有结构简单，容易用硬件实现的优点，但其编码 压缩比较低，因此常用在混合编码中。 帧间预测编码主要利用活动图像序列相邻帧间的相关性，即图像信息的时间冗 余来达到压缩的目的，因此可以得到比帧内预测编码高得多的压缩比。帧间预测编 码一般是针对图像块的预测编码，其中运动估计和运动补偿编码现已被各种视频图 像编码标准采用，得到很好的效果。 2 ) 变换编码 变换编码的基本原理就是将原来在空间域上描述的图像信息，通过一种数学变 上海大学硕士学位论文 换( 例如，傅立叶变换、正交变换等) ，变换到变换域( 如频率域、正交矢量空间) 中用变换系数进行描述。尽管图像变换本身并不带来数据压缩，但由于变换后系数 之间的相关性明显降低，图像的大部分能量只集中到少数一些变换系数上，采用适 当的量化和熵编码就可以有效地实现压缩编码，且可以利用人类视觉系统的生理和 心理特点来得到较好的编码系统。 用于图像编码的变换类型主要有：斜变换、沃尔什一哈达马变换、哈尔变换、 k l 变换( k a r h u n e n l o e v e ) 、余弦变换等，除了k l 变换外，都有快速算法。 3 ) 熵编码 熵编码是一种无损压缩编码方式，它是纯粹基于信号统计特性的一种编码技 术，解码后能无失真地恢复原图像信息。熵编码的目的就是去除熵冗余，使编码后 的平均码长接近信源熵值，从而实现码率的压缩。常用的熵编码方法有v l c 编码和 算术编码等。 v l c 编码是一种不等长最佳无损压缩编码方法，它的基本思想是根据符号发送 概率的不同而分配以不同码长的码字。对出现概率大的符号( 携带较少的信息量) 用短的码字编码，对出现概率小的符号( 携带较多的信息量) 用长的码字编码，这 样可使平均码长接近于信源熵。它是一种效率高、方法简单的编码。信源中符号出 现的概率相差越大，v l c 编码效果越好。 算术编码是把一个信源表示为实轴上0 和l 之间的一个区间，信源集合中的每 一个元素都用来缩短这个区间。它从整个符号序列出发，采用递推形式连续编码的 方法。在算术编码中，源符号和码字问的一一对应关系并不存在，一个算术码字要 赋给整个信源符号序列。 在实际的系统中，选择上述几种编码技术的组合，可以在某一可接受图像质量 的条件下，达到较高的压缩比。用于实时电视信号压缩编码的一种成熟方案包括： 基于运动估计和运动补偿的差分脉冲编码调制d p c m ，二维离散余弦变换d c t ，v l c 编码等。这个混合方案是当前提出的几种图像编码国际标准的基础，它们在各种视 频压缩标准中均得到广泛采用。 1 2 2 视频压缩国际标准 经过三十多年的努力，形成了一系列完整、实用的编码方法，这就是一系列的 上海大学硕：| = 学位论文 国际编码标准。每一个标准都是以上几种编码方法的综合运用。目前，视频压缩标 准制定的国际组织主要有国际电信联盟i t u t 的视频编码专家组( v i d e oc o d i n g e x p e r tg r o u p ，v c e g ) 和国际标准化组织i s o i e c 的运动图像专家组( m o t i o n p i c t u r ee x p e r tg r o u p ，m p e g ) 【。两个标准化组织基于不同的应用需求，采用类 似的压缩编码技术，分别制定了 f2 6 x 和m p e g x 系列视频压缩标准f 1 。以上国际 压缩标准尽管应用领域不同，但是均采用了预测编码结合变换量化和v h c 编码的混 合编码模式。其中两大视频标准化组织联合提出的m p e g 一2 h 2 6 2 是现有最成功的 国际视频压缩标准。 1 9 8 4 年c c i t t 第1 5 研究组发布了数字基群电视会议编码标准h 1 2 0 建议。1 9 8 8 年c c i t t 通过了“p 6 4 k b i t s ( p = l ，2 ，3 ，3 0 ) ”视像编码标准h 2 6 1 建议，被 称为视频压缩编码的一个里程碑。从此，i t u t 、i s o 等公布的基于波形的一系列 视频编码标准的编码方法都是基于h 2 6 1 中的混合编码方法。1 9 9 5 年，i t u t 推出 h 2 6 3 标准，用于低于6 4 k b i t s 的低码率视频传输，如p s t n 信道中的可视会议、 多媒体通信等。1 9 9 8 年和2 0 0 0 年又分别公布了h 2 6 3 + ，h 2 6 3 + + 等标准，主要用 于会议电视和可视电话等领域。2 0 0 3 年3 月，i t u t 和i s o i e c 正式公布了h 2 6 4 视频压缩标准，不仅显著提高了压缩比，而且具有良好的网络亲和性，加强了对 i p 网、移动网的误码和丢包的处理。 1 9 8 8 年，i s o i e c 信息技术联合委员会成立了运动图像专家组m p e g 。1 9 9 1 年 公布了m p e g 一1 视频编码标准，码率为1 5 m b i t s ，主要应用于家用v c d 的视频压 缩；1 9 9 3 年1 1 月，公布了m p e g 一2 标准，用于数字视频广播( d v b ) 、家用d v d 的 视频压缩、网络视频通信及高清晰度电视( h d t v ) 。码率从l 5 m b i t s ，1 5m b i t s 直至l o o m b i t s 分别用于不同档次和不同级别的视频压缩中。1 9 9 9 年1 2 月，i s o i e c 通过了“视昕对象的编码标准”m p e g 一4 ，它除了定义视频压缩编码标准外， 还强调了多媒体通信的交互性和灵活性。m p e g 一4 标准是基于图像中的某个内容进 行编码，其具体的编码对象就是图像中的音频和视频对象。m p e g 一4 就是围绕音视 频对象的编码、存储、传输和组合而制定的，主要用于多媒体会议、低比特率移动 多媒体通信、基于内容的交互多媒体数据库检索、网络上的视音频通信等。此外， m p e g7 ( 多媒体内容描述接口标准) 和m p e g 一2 1 ( 多媒体框架标准) 是两个正在研 究和制定中的标准。前者适于音频和视频内容的描述和检索，其应用领域包括：数 4 上海大学硕士学位论文 字图书馆、广播媒体的选择、多媒体编辑、多媒体创作等；后者的重点是将不同的 协议、标准和技术结合在一起，支持连接全球网络的各种没备透明的访问各种多媒 体资源，以便从多媒体内容发布到消费所涉及的所有标准建立一个基础体系。 1 3 课题的主要研究内容 1 3 1 变长码编码原理 v l c 编码根据信源符号出现的概率不同分配码字，对于出现概率较高的符号分 配一个较短的输出码字，对于出现概率低的符号分配一个较长的输出码字。按照概 率出现大小的顺序，对输出码字分f l u 4 ：, 同码字长度的v l c 编码，其输出码字的平均 码长最短，与信源熵值最接近【1 2 。v l c 编码的编码效率高，运算速度快，实现方式 比较灵活，因此在数据压缩领域得到了广泛的应用，被许多图像和视频标准如： j p e g 、m p e g 、h 2 6 3 、h 2 6 4 等推荐作为熵编码标准。 v l c 编码是以信源概率分布为基础的，但一般无法事先知道信源的概率分布， 通常采用对大量数据进行统计后得到的近似分布来代替，这样会导致实际应用时 v l c 编码无法达到最佳性能。利用根据输入数据序列自适应地匹配信源概率分布的 方法，可以较好地改进v l c 编码的性能。v l c 编码的一般算法如下u 3 , 1 4 ： 1 ) 首先，统计信源中各符号出现的概率，按符号出现的概率从大到小排序。 2 ) 把最小的两个概率相加合并成一个新的概率，与剩余的概率组成新的概率 集合。 3 ) 对新的概率集合重新排序，再次把其中最小的两个概率相加，组成新的概 率集合。如此重复进行，直到最后两个概率的和为1 。 4 ) 分配码字。码字分配从最后一步开始反向进行，对于每次相加的两个概 率，给大的赋l ，小的赋0 ( 也可以全部相反，如果两个概率相等，则从中任 选一个赋0 ，另一个赋1 即可) ，读出时由陔符号开始一直走到最后的概率和 1 ，将路线上所遇到的o 和1 按最低位到最高位的顺序排好，就是该符号 的v l c 编码码字。 下图1 1 用一个实例说明v l c 的编码过程。 上簿大学硕士学位论文 信源符号出现概率 图1 1v l c 编码举例 由图1 1 中的示例数据可得到的结果见表l _ 1 。 表1 1v l c 编码结果 口ld 2码a 4n 5盘6 以， a o 2 2o 1 90 1 8o1 7o 1 50 0 80 0 1 2233344 w l 1 11 00 l l0 1 0 0 0 l0 0 0 1 0 0 0 0 其编码后的平均码长w 为： 品= 嘲 i = 1 = 2 ( o 2 2 + o 1 9 ) + 3 x ( o 1 8 + o 1 7 + 0 1 5 ) + 4 x ( o 0 8 + 0 0 1 ) = 2 6 8 上述v l c 编码方法具有以下一些特点： 1 ) 形成的码字是可识别的，能够保证一个符号的码字不会与另一个符号的码 字的前几位相同。即编出来的任何一个码字都不是另一个码字的前缀，保证了每 个码字的唯一可解性。比如说，如果a 1 的码字为1 1 ，a 3 的码字为0 1 1 ，而 a 4 的码字为0 1 0 ，a 5 为0 0 1 ，则当编码序列中出现0 0 1 0 1 1 时，就能判别 它不是a 4 的码字后面跟一个a 1 的码字，而是a 5 的码字后面跟了一个a 3 的码字。 2 ) 对于不同信号源的编码效率不同。当信号源的符号概率为2 的负幂次方时， 达到1 0 0 的编码效率：若信号源符号的概率相等，则编码效率最低。 3 ) 由于0 与l 的指定是任意的，故由上述过程编出的最佳码不是唯 的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。 酹 m 删 眭睁 2 2 3 3 3 4 4 丝 侈 博 ” 叭 0 0 0 o 0 o 0 引 趾 甜 ；3 斯 盯 上海大学硕士学位论文 1 3 2 变长码解码原理 在一些实时应用场合中，人们对v l c 解码芯片的解码速度要求越来越高，解 码算法的研究也逐渐引起了人们的注意。尤其在一些嵌入式系统中，v l c 解码模 块往往成为限制系统速度的瓶颈。这主要是由于v l c 编码后的码字长度不固定， 码字之间又没有明显的界限，只有在当前码字长度确定以后才能够进行下一码字的 解码。解码过程中这种数据的递归依赖性在编码过程中不会出现，因为信源符号都 以同样的长度进行编码，流水线结构能够提高编码的速度。进行v l c 解码时，要求 能够判断一个码字的起始位置，并对接收到的一串码字做出正确且唯一的划分；此 外，还要解决输入输出速率匹配的缓存等问题。因此，高性能的v l c 解码结构远 比编码复杂。 v l c 的解码过程是从一个v l c 集合到另一个定长码集合的映射过程。为了解出 信源符号，解码器必须有一个与编码对应的v l c 码表( 或称查找表) 。这可以通过 传送查找表获得，或者通过给已编码的符号发送信源符号及其概率的清单而获得。 解码过程就是把每一个唯一的可解码字转换成原始的信源符号，如表1 1 的逆过程： 码字1 1 解码后为a 1 ，码字叭1 解码后为a 3 ，而码字0 1 0 解码后为a 4 。 解码开始时，首先要从经过v l c 编码的码流中读入l 比特或多个比特的二进制码 流，通过与查找表进行比较，找到相匹配的码字，从而得到解码后的符号【1 ”。 v l c 常常表示成一个码树结构，故v l c 的结构和编码规则决定了解码时有时需 要逐位分析比较才能确定出一个码字，得到码字长度和解出码字符号。这样，一个 时钟解一位码效率太低，可能无法达到实时解码的目的；其次，由于解码时每一个 码字的长度不一，无法按一定的时钟节律进行处理，从而在对解码系统进行控制时 将会非常复杂；再者，由于v l c 的码长由其码字内容来决定，从这种码字结构上来 看，采用d s p 核来解v l c 效率很低。因此，目前大多数视频解码器都设计了专门的 v l c 解码单元来进行v l c 解码f l “，如p h i l i p s 的t r i m e d i at b l l 3 0 0 、三菱公司的d 3 0 v 等。 1 4 已有的变长码解码算法及结构 从硬件实现的角度上来划分，v l c 的觯码结构一般叮以分为串行解码和并行解 码两种方式。 上海大学硕士学位论文 1 4 1 串行解码方法 串行解码方法根据v l c 码树结构的特点，从根结点到叶结点每个周期解码一个 码字的一位。其中比较经典的是m u k h e u e ep 7 提出的基于码树结构的树搜索算法， 它是一种串行解码方案，其解码结构如图1 2 所示。在每个时钟周期逐位读入输入 码流的一个比特，与码表内的各个码字进行逐位比较匹配。解码器每读取一个比特 a 。，就将它与以前读取的比特组( a a ：a 。) 进行组合得到( a 。a ：a 。a 。) ，然后 将它与查找表进行比较，如果在查找表中找到相同的码字( a a ：a n - j a 。) ，则与之 对应的值就是该v l c 解码输出的值，否则继续读取下一比特。 这种结构的查找表采用只读存储器( r e a d o n l ym e m o r y ，r o m ) 来实现。由于 v l c 的码字长度是不确定的，而r o m 的查表输入应能表示为地址格式，必须是定长 的。为实现查表，需要将码字扩展成最长的码字长度。例如，对于m p e g 一2 中帧内 亮度和色差系数的v l c 码表，最长的码字是1 6 比特长，查表输出包括5 位码字长 度、6 位t u n 和1 2 位l e v e l 的d c t 系数，于是用r o m 查表时，其容量要达到2 2 3 比特。而实际有效的码字只有1 1 3 x2 个，实际解码用到的r o m 资源只有1 1 3 x 2 x2 3 比特，绝大部分资源都被浪费掉了。 图l - 2 串行解码方法示意图 上海大学硕士学位论文 董培良等提出一种前n 位的快速解码算法【”】，它从码流中读出最前面的n 位， 当被解码码字实际长度小于n 时，能一次解码，反之则从n + 1 位开始按传统方式解 码。该算法对于短码字解码速度快，但是短码字是叶节点深度差别较大的部分，用 前1 1 位建立查找表，需要内存2 ”字节，内存中的冗余数据仍然很多，并且v l c 码 字长度还要另行计算。此外，对于长的码字，虽然出现的概率比较小，但是由于其 解码速度没有明显改善，因此对整体解码速度的提高有一定的限制。 串行的树搜索算法解码方式结构简单，比较适合于对低码率的视频码流进行解 码。如对h 2 6 1 h 2 6 3 标准规定的图像大小为3 5 2 x2 8 8 像素的c i f 或1 7 6 1 4 4 像 素的q c i f 格式视频图像进行解码，可以满足实时处理的要求。但是，这种解码方 法的解码时间取决于码字长度，对长的码字序列来说，解码时间很长。此外，因为 对每个码字来说，操作时钟周期是变化的，所以，它们的i o 条件和缓冲器设计也 十分复杂。采用这种方法来对性能要求较高的实时应用的v l c 解码，显然是不适合 的。 1 4 2 并行解码方法 v l c 由于其码字长度不固定，解码器在确定当前码字长度之前，不能开始下 一个码字的解码，所以在整体设计上很难使用流水线技术来提高解码速度。因此， 一般采用并行的策略进行解码。并行解码的意思只能是对某一个v l c 码字的多个 位同时进行解码，而不是对多个v l c 同时解码。并行解码方式可以实现每个周期 解出一个码字，而不用考虑码字的长度问题。 s u n 和l e i 1 9 , 2 0 1 提出了一种位并行解码方法，通过当前码流与查找表中所有可 能的码字进行模式匹配，实现在一个时钟周期内解出一个码字。其v l c 解码结构图 如图1 3 所示。这种解码算法可以实现固定的解码操作时间，从而提高了系统的性 能，减少了控制复杂性。它采用基于可编程逻辑阵列( p r o g r a m m a b l el o g i ca r r a y ， p l a ) 的并行查找表方案。p i 。a 作为多端输入输出网络，由一个“与”阵列和一个 “或”阵列串接而成，其内部的“线与”、“线或”恰恰是最合理、最佳地反映出 输入输出逻辑变量的“与一或”表达式。因此，这种逻辑器件的硬件冗余度最低。 p l a 具有高速的特点，它对输入变量的位数不很敏感，信号延迟仅为p l a 的读出时 间。此外，p l a 中存储的是以码流中的码字为输入、解码的码值和码长为输出的真 上海大学硕士学位论文 值表，没有多余的数据，所以它的面积可做到比r o m 小得多。因此并行解码方法在 存储面积、解码速度等方面都优于串行解码方法。 p l f 镕5 4 1 j ：d e c r i e r 图13 基于p l a 的并行v l e 解码结构 近年来提出了很多优化解码方案，如r h a s h e mja n 2 1 1 提出了多级查找法；y m k y e o n g 2 2 1 等人提出了最大匹配查找表方法；b j s h i e h 2 3 , 2 4 1 等人提出了分组优化 查找法等；惠新标等 2 5 , 2 6 1 根据v l c 码表特性，提出了将码表分割成多个小码表以提 高系统性能的思想；a s p a r 等【2 7 l 提出优化查找表的方法；n i k a r a 等提出前n 位 的并行解码算法，打破了v l c 的数据递归依赖性；此外，低功耗的变长码解码器的 设计也正成为近年来的研究热点 2 9 , 3 0 , 3 1 】。这些算法的基本思路都是对码表的结构进 行重新调整，减少遍历二叉树的计算量和存储结构，通过使用不同的分组或分级原 则对码字进行排序、分割、分组，以实现快速高效的搜索和最少的存储资源占用。 1 5 本论文所做的研究 由于v l c 码表的种类繁多，对于较大的v l c 码表，如果采用完全搜索的方式查 找码表中所有的码字，不但搜索时间长、效率低，解码延迟大，而且会造成很大的 存储资源的浪费。本文根据v l c 码表的结构特点，把一个大的码表分成若干个小的 上晦大学硕士学位论文 码组，再对这些小的码组进行分别搜索。这样，不仅可以提高搜索效率，缩短解码 时间，还可以大大地节约码字的存储资源，特别是对于大的码表解码时其效果尤其 明显。 以往的码字搜索方案都是按照模式匹配的方式实现的，也就是将输入码流与码 表中的码字逐一进行比较，从而找到唯一相匹配的码字。而本文采用的是用算术运 算方式搜索码组。首先对码表进行分组和排序，通过算术运算找到相匹配的码组及 码字的存储地址。这种解码方式有利于实现可编程的结构，针对不同的应用场合， 它可以方便地更换v l c 码表而不用修改硬件结构。这种结构可以满足不同场合的应 用，例如，卫星对地面扫描时，对于凹凸不平的大陆和平整的海洋画面，其原始图 像符号概率显然有很大差别，因此针对不同的应用场合，可以采用用户自己定义码 表来提高压缩比。为方便起见，本文以m p e g - - 2 的d c t 系数码表为例，来进行v l c 解码器设计的阐述。 此外，解码器的设计采用了并行的结构，从而实现每个时钟周期解出一个码 字。 1 6 本文的章节安排 本篇论文主要研究基于分组的可编程v l c 解码算法、结构及其硬件实现。本文 首先回顾了国内外各研究机构的研究成果，比较各种v l c 解码算法及其结构的优缺 点，从而引出了本文研究的重点。根据v l c 码表的特征，对码表进行分组达到节约 存储资源的目的；采用算术运算的方式获得解码器的可编程能力，针对不同的压缩 图像场合，可以选用不同的码表而不必改变解码器的硬件结构。最后，对该v l c 解 码器的硬件验证及其a s i c 实现做出详细阐述，并对其性能做出评估。 本文章节安排如下： 第一章阐述了课题研究的目的及其意义，并指出了本文的研究内容；介绍了本 课题研究的背景：视频压缩的国际标准和基本的视频压缩编码方法。本章概括了传 统v l c 解码器的研究成果，从v l c 编码的基本原理出发，指出了设计v l c 解码器的 技术难点，从而引出了本文研究的重点，即可编程v l c 解码器。 第二章介绍了基于分组的可编程v l c 解码算法。为节约码字的存储资源，对 v l c 码表做出分组，并采用算术运算的方式搜索码组及码字的存储地址，随后给出 上海大学硕士学位论文 了整个v l c 的解码过程。 第三章给出了整个v l c 解码器的结构，并详细的给出了各个组成模块的实现结 构；对解码器提出了一些改进和优化措施，缩短关键路径上的延时，从而提高了整 个解码器的性能。 第四章首先给出了本设计r t l 级的仿真结果；接着，采用s y p l i f y 工具对r t l 级设计做出综合；然后把综合后的结果下载到f p g a 中，利用o u a r t u s 软件及内嵌 式逻辑分析仪s i g n a l t a p 对测试结果做出分析和验证。 第五章给出了v l c 解码器的芯片实现。描述了v l c 解码器芯片实现的设计流程。 然后，对逻辑综合以及自动布局布线等分别做出阐述。最后，对该解码器芯片的性 能做出评估和总结。 第六章对全文做出总结，并对未来的进一步工作做出展望。 上海大学硕二b 学位论文 第二章基于分组的可编程变长码解码算法 本章着重介绍了基于分组的可编程v l c 的解码算法- 根据v l c 的码字特征， 对d c t 系数码表进行分组；根据码字的分组和存储映射，将数字特征应用到码字、 符号地址和码流；采用算术运算的方式实现解码。 2 1 基于r a m 的可编程算法 v l c 编码是以信源符号概率分布为基础的，一般无法事先知道信源的概率分布， 通常采用对大量数据进行统计后得到的近似分布来代替，这样会导致实际应用时 v l c 编码无法达到最佳性能。根据输入数据序列自适应地匹配信源概率分布的方法， 可以较好地改进v l c 编码的性能。 但一般的基于p l a 的解码方法都是针对固定的v l c 码表进行解码的。它针对每 张码表都需要设计一个v l c 解码器，这对硬件资源造成了很大的浪费。 研究报告显示：一个2 0 0 项左右分支的p l a 码表耗费4 0 0 0 门左右的硬件资源， 约占整个v l c 解码部件硬件资源的三分之一左右，而且大的p l a 码表会导致电路的 关键路径过长，因此，纯粹的p l a 并行解码算法并不适合于解大的v l c 码表。另一 方面，由于一段视频码流可能使用多张v l c 码表，若采用基于p l a 并行方式解码， 则对于每一张码表都需要一个p i a 来实现，这对存储资源同样也造成了很大的浪 费。 基于p l a 和基于r o m 的系统缺乏可编程能力，而基于c a m 的设计需要更高的成 本去存储所有可能的模式3 2 】。随着存储映射方案的效能提升，基于r a m 的v l c 解码 结构有利于降低设计成本，节约存储空间，而且还可以通过更改存储内容来获得可 编程能力。具有可编程能力的解码器根据压缩资源的内容定义码表，有利于增加数 据的压缩效率，并可以根据图像内容方便地更换码表而不用重新设计系统的硬件实 现结构。另外，把具有相同码字特征的码字组合成一个组，还可以大大节省存储空 旧【。 上海大学硕士学位论文 2 2 码表分组的方法 v l c 的码表结构有一个明显的特征，就是一个码通常由若干比特的前缀 ( p r e f i x ) 以及若干比特的后缀( s u f f i x ) 组成，如m p e g 一2d c t 系数中码字： 0 0 0 0 1 0 1 ，其中开头有四个0 和一个1 组成码字的前缀，o l 构成码字 的后缀。通过码字的前缀检索到整个码字的长度c o d e e n g t h = 7 ，通过码字后缀可 以检索到解码的码值r u n = 9 ，l e v e l = l 。由此可见，可以根据码字前缀对码表进行 分组，并根据码字后缀查询码值，达到快速查询码表进行解码的目的，这样一方面 可以加速对码表的查询速度，提高搜索效率，另一方面，还可以节约码字的存储资 源，特别是对于大的码表解码时其效果尤其明显。 v l c 编码的限制是码字要有单义性( 唯一可译) 和非续长性( 瞬时可译) 。单 义性代码是指任意一个有限长的码字序列，只能被唯一地分割成一个个码字，而任 何其他分割方法都会产生一些不属于码字集合的码字，符合这个条件的代码为单义 代码。v l c 编码方法形成的码字是可识别的，即能够保证一个符号的码字不会与另 一个符号的码字的前几位相同。非续长代码是指任意一个码字都不是其他码的续 长，即码字集中任意一个码字都不是在其码字后面添加一些码元所构成。 基于v l c 编码特性，把同样码字长度的源符号组合成一个组，实现v l c 编码 分组操作。码表分组应该遵循两条原则： 1 ) 在同一个分组中，所有的码字都具有相同的码字长度； 2 ) 同一分组中的码字，具有相同的码字前缀。 基于以上两条分组原则，分组的码字应该具有以下特征： 1 ) 在同一个分组中，由于码字具有相同的长度，码字可以看作是一个码字长 度的二进制数字，这里称作b i n a r y c o d e 。 2 ) 在一个码表分组中，把最小的b i n a r y c o d e 码字标记为m i n c o d e 。 3 ) m i n c o d e 和b i n a r y c o d e 之间的差值( 也可称偏移值) 称作b i n a r y o f f s e t 。因 为在同一分组中的码字有相同的前缀，所以，b i n a r y o f f s e t 的位长是后缀字长，即码 字后缀的长度。 分组的一个实例在表2 1 给出，在表中，符号x 7 、x 8 、及x 2 2 属于同一码 表分组g 3 ，在这一分组中，码字有同样的码字长度：1 4 位，同样的前缀：l o 位 上海大学硕= ：学位论文 0 0 0 0 0 0 0 0 0 1 ，码字后缀的字长是4 位。因此，1 4 位的b i n a r y c o d e 分别是 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ，0 0 0 0 0 0 0 0 0 1 0 0 0 1 ，0 0 0 0 0 0 0 0 0 1 1 1 1 l ，m i n c o d e 是1 4 位0 0 0 0 0 0 0 0 0 1 0 0 0 0 ，4 位b i n a r y o f f s e t 分别为0 ，1 ，1 5 。有些码字长度尽管 相同，但没有组合的符号属于不同的组，如x 0 属于组g o ，x 2 3 属于组g 4 。x 0 独自完成了v l c 编码过程，这里仅有一个符号在组g o 中；同样，组g 4 中也仅有 一个符号x 2 3 。 表2 1v l c 编码的码表分组 g r o u ps v m b o lp r s l l x s h f f i xb m a r v c o d e b i n a r y o f f s e t a t t r i b u t e g 0 x o o l o0 1 0 0 m i n c o d e x l0 0 1 1o0 0 1 1 0om i n c o d e g 1 x 20 0 1 l10 0 1 1 11 x 30 0 0 10 0 0 0 0 1 0 0 om l n c o d e x 40 0 0 10 10 0 0 1 0 11 g 2 x 5 0 0 0 11 00 0 0 1 1 0 2 x 60 0 0 11 10 0 0 1 1 13 x 7o o 0 0 0 0 0 0 0 10 0 0 00 0 0 0 0 0 0 0 0 1