FFT 原 理 与实现 2010-10-07 21:10:09| 分类： 数字信号处理 | 标签：fft dft |举报|字号 订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT 算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至 DFT 被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT 并不是一种新的频域特征获取方式，而是 DFT 的一种快速实现算法。本文就 FFT 的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出 DFT 的计算公式： 其中x(n)表示输入的离散数字信号序列，WN 为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设 x(n)来自于低通采样，采样频率为 fs，那么 X(k)表示了从-fs/2 率开始，频率间隔为 fs/N,到fs/2-fs/N 截至的N 个频率点的相对幅度。因为 DFT 计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即 X(k+N)=X(k)。因此任意取连续的N 个点均可以表示 DFT 的计算效果，负频率成分比较抽象，难于理解，根据 X(k)的周期特性，于是我们又可以认为 X(k)表示了从零频率开始，频率间隔为 fs/N,到fs-fs/N截至的N 个频率点的相对幅度。 N 点 DFT的计算量 根据(1)式给出的DFT 计算公式，我们可以知道每计算一个频率点X(k)均需要进行N 次复数乘法和N-1 次复数加法，计算N 各点的X(k)共需要N^2 次复数乘法和N*(N-1)次复数加法。当 x(n)为实数的情况下，计算N 点的DFT 需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子 W N 的特性 1.WN 的对称性 2.WN 的周期性 3.WN 的可约性 根据以上这些性质，我们可以得到式(5)的一系列有用结果 基-2 FFT 算法推导 假设采样序列点数为 N=2^L，L 为整数，如果不满足这个条件可以人为地添加若干个0 以使采样序列点数满足这一要求。首先我们将序列 x(n)按照奇偶分为两组如下： 于是根据DFT 计算公式(1)有： 至此，我们将一个N 点的DFT 转化为了式(7)的形式，此时k 的取值为0 到N-1,现在分为两段来讨论，当k 为0～N/2-1 的时候，因为x1(r)，x2(r)为N/2 点的序列，因此，此时式(7)可以写为： 而当 k 取值为N/2~N-1 时，k 用k’+N/2 取代，k’...
