用C++实现FFT运算.docVIP

用C++实现FFT运算 姓名： 学号： 专业：通信工程 用C++实现FFT运算 摘要：介绍用C++实现FFT运算的原理算法、硬件框图、软件流程图，以及调试过程、步骤和结果。并对结果进行了分析。 引言：（FFT的用处及应用 为什么要用C++编写，C++和matlab相比优势和不足，C++能够实现的算法单一，调用的函数简单都有哪些，本例是通用程序） 原理: 1.算法 DFT：离散傅里叶变换是连续傅里叶变换字时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换。有限长序列x(n)的N点DFT为 基2FFT基本原理 设序列x(n)的长度为N,且满足，M为自然数。按n的奇偶把x(n)分解为两个N/2点的子序列 因此X(k)又可表示为 （1.1） （1.2） 这样，就将N点DFT分解为两个N/2点DFT和（1.1），（1.2）的运算。 原位计算:蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在??存储器中,这种利用同一存储单元存储蝶形计算输入、输出的方法即为原位运算。每一级(列)有N/2个蝶形运算,所以只需N个存储单元，可以节省存储单元。 蝶形运算 A+CB A 式(1.1),(1.2)的运算可用下图所示的流图符号表示，成为蝶形运算符号。 A-BC C B 倒位序 顺序倒序十进制数I二进制数二进制数十进制数J0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111000 100 010 110 001 101 011 1110 4 2 6 1 5 3 7 软件流程图： 开始 读入x(n),M 倒序 L=1,M J=0,B-1 结束 输出 调试过程和步骤： 1.程序代码： #include stdio.h #include math.h #include stdlib.h #define N 1000 // struct complex { double real;double img; }; complex x[N], *W; /*输入序列,变换核*/ int size_x=0; //初始化x的点数 double PI; //pi的值 void fft(); /*快速傅里叶变换*/ void initW(); /*初始化变换核*/ void change(); /*变址*/ void add(complex ,complex ,complex *); /*复数加法*/ void mul(complex ,complex ,complex *); /*复数乘法*/ void sub(complex ,complex ,complex *); /*复数减法*/ void output(); int main(){ int i; /*输出结果*/ system(cls); PI=atan(1)*4; //求出pi的值 printf(请输入x的点数:\n); scanf(%d,size_x); printf(请输入x的数据:\n); for(i=0;isize_x;i++) scanf(%lf%lf,x[i].real,x[i].img);//lf:长浮点 initW(); fft(); output(); return 0; }/*快速傅里叶变换*/ void fft(){ int i=0,j=0,k=0,l=0; complex up,down,product; change(); for(i=0;i log(size_x)/log(2) ;i++) { /*一级蝶形运算*/ l=1i; for(j=0;jsize_x;j+= 2*l ) { /*一组蝶形运算*/ for(k=0;kl;k++){ /*一个蝶形运算*/ mul(x[j+k+l],W[size_x*k/2/l],product); add(x[j+k],product,up); sub(x[j+k],product,down); x[j+k]=up; x[j+k+l]=down; } } } }/*初始化变换核*/ void initW() { int i; W=(complex *)malloc(sizeof(complex) * size_x); for(i=0;isize_x;i++) { W[i].real=cos(2*PI/size_x*i); W