基于FPGA的二维FFT实现

论文总字数：30324字

摘 要

二维快速傅立叶变换（2D FFT）在信号和图像处理应用中起着重要作用。在本文中，我们提出了一个基于FPGA的8*8点二维快速傅里叶变换架构，在vivado环境下对二维矩阵进行快速傅立叶变换得到其频谱信息。

在Xilinx一维FFT IP核 v9.1的基础上,构建二维傅里叶变换的实现架构，利用该模块可以计算出二维数据的频谱值。将二维FFT分解为两步，首先对原始矩阵各行分别进行FFT,得到一维FFT后的复数矩阵，然后，再对得到的复数矩阵各列进行FFT得到二维傅里叶变换的频谱信息。编写Verilog程序，通过simulation观察整个处理流程的仿真波形，验证了对一维FFT单元正确地控制，继续实现了二维FFT变换。由于行变换和列变换中对各行各列计算是相对独立的，可以采用两个一维FFT模块并行处理行或列的傅里叶变换，提高整个模块的运算速度。

将所设计二维FFT模块应用到数字图像处理系统中，可为图像数据的处理和分析提供支持。

关键词：二维FFT，基二突变型，IP核，Verilog

Abstract

Two-dimensional fast Fourier transform (2D FFT) plays an important role in signal and image processing applications. In this paper, we propose an FPGA-based 8*8-point 2D fast Fourier transform architecture, which performs fast Fourier transform on the 2D matrix to obtain its spectral information in the vivado environment.

Based on the Xilinx one-dimensional FFT IP core v9.1, the implementation architecture of the two-dimensional Fourier transform is constructed, and the module is used to obtain the spectral values ​​of the two-dimensional data. The two-dimensional FFT is decomposed into two steps. First, the FFT is performed on each row of the original matrix to obtain a complex matrix after the one-dimensional FFT. Then, the spectrum of the two-dimensional Fourier transform is obtained by performing FFT on each column of the obtained complex matrix. The Verilog program was written, and the simulation waveform of the whole process flow was observed by simulation. The correct control of the one-dimensional FFT unit was verified, and the two-dimensional FFT transformation was continued. Since the row transformation and the column transformation are relatively independent for each row and column calculation, two one-dimensional FFT modules can be used to perform row or column Fourier transform in parallel to improve the operation speed of the entire module.

Embedding the designed module into the image processing system provides support for image data processing and analysis.

KEY WORDS: 2D FFT, Radix-2Burst,IP core,Verilog

目 录

摘要 ……………………………………………………………………………………………Ⅰ

Abstract …………………………………………………………………………………… Ⅱ

1. 绪论 ………………………………………………………………………1

1.1 引言 ………………………………………………………………1

1.2 基于FPGA的二维FFT研究背景及现状 ………………………………2

1.3 本文的研究目的和主要研究内容 ……………………………………4

1.5.1 研究目的 …………………………………………………4

1.5.2 主要研究内容 ………………………………………………4

1. 基于FPGA的二维FFT相关的理论分析……………………………………5

2.1 FPGA原理 ……………………………………………………………5

2.1.1 FPGA应用 …………………………………………………5

2.1.2 FPGA架构 …………………………………………………5

2.1.3 Verilog HDL简介 …………………………………………6

2.1.4 VLSI设计流程 …………………………………………6

2.1.5 HDLs的重要性 ……………………………………………7

2.1.6 FPGA数字设计方法 …………………………………………8

2.2 Vivado自带FFT v9.0 IP核介绍………………………………………8

2.2.1 Xilinx FFT IP核特点 ……………………………………8

2.2.2 Xilinx FFT IP核端口图 …………………………………10

2.3 快速傅里叶变换的常用算法 …………………………………………11

2.3.1 快速傅里叶变换原理 ………………………………………11

2.3.2 按时域抽取算法 ………………………………………………13

2.3.3 按频域抽取算法 ………………………………………………17

