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

基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算法流图？ 按频率