基于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算法的基本运算法则。
    不同于以往的基-4 FFT算法，这里是将输入的64点数据以8位输入数据为一组，共分成8组的方式输入给FFT运算单元进行FFT运算的。完整的FFT蝶形运算共分6级，经历196个循环状态。将来自存储单元的数据输入到FFT运算单元中，前三级是按8位1组的方法，分为8组进行运算；后三级是将前三级运算所得到的中间数据送入运算单元进行运算。经过FFT运算后，将所得到运算结果写入存储单元中保存。结果以倒位序方式输出，需要经过调整位序变换成为自然顺序输出。

2 FFT运算器设计
2．1 系统的整体结构
    一个完整的FFT运算单元应该包括以下几个组成部分：
    全局控制单元包括控制器和地址产生单元，用于调控整个FFT运算系统，生成蝶形运算单元以及其他子单元所需的地址，控制各子单元时序，保证其正常有序地工作；
    蝶形运算器单元 由蝶形运算器和旋转因子存储单元(ROM)组成，负责将送入的输人数据进行蝶形运算，是FFT运算器的核心单元；
    存储寄存器单元 采用两个RAM乒乓通信，通过通信接口单元接收总线控制信号，负责存储输入数据、中间数据和运算所得最终结果。
    系统整体框图如图1所示。

3 实验结果验证
    这里的FFT运算器通过硬件描述语言VHDL代码进行编写，在ModelSimSE PLUS 6．1f环境下完成系统仿真，波形仿真如图3所示。
    由波形仿真图可以看出，地址控制单元以3位二进制编码定义各子单元的地址，存储的数据在时序信号和地址总线单元控制下进行FFT运算。实验证明，当外部时钟频率为40 MHz时，可以对随机生成的64点序列进行FFT定点运算，运算时间为10μs。

4 结 语
    这里的FFT运算器采用定点数处理，当处理浮点数时，系统存在处理异常、数据溢出等问题。但是由于可以迅速处理多点数信号，因此在数字图像处理、实时通信系统的调试和解调等方面具有一定的实际意义，达到了使用FPGA实现DSP算法的目的。
    本文在以下方面有所创新：
    (1)输入的64位数据以8位共8组的方式并行输入，将FFT运算流程分为6级，整个FFT运算过程清晰，结构合理，提高了运行效率。
    (2)使用2块双口RAM作为存储器，采用“乒乓操作”，在一个时钟周期内保证数据传递的单向性，减少了数据传输的冗余，提高了精度。
    (3)将整个FFT运算器进行模块化设计，在控制模块的调配下，各个子模块准确工作，保证了运算的可靠性。