改进的一维DCT方案设计与实现

1.引言

Ahmed，Natarajan 和Rao在1974年首先提出了DCT算法[1]。从那时开始，它成为了图像和视频编码最流行的算法，并被广泛应用，这主要有两个原因：首先，它把图像数据转变成容易压缩的形式；第二，它能有效地用软件和硬件实现[2]。至今，基于行列变换的DCT被应用最广泛，因些，有必要对一维DCT的硬件设计的改进并使其硬件资源达到最简。

分布式算法自提出20年来一直被广泛应用于VLSI与DSP中[3-8]。在它的运用过程中，大多数的运算量集成在加法器或乘法。因此，减少加法器或乘法器成了一大批学者们研究对象。

经研究发现，目前所用的分布式算法大都是基于组合电路设计的，即三级加法在同一个时钟周期完成，由于电路的最小时钟周期取决于电路中所需处理时间最多的模块，因此，基于组合电路的时钟处理频率必大大受影响，故，我们考虑用时序电路来完成基于分布式算法的一维DCT，并且，为了加快处理速度，我们对一维DCT的变换数据进行了分析，发现如果改变对DCT各数据的处理顺序，更是可大大加快一维DCT的处理速度。

下面是我们对基于分布式算法的一维DCT的研究:

2.分布式算法的相关知识 [3]

首先,考虑下式

（2-1）

这里， 是常数， 是输入的数据，写成矩阵形式为：

（2-2）

如果 是一个N比特的二进制数，则 可表示为：

（2-3）

其中 or 1而 i = 0 ,1 , … , N-1； 表示 的最高比特位(符号位)， 表示它的最低比特位。于是：

（2-4）

这里INV(.)表示求补。
于是，在一维DCT变换公式式

（2-5）

中我们令

（2-6）

则：

（2-8）

当u=1时

如果运算精度取为13比特，则用二进制表示为：

（2-9）

（2-10）

从上述分析很容易发现一维DCT可以完全用加法器来实现。

3.一维DCT的算式分析

首先，让我们看看一维DCT各项算术式子：

第一个一维DCT变换系数的各项：

第二个一维DCT变换系数的各项：

第四个一维DCT变换系数的各项：

第三个一维DCT变换系数的各项：

第五个一维DCT变换系数的各项：

第六个一维DCT变换系数的各项：

第七个一维DCT变换系数的各项：

现在，我们来分析一下，这些项中的共用项。首先，我们按如下式子所示，把上面的式子所用到的项提取出来：

现在，我们来分析一下各二级加法器的结果都被哪些DCT变换系数所用：

接下来，我们再分析一下第三级加法器都做了什么运算及各对应的DCT变换系数。

　　如此，我们就很容易发现，其实，我们并不需要每计算一个一维DCT变换系数都要用组合电路把所有的各项都重复的计算出来，我们只要在计算的过程中加入一些寄存器，把我们已经计算出来的项存起来，等到用到的时候从里面取出来就直接可以用了，这样，只要我们通过合理的布局布线，我们的一维DCT变换系数就可以很快的计算出来，这样，功耗肯定也是会降低的。下面，我们设计了两种基于时序电路的一维DCT。事实证明，我们这样做，还可以大大减少加法器的数量。

4.DCT_13的设计

仅用13个加法器的一维DCT（为方便起见，我们暂且称之为DCT_13）设计：
在这个设计中，我们只用了13个加法器，就完成了一维DCT。我们的基本思路是这样的：首先，A0，A1，A2，A3，A4，A5，A6，A7依次顺序输入，经过一个8数据的串并转换模块，这8个数据同时输入到第一级加法器，我们的第一级加法器共有4个加减可控制的简单ALU，首先，我们当然是让这4个ALU做加法运算，因为，我们发现F0，F2并没有用到这一级加法器所计算出来的D_07,D_16,D_25,D_34,而它们的输出当然也是需要一个时钟周期的,于是,我们完全可以先让这4个ALU做加法运算，再在下一个周期让它们做减法运算，当然，每次计算完的结果要保存在寄存器，于是，第一级的加法运算是不会引起任何延时的。

让我们再来看第二级的加法器设计。通过对表2的研究，你发现什么了？是的，如同第一级加法器的设计一样，我们同样可以改变输出的顺序，来计算第二级加法器所需的各项。结合第一级加法器的设计，我们让DCT变换系数的输出变为这个顺序吧：F0，F2，F6，F4，F5，F7，F1，F3。于是，我们可以先用两个加减可控制的简单的ALU计算出F0所需要的D0716，D2534，同时，我们在设计中也让D07_34,D_2534也各用了一个加法器计算出来了D07_16，D25_34,当然也在接在来的一个时钟周期被前面所提到的ALU计算出来，接下来，我们再设计两个加法可控制的简单ALU来分别计算D_1625 ，D_1634 和D_0716 ，D_0725 ，D_0734，发现我们为什么这么做了吗？这是因为如此我们就

