二维DCT算法的高速芯片设计
摘要: 介绍了一种基于行列变换快速算法的高速DCT 处理芯片的设计，并详细阐述了实现这一算法的电路结构。为了提高芯片的处理速度，电路中采用了流水线结构和双RAM 转置存储技术，并给出FPGA 实现和Verilog 综合结果。综合结果显示，该芯片最高可以工作在140 MHz 的时钟频率上，非常适合于各种视频图像压缩方面的实时应用。
关键词: DCT ; FPGA ;芯片设计;视频压缩
目前大部分的视频编码标准都采用运动估计和运动补偿来降低图像序列的时间冗余度;采用正交变换来消除图像的空间相关性。离散余弦变换(DCT ，Discrete Cosine Transform) 是一种最主要的正交变换。它将图像信号从空间域变换到DCT 域，保持原始信号的熵和能量不变，却使得DCT 域系数之间的相关性减弱，然后再对DCT 域系数进行量化和编码，以达到压缩的目的。
然而，DCT 的算法复杂，如果直接进行计算，计算量很大。以8 ×8 的图像块为例，若采用直接计算，那么进行二维DCT(2D-DCT) 运算需要1 024 次乘法和896 次加法，难于满足实时处理的要求。考虑到DCT 的正交性和对称性，人们提出了许多快速的算法。在这些快速算法中，一类是利用快速傅里叶变换( FF T) 来计算DCT ，另一类是直接根据DCT 的规律寻求快速算法。在第2 类算法中，最常用的是采用行列快速算法，该算法首先逐行计算一维DCT ，再逐列计算一维DCT ，从而把乘法的计算量减少了一半，其算法规律性强，特别适合于DCT 算法芯片的研制。
二维DCT 算法
对于一个大小为N ×N 的像素块来说，假设x ( i ，j) 为输入的像素点阵数据，其二维DCT 变换公式如下:
上式也可以写成矩阵运算形式Z = CXCT (2)其中，C为带余弦基本函数的变换系数矩阵，CT 为C 的转置。从式(1) 和(2) 可以看出，二维DCT 变换是可分离的，它可以分解成串联的两次一维变换，即
写成矩阵形式为: Z = CY，Y = XCT
这里，Y为中间乘积矩阵(Y的列等于X 行的一维DCT 输出) 。因此，在做二维DCT 变换时，可以应用一维DCT 变换来计算，即先沿X 的行进行一维DCT 计算获得Y，再沿着Y的转置的行进行一维DCT运算。这样的算法结构如图1 所示。
一维DCT 的计算
对于一维DCT变换Y = CX ，其展开式如式(3) 所示:
观察发现，系数矩阵C 具有很特殊的对称性，式(3) 可进一步化简，如式(4) 所示。
由于系数矩阵全是浮点数，为了能用定点乘法器运算，将它们扩大216 倍后再取整，代入式(4) ，得
硬件电路设计
根据前述的2D-DCT 快速算法，可以设计出VLSI 实现的电路结构。
1) 第1 级1D-DCT
图2 是实现一维DCT 变换的电路结构，它主要由串行/ 并行转换电路、系数矩阵循环移位寄存器、加/ 减法器、乘法器及负号处理等电路组成。为了提高芯片的运算处理能力，电路中采用了流水线结构。 数据以串行的方式输入，每个时钟周期送入一个，在经过初始的15 个时钟延时后，每一个时钟将输出一个变换结果。下面，依据流水线的作业顺序，对数据的运算处理和电路结构作阐述。
对于一个8 ×8 图像块来说，共有64 个输入数据，它们以串行的方式输入到电路中来，每行数据(共8个) 为一组，分别为xk0～xk7。
当第1 组数据输入进来后，经过串/ 并转换器将串行输入的数据转变为并行输出，并在寄存器中保持8 个时钟，为后面的运算电路提供输入。
在移位寄存器保持数据的8 个时钟内，其后的加减运算器工作在交替变换的加/ 减运算状态(每个时钟变换一次) 。 这样，这4 个加减法器在8 个时钟内一直交替输出x00 + x07 、x01 + x06 、x02 + x05 、x03 +x04 和x00 - x07 、x01 - x06 、x02 - x05 、x03 - x04。
在将上述的两两相加减结果送入到乘法器之前，为了简化乘法器的设计，对两个相乘数进行取绝对值处理，并作了负号保存， 在乘法运算后再进行负号还原。
接下来再进行两级累加及去低16 位处理，去除低16 位是为了抵消前面对DCT 系数所做的216 倍放大。
至此，完成了一行数据的一维DCT 运算。 随着64个输入数据源源不断地送入，在第15～78 个时钟期间，所有64 个一维DCT 变换结果将一一输出。
2) 转置存储器
转置RAM 是对前面的一维DCT 结果做行列转置，即将逐行输入的8 ×8 个数据转换为逐列输出。 从第1 个数据输入到第1 个数据输出，中间需要64 个时钟间隔。
对一个64 个存储单元的RAM 来说，要先用64个时钟完成数据写操作，再用64 个时钟完成数据读操作。 考虑到时序的合理性和连贯性，即前后两级1D-DCT 都在连续工作，转置存储器必须能够同时接受第1 级1D-DCT 的数据输出并为第2 级1D-DCT 提供输入数据源。因此，在设计时采用了双RAM 结构，并让这两个RAM 工作在交替读/ 写模式，如图3 所示。
这样，在从一个RAM 读出数据并送入第2 级1D-DCT 的同时，可以往另一个RAM 写入第1 级1D-DCT 的转换结果。
3) 第2 级1DDCT
第2 级1D-DCT 逐列完成变换，和第1 级1D-DCT 采用相同的快速算法，因此这一部份的电路结构与第1 级1D-DCT 基本相同，不同之处仅在于所处理的数据长度不同(比第1 级1D-DCT 略长) ，因此，在电路实现上耗费的片内资源会略多些。从时序上来看，第80 个时钟开始接受数据输入，直至第143 个时钟;而输出数据则发生在第94 到第157 个时钟。
FPGA 实现与仿真结果
本次设计采用Verilog HDL 硬件描述语言对上述的算法结构在RTL (Register Transfer Level) 级上进行描述，所选用的芯片为Xilinx XC2V250-6 FPGA ，这块FPGA 芯片属于Virtex-II 系列，Virtex-II系列的FPGA 芯片内置有多个18 位×18 位乘法器以及一定容量的存储器，非常适合DCT 算法芯片的设计。
综合结果显示，芯片最高工作频率可达140MHz。对于4CIF 格式的视频输入信号，图像尺寸为704 ×576 ，假设帧频为30 帧/ 秒，每64 个输入信号间有一个时钟的间隔，那么对所设计芯片的最低时钟要求为:
可以看出，所设计的FPGA 芯片已经可以很好地满足实时视频处理的速度要求。表1 给出了片内各逻辑器件的用量统计，这些器件共使用了730 个Slice ，占可用设计资源的47 %。
图4 给出芯片的功能引脚示意图，XIN 为待转换的9 位数据输入端，CL K 为时钟信号输入端，RST 为复位端，DCT_2D 为12 位的DCT 转换结果，RDY 是转换结果就绪指示。其逻辑功能见图5 的时序仿真波形。
结 论
本文研究了基于FPGA 的二维DCT 算法的芯片设计，并给出了具体的实现电路。由于采用了高度并行的流水线结构和双RAM 转置技术，整个设计方案获得了很好的性能，该设计方案可与其它视频算法模块集成，共同构造出完整的视频图像处理芯片。