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

WORD格式-可编辑 串行 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蝶式计算傅里叶变换 专业知识-- 整理分享 WORD格式-可编辑 目录 一．题目及要求 1 1.1 题目.1 二．设计算法、算法原理 1 2.1 算法原理与设计.1 2.2 设计步骤.2 三．算法描述、设计流程 4 3.1 算法描述.4 3.2 流程图.5 四． 源程序代码及运行结果 .7 4.1 源程序代码.7 4.2 运行结果12 五． 算法分析、优缺点 13 5.1 算法分析13 5.2 优缺点14 六． 总结 15 七． 参考文献 16 专业知识-- 整理分享 WORD格式-可编辑 一．题目及要求 1.1 题目 对给定的(21, 22, 74, 30, 8, 16, 27, 23)，利用串行 FFT 递归算法（蝶式递归计算原 理）计算其傅里叶变换的结果。 1.2 要求 利用串行递归与蝶式递归原理，对给定的向量求解傅里叶变换的结果。 二．设计算法、算法原理 2.1 算法原理与设计 T ,b 1 ,.,b 1 ) 和奇数项 (b 0n 将 b 向量的偶数项分别记 (b ,b ,.,b) 02n2 2 ~ ＝ e2 i/(n /2)为 n/2 次单位元根，则有 ~＝ 2，蝶式递归计算原理：令 T ,b 1,., b(b 0 ) 。为 n (b ,b ,.,b)T和 1 13n 1 2 T 注意推导中反复使用：1,1, ln1,sn pp 。 nn/2 图 2.1 公式图形 专业知识-- 整理分享 WORD格式-可编辑 2.2 设计步骤 偶数时： b l b 2l 2lka k k0 n 1 n 1 a 0 a 1 a 2 2 a n 1 2l4l 2l 2 a n a n 1 a n 2 222 22 2l4l n 1 2 a n 1 2l 2 (a 0 a n ) 2l(a 1 a n 1 ) 4l(a 2 a n 2 ) 2l n 1 2 (a n 1 a n 1 ) 2 22 ~ l(aa) ~ 2l(aa)(a 0 a n ) nn12 12 2 l n 1 ~ 2 (a n 1 2 n 1 2 a n 1 ) l0, 1,,n 2 1 ~ kl(aa) nk k k0 2 222 因此，向量(b 0 ,b 2 ,.,b n 2 )T是(a 0 a n ,a 1 a n 1 ,.,a n 1 a n 1 )T的DFT 奇数时：b l b 2l 1 (2l 1)ka k 因此，向量(b 1,b3,., b n 1) 是(( a0 a n ), (a 1 a n1),., 22 n 1 k 0 a 0 2l 1a 1 2(2l 1)a 2 2 n 1 (2l 1) 2 a n 1 2 n(2l 1) 2 a n 2 n 1 (2l 1) 2 4l2 a n 1 n 1 (2l 1)a n 1 2l 2 n 1 n 1 2 a 0 a 1 a 2 2 a n 1 2l n 1 n 1 2 a n a n 1 2 a n 1 2l 2l 22 n 1 n 1 2 (a 0 a n )(a 1 a n 1 )(a 2 a n 2 ) 2 (a n 1 a n 1 ) 2l4l2 2l 2222 ln1 n 1 l2l2 ~~~ 2 (a 0 a n )(a 1 a n 1 )(a 2 a n 2 ) 2 (a n 1 a n 1 ) 2222 ~ klk(aa) nk k k 0 2 n1 2 n 1 2 l0, 1,,n 2 1 T(a n1 a n 1)) T的DFT 2 对于以上的分析可画出如图 2.2 所示的离散傅里叶变换递归计算流图。 图 2.3 就是 一个按此递归方法计算的 n=8 的 FFT 蝶式计算图。 专业知识-- 整理分享 WORD格式-可编辑 FFT 的蝶式递归计算图（有计算原理推出）： a a + 0 a0+a n 2 + 1 a1+a n +1 2 . . . . . . + 1 - n a 2 -1+an-1 DFT(n/2) . . . a n -1 2 a a n 2 n 2 a0-a n 2 +1 ω ω (a1-a n +1 ) 2 . . . - . . . ω n 2 DFT(n/2) -1-an-1) -1 a n-1 ωn2 -1 (a n . . . 2 - 图 2.2 递归计算流图 特别的，ｎ＝８的 FFT 蝶式计算图（展开的）： 图 2.3 蝶式计算图 按输入元素a k 展开， 前面将输出序列之元素b j 按其偶下标 （j2l） 和 （j2l 1） ~ kl(aa)展开，导出 nk k k 0 2 n 1 2~ klk(aa)递归计算式，按此构造出了如图 1和 nk k k 0 2 n 1 2 所示的 FFT 递归计算流程图。 事实上， 我们也可以将输入序列之元素a k 按其偶下标 （2k） 专业知识-- 整理分享 WORD格式-可编辑 和几下标（2k1）展开，则导出另一种形式的 FFT 递归计算式b j wkja k 。 k 0 n 1 三．算法描述、设计流程 3.1 算法描述 SISD 上的 FFT 分治递归算法： 输入: a=(a 0,a1,…,an-1); 输出: B=(b 0,b1,…,bn-1) Procedure RFFT(a,b) begin if n=1 then b 0=a0 else (1)