基于Cyclone系列FPGA的1+024点FFT算法的实现

第33卷第2期电子工程师

2007年2月 ELECTRONICENGINEER

VoI.33No.2

Feb.2007

基于Cyclone系列FPGA的1024点FFT算法的实现

钱文明，刘新宁，张艳丽

（东南大学国家专用集成电路系统工程技术研究中心，江苏省南京市2l0096）

介绍了一种用低成本CycIone系列FPGA（现场可编程门阵列）实现基于按DIF（频率抽摘 要：

取）radix2结构l024点FFT（快速傅里叶变换）算法的方法。本设计采用VeriIog语言编程实现，利用EDA（电子设计自动化）工具对设计进行了仿真、综合，并在开发板上实现板级验证，最后分析了整个设计的性能，说明在低成本CycIone系列上可以实现高速FFT算法。

关键词：FFT；频率抽取；蝶形运算；FPGA中图分类号：TN402

0 引 言

随着数字技术的飞速发展，DSP（数字信号处理器）已广泛应用于通信、多媒体、医疗仪器和军事等领域。FFT（快速傅里叶变换）是DSP的核心技术之一和DFT（离散傅里叶变换）的快速算法，作为时域和频域转换的基本运算，是数字谱分析的必要前提，在雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域有广泛应用。而FPGA（现场可编程门阵列）内部含有大量逻辑单元和高速RAM模块，使FFT算法可以灵活快速地实现，并具有很高的性能。

本文主要研究l024点FFT的低成本FPGA实现方法，介绍了FFT算法的基本原理和实现结构，采用自顶向下的设计思路，描述了FFT硬件实现的结构以及各个模块的功能，并进行仿真、逻辑综合、时序分析和板级验证，将运算结果与理想值进行比较，分析系统功能和性能。采用的FPGA为AItera公司的CycIone系列EPlC60240c芯片，这是一款价格适中、功能强大的FPGA芯片。

图1 FFT实现结构

这种结构的优点是：在同一级运算中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又同在一条水平线上，这就意味着计算完一个蝶形运算后，所得输出数据可以立即存入原输入数据所占用的存储单元，即同址运算，因此在工程实现时可以节省存储单元。这种算法的缺点是：每级运算的几何结构是变化的，无法在程序中进行循环控制，所以不便于扩展。

1 FFT算法

本文采用的算法是将频域X（ ）按奇偶分开，故称DIF（频率抽取）基2FFT算法。

设序列（xn）的长度为N，且满足N=2M，M为整数。将N点DFT先分成2个N/2点DFT，再是4个N/4点DFT，进而8个N/8点DFT，直至N/2个2点DFT。每分一次，称为一级运算。因为M=Iog2N，所以N点DFT可分成M级。

FFT的实现结构如图l所示。图中有大量蝶形运算单元，它是FFT

算法的基本运算单位。

收稿日期：2006-07-3l；修回日期：2006-09-27。

2 FFT的硬件实现

整个设计主要包含存放数据的RAM、存放旋转因子的ROM、蝶形运算单元、地址产生单元以及使各个模块协调工作的控制单元5个模块。如图2所示。2.1 RAM数据存储单元

RAM是存储输入数据、中间运算结果以及最终运算结果的单元。每个蝶形运算的输入、输出数据均要经过RAM的读写操作，因此，RAM的频繁读写操作对FFT的处理速度影响较大。为了加快FFT的运算速度，需要构造双端口RAM来加快数据传输的吞吐量。EPlC60240c内置了20块4kbit的RAM，将RAM设置在FPGA内部不存在驱动和Pad延时，速度极快，而

12