基于分块转置的二维快速傅里叶变换的FPGA设计

离散二维快速傅里叶变换被广泛应用于数字图像处理，对工程领域具有重要意义。通常2D FFT使用行列分解计算，即先沿着行计算一维快速傅里叶变换，再沿列计算。由于现场可编程门阵列的数据传输带宽以及相关存储硬件的物理结构特性的限制，该方案不满足高分辨图像实时处理的需求。采用行FFT 转置 行FFT的方案，虽减少计算过程中直接内存访问控制器的等待时间且能提高2D FFT的计算效率，但目前矩阵转置实现有很大的局限性。传统的设计使用加载和存储指令来完成矩阵的换位。提出一种基于快速分块转置的2D FFT方案，通过搭建转置模块与四路并行1D FFT模块，充分利用FPGA片上资源以降低延时。实验基于Xilinx Kintex UltraScale FPGA，在相同的时钟频率以及并行条件下，对比不同的2D FFT计算方案。在实验误差范围内，本文提出的解决方案使计算效率提升约15倍。

FPGA-based design of two-dimensional fast Fourier transformation via block transposing

Two-dimensional discrete fast Fourier transformation is widely used in digital image processing, which is of great significance in engineering field. Usually, 2D FFT is computed using column decomposition, that is, a row wise 1D FFT followed by another column wise one. Due to the limitation of data transmission bandwidth of field programmable gate array and the physical structure characteristics of related storage hardware, this method cannot meet the requirement of real time processing of high resolution images. The scheme of row FFT transposed row FFT can reduce the waiting time of direct memory access controller in the computation process and improve the computational efficiency of 2D FFT, but the existing implementation of matrix transposition has significant limitations. Traditional design uses load and store instructions to complete the transposition of a matrix. This paper proposes a 2D FFT scheme based on fast block transposition. By building a transposition module and a four way parallel 1D FFT module, the FPGA on chip resources are fully utilized, thus the delay is reduced. The experiment is based on Xilinx Kintex UltraScale FPGA, and under the same clock frequency and parallel conditions, different 2D FFT calculation schemes are compared. Within the experimental error range, the solution proposed in this paper improves the computational efficiency by about 15 times.