可以让ALU的一个输入固定下来，而不用再设计缓存器来缓存输入。当然，你也可以试试不把一个输入端固定下来会是什么样子。

第三级加法器的设计。首先，我们要输出的是F0，所以，我们用一个加减可控制的简单ALU计算出了D0716 +D2534，再在下一个时钟周期计算出 D0716 -D2534，同时，另一个加法器将D_0716+D_34，D_0716+D_25，D_16+D_2345依次计算出来，我们的输出顺序为：F0，F2，F6，F4，F5，F7，F1，F3。我们这种输出顺序是方便读者理解整个流程，其实，我们很容易发现第三个数据输出后，所有的项其实都已经被计算出来了，所以，我们后面的顺序是什么样的都是不重要的 (如果我们能曾加两个时钟的延时，也可以按顺序输出数据，即：F0，F1，F2，F3，F4，F5，F6，F7) 。

图1是我们的DCT_13的结构图。其中，series_to_parallel完成八数据串并转换，Addmat1完成第一级加法，Addmat2完成一维DCT变换的其余工作。

图1 DCT_13的结构图

　　图2是我们的一维DCT（13个加法器）的仿真时序图。可以发现，我们的8个数据输入完成同时就可以有一维DCT变换系数持续输出。可以看到我们的第一组输入数据A0—A7依次为：170，153，153，153，170，153，153，153，输出的一维DCT变换系数F0—F7为：440，6，0，11，11，-4，0，9与理论值：444，6，0，11，12，-2，0，9基本相符，出现的差异是由于加法器的位数的有限性造成的，但它是可以满足实际要求的。

图2 DCT_13的仿真时序图

图3是我们用Synplify综合工具综合后得到的一些数据，所选用的器件为APEX20KE160etc144-2x，可以看到在这个DCT_13中，我们仅用了1257个LUT。

图3 DCT_13的一些综合相关数据

5.DCT_11的设计

仅用11个加法器的一维DCT（为方便起见，我们暂且称之为DCT_11）设计。

在这个设计中，我们改变了前面提到的13个加法器的一维DCT设计的串并转换和第一级加法器。而第二级和第三级加法器与前面提到的是一样的。

在这里，我们让输入的顺序改变一下，为A0，A7，A1，A6，A2，A5，A3，A4。发现什么没有？是的，如此，我们可以让串并转换变为二数据的串并转换，这样对资源的节约是巨大的，让两个并行出来的数据输入到第一级加法器。在这里，我们的第一级加法器就可以只用两个加减可控制的简单ALU。其中一个计算出D07，D_07 ，D25，D_25，另一个则计算出D16，D_16，D34，D_34并且，我们当它们都被计算出来的时候，我们让它们同时保存到另一组寄存器，再做接下来的运算。

图4是我们的DCT_11的结构图。其中，SeriToPara完成二数据串并转换，Addmat1完成第一级加法，Addmat2完成一维DCT变换的其余工作。

图4 DCT_11的结构图

图5是我们用Synplify综合工具综合后得到的一些数据，所选用的器件为APEX20KE160etc144-2x，可以看到在这个DCT_13中，我们仅用了1151个LUT。

图5 DCT_11的一些综合相关数据

6.方案设计比较

　　下面，我们将我们的设计与目前已有的一维DCT设计进行了比较。通过比较可以看到我们的设计大大减少了一维DCT设计中所需要的加法器数。

7. 结语

　　我们举了两个例子，来说明基于时序电路的一维DCT。也许我们的设计还不是最简，我们也只希望能起到一个抛砖引玉的作用，让研究人员能够设计出更节约硬件资源的一维DCT。

参考文献

[1]N.Ahmed, T.Natrajan and K.R.Rao, “Discrete cosine transform”,IEEE trans. Computers, January 1974.
[2]欧阳合，韩军，“视频编解码器设计_开发图像与视频压缩系统”，国防科技大学出版社，2005.
[3] high performance distributed DCT architecture, " in Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Pittsburgh, Pennsylvania, April 2002.
[4] A.Peled, B.Liu, "A new hardware realization of digital filters," IEEE Trans. ASSP, vol.ASSP-22,no.6, pp.456-462, Dec.1974.
[5] D.F.Elliott (ed.), Handbook of Digital Signal Processing, Academic Press, pp.964-972, 1987.
[6] S.A.White, "Applications of distributed arithmetic to digital signal processing: A tutorial review," IEEE ASSP Magazine, pp.4-19, July 1989.
[7] G-K.Ma and F.J.Taylor, "Multiplier policies for digital signal processing," IEEE ASSP Magazine, pp.6-19, Jan.1990.
[8] Iain E. G. Richardson, "Video Codec Design _ Developing Image and Video Compression Systems " The Robert Gordon University Aberdeen. UK