FFT与DFT计算时间的比较及圆周卷积代替线性卷积的有效....ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,实验二,FFT,与,DFT,计算时间的比较及圆周卷积代替线性卷积的有效性实验,一 实验目的,二 实验内容及要求,三 预做实验,一 实验目的,1,：掌握,FFT,基,2,时间（或基,2,频率）抽选法，理解其提高减少乘法运算次数提高运算速度的原理。,2,：掌握,FFT,圆周卷积实现线性卷积的原理,二 实验内容及要求,1.,对,N=2048,或,4096,点的离散时间信号,x(n,),，试用,Matlab,语言编程分别以,DFT,和,FFT,计算,N,个频率样值,X(k,),比较两者所用时间的大小。,2.对,N/2,点长的,x(n,),和,N/2,点长的,h(n,),，试用,Matlab,语言编程实现以圆周卷积代替线性卷积，并比较圆周卷积法和直接计算线性卷积两者的运算速度。,三预做实验,1.FFT,与,DFT,计算时间的比较,（,1,）,FFT,提高运算速度的原理,（,2,）实验数据与结论,2.,圆周卷积代替线性卷积的有效性实验,（,1,）圆周卷积代替线性卷积的原理,（,2,）实验数据和结论,FFT,提高运算速度的原理,FFT,算法将长序列的,DFT,分解为短序列的,DFT,。,N,点的,DFT,先分解为,2,个,N/2,点的,DFT,，每个,N/2,点的,DFT,又分解为,N/4,点的,DFT,，等等。最小变换的点数即所谓的“基数”。因此，基数为,2,的,FFT,算法的最小变换（或称蝶型）是,2,点的,DFT,。一般地，对,N,点,FFT,，对应于,N,个输入样值，有,N,个频域样值与之对应。,以基,2,时间按抽选法为例，分解递推公式为：,X1(K),和,X2,（,K,）分别对应时间序列,x(n,),的的偶、奇序列,N/2,点长的,DFT,，以此方法分解下去，得到两点长,N/2,为组的离散时间分组结果。在一次由两点,DFT,复合产生,4,、,8,、,16,到,N,点的最后结果。运算量由,N*N,次降为 次乘法。,实验数据与结论,令,N,为不同长度的序列时，,DFT,和,FFT,的耗时比较：,N=512,点时：,dft_cost_time,=0.3750s,fft_cost_time,=0.0150s,N=1024,点时：,dft_cost_time,=2.9220s,fft_cost_time,=0.1250s,N=2048,点时：,dft_cost_time,=23.5000s,；,fft_cost_time,=0.4690s,N=4096,点时：,dft_cost_time,=305.9530s,fft_cost_time,=103.9220s,有上面数据表明，同样长度的信号，,DFT,耗时要比,FFT,耗时要少，表明,FFT,算法的有效性。,圆周卷积代替线性卷积的原理,线性卷积的长度及运算量；,用,FFT,算的步骤；,比较两者乘法运算量；,线性卷积的长度及运算量,设一离散线性移不变系统的冲激响应为,其输入信号为,.,其输出为,.,并且的长度为,L,点,的长度为,M,点,则：,则,y(n,),的长度为,L+M-1,。,线性卷积的乘法运算量为,LM,次，又由于,FIR,滤波,器,h(n,),的特性是对称序列即,因而，乘法运算次数减半，即为,LM/2,。,用,FFT,算的步骤,流程图,IFFT,FFT,FFT,以上各步运算量统计：,比较两者乘法运算量,当,h(n,),和,x(n,),长度相当时，若,M,较短时，,e.g.,为,8,，,16,，,32,时,圆周卷积的时间大于直接线性卷积的结果；当,M=64,时，两者的运算速度相当，当,M,超过,64,以后，,M,越长圆周卷积的速度越快。当输入序列,x(n,),也表现不出来，此时可用重叠相加法和重叠保留法，进行分段卷积，保障圆周卷积的优势。,实验数据和结论,（,1,）两个长度为,N/2=4096/2=2048,点的序列直接线性卷积与,N,点的圆周卷积，两过程的计算时间与计算结果比较,计算时间比较：,direct_convolution_time,=0.0460s,fft_convolution_time,=0s,计算结果如下所示,N=4096,点时圆周卷积的结果,两个长度为,N/2=4096/2=2048,点的序列直接线性卷积,（,2,）两个长度为,N/2=8000/2=4000,点的序列直接线性卷积与,N,点的圆周卷积，两过程的计算时间与计算结果比较,计算时间比较：,direct_convolution_time,=0.1560,fft_convolution_time,=0.0160,计算结果如下所示：,两个长度为,N/2=8000/2=4000,点的序列直接线性卷积,N=8000,点时圆周卷积的结果,（,3,）两个长度为,N/2=10000/2=5000,点的序列直接线性卷积与,N,点的圆周卷积，两过程的计算时间与计算结果比较,计算时间比较：,direct_convolution_time,=0.2500s,fft_convolution_time,=0.0470s,两个长度为,N/2=10000/2=5000,点的序列直接线性卷积,计算结果比较,N=10000,点时：,N=10000,点时圆周卷积的结果,数据分析与结论,通过以上三组数据比较，证实了圆周卷积代替线性卷积时所需计算时间要少；且,N,点圆周卷积比两个,N/2,点的序列线性卷积的结果多最后一项，而圆周卷积最后一项为零，通过比较其余各项卷积结果，得知均一一对应相等，因此，用圆周卷积代替直接计算线性卷积是有效的。,