二维DCT编码的DSP实现与优化

1 引言

　　现今的图像编码标准，一般采用纹理编码方式对图像进行压缩。这种方式极大的利用了图像数据的空间相关性，使图像数据的压缩能够达到很高的比率。它主要是利用数学变换的方法，使用极少量的离散信号来表示大量的时域连续信号[1]。常用的数学变换有很多种，比如离散傅立叶变换DFT、沃尔什变换、哈尔变换、斜变换、离散余弦变换DCT、离散正弦变换DST 、K-L变换等。其中，K-L变换为理想状态下的最佳变换方法，但是，由于K-L变换没有快速的变换算法，而DCT、DFT和DST都具有与K-L变换近似的良好性质，尤其是当一阶马尔可夫过程相邻元素相关系数ρ逼近1时，DCT的近似性能远远优于其它两者，并且DCT变换有具体的快速算法。因此，图像压缩标准中，使用DCT变换来实现纹理编码。

　　由于DCT变换在各种编码标准中要被反复调用，因此，其代码执行效率对实时视频压缩起着至关重要的作用。实际应用中，如何实现DCT变换的编码及如何用硬件电路实现这种编码变换是使用者关心的问题[。本文将利用DSP实现图像的二维DCT变换并对其实行优化。

　　2　DCT 变换

　　1974年Ahmed和Rao首先给出二维DCT 变换的数学表达式。该表达式适用于N点的DCT定义，但是，由于MPEG编码一般是把视频图像帧或图片分为场、片、宏块的结构，一帧图像一般包括1－2场，每场包括若干片，每片包括若干宏块，为了方便处理，把每个宏快分成8×8的子块，即DCT处理的基本单元是8×8的子块。因此，直接定义实用8点二维DCT变换：

　　其反变换为：

　　其中 ，i,j,u,v=0,1…7.

　　在（1）式中，把变换核分离可得两次一维DCT变换：


　　因此，可以使用2次一维DCT变换来实现二维DCT变换。

　　在该定义被提出以后，很多优秀的算法也被提了出来。如Chen,Lee的快速DCT算法等，Loeffler 在1989年提出的实用快速DCT算法共使用11次乘法和29次加法，该算法比起Chen的算法快而且不会发生Lee算法中的上溢问题，并且该算法被证明已经达到了算法极限，是最优秀的算法[4]。该算法如图1，它把整个DCT过程分成了四级，第一级只有8次加法，第二级分为上下两块，上面是偶块，下面是奇块，偶块有4次加法，奇块有6次乘法和6次加法，第三级上面有5次加法3次乘法，下面有4次加法，第四级仅奇块有2次乘法和2次加法。由图1可见，奇数部分的第四级与第二级的计算构成了连续的乘法，这种运算实现的时间将增加实际的计算时间。故Loeffler 提出了无乘法串行的并行计算方法，该方法使用了12次乘法和32次加法，这在具有并行的MAC处理器的运算中，并不增加实际的计算时间[1]。本文即采用这种DCT算法实现图像的压缩与处理。

　　3　DSP及其视频指令

　　我们使用ADI的ADSP－BF533EZLITE评估板作为实验平台，该评估板使用最大内部时钟600M的BF533处理器。处理器内核包括二个40位的ALU,2个MAC,4个视频ALU 及一个桶形移位寄存器。这种结构使并行的视频处理成为可能[5]。实验的软件环境是VisualDSP4.5，该环境集成了高性能C/C++编译器，并且具有比普通C/C++编译器更高效的代码优化功能。

　　为了进一步提高代码效率，减少程序运行时间和代码空间，根据DSP硬件结构及其指令的特点，对代码进行汇编优化。本文主要注重以下三方面的优化。

　　（1）利用高度并行的算术运算单元和功能强大的地址运算单元的相结合的特点，使用高密度指令代码进行代码优化。

　　Blackfin的高度并行结构能在计算的同时进行数据的存储，如R5=R1+R5,R4=R1-R5 ||R1=W[P0+0x4]（X）;该指令使用两个加法器同时计算出两个32位的值R1＋R5和R1－R5并把该结果分别存入到R5和R4中，此时占用的是算术运算单元的两条内部总线一个指令周期时间，由于外部总线空闲，可以把外部Cache中的数据送入到R1中。索引寻址和变址寻址相结合的模式使一个指令周期内对不同块的SDRAM访问成为了可能，比如上面的指令可以加一条R4=[I2++]仍能正确执行，而且不增加指令执行时间，地址运算单元DAG还包括两个用于嵌套零开销循环的循环计数器以及支持传输过程中饱和的限幅的硬件。这些特性使得Blackfin指令操作的效率很高。

　　（2）利用有利于DCT变换的操作数位寻址指令来优化

　　Blackfin DSP指令集不仅支持一个周期最多3条指令的并发执行，而且具有大量的像素操作和向量操作指令可以减少算法时间复杂度。位反转指令对FFT、DCT、DFT等数学变换的操作数寻址提供了方便，在变换之前它把输入数组数据通过位变换的方式变换到易于处理的排列方式，减少了操作数寻址的时间。

　　（3）利用IEEE 1180 舍入指令来支持DCT变换

　　Blackfin的加法指令支持预比例加减法，这种指令执行的时间首先通过算术移位将两个操作数变大或者变小后再相加减，这在DCT变换中为了保证运算精度，一般会移位后相加减，这条指令大大加快了DCT变换的速度。