用C++实现FFT运算.doc
文本预览下载声明
用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
显示全部