离散傅里叶变换DFT在通讯、操控、信号处理、图画处理、生物信息学、核算物理、使用数学等范畴中有着广泛的使用。FFT算法是作为DFT快速算法提出的，它将长序列的DFT分解为短序列的DFT，大大减少了运算量。FFT的FPGA完结一起具有软件编程的灵活性和ASIC电路的快速性等长处，成为快速实时完结FFT的一种重要手法。文章意在规划一种高速率高吞吐率的FFT处理器，以满意实时处理要求。
1 数学模型
FFT的根本思想是使用旋转因子的周期性、对称性和可约性将一个长度为N的序列的DFT逐次分解为较短的DFT来核算，而总的运算次数比直接DFT运算要少得多，到达进步速度的意图。依据旋转因子的周期性、对称性和可约性，咱们能够得到如式(1)的一系列有用成果。
2 结构阐明
2.1 流水线结构
硬件结构完结FFT的常用方式有4种：递归结构，流水线结构，并行迭代结构和全并行结构。规划选用流水线结构，流水线结构一般在FFT完结的每一级均选用一个运算单元，前一级算成果直接用于下一级运算而无需比及本级运算悉数完结，因而，可进步运算速度。递归结构的运算的时刻较长，并行迭代结构对数据存取带宽要求很高，全并行结构资源耗费过大，均不适用。
2.2 并行处理
FFT作为时域和频域转化的根本运算，是数字频谱剖析的必要条件，超级的运算才能在雷达处理、观测、盯梢、守时定位处理、高速图画处理、保密无线通讯和数字通讯、滤波等的使用上极为激烈，而实时体系对FFT的运算速度要求更高。进步FFT速度的一种有用解决办法是并行运算，如选用多个蝶形运算单元并行处理。
综上，规划选取流水结构，4路并行处理结构。
3 硬件规划
3.1 逻辑规划
FFT逻辑结构如图1，为了结构高速率高吞吐量的FFT，规划4路并行输入输出，选用基4与基2混合FFT，FFT512选用基4蝶形算法，其他则选用基2蝶形算法。
流水结构的FFT处理器的根本结构如图2所示。实践规划由3个部分组成：运算单元、数据交流单元和重排单元。
运算单元完结蝶形运算，是处理器的中心，其运算速度直接决议整个FFT处理器的速度。由于4组输入数据一起进入蝶形运算，所以处理速度为串行的4倍。其间，每个蝶形单元均选用流水线技术规划。运算单元发动后，每个周期处理4组数据，完结4输入4输出的FFT。
数据交流单元是处理器的要害，完结对前一级蝶形运算单元输出数据的交流，以满意下一级蝶形运算的配对需求。完结办法为每一级的输入均选用次序输入，内部用FIFO缓存数据，依照逆序方式配对数据，等候数据到来，将加法成果输出，减法成果存至FIFO中，待加法成果输出结束，持续输出减法成果，如此输出成果即为次序输出。
数据重排单元担任对终究核算成果进行从头排序，以完结天然序数输出。512点基4结构图如图3所示，在512基4运算完结后，输出数据的次序并不是所需次序，需求进行调整，由输入数据与输入数据的地址特色发现，倒序RAM的读地址即完结次序输出。
3.2 时序规划
流水示意图如图4所示，具体阐明如下：
FFT64模块的5级流水：第1级，前64组输入数据的实部、虚部均存放在FIFO中，当第65组数据到来时，与FIFO中存放的榜首组数据做蝶形运算，将相减的成果持续存在FIFO中待用，相加运算将在第二级进行;第2级，前64个周期，做蝶形加法，成果记为add，第65个周期起，从FIFO中读数给add;第3级，前64个周期，add赋给榜首级缓存存放器，第65个周期起，把add赋给乘法器的输入端;第4级，前64个周期，把榜首级缓存存放器赋值给第二级缓存存放器，第65个周期起，做乘法运算;第5级，前64个周期，把第二级缓存存放器的值赋给输出端，第65个周期起，把乘法器输出累加的成果赋给输出端;
FFT512模块的6级流水：第1级，当输入有用信号拉高时，将榜首组输入数据放入榜首级缓存器中，存放第二至四组数据，待接乘法器输入端。一起，从rom中读取旋转因子;第2级，榜首路缓存至第二级缓存中，其他三路做乘法运算;第3级，榜首路缓存至第三级缓存中，其他三路做复数乘法的加法运算;第4级，四路数据均做缓存;第5级，做如图3中的榜首个蝶形运算。其间，乘以-j运算能够用倒置相加来完结，如此能够节约乘法器资源;第6级，做如图3中的第二个蝶形运算，一起将输出有用信号拉高。
FFT32、FFT16、FFT8、FFT4、FFT2、FFT1与FFT_64流水原理共同，仅仅操控位数不同，其分别为32、16、8、4、2、1。
4 验证规划
Testbench是一种验证手法，一般包括3个部分，鼓励生成、待测规划、输出校验。针对规划建立的testbench如图5所示，从文件中读取向量i_data_real、i_data_imag，通过FFT处理得到成果o_data_relal、o_data_imag，并依据end信号将向量写入相应文档中，与正确成果进行比对。
5 仿真成果
ISE仿真波形如图6所示，输出文件经与MATLAB比照验证正确。图(1)为全体仿真波形，输出有用信号拉高后，数据接连输出。图(2)为FFT 512模块部分仿真波形，输入有用信号拉高后，第6个周期输出有用，与剖析的流水级数相符合。
6 归纳成果
归纳后得到资源使用状况如表1，咱们发现，并行处理带来面积的增大，如安在实践问题中平衡速度与面积尤为重要。
7 结束语
文章用FPGA完结了512点FFT处理器，选用Verilog硬件描绘言语进行RTL级描绘，并完结归纳、布局布线。通过ISE仿真，成果与MATLAB仿真输出成果符合。处理器先选用时域基2蝶形算法，后选用时域基4蝶形算法，并行处理4个蝶形运算单元，并一起选用流水线结构，大幅度进步了处理器速度，可进行实时FFT运算。在规划顶用FIFO存储中心数据，并将旋转因子固定为乘法器IP的常数系数，以进一步进步处理器的速度。由于选用并行结构，所以FPGA硬件资源耗费较多，体系功耗也相应增大，怎么依据体系实践需求找到速度与资源的平衡至关重要。
