【正文】 于N=2M， 所以順序數(shù)可用 M位二進制數(shù) (nM1nM2…n1n0)表示 。2 ML； J=0,1,…， 2 L11； L=1,2,…， M ?? 下標 L表示第 L級運算 ， AL(J)則表示第 L級運算后數(shù)組元素 A(J)的值 。 N=23=8時的各級旋轉因子表示如下： pNWpNW DIT―FFT 的運算規(guī)律及編程思想 2 對 N=2M的一般情況，第 L級的旋轉因子為 3,2,1,0 31,0 20 1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時時時2120 1 2 2 12, , , , ,MLLMP J J LNN NMLW W W JpJ??????? ? ? ? ? ? ???12 , 0 , 1 , 2 , , 2 12 2 2 2???? ? ??? ?? ? ? ?Lp J LNL M L M L MW W JN3. 蝶形運算規(guī)律 設序列 x(n)經(jīng)時域抽選 (倒序 )后 ， 存入數(shù)組 X中 。用 L表示從左到右的運算級數(shù) (L=1， 2， … ， M)。但各級的旋轉因子和循環(huán)方式都有所不同。 在 N點 DITFFT運算流圖中，每級都有 N/2個蝶形。 所以 ， M級運算總共需要的復數(shù)乘次數(shù)為 2222lo glo g? ? ?? ? ?MANNC M NC N M N N復數(shù)加次數(shù)為 例如 ， N=210=1024時 221048576 2 0 4 .8( / 2 ) l o g 5 1 2 0NNN ??第 4章 快速傅立葉變換（ FFT） 圖 FFT算法與直接計算 DFT所需乘法次數(shù)的比較曲線 第 4章 快速傅立葉變換（ FFT） 由圖 ， DIT―FFT 的運算過程很有規(guī)律 。所以，計算 N點 DFT時，總共需要的復數(shù)乘法次數(shù)為 2 21122 2 2 2()????? ? ? ?????NN N N N N 222122NNNN ???????? ?第 4章 快速傅立葉變換（ FFT） 由于 N=2M ,所以 N/2仍為偶數(shù) ,可以進一步把每個 N/2點的序列再按其奇偶部分分解為兩個 N/4的子序列。()(),()(),()(),()(735231102222xxxxxxxx????3,2,1,0)12()()(30430422 ???? ????kWrxWrxkXrrkrrk)(/ kXD F TN 242 ，得點的進行 ?3,2,1,0),()()4()()()(2121??????kkXWkXkXkXWkXkXkNkN)0()0(1 xx ?)2()1(1 xx ?)4()2(1 xx ?)6()3(1 xx ? 點 DFT 2N)3()2()1()0(1111XXXX)1()0(2 xx ?)3()1(2 xx ?)5()2(2 xx ?)7()3(2 xx ? 點 DFT 2N)3()2()1()0(2222XXXX)0(X)4(X0NW)1(X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW1 1 1 1 一個 N點 DFT分解為兩個 N/2點 DFT的信號流圖 3,2,1,0),()()4()()()(2121??????kkXWkXkXkXWkXkXkNkN圖 N點 DFT的一次時域抽取分解圖 (N=8) N /2 點D F TW N0N /2 點D F TW N1W N2W N3x ( 0 )X1( 0 )x ( 2 )x ( 4 )x ( 6 )x ( 1 )x ( 3 )x ( 5 )x ( 7 )X1( 1 )X1( 2 )X1( 3 )X2( 0 )X2( 1 )X2( 2 )X2( 3 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )第 4章 快速傅立葉變換（ FFT） 經(jīng)過一次分解后，計算 1個 N點 DFT共需要計算兩個 N/2點DFT和 N/2個蝶形運算。()(),()(),()(),()(634221001111xxxxxxxx????)。 *N點的 DFT可由兩個 N/2點的 DFT來計算。 (2) X(k)=X1 (k)+WNk X2 (k)只能確定出 X(k)的k= … .N/21 個，即前一半的結果。直到 1965年提出 DFT的一種快速算法以后，情況才發(fā)生了根本的變化。第 4章 快速傅立葉變換（ FFT） 引言 基 2FFT算法 進一步減少運算量的措施 其他快速算法簡介 引 DFT是數(shù)字信號分析與處理中的一種重要變換。但直接計算 DFT的計算量與變換區(qū)間長度 N的平方成正比，當 N較大時，計算量太大，所以在快速傅里葉變換 FFT(Fast Fourier Transform)出現(xiàn)以前，直接用 DFT算法進行譜分析和信號的實時處理是不切實際的。 第 4章 快速傅立葉變換（ FFT） 基 2FFT算法 直接計算 DFT的特點及減少運算量的基本途徑 1,1,0 ,)()(10??? ???NkWnxkXNnnkN ????? ???101,1,0 ,)(1)(NknkN NnWkXNnx ?兩者的差別僅在指數(shù)的符號和因子 1/N. 1. 直接計算 DFT的運算量 第 4章 快速傅立葉變換（ FFT） 計算一個 X(k)的值： N次復數(shù)乘法運算 N1 次復數(shù)加法運算 . 一個 X(k)的值的工作量 ,如 X(1) 1210 )1()2()1()0()1( ??????? NNNNN WNxWxWxWxX ?N點 DFT運算量： 復數(shù)乘法： N2 復數(shù)加法： N(N1) 第 4章 快速傅立葉變換（ FFT） 2 改進的途徑 的對稱性、周期性、可約性 nkNW.),1(1)2/(2/ 2kNNkNjNNNWWeWWN???????????nkNnkN WW ??*)(對稱性 : mnkmNn m kmNnkN WWW ??可約性 : 周期性 : )(NknnkW??)1( )(2)()( ????? ????? nkNnNNkNnkNknNNkNnN eWWWWW ?第 4章 快速傅立葉變換（ FFT） 時域抽取法基 2FFT基本原理 ?????10)()]([)(NnnkNWnxnxD F TkX? 算法原理 (一 )N/2點 DFT 1,1,0 ),()12(1,1,0 ),()2(2221???????NNrrxrxrrxrx?? x(n) 按 n的奇偶分為兩組作 DFT,設 N=2M , 這樣有 : n為偶數(shù)時 : n為奇數(shù)時 : 第 4章 快速傅立葉變換（ FFT） ??????????10)12(10222)12()2(NNrkrNrrkN WrxWrx? ???????1010)()()(NnNnnkNnkN WnxWnxkX (n為偶數(shù) ) (n為奇數(shù) ) 222 )/(222NNN WeeW jjN ??????? ?因為：)()()()()( kXWkXWrxWWrxkX kNrrkkNrrkNNNN 2110 210 12222???? ??????????????1022102122))(())((NNrrkNkNrrkN WrxWWrx第 4章 快速傅立葉變換（ FFT） (1) X1 (k),X2 (k)均為 N/2點的 DFT。 ?????????????????10102210101122222222122NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX)()()()()()( 第 4章 快速傅立葉變換（ FFT） (k)的后一半的確定 )()2( 11 kXkNX ?? )()2( 22 kXkNX ??由于 X1(k)和 X2(k)均以 N/2為周期，得 )2()2()2( 2)2(1 NkXWNkXNkXNkN ?????＋kNkNN WWWN ??? 21,1,0 )()()2