快速傅里叶变换FFT原理与实现快速傅里叶变换FFT原理与实现.pdf

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)次实数加法。 旋转因子WN 的特性 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’取值为0~N/2-1。对式(7)化简 可得： 综合以上推导我们可以得到如下结论：一个N 点的DFT 变换过程可以用两 个N/2 点的DFT 变换过程来表示，其具体公式如式(10)所示DFT 快速算法的迭 代公式： 上式中X(k’)为偶数项分支的离散傅立叶变换，X(k’’)为奇数项分支的离散傅立 叶变换。 式(10)的计算过程可以用图1 的蝶形算法流图直观地表示出来。 图1 时间抽取法 蝶形运算流图 在图1 中，输入为两个N/2 点的DFT 输出为一个N 点的DFT 结果，输入输出 点数一致。运用这种表示方法，8 点的DFT 可以用图2 来表示： 图2 8 点DFT 的4 点分解 根据公式(10)，一个N 点的DFT 可以由两个N/2 点的DFT 运算构成，再结合图 1 的蝶形信号流图可以得到图2 的8 点DFT 的第一次分解。该分解可以用以下 几个步骤来描述： 1.将N 点的输入序列按奇偶分为2 组分别为N/2 点的序列 2.分别对1 中的每组序列进行DFT 变换得到两组点数为N/2 的DFT 变换值X1 和X2 3.按照蝶形信号流图将2 的结果组合为一个N 点的DFT 变换结果 根据式(10)我们可以对图2 中的4 点DFT 进一步分解，得到图3 的结果，分解 步骤和前