【正文】 ?101( ) ( )N knNkx n X k WN????? ?1011( ) [ ( ) ] { [ ( ) ] }N knNkx n X k W D F T X kNN?? ? ? ?????33 進一步減少運算量措施 快速傅里葉變換（ FFT） 01 , 1NLW??只 有 一 種 旋 轉(zhuǎn) 因 子0 / 42 , 1 , NNNL W W j? ? ? ?只 有 兩 種 旋 轉(zhuǎn) 因 子2N復(fù) 數(shù) 乘 法 運 算 各 減 少( 2 ) ( 2 )2M N M??所 需 復(fù) 數(shù) 乘 法 次 數(shù) C N=2M點 FFT共需 MN/2次復(fù)乘 34 快速傅里葉變換（ FFT） 0 / 43 , 1 , NNNL W W j? ? ? ?其 中 兩 種 旋 轉(zhuǎn) 因 子ML ?同 一 旋 轉(zhuǎn) 因 子 對 應(yīng) 2 個 蝶 形 運 算4ML N???復(fù) 數(shù) 乘 法 運 算 減 少 220 / 43 , 1 , NNNL W W j? ? ? ? ?都 有 兩 個 旋 轉(zhuǎn) 因 子13312 ( ) 22 2 2LMMLLLNN N???? ? ???復(fù) 數(shù) 乘 法 運 算 減 少( 2 ) ( 2 ) ( 2 ) ( 3 ) 22 2 2M N N NMM? ? ? ? ? ? ?所 需 復(fù) 數(shù) 乘 法 次 數(shù) C35 快速傅里葉變換（ FFT） /8 ( 1 ) 2 / 2NNWj ??特 殊 復(fù) 數(shù)22( 1 ) ( ) ( )222[ ( ) ( ) ]2j x jy x jy jx yx y j x y? ? ? ? ? ?? ? ? ?一 次 復(fù) 數(shù) 乘 法 運 算 需 要 四 次 實 數(shù) 乘 ， 兩 次 實 數(shù) 加節(jié) 省 二 次 實 數(shù) 乘32222MLLNN????L=3,實 數(shù) 乘 法運 算 減 少13( 2 ) 4 [ ( 3 ) 2 ] ( 2 ) ( 2 ) 1 02 2 2MNNR M N M? ? ? ? ? ? ? ?36 快速傅里葉變換（ FFT） 一類 蝶形單元運算：包括 所有 旋轉(zhuǎn)因子 蝶 形 單 元 類 型 越 多 ， 編 程 就 越 復(fù) 雜 ，但 乘 法 運 算 的 減 少 量 是 可 觀 的 。 /2n n N??25 快速傅里葉變換（ FFT） / 2 10( ) [ ( ) ( 1 ) ( ) ]2Nk k nNnNX k x n x n W??? ? ? ??/ 2 1/20( 2 ) [ ( ) ( ) ]2NrnNnNk X r x n x n W??? ? ??為 偶 數(shù) ：/ 2 1/20( 2 1 ) [ ( ) ( ) ]2Nn r nNNnNk X r x n x n W W??? ? ? ? ??為 奇 數(shù) ：12( ) ( ) ( )2( ) [ ( ) ( ) ]2nNNx n x n x nNx n x n x n W? ? ?? ? ?1 ()xn2 ()xnnNW1?()xn()2Nxn ?26 快速傅里葉變換（ FFT） (2)X1 1 1 1 2(0)x1(1)x1(2)x1(3)x2(1)x2(2)x2(3)x0NW1NW2NW3NW(0)X(1)X(6)X(3)X(5)X(7)X1(0)x/2NDFT點/2NDFT點(1)x(0)x(4)x(2)x(3)x(5)x(6)x(7)x(4)X27 快速傅里葉變換（ FFT） 1 1 1 1 2(0)x1(1)x1(2)x1(3)x2(1)x2(2)x2(3)x0NW1NW2NW3NW1(0)x(0)x(2)x(1)x(3)x(4)x(3)x(5)x(7)x5(1)x6(0)x6(1)x5(0)x0/2NW1 1/2NW1 0/2NW1 1/2NW 1 7(1)x8(0)x8(1)x7(0)x/4NDFT點/4NDFT點/4NDFT點/4NDFT點(4)X(0)X(1)X(2)X(6)X(5)X(3)X(7)X28 快速傅里葉變換（ FFT） 1 1 1 1 2(0)x1(1)x1(2)x1(3)x2(1)x2(2)x2(3)x0NW1NW2NW3NW1(0)x(0)x(2)x(1)x(3)x(4)x(6)x(5)x(7)x5(1)x6(0)x6(1)x5(0)x0/2NW1 1/2NW1 0/2NW1 1/2NW 1 7(1)x8(0)x8(1)x7(0)x(4)X(0)X(1)X(2)X(6)X(5)X(3)X(7)X0/4NW1 0/4NW1 0/4NW1 0/4NW1 29 快速傅里葉變換（ FFT） 比較 DIFFFT算法與 DITFFT算法的異同點： 相同點 222( 2 ) l o gNNMC M N? ? ? ?2( 2 ) l o gAC M N N N? ? ? ?、圖形類似 不同點 ：輸入是自然序列，輸出是到位序列； DITFFT：輸入是到位序列，輸出是自然序列。/ 2 1 / 2 139。 ( 2 ) l o g22MANNC M N C N M N N? ? ? ? ? ? ?（ ） =15 快速傅里葉變換（ FFT） DITFFT的運算規(guī)律及編程思想 12( ) ( ) ( )kNX k X k W X k??12( ) ( ) ( )2kNNX k X k W X k? ? ?蝶形運算的規(guī)律和通式 旋轉(zhuǎn)因子 的規(guī)律性 kNW122( ) , ( ) , ( ) , ( )NX k X k X k X k?的存儲問題 16 快速傅里葉變換（ FFT） 一、原位計算 利 用 同 一 存 儲 單 元 存 儲 蝶 形 計 算 輸 入 、 輸 出 數(shù) 據(jù))(1) (1A X?1 1 1 1 (4)A(1)A(2)A(3)A(5)A(6)A(7)A0NW1NW2NW3NW)(0 ) (0A X?)( 4 ) (4A X?)( 2 ) (2A X?)(3 ) (3A X?)(5 ) (5A X?)(6 ) (6A X?)(7 ) (7A X?)(0) (0x A?)(2) (2x A?(2)A0NW 1 )(4) (1x A?)(6) (3x A?(1)A(3)A2NW 1 )(1) (4x A?)(3) (6x A?)(5) (5x A?)(7 ) (7x A?(4)A(6)A0NW 1 (5)A(7)A2NW 1 0NW1 0NW1 0NW1 1 17 快速傅里葉變換（ FFT） 二、旋轉(zhuǎn)因子 pNW旋 轉(zhuǎn) 因 子 的 指 數(shù)L 表 示 運 算 級 數(shù) ， = 1 , 2 , M/4 210 Lp J JNNL W W W J? ? ? ?， ，/2 22 0 ,1Lp J JNNL W W W J? ? ? ?， ，23 0 ,1 , 2 , 3Lp J JNNL W W W J? ? ? ?， ，12 0 ,1 , 2 , 2 1Lp J LNL W W J?? ? ?級 ， ，2 2 222L M L MLMMLpJJNJNWWWW????????? 120 , 1 , 2 ,21MLLpJJ??????18 快速傅里葉變換（ FFT） 三、蝶形運算規(guī)律 1111( ) ( ) ( )( ) ( ) ( )pL L L NpL L L NX J X J X J B WX J B X J X J B W????? ? ? ?? ? ? ? ?L 表 示 運 算 級 數(shù) ， = 1 , 2 , M( ) ( )LX J X J表 示 第 L 級 運 算 后 數(shù) 組 元 素 的 值12 0 , 1 , , 2 1M L Lp J J??? ? ? ?；12 2 2L p L M LNBW ??? ， 同 一 對 應(yīng) 著 間 隔 為 點 的 個 蝶 形19 快速傅里葉變換（ FFT） 四、編程思想及程序框圖 開始 送入 x(n),M N=2M 倒序 L=1， M J=0， B1 B=2L1 P=2MLJ ( ) ( ) ( )( ) ( ) ( )pNpNX k X k X k B WX k B X k X k B W? ? ? ?? ? ? ? ?輸出 結(jié)束 k=J,N1,2L ( ) ( ) ( )( ) ( ) ( )pNpNX k X k X k B WX k B X k X k B W? ? ? ?? ? ? ? ?20 快速傅里葉變換（ FFT） 四、序列的倒序 )(1) (1A X?1 1 1 1 (4)A(1)A(2)A(3)A(5)A(6)A(7)A0NW1NW2NW3NW)(0 ) (0A X?)( 4 ) (4A X?)( 2 ) (2A X?)(3 ) (3A X?)(5 ) (5A X?)(6 ) (6A X?)(7 ) (7A X?(0)A)(0) (0x A?)(2) (2x A?(0)A(2)A0NW 1 )(4) (1x A?)(6) (3x A?(1)A(3)A2NW 1 )(1) (4x A?)(3) (6x A?)(5) (5x A?)(7 ) (7x A?(4)A(6)A0NW 1 (5)A(7)A2NW 1 0NW 1 0NW 1 0NW 1 0NW 1 輸出是自然序列，輸入稱為倒位序列，即二進制數(shù)倒位 21 快速傅里葉變換（ FFT） 000 0x（ ）2 1 0( , , )x n n n0 0 n ? 偶0 1 n ? 奇1 0n ?1 1n ?1 0n ?1 1n ?2 0n?2 1n?2 0n?2 1n?2 0n?2 1n?2 0n?2 1n?100 4x（ ）010 2x（ ）110 6x（ ）001 1x（ ）101 5x（ ）011 3x（ ）111 7x（ ）22 快速傅里葉變換（ FFT） 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7