精华公布栏

发信人: champaign (原野), 信区: ECE
标  题: 在TMS320C80上实现的一种可变长解码算法
发信站: 紫丁香 (Sat Jan  8 19:34:03 2000), 转信

发信人: fangf (方方), 信区: DSP
标  题: 在TMS320C80上实现的一种可变长解码算法
发信站: 饮水思源站 (Mon Aug  9 09:15:29 1999) , 站内信件

在TMS320C80上实现的一种可变长解码算法
谭径微，周璇，方勤，余松煜
(上海交通大学图象通信与信息处理研究所)
随着数字技术的高速发展，出现了很多视频编码标准，如JPEG、H.261、MPEG1、MPEG

2、H.263［1］等.这几种视频编码标准都采用了以下方法：① 离散余弦变换DCT，用于
减少帧内的空间冗余度；② 运动补偿MC(JPEG除外)，用于减少帧间的冗余度；③ 可变长
编码VLC，也称哈夫曼编码，用于去除经过DCT和量化后的统计冗余.VLC是一个查表的过程
，它根据输入数据统计特性，给数据分配码字(codeword)，从而达到进一步压缩的目的.
因此，必须建立一个码表，将每一个输入的数据与其VLC码字对应起来，以便解码时进行
查找.可变长解码(VLD)是VLC的逆过程.它通过查找码表，找到对应VLC编码的数据值，并
确定该码字的长度，然后将数据值输出，并将码字长度返回至输入端，将输入码流移动码
字长度位，使输入码流指针指向下一个码字的开始处.VLD必须依赖码流指针，所以无法同
时进行两个可变长码字的解码，这就限制了解码速度.另外，以H.263中DCT的系数(run,
level,last)为例，其VLC码表中只有102个码字，但其码字的长度范围却是2~12位(不包
括符号位)，如果不对输入码流进行预处理，而直接将各个码字长度扩充为12位，将对应
的数值作为码表的下标，该码表的长度将是4 096(212)个存储单位.同时，因为码表内应
该包含解码值及码字长度两部分信息，如果每部分信息用16位来存储，则需要16384 B.
在片内RAM容量较小的系统中，是无法存储的，为此，VLD码表应设计得较小.高速信号处
理器TMS320C80具有高速并行处理的能力，但片内存储空间很小.本文使用C80开发了
H.263编解码系统.为了提高系统的解码速度，提出了一种改进的VLD算法，它减少了VLD
码表存储空间，可存储在C80的片内RAM中，免去了片内与片外数据交换的开销.
1高速信号处理器TMS320C80
随着序列图象处理实时性要求的提高，单片DSP处理器的速度一般达不到要求.TMS320C80
［2］在一片C80内集成了多个功能强大、可编程的处理器和图形系统控制器，包括1个
RISC主处理器(MP)和4个并行处理器(PP).
PP肩负着大部分的运算任务，PP的核心是一个数据单元和两个地址单元，其指令字为64位
，每个指令字内分别有控制数据单元和2个地址单元的场，这些场是独立的，每个指令由多
个独立场构成，每个场指定一个独立的操作，一个指令字内便可指明多个操作.每个PP在一
个时钟周期内可完成10个RISC级的并行操作 .全局和局部2个地址单元(address unit)在
一个周期内可以同时进行存储器操作.由于存取操作是独立于数据单元操作的，所以数据单
元和2个地址单元的操作可以并行执行.如果指令内不需要地址单元进行存储器访问，地址
单元便可对寄存器数据进行算术操作，使C80的处理速度较一般的DSP快，特别适用于图形/
图象处理.本文提出的VLD算法就是利用了PP的数据单元和地址单元的并行处理能力，使看
上去增加的操作，而在实际实现中与其他操作是并行执行的，从而在改进算法的同时没有
增加额外的开销.
表1VLC码表概况
Tab.1VLC table information
VLC码表码字长度/位码字数目未经预处理的码表长度
帧内MCBPC1~99512
帧间MCBPC1~921512
MODB1~234
CBPY2~61664
MVD1~13648192
TCOEF2~121034096
但是，C80也有其局限性，那就是每个PP的片内存储空间比较小.虽然C80的传输控制器TC提
供了片内与片外存储器的数据传输，并支持块传输，但是从片外进行数据的存取操作所需的
时间是在片内进行数据存取的10倍.所以只有当一次传输整块的数据，即将数据打"包"
进行传输，并且数据传输操作可以与其他操作并行时，TC的效率才得以充分利用.VLD的操
作需要经常查找码表，每次查表只是查找一个数据，而且码表的查找操作依赖于上一次的查
找结果，故不能用到"包"传输.如果将码表放在片外，存取操作会需要很多时间.为了提
高系统的解码速度，应该将码表放在PP的片内RAM中.所以，码表必须设计得比较小，才能够
存储在PP的一个片内RAM中.本文的VLD算法就是为克服C80较小片内存储空间的问题而设计
改进的.

