-第3快速疼里叶变换一 则可将DFT化为 N X(k)=DFT[x(m)=∑x(mW=∑x(m+∑xm n=0 n为偶数 n为奇数 N ark X(2r +∑x2r+1 (2r+1)k N ∑x()V2)+W∑x()V)y 12 由于W e 故上式可表示成 N/2 X()=∑x()2+W∑x()W2=X)+X( F=0 (3-5)
第3章 快速傅里叶变换 则可将DFT化为 r k N N r k N r k N N r r k N N r r k N N r N n n n k N N n N n n n k N n k N x r W W x r W x r W x r W X k DFT x n x n W x n W x n W ( )( ) ( )( ) (2 ) (2 1) ( ) [ ( )] ( ) ( ) ( ) 2 1 2 0 2 2 1 2 0 1 (2 1) 1 2 0 2 1 2 0 1 0 1 0 1 0 − = − = + − = − = − = − = − = = + = + + = = = + 为偶数 为奇数 由于 ， 故上式可表示成 / 2 2 2 2 2 2 N j N j WN = e = e =W − − ( ) ( ) ( ) ( ) ( ) 2 / 2 1 2 1 2 0 1 / 2 1 2 0 X k x r W W x r W X k W X k k N r k N N r k N r k N N r = + = + − = − = （3-5）
-第3快速疼里叶变换一 式中,X1(k)与x4(k)分别是x()及x2(7)的N2点DFT: X(k)=∑x()WM2=∑x(2)W2(36) X()=∑x()W2=∑x(2r+1)W2(37) 由此,我们可以看到,一个N点DFT已分解成两个M2点的DFT。 这两个M2点的DFT再按照式(3-5)组合成一个N点DFT。这里 应该看到X(k,X(k只有M2个点,即k=0,1,…,M21。而X(k)却 有M个点,即k=0,1,…,N-1,故用式(35)计算得到的只是X(k) 的前一半的结果,要用X1(k),X2(k来表达全部的X(A)值,还必须 应用系数的周期性,即
第3章 快速傅里叶变换 式中，X1 (k)与X2 (k)分别是x1 (r)及x2 (r)的N/2点DFT： r k N N r r k N N r r k N N r r k N N r X k x r W x r W X k x r W x r W / 2 1 2 0 2 / 2 1 2 0 2 / 2 1 2 0 1 / 2 1 2 0 1 ( ) ( ) (2 1) ( ) ( ) (2 ) = = + = = − = − = − = − = （3-6） （3-7） 由此，我们可以看到，一个N点DFT已分解成两个N/2点的DFT 。 这两个N/2点的DFT再按照式（3-5）组合成一个N点DFT。这里 应该看到X1 (k)，X2 (k)只有N/2个点，即k=0, 1, …, N/2-1。而X(k)却 有N个点，即k=0, 1, …, N-1， 故用式（3-5）计算得到的只是X(k) 的前一半的结果，要用X1 (k)，X2 (k)来表达全部的X(k)值，还必须 应用系数的周期性， 即
-第3快速疼里叶变换一 k- k N/2 N/2 这样可得到 tk X|2+k=∑x()W2=∑x(W2=X(k) 0 (3-8) 同理可得 X2|+k|=X2(k) 3-9) 式(3-8)、式(3-9)说明了后半部分k值(M2<kN-1)所对应 的X1(k),X2(k)分别等于前半部分k值(0≤kM2-1)所对应的 x1(k),X2(k)
第3章 快速傅里叶变换 rk N N r k WN W / 2 2 / 2 = + 这样可得到 ( ) ( ) ( ) 2 / 2 1 1 2 0 1 2 / 2 1 2 0 1 1 k x r W x r W X k N X r k N N r k N r N N r = = = + − = + − = （3-8） 同理可得 ( ) 2 2 2 k X k N X = + （3-9） 式（3-8）、式（3-9）说明了后半部分k值（N/2≤k≤N-1）所对应 的X1 (k)，Ｘ2 (k)分别等于前半部分k值（0≤k≤N/2-1）所对应的 X1 (k)，X2 (k)
-第5快速傅里叶度换 再考虑到W的以下性质 N +k w/2wk k (3-10) 这样,把式(3-8)、式(3-9)、式(3-10)代入式(3-5),就 可将X(k)表达为前后两部分: X(k)=X1(k)+WX2(k)k=01….M 1(3-11) N H×N)=H1k++形2x21k+ N (3-12 =X1(k)-W2(k)k=0
第3章 快速傅里叶变换 再考虑到Wk N 的以下性质: k N k N N N k N WN =W W = −W + 2 / 2 这样，把式（3-8）、式（3-9）、式（3-10）代入式（3-5），就 可将X(k)表达为前后两部分： 1 2 ( ) ( ) ( ) 0,1, , = 1 + 2 = − N X k X k W X k k k N ( ) ( ) 2 2 2 1 2 2 2 1 X k W X k N W X k N X k N X k k N N k N = − + + = + + + 1 2 = 0,1, , − N k （3-10） （3-11） （3-12）
-第5快速傅里叶度换 x1(k) X, (k)+WN X,(k) Wi k X,(k) -WNX(k) 图3-1时间抽取法蝶形运算流图符号
第3章 快速傅里叶变换 图 3-1 时间抽取法蝶形运算流图符号 X2 (k) X1 (k) k WN － 1 X1 (k)＋ k WN X2 (k) X1 (k)－ k WN X2 (k)