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

串行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 蝶式计算 傅里叶变换
目录
一．题目及要求 1
1
二．设计算法、算法原理 1
1
2
三．算法描述、设计步骤 4
4
5
四． 源程序代码及运行结果 7
7
12
五． 算法分析、优缺点 13
13
14
六． 总结 15
七． 参考文件 16
一．题目及要求

对给定，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换结果。

利用串行递归和蝶式递归原理，对给定向量求解傅里叶变换结果。
二．设计算法、算法原理

蝶式递归计算原理：令 为n/2次单位元根，则有 ，
将b向量偶数项 和奇数项 分别记
为 和 。
注意推导中反复使用： 。
公式图形

对于以上分析可画出图 。=8FFT蝶式计算图。
FFT蝶式递归计算图（有计算原理推出）：
递归计算流图
尤其，ｎ＝８FFT蝶式计算图（展开）：
蝶式计算图
按输入元素展开，前面将输出序列之元素 按其偶下标（）和（
）展开，导出 和递归计算式，按此结构出了图1所表示FFT递归计算步骤图。实际上，我们也能够将输入序列之元素按其偶下标（） 和几下标（）展开，则导出另一个形式FFT递归计算式 。
三．算法描述、设计步骤

SISD上FFT分治递归算法：
输入: a=(a0,a1,…,an-1); 输出: B=(b0,b1,…,bn-1)
Procedure RFFT(a,b)
begin
if n=1 then b0=a0 else
(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)for j=0 to n-1 do
()bj=uj mod n/2+zvj mod n/2
()z=zω