单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 快速傅里叶变换,(Fast Fourier TransformFFT),4.1,引言,4.2,基,2FFT,算法,4.1,引言,计算,X,(,k,),的一个值需要,N,次复数乘法和,(N-1),次复数加法，计算,X,(,k,),的所有,N,个值需要,NN,次复数乘法和,N(N-1),次复数加法。,一、,时域抽取法基,2FFT,原理,4.2,基,2FFT,算法,将长度为,N,的序列,x,(,n,),按奇偶分解为两个,N/2,点的子序列,则,x,(,n,),的,DFT,为,X,(,k,),按前,N/2,点和后,N/2,点分开表示,图,4.2.2 N,点,DFT,一次时域抽取分解运算流图（,N=8,）,图,4.2.2 N,点,DFT,一次时域抽取分解运算流图（,N=8,）,图,4.2.2,包括两个,N/2,点,DFT,和,N/2,个蝶形，每个,N/2,点,DFT,需要,(N/2)(N/2),次复数乘法和,(N/2-1)(N/2),次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为：,总的复数加法次数为：,图,4.2.3 N,点,DFT,二次时域抽取分解运算流图（,N=8,）,图,4.2.4 N,点,FFT,运算流图（,N=8,）,分组,方法,原始数据序列,N/2,分组,N/4,分组,(,最终分组结果,),计算,结果,按,奇,偶,分,组,x(0),x,1,(0),x(0),x,3,(0),x(0),X(0),x(1),x,1,(1),x(2),x,3,(1),x(4),X(1),x(2),x,1,(2),x(4),x,4,(0),x(2),X(2),x(3),x,1,(3),x(6),x,4,(1),x(6),X(3),x(4),x,2,(0),x(1),x,5,(0),x(1),X(4),x(5),x,2,(1),x(3),x,5,(1),x(5),X(5),x(6),x,2,(2),x(5),x,6,(0),x(3),X(6),x(7),x,2,(3),x(7),x,6,(1),x(7),X(7),离散数据点按奇偶分组过程,【,例,】,假设时域连续信号,x(t,)=x1(t)+x2(t)+x3(t),，其中,x1(t)=3sin(30,t),，,x2(t)=2sin(40,t),，,x3(t)=sin(60,t),。,如果用,FFT,对,x(t,),进行频谱分析，问采样频率,Fs,和采样点数,N,应如何选择，才能精确求出,x1(t),、,x2(t),、,x3(t),的频率；,按照你选择的,Fs,、,N,对,x(t,),等间隔采样，得到,x,(,n,),，用,FFT,进行频普分析求出各频率分量的幅值，计为,X(k,),，画出幅度谱，并说明,x1(t),、,x2(t),、,x3(t),的信号频率出现在,k,的什么位置。,