第四章快速傅里叶变换
第四章 快速傅里叶变换
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
基4-DIF FFT算法N/4-1NN3N2WowknX(4k)=x(n)+x(n+) +x(n++N12N/4441=0N/4-1NN3NV"WhNX(4k+1)=x(n)- jix(n+xn-ix(n-NN/4424入n=00<k<2NN3N4y2nw.knX(4k+2) =x(n)-NN/4442n=0N/4-1N3NNWk3mZX(4k+3)=Mx(n)+ jx(n +x(njx(nNN/4244n=0woNN3NWoxo(n)xo(n)=x(n)+x(x(n)VN244NN3NW2nWnx,(n)=x(n)-Nnix(nN-41244x(n+x(n)NN3NW2nx(n)=x(n)-x(n+x(n-+xin+N442W"M-2NN3Nx(nW3n一x,(n)x(n)=x(n)+ jx(n+xn+ix(nN244W3n蝶形运算：×一3次3NNx(n+x(n)+一2次4
基4-DIF FFT算法 4 1 2 / 4 0 3 (4 2) ( ) ( ) ( ) ( ) 4 2 4 N n kn N N n N N N X k x n x n x n x n W W − = + = − + + + − + 4 1 3 / 4 0 3 (4 3) ( ) ( ) ( ) ( ) 4 2 4 N n kn N N n N N N X k x n jx n x n jx n W W − = + = + + − + − + 1 4 0 − N k 4 1 0 / 4 0 3 (4 ) ( ) ( ) ( ) ( ) 4 2 4 N kn N N n N N N X k x n x n x n x n W W − = = + + + + + + 4 1 / 4 0 3 (4 1) ( ) ( ) ( ) ( ) 4 2 4 N n kn N N n N N N X k x n jx n x n jx n W W − = + = − + − + + + 2 2 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 n N N N N x n x n x n x n x n W = − + + + − + 3 3 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 n N N N N x n x n jx n x n jx n W = + + − + − + 0 0 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 N N N N x n x n x n x n x n W = + + + + + + 1 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 n N N N N x n x n jx n x n jx n W = − + − + + + 蝶形运算：×— 3次 ＋— ?次 ( ) ( ) 4 ( ) 2 3 ( ) 4 x n N x n N x n N x n + + + 0 2 1 3 ( ) ( ) ( ) ( ) x n x n x n x n 1 1 1 1 1 1 1 -1 1 -1 -j -1 j j -1 -j 0 WN 2n WN n WN 3n WN
基4-DIF FFT算法NN3NWoxo(n)=x(n)+x(n+(n+N42N3Nx(n)=x(n)-x(n+x(ntnN24NN3NW2nx2(n)=x(n)-x(n++x(nnN424蝶形运算：×一3次3N+-8次NNW3nx(n)-x(n+x(n)=x(n+x(n+N4.24WNx(n)xo(n)xo(n)x(n)1woW"NN-41x(n+x(n+W2nx(n)4X2(n)NWNW"(1N-2x(n+x(n--x,(n)2x,(n)W3nN(1-1)W3n3N3NNx(n+x(n+x(n)4x(n)4
基4-DIF FFT算法 2 2 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 n N N N N x n x n x n x n x n W = − + + + − + 3 3 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 n N N N N x n x n x n j x n x n W = − + + + − + 0 0 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 N N N N x n x n x n x n x n W = + + + + + + 1 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 n N N N N x n x n x n j x n x n W = − + + + − + 蝶形运算：×— 3次 ＋— 8次 ( ) ( ) 4 ( ) 2 3 ( ) 4 x n N x n N x n N x n + + + 0 2 1 3 ( ) ( ) ( ) ( ) x n x n x n x n 0 WN 2n WN n WN 3n WN 1111 1 1− − j j 1 1 1 1 − − 1 1− − j j ( ) ( ) 4 ( ) 2 3 ( ) 4 x n N x n N x n N x n + + + 0 2 1 3 ( ) ( ) ( ) ( ) x n x n x n x n 1 1 1 1 1 1 1 -1 1 -1 -j -1 j j -1 -j 0 WN 2n WN n WN 3n WN
基4-DIF FFT算法3NNNWoxo(n)=x(n)+x(n+xn+x(ntN3NN244NN10g210g2UNN3N24 2Wnx(n)=3x(n)-x(n+x(n+xinN244N3NNW2nx(n)=x(n)+x(n4+x(n+x(n+蝶形运算：×—3次244+—8次N3NN(4个x)W3nx(n)=x(n)-x(nx(n-x(n+++-12N44woWoxo(n)Nx(n)x.(n)x(n)V2NW2nNNN-4x(n+x(n)x(n+4x(n)W"N-2-2x(n+Wnx(n)x(n-x(n)NW3nNW3n3N3NNx(n+x(n)x(n+X(n)44
基4-DIF FFT算法 ( ) ( ) 4 ( ) 2 3 ( ) 4 x n N x n N x n N x n + + + 0 2 1 3 ( ) ( ) ( ) ( ) x n x n x n x n -j 2 2 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 n N N N N x n x n x n x n x n W = + + − + + + 3 3 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 n N N N N x n x n x n j x n x n W = − + + + − + 0 0 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 N N N N x n x n x n x n x n W = + + + + + + 1 3 ( ) ( ) ( ) ( ) ( ) 2 4 4 n N N N N x n x n x n j x n x n W = − + − + − + 0 WN n WN 2n WN 3n WN 蝶形运算：×— 3次 ＋— 8次 (4个x) ( ) ( ) 4 ( ) 2 3 ( ) 4 x n N x n N x n N x n + + + 0 2 1 3 ( ) ( ) ( ) ( ) x n x n x n x n 1 1 1 1 1 1 1 -1 1 -1 -j -1 j j -1 -j 0 WN 2n WN n WN 3n WN N N N N 2 2 log 4 2 3 log 2
r(o.n.)o X(0.n,)r(l.n,)0X(2.n。)r(2,n.0 x,(,n。)r(3."。o X,(3.n。)-i-11图4-21一个基-4FFT基本运算的信号流图
基-4按时间抽取OrFFT算法流图？按频率
基-4 按时间 Or 抽取 FFT算法流图？ 按频率