《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-3 按时间抽取（DIT）的FFT算法（Cooley-Tukey算法）

第四章快速傅里叶变换

第四章 快速傅里叶变换

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算法)