串行FFT递归算法(蝶式递归计算原理)求傅里叶变换

串行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+N^2/2。继续上面的例子，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算法描述..........................................................................................................................................43.2流程图..............................................................................................................................................5四．源程序代码及运行结果.......................................................................................................................74.1源程序代码......................................................................................................................................74.2运行结果........................................................................................................................................12五．算法分析、优缺点.............................................................................................................................135.1算法分析........................................................................................................................................135.2优缺点............................................................................................................................................14六．总结.....................................................................................................................................................15七．参考文献.............................................................................................................................................161一．题目及要求1.1题目对给定的)23,27,16,8,30,74,22,21(，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。1.2要求利用串行递归与蝶式递归原理，对给定的向量求解傅里叶变换的结果。二．设计算法、算法原理2.1算法原理与设计蝶式递归计算原理：令为n/2次单位元根，则有，将b向量的偶数项和奇数项分别记为和。注意推导中反复使用：。图2.1公式图形)2//(2~nie＝2~＝Tnbbb),...,,(220Tnbbb),...,,(131Tnbbb),...,,(1102Tnbbb),...,,(1102ppsnnn,1,1,1ln2/22.2设计步骤DFTaaaaaabbbTnTnnnn的是因此，向量),...,,(),...,,(11110220222DFTaaaaaabbbTnTnnnnn的是因此，向量))(),...,(),((),...,,(1111101312222对于以上的分析可画出如图2.2所示的离散傅里叶变换递归计算流图。图2.3就是一个按此递归方法计算的n=8的FFT蝶式计算图。1,,1,0)(~)(~)(~)(~)()()()()(210111222110111222411201122412112241201022222222222222222222nkkklknlllnlllnllllllnkklklllaaaaaaaaaaaaaaaaaaaaaaaaaaabbnnnnnnnnnnnnnnnnnn偶数时：1,,1,0)(~)(~)(~)(~)()()()()(21011112222110111122224112011121211122241201)12(11)12(1)12(1)12(12)12(2112010)12(12222222222222222222222222222nkkkklknlllnlllnlllllnlnlllllnkkkllllaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbnnnnnnnnnnnnnnnnnnnnnnnnnnn奇数时：3FFT的蝶式递归计算图（有计算原理推出）：图2.2递归计算流图特别的，ｎ＝８的FFT蝶式计算图（展开的）：图2.3蝶式计算图按输入元素ka展开，前面将输出序列之元素jb按其偶下标（lj2）和（12lj）展开，导出1022)(~nnkkklkaa和1022)(~nnkkkklkaa递归计算式，按此构造出了如图1所示的FFT递归计算流程图。事实上，我们也可以将输入序列之元素ka按其偶下标（k2）...a0a1an-1DFT(n/2)DFT(n/2).........+++---1-a(a)ωn2-1n2-1n-1-a(a)ωn2+11-aan20+aan2-1n-1+aan20+aan2+11an2-1an2an2+1......ωn2-1ω4和几下标（12k）展开，则导出另一种形式的FFT递归计算式10nkkkjjawb。三．算法描述、设计流程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ωendforendifend注:(1)算法时间复杂度t(n)=2t(n/2)+O(n)t(n)=O(nlogn)5n=8的FFT蝶式计算图:图3.1FFT蝶式计算图n=6的FFT递归计算流程图:图3.2FFT递归计算流程图3.2流程图6飞是否是否是否输入序列长度size_x输入序列对应值（例如5+j3，输入53）计算出前size_x/2个exp(-j*2π*k/size_x)个值，即W的值级数i=错误!未找到引用源。？输出fft结果序列开始结束计算