用C++实现FFT运算

用C++实现FFT运算

姓名： 学号：

专业：通信工程

用C++实现FFT运算

摘要：介绍用C++实现FFT运算的原理算法、硬件框图、软件流程图，以及调试过程、步骤和结果。并对结果进行了分析。 引言：（FFT的用处及应用 为什么要用C++编写，C++和matlab相比优势和不足，C++能够实现的算法单一，调用的函数简单都有哪些，本例是通用程序） 原理: 1.算法

 DFT：离散傅里叶变换是连续傅里叶变换字时域和频域上都离散的形式，将时域信号的

采样变换为在离散时间傅里叶变换。有限长序列x(n)的N点DFT为X(k) 基2FFT基本原理

设序列x(n)的长度为N,且满足N2，M为自然数。按n的奇偶把x(n)分解为两个N/2点的子序列x1(r)x(2r) r0,1,...,N/21

x2(r)x(2r1) r0,1,...,N/21

因此X(k)又可表示为X(k)X1(k)WNX2(k) k0,1,...,N/21 （1.1） X(kN/2)X1(k)WNX2(k) k0,1,...N,/21 （1.2） 这样，就将N点DFT分解为两个N/2点DFT和（1.1），（1.2）的运算。

 原位计算:蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,这种利

用同一存储单元存储蝶形计算输入、输出的方法即为原位运算。每一级(列)有N/2个蝶形运算,所以只需N个存储单元，可以节省存储单元。  蝶形运算

式(1.1),(1.2)的运算可用下图所示的流图符号表示，成为蝶形运算符号。

A A+CB

B

 倒位序 顺序 十进制数I 0 1 2 3 4 5 二进制数 000 001 010 011 100 101 C

kkx(n)Wn0N1knN

MA-BC

倒序 二进制数 000 100 010 110 001 101 十进制数J 0 4 2 6 1 5 6 7

软件流程图： 110 111 011 111 3 7 开始 读入N2M 倒序 L=1,M B2L1 J=0,B-1 P2MLJ KJ,N1,2L TA(k)A(kB)WNpA(kB)A(k)A(kB)WNp A(k)T输出 结束

调试过程和步骤： 1.程序代码： #include #include #include #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\

printf(\"请输入x的数据:\\n\"); for(i=0;iscanf(\"%lf%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=1<}/*初始化变换核*/ void initW() { int i; W=(complex *)malloc(sizeof(complex) * size_x); for(i=0;ivoid change(){ //x倒位序 complex temp; //temp是复数 unsigned short i=0,j=0,k=0; double t; for(i=0;i0 ){ j=j<<1; //j左移一位 j|=(k & 1);//j=j|(k & 1),|表示位或 k=k>>1; } if(j>i) { temp=x[i]; x[i]=x[j]; x[j]=temp; }}}

/*输出傅里叶变换的结果*/ void output(){ int i; printf(\"The result are as follows\\n\"); for(i=0;i=0.0001)printf(\"+%.4fj\\n\ else if(fabs(x[i].img)<0.0001)printf(\"\\n\"); else printf(\"%.4fj\\n\}}

void add(complex a,complex b,complex *c){c->real=a.real+b.real; c->img=a.img+b.img;

}void mul(complex a,complex b,complex *c){ c->real=a.real*b.real - a.img*b.img; c->img=a.real*b.img + a.img*b.real;

}void sub(complex a,complex b,complex *c){c->real=a.real-b.real; c->img=a.img-b.img; }

2.调试过程：

实验结果：

结果分析：

用C++实现了FFT

结束语：

通过这个题目，让我学会了结构体，同时对DFT，FFt有加深了印象。而且对书本上的“DIT-FFT的运算规律及编程思想”有了进一步的认识，对原位计算、旋转因子的变化规律、蝶形运算规律、编程思想及程序框图、序列的倒序等都有了一定的认识。对于我的Ｃ＋＋编程非常有帮助。