FFT算法分析精.docx

《FFT算法分析精.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFTo按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。基2、DIT-FFT(按时间抽取人X伙)=工心)必'n=0=X+X"偶数2奇数N/2-1N/2-1=£x(2r)C2r+£x(2r+l)W；(2r+,)r=0n=0N/2-1N/2-1=ZX2r)C2£兀(2厂+1)臥；2r=0z?=0N/2-1N/2-1令工x(2

2、”W；；2=Xi伙)，工班2厂+l)Wj；2=X2伙)，则有:r=0r=0X伙)=Xi(k)+W；X2伙)X(k+N/2)=Xi(k)-W^X2(k)XiQt)DIT-FFT基2、DIF-FFT(按频率抽取)：N・X⑹二》＞(小枕“”=0N/2-】N-1=S血)呼+x心)呼/j=0n=N}2N/2-】N/2-1=Ex(72)W『+£x(/?+N/2)W,e⑵71=0P】=0N/2-1=工[心)+叱畀2如川⑵畸71=0N/2-1x(2门二工[xS)+xa+N/2)W・，；；27：=0N/2-1X(2r+1)=XMn)-x(n+N/2)W

3、Xf2n=0则有：xi(n)=x(n)+x(n+N/2)X2(n)=[%(/?)一x{n+N/2)]W$心+"/2丫、兀2（勿DIF-FFT由前面的分析可知，DIT（按时间抽取）算法与DIF（按频率抽取）算法没有本质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。在基2算法中，每个蝶形运算单元都包括1次复数乘法、2次复数加法。N（N=2"）点序列的运算流图应有M级蝶形，每一级都由N/2个蝶形运算组成，所以N点序列的基2FFT算法，总的运算量为斗呃“次复数乘法，Nlog2N次复数加法。直接DFT运算量为矿次复

4、数乘法、N（N-1）次复数加法。可见，FFT算法大大减少了运算量，当N越大时，FFT算法的优越性越明显。基4、DIF-FFT（按频率抽取）N-lX伙)=0(吨n=0N/4-1N/2-13N/4-1N-=ZX^WN+Z+Z+Zx(〃)wfn=0n=N14n=N/2”=3N/4/V/4-1N/4-1N/4-1=工x(n)W^n+工兀S+N/4)W：e⑷+工xS+N/2)W『+n⑵n=0n=0n=0N/4-1+工x(〃+3N/4)WjgN⑷n=0N/4-1=工Mn)+x(n+N/4)W^/4+x(n+N/2)^A，/2+x(h+37V/4)

5、W^kN,4]W^?»=0N/4-1x(4r)=为[兀⑺)+尢S+N/4)++N/2)+x(n+3N/4)]W；；/i=0N/4-1X(4r+1)=工[x(〃)—”(〃+N/4)-兀S+N/2)+jx(n+3^/4)]^；^4〃=0N/4-1X(4r+2)=工[x(/i)一x(n+N/4)+x(n+N/2)—兀⑺+3N/4)]W$”肖爲71=0N/4-1X(4r+3)=工[%(/?)+jxS+N/4)—xa+N/2)-/xS+3N/4)]U^W；；4w=0令：xo(n)=x(n)+x(n+N/4)+x(n+N/2)+x(n+3/V/4)

6、x(n)=[x(n)一jx(n+N/4)-x(n+N/2)+jx(n+3N/4)]W,X2(n)=[x(n)一x(n+N/4)+兀O+N/2)-兀⑺+3N/4)网"X3(n)=[x(n)+jx(n+N/4)-x(n+N/2)-jx(n+3N/4)]W："则有：N/4-1N/4-1X(4r)=工xo(H)W；；4,X(4r+l)=工xi(h)W；%”=0N/4-1N/4-1X(4r+2)=XX2(n)^4,X(4r+3)=工xs(m)W；；4fi=0n=0xoQi)Xl(n)X20)X3("基4、DIF-FFT蝶形运算单元由上图可知每个

7、基4蝶形运算单元包括3次复数乘法、8次复数加法。N（N=2JM为偶数）点序列的FFT运算若采用基4算法则有M/2级蝶形，每级由N/4个蝶形运算构成。采用基4算法计算N点序列的FFT共需要^Nog2N次复数乘法、N鸥2N次O复数加法。由于主要的运算时间集中在乘法上面，可见基4算法的运算量较基2算法减少了25%,但运算量的减少是以硬件的复杂性及使用更多资源为代价的。FFT算法的FPGA实现以8点（复数点，包括实部与虚部）、基2、DIF-FFT为例来考虑FFT算法的FPGA实现。整个运算流图应由3级蝶形构成,每级中有4个蝶形运算。若DIF

8、的输入序列为顺序输入，则得到倒序输出。完整的运算流图如下所示：X(0)*(4)X⑵*(6)X(l)・X(5)X⑶XQ)考虑采用流水线结构，系统可采用3级基2蝶形运算单元构成，系统总体结构如下所示：radix