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

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，

3、对应于N个输入样值，有N个频域样值与之对应。v以基2时间按抽选法为例，分解递推公式为：1212( )( )( )0,12()( )( )2kNkNX kX kW XkNkNX kX kW XkX1(K)和X2（K）分别对应时间序列 x(n)的的偶、奇序列 N/2点长的DFT，以此方法分解下去，得到两点长N/2为组的离散时间分组结果。在一次由两点DFT复合产生4、8、16到N点的最后结果。运算量由N*N次降为 次乘法。 2log2NN实验数据与结论v令N为不同长度的序列时，DFT和FFT的耗时比较：vN=512点时： dft_cost_time =0.3750s fft_cost_time =0

4、.0150svN=1024点时： dft_cost_time =2.9220s fft_cost_time =0.1250svN=2048点时： dft_cost_time =23.5000s； fft_cost_time =0.4690svN=4096点时： dft_cost_time =305.9530s fft_cost_time =103.9220sv有上面数据表明，同样长度的信号，DFT耗时要比FFT耗时要少，表明FFT算法的有效性。圆周卷积代替线性卷积的原理v线性卷积的长度及运算量 ；v用FFT算的步骤；v比较两者乘法运算量 ； 线性卷积的长度及运算量v 设一离散线性移不变系统的冲

5、激响应为,其输入信号为.其输出为.并且的长度为L点,的长度为M点,则： 10( )( )( )( ) ()Lmy nx nh nx m h nm10( )( )( )( ) ()Lmy nx nh nx m h nm10( )( )( )( ) ()Lmy nx nh nx m h nm1hnhMn 则y(n)的长度为L+M-1。 线性卷积的乘法运算量为LM次，又由于FIR滤波 器 h(n)的特性是对称序列即 因而，乘法运算次数减半，即为LM/2。 用FFT算的步骤 1.( ), ( )1 ;x n h nNML将补零点，至少为点2 .()()HkF F Thn求；3.( )( )X kFFT

6、x n求；1.( ), ( )1 ;x n h nNML将补零点，至少为点4.()()()YkXk Hk求；5.( )( )y nIFFT Y k求。流程图( )x n( )h n( )X kIFFTFFTFFT( )Xk( )H k( )( )( )y nx n hn( )x n( )X k1.( )( )H kFFT h n求；2.( )( )X kFFT x n求；3.( )( )( )Y kX k H k求；4.( )( )y nIFFT Y k求。2log2NNN2log2NN2log2NN23log2NNN总运算量：次乘法以上各步运算量统计： 比较两者乘法运算量比较两者乘法运算量2

7、32(1log )2dmNFmLMKmN当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.0460s fft_convolution_time =0sv计算结果如

8、下所示40914092409340944095409640974098-0.2-0.100.10.20.30.40.50.60.7fft method circle convolutionN=4096点时圆周卷积的结果4092409340944095409640970.40.50.60.70.80.9direct convolution result两个长度为N/2=4096/2=2048点的序列直接线性卷积v（2）两个长度为N/2=8000/2=4000点的序列直接线性卷积与N点的圆周卷积，两过程的计算时间与计算结果比较v计算时间比较：direct_convolution_time =0.1

9、560 fft_convolution_time =0.0160v计算结果如下所示：7993799479957996799779987999800000.20.40.60.811.2direct convolution result两个长度为N/2=8000/2=4000点的序列直接线性卷积7994799579967997799879998000800100.20.40.60.811.21.4fft method circle convolutionN=8000点时圆周卷积的结果v（3）两个长度为N/2=10000/2=5000点的序列直接线性卷积与N点的圆周卷积，两过程的计算时间与计算结果比较v计算时间比较： direct_convolution_time =0.2500s fft_convolution_time =0.0470s99909991999299939994999599969997999899991000000.511.52direct convolution result两个长度为N/2=10000/2=5000点的序列直接线性卷积计算结果比较N=10000点时：99919992999399949995999699979998999910000-0.500.511.522.5fft method circle c