数字信号处理期末大作业 FFT 的发展史、现状及典型算法 班级 学号： 姓名： FFT 的 发 展 史 、 现 状 及 典 型 算 法 傅 里 叶 分 析 已 有 200 多 年 的 历 史 ， 目 前 FFT 及 其 校 正 算 法 在 工 程 实 际 中 仍 在广 泛 应 用 ， 展 现 了 其 不 竭 的 生 命 力 。 本 次 作 业 我 们 论 述 FFT 的 现 状 ， 发 展 史 以 及一 些 算 法 ， 去 详 细 了 解 、 扩 展 这 一 算 法 ， 巩 固 所 学 知 识 。 一 ． FFT 的 简 介 傅 里 叶 变 换 是 一 种 将 信 号 从 时 域 变 换 到 频 域 的 变 换 形 式 ，然 而 当 N 很 大 的 时候 ， 求 一 个 N 点 的 DFT 要 完 成 N*N 次 复 数 乘 法 和N*（ N-1） 次 复 数 加 法 ， 计 算 量非 常 大 ， 所 以 人 们 开 始 探 索 一 种 简 便 的 算 法 对 于 一 个 较 大 的N 进 行 傅 里 叶 变 换 。在 20 世 纪 60 年 代 由 Cooley 和 Tukey 提 出 了 快 速 傅 里 叶 变 换 算 法 ， 它是 快 速 计算 DFT 的 一 种 简 单高效的 方法 。 关于 何为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 次 运算 ， 再...
