2D-DCT的FPGA实现

郭前岗，潘 磊，周西峰

（南京邮电大学 自动化学院，江苏 南京 210046）

在信息社会迅猛发展的21世纪，多媒体信息日益增多，其中人类主要依靠图像来接收各种各样的信息。图像中包含如此巨大的数据量，如果不经过压缩，不仅超出了计算机的存储和计算能力，而且无法完成信息的实时传输。图像的高速传输和所需巨大的存储容量已成为数字图像通信的最大障碍。离散余弦变换（DCT）由于其变换特点被认为是性能最接近K—L变换的准最佳变换，现在已经是最流行的图像压缩变换技术，并已经在 JPEG、MPEG-1/2/4、H.26x等国际编码标准中获得了广泛的应用[1]。

由于集成电子技术的高速发展和广泛运用，数字图像处理也由软件向硬件过渡并得到了非常迅速的发展。FPGA作为当今运用极为广泛的可编程逻辑器件，也是数字图像处理的理想器件。目前，利用FPGA进行图像处理主要是直接在FPGA上利用硬件描述语言或EDA软件进行设计，这种设计方法的最大优点就是速度快，可以利用流水线实现，具有一定的灵活性。

基于行列分解的2D-DCT由于算法规律性强、实现结构直观、时序控制简单而被广泛应用。本文提出使用行列分解法和分布式算法来实现2D-DCT，可以减少硬件资源，提高运算速度，具有一定的现实意义。

1 2D-DCT系统模块设计

离散余弦变换经常使用在信号处理和图像处理中，用于对信号和图像进行有损数据压缩。这是由于离散余弦变换具有很强的“能量集中”特性，使图像的主要信息集中在变换后的低频上，并且能够去掉像素间较强的相关性，让图像的信息集中在少数几个系数上，以减少冗余达到对图像进行压缩的目的。

1.1 2D-DCT定义

设 f（x，y）（x=0，1，…，N-1；y=0，1，…，M-1）为 N×M的二维信号序列，则其二维离散余弦变换定义为：

其中，u=0，1，…，L，…，N-1是水平方向的频率，v=0，1，…，L，…，M-1，是垂直方向的频率，F（u，v）是频域的系数值，f（x，y）是空间域的系数值，C（u）=由于二维离散余弦变换具有行列分解性[2]，即把2D-DCT

分解为 2个 1D-DCT来求解，因此欲求 F（u，v），可以先对 f（x，y）每一行数据作一维离散余弦变换得到 F（x，

y），然后再对每一列数据进行一维离散余弦变换便可得到 F（u，v），整个计算流程如图 1所示。 因此式（1）可改写成：

图1 2D-DCT的计算流程

式（2）方括号中的部分就是1D-DCT的计算公式。由于DCT在M=N=8时变换的平均性能最好，因此本文采用8×8的数据块作为变换对象。

1.2 系统模块设计

根据2D-DCT的行列分解性及2D-DCT的计算流程所设计的系统框图如图2所示，整个系统由控制模块、1D-DCT模块和行列转换模块3个模块组成。

图2 2D-DCT系统模块设计框图

在每个时钟的上升沿从数据输入端输入一个数据，8个时钟周期后，输入的就是8×8数据块的一行数据。同时，控制模块给1D-DCT模块一个信号，通知它对这8个数据进行1D-DCT变换，并且在计算完之后把结果存进行列转换模块中。如此反复8次后，就对8×8数据块完成了行变换，所得到的64个数据依然是以8×8的矩阵形式存放在行列转换模块中。之后控制模块分8次从行列转换模块中读出8×8矩阵的每一列数据，再送入1D-DCT模块中进行变换，变换后的数据就是8×8数据块的2D-DCT变换结果。

2 模块功能介绍

2.1 控制模块

控制模块用于保持整个模块设计的时钟同步，并且使用控制信号来控制1D-DCT模块状态之间的转换。1D-DCT模块有空闲状态和1D-DCT变换状态2个状态。当控制信号控制整个系统复位时，控制模块通知1D-DCT模块进入空闲状态；当需要计算的数据输入完成时，控制模块通知1D-DCT模块进入1D-DCT变换状态。1D-DCT模块的状态转移图如图3所示。

