当前位置:首页 > 快速傅里叶变换FFT的C语言实现及应用
m?1r?X(k)?X(k)?X(k?2)W mm?1m?1N?m?1m?1r X(k?2)?X(k)?X(k?2)Wm?1m?1N?m
蝶形运算两节点的第一个节点为k值,表示成L位二进制数,左移L – m位,
把右边空出的位置补零,结果为r的二进制数。
r?Xm(k)?Xm?1(k)?Xm?1(j)WN
?r X(j)?X(k)?X(j)Wm?1m?1N?m
2)倒位序
x(n)n?(n2n1n0)2
3)蝶形运算
对N = 2L点FFT,输入倒位序,输出自然序,
第m级运算每个蝶形的两节点距离为 2m–1
Wr 的确定N 蝶形运算两节点的第一个节点为k值,表示成L位二进制数,左移L – m 输入序列x(n) : N个存储单元 r的二进制数。 位,把右边空出的位置补零,结果为 系数 :N / 2个存储单元
4)存储单元
快速傅立叶变换的C语言实现方法
rN 有了傅立叶变换,我们可以从信号的频域特征去分析信号。尤其在无线通信系统 中,傅里叶变换的重要性就更加明显了,无论是设计者还是测试工程师,在工作中都会和傅立叶变换打交道。
W我们要衡量一个处理器有没有足够的能力来运行FFT算法,根据以上的简单介绍可以得出以下两点:
1. 处理器要在一个指令周期能完成乘和累加的工作,因为复数运算要多次查表相乘
才能实现。
2. 间接寻址,可以实现增/减1个变址量,方便各种查表方法。FFT要对原始序列进
行反序排列,处理器要有反序间接寻址的能力。
下面为一份FFT(快速傅立叶变换)的源码(基于C) /************FFT***********/ #include
#define N 1000 typedef struct {
double real;/*实部*/ double img;/*虚部*/ }complex;
void fft(); /*快速傅里叶变换*/ void ifft(); /*快速傅里叶逆变换*/ void initW(); /*初始化变化核*/ void change(); /*变址*/
void add(complex ,complex ,complex *); /*复数加法*/ void mul(complex ,complex ,complex *); /*复数乘法*/ void sub(complex ,complex ,complex *); /*复数减法*/ void divi(complex ,complex ,complex *);/*复数除法*/ void output(); /*输出结果*/
complex x[N], *W;/*输出序列的值*/
int size_x=0;/*输入序列的长度,只限2的N次方*/ double PI;
int main() {
int i,method;
system(\
PI=atan(1)*4;/*pi等于4乘以1.0的正切值*/
printf(\ /*输入序列的长度*/ scanf(\
printf(\ /*输入序列对应的值*/ for(i=0;i scanf(\ initW(); /*选择FFT或逆FFT运算*/ printf(\ scanf(\ if(method==0) fft(); else ifft(); output(); system(\ return 0; } /*进行基-2 FFT运算*/ 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< for(j=0;j for(k=0;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 ifft() { int i=0,j=0,k=0,l=size_x; complex up,down; for(i=0;i< (int)( log(size_x)/log(2) );i++) /*一级蝶形运算*/ { l/=2; for(j=0;j
共分享92篇相关文档