【精品】FFT算法分析.doc

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

1、FFT算法分析FFT算法的基木原理是把长序列的DFT逐次分解为较短序列的DFTo按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的桀数），基2、基4算法较为常用。基2、DIT-FFT（按时间抽取）：n=0=£+E出数〃二奇数N/2-1.v/2-l=£班2训7+£x（2r+1）W严冲）r=0//=0N/2-1N/2-1=EH2厂）W為工x（2r+l）C2r=0/?=0.V/2-1N/2-1令£X2r）C/2=Xi（Zr）,£班2厂+=X2伙），则有:r=0

2、r=0X伙）=X

3、伙）+W：X2伙）X伙+N/2）=X1伙）—W；X2伙）蝶形运算单元如下所示:Xi{k）DIT-FFT基2、DIF-FFT（按频率抽取）:N-X伙)=》x(/7)W『n=0N/2-1N-l=£x(n)W^+工xMW^1n=0n=N/2N/2-1N/2-1=£xS)W『+，xS+N/2)W$z"⑵n=0"=()N/2-1=SU")+W,y%+N/2)K‘n=0N/2-1X(2厂)=工k(/i)+x(/?+N/2)W；；2n=0N/2-1X(2r+1)=工［兀(〃)—兀a+N/2)W；W；；2n=0则冇:x(h)=x(«)+x(n+N/2)X2(n

4、)=［%(/?)-x(n+N12)］昭蝶形运算单元如下所示:g)x©)由前面的分析可知，DIT（按时间抽取）算法与DIF（按频率抽取）算法没有木质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。在基2算法屮，每个蝶形运算单元都包括1次复数乘法、2次复数加法。N（N二2"）点序列的运算流图应有M级蝶形，每一级都由N/2个蝶形运算组成，所以N点序列的基2FFT算法，总的运算量为-log2N次复数乘法，"log?N次复数加法。育接DFT运算量为矿2次复数乘法、N（N-1）次复数加法。可见，FFT算法大大减少了运算量，当N越大时，FFT算法的优

5、越性越明显。基4、DIF-FFT（按频率抽取）N-lX(^)=^X(/2)Cw=0N/4-1N/2-13N/4-1NT=X血)呼+E咖呼+S兀⑷阶+E兀⑷呼w=0〃=N/4n=N$2n=3N/4N/4-1N/4-1N/4-1=£兀⑷呼+工兀S+N/4)Wf"+N⑷+》兀S+N/2)Wysw=0/t=0/t=0N/4-1+》xG+3N/4)W：gN⑷n=0N/4-1=工[X(H)++^/4)IV^，/4+x(n+N/2)W^/2+x(n+37V/4)W^V/4]^'Nw=0N/4-1X(4r)=工[x(n)+兀(死+N/4)+兀(〃+N/2)+x(zz4-3A^/4)

6、]IV^4w=0N/4-1X(4厂+1)=工[X(H)-jx(n+N/4)—兀S+N/2)+jx(n+3N/4)]W^,4w=0N/4-1X(4+2)=工XS)—xS+N/4)+xS+N/2)—jcS+3N/4)]iy7W；；4n=0N/4-1X(4r+3)=工[x(n)+jx(n+/4)-x(n+/2)-+3^/4)]W^W^/47/=0令:xo(n)=x(n)+x(n+N/4)+x(n+N/2)+x(n+3N/4)xi(n)=[x(n)-办:(m+N/4)-兀(m+N/2)+jx(m+37V/4)]W；X2(n)=[x(n)一x(n+N/4)+x(n+N/2)-

7、x(n+3N/4)]WJX3(n)=[x(n)+jx(n+N/4)—x(n+N/2)-jx(n+3N/4)]W："则有:N/4-1N/4-1X(4r)=工xo(n)W；；4,X(4r+l)=工Xi(n)W；；4W=071=0X(4+2)=工X2(/z)W；；4,X(4+3)=X叔〃)昭；4蝶形运算单元如下所示:X10)X2@)响）基4、DIF-FFT蝶形运算单元N/4-1N/4-1由上图可知每个基4蝶形运算单元包括3次复数乘法、8次复数加法。N（N=2",M为偶数）点序列的FFT运算若采用基4算法则有M/2级蝶形，毎级由N/4个蝶形运算构成。3采用基4算法计算N点序

8、列的FFT共需要-Nlog2N次复数乘法、Nlog2N次复数加法。8由于主要的运算时间集屮在乘法上面，可见基4算法的运算量较基2算法减少了25%,但运算量的减少是以硬件的复杂性及使用更多资源为代价的。FFT算法的FPGA实现以8点（复数点，包括实部与虚部）、基2、DIF-FFT为例来考虑FFT算法的FPGA实现。桀个运算流图应由3级蝶形构成，每级屮有4个蝶形运算。若DIF的输入序列为顺序罚)*(4)*(6)*(1)X(5)*⑶考虑采用流水线结构，系统可采用3级基2蝶形运算单元构成，系统总体结构如下所不:并串倒转f换xe总体结构说明输入数据为串行的数据流，故在第一