《FFT与DFT计算时间的比较及圆周卷积代替线性卷积的有效...》由会员分享,可在线阅读,更多相关《FFT与DFT计算时间的比较及圆周卷积代替线性卷积的有效...(23页珍藏版)》请在金锄头文库上搜索。
1、实验二 FFT与DFT计算时间的比 较及圆周卷积代替线性卷积的有 效性实验一 实验目的 二 实验内容及要求 三 预做实验一 实验目的v1:掌握FFT基2时间(或基2频率)抽选法 ,理解其提高减少乘法运算次数提高运算 速度的原理。v2:掌握FFT圆周卷积实现线性卷积的原理二 实验内容及要求v1.对N=2048或4096点的离散时间信号 x(n),试用Matlab语言编程分别以DFT 和FFT计算N个频率样值X(k), 比较两者 所用时间的大小。v 2.对N/2点长的x(n)和N/2点长的h(n), 试用Matlab语言编程实现以圆周卷积代 替线性卷积,并比较圆周卷积法和直接 计算线性卷积两者的运
2、算速度。三预做实验v1.FFT与DFT计算时间的比较 (1)FFT提高运算速度的原理(2)实验数据与结论 v2.圆周卷积代替线性卷积的有效性实验(1)圆周卷积代替线性卷积的原理(2)实验数据和结论 FFT提高运算速度的原理v FFT算法将长序列的DFT分解为短序列的 DFT。N点的DFT先分解为2个N/2点的 DFT,每个N/2点的DFT又分解为N/4点的 DFT,等等。最小变换的点数即所谓的“基 数”。因此,基数为2的FFT算法的最小变 换(或称蝶型)是2点的DFT。一般地,对 N点FFT,对应于N个输入样值,有N个频 域样值与之对应。v以基2时间按抽选法为例,分解递推公式为:X1(K)和X
3、2(K)分别对应时间序列 x(n)的的偶、奇序 列 N/2点长的DFT,以此方法分解下去,得到两点长 N/2为组的离散时间分组结果。在一次由两点DFT复合 产生4、8、16到N点的最后结果。运算量由N*N次 降为 次乘法。 实验数据与结论v令N为不同长度的序列时,DFT和FFT的耗时比 较:vN=512点时: dft_cost_time =0.3750s fft_cost_time =0.0150svN=1024点时: dft_cost_time =2.9220s fft_cost_time =0.1250svN=2048点时: dft_cost_time =23.5000s; fft_cos
4、t_time =0.4690svN=4096点时: dft_cost_time =305.9530s fft_cost_time =103.9220sv有上面数据表明,同样长度的信号,DFT耗时要 比FFT耗时要少,表明FFT算法的有效性。圆周卷积代替线性卷积的原理v线性卷积的长度及运算量 ;v用FFT算的步骤;v比较两者乘法运算量 ; 线性卷积的长度及运算量v 设一离散线性移不变系统的冲激响应为,其输入 信号为.其输出为.并且的长度为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)也表现不出来,此时可用重叠相加法和重 叠保留法,进行分段卷积,保障圆周卷积的优势 。实验数据和结论v(1)两个长度为N/2=4096/2=2048点的 序列直接线性卷积与N点的圆周卷积,两 过程的计算时间与计算结果比较v 计算时间比较:direct_convolution_time =0
6、.0460s fft_convolution_time =0sv计算结果如下所示N=4096点时圆周卷积的结果两个长度为N/2=4096/2=2048点的序列直接线性卷积v(2)两个长度为N/2=8000/2=4000点的 序列直接线性卷积与N点的圆周卷积,两 过程的计算时间与计算结果比较v计算时间比较:direct_convolution_time =0.1560 fft_convolution_time =0.0160v计算结果如下所示:两个长度为N/2=8000/2=4000点的序列直接线性卷积N=8000点时圆周卷积的结果v(3)两个长度为N/2=10000/2=5000点的 序列直接线性卷积与N点的圆周卷积,两 过程的计算时间与计算结果比较v计算时间比较:direct_convolution_time =0.2500s fft_convolution_time =0.0470s两个长度为N/2=10000/2=5000点的序列直接线性卷积计算结果比较N=10000点时:N=10000点时圆周卷积的结果数据分析与结论通过以上三组数据比较,证实了圆周 卷积代替线性卷积时所需计算时间要少 ;且N点圆周卷积比两个N/2点的序列 线性卷积的结果多最后一项,而圆周卷 积最后一项为零,通过比较其余各项卷 积结果,得知均一一对应相等,因此, 用圆周卷积代替直接计算线性卷积是有 效的。