fft算法代码注释及流程框图.docx

基2的DIT蝶形算法源代码及注释如下
*FFT
*/
〃整个程序输入和输由利用同一个空间 x[N],
节约空间
#in elude <>
#in elude <>
#include <stdl个算法的思路就是，
先把计算过程分为log(size_x)/log(2)-l级(用i控制级数)；
然后把每一级蝶形单元分组(用j控制组的第一个元素起始下标)；最后算由某一级某一组每
一个蝶形单元(用k控制个数，共I个)。*/ void fft() {
int i=O/j=O/k=O/l=O;
complex up,dow n,product;
change();〃实现对码位的倒置
for(i=0;i<log(size_x)/log(2);i++)〃 循环算由 fft 的结果
{ l=l?i; for(j=0;j<size_x;j+=2* I) 〃算由第 m二i级的结果【i从0至巾og(size_x)/log(2)) -1]
for(k=0;k<l;k++)〃算由第i级内j组蝶形单元的结果
〃算由j组中第k个蝶形单元
mul(x[j+k+l],W[(size_xZVI)*k],&product); /*sizeM 是该级 W 的相邻上标差， I是该级该组取的 w总个数p/
addlxD+,&up);
sub(x[j+k],product z&down);
x[j+k]=up;//up为蝶形单元右上方的值
x[j+k+l]=down;//down为蝶形单元右卞方的值
}
}
}
}
void initW()
int i;
W=(complex *)malloc(sizeof(complex) * size_x);
for(i=0;i<(size_x/2);i++)
〃计算W的实现函数
/*申请size_x个复数 W的空间(这部 申请的空间有点多，实际上只要 申请size_x左个即口 J)*/
厂预先计算由size_x/2个W的值，存 放，由于蝶形算法只需要前
size x/2个值即可*/
〃计算W的实部
〃计算W的虚部
W[i].real=cos(2*PI/size_x*i);
W[i].img=-l*sin(2*PI/size_x*i);
〃输入的码组码位倒置实现函数
void change()
{
complex temp;
unsigned short i=OJ=O,k=O;
double t;
for(i=0;i<size_x;i++)
{
k=i;
j=0;
t=(log(size_x)/log(2));
while((t-)>0)
j|=(k &1) ； k=k? l;
}
if(j>i)
temp=x[i];
x[i]=x[j];
x[j]=temp;
void output() 〃输出结果实现函数
{
int i;
printf( HThe result are asfollows\nJ;
for(i=0;i<size_x;i++)
{
printf( ％”.4f “ ,x[