《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-6 分裂基FFT算法 §4-7 实序列的FFT算法

第四章快速傅里叶变换

第四章 快速傅里叶变换

S4-6分裂基FFT算法一、背景对更快速算法的需求N基-2FFT~10g221984年,杜梅尔（P.Douhamel）霍尔曼(H.Hollman)-基-2 FFTNN分裂基FFT~l0g23基-4 FFT

• 3 / 30 §4-6 分裂基FFT算法 一、背景 对更快速算法的需求 N N FFT 2 log 2 基− 2 ~ 1984年，杜梅尔（P.Douhamel） 霍尔曼（H.Hollman） 基-2 FFT 基-4 FFT N N FFT 2 log 3 分裂基 ~

S 4-6分裂基FFT算法基4-DIFFFT算法V x(n),0≤n≤N-1,N=2vDFT[x(n)一→更快的FFT算法设 N=Pg,P=N/4, q=4令 n=Pn,+no= N/4 n,+no ;0<n ≤3,0≤ n^≤(N/4)-1k=4k,+ko;0≤k;≤(N/4)-1,0≤ko≤3N-1X(k)=Zx(n)Whn=0N/41_3NK4n+no)4MMOWx(n+no)Ano=0 n,=0N/4-1NN3NW3kZ)W2kWkno+x(n。 +)W4x(n.)WN2Ano=0

§4-6 分裂基FFT算法 4 / 30   x(n), 0  n  N −1,N = 2 DFT[x(n)] → 更快的FFT算法 设 N=Pq, P=N/4, q=4 令 n=Pn1+n0 = N/4 n1+n0 ; 0≤n1 ≤3, 0≤ n0 ≤(N/4)-1 k=4k1+k0 ; 0≤k1 ≤(N/4)-1 , 0≤ k0 ≤ 3 1 0 0 1 0 0 1 0 4 1 3 ( ) 4 1 0 0 0 4 1 0 2 3 0 4 0 4 0 4 0 4 0 ( ) ( ) ( ) 4 3 ( ) ( ) ( ) ( ) 4 2 4 N kn N n N N k n n N n n N k k k kn N n X k x n W N x n n W N N N x n W x n W x n W x n W W − = − + = = − = = = +   = + + + + + +         基4-DIF FFT算法

X(k)= X(4k +k.)k。= 0.1,2,3(k →k,no →n)N/41NN3N)W(4k;+ko) + x(no3(4k,+ko))W2(4k+ko) + x(ng +W(4k +ko)noZx(no)+x(no +N244no=0N/4-13NNN4m[We]W3k0W(4kj+ko)no2koWKNx(n)+x(no ++ x(noV+x(no444A2no=0Re[We在k。=0,1,2,3时，用k表示k，n表示nN/4-1NN3N4kmNWX(4k)=x(n) +A2n=0N/4-NN3N4kn+nX(4k+1)= ZWx(n)-(n+(n+424n=0N/4-1NN3NW4hn+2nZX(4k +2) =x(n)-x(n+XN244n=0N/4-NN3NW4kn+3nZX(4k +3) =x(n)+ jx(n+x(n-N424n=0N0≤k≤1(4-43)基4-DIF4

4 1 4 2 0 3 (4 2) ( ) ( ) ( ) ( ) 4 2 4 N kn n N n N N N X k x n x n x n x n W − + =   + = − + + + − +      4 1 4 3 0 3 (4 3) ( ) ( ) ( ) ( ) 4 2 4 N kn n N n N N N X k x n jx n x n jx n W − + =   + = + + − + − +      1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 4 1 (4 ) 2(4 ) 3(4 ) (4 ) 0 0 4 0 4 0 4 0 4 1 2 3 (4 ) 0 0 4 0 4 0 4 0 ( ) (4 ) 3 ( ) ( ) ( ) ( ) 4 2 4 3 ( ) ( ) ( ) ( ) 4 2 4 N k k k k k k k k n N n N k k k k k n N n X k X k k N N N x n x n W x n W x n W W N N N x n x n W x n W x n W W − + + + + = − + = = +   = + + + + + +       = + + + + + +       0,1,2,3 ( , ) k0 = k1 → k n0 → n 4-DIF  基 1 (4-43) 4 0   − N k 4 1 4 0 3 (4 ) ( ) ( ) ( ) ( ) 4 2 4 N kn N n N N N X k x n x n x n x n W − =   = + + + + + +      4 1 4 0 3 (4 1) ( ) ( ) ( ) ( ) 4 2 4 N kn n N n N N N X k x n jx n x n jx n W − + =   + = − + − + + +      0 1 0 在k k k n n = 0,1,2,3时，用 表示 ， 表示 14 W16 15 W16 Re[ ] 16 Wm 16 Im[ ] Wm 0 W16 1 W16 2 W16 3 4 W16 W16 5 W16 6 W16 7 W16 8 W16 9 W16 10 W16 11 W16 12 W16 13 W16 17 W16 1 W16 − 3 W8 18 W32

WieWiWi?WiawioWieW?WWi5Re[Wi]woWoW?Wiowi.WeWoW?WeWieWie参考P96图3-21

14 W16 15 W16 Re[ ] 16 Wm 16 Im[ ] Wm 0 W16 1 W16 2 W16 3 4 W16 W16 5 W16 6 W16 7 W16 8 W16 9 W16 10 W16 11 W16 12 W16 13 W16 17 W16 1 W16 − 3 W8 18 W32 参考P96 图3-21