当前位置:首页 >> 工程科技 >>

快速傅里叶变换FFT的C语言实现及应用


快速傅里叶变换 FFT 的 C 语言实现及应用
孙娟 0909083014,蔡云 0909083001,周硕举 0909082830
1. 中南大学升华公寓 27 栋, 湖南 410032 E-mail: chxycrwo@163.com 摘 要: 快速傅里叶变换简介,FFT 算法的基本原理,快速傅里叶变换的 C 语言实现方法,快速傅里 叶变换的发展前景,快速傅里叶变换的应用领域,感想。 关键词:快速傅里叶变换 C 语言 FFT 应用

快速傅里叶变换简介 快速傅里叶变换简介 里叶变换
计算离散傅里叶变换的一种快速算法,简称 FFT。快速傅里叶变换是 1965 年由 J.W. 库利和 T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次 数大为减少,特别是被变换的抽样点数 N 越多,FFT 算法计算量的节省就越显著。 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化

快速傅里叶变换 成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年,Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT)的快速算法, 将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换(FFT)算法的研究 便不断深入,数字信号处理这门新兴学科也随 FFT 的出现和发展而迅速发展。根据 对序列分解与选取方法的不同而产生了 FFT 的多种算法,基本算法是基2DIT 和基 2DIF。FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。 快速傅氏变换(FFT) ,是离散傅氏变换的快速算法,它是根据离散傅氏变换的 奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。它对傅氏变换 的理论并没有新的发现, 但是对于在计算机系统或者说数字系统中应用离散傅立叶 变换,可以说是进了一大步。 设

快速傅里叶变换

x(n)为 N 项的复数序列,由 DFT 变换,任一 X(m)的计算都需要 N 次复数乘法和 N-1 次复数加法,而一次复数乘法等于四次实数乘法和两次实数加法,一次复数加 法等于两次实

快速傅里叶变换 数加法,即使把一次复数乘法和一次复数加法定义成一次“运算” (四次实数乘法 和四次实数加法) ,那么求出 N 项复数序列的 X(m),即 N 点 DFT 变换大约就需要 N^2 次运算。当 N=1024 点甚至更多的时候,需要 N2=1048576 次运算,在 FFT 中, 利用 WN 的周期性和对称性,把一个 N 项序列(设 N=2k,k 为正整数) ,分为两个 N/2 项的子序列,每个 N/2 点 DFT 变换需要(N/2)2 次运算,再用 N 次运算把两个 N/2 点的 DFT 变换组合成一个 N 点的 DFT 变换。这样变换以后,总的运算次数就变成 N+2(N/2)2=N+N2/2。继续上面的例子,N=1024 时,总的运算次数就变成了 525312 次,节省了大约 50%的运算量。而如果我们将这种“一分为二”的思想不断进行下 去,直到分成两两一组的 DFT 运算单元,那么 N 点的 DFT 变换就只需要 Nlog2N 次 的运算,N 在 1024 点时,运算量仅有 10240 次,是先前的直接算法的 1%,点数越 多,运算量的节约就越大,这就是 FFT 的优越性。

FFT 算法的基本原理
FFT 算法的基本思想:利用 DFT 系数的特性,合并 DFT 运算中的某些项,吧长序列的 DFT—>短序列的 DFT,从而减少其运算量。 FFT 算 法 分 类 : 时 间 抽 选 法 DIT: Decimation-In-Time ; 频 率 抽 选 法 DIF: Decimation-In-Frequency 按时间抽选的基-2FFT 算法 1、算法原理 设序列点数 N = 2L,L 为整数。 若不满足,则补零。N 为 2 的整数幂的 FFT 算法称基-2FFT 算法。将序列 x(n)按 n 的奇偶分成两组:

x ( 2r ) = x1 ( r )
N ?1 n =0

x ( 2r + 1) = x2 ( r )
N ?1 n =0 n为偶数

r = 0,1,...,
N ?1 n =0

N ?1 2

