当前位置:首页 >> 计算机软件及应用 >>

用c语言实现的FFT


一、对 FFT 的介绍 1. FFT(Fast Fourier Transformation),即为快速傅里叶变换,是离散 傅里叶变换的快速算法,它是根据离散傅里叶变换的奇、偶、虚、实等 特性,对离散傅里叶变换的算法进行改进获得的。 2.FFT 算法的基本原理 FFT 算法是把长序列的 DFT 逐次分解为较短序列的 DFT。 按照抽取方式的不同可分为 DIT-FFT(按时间抽取)和 DIF-FFT(按 频率抽取)算法。按蝶形运算的构成不同可分为基 2,基 4,基 8,以及 任意因子的类型。

3.迭代关系

4、本次程序的基本过程 我们这次所研究的是数字信号处理中的 FFT 算法, 我们这次所用的数字 信号是复数类型的。 (1)所以首先,我们先定义了一个复数结构体,因为是进行复数的运算, 我们又相继定义复数的加减乘运算的函数。 (2)紧接着,我们定义了进行 FFT 计算的 fft()快速傅里叶变换函数 initW() 初始化变换核函数即旋转因子的计算,change() 变址函数, output()输出傅里叶变换的结果的函数。 (3)定义主函数, 并调用定义好的相关子函数, 利用 fft()中的蝶形运算以 及 change()函数来完成从时间域上选取的 DIT-FFT。

二、FFT 中码位倒置排序 1、码位倒置的实现方法: (1)简单的利用按位与、或循环实现 (2)利用公式推导的迭代方法 2、为什么要进行码位倒置 因为由于 FFT 的计算特性,如果按照正常顺序输入,而没有进行码位 倒置的话,就会以乱序输出,就不便于我们后续对信号的相关性质进行

研究了,所以 DIT-FFT 算法就是在进行 FFT 计算之前,进行分奇偶后 的码位倒置运算,即二进制数的倒位。

3、倒位序由奇偶分组造成,以 N=8 为例,说明如下:

三、蝶形运算



按照上述公式的规律进行逐级分解,直到 2 点 DFT,如下是 N=8 时的 蝶形算法分析图:

四、FFT 算法中蝶形算法的基本思想分析 (1)我们知道 N 点 FFT 运算可以分成 log2(N)级,每一级都有 N/2 个碟形,FFT 的基本思想是用 3 层循环完成全部运算(N 点 FFT)。

(2)第一层循环:由于 N=2^m 需要 m 级计算,第一层循环对运算的 级数进行控制。(stages)

(3)第二层循环:由于第 L 级有 2^(L-1)个蝶形因子(乘数),第二 层循环根据乘数进行控制, 保证对于每一个蝶形因子第三层循环要执行 一次,这样,第三层循环在第二层循环控制下,每一级要进行 2^(L-1) 次循环计算.(选择 W)

(4)第三层循环:由于第 L 级共有 N/2^L 即 2^(n-L)个群,并且 同一级内不同群的乘数分布相同,当第二层循环确定某一乘数后,第三 层循环要将本级中每个群中具有这一乘数的蝶形计算一次, 即第三层循 环每执行完一次要进行 N/2^L 个碟形计算。 (执行不同 group 中具有 相同 W 的蝶形运算)

(5) 可以得出结论: 在每一级中, 第三层循环完成 N/2^L 个碟形计算; 第二层循环使第三层循环进行 2^(L-1)次,因此,第二层循环完成时, 共进行 2^(L-1) *N/2^L=N/2 个碟形计算。实质是:第二、第三层循 环完成了第 L 级的计算。

五、用 c 语言实现的 FFT 算法如下:
<span style="font-size:18px;">#include <stdio.h> #include <math.h> #include <stdlib.h> #define N 1000 /*定义复数类型*/ typedef struct{ double real; double img; }complex;

complex x[N], *W; /*输入序列,变换核*/ int size_x=0; double PI; void fft(); void initW(); /*输入序列的大小,在本程序中仅限 2 的次幂*/ /*圆周率*/ /*快速傅里叶变换*/ /*初始化变换核*/

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; printf(" 果\n"); 输出 DIT 方法实现的 FFT 结 /*输出结果*/

printf("Please input the size of x:\n");//输入序列的大小 scanf("%d",&size_x); printf("Please input the data in x[N]:\n");//输入序列的实部和虚部 for(i=0;i<size_x;i++) { printf("请输入第%d 个序列:",i); scanf("%lf%lf",&x[i].real,&x[i].img); } printf("输出倒序后的序列\n"); initW();//调用变换核 fft();//调用快速傅里叶变换 printf("输出 FFT 后的结果\n"); output();//调用输出傅里叶变换结果函数 return 0; }

/*快速傅里叶变换*/ void fft() { int i=0,j=0,k=0,l=0; complex up,down,product; change(); { l=1<<i; for(j=0;j<size_x;j+= 2*l ) p 的蝶形因子乘数不同*/ { for(k=0;k<l;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; } } } } /*一个蝶形运算每个 group 内的 /*一组蝶形运算 group,每个 grou //调用变址函数 /*一级蝶形运算 stage */ for(i=0;i< log(size_x)/log(2) ;i++)

