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

WORD格式-可编辑 串行 FFT 递归算法（蝶式递归计算原理）求傅里叶变换 摘要 FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的 奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理 论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可 以说是进了一大步。 设 xn为 N 项的复数序列，由 DFT 变换，任一 X（m）的计算都需要 N 次复数乘法 和 N-1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法 等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算” （四次实 数乘法和四次实数加法） ，那么求出 N 项复数序列的 X（m）,即 N 点 DFT 变换大约就需要 N2 次运算。当 N1024 点甚至更多的时候，需要 N21048576 次运算，在 FFT 中，利用 WN 的周期性和对称性，把一个 N 项序列（设 N2k,k 为正整数） ，分为两个 N/2 项的子序 列，每个 N/2 点 DFT 变换需要（N/2）2 次运算，再用 N 次运算把两个 N/2 点的 DFT 变 换组合成一个 N 点的 DFT 变换。这样变换以后，总的运算次数就变成N2（N/2） 2NN2/2。继续上面的例子，N1024 时，总的运算次数就变成了 525312 次，节省了 大约 50的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两 两一组的 DFT 运算单元， 那么 N 点的 DFT 变换就只需要 Nlog2N次的运算， 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,., bb 0 。为 n b ,b ,.,bT和 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 2la 1 a n 1 4la 2 a n 2 2l n 1 2 a n 1 a n 1 2 22 laa 2laaa 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 klaa 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 1ka k 因此，向量b 1,b3,., b n 1 是 a0 a n , a 1 a n1,., 22 n 1 k 0 a 0 2l 1a 1 22l 1a 2 2 n 1 2l 1 2 a n 1 2 n2l 1 2 a n 2 n 1 2l 1 2 4l2 a n 1 n 1 2l 1a 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 klkaa nk k k 0 2 n1 2 n 1 2 l0, 1,,n 2 1 Ta n1 a n 1 T的DFT 2 对于以上的分析可画出如图 2.2 所示的离散傅里叶变换递归计算流图。 图 2.3 就是 一个按此递归方法计算的 n8 的 FFT 蝶式计算图。 专业知识-- 整理分享 WORD格式-可编辑 FFT 的蝶式递归计算图（有计算原理推出） a a 0 a0a n 2 1 a1a n 1 2 . . . . . . 1 - n a 2 -1an-1 DFTn/2 . . . a n -1 2 a a n 2 n 2 a0-a n 2 1 ω ω a1-a n 1 2 . . . - . . . ω n 2 DFTn/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） klaa展开，导出 nk k k 0 2 n 1 2 klkaa递归计算式，按此构造出了如图 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 分治递归算法 输入 aa 0,a1,,an-1; 输出 Bb 0,b1,,bn-1 Procedure RFFTa,b begin if n1 then b 0a0 else 1