摘 要：为适应FFT在实时的信号处理上的要求，从DIF的基本原理出发，分析讨论了FFT在可编程逻辑阵列器件上实验实时变换的问题，设计并实现了应用流水线和具有高吞吐量的片上系统。

 关键字：FFT; 傅里叶变换；FPGA

1 引言

DFT的计算在数字信号处理中非常有用，信号的频谱分析对通信、图像传输、雷达、声纳等都是很重要的。此外，在系统分析、设计和实现中都会用到DFT的计算。但是，在相当长的时间里，由于DFT的计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的应用。直到1965年Cooley 和Tukey在《计算数学》（Mathematicsof Computation）杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，提出了DFT的一种快速算法，使DFT的计算大大简化，运算时间大大缩短，从而使DFT的运算在实际中真正得到了广泛的应用。本系统实现了流水线形式的基于Cooley-Tukey基4按频率抽取算法的实时16点快速傅里叶变换。

2 功能描述

本系统所用FPGA芯片为Xilinx SpartanII XC2S200。Spartan-II系列2.5v现场可编程门阵列器件具有丰富的逻辑门，输入输出借口，和其他FPGA器件相比具有更高的性价比。它的特色包括片内block-RAM，四个延时锁相环（DLL），以及大容量的逻辑门。XC2S200内含20万的逻辑门单位，块RAM总数达到56k，足以满足本系统的设计。

 结合该高性能的FPGA芯片，本系统的设计特点是：

高性能16点复数FFT，16位复数数据输入与输出
二进制补码算术逻辑内核，精度达到16bit
并行流水线结构提供了在每个时钟输出一个处理完的数据
自然序列输入，自然序列输出

3 算法原理

1. 离散傅里叶变换（DFT）的演化

 2.  快速算法数学模型

本内核采用Cooley-Tukey基4按频率抽取快速傅里叶变换算法, 算法原理图如下

 3.  效率以及误差考虑

 FFT是离散快速傅里叶变换的一种实现方案.因此当N很大时，完成FFT的运算量比DFT减少了很多。但是，采用FFT要满足两个条件，所以在某些情况下，FFT并没有DFT效率高。两个条件是：
1) FFT必须同时计算N个频率值,而DFT可以值计算感兴趣的的几个频率值。

2) FFT只能进行复数运算，因此，如果只有实数时，FFT得到的一半运算结果都没有用。虽然可以容易地删除这些无用的计算结果，但需要花费时间计算出它们，还需要花费时间删除。

 在运行过程中将有连续的信号阵列通过碟形运算单元,每次每个运算单元取得四个复数经过处理得到四个复数处在相同的地址里但是在不同的内存里。每次处理完的存回到内存的数据将比16位长得多，因此在进行复数乘法的时候对相关位采取了舍去的措施。
本设计使最后的结果为实际结果的十六分之一。

4 设计的模型与框架

5 算法说明
         
1．倒序数据处理结构
根据快速算法的原型,设计该框架,实部与虚部分别以流水线方式同步输入到Address Generator RAM1,根据碟形运算的倒序规则将自然序列存入相应的地址里,然后在按自然序列方式取数进行第一级4点FFT运算, 结果存入Address Generator RAM2 与AddressGeneratorRAM1相对应的地址里, 然后根据第二级4点FFT的倒序规则取数运算, 存入 AddressGenertorRAM3, 其中AddressGenertorRAM3只作为流水线缓冲器，没有进行地址变换。经过上述地址变换原理真正实现了自然序列输入, 自然序列输出。Address Generator RAM的结构如下图：

 倒序基本算法如下:

基4的数字逆序为:

根据此逆序方式可以将自然序列地址(由计数器产生)通过组合逻辑成为逆序,因此自然序列的数据将存在逆序的地址中,例如x(8) 存在地址0001中,在读取数据时是按自然顺序读取的,这样就完成了倒序的流水线变换。本核地址变换如图4。
 
2. 旋转因子发生器

 根据旋转因子 WN = cos(2π/N) –j sin(2π/N) , 本内核使用ROM 将算法数学模型中的旋转因子按处理的地址顺序分别将 sin,cos,triv 的值以2进制补码的形式存在三个ROM里,其中triv是复数部分的符号存储器。它们在内核工作时，会直接与处理单元同步，精度为16bit。
如下图旋转因子表：（量化等级216 ＝ 32768）

3．16位复数乘法器
 在FPGA或者其他数字电路中实现高性能，高精度以及低耗逻辑单元的乘法器是非常困难的。该16位复数乘法器是复数旋转因子乘法

     R + j I = (X+jY)(C+jS)

是可以简化的，C 和 S 是预先知道的，并储存在一个LUT表中，而且还可以储存3个系数：

C， C+S ，C-S

有了这3个预先计算的因子，首先计算：

     E＝ X－Y 和 Z = C*E= C*(X –Y)

然后用：

     R = (C-S)*Y +Z
     I = (C+S)*X – Z

这种算法使用了3次乘法、1次加法和2次减法，但其额外的代价是第三个LUT，大大节省了LCB使用。为了配合系统的流水线结构，该乘法器设计结构如下：

4．4点FFT计算单元
 4 points FFT 是16点FFT计算的基本单元，数学结构如下：

该模块在硬件电路中是以加法器以及减法器配置的，并通过数据选择器进行结构化的处理。

6  工作时序

    为使FFT核开始工作， start 信号需要一个时钟周期（只能一个CLK）高电平，内核即开工作，本设计为流水线结构，一旦开始数据将在每个时钟被接收，等到流水线满后，每帧（16点）数据处理输出延时只需16个时钟周期。但第一帧数据需要处理76个时钟周期。

7  性能分析

处在流水线中该内核需要花费时间：

Clock Frequency 52 MHz 58 MHz 60MHz 74MHz
FFT ExecutionTime 307.7ns 275.9ns 266.7ns 216.2ns
 因此它在不同CLK下的性能为：

1．本设计用XC2S200-5测试,性能为
Speed Grade: -5
    Minimum period: 23.580ns (Maximum Frequency: 42.409MHz)
   Minimum input arrival time before clock: 22.516ns
    Maximum output required time after clock: 12.452ns
 
2．所耗片内资源
Device utilization summary:
Selected Device : 2s200pq208-5
Number of Slices:                     1821  out of   2352    77% 
  Number of Slice Flip Flops:              2604  out of   4704    55% 
  Number of 4 input LUTs:              2726  out of   4704    57% 
  Number of bonded IOBs:     68    out of    144    47% 
  Number of GCLKs:                     1    out of      4    25% 

参考文献：

[1] Uwe Meyer-Baese, “Digital Signal Processing With Field Programmable Gate Arrays”
 tup.tsinghua.edu.cn
[2] High-Performance 16-Point FFT VHDL Behavioral Model,  Dr Chris Dick
chrisd@xilinx.com , 2100 Logic DriveSan JoseCA 95124
[3] W. R. Knight and R. Kaiser, ``A Simple Fixed-Point Error Bound for the Fast Fourier
Transform’’, IEEE Trans. Acoustics, Speech and Signal Proc., Vol. 27, No. 6, pp. 615-620, Dec.1979.
[4] L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing,
Prentice-HallInc., Englewood Cliffs, New Jersey, 1975.