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

孙娟0909083014，蔡云0909083001，周硕举0909082830

1. 中南大学升华公寓27栋, 湖南 410032

E-mail:****************

摘 要: 快速傅里叶变换简介，FFT算法的基本原理，快速傅里叶变换的C语言实现方法，快速傅里叶变换的发展前景，快速傅里叶变换的应用领域，感想。 关键词：快速傅里叶变换 C语言 FFT应用

快速傅里叶变换简介

计算离散傅里叶变换的一种快速算法,简称FFT。快速傅里叶变换是1965年由J.W.

库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化 快速傅里叶变换 成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基２DIT和基２DIF。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的奇偶分成两组： x2rxrN1r0,1,...,1

2x2r1x2r

N1N1N1nknknk则x(n)的DFT:

XkxnWNxnWNxnWN n0n0n0

2rk r1Wx2rWNx2NN12N122r1kx1rWr0N12N12r0r0NkN22NrkWxrW22Nr0N121

rkr0r0

kN X1kWNX2k(r,k0,1,...1)2

N1N122 其中 rkrkX(k)x(r)Wx(2r)WNN11 22r0r0N1N1 22rkNX1(k)x1(r)WNx(2r)WNrk(k0,1,...1) 222r0r0

再利用周期性求X(k)的后半部分： NXk,Xk是以为周期的12 2 NNX1kX1kX2kX2k 22 NNkkk 又WN2WN2WNWN

k X(k)X1(k)WNX2(k) NkX(k)X(k)WX2(k)1N 2

rkkrk x1rWNWxrW/2N2N/2n为偶数n为奇数

2当、运算量N = 2L 时，共有L级蝶形，每级N / 2个蝶形， 每

NN 复数乘法： mLlog2NF 22 复数加法：

aFNLNlog2N比较DFT

mF(DFT)N22NNmF(FFT)log2Nlog2N2

3、算法特点

1）原位计算

蝶形运算两节点的第一个节点为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

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

Wr 的确定N 蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L – m 位，把右边空出的位置补零，结果为r的二进制数。

4）存储单元

r 输入序列x(n) : N个存储单元

N 系数 ：N / 2个存储单元

W 快速傅立叶变换的C语言实现方法

有了傅立叶变换，我们可以从信号的频域特征去分析信号。尤其在无线通信系统 中，傅里叶变换的重要性就更加明显了，无论是设计者还是测试工程师，在工作中都会和傅立叶变换打交道。

我们要衡量一个处理器有没有足够的能力来运行FFT算法，根据以上的简单介绍可以得出以下两点：

1. 处理器要在一个指令周期能完成乘和累加的工作，因为复数运算要多次查表相乘

才能实现。

2. 间接寻址，可以实现增/减1个变址量，方便各种查表方法。FFT要对原始序列进

行反序排列，处理器要有反序间接寻址的能力。

下面为一份FFT（快速傅立叶变换）的源码（基于C） /************FFT***********/ #include #include #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(\"cls\");

PI=atan(1)*4;/*pi等于4乘以1.0的正切值*/

printf(\"Please input the size of x:\\n\"); /*输入序列的长度*/ scanf(\"%d\

printf(\"Please input the data in x[N]:(such as:5 6)\\n\"); /*输入序列对应的值*/ for(i=0;iscanf(\"%lf %lf\ initW();

/*选择FFT或逆FFT运算*/

printf(\"Use FFT(0) or IFFT(1)?\\n\"); scanf(\"%d\

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<for(j=0;jfor(k=0;kmul(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;jfor(k=0;kadd(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) * size_x); for(i=0;iW[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;ik=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; } } }

void output() /*输出结果*/ {

int i;

printf(\"The result are as follows\\n\"); for(i=0;iprintf(\"%.4f\ if(x[i].img>=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; }

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