基于FPGA的FFT算法的实现

基于FPGA的FFT算法的实现

武志勇林永君

华北电力大学控制与计算机工程学院河北保定071003

摘要：信号处理在电力系统工作中应用广泛，其中快速傅里叶变换（FFT）在信号处理中是一种采用较多的方式。现提出一种基于FPGA的快速傅里叶变化算法的实现方式，同时给出基于Modelsim的仿真结果与Matlab的计算结果进行对比。

关键词：FFT；FPGA；信号处理

0引言

FFT是DFT的一种快速计算方式，能够将DFT运算的计算效率提高1~2个数量级[1]。传统的快速傅里叶变化多采用单片机或者DSP进行实现，而单片机都采用循环的串行计算，当碰到高频信号需要较高的采样频率时，其计算结果的实时性无法得到保证。FPGA（现场可编程门阵列）其并行运算的特性，能够进一步提高FFT计算的速度，拥有较高的实时性。本文提出了一种基于FPGA的256点的FFT算法的实现。

1FFT算法的原理

对于一个N点有限长度的序列的，其DFT计算方式为：

完成一次N点序列的DFT计算需要N2次复数乘法即N(N-1)次复数加法[2]，最终需要经历4N2次实数乘法，2N(2N-1)次实数加法才能得到其计算结果，其计算量十分庞大。考虑到旋转因子的对称性和周期性，有：

若N=2M,M为整数，则可将N点序列按照N的奇偶性分为N/2长度的两个序列：

根据旋转因子的特性，将上式改写为：

如图1-1所示的蝶形运算形式：

图1-1

2256点基2DIT的FPGA实现

2.1FFT运算模块的结构

FFT的设计采用并行迭代的结构，计算完上一级的蝶形运算后将计算结储存在RAM中，作为下一级蝶形运算的输入，继续调用蝶形运算模块，最总完成FFT的计算。

对于256点FFT需要进行8级蝶形运算，每级需要进行128次蝶形运算。这里采用32位的定点数运算，在节约逻辑门资源的同时也保证了计算的精度。FFT模块分为数据储存模块，蝶形运算模块，时钟模块，旋转因子储存模块，其整体结构如图2-1所示：

图2-1

蝶形运算模块的结构图如2-2：

图2-2

2.2FFT模块的工作过程

1)当复位信rst_n（低电平有效）为高电平，发出一个启动信号FFT_START后，FFT模块开始工作，将输入的数据转存到RAM中去。

2)并行调用128个蝶形运算模块，并将输入数据进行地址取反并输出到每个蝶形运算模块，同时将当前计算所需的旋转因子通过ROM读取到蝶形运算模块进行第一层蝶形运算，然后将结果保存到RAM中作为下一层蝶形运算的输入。

3)重复的将上一级蝶形运算的结果迭代到下一级蝶形运算模块中[3]，当完成所有计算后将结果输出，并发出一个结束信号FFT_STOP，此时FFT模块停止工作，并等待下一个FFT_START信号的产生。

3Modelsim和Matlab联合仿真

对于给定的信号x(t)=2cos(2π*50t)+0.5*cos(2π*100t)+0.25*cos(2π*150t)+0.05*cos(2π*200*t)+0.05*cos(2π*250*t);然后分别在Matlab和Modelsim中进行FFT的计算对该信号进行频谱分析。

可知该信号周期为0.02s，在一个周期内进行256点采样，其曲线图如3-1：

图3-1

用Matlab对该曲线的采样值进行FFT计算，可得到其频谱图如3-2：

图3-2

表3-1Matlab与FPGA结算结果对照表

表3-1为Matlab的FFT计算结果与FPGA的FFT计算结果的部分对照表，由表的结果可看出该信号频谱如表3-2：

表3-2

可看出计算出来的频谱和原函数频谱信息基本一致。Xr_M和Xi_M分别代表Matlb的计算结果，Xr_F和Xi_F分别代表FPGA的计算结果。可看出两种方式得出的计算结果基本完全一样。而Matlab的计算时间大概在0.28秒左右，而FPGA的计算时间在77us左右，其计算速度比Matlab高了3个数量级左右，完全满足实时性的要求。

4结论

本文给出了一种基于FPGA的快速傅里叶变换算法的实现，充分的利用了FPGA并行运算的特点，仅需77us就能实现32位数的256点FFT运算，虽采用并行运算占用了较大的逻辑门器件资源，但计算的精度和实时性得到了很大的保证，本文给出的这种FFT的实现方法在实际的信号处理中具有良好的应用前景。

参考文献

[1]王昊.基于GPU的傅里叶变换光谱复原方法研究[D].南京理工大学,2017.

[2]张晓宇,龚玉萍,朱光喜.相关跳频系统中一种高效FFT变换算法[J].舰船电子工程,2005(04):124-126.

[3]张玲佳.高维度FFT加速器设计及硬件实现[D].合肥工业大学,2017.