快速傅里叶变换
快速傅里叶变换（FFT ）是根据计算量的最小化原理来设计和实施离散傅里叶变换(DFT)计算的方法。1965年，库利（T.W.Cooley ）和图基（J.W.tukey ）发表了著名的《计算机计算傅里叶级数的一种算法》论文。从此掀起了快速傅里叶变换计算方法研究的热潮。快速傅里叶变换（FFT ）的出现，实现了快速、高效的信号分析和信号处理，为离散傅里叶变换(DFT)的广泛应用奠定了基础。
1.1离散傅里叶变换(DFT)的计算
设x(n)是一个长度为M 的有限长序列， 则定义x(n)的N 点离散傅里叶变换为
∑-===1
0)()]([)(N n kn N
W n x n x DFT k X  其中
由于计算一个X(k)值需要N 次复乘法和(N-1)次复数加法，因而计算N 个X(k)值，共需N2次复乘法和N(N-1)
次复加法。每次复乘法包括4次实数乘法和2次实数加法，每次复加法包括2次实数加法，因此计算N 点的DFT 共需要4N2次实数乘法和(2N2+2N ·(N-1))次实数加法。当N 很大时，这是一个非常大的计算量。
1.2减少DFT 计算量的方法
减少DFT 的计算量的主要途径是利用k N W 的性质和计算表达式的组合使用，
其本质是减少DFT 计算的点数N 以便减少DFT 的计算量。    k N W 的性质：
（1）对称性：                      (2)周期性：  (3) 可约性：  (4) 特殊点： 选择其中一个证明N N j k N j N k N j N k N e e e W 222)2(22πππ--+-+==ππj k N j e e --=2k N j e π2--=k N W -=
FFT 算法是基于可以将一个长度为N 的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这一原理产生了许多不同的算法，但它们在计算速度上均取得了大致相当的改善。
0,1,,1
k N =
-()*nk nk N N W W -=()()nk N n k n N k N N N
W W W ++==nk mnk N mN W W =//nk nk m N N m
W W =01N W =/21N N W =-(/2)k N k N N
W W +=-
在这里讨论两类基本的FFT 算法。
第一类称为按时间抽取(Decimation-in-Time)的基2FFT 算法
第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT 算法
2.1 按时间抽选(DIT)的基-2 FFT 算法(库利·图基算法)
这种算法简称为时间抽选FFT 算法，其基本出发点是，利用旋转因子WNk 的对称性和周期性，将一个大的DFT 分解成一些逐次变小的DFT 来计算。    分解过程遵循两条规则：
①对时间进行偶奇分解；      ②对频率进行前后分解。
傅里叶变换公式证明
设N ＝2M ，M 为正整数。为了推导方便，取N ＝23＝8，即离散时间信号为
先按n 的奇偶分成以下两组：
分别表示为：
利用系数    的可约性：
上式中的G(k)和H(k)都是N/2点的DFT 。
有N 点．而用上式计算得到的只是      的前一半项数的结果，要得到全部的值，还必须应用系数的周期性
因为                                          所以
nk N W ()22222
/2j N j N N N W e e W ππ--⋅
===()X k ()
X k ()2/2/2N r k rk N N W W +=()/22
N k N k k N N N N W W W W +==-
由上面的公式可以得到下面的信号流程图：
前面把原来N点DFT的计算分解成两个N/2点DFT的计算。照此可进一步把每个N/2点DFT的计算再各分解成两个N/4点DFT的计算。具体说来，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)，x(5)，x(7)}分为{x(0)，x(4) | x(2)，x(6)}和{x(1)，x(5) | x(3)，x(7)}。这样，原信号序列被分成{x(0)，x(4) | x(2)，x(6) I x(1)，x(5) I x(3)，x(7)}4个2项信号。G(k)和H(k)分别计算如下:
因为N=8，所以N/4点的DFT就是2点的DFT，不能再分解了。
将2点DFT的信号流程图移入上图，得到如图所示的8点时间抽选的完整的FFT流程图。
2.2运算量分析：
如图所示蝶形的一般形式表示为：其输入和输出之间满足下列关系：
从上式可以看出完成一个蝶形计算需一次复数乘法和两次复数加法。由按时间抽选法FFT的流图可见，共有M级蝶形，每级都由N/2个蝶形运算组成，因此总
的运算量为：
大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算DFT需要的乘法次数为αD=N2，于是有
例如，当N=1024时，则：205，即直接计算DFT所需复数乘法次数约为FFT的205倍。显然，N越大，FFT的速度优势越大。
下表列出了不同N值所对应的两种计算方法的复数乘法次数和它们的比值。
3.1频率抽选基2FFT算法
频率抽选基2FFT算法简称为频率抽选，它的推导过程遵循两个规则：①对时间前后分；②对频率偶奇分。
设N＝2M，M为正整数。为推导方便，取N=23＝8。
首先，根据规则(1)，将x(n)分成前一半和后一半，即
x(n)＝{x(0), x(1), x(2), x(3), I x(4), x(5), x(6), x(7)}
这样
虽然包含两个N/2点求和公式，但是在每个求和公式中出现的是WNkn，而不是WN/2kn，因此这两个求和公式都不是N/2点的DFT。如果合并这两个求和公式，并利用则得：
其次，按规则(2)，将频率偶奇分，即X(k)={X(0), X(2), X(4), X(6), | X(1), X(3), X(5), X(7)}。如果用X(2r)和X(2r+1)分别表示频率的偶数项和奇数项，则有
令得

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。