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

N=16基-4按频率抽取FFT流图X,.k)X()X(kt(n)i(ngn0X,(0.0)=X(0)1(0)=1(0.0)X,(0.2)=X(8)(1)=r(0.1)0X(0.1)=X(4)r(2)-1(0.2)X,(0.3)=X(12)1(3)=1(0.3)n0X,(2.0)=X(2)r(4)=r(1.0)W2.0X,(2.2)-X(10)r(5)=r(1.1)-0X,(2.1)-X(6)r(6)=r(1.2)W0X.(2.3)=X(14)r(7)=r(1.3)-0 X,(1,0)-X(1)r(8)=r(2,0)0X,(1.2)=X(9)2(9)=r(2.1)10X,(1.1)=-X(5)1(10)=1(2.2)W-0X,(1-3)=X(13)1(11)=r(2.3)-L人0XK3.0)-X(3)r(12)=r(3.0)W-0X,(3.2)=X(11)r(13)=r(3.1)20X.(3,1)=X(7)1(14)=r(3.2)nW-0X(33)=X(15)z(15)=r(3,3)按时间抽选基-4FFT流图图4-22

N=16 基-4 按频率抽取FFT流图

回忆:N=12组合数基-3x4FFT流图x(ng.o)WO第一级第二级x(0)=x(0.0)PX(0)Wox(1)=x(0,1)OX(3)W2x(2)=x(0.2)o.X(6)WOx(3)x(0.3)X(9)x(4)=x(1.0)1WS15-X(1.1)0X4)WOx(6)x(1.2)0.7)hox(7)-x(1.3)0.(10)WOx(8)=x(2,0)X(2)x(9)=x(2,1)0X(5)Wex(10)=x(2,2)0.1(8)weX(11FX(2.3)X1)woxo(n)x(n)W."NIXn+x(n)4图P4-5WNx(n+x(n)2W33Nx,(n)x(n+4

回忆：N=12 组合数 基-3x4 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 1 1 1 1 1 1 1 -1 1 -1 -j -1 j j -1 -j 0 WN 2n WN n WN 3n WN