傅里叶转换理解.docx

一、彻底理解傅里叶变换快速傅里叶变换（FastFourierTransform)是离散傅里叶变换的一种快速算法，简称FFT，通过FFT可以将一个信号从时域变换到频域。模拟信号经过A/D转换变为数字信号的过程称为采样。为保证采样后信号的频谱形状不失真，采样频率必须大于信号中最高频率成分的2倍，这称之为采样定理。假设采样频率为fs，采样点数为N，那么FFT结果就是一个N点的复数，每一个点就对应着一个频率点，某一点n(n从1开始)表示的频率为：fn=(n-1)*fs/N。举例说明：用1kHz的采样频率采样128点，则FFT结果的128个数据即对应的频率点分别是0，1k/128，2k/128，3k/128，127k/128Hz。这个频率点的幅值为：该点复数的模值除以N/2（n=1时是直流分量，其幅值是该点的模值除以N）。二、傅里叶变换的C语言编程1、对于快速傅里叶变换FFT，第一个要解决的问题就是码位倒序。假设一个N点的输入序列，那么它的序号二进制数位数就是t=log2N.码位倒序要解决两个问题：将t位二进制数倒序；将倒序后的两个存储单元进行交换。将t=3位二进制数倒序将倒序后的两个存储单元进行交换如果输入序列的自然顺序号i用二进制数表示，例如若最大序号为15，即用4位就可表示n3n2n1n0，则其倒序后j对应的二进制数就是n0n1n2n3，那么怎样才能实现倒序呢？利用C语言的移位功能！程序如下，我不多说，看不懂者智商一定在180以下！复数类型定义及其运算#defineN64/64点#definelog2N6/log2N=6/*复数类型*/typedefstructfloatreal;floatimg;complex;complexxdataxN;/输入序列/*复数加法*/complexadd(complexa,complexb)complexc;c.real=a.real+b.real;c.img=a.img+b.img;returnc;/*复数减法*/complexsub(complexa,complexb)complexc;c.real=a.real-b.real;c.img=a.img-b.img;returnc;/*复数乘法*/complexmul(complexa,complexb)complexc;c.real=a.real*b.real-a.img*b.img;c.img=a.real*b.img+a.img*b.real;returnc;/*码位倒序函数*/voidReverse(void)unsignedinti,j,k;unsignedintt;complextemp;/临时交换变量for(i=0;iN;i+)/从第0个序号到第N-1个序号k=i;/当前第i个序号j=0;/存储倒序后的序号，先初始化为0for(t=0;tlog2N;t+)/共移位t次，其中log2N是事先宏定义算好的j=1;/k右移一位，次低位变为最低位if(ji)/如果倒序后大于原序数，就将两个存储单元进行交换（判断ji是为了防止重复交换）temp=x;x=xj;xj=temp;2、第二个要解决的问题就是蝶形运算第1级（第1列）每个蝶形的两节点“距离”为1，第2级每个蝶形的两节点“距离”为2，第3级每个蝶形的两节点“距离”为4，第4级每个蝶形的两节点“距离”为8。由此推得，第m级蝶形运算，每个蝶形的两节点“距离”L=2m-1。对于16点的FFT，第1级有16组蝶形，每组有1个蝶形；第2级有4组蝶形，每组有2个蝶形；第3级有2组蝶形，每组有4个蝶形；第4级有1组蝶形，每组有8个蝶形。由此可推出，对于N点的FFT，第m级有N/2L组蝶形，每组有L=2m-1个蝶形。旋转因子的确定以16点FFT为例，第m级第k个旋转因子为，其中k=02m-1-1，即第m级共有2m-1个旋转因子，根据旋转因子的可约性，所以第m级第k个旋转因子为，其中k=02m-1-1。为提高FFT的运算速度，我们可以事先建立一个旋转因子数组，然后通过查表法来实现。complexcodeWNN=/旋转因子数组/为节省CPU计算时间，旋转因子采用查表处理/根据实际FFT的点数N，该表数据需自行修改/以下结果通过Excel自动生成/WNk.real=cos(2*PI/N*k);/WNk.img=-sin(2*PI/N*k);1.00000,0.00000,0.99518,-0.09802,0.98079,-0.19509,0.95694,-0.29028,0.92388,-0.38268,0.88192,-0.47140,0.83147,-0.55557,0.77301,-0.63439,0.70711,-0.70711,0.63439,-0.77301,0.55557,-0.83147,0.47140,-0.88192,0.38268,-0.92388,0.29028,-0.95694,0.19509,-0.98079,0.09802,-0.99518,0.00000,-1.00000,-0.09802,-0.99518,-0.19509,-0.98079,-0.29028,-0.95694,-0.38268,-0.92388,-0.47140,-0.88192,-0.55557,-0.83147,-0.63439,-0.77301,-0.70711,-0.70711,-0.77301,-0.63439,-0.83147,-0.55557,-0.88192,-0.47140,-0.92388,-0.38268,-0.95694,-0.29028,-0.98079,-0.19509,-0.99518,-0.09802,-1.00000,0.00000,-0.99518,0.09802,-0.98079,0.19509,-0.95694,0.29028,-0.92388,0.38268,-0.88192,0.47140,-0.83147,0.55557,-0.77301,0.63439,-0.70711,0.70711,-0.63439,0.77301,-0.55557,0.83147,-0.47140,0.88192,-0.38268,0.92388,-0.29028,0.95694,-0.19509,0.98079,-0.09802,0.99518,0.00000,1.00000,0.09802,0.99518,0.19509,0.98079,0.29028,0.95694,0.38268,0.92388,0.47140,0.88192,0.55557,0.83147,0.63439,0.77301,0.70711,0.70711,0.77301,0.63439,0.83147,0.55557,0.88192,0.47140,0.92388,0.38268,0.95694,0.29028,0.98079,0.19509,0.99518,0.09802;3、算法实现我们已经知道，N点FFT从左到右共有log2N级蝶形，每级有N/2L组，每组有L个。所以FFT的C语言编程只需用3层循环即可实现：最外层循环完成每一级的蝶形运算（整个FFT共log2N级），中间层循环完成每一组的蝶形运算（每一级有N/2L组），最内层循环完成单独1个蝶形运算（每一组有L个）。/*【快速傅里叶变换】*/voidFFT(void)unsignedinti,j,k,l;complextop,bottom,xW;Reverse();/码位倒序for(i=0;ilog2N;i+)/*共log2N级*/一级蝶形运算l=1i;/l等于2的i次方for(j=0;jN;j+=2*l)/*每L个蝶形是一组，每级有N/2L组*/一组蝶形运算for(k=0;kl;k+)/*每组有L个*/一个蝶形运算xW=mul(xj+k+l,WNN/(2*l)*k);/碟间距为ltop=add(xj+k,xW);/每组的第k个蝶形bottom=sub(xj+k,xW);xj+k=top;xj+k+l=bottom;三、FFT计算结果验证随便输入一个64点序列，例如xN=1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2,0,5,0,8,0,4,0,1,0,3,0,2