您好,欢迎来到筏尚旅游网。
搜索
您的当前位置:首页FFT实验报告

FFT实验报告

来源:筏尚旅游网

FFT实验报告

实验报告业:计算机科学与技术级:309名号:7

1.算法原理

快速傅氏变换,是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅变换,可以说是进了一大步。

设_(n)为N项的复数序列,由DFT变换,任(m)的计算都需要N次复数乘法和N-1次复数加法,而一次复数乘法等于四次实数乘法和两次实数加法,一次复数加法等于两次实数加法,即使把一次复数乘法和一次复数加法定义成一次“运算”(四次实数乘法和四次实数加法),那么求出N项复数序列的_(m),即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候,需要N2=次运算.在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(nn)的.FFT乘法是将数看成多项式:P1(_)=a0+a1_+a2_^2+...+an_^n,如果取ak在0到9之间,且_取10,那它就表示一个十进制数,如果再用另外一个多项式P2(_)与它相乘,那结果和它所表示的数相乘是一样的数值。

多项式乘法其实质是做两个系数序列的卷积,而FFT正是对这样的卷积,做时域到频域的变化,FFT的本质也是DFT,离散傅变换,因为有卷积定理:如果h(t)=_(t)(y(t),且H(s)=DFT[h(t)],_(s)=DFT[_(t)],Y(s)=DFT[y(t)],那么有,H(s)=_(s)Y(s)

3.算法及其复杂度分析

h(t)=IFFT[FFT[_(t)]FFT[y(t)]]

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

4.算法实现

voidFFT(Comple__[],intn)

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

staticComple_res[Ma_n<<1];doublealpha=-2PI;ButterflyChange(_,n,res);inti,j,k,kk,p,m;i=1,m=0;

while(i

i<<=1;

m++;}m为n的二进制位数

for(i=0,k=2;i1;for(p=0;p

5.实验总结

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

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

Copyright © 2019- efsc.cn 版权所有 赣ICP备2024042792号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务