资源描述：
《基于FPGA的高速流水线FFT算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第34卷第3期电子工程师Vol.34No.32008年3月ELECTRONICENGINEERMar.2008基于FPGA的高速流水线FFT算法实现樊光辉,许茹,王德清(厦门大学通信工程系水声通信与海洋信息技术教育部重点实验室,福建省厦门市361005)摘要:提出了在FPGA(现场可编程门阵列)上实现1024点基4-FFT(快速傅里叶变换)算法的设计方案。方案对FFT算法的核心单元即蝶形运算单元的结构进行了分析和优化,用一个复乘器通过时序控制实现了和3个复乘器同样的效率,而且对整个算法的流程采用了流水线式的工作控制方式,不仅节省了FFT在FPGA上
2、实现时占用的硬件资源,并且极大地提高了算法的运算效率。最后给出了仿真实验结果,并同MATLAB的FFT运算结果进行了对比。结果显示,在100MHz时钟条件下,本方案完成1024点的基4-FFT运算仅需51.28μs,完全满足高速FFT运算的实时性要求。关键词:FFT;基4蝶形运算;流水线;FPGA中图分类号:TP301.600引言X′(0)1111X(0)WNK0X′(2)1-11-1X(1)WN=有限长序列的DFT(离散傅里叶变换)特点是能2K0X′(1)1-j-1jX(2)WN够将频域的数据离散化成有限长的序列。但由于DFTX′(3)1j-1-
3、j3KX(3)W0N本身运算量相当大,限制了它的实际应用。FFT(快速[1](1)傅里叶变换)算法是作为DFT的快速算法提出,它式(1)对于输出变量进行了二进制倒序,便于在将长序列的DFT分解为短序列的DFT,大大减少了运[1]运算过程中进行同址运算,节省了运算过程中所需算量,使得DFT算法在频谱分析、滤波器设计等领域存储器单元的数量。得到了广泛的应用。按DIT(时间抽取)的1024点的基4-FFT共需5FPGA(现场可编程门阵列)是一种具有大规模可级蝶形运算,每级从RAM中读取的数据经过蝶形运编程门阵列的器件,不仅具有专用集成电路(ASIC)快算
4、后原址存入存储单元准备下一级运算。算法的第1速的特点,更具有很好的系统实现的灵活性。FPGA级为一组N=1024点的基4蝶形运算,共256个蝶可通过开发工具实现在线编程。与CPLD(复杂可编形,每个蝶形的距离为256点;第2级为4组N=256程逻辑器件)相比,FPGA属寄存器丰富型结构,更加点的基4蝶形运算,每组64个蝶形,每个蝶形的距离适合于完成时序逻辑控制。因此,FPGA为高速FFT为64点。后3级类推。这种算法每一级的运算具有算法的实现提供了一个很好的平台。相对独立性,每级运算都采用同址运算,因此,本设计1基4-FFT算法基本原理只使用了2个
5、1k×16bits的RAM单元。运算过程中所需的旋转因子的值经过查询预设的正弦与余弦在FFT各类算法中,基2-FFT算法是最简单的一ROM表得到。种,但其运算量与基4-FFT算法相比则大得多,分裂基算法综合了基4和基2算法的特点,虽然具有最少的21024点FFT算法模块的设计复乘运算量,但其L蝶形运算控制的复杂性也限制了[2]本设计的总体框图如图1所示。整个模块的输入其在硬件上的实现,因此,本设计采用了基4-FFT算包括16位带符号实部和虚部数据输入、FFT启动信法结构。号,输出包括16位带符号实部和虚部数据输出、输出基4-FFT算法的基本运算是4
6、点DFT。一个4点有效数据区间标志。内部结构包括2个1k×16bits的DFT运算的表达式为:的实部和虚部双口RAM存储单元、蝶形运算单元、旋收稿日期:2007-07-26;修回日期:2007-09-25。转因子生成模块(包括正弦因子查询表、余弦因子查基金项目:国家自然科学基金(60572106);厦门大学“985”二期询表和象限转换模块)、RAM和ROM存储器地址控制信息创新平台项目。单元、倒序模块以及时序总控制单元。·38·第34卷第3期樊光辉,等:基于FPGA的高速流水线FFT算法实现·计算机与自动化技术·x′+y′i=(x+yi)(c+si
7、)=xc-ys+i(yc+xs)(2)式中:i为虚数单位。这种乘法表达式需要4个实数乘法运算和2个加减运算,设计中对表达式进行如下变换:x′+y′i=(x+yi)(c+si)=x(c+s)-(y+x)s+i[x(s+c)+(y-x)c](3)式(3)这种复乘方式只需要3个实数乘法运算和图1FFT算法的总体结构框图5个加减就可以完成复乘运算,减少了乘法器数量。式中(c+s)值可以在进行象限转换的同时通过计算得下面对主要单元进行分析。到,而无需另外存储。2.1旋转因子产生模块2.2.3数据溢出控制在整个FFT运算过程中,需要存储一组旋转因子为了防止数据
8、计算过程中的溢出,上述蝶形单元表用于蝶形运算,如第1级运算需要的旋转因子有中的加减法运算单元对于输入的4个有符号复数数据0
