第6讲FFT算法设计如何有傅氏变换->DFT->FFT?推导分析蝶形分解图示N=8点FFT运算图示N=16点FFT运算图示蝶形运算规律公式中的J就是流程图中公式的变量k，流程图中：N表示阶数，M表示总级数，L表示当前级数，B表示每个蝶形的两个输入数据的间隔，P表示旋转因子指数看图推导软件编程规则：方法一看图推导方法二：外循环次数为级数L中循环为根据当前L求出各个不同的p，循环次数为p的个数2L-1内循环为每级中每个p对应的蝶形运算个数(记为VTotal)，循环次数为2M-L每个蝶形的两个输入数据间隔（记为INd）：输入序列倒序的算法设计倒序规律//输入序列倒序软件程序j=N/2;//第0个数(二进制数都为0)和最后一个第N-1个数(二进制数都为1)不需倒序for(i=1;i<N-2;i++){if(i<j){temp=dataR[i];dataR[i]=dataR[j];dataR[j]=temp;}k=N/2;while(1){if(j<k){j=j+k;break;}else{j=j-k;k=k/2;}}}输入序列倒序的算法设计方法二方法二软件分析：已一个字节(N=256)的倒序为例F0=i&0x04;F1=i&0x20;if(F0)j=j|0x20;if(F1)j=j|0x04;F0=i&0x08;F1=i&0x10;if(F0)j=j|0x10;if(F1)j=j|0x08;if(i<j)//前半部与后半部交换，相等时无需交换A[i]A[j];}算法改进一：算法改进二：针对任意N=2M的情况FFT软件示例//输入序列倒序j=N/2;//第0个数(二进制数都为0)和最后一个第N-1个数(二进制数都为1)不需倒序for(i=1;i<N-2;i++){if(i<j){temp=dataR[i];dataR[i]=dataR[j];dataR[j]=temp;//因为波形虚数部分都为0,所以不用交换//temp=dataI[i];//dataI[i]=dataI[j];//dataI[j]=temp;}k=N/2;while(1){if(j<k){j=j+k;break;}else{j=j-k;k=k/2;}}}//进行FFT//Xr[J]=Xr'(J)+Tr//Xi[J]=Xi'(J)+Ti//Xr[J+B]=Xr'(J)-Tr//Xi[J+B]=Xi'(J)-Ti//(其中Xr'为上一级的Xr,Xi'为上一级的Xi)//其中Tr=Xr'(J+B)cos(2.0*PI*p/N)+Xi'(J+B)sin(2.0*PI*p/N)//Ti=Xi'(J+B)cos(2.0*PI*p/N)-Xr'(J+B)sin(2.0*PI*p/N)for(L=1;L<=M;L++)//FFT蝶形级数L从1--M{//计算每个蝶形的两个输入数据相距B=2^(L-1);B=1;i=L-1;while(i){B=B*2;i--;}//或采用运算,即B=2^(L-1);B=(int)pow(2,L-1);//第L级蝶形有pow(2,L-1),即2的L-1次方个蝶形运算和pow(2,L-1)个旋转因子pfor(J=0;J<=B-1;J++)//J=0,1,2,...,2^(L-1)-1{//计算p=J*2^(M-L)p=1;i=M-L;while(i){p=p*2;i--;}p=J*p;//第L级蝶形中同一个旋转因子包含多少个蝶形运算//每个蝶形的两个输入数据相距B=2^(L-1)个点//同一旋转因子对应着间隔为2^L点的2^(M-L)个蝶形(2^L=2*B)for(k=J;k<=N-1;k=k+2*B){Tr=dataR[k];Ti=dataI[k];temp=dataR[k+B];dataR[k]=dataR[k]+dataR[k+B]*cos(2.0*PI*p/N)+dataI[k+B]*sin(2.0*PI*p/N);dataI[k]=dataI[k]+dataI[k+B]*cos(2.0*PI*p/N)-dataR[k+B]*sin(2.0*PI