电子科技大学数字信号处理实验报告FFT的实现

电 子 科 技 大 学 实 验 报 告 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 一 、 实 验 室 名 称 ： 数 字 信 号 处 理 实 验 室 二 、 实 验 项 目 名 称 ： FFT 的 实 现 三 、 实 验 原 理 ： 一 ． FFT 算 法 思 想 ： 1． DFT 的 定 义 ： 对 于 有 限 长 离 散 数 字 信 号 {x[n]}， 0  n  N-1， 其 离 散 谱 {x[k]}可 以 由 离散 付 氏 变 换 （ DFT） 求 得 。 DFT 的 定 义 为 ： 210[ ][ ]NjnkNnX kx n e ， k=0,1,… N-1 通 常 令2j NNeW， 称 为 旋 转 因 子 。 2． 直 接 计 算 DFT 的 问 题 及 FFT 的 基 本 思 想 ： 由DFT 的 定 义 可 以 看 出 ， 在 x[n]为 复 数 序 列 的 情 况 下 ， 完 全 直 接 运 算 N 点DFT 需 要 （ N-1）2次 复 数 乘 法 和 N（ N-1） 次 加 法 。 因 此 ， 对 于 一 些 相 当 大 的 N 值（ 如 1024） 来 说 ， 直 接 计 算 它 的DFT 所 作 的 计 算 量 是 很 大 的 。 FFT 的 基 本 思 想 在 于 ， 将 原 有 的 N 点 序 列 分 成 两 个 较 短 的 序 列 ， 这 些 序 列 的DFT 可 以 很 简 单 的 组 合 起 来 得 到 原 序 列 的DFT。 例 如 ， 若N 为 偶 数 ， 将 原 有 的N点 序 列 分 成 两 个 （ N/2） 点 序 列 ， 那 么 计 算 N 点 DFT 将 只 需 要 约[(N/2)2 ·2]=N2/2次 复 数 乘 法 。 即比直 接 计 算 少作 一 半乘 法 。 因 子 （ N/2）2 表示直 接 计 算 （ N/2）点 DFT 所 需 要 的 乘 法 次 数 ， 而乘 数 2 代表必须完 成 两 个 DFT。 上述处 理 方法 可 以反复 使用， 即（ N/2） 点 的 DFT 计 算 也可 以 化成 两 个 （ N/4） 点 的 DFT（ 假定 N/2为 偶 数 ）， 从而又少作 一 半的 乘 法 。 这 样一 级一 级的 划分 下 去一 直 到 最后就划分成 两 点 的 FFT 运 算 的 情 况 。 3． 基 2 按时间 抽 取 （ DIT） 的 FFT 算 法 思 想 ： 设 序 列 长 度 为2LN ， L 为 整 数 （ 如 果 序 列...