实验二-快速傅里叶变换FFT与DFT计算时间.ppt

《实验二-快速傅里叶变换FFT与DFT计算时间.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二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语言编程实现以圆周卷积代替线性卷积，并比较圆周卷积法和直接计算线性卷积两者的运算

2、速度。三预做实验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时间按抽选法为例，分解递推公式为：

3、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.3750sfft_cost_time=0.0150sN=1024点时：dft_cost_time=2.9220sfft_cost_time=0.1250sN=2048点时：dft_cost_time=23.5000s

4、；fft_cost_time=0.4690sN=4096点时：dft_cost_time=305.9530sfft_cost_time=103.9220s有上面数据表明，同样长度的信号，DFT耗时要比FFT耗时要少，表明FFT算法的有效性。圆周卷积代替线性卷积的原理线性卷积的长度及运算量；用FFT算的步骤；比较两者乘法运算量；线性卷积的长度及运算量设一离散线性移不变系统的冲激响应为,其输入信号为.其输出为.并且的长度为L点,的长度为M点,则：则y(n)的长度为L+M-1。线性卷积的乘法运算量为LM次，又由于FIR滤波器h(n)的特性是对称序列即因而

5、，乘法运算次数减半，即为LM/2。用FFT算的步骤流程图IFFTFFTFFT以上各步运算量统计：比较两者乘法运算量当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

6、_convolution_time=0.0460sfft_convolution_time=0s计算结果如下所示N=4096点时圆周卷积的结果两个长度为N/2=4096/2=2048点的序列直接线性卷积（2）两个长度为N/2=8000/2=4000点的序列直接线性卷积与N点的圆周卷积，两过程的计算时间与计算结果比较计算时间比较：direct_convolution_time=0.1560fft_convolution_time=0.0160计算结果如下所示：两个长度为N/2=8000/2=4000点的序列直接线性卷积N=8000点时圆周卷积的结果（

7、3）两个长度为N/2=10000/2=5000点的序列直接线性卷积与N点的圆周卷积，两过程的计算时间与计算结果比较计算时间比较：direct_convolution_time=0.2500sfft_convolution_time=0.0470s两个长度为N/2=10000/2=5000点的序列直接线性卷积计算结果比较N=10000点时：N=10000点时圆周卷积的结果数据分析与结论通过以上三组数据比较，证实了圆周卷积代替线性卷积时所需计算时间要少；且N点圆周卷积比两个N/2点的序列线性卷积的结果多最后一项，而圆周卷积最后一项为零，通过比较其余各项

8、卷积结果，得知均一一对应相等，因此，用圆周卷积代替直接计算线性卷积是有效的。