第四章快速傅里叶变换
第四章 快速傅里叶变换
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)一、算法原理V x(n),0≤n≤N-1.N=2若N≠2'，可通过补零达到↓FFT→基-2FFT/即N为2的整数幂的FFT由FFT的定义：X(k) = x(n)wkmk=0,1,...,N-1(4-4)n=0NDFTx(n)2N-x(n)？NDFTDFTx2(n)2
一、算法原理 x(n), 0 n N 1, 2 (若 2 ，可通过补零达到) N N - 2 / 2 FFT FFT 基 FFT 即N为 的整数幂的 01 1 (4 - 4) : 1 0 N n kn N X k x n W k , , ,N FFT 由 的定义 DFT N x n ( ) x n DFT N ( ) 2 1 x n DFT N ( ) 2 2 ? §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)设序列点数 N=2L，L 为整数（若不满足，则补零)将序列α(n)按n的奇偶分成两组：c(2r) = a,(r)r(2r +1)= c,(r): r =0,1..,-7：01234567(nr(n)01234567(n
将序列 x(n) 按 n 的奇偶分成两组： 设序列点数 N=2L , L 为整数 (若不满足，则补零) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 2 x n( ) 1 x n( ) x n( ) §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N令 x(n)=x(2r)r=0.12Nx2(n)= x(2r +1)-1(4-5)r= 0.12代入(4-4)式NNX(k)=Zx(2r)W2* +Zx(2r+1)Wr+)kr=0r=0N-1N-I≥x(n)W+w≥ (n)w)式中：X(k),0≤k≤N-12n=02r=0NX,(k) = DFT[x(n)],0 ≤k≤2(4-7)= X(k)+WkX,(k)NX,(k) = DFT[x2(n)],0 ≤ k≤2
代入(4-4)式 1 1 2 2 2 (2 1) 0 0 ( ) (2 ) (2 1) N N rk r k N N r r X k x r W x r W 1 1 2 2 1 2 0 0 2 2 ( ) N N rk k rk N N N n r x n W W x n W 1 2 ( ) (2 ) 01 1 N 令 x n x r r , ,., △ 1 (4-5) 2 ( ) (2 1) 01 2 N x n x r r , ,., △ ( ) ( ) 1 2 X k W X k k N (4 - 7) 1 2 ( ) [ ( )],0 1 2 ( ) [ ( )],0 2 2 1 1 N X k DFT x n k N X k DFT x n k 式中： §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法) X(k),0 k N 1
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N可见：DFT2N-DFTN-DFT?NDFT2由(4-7)式X,(k)N*X(k),0≤k≤2X,(k)N0<k<-12N问题：≤k≤N-时,X(k)=?2
可见： N DFT DFT N 2 DFT N 2 N DFT ? 由(4-7)式 1 2 0 N k ( ) 1 X k X(k), ( ) 2 X k 1 2 0 N k 问题： 1时， ( ) ？ 2 k N X k N §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N-+k)利用W的周期性，W2=WN1222N.-)N-+k）N2X(k+=)Zx(r)W))=212r=0N-IZx(r)wrkN-2r=0N(4-10)0≤k≤= X,(k),2NN同理有，X,(k+-0≤k≤ = X2(k),(4-11)22[可见X,(k)和X,(k)的后半部分完全重复了各自的前半部分]代入(4-7)式，有:
rk WN 2 利用 的周期性， ) 2 ( 2 2 k N r N rk WN W 1 2 0 ) 2 ( 2 1 1 ) ( ) 2 ( N r k N r WN x r N X k 1 2 0 2 1 ( ) N r rk WN x r [ ( ) ( ) ] 可见X1 k 和X2 k 的后半部分完全重复了各自的前半部分 代入(4-7)式，有: 1 2 1 ( ), 0 N X k k (4-10) 同理有， 1 2 ) ( ), 0 2 (2 2 N X k k N X k (4-11) §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)N= X,(k)+W?"X(k)+kNN1:W =ejn =-10≤k≤2N0≤k≤1= X,(k)-WkX2(k)2归纳起来有Nk = 0,1(4-13)X(k) = X,(k)+WkX,(k)2N-+k) = X,(k)-WkX,(k)k =0,1(4-14)2一NDFT可见，2N-DFTN-DFTNDFT2
1 2 1 0 2 N W e k j N N 归纳起来有 1 2 1 2 ( ) ( ) ( ) 0,1,., 1 (4-13) 2 ( ) ( ) ( ) 0,1,., 1 (4-14) 2 2 k N k N N X k X k W X k k N N X k X k W X k k 1 2 1 ( ) 2 ( ) 0 N X k W X k k k N 可见， N DFT DFT N 2 DFT N 2 N DFT §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法) 2 1 2 ( ) ( ) ( ) 2 N k N N X k X k W X k
S 4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)上述运算可用下列蝶形信号流图表示X,(k)X(k)= X,(k)+WkX2(k)WkNX,(k)X(-+k)= X,(k)-WkX2(k土运算符图4-1蝶形运算流图符号
上述运算可用下列蝶形信号流图表示: ( ) 1 X k 2 X k( ) ( ) ( ) ( ) 1 2 X k X k W X k k N ) ( ) ( ) 2 ( 1 2 k X k W X k N X k N k WN 运算符 图 4-1 蝶形运算流图符号 §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
S 4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)例：N=8NWk,k=012x (0) = x(0)X(0)x,(1) = x(2)N/2-X(1)x(n)DFTx(2) = x(4)X(2)x (3) = x(6)X(3)Wx2(0) = x(1)X(4)W!N/2-x2(1) = x(3)X(5)W?x(n)DFTx2(2) = x(5)X(6)Wx2(3) = x(7)X(7)
例：N=8 1 1 1 1 1 (0) (0) (1) (2) ( ) (2) (4) (3) (6) x x x x x n x x x x 2 2 2 2 2 (0) (1) (1) (3) ( ) (2) (5) (3) (7) x x x x x n x x x x (3) (2) (1) (0) X X X X (7) (6) (5) (4) X X X X N/2- DFT N/2- DFT 3 2 1 0 N N N N W W W W 1 2 , 0,1,., N W k k N §4-3 按时间抽取(DIT)的FFT算法 (Cooley-Tukey算法)
X,[0]2[0]X[0]X,[1]2[2]X[1]4点DFTX,[2]24]X[2]X,[3]a(6]X[3]X,[0] W.2[1]X[4]X,[1] W,]2[3] X[5]4点DFTX,[2] W?z[5] X[6]X,[3] W3a[7]X[7]X[K] = X,[K] + WX,[K], k = 0,1,2,3X[k + 8 / 2] = X,[K] - WX,[K], k = 0,1, 2,3**8点基2时间抽取FFT算法流图
4 点DFT 4 点DFT x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] X1 [0] 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] - 1 - 1 - 1 - 1 0 W8 1 W82 W83 W8 1 8 2 1 8 2 [ ] [ ] [ ], 0,1,2, 3 [ 8 / 2] [ ] [ ], 0,1,2, 3 kk X k X k W X k k X k X k W X k k ** 8点基 2时间抽取FFT算法流图