基于FPGA的64点FFT处理器设计

0 引 言
DFT作为DSP领域中时域和频域转换的基本运算，存在运算量太大的缺点，导致其应用受到局限。 DFT快速算法FFT的提出，简化了DFT的运算过程，使其在实时信号处理领域中得到广泛应用。FFT实现的方法包括软件实现和硬件实现两种。采用软件实现FFT的方法存在计算慢，实现过程复杂等缺点，所以目前比较流行的方式是采用硬件实现FFT。硬件实现的具体方法可以分为ASIC方法、FPGA方法、 DSP方法和通用处理机方法等。
FPGA是20世纪80年代中期出现的一种新的电子设计自动化技术，具有集成度高，逻辑实现能力强，设计灵活等优势。在FPGA上实现数字信号处理，即用纯数字逻辑进行DSP模块设计，为高速数字信号处理算法提供了实现途径。在此，采用FPGA方法设计64点FFT处理器。
现有的FFT模块可以对多点数据进行运算，但是存在运算周期长。结构复杂，硬件资源耗费大等缺陷。采用64点FFT可以通过优化结构来快速处理多点数数据。目前设计的64点FFT处理器主要采用以专用处理单元取代常规FFT处理单元的方法，或者按照固定几何结构设计FFT处理器的方法。这里所介绍的64 点FFT处理器是在固定几何结构设计方法的基础上加以改进，将输入的64点数据均匀分成8组，并行输入给FFT运算单元，进行FFT运算。通过对蝶形运算单元进行优化设计，所设计的64点FFT处理器模块较之以往的FFT模块，节省了硬件资源，提高了运算效率。通过ModelSim仿真实验证明，在外部工作时钟频率为40 MHz下，对随机生成的序列进行64点FFT运算处理，运算时间为10μs，缩短了现有FFT模块的运算时间。

1 按频率抽取的基――4FFT算法原理
对于序列长度为N(N为2的整数次幂)的FFT算法主要有基-2 FFT和基-4 FFT两种。计算一次基-2FFT需要二次复乘和两次复加；计算一次基-4 FFT需要三次复乘和八次复加。从运算次数上看，基-2 FFT较为简单，但是因为基-2 FFT的复数运算较为复杂，所以在硬件实现上反而要比基-4 FFT占用的资源更多。为了满足对数据高速处理的要求，在此选择在FP-GA上实现基-4 FFT的算法。
根据定义，对于长度为N的序列x(N)(0≤N≤N-1)，它的DFT可表示为：

式中：WnkN=e-J2π/Nnk称为旋转因子。直接计算DFT，需要的计算量为N2次复乘和N(N-1)次复加。当N很大时，运算量相当大，无法满足实时处理的要求。因此利用旋转因子的对称性、周期性和可约性，把长序列分解成为短序列来进行快速傅里叶变换。
由式(1)可以得到4个子序列：

利用旋转因子WnkN的特性，如：将A，B，C，D作为复数操作数进行运算，由式(2)可得简化计算式：

式(3)就是在FPGA上实现基-4 FFT算法的基本运算法则。