F压数 理 22、改进的途径 着考处 利用DFT中W的下述性质,可以减小DFT的运算量 (1)W的对称性:(Ww)=W 2)W的周期性:Wm=W(+Nk=形mk+N) (3)W的可约性:W=Wm,W=WWm 显然有:WmN-8)=W(N-m)=W,WN2=-1,W(+N2)=-Wk 综上所述 (1)利用W的上述特性,可使DFT运算中的有些项可以合并; 2)利用W的对称性、周期性和可约性,可以将长序列的DFT 分解成短序列的DFT。 快速傅里叶变换(FFT)算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类,即按时间 抽选(DT)法,按频率抽选(DIF)法。() () () () 2 ( 2) 1 ( ) 2 3 , 1 1 nk N nk nk nk N N N nk nk n N k n k N N N N N nk nk nmk nk nk m N N mN N N m n N k N n k nk N k N k N N NN N N nk N W W WW W WW W W WW WW W W WW W W W ∗ − + + − −− + = = = = = = = =− =− DFT DFT DFT 利用 中 的下述性质，可以减小 的运算量。 （） 的对称性： （ ） 的周期性： （ ） 的可约性： 显然有： ， ， 综上所述 （）利用 的上述特性，可使 运算中的有 2 ) nk WN DFT DFT FFT DIT DIF 些项可以合并； （ ）利用 的对称性、周期性和可约性，可以将长序列的 分解成短序列的 。 快速傅里叶变换（ 算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类，即按时间 抽选（ ）法，按频率抽选（ ）法。 2、改进的途径