四章快速傅里叶变换fft.ppt

第四章 快速傅里叶变换（ FFT ） Chapter 4 Fast Fourier-Transform 时间抽取 DIT 基 2FFT 算法 / 2 1 / 2 1 / 2 1 / 2 1 2 (2 1) / 2 / 2 0 0 0 0 / 2 1 / 2 0 2 , ( ) 2 2 1, 0,1,..., / 2 1, ( ) (2 ) (2 1) (2 ) (2 1) ( ) (2 ) ; 0,1,..., / 2 1 ( M N N N N rk r k rk k rk N N N N N r r r r N rk N r N M n x n n r n r r N X k x r W x r W x r W W x r W A k x r W k N B k ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 为正整数 按照 奇偶把 分为两组,令： 和 则： 令： / 2 1 / 2 0 / 2 1 / 2 1 ( / 2) / 2 ( / 2) / 2 / 2 0 0 / 2 1 / 2 / 2 0 / 2 ) (2 1) ; 0,1,..., / 2 1 ( ) ( ) ( ); 0,1,..., / 2 1 ( / 2) (2 ) (2 1) (2 ) (2 1) N rk N r k N N N r k N k N r k N N N N r r N rk k rk N N N r N DFT x r W k N X k A k W B k k N X k N x r W W x r W x r W W x r W ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 两个 点的 / 2 1 0 ( ) ( ) N r k N A k W B k ? ? ? ? ? / 2 1 / 4 1 / 4 1 / 4 1 / 4 1 2 (2 1) / 2 / 2 / 2 / 4 / 2 / 4 0 0 0 0 0 / 2 ( ) , ( ) 2 2 1, 0,1,..., / 4 1, ( ) (2 ) (4 ) (4 2) (4 ) (4 2) ( ) ( ) 0,..., N N N N N rk lk l k lk k lk N N N N N N r l l l l k N A k B k r l r l l N A k x r W x l W x l W x l W W x l W C k W D k k N ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 继续按照上述方法分解， 令： 和 则： / 2 / 4 1 / 2 0 / 4 1 / 2 0 / 2 1 / 4 1 2 / 2 / 2 0 0 / 4 1 ( / 4) ( ) ( ) 0,..., / 4 1 ( ) (4 ) ; 0,1,..., / 4 1 / 4 ( ) (4 2) ; 0,1,..., / 4 1 ( ) (2 1) (4 1) (4 k N N rk N l N rk N l N N rk lk N N r l A k N C k W D k k N C k x l W k N N DFT D k x l W k N B k x r W x l W x l ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 两个 点的 同理： / 4 1 / 4 1 / 4 1 (2 1) / 2 / 4 / 2 / 4 0 0 0 / 2 / 2 / 4 1 / 2 0 / 2 3) (4 1) (4 3) ( ) ( ) 0,1,..., / 4 1 ( / 4) ( ) ( ) 0,..., / 4 1 ( ) (4 1) ; 0,1,..., / 4 1 ( ) (4 3) N N N l k lk k lk N N N N l l l k N k N N rk N l r N W x l W W x l W E k W F k k N B k N E k W F k k N E k x l W k N F k x l W ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? / 4 1 0 / 4 ; 0,1,..., / 4 1 N k l N DFT k N ? ? ? ? ? ? ? ? ?