2可变长解码算法
在H.263中有6个VLC码表：帧内MCBPC(宏块类型和编码块色度模块)、帧间MCBPC、MODB(B块
的宏块模式)、CBPY(亮度编码块模式)、MVD(运动矢量)、TCOEF(帧内块的DC系数).其中MO
DB由于码表简单，只有3个码字，并且有一定的规律，所以不必进行码表的设计，可通过软
件的判断直接获得.VLC码表如表1所示，其中码表长度是指将解码值及其码字长度作为一个
"单元字"，每个码表中包含这样的"单元字"数.
传统上，人们用码树来表示VLC的码表.图1所示是CBPY的码树.如果将此二叉树写成完全二
叉树，那么在最低端有26(=64)个叶子.也就是说，如果不经过预处理，将其写成码表，
码表的大小将是64个单元字.其中，从表1可以看到，MVD与TCOEF的码表很大，需要进行预
处理.同时，由图1可看出，码字为"11"的"叶子"深度较小，故CBPY码表也可通过预处
理，来进一步降低其长度.下面将具体给出在C80上对VLD码表进行预处理的算法步骤.
2.1码表的建立
H.263的5个VLD码表(MODB除外)中，帧内MCBPC及帧间MCBPC仍采用二叉完全树，分别
对CBPY、MVD及TCOEF分为子完全树.由于CBPY码表较简单，本文以CBPY为例来说明
算法.由
表2CBPY码表
Tab.2CBPY table
0
1
2
3
4
5
01234567
-1/0-1/0a/6b/6c/5c/5d/5d/5
e/5e/5f/5f/5g/4g/4g/4g/4
h/4h/4h/4h/4l/4l/4l/4l/4
j/4j/4j/4j/4k/4k/4k/4k/4
l/4l/4l/4l/4m/4m/4m/4m/4
n/4n/4n/4n/4o/4o/4o/4o/4
CBPY的二
叉树可以看出，当其码字长度为2位时，只有一个码字：11，并且由它产生的完全树的叶子
有24(=16)个.不妨将由码字11产生的分支"剪掉"，另作处理，可以将它作为另外一棵
完全树，这棵完全树的根即为叶子，其深度为1.当读进来的6位码子的值大于48时，就认为
是"11"这棵树，从而可解出该码字为"11"，长度为2，继而确定其对应的数据值(设其为
p).这样，码表CBPY就可分为2个表，第一个表的长度为48，第二个"表"的长度为
1.如果将每个码字对应的数据值(或称码表中的符号)用英文字母来表示，则第一个码表
如表2所示.
MVD及TCOEF的码表设计思想同上：根据码树的特点，分别分成3个子完全树.从而降低每个
子树的深度，减少浪费的存储空间.
2.2码表的查找过程
以CBPY为例，其码表的查找过程是：(1) 从码流内读数.每次从码流中读入码树中最长的码
字位数.由于CBPY中最长的码字为6位，所以读进6位数.(2) 判断该码字属于哪一个码树.
对CBPY，当6位数不小于48时，得出该码字在"11"生成的子树中；反之，则该码字在第一
个码表中.(3) 查表解出码字对应的数值及码字的长度.在CBPY中，如果由步骤(2)知该码
字在第一个码表中，则这6位数即代表该码字在第一个码表中的位置.从中读出数值及码字
长度即可.若在第二个码表中，则知该码字为"11"，因为第二个码表只有一个码字，可以
认为该码字的位置是在第二个码表的0处，将读入的6位数右移6位即可得到"11"所在的位�
置了(实际上，第二个码表并不需要，在程序中可直接给出"11"所对应的数据值和它的长
度：2).MVD或TCOEF码表的原理相同，即：若码字在另一个子码树中，将读入的数值右移一
定的数目，即可获得该码字在码表中的位置.继而查表，获得码字对应的数值及码字的长度
.(4) 将码字的长度反馈至输入端，将指向输入码流的指针移动至下一个码字的起始处.

2.3码表的存放
虽然对各个码表进行了预处理，减少了部分存储空间的浪费.但是码表在内存中若存放得当
，会更进一步降低存储空间.这是在许多关于VLD算法中被忽视的问题.作者在用C80开发H.
263解码软件系统时，注意到了这个问题，并结合C80的特点，提出了在内存中存储码表的方
案，收到了满意的效果.
每个VLD码表中，解码值包括两部分：VLC编码对应的解码值及VLC码字长度.研究解码值发
现，除了TCOEF解码表中的解码值需要用16位表示外，其余的解码值只需一个字节(8位)即可
存放.而所有码字长度均只需4位便足够了.C80的PP在片内只有3个2 KB的Data RAM, 一个2
KB的PRAM，整个解码系统的运行还需要许多其他的参数，它们必须存储在片内.为了提高
系统的处理速度，VLD码表也应该放在片内.如果不考虑解码值的大小，一律将它们按照32位
或16位来分别存放解码值和码字长度，所需存储空间是很大的.用32位即C80中一个word来
存放，整个H.263的6个VLD码表需1 796 word或7 184 B；若按16位存放，则需3 592 B.均大
于一个PP的片内RAM.显然是不可行的.
如果不用传统的解码值与码字长度一起存放，而将它们分开存放，组成解码值表和其码字长
度表.将每个码字长度只用4位二进制数表示.由于C80和许多DSP一样是以字节为存取单位的
，所以将两个码字长度合并，存放在一个字节中(见图2(c)).当然，在解码时需进行一个分
解操作，才可从8位数中提取出所需的4位码字长度.经过这样的存放，H.263的所有码表只
需1 650 B.在一个PP的片内RAM中即可存放.
图2CBPY可变长码表内存存放结构
Fig.2CBPY VLD table structure in the onchip memory
以CBPY为例，其解码值表及长度码表在内存中存储结构如图2所示.如果从寄存器中读出的6
位码字为(100100)2=(36)10时，则需分别查找CBPY的解码值表和解码长度表.查
解码值表时按照下标36来查，得到解码值m；查长度表时，需按以下步骤进行：(1) 将
读入的6位码字(100100)2右移一位得到(10010)2=18；(2) 按照下标18从长度码表中读
出一个字节的值为(4，4)(字节表示为：01000100)；(3) 判断最初读入的6位数为奇数还是
偶数，即读(100100)2的末位数，若为0，则取(01000100)2的4~7位，即取第二个4；反
之，则取(01000100)2的0~3位数.从而得到码字的长度为4位.

