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

基于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

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

第33卷第2期钱文明，等：基于CycIone系列FPGA的1024点FFT算法的实现 微电子与基础产品

且控制简单，不需占用片外电路板面积，可提高系统的

总体速度和可靠性。

定关系：

addr_B=addr_A+

N/2

2i

第0级：addr_A随ctI信号从0递增至N/2-1，此时本级的地址已产生完全，之后再加1溢出变成0，成为下一级的首地址。

第1~M-1级：判断addr_A的第［M-i-1：0］位，若小于N/2

-1，则来一个ctI信号，addr_A就加1，i

图2

FFT模块划分

本设计外部输入数据为12bit有符号数，由于FPGA内部含大量RAM，所以FPGA内部将其扩充为32bit有符号数，这样进行10级蝶形运算后可确保不会产生溢出，减少了溢出检查处理模块。1024点FFT共需1kX32bit实部RAM、1kX32bit虚部RAM。2.2 ROM旋转因子存储单元

参照FFT结构，旋转因子要参与蝶形运算以得到第2个运算结果。旋转因子都是小于1的小数，所以设计中需将其定点化，定点化过程是将旋转因子扩大16384（214）倍，取整数部分定点化，存入内置ROM。蝶形运算后将运算结果右移14位后作为第2个运算结果存入RAM，作为下一级的输入数据。所需ROM的容量应为1024点FFT所需的全部旋转因子数，共512个16bit实部ROM，512个16bit虚部ROM。2.3 蝶形运算单元

蝶形单元是FFT的核心部分，

主要包括乘法器和加法器。每级蝶形运算的输入数据和运算结果存储在相同地址单元中。在蝶形运算单元中，首先将两个操作数相加减，加法结果为第1个运算结果；减法结果乘以旋转因子，再右移14位，得出第2个运算结果，同时将第1个操作数存入RAM，在下1个节拍时存入第2个运算结果，可实现部分PipeIine结构。2.4 地址产生单元

地址产生单元根据控制单元输出的ctI信号产生下一级蝶形运算所需的两个操作数和旋转因子的地址。观察RAM地址生成规律：序列（xn）的长度为N，M=Iog2N，则所需的级数和地址位宽都为M（0~M-1）

。第i级蝶形运算可分为2i组，每组有（N/2）/2i个蝶形运算。每个蝶形运算的两个操作数的地址都有一

2若等于

N/22i-1，则随ctI信号addr_A加上N/2

2i

+1。本文采取的FFT实现结构为原址运算，运算结果仍然写回原地址，因此需将读数据地址延迟若干时钟

周期，作为运算结果写入地址。

ROM地址生成规律：维护一个模为N/2的计数器，第i级的地址取计数器的第［M-2：i］位即可。2.5 控制单元

控制单元是整个系统的控制核心，各个功能模块之间的地址、数据传递均通过控制单元协调工作。控制单元记录当前蝶形运算所处的级数和个数，并产生ctI信号传递给地址产生单元，以产生操作数和旋转因子的地址，地址产生单元将旋转因子的地址送入ROM模块的地址总线，直接读出旋转因子的值，送入蝶形运算单元；将操作数的地址送入控制单元，控制单元将两

个操作数的地址连续送入RAM的地址总线，连续读取两个操作数，将其寄存后送入蝶形运算单元。运算结果在中央控制单元控制下连续写入RAM。FFT完

成后，产生done信号通知外部读取处理后的数据。

3 仿真与验证

本设计采用自顶向下的设计思路，完成系统模块划分和各个功能模块的VeriIog代码编写。选用Ouar-tus!作为软件开发平台，利用该软件宏模块的调用功能产生RAM、ROM、乘法器等模块，以节省设计时间，提高系统工作效率。得出整个系统占用30%FPGA的逻辑单元和90%片上RAM，CIock最快为75MHZ。系统在工作主频率75MHZ情况下通过板级验证，完成全部1024点复数FFT运算时间大约需要250"s。功能仿真结果如图3所示。从图中可以看到，第1个节拍输出第1个操作数的地址，并寄存上一个蝶形运算得到的第2个操作数，将其送入RAM输入数据总线上；第2个节拍得到第1个操作数，并输出第2个操作数的地址；第3个节拍得到第2个操作数，并计算出第1个结果；第4个节拍寄存第1个结果，送入RAM输入数据总线上。

本系统选用GE02开发板（处理器为东南大学研

13

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

微电子与基础产品 电子工程师2007年2月

发的基于ARM7的SEP3203芯片）为硬件平台，通过DMA方式传送l024个数据到FPGA的RAM模块，数据传输完成后开始FFT运算，处理器等到done信号后，通过CodeWarriorforARMDeveIoperSuite将存储器中的运算结果导出，在MATLAB中画出图形，图4为理想值与运算值的对比。也可在Memory区中观测具体数值，

判断由于截断和定点运算带来的误差。

于电子设计师可以采用相对廉价的大规模可编程集成

电路来设计灵活多变的专用芯片而不必受传统ASIC（专用集成电路）的固有设计模式制约。本设计全部

