【精品】FFT算法分析

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

1、FFT算法分析FFT算法的革本原理是把长序列的DFT逐次分解为校短序列的DFTo按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。基2、DIT-FFT（按时间抽取）：X伙）=Y兀n=0=X血）呼+X血）呼川=偶数心奇数N/2-1N/2-1=£兀（2训了+£兀（2厂+1）比铲Mr=0?i=0N/2-IN/2-1=X兀（2JW爲+肌X班2广+1）肌；2r=0n=0N

2、/2-1/V/2-1令》兀（2厂）叫：2=XKk）,》兀（2厂+1）叭；2=X2伙），则有:r=0r=0X伙）=X1伙）+W/X2伙）X仗+N/2）=X1伙）—W；X2伙）蝶形运算单元如下所示:艸）DIT-FFT基2、DIF-FFT（按频率抽取人N・1X(幻二工n=0N/2-1N-l=£+工兀S)wf/i=0n=Ni2N/2-1N/2-1=£血)呼+£心+n⑵叭曲⑵/:=0/i=0N/2-1=工M)+W畀2心+N/2)WF?:=0N/2-1x(2门=工[x(n)+x(n+N/2)^l/271=0N/2-1

3、X(2r+1)=工[如-g+W/2)叫W；；2n=0则有：xi(n)=x(n)+x(n+N/2)X2(z?)=[x(h)一x(n+N/2)]W；蝶形运算单元如下所示：DIF-FFT由前面的分析町知，DIT（按吋间抽取）算法-UDIF（按频率抽収）算法没有本质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。在棊2算法中，每个蝶形运算单元都包括1次复数乘法、2次复数加法。N（N二2"）点序列的运算流图应冇M级蝶形，每一级都由N/2个蝶形运算组成，所以N点序列的基2FFT算法，总的

4、运算量为—log2N次复数乘法，/Vlog2N次复数加法。直接DFT运算量为2次复数乘法、N（N-1）次复数加法。可见，FFT算法大人减少了运算量，当N越人时，FFT算法的优越性越明显。基4、DIF-FFT（按频率抽取）NTX(k)=X^n)W^n=0N/4-1N/2-13N/4-1N-=XX^WN+Z+Z+ZX^WNn=0zt=N/4n=N/2/i=3Af/4N/4-1N/4-1N/4-1=工x(n)W^n+工兀S+N/4)W『+n⑷+工x(n+N/2)呼"?)n=0n=0/t=0N/4-1+为x(〃

5、+3N/4)W：gN⑷n=0N/4-1=工[兀S)+xS+N/4)叱律"+兀(〃+2/2)叱畀2+xS+3N/4)wJNM]wy“=0N/4-1x(4r)=工[x(n)+兀⑺+N/4)+x®+N/2)+x(n+3N/4)]WQw=0N/4-1X(4r+1)=工[x(n)-jx(n十N/4)—x(n+N/2)+jx(n+3/V/4)]lVX^4〃=0N/4-1X(4r+2)=工[x(n)一兀(〃+N/4)+x(n+N/2)—兀⑺+3N/4)]W?W；；4n=0N/4-1X(4r+3)=工[xS)+/xS+N

6、/4)—xa+N/2)-/xS+3N/4)]比：W；；4n=0令：xo(n)=x(n)4-x(n+N/4)+x(n+N/2)+x(n+3N/4)xi(n)=[x(n)-办S+N/4)—x(t?+N/2)+灿1+3N/4)]%；X2(n)=[x(n)一x(n+N/4)+x(n+N/2)-x(n+3N/4)]W；"X3(n)=[x(n)+jx(n+N/4)-x(n+2V/2)-/r(n+3N/4)]Wj则有:N/4-1N/4-1X(4r)=工xo(")WQ，X(4厂+1)=为n=0?i=0N/4-1N/4-1

7、X(4r+2)=工X2(,i)W^4,X(4r+3)=工X3(n)W；%/?=0n=0蝶形运算单元如下所示:-J基4、DIF-FFT蝶形运算单元由上图可知每个基4蝶形运算单元包括3次复数乘法、8次复数加法。N（N=2jM为偶数）点序列的FFT运算若采用基4算法则有M/2级蝶形，每级lllN/4个蝶形运算构成。3采用基4算法计算N点序列的FFT共需要二Nlog?N次复数乘法、Nlog2N次复数加法。8由于主要的运算时间集中在乘法上面，可见基4算法的运算量较基2算法减少了25%,但运算最的减少是以硬件的复杂性

8、及使用更多资源为代价的。FFT算法的FPGA实现以8点（复数点，包括实部与虚部）、基2、DIF-FFT为例来考虑FFT算法的FPGA实现。整个运算流图应由3级蝶形构成，每级屮有4个蝶形运算。若DIF的输入序列为顺丿芋*(0)*(4)*⑵*(6)*(1)・*(5)*⑶Xf7)串并转换radix-2旋转因子产生radix-2并出转换延时对齐延时対齐考虑采用流水线结构，系统可采用3级基2蝶形运算单元构成，系统总体结构如下所示:总体结