第4章快速傅立叶变换(FFT) A 4+BC A-BC 图4.2.1蝶形运算符号
图4.2.1 蝶形运算符号 C A B A＋ BC A－ BC 第4章 快速傅立叶变换（FFT）
例如N=8时的DFT,可以分解为两个N/2=4点的 DFT.具体方法如下： (1)n为偶数时，x(0),x(2),x(4),x(6)5 记作： x(0)=x(0)2 x(1)=x(2), x(2)=x(4), x(3)=x(6); 进行N/2=4点的DFT,得X,(k) X,(k=之x,)w=2x(2r)w*k=0,12,3
例如 N=8 时的DFT,可以分解为两个N/2=4点的 DFT.具体方法如下: N / DFT X (k) 进 行 2 = 4点 的 ， 得 1 ( ) ( ) (2 ) 0,1,2,3 3 0 4 3 0 1 = 1 4 = = = = X k x r W x r W k r r k r r k ( ) ( ); ( ) ( ), ( ) ( ), ( ) ( ), 3 6 2 4 1 2 0 0 1 1 1 1 x x x x x x x x = = = = (1)n为偶数时, x(0), x(2), x(4), x(6); 记作:
(2)n为奇数时，分别记作： x2(0)=x(1), x21)=x(3), x2(2)=x(5), x2(3)=x(7); 进行N/2=4点的DFT,得X,(k) X,k)=2x,r)w=2x2r+10mk=0.12,3 r=0 X(k)=X(k)+WX2 (k) X(k+4)=X(k)-WwX2(k),k=0,1,2,3
(2) n为奇数时,分别记作: ( ) ( ); ( ) ( ), ( ) ( ), ( ) ( ), 3 7 2 5 1 3 0 1 2 2 2 2 x x x x x x x x = = = = ( ) ( ) (2 1) 0,1,2,3 3 0 4 3 0 2 = 2 4 = + = = = X k x r W x r W k r r k r r k N / DFT X (k) 进 行 2 = 4点 的 ， 得 2 ( 4) ( ) ( ), 0,1,2,3 ( ) ( ) ( ) 1 2 1 2 + = − = = + X k X k W X k k X k X k W X k k N k N
一个W点 X(k)=X(k)+WX2(k) 「的信号 流图 X(k+4)=X(k)-WX2(k),k=0,1,2,3 x,(0)=x(0) X(0) X(0) x(1)=x(2) X (1) X() x,(2)=x(4) 点DFT X(2 X(2) x13)=x(6) X(③ X(3) x2(0)=x(1)】 X0) W四 X(4) x2(1)=x(3)】 X:(1)WN X5) x2(2)=x(5) 点DFT X,(②)W x2(3)=x(7) X2(3) W足 X7)
(0) (0) x1 = x (1) (2) x1 = x (2) (4) x1 = x (3) (6) x1 = x 点DFT 2 N (3) (2) (1) (0) 1 1 1 1 X X X X (0) (1) x2 = x (1) (3) x2 = x (2) (5) x2 = x (3) (7) x2 = x 点DFT 2 N (3) (2) (1) (0) 2 2 2 2 X X X X X(0) X(4) 0 WN X(1) X(5) 1 WN X(2) X(6) 2 WN X(3) X(7) 3 WN -1 -1 -1 -1 一个N点DFT分解为两个N/2点DFT的信号 流图 ( 4) ( ) ( ), 0,1,2,3 ( ) ( ) ( ) 1 2 1 2 + = − = = + X k X k W X k k X k X k W X k k N k N
第4章快速傅立叶变换(FFT) X(0) x(0) X(O) N/2点 X(1) x(2) X1) X,(2) x(4) X2) DFT X(3) x(6)● X3) X(0) x(1)· X4) N/2点 x(3) X(1) X5) x(⑤) X(2) Wx X(6 DFT X,(3) x(7) X7)
图4.2.2 N点DFT的一次时域抽取分解图(N=8) N/ 2点 DFT W N 0 N/ 2点 DFT W N 1 W N 2 W N 3 x(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）