北京理工大学数字信号处理2-基2-fft

数字信号处理第三章快速傅里叶变换FFT班级：05941401姓名：张xx学号：112014xxxx一、实验要求针对典型序列，从基2-FFT、基4-FFT和分裂基FFT算法中选一种，用C语言编程实现，并与MATLAB中自带的FFT函数的计算结果进行比较。二、实验内容1.C语言实现基2-FFT程序代码：#includestdio.h#includecomplex#includemath.htypedefstd::complexdoublecomplex;intN=16,N1=4;//N为总输入数，N1为总级数intr=0;complexa[64],b[64];//a[64]为每一级蝶形算法输入，b[64]为每一级蝶形算法的输出constdoublepi=3.141592653589793;intreverse_order(intN,inta)//倒序算法N为总级数（带入N1）{intc[20],res=0;for(inti=N-1;i=0;i--){if(a%2==0)c[i]=0;elsec[i]=1;a=a/2;res+=c[i]*pow(2,i);}returnres;}voidbutterfly(intlayer){complexw;intc1=pow(2,N1-layer);//本级包含基本蝶形算法的次数intc2=pow(2,layer-1);//本级蝶形算法包含的次数intc3=pow(2,layer);for(inti=0;ic1;i++){for(intj=0;jc2;j++){r=j*pow(2,N1-layer);w=complex(cos(2*pi*r/N),-sin(2*pi*r/N));b[j+i*c3]=a[j+i*c3]+a[j+c2+i*c3]*w;b[j+c2+i*c3]=a[j+i*c3]-a[j+c2+i*c3]*w;}}for(intk=0;kN;k++){a[k]=b[k];}}voidfft(){inti;for(i=0;iN1;i++){butterfly(i+1);}}intmain(){inti;doublenum1[64]={1,2,3,4,5,6,7,8,0,0,0,0,0,0,0,0};//输入doublenum2[64];doubleres;for(i=0;iN;i++)//倒序{num2[i]=num1[reverse_order(N1,i)];}for(i=0;iN;i++)//初始化{a[i]=complex(num2[i],0);}fft();for(i=0;iN;i++){res=sqrt(a[i].real()*a[i].real()+a[i].imag()*a[i].imag());printf(%f\t,res);}2.MATLAB中的FFT算法实现x=[1,2,3,4,5,6,7,8];y=fft(x,16);y3.运行结果（1）示例一16位序列[1,0,0...]，补零至16位①C运行结果输入数=16，级数=4②MATLAB运行结果x=[1];y=fft(x,16);yy=1111111111111111（2）示例二16位序列[1,2,3,4,5,6,7,8,0,0...]，补零至16位①C运行结果输入数=16，级数=4}②MATLAB运行结果x=[1,2,3,4,5,6,7,8];y=fft(x,16);yy=1至5列36.0000+0.0000i-8.1371-25.1367i-4.0000+9.6569i3.3801-7.4830i-4.0000+4.0000i6至10列4.2768-3.3409i-4.0000+1.6569i4.4802-0.9946i-4.0000+0.0000i4.4802+0.9946i11至15列-4.0000-1.6569i4.2768+3.3409i-4.0000-4.0000i3.3801+7.4830i-4.0000-9.6569i16列-8.1371+25.1367i（3）示例三8位序列[1,2,3,4,5,6,7,8]①C运行结果输入数=8，级数=4②MATLAB运行结果x=[1,2,3,4,5,6,7,8];y=fft(x);yy=1至5列36.0000+0.0000i-4.0000+9.6569i-4.0000+4.0000i-4.0000+1.6569i-4.0000+0.0000i6至8列-4.0000-1.6569i-4.0000-4.0000i-4.0000-9.6569i（4）示例四[3,5,1,7,8]补零至16位①C运行结果输入数=16，级数=4②MATLAB运行结果x=[3,5,1,7,8];y=fft(x,16);yy=1至5列24.0000+0.0000i11.0053-17.0877i-6.4142-9.4853i-2.2608+5.3523i10.0000+2.0000i6至10列6.8466-9.2335i-3.5858-7.4853i-3.5911+0.3265i0.0000+0.0000i-3.5911-0.3265i11至15列-3.5858+7.4853i6.8466+9.2335i10.0000-2.0000i-2.2608-5.3523i-6.4142+9.4853i16列11.0053+17.0877i三、实验结果1.对于快速傅里叶变换后得实数的序列，C与MATLAB程序中的fft函数所得结果相同。2.对于快速傅里叶变换后结果中有虚数的序列，C中只能得出模的值，MATLAB中可以得出具体实部和虚部的值。四、问题1.当输入数为8，总级数依旧为4，c得出的结果与MATLAB得出的结果不同，是MATLAB结果的二分之一。2.只能计算离散序列。