2.2 1D-DCT模块

设 X=[X（0），X（1），X（2），X（3），X（4），X（5），X（6），X（7）]为输入的一行信号序列，Y=[Y（0），Y（1），Y（2），Y（3），Y（4），Y（5），Y（6），Y（7）]为 1D-DCT 变换后输出的信号序列，根据1D-DCT的数学定义式[3]并且在经过合并同类项后得到：

图4 8输入1D-DCT结构

由于FPGA中硬件乘法器资源有限，直接应用乘法会消耗大量的资源。本方案中使用分布式算法[4]来实现乘法，它是一种适合FPGA的乘加运算，与传统算法实现乘加运算的区别在于，执行部分积运算的先后顺序不一样。分布式算法在实现乘加功能时，首先将各输入数据的每一对应位产生的部分积预先进行相加，形成相应的部分积，然后再对各个部分积累加形成最终结果；而传统算法是所有乘积已经产生之后再相加完成乘加运算的。与传统算法相比，分布式算法可极大地减少硬件电路的规模，提高电路的执行速度。分布式乘法器结构如图5所示。

图5 分布式乘法器

其中Cn为常系数。这种乘法器不仅能够有效地减少硬件资源，而且在增加输出端口时能够减小数据传输所带来的延迟和布局布线面积[5]。

2.3 行列转换模块

本文使用同步动态随机存储器（SDRAM）来存储第一次1D-DCT的中间结果及数据的行列转换。由于SDRAM与系统时钟同步，因此避免了不必要的等待周期，减少了数据存储时间。SDRAM的核心结构由多个内存单元组成，这些内存单元又分成由行和列组成的二维阵列。2D-DCT变换首先是对8×8数据块的每一行数据进行1D-DCT变换，然后将结果放入SDRAM中，每一行的结果就占SDRAM中的一行内存。SDRAM通过采用地址线行列复用技术读取其储存的内容，访问这些内存时，在地址线上依次给出行地址和列地址[6]，读出SDRAM中的每一列数据，再重新送入1D-DCT模块中进行1DDCT变换，这样就完成了整个2D-DCT的变换。

3 仿真结果

整个设计采用Verilog HDL语言进行编程，使用Xilinx公司的 Spartan3E系列 FPGA（XC3S500E）实现，时钟晶振为50 MHz，SDRAM容量为512 MB，位宽为16 bit，同步时钟能达到100 MHz。使用的编程软件是ISE，仿真软件是ModelSim。

图6是用ModelSim仿真软件仿真出来的2D-DCT的仿真结果及执行结果。其中，din是8 bit数据输入端口，dout是经变换后12 bit数据输出端口。由执行结果可以看出，从输入端口输入的64个数据在经过2D-DCT变换后，所得到的结果与期望值一致。

图6 2D-DCT仿真结果及执行结果

本文提出了分布式算法和行列分解法相结合的方案来实现2D-DCT，该方案不仅能够减少硬件资源的使用，提高资源的利用率，并能提高运算速度，能够满足数字图像和视频压缩的实时性要求。在查找表中所使用的值取的精度不够高，所以存在一定的误差，但这种误差不会引起人眼视觉上的差别，是允许存在的。因此，该方案可作为用FPGA来进行数字图像和视频压缩中的一部分。

[1]王相海，宋传鸣.图像及视频可分级编码[M].北京：科学出版社，2009.

[2]王新年，张涛.数字图像压缩技术实用教程[M].北京：机械工业出版社，2009.

[3]KASSEM A，HAMAD M，HAIDAMOUS E.Image compression on FPGA using DCT[C].IEEE International Conference on the Engineering Applications， 2009（7）：320-323.

[4]FAKHR W，EL-BANNA H.An efficient implementation of the1D DCT using FPGA technology[C].11th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems， 2004（7）： 356-360.

[5]PRASOON A K， RAJAN K.4×4 2-D DCT for H.264/AVC[C].International Conference on Advances in Computing，Communication and Control， 2009（5）：573-576.

[6]NAVINER L，DANGER J L.Efficient implementation for high accuracy DCT processor based on FPGA [C].42nd Midwest Symposium on Circuits and System， 1999，8（1）：508-511.