资源描述：
《串行fft递归算法蝶式递归计算原理求傅里叶变换》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、串行FFT递归算法（蝶式递归计算原理）求傅里叶变换摘要 FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和
2、一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出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。继续上面的例
3、子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog(2)(N)次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。关键字：FFT蝶式计算傅里叶变换目录一．题目及要求11.1题目1二．设计算法、算法原理12.1算法原理与设计12.2设计步骤2三．算法描述、设计流程43.1算法
4、描述43.2流程图5四．源程序代码及运行结果74.1源程序代码74.2运行结果12五．算法分析、优缺点135.1算法分析135.2优缺点14六．总结15七．参考文献16一．题目及要求1.1题目对给定的，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。1.2要求利用串行递归与蝶式递归原理，对给定的向量求解傅里叶变换的结果。二．设计算法、算法原理2.1算法原理与设计蝶式递归计算原理：令为n/2次单位元根，则有，将b向量的偶数项和奇数项分别记为和。注意推导中反复使用：。图2.1公式图
5、形162.2设计步骤对于以上的分析可画出如图2.2所示的离散傅里叶变换递归计算流图。图2.3就是一个按此递归方法计算的n=8的FFT蝶式计算图。16FFT的蝶式递归计算图（有计算原理推出）：图2.2递归计算流图特别的，ｎ＝８的FFT蝶式计算图（展开的）：图2.3蝶式计算图按输入元素展开，前面将输出序列之元素按其偶下标（）和（）展开，导出和递归计算式，按此构造出了如图1所示的FFT递归计算流程图。事实上，我们也可以将输入序列之元素16按其偶下标（）和几下标（）展开，则导出另一种形式的FFT递归计算
6、式。三．算法描述、设计流程3.1算法描述SISD上的FFT分治递归算法：输入:a=(a0,a1,…,an-1);输出:B=(b0,b1,…,bn-1)ProcedureRFFT(a,b)beginifn=1thenb0=a0else(1)RFFT(a0,a2,…,an-2,u0,u1,…,un/2-1)(2)RFFT(a1,a3,…,an-1,v0,v1,…,vn/2-1)(3)z=1(4)forj=0ton-1do(4.1)bj=ujmodn/2+zvjmodn/2(4.2)z=zωendfo
7、rendifend注:(1)算法时间复杂度t(n)=2t(n/2)+O(n)t(n)=O(nlogn)16n=8的FFT蝶式计算图:图3.1FFT蝶式计算图n=6的FFT递归计算流程图:图3.2FFT递归计算流程图3.2流程图16开始计算出前size_x/2个exp(-j*2π*k/size_x)个值，即W的值输入序列对应值（例如5+j3，输入53）输入序列长度size_x飞级数i>=？级数i加1是输出fft结果序列结束否该级该组起始下标j>=？计算出该级需要的W的个数l是否该级该组元素序数k>
8、=？组起始下标加2*lK加1是X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]-1否16四．源程序代码及运行结果4.1源程序代码/************FFT***********/#include//整个程序输入和输出利用同一个空间x[N]，节约空间#include#include#defineN1000//定义输入或者输出空间的最大长度typedefstruct{doublereal;dou