则 x(n)的 DFT:

nk nk nk X ( k ) = ∑ x ( n )WN = ∑ x ( n )WN + ∑ x ( n )WN

n为奇数

= ∑ x ( 2r )W
N ?1 2

N ?1 2

2 2 = ∑ x1 ( r ) (WN ) + WNk ∑ x2 ( r ) (WN ) rk
2

r =0

2 rk N

( + ∑ x ( 2r + 1)WN
r =0 N
?1

N ?1 2

2 r +1)k

rk

r =0
N 2

r =0

= ∑ x1 ( r )W
r =0

?1

rk N /2
k N

+W

k N

∑ x ( r )W
r =0 2

N 2

?1

rk N /2

= X1 ( k ) + W X 2 ( k )
其中
N ?1 2 N ?1 2

( r , k = 0,1,...

N ? 1) 2

X 1 (k ) = ∑ x1 (r )WN = ∑ x(2r )W Nrk
rk

X 1 (k ) = ∑ x1 (r )W Nrk = ∑ x(2r )W Nrk
r =0
2

N ?1 2

r =0

2

N ?1 2

r =0

2

r =0

2

(k = 0,1,...

N ? 1) 2

再利用周期性求 X(k)的后半部分:

Q X 1 ( k ) , X 2 ( k ) 是以

N 为周期的 2 N? N? ? ? ∴ X1 ? k + ? = X1 ( k ) X2 ? k + ? = X 2 (k ) 2? 2? ? ?

又WN

k+

N 2

k k = W WN = ?WN

N 2 N

k ? X (k ) = X 1 (k ) + WN X 2 (k ) ? ∴? N k ? X (k + 2 ) = X 1 (k ) ? WN X 2 ( k ) ?

mF =

N N L = log 2 N 2 2

2、运算量

2、运算量 当 N = 2L 时,共有 L 级蝶形,每级 N / 2 个蝶形, 每 N N 复数乘法: m = L = log N
F

复数加法: 比较 DFT

aF = NL = N log2 N

2

2

2

mF (DFT ) N2 2N = = N mF (FFT ) lo g 2 N lo g 2 N 2

3、算法特点 1)原位计算 蝶形运算两节点的第一个节点为 k 值,表示成 L 位二进制数,左移 L – m 位, 把右边空出的位置补零,结果为 r 的二进制数。
r ? X m ( k ) = X m?1 ( k ) + X m?1 ( j )WN ? r ? X m ( j ) = X m?1 ( k ) ? X m?1 ( j )WN

2) 倒位序

x(n) n = (n2n1n0 )2

3) 蝶形运算 对 N = 2L 点 FFT,输入倒位序,输出自然 序, 第 m 级运算每个蝶形的两节点距离为 2m–1

r ? X m (k ) = X m?1 ( k ) + X m?1 ( k + 2m?1 )WN ? m ?1 m ?1 r ? X m ( k + 2 ) = X m?1 ( k ) ? X m?1 ( k + 2 )WN

r WN 的确定

蝶形运算两节点的第一个节点为 k 值,表示成 L 位二进制数,左移 L – m 位,把右边空出的位置补零,结果为 r 的二进制数。 4)存储单元 输入序列 x(n) : N 个存储单元 r 系数 :N / 2 个存储单元 N

W