/*初始化变换核,定义一个变换核,相当于旋转因子 WAP*/ void initW() { int i; W=(complex *)malloc(sizeof(complex) * size_x); for(i=0;i<size_x;i++) { W[i].real=cos(2*PI/size_x*i); W[i].img=-1*sin(2*PI/size_x*i); } } //用欧拉公式计算旋转因子 //生成变换核

/*变址计算,将 x(n)码位倒置*/ void change() { complex temp; unsigned short i=0,j=0,k=0; double t; for(i=0;i<size_x;i++) { k=i;j=0; t=(log(size_x)/log(2)); while( (t--)>0 ) { j=j<<1; j|=(k & 1); k=k>>1; } if(j>i) { temp=x[i]; x[i]=x[j]; x[j]=temp; } } output(); } //将 x(n)的码位互换 //利用按位与以及循环实现码位颠倒

/*输出傅里叶变换的结果*/

void output() { int i; printf("The result are as follows:\n"); for(i=0;i<size_x;i++) { printf("%.4f",x[i].real); if(x[i].img>=0.0001)printf("+%.4fj\n",x[i].img); else if(fabs(x[i].img)<0.0001)printf("\n"); else printf("%.4fj\n",x[i].img); } }

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; } </span>

// 复数减法的定义

六、FFT 原理的理解和程序设计中遇到的相关问题及解决方法 1、遇到的相关问题: (1)首先一开始不知道什么是 FFT,以及 FFT 原理是什么 (2)不理解 FFT 中迭代关系的推导以及缘由 (3)不理解变址计算的原理

(4)对蝶形运算的推导与原理的理解不透彻 (5)编程过程中对变址计算即对按位与的变换形式的不理解 2、解决的方法: (1)到图书馆借相关的书籍理解相关的原理和过程 (2)到百度收索相关的资料促进理解相应的原理过程 (3)向学长学姐请教或老师的指导 七、总结 从这次的考核中我学到了一些有关数字信号处理的相关知识, 即快速傅 里叶变换的原理, 虽然并不是非常深入的去学习, 但却深刻的领悟到了, 弄懂最基本的原理是理解的关键, 只有弄懂了最基本的原理并具备一定 的编程语言基础,才能顺利完成一个项目。在这次的学习过程中,我对 原理的理解是通过对大量书籍和上网查阅资料以及老师的指导才渐渐 的理解的。所以我觉得做好一件事,需要有坚持不懈的努力和一点一滴 的积累。


赞助商链接
相关文章:
FFT的C语言算法实现
FFT的C语言算法实现_信息与通信_工程科技_专业资料。一个用C语言写的简易的FFT的算法,FFT 的 C 语言算法实现程序如下: /***FFT***/ #include <stdio.h> ...
C语言、Matlab实现FFT几种编程实例
C 语言、MATLAB 实现 FFT 几种方法 总结前人经验,仅供参考 ///一、 /// ///...
实序列FFT算法的C语言实现
实序列FFT算法的C语言实现_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 实序列FFT算法的C语言实现_数学_自然科学_专业资料。...
C语言实现FFT
C语言实现FFT_信息与通信_工程科技_专业资料。#include <iom128.h> #include ...() 函数功能:测试 FFT 变换,演示函数使用方法 输入参数:无 输出参数:无 ***...
C语言实现FFT(快速傅里叶变换)
C语言实现FFT(快速傅里叶变换)_信息与通信_工程科技_专业资料。C语言实现FFT(快速傅里叶变换) #include <iom128.h> #include <intrinsics.h> /*** 快速福利...
用c语言实现的FFT
用c语言实现的FFT - 一、对 FFT 的介绍 1. FFT(Fast Fourier Transformation),即为快速傅里叶变换,是离散 傅里叶变换的快速算法,它是根据离散傅里叶变换...
C语言及Matlab实现fft
C语言及Matlab实现fft_工学_高等教育_教育专区。C语言及Matlab实现fft/*时间抽选基 2FFT 及 IFFT 算法 C 语言实现 时间抽选基 语言实现*/ 学号 3070503041 电信...
快速傅里叶变换FFT的C语言实现及应用
快速傅里叶变换 FFTC 语言实现及应用快速傅里叶变换简介计算离散傅里叶变换的一种快速算法,简称 FFT。快速傅里叶变换是 1965 年由 J.W. 库利和 T.W....
FFT算法设计与实现
FFT算法设计与实现_信息与通信_工程科技_专业资料。c语言实现FFT算法 FFT 算法研究报告 1、 程序设计背景(FFT 算法理解) FFT(fast fourier transformation),快速傅...
FFT的C语言编程
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 FFT的C语言编程 如题如题隐藏>> FFTC 语言编程 1.程序: #...
更多相关标签: