【文章內(nèi)容簡介】 NW2NW1 1 )1()0(55XX)1()0(66XX0NW2NW1 1 0NW1 點(diǎn) DFT 4N 點(diǎn) DFT 4N 點(diǎn) DFT 4N 點(diǎn) DFT 4N0NW1 0NW1 0NW1 第 4章 快速傅立葉變換（ FFT） 圖 N點(diǎn) DIT―FFT 運(yùn)算流圖 (N=8) W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0x ( 0 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )A ( 0 )A ( 7 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )第 4章 快速傅立葉變換（ FFT） DIT―FFT 算法與直接計(jì)算 DFT運(yùn)算量的比較 ? 每一級運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù)加 (每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。 所以 ， M級運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 2222lo glo g? ? ?? ? ?MANNC M NC N M N N復(fù)數(shù)加次數(shù)為 例如 ， N=210=1024時(shí) 221048576 2 0 4 .8( / 2 ) l o g 5 1 2 0NNN ??第 4章 快速傅立葉變換（ FFT） 圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線 第 4章 快速傅立葉變換（ FFT） 由圖 ， DIT―FFT 的運(yùn)算過程很有規(guī)律 。N=2M點(diǎn)的 FFT共進(jìn)行 M級運(yùn)算 ， 每級由 N/2個(gè)蝶形運(yùn)算組成 。 在 N點(diǎn) DITFFT運(yùn)算流圖中，每級都有 N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子 ，稱其為 旋轉(zhuǎn)因子， p為旋轉(zhuǎn)因子的指數(shù) 。但各級的旋轉(zhuǎn)因子和循環(huán)方式都有所不同。為了編寫計(jì)算程序，應(yīng)先找出旋轉(zhuǎn)因子 與運(yùn)算級數(shù)的關(guān)系。用 L表示從左到右的運(yùn)算級數(shù) (L=1， 2， … ， M)。觀察圖 ，第 L級共有 2L－ 1個(gè)不同的旋轉(zhuǎn)因子。 N=23=8時(shí)的各級旋轉(zhuǎn)因子表示如下： pNWpNW DIT―FFT 的運(yùn)算規(guī)律及編程思想 2 對 N=2M的一般情況，第 L級的旋轉(zhuǎn)因子為 3,2,1,0 31,0 20 1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)時(shí)時(shí)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. 蝶形運(yùn)算規(guī)律 設(shè)序列 x(n)經(jīng)時(shí)域抽選 (倒序 )后 ， 存入數(shù)組 X中 。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn) ， 應(yīng)用原位計(jì)算 ， 則蝶形運(yùn)算可表示成如下形式： AL (J) AL1(J)+A L1(J+B)WpN AL(J+B) AL1(J)A L1(J+B)WpN 式中 p=J2 ML； J=0,1,…， 2 L11； L=1,2,…， M ?? 下標(biāo) L表示第 L級運(yùn)算 ， AL(J)則表示第 L級運(yùn)算后數(shù)組元素 A(J)的值 。 而 AL－ 1(J)表示第 L級運(yùn)算前 A(J)的值 （ 即第 L級蝶形的輸入數(shù)據(jù) ） 4. 編程思想及程序框圖 圖 DIT―FFT 運(yùn)算和程序框圖 開 始送入 x ( n ) ， MN ＝ 2 M倒 序L ＝ 1 , MＪ ＝ 0 , B － 1P ＝ 2 M － LJk ＝ J , N － 1 , 2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(???????輸 出結(jié) 束B 2 L － 1 DIT―FFT 算法的輸入序列的排序看起來似乎很亂 ，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的 。 由于N=2M， 所以順序數(shù)可用 M位二進(jìn)制數(shù) (nM1nM2…n1n0)表示 。 圖 形成倒序的樹狀圖 (N=23) 01010101010101( n2n1n0)2000 042615371000101100011010111115. 序列的倒序 表 順序和倒序二進(jìn)制數(shù)對照表 圖 倒序規(guī)律 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) 圖 倒序程序框圖 221????NNLHJNLHI ＝ 1 , N1I ≥ JTJAJXIAIXT???)()()()(J ＜ KLHK ?KJJ ??2KKKJJ???ＹNNY 頻域抽取法 FFT（ DIT_FFT) ?算法原理 ????10)()(NnnkNWnxkX????????12/10)()(2 NNnnkNnnkN WnxWnxN??????????10)(10222)2()(NNNnknNnnkN WNnxWnx(一 )N/2點(diǎn) DFT 第 4章 快速傅立葉變換（ FFT） nkNnkN WWNnxnxNN????????? ??? 1022)2()(, 12 ??? ? ?jN eW N kkNNW )( 12 ??nkNnk WNnxnxkXN????????? ???? 102)2()1()()(1,1,0 ?? Nk ?第 4章 快速傅立葉變換（ FFT） nrNnWNnxnxrXN2102)2()()2( ????????? ???k為偶數(shù)時(shí)： nrnNNWNnxnx22 10)2()(????????? ??? 1,1,02 ?? Nr ?)(1 nxk為奇數(shù)時(shí)： nrnnN NNWWNnxnx22 10)2()(??? ???????????? ???)(2 nx1,1,0 2 ?? Nr ?)12(102)2()()12( ???? ?????? ???? rnNnWNnxnxrXN第 4章 快速傅立葉變換（ FFT） 1,1,0 )]2()([)()2()()(221???????????????NnNnWNnxnxnxNnxnxnx?1,1,0 )()12()()2(21202120122???????????????????? NnrNnnrNnrWnxrXWnxrXNN? 可見 ,上面兩式均為 N/2的 DFT。 第 4章 快速傅立葉變換（ FFT） )2()()(1 Nnxnxnx ???1,1,0 2 ?? Nn ?nNWNnxnxnx?????? ??? )2()()(2進(jìn)行如下碟形運(yùn)算：和 )2()( Nnxnx ?1 nNW)2( Nnx ?)(nx(二 )蝶形運(yùn)算 第 4章 快速傅立葉變換（ FFT） 圖 DIF―FFT 蝶形運(yùn)算流圖符號 第 4章 快速傅立葉變換（ FFT） N=8時(shí) ,按 k的奇偶分解過程先蝶形運(yùn)算 ,后作 DFT: 1 1 1 1 )0(x)1(x)5(x)4(x