快速傅立叶变换的 C 语言实现方法
有了傅立叶变换,我们可以从信号的频域特征去分析信号。尤其在无线通信系统 中,傅里叶变换的重要性就更加明显了,无论是设计者还是测试工程师,在工作中都会 和傅立叶变换打交道。 我们要衡量一个处理器有没有足够的能力来运行 FFT 算法,根据以上的简单介绍可以得 出以下两点: 1. 处理器要在一个指令周期能完成乘和累加的工作,因为复数运算要多次查表相乘 才能实现。 2. 间接寻址,可以实现增/减 1 个变址量,方便各种查表方法。FFT 要对原始序列进 行反序排列,处理器要有反序间接寻址的能力。 下面为一份 FFT(快速傅立叶变换)的源码( 下面为一份 FFT(快速傅立叶变换)的源码(基于 C) /************FFT***********/ #include <stdio.h> #include <math.h> #include <stdlib.h>

#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 { int main() i,method;

system("cls"); PI=atan(1)*4;/*pi等于4乘以1.0的正切值*/ printf("Please input the size of x:\n"); /*输入序列的长度*/ scanf("%d",&size_x); printf("Please input the data in x[N]:(such as:5 6)\n"); /*输入序列对应的值*/ for(i=0;i<size_x;i++) scanf("%lf %lf",&x[i].real,&x[i].img); initW(); /*选择FFT或逆FFT运算*/ printf("Use FFT(0) or IFFT(1)?\n"); scanf("%d",&method); if(method==0)

fft(); else ifft(); output(); 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<<i; for(j=0;j<size_x;j+= 2*l ) /*一组蝶形运算*/ { 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; } } } }

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) { l/=2;

);i++) /*一级蝶形运算*/

for(j=0;j<size_x;j+= 2*l ) /*一组蝶形运算*/ { for(k=0;k<l;k++) /*一个蝶形运算*/ { add(x[j+k],x[j+k+l],&up); up.real/=2;up.img/=2; sub(x[j+k],x[j+k+l],&down); down.real/=2;down.img/=2; divi(down,W[size_x*k/2/l],&down); x[j+k]=up; x[j+k+l]=down; } } } change(); } /*初始化变化核*/ void initW() { int i; W=(complex *)malloc(sizeof(complex) 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;

*

size_x);

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

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; } void divi(complex a,complex b,complex *c) { c->real=( a.real*b.real+a.img*b.img )/( b.real*b.real+b.img*b.img); c->img=( a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img); }

快速傅立叶变换的发展前景
快速傅立叶变换作为一种数学方法,已经广泛地应用在几乎所有领域的频谱分析中, 而且经久不衰,因为信号处理方法没有先进和落后之分,只有经典和现代之别,在实际 系统中用得最好的方法就是管用的方法。换句话说,信号处理方法与应用背景和目的的 贴近程度是衡量信号处理方法优劣的唯一标准。FFT 是快速傅利叶变换(Fast Fourier Transform 简称 FFT)的英文缩写,它在当今科技世界中的应用姻当活跃,无论是在时间序 列分析领域中,还是在我国刚刚兴起的生物频谱治疗的研究与应用中,都有着重要的作 用。同时,它又是软件实现数字滤波器的必备组成部分之一。

快速傅立叶变换的应用领域 快速傅立叶变换的应用领域
?? 信号分析,包括滤波、数据压缩、电力系统的监控等; ?? 研究偏微分方程,比如求解热力学方程的解时,把 f(t)展开为三角级数最为关键 ?? 概率与统计,量子力学等学科。 ?? 我们以快速傅里叶变换在信号分析某一方面为例稍微说明一下应用过程。利用快速 傅里叶变换 FFT 将图像信号从空间转换到频域进行分析,是快速卷积,目标识别等许多 算法易于实现,然后根据图像信号的灰度结构特征和频谱分布,用 Butterworth 带通滤 波器和二维维纳滤波器进行滤波处理,去除图像信号中的低频感染和噪声信号,再利用 傅里叶反变换将信号还原。结果显示,处理后的模拟远程高空卫星照片轮廓清晰可见, 对下一步利用光学系统装置采集的远程目标的进一步识别提供了有力的条件。利用离散 傅里叶变换在实现是存在快速算法,即快速傅里叶变换(FFT)和有效的滤波处理,对模 拟远程高空卫星照片进行了较为有效的处理。我对快速傅里叶变换和信号这门课的看法 和认识

