FFT实验报告

快速傅里叶变换算法

实验报告

专业: 计算机科学与技术

班级: 2008211309

姓名: 潘婉琼

学号: 08211407

1.算法原理

●快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变

换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数

字系统中应用离散傅立叶变换，可以说是进了一大步。

●设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+N^2/2。继续上面的例子，N=1024时，总的运算次数就变成

了525312次，节省了大约50%的运算量。

●如果我们将这种“一分为二”的思想不断进行下去，直到分成两两

一组的DFT运算单元，那么N点的DFT变换就只需要Nlog(2)(N)次的

运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，

点数越多，运算量的节约就越大，这就是FFT的优越性。

2.问题描述

●乘法如果直接像手工算一样做，复杂度是O(n*n)的.FFT乘法是将

数看成多项式：P1(x)=a0+a1x+a2x^2+...+anx^n，如果取ak在0到9之间，且x取10，那它就表示一个十进制数，如果再用另外一个多项式P2(x)与它相乘，那结果和它所表示的数相乘是一样的数值。

●多项式乘法其实质是做两个系数序列的卷积，而FFT正是对这样的

卷积,做时域到频域的变化，FFT的本质也是DFT，离散傅里叶变换，因为有卷积定理：如果h(t)=x(t)*(y(t)，且H(s)=DFT[h(t)]，

X(s)=DFT[x(t)]，Y(s)=DFT[y(t)]，那么有，H(s)=X(s)Y(s)

3.算法及其复杂度分析

h(t)=IFFT[ FFT[x(t)] *FFT[y(t)] ]

IFFT是快速傅里叶反变换，可以转换成FFT，所以一个乘法的时间是3个FFT 加一个线性乘积运算，因此也是O(nlogn)。

4.算法实现

void FFT(Complex x[], int n)

//对x数组进行快速傅里叶变换,返回的结果仍存在x中

{

static Complex res[Maxn<<1];

double alpha = -2 * PI;

ButterflyChange(x, n, res);

int i,j,k,kk,p,m;

i=1,m=0;

while(i

i<<=1;

m++;

}//m为n的二进制位数

for(i=0,k=2;i

Complex temp=Complex(cos(alpha / k), sin(alpha / k));

for(j=0;j

Complex w=1,u,t;

kk=k>>1;

for(p=0;p

t=w*res[j+p+kk];

u=res[j+p];

res[j+p]=u+t;

res[j+p+kk]=u-t;

w*=temp;

}

}

}

memcpy(x,res,sizeof(Complex)* n);

}

5.实验总结

虽然之前信号与系统课上听说过快速傅里叶转换算法,但是一直没有深入研究.通过在网上查资料,看书等各种途径,我逐步了解了FFT算法的原理,特别是将FFT 算法用于求大数乘法后,对FFT的算法有了更加深入的理解.

虽然算法的研究偏理论,但是作为计算机专业的学生,将算法用代码实现,也是非常必要的.不但提升了动手能力,更对算法本身的理解更加深刻.