部分采用PipeIine并行结构，使用了由VeriIog实现，

FPGA内置的双端口RAM、ROM单元，加快了系统总体速度。全部电路已由功能仿真、综合、映射、布局布线和时序仿真验证，并成功下载到CycIone

最大误差不超过2%，EPlC60240c。验证结果良好，

在75MHz条件下，完成l024点FFT的运行时间为267!s，可实现实时处理。

仿真实验表明，随着可编程器件规模、速度的不断提高和成本的相对低廉，采用FPGA实现高速数字信号处理的算法具有可行性和优越性。

参 考 文 献

［l］胡广书.数字信号处理———理论、算法与实现［M］.2版.

图3

功能仿真结果

北京：清华大学出版社，2003.

［2］IFEACHOREC，JERVISBW.数字信号处理实践方法

［M］.2版.罗鹏飞，等译.北京：电子工业出版社，2004.［3］DINIZPSR.数字信号处理系统分析与设计［M］.门爱

东，等译.北京：电子工业出版社，2004.

［4］CHUChao，ZHANG0in，XIEYingke，etaI.Designofa

highperformanceFFTprocessorbasedonFPGA［C］//Pro-ceedingsofDesignAutomationConference，AsiaandSouthPacific：VoI2，Janl8-2l，Shanghai，China.2005：920-923.

［5］SUNGCH，LEEKB，JENCW.DesignandimpIementation

ofascaIabIefastFouriertransformcore［C］//Proceedingsof2002IEEEASIA-PacificConferenceonASIC，Aug6-8，2002，Taipei，China.Piscataway，NJ，USA：IEEE，2002：295-298.

钱文明（l982-），女，硕士研究生，主要研究方向为电路与系统。

图4 理想值与实际值的对比

4 结束语

本文研究用低成本FPGA实现FFT的重要意义在

Implementationof1024-pointFFTAlgorithm

BasedonCycloneFPGA

(IANWenming，LI Xinning，ZHANGYanli

（NationaIASICSystemEngineeringResearchCenter，SoutheastUniversity，Nanjing2l0096，China）Abstract：ThispaperdescribesanimpIementationofl024-pointFFTaIgorithmusingDecimationinFre-guency（DIF）radix2structurebasedontheIow-costFPGAofAItera（CycIoneseriaIs）.ThesystemdesignedbyVeriIogHDLissimuIated，synthesizedbyEDAtooIsandverifiedwiththedeveIopmentboard.AtIast，theperformanceofthewhoIesystemisanaIyzed.ExperimentaIresuItsshowthatthehighspeedofFFTcanbere-aIizedbyIow-costFPGA.

Keywords：FFT；DIF；butterfIyoperation；FPGA

14

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

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

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

钱文明， 刘新宁， 张艳丽， QIAN Wenming， LIU Xinning， ZHANG Yanli东南大学国家专用集成电路系统工程技术研究中心,江苏省南京市,210096电子工程师

ELECTRONIC ENGINEER2007,33(2)6次

1.胡广书 数字信号处理--理论、算法与实现 2003

2.IFEACHOR E C;JERVIS B W;罗鹏飞 数字信号处理实践方法 20043.DINIZ P S R;门爱东 数字信号处理系统分析与设计 2004

4.CHU Chao;ZHANG Qin;XIE Yingke Design of a high performance FFT processor based on FPGA 2005

5.SUNG C H;LEE K B;JEN C W Design and implementation of a scalable fast Fourier transform core[外文会议]2002

1. 孙志坚.刘学梅.SUN Zhi-jian.Liu Xue-mei 在FPGA中实现高速FFT算法的研究[期刊论文]-青岛建筑工程学院学报2005,26(2)

2. 张育钊.邱应强.ZHANG Yu-zhao.QIU Ying-qiang 一种FFT处理器的地址生成算法[期刊论文]-华侨大学学报（自然科学版）2008,29(4)

3. 张辉.张记龙.ZHANG Hui.ZHANG Ji-long 基-2 FFT处理器的FPGA实现[期刊论文]-计算机与现代化2009(5)

1.张裕.方康玲 基于FPGA的通用FFT处理器的设计[期刊论文]-计算机技术与发展 2010(8)2.杨兴.谢志远.戎丽 基于FPGA的FFT处理器设计[期刊论文]-国外电子元器件 2008(5)3.张雪侠 利用FPGA实现FFT的硬件设计的研究[期刊论文]-西部大开发（中旬刊） 2011(3)4.赵敏玲.葛立敏.李文辉 基于FPGA的块浮点FFT的实现[期刊论文]-兰州理工大学学报 2009(4)5.淮永进.屈晓声 具有蝶型单元的FFT在FPGA上的实现[期刊论文]-微电子学 2008(3)

6.刘辉志.张记龙.张辉.李晓.王志斌 实时光谱探测中快速傅里叶变换的FPGA实现[期刊论文]-红外 2009(11)

本文链接：/Periodical_dzgcs200702005.aspx

本文来源：https://www.bwwdw.com/article/rkr4.html