感想
快速傅里叶变换并不是一种新的变换,而是傅里叶变换的一种快速算法,经过人们对算 法的改善发展而形成的一套高速有效的运算方法。使 DFT 得计算大大简化,运算时间一 般可缩短 一、二个数量级,从而使 DFT 的运算在实际中得到真正广泛运用。 通过本次论文的设计,得到了以下结论:1、极大地调动了我们学生学习的积极性和自主 性。2、因为需要除了课本外的很多知识,所以也培养了学生的自学能力,也让我们拓宽 了自己的眼界,提高了我们自主学习和逐步发现问题、分析问题和解决问题的能力。3、 而且,整个论文设计过程中我们同学之间的互相帮助和互相团结的得到了充分的发挥, 让我们进一步认识到了团结就是胜利这句话的含义,也让我们认识到了三人行必有我师 的道理,扬长补短。4、论文设计时不仅帮助我们复习了已学习的知识,也使我们在查阅 资料的过程中,拓宽了自己的眼界,和学习到了对资料好坏的评判。

参考文献
《数字信号处理教程》(第三版) 《C 语言程序设计(第三版) 》 程佩青 谭浩强 清华大学出版社 清华大学出版社

http://wenku.baidu.com/view/95f99d0590c69ec3d5bb7541.html http://wenku.baidu.com/view/5f67a64c2e3f5727a5e96257.html


赞助商链接
相关文章:
运用快速傅里叶变换(FFT)进行信号时—频转换
运用快速傅里叶变换(FFT)进行信号时—频转换 *对输入(待测)信号的处理过程窗函 数 截取信号 输入连续信号 fsam 离散周期信号 有限序列(N 点) FFT 输入信号的...
FFT-C快速傅里叶变换超级详细的原代码
FFT-C快速傅里叶变换超级详细的原代码_工学_高等教育_教育专区。快速傅里叶变换超级详细的原代码快速傅里叶变换超级详细的原代码快速...
快速傅里叶变换(FFT)算法C++实现代码
} // Danielson - Lanczos 引理应用 mmax = 2; while(n > mmax) { step...C语言实现FFT(快速傅里叶... 12页 1下载券 快速傅里叶变换法(FFT) 9...
快速傅里叶变换(FFT)算法--理论与程序设计
快速傅里叶变换(FFT)算法 ——理论与程序设计 一、 引言快速傅里叶变换(FFT)是信号谱分析与实时处理中的一种重要变换。它来自 于 1965 年图基 (J. W. Tu...
带注解的快速傅里叶变换(fft)matlab程序
带注解的快速傅里叶变换(fft)matlab程序 - Fs = 128; T = 1/Fs; L = 256; % 采样频率 % 采样时间 % 信号长度 t = (0:L-1)*T; % 时...
快速傅里叶变换FFT算法及其应用_———
快速傅里叶变换FFT算法及其应用_——— - 快速傅里叶变换 FFT 算法及其应用 摘要 本文较为系统地阐述了快速傅里叶变换算法原理及其在数字信号处理等 工程...
实验二 快速傅里叶变换(FFT)及其应用
(FFT)及其应用 闫春遐 00824049 实验二 快速傅里叶变换(FFT)及其应用 一、实验目的(1)在理论学习的基础上,通过本实验,加深对 FFT 的理解,熟悉 MATLAB 中的有...
快速傅里叶变换(FFT)原理及源程序
快速傅里叶变换(FFT)原理及源程序 - 《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量,其用到的方法是分级...
利用MATLAB编写FFT快速傅里叶变换
利用MATLAB编写FFT快速傅里叶变换 - 数字信号处理实验报告 1.利用MATLAB编写FFT快速傅里叶变换。 2.比较编写的myfft程序运算结果与MATLAB中的FFT的有无误差。
快速傅里叶变换fft的Matlab实现 实验报告
快速傅里叶变换fft的Matlab实现 实验报告_信息与通信_工程科技_专业资料。一、...FFT 进行信号分析的 C 语言(或 MATLAB 语言)程序; 用 MATLAB 语言编写的 FFT...
更多相关标签: