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

fft算法代码注释及流程框图.doc}
基2的DIT蝶形算法源代码及注释如下:
*FFT
*/
〃整个程序输入和输出利用同一个空间x[N],
节约空间
#in elude
<>
}
#in elude <>
#include <>
#defi ne typedef struct
1000
〃定义输入或者输出空间的最人长度
}
}
double
double
system(,,cls,,)；
Pl=atan(l)*4;
prin tf("Please in put the size of x:\rf); scanf("%d,,/&size_x);
printf("Please input the data in x[N]:(such as:5 6)\n")； for(i=0;i<size_x;i++)
scanf("%lf %lf"/&x[i].real/&x[i].img);
initW();
output();
厂输入序列的长度穴/
厂输入序列对应的值
〃计算 W(0)~W(size_x・l)的值 〃利用fft快速算法进行DFT变化 〃顺序输岀size_x个fft的结果
{complex;
〃定义复数型变量的结构体
void
〃快速傅里叶变换函数声明
void
initW();
〃计算W(0)~W(size_x-l)的值函数声明
void
change();
〃码元位置倒置函数函数声明
void
add(complex,complex,complex *);
/*复数加法*7
void
mul(complexzcomplex,complex *);
/*复数乘法*/
void
sub(complex,complex,complex *);
/*复数减法*7
void
divi(complex,complex,complex *);
/*复数除法-7
void
output();
/*输出结果-7
complex x[N],*W;
/*输出序列的值-7
int
size_x=0;
厂输入序列的长度，只限2的N次方*/
double PI;
//pi的值
int
main()
real;
img;
int
}
}
return 0;
}
}
}
厂进行基J FFT运算，蝶形算法。这个算法的思路就是，
先把计算过程分为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到(log(size_x)/log(2)) -1]
for(k=0