2.3.4 CORDIC算法 ………………………………………………19

2.3.5 Winograd算法 ……………………………………………20

2.4 二维FFT算法原理 ……………………………………………………21

2.5 验证二维FFT可由一维FFT架构 ……………………………………21

1. 研究结果 …………………………………………………………………24

3.1 研究方案 ………………………………………………………………24

3.1.1 二维FFT顶层模块的设计 ………………………………………24

3.1.2 计算单元的例化 …………………………………………25

3.1.3 二维FFT处理流程 ……………………………………………25

3.2 结果展示 ……………………………………………………………………27

3.2.1 简化后的FFT ip核有效性验证 …………………………………27

3.2.2 二维FFT仿真结果…………………………………………………30

1. 总结与展望 ……………………………………………………………33

4.1总结 …………………………………………………………………………33

4.2展望 …………………………………………………………………33

…………………

致谢 …………………………………………………………………………………34

参考文献（References） ……………………………………………………………35

1. 绪论
   1. 引言

二维快速傅里叶变换（FFT）在理论研究领域和工程应用方面都具有重要的价值。它是一种常用于图像处理领域的分析和计算工具。图像处理的基本步骤是恢复、压缩、重建、过滤和图像增强，傅立叶变换是必不可少的工具。离散傅里叶变换（DFT）仅限于数字图像，在数字信号处理中，FFT是最常见的操作之一。由于时钟频率和每个时钟的有用操作数量，普通的DSP实现不能满足高性能要求，因此不适合在极端苛刻的条件下处理需要高数据密集型的复杂任务，因此需要具有更高处理性能的功能模块完成对图像数据的二维离散傅里叶变换[1]。而且随着需要处理的数字信号的信号量的急速增加，能够快速处理大容量数据的二维离散傅里叶变换模块的需求越来越高。

• 1. 基于FPGA的二维FFT研究背景及现状

随着集成电路技术水平的不断提高，各种形式的处理器已经开发出来，从第一个通用处理器到广泛使用的可编程逻辑器件如FPGA和CPLD，还有图形处理器和数字信号处理器。半导体集成密度摩尔级的增长也显着提高了单芯片处理器的计算能力，并且存储器规模增加了一倍。作为半定制集成电路，FPGA可以有效地编写计 算和控制逻辑，以满足客户的个性化开发需求。通过调用制造商提供的IP内核[2]，我们可以使用我们使用的芯片快速构建所需的硬件架构，从而为系统开发提供便利的平台。因此，利用FPGA来实现对数字信号的二维快速傅里叶变换将显著提高计算速度，具有更高的应用价值，,在FPGA片内完成二维FFT和使用DSP或GPU相比较，使用FPGA可以减小功耗和所占面积，同时也能减少片间数据传输较高的延时，降低接口的使用。

一维快速傅里叶变换的研究相对较成熟，已经有许多算法可以实现，比如使用较广泛的库利-图基算法[3]，也就是我们常用的基2 按时间抽取算法和基2按频率抽取算法，当然，也可以有基4按时间抽取算法和基4按频率抽取算法、基n等等，n为2的整数次幂，但是n越高，算法越复杂。事实上，并不是n越大的算法效率越高，应用较多的为基2和基4算法。因为对一个序列进行快速傅里叶变换，我们一般需要该序列的长度为n的整数次幂，当n太大，比如n等于8，那么该FFT模块能处理的序列长度可以为8、64、512、4096……等，可见，对于序列长度为512到4096中间的点数，要是不够4096点，都得补0到4096点，甚至对于一个600点的序列也得补齐到4096点，然后进行快速傅里叶变换，这显然是效率很低的。还有CORDIC算法，一种高效的迭代方法，它使用旋转因子来计算各种基本函数。还有Winograd傅里叶变换算法，一种利用数据索引集上的乘法结构的算法，用于将傅立叶变换计算变换为循环卷积计算的算法。

剩余内容已隐藏，请支付后下载全文，论文总字数：30324字