资源描述：
《FPGA实现FFT的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第19卷 第2期北京理工大学学报Vol.19No.21999年4月JournalofBeijingInstituteofTechnologyApr.1999用FPGA实现FFT的研究刘朝晖 韩月秋(北京理工大学电子工程系,北京 100081)摘 要 目的 针对高速数字信号处理的要求,给出了用现场可编程门阵列(FPGA)实现的快速傅里叶变换(FFT)方案Z方法 算法为按时间抽取的基4算法,采用递归结构的块浮点运算方案,蝶算过程只扩展两个符号位以适应雷达信号处理的特点,乘法器由阵列乘法器实现Z结果 采用流水方式保证系统的速度,使取数据、计算旋转因子、复乘、DFT等操作协调一致,在
2、计算、通信和存储间取得平衡,避免了瓶颈的出现Z结论 实验表明,用FP2GA实现高速数字信号处理的算法是一个可行的方案Z关键词 离散傅里叶变换;快速傅里叶变换;块浮点运算;可编程门阵列分类号TP39;TN95715111FFT算法选择[1]提高FFT速度的两个主要技术途径是采用流水线结构和并行运算,采用高基数结构也可以提高速度,只是算法中基数r的选择,在考虑运算量的同时,还应综合考虑系统的要求、FPGA的结构特点及对片内资源的占用Z1个基2蝶算由1个复乘和2个复加组成,而1个基4蝶算包含3个复乘和8个复加,在硬件上实现3个复数乘法器会占用FPGA中太多的资源,但如果充分利用FPG
3、A片内的寄存器,以流水的方式运算,可以用1个复数乘法器和6个实数加法器实现蝶算,因此二者占用面积相差不大Z基2算法虽相对基4算法占用的资源较少,但为满足系统运算的速度,要求FFT有更小的流水周期Z当对FPGA内部资源占用较少时,这一速度要求不难满足;但由于FPGA的内部连线资源有限,故当设计中对于FPGA的资源利用率相当高时,各信号间连线延时加大,这一要求往往不容易满足Z若采用高基数结构的基4算法,降低了运算量,同时提高了速度,在系统时钟频率相同时,基4处理器运算速度是基2处理器的2倍Z故基4算法更便于对FPGA的布局、布线和调试Z2 算数运算方案若{x(n)}是一N点序列,其
4、DFT为{X(K)},由Parseval定理得N-1N-1212∑x(n)=∑ûX(K)ûZ(1)n=0NK=0由式(1)可知变换结果的均方值是输入序列均方值的N倍Z考虑基4的FFT算法第m级蝶式运算,由蝶算公式k2k3kxm+1(p1)=xm(p1)+xm(p2)W+xm(p3)W+xm(p4)W,(2)收稿日期:19980410©1995-2003TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved. 第2期刘朝晖等:用FPGA实现FFT的研究235k式(2)中p1,p2,p3,p4为该级蝶算输入数据的序号,W为旋转因子Z
5、可得m+1级蝶算输出与m级蝶算输出的关系为ûxm+1(p1)û≤ûxm(p1)û+ûxm(p2)û+ûxm(p3)û+ûxm(p4)û≤ 4max{ûxm(p)û,ûxm(p2)û,ûxm(p3)û,ûxm(p4)û},(3)式(3)表明序列中数的值一般是逐级增大的,且复数的最大模值以小于每级2个二进位的速度增长Z由以上讨论可知,当采用定点运算时,必须用定比例的方法防止溢出,即必须解决动态范围的问题Z若采用浮点运算,则运算复杂性增加且运算速度降低Z这里采用文献[2]给出的块浮点方案,其基本思想是在计算DFT过程中要更多地扩充符号位Z在DFT输出端,检验数据的扩充符号位,以确定
6、数据所需右移的位数,保证下一级蝶算不溢出Z可见该方案运算操作简单且具有较高的精度Z由式(3)可知,若输入数据的模可以用N位表示,则每级蝶算输出的模可以用N+2位表示,因而蝶算输出的实部、虚部都可以只用N+2位表示Z通常情况下,输入数据的实部、虚部分别为N位字长,即输入数据的模为N+1位,蝶算结果必须采用N+3位字长来防止溢出Z对于雷达信号处理而言,为消除盲速,一般采用零中频、正交双通道处理,因此若实部、虚部分别用N位字长表示,则能够保证输入数据的模为N位,蝶算输出可以只用N+2位表示,即每级蝶算只需扩展2个符号位Z对于基2、基8等算法,也能得出相应的结果Z这一结论的意义在于明确
7、了输出结果的有效最高位Z3 硬件实现方案对于基4的FFT算法,具体讨论以下单元电路:①由于FFT是混序算法,因而需要读取数据的地址产生单元;②相应旋转因子值的计算;③由复数乘法器或CORDIC旋转器完成与旋转因子相乘;④块浮点防溢出电路Z311 地址发生器及旋转因子的产生p[3]设序列x(n)的长度为N=4,其中p为正整数,则基4按时间抽取的蝶算单元的方程为p-snp-s2np-s3nX(n)=x(n)+x(n+4)W4s+x(n+2×4)W4s+x(n+3×4)W4sp-sp-snp-s2
