文档介绍：快速傅里叶变换概要
快速傅里叶变换概要
快速傅里叶变换概要
实验二 快速傅立叶变换
一、 实验目的
1． 学****和掌握快速傅立叶变换（ FFT）的实现过程和编程技术
2． 运用 FFT 分析正弦信号的频谱
3． 测试 FFT 的运算时间，比较 FFT 与 DFT的运算速度，获得对 FFT“快速”的感性认识。
4． 锻炼和提高数字信号处理的程序设计和调试能力。
二、实验原理与方法
FFT 并不是与 DFT 不同的另一种变换，而是为了减少
DFT 运算次数的一种快速算法。它是对
DFT
变换式进行一次次分解，使其成为若干小点数的组合，从而减少运算量。常用的
FFT是以 2为
基数的，其长度=2M。它的效率高，程序简单，使用非常方便，当要变换的序列长度不等于
2
N
的整数次方时， 为了使用以 2 为基数的 FFT，可以用末尾补零的方法，
使其长度延长至 2 的整数
次方。
本实验运用时间抽取基
2 FFT，其原理、信号流图和运算过程可参阅课堂笔记、教材和其它教科
书。 FFT 的实现要比
DFT复杂，通常采用三个嵌套循环来实现。最外面的循环是分级循环，
N=2M
点的 FFT 分为 M级计算。中间一层是分组循环，一级内蝶形系数
k
W 相同的蝶形构成一组。最内
层为蝶形计算的循环，一组内不同输入数据的蝶形逐个计算。编程时要注意各级蝶形组之间的
k
间隔、组内蝶形之间间隔、以及系数 W 变化。有不少书中有 FFT 程序可供参考，但要注意理解
和弄懂，不可一味照搬，要尽量自己去编。
三、实验内容
1．设计说明
编制时间抽取基 2 FFT 程序计算前面 DFT程序分析过的正弦信号，与 DFT
计算的结果进行比较，以验证所编程序的正确性。
快速傅里叶变换概要
快速傅里叶变换概要
快速傅里叶变换概要
FFT 为复数运算，若用实数运算来实现， 需要设置两个数组来存放输入输出数据。 其中一个用于
存放数据的实部，另一个存放数据的虚部。正弦输入信号为实数，则令其虚部为零。同样，碟
形运算也要化成实数来进行，分别算出实部和虚部。当然也可以直接用复数数组和语句实现。
程序设计的难点和重点在于要合理安排和正确设置碟形运算的分级循环、级内分组循环和组内
k
分碟形循环。要注意乘法系数 WN 的变化以及各循环变量的变化和调整。
程序中，在进行 FFT 计算之前，先要将输入数据排列成二进制倒序的形式，这可通过将有关数
据相互换位来实现。
正弦抽样信号的产生和输出频谱图的绘制与前面的 DFT程序相同。
2．实验步骤
（ 1） 将编制的程序输入计算机，调试、运行正确。即输入实验一中的 1～ 2 组数
据，看 FFT 输出谱线的结果是否与前面 DFT 的结果一致。
（ 2） 在不同的 FFT 长度下（可