3结论
传统的逐位分析解码树方法速度很慢.本文用Miss America图象序列的前70帧进行解码测试
，实验结果是该方法的解码速度比本文采用的方法慢1/2左右.
Reza［3］提出了一种改进的解码树方法，其特点是VLD码表存储空间小.对最长码字
为13位的码表，Reza采用分组读入码流的方法.第一次读进4位数，根据这4位数查找码表，
如果该码字长度大于4位，则表明需继续读入码流，并可查出需读入的位数(小于等于4位)，
再从输入码流中读入4位数，如此下去.反之，即找到该码字对应的解码值及其长度.
但这种方法应用在C80开发的解码系统中时，与本文方法比较，就会有很多劣势，这也是作
者不采用该方法的原因：
(1) Reza方法建立的码表需要存储三方面的信息：① 是否找到码字的标识信息；② 码字
长度信息或下一组的深度信息；③ 解码值或下一组的起始地址信息.本文方法只需要存储
解码值及码字长度.使用Reza方法建立的码表占用的内存空间只比本文的方法少150 B，存
储空间上该方法的优势不明显.
(2) 任何方法在存储上占有优势时，在运行速度上就要有所牺牲.Reza方法也是一样，它在
每次查找码表中的一个组时，需进行一次加法运算，用来计算码字长度或码字在下一个组的
位置.最差时需查找三个组，才可找到码字，即要进行三次加法计算.而每次计算要
依赖于上一次的计算结果，所以无法利用C80并行处理的优势来提高速度.本文方法不需要
加法计算.
(3) 本文方法在每次查码表时，只需一次读码流操作，而Reza方法不可避免地会出现两次或
两次以上的读数操作.在C80上运行读码流操作，每次需9个系统时钟周期(cycle).两次读
数操作便需18个系统时钟周期.故Reza方法在读数操作上用去了较多的时间.本文方法采用
一次读数的方法，即每次读进的码字数为该VLC码表中最长码字的长度.速度较Reza的方法
快.
(4) 为了减少存储空间，本文方法采用了"纵向剪枝法"和解码值与码字长度分别存放，将
两个码字长度合放组成一个存取单元(一个字节)的方法，所以在读码字长度时需进行一个分
离码字长度的操作.这个操作看上去好像是较Reza方法"多"出来的操作.但由于C80提供
了数据单元与地址单元并行执行的机制，即在一个时钟周期内可同时实现数据单元计算、地
址单元的本地地址单元和全局地址单元的存取，最多时可在一条指令周期内并行处理3条指
令.这样，编程时便可将分离码字的操作(实际上只使用了3条C80汇编语句)与其他语句并
行执行，在系统周期上，可认为这个操作不存在.所以，C80硬件系统的支持，使本算法既
达到了减少存储空间的目的，又没有人为地降低速度.
(5) 用图象序列Miss America的前70帧进行解码测试，本文方法较Reza方法的解码速度提高
了9.4%，且能够以12.5帧/s的速度实现CIF格式的解码.实践证明，上述改进方法对类似C80
这样的具有高运行速度的系统是适用的，整个解码系统可得到满意的效果.作者应用
TMS320C80开发的全软件H.263解码系统在C80的一个PP上实现了QCIF和CIF的解码，同时这
个系统还实现了H.263中除算术编码以外的其他选项.
参考文献
1International Telecommunication Union. Draft ITUT Recommendation
H.263:video coding for low bitrate communication. ITUT, May， 1996.
2Texas Instruments. TMS320C80 multimedia video processor(MVP)parallel
processor. TI， 1995.
3Reza H. Design and hardware implementation of a memory efficient huff
man decoding. IEEE Transaction on Consumer Electronics, 1994,40(3):345~352
返回摘要
返回目次

--
    感情是一个难以驯服的野马
    理智却是一个严厉的马夫

※ 来源:．紫丁香 bbs.hit.edu.cn．[FROM: 202.118.228.139]