第四章快速傅里叶变换
有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基２DIT和基２DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。
快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法。
DFT的定义式为
)(k X =)()(1
k R W n x N N n kn
N
∑-= 在所有复指数值kn N
W 的值全部已算好的情况
下，要计算一个)(k X 需要N 次复数乘法和N －1次复数加法。算出全部N 点)(k X 共需2
N 次
复数乘法和)1(-N N 次复数加法。即计算量是与2
N 成正比的。
FFT 的基本思想：将大点数的DFT 分解为若干个小点数DFT 的组合，从而减少运算量。
N W 因子具有以下两个特性，可使
DFT 运算
量尽量分解为小点数的DFT 运算：
（1） 周期性：k
N n N kn N n
N k N W W W )()(++== （2）
对称性：k N N k N
W W
-=+)2/(
利用这两个性质，可以使DFT 运算中有些项合并，以减少乘法次数。例子：求当N ＝4时，X(2)的值
通过合并，使乘法次数由4次减少到1次，运算量减少。
FFT 的算法形式有很多种，但基本上可以
分为两大类：按时间抽取（DIT ）和按频率抽取（DIF ）。
4.1 按时间抽取（DIT ）的FTT
为了将大点数的DFT 分解为小点数的DFT 运算，要求序列的长度N 为复合数，最常用的是M
N 2=的情况（M 为正整数）。该情况下的变换称为基2FFT 。下面讨论基2情况的算法。 先将序列x(n)按奇偶项分解为两组
???=+=)
()12()()2(21r x r x r x r x 12,,1,0-=N
r
将DFT 运算也相应分为两组
=
=)]([)(n x DFT k X ∑-=10
)(N n kn N
W
n x
∑∑-=-==
1n 0
1
0)()(N n kn N
N n n kn N
W
n x W
n x 为奇数为偶数＋
∑∑-=+-=++
1
2/0)12(1
2/02)12()2(N r k r N
N r rk N
W
r x W
r x ＝
∑∑-=-=+12/0
22
12/0
21)()(N r rk
N k N N r rk N
W r x
W
W r x ＝
∑∑-=-=+12/0
2/2
1
2/02
/1)()(N r rk
N k N
N r rk
N W r x
W
W
r x ＝
（因为rk N rk N W W 2/2=） )()(21k X W k X k
N +=
其中)(1k X 、)(2k X 分别是)()(21n x n x 、的N/2点的DFT
)(1k X 12
0,)2()(1
2/02
/1
2/02
/1-≤
≤=
∑∑-=-=N k W
r x W
r x N r rk N N r rk N ＝ )(2k X 12
0,)12()(1
2/0
2/12/0
2
/2-≤
≤+=
∑∑-=-=N k W r x W
r x N r rk N N r rk N ＝ 至此，一个N 点DFT 被分解为两个N/2点的DFT 。 上面是否将全部N 点的)(k X 求解出来了？
分析：)(1k X 和)(2k X 只有N/2个点（12
,
,1,0-=N
k ）
，则由)(k X )()(21k X W k X k
N
+=只能求出)(k X 的前N/2个点的DFT ，要求出全部N 点的)(k X ，需要找出)(1k X 、)(2k X 和)2/(N k X +的关系，其中12
,
,1,0-=N k 。由式子)(k X )()(21k X W k X k
N
+=可得 )2/(N k X +)2/()2/(22
/1N k X W N k X N k N
+++=+化简得 )2/(N k X +＝)()(21k X W k X k
N
-=，12
,,1,0-=N
k 这样N 点DFT 可全部由下式确定出来：
?????-=++=)
()()2/()
()()(2121k X W k X N k X k X W k X k X k
N k
N 12,,1,0-=N k （＊） 上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运
算。
a
b
k
N
W b
W a k
N +b
W a k
N --1
图 蝶形运算符号
通过这样的分解以后，每一个N ／2点的DFT 只需要4
)2(2
2N N =次复数乘
法，两个N/2点的DFT 需要2
)2(22
2N N =次复乘，再加上将两个N ／2点
DFT 合并成为N 点DFT 时有N ／2次与W 因子相乘，一共需要
2
222
2N N N ≈+次复乘。可见，通过这样的分解，运算量节省了近一半。 因为M
N 2=，N/2仍然是偶数，因此可以对两个N/2点的DFT 再分别作进一步的分解，将两个N/2点的DFT 分解成两个N/4点的DFT 。
例如对)(1r x ，可以在按其偶数部分及奇数部分进行分解：
???=+=)
()12()()2(4131l x l x l x l x 14,,1,0-=N
l
则的运算可相应分为两组：
)(1k X ∑∑-=+-=++
1
4/0)12(2
/114/0
22
/1)12()2(N l k l N N l lk N W
l x W
l x ＝
∑∑-=-=+14/0
4/4
2
/1
4/04
/3)()(N l lk
N k N N l lk
N W l x
W
W
l x ＝
)()(42/3k X W k X k
N += 14
,
,1,0-=N k 将系数统一为以Ｎ为周期，即k
N k N W W 22/=，可得
?????-=++=)
()()4/()
()()(42314231k X W k X N k X k X W k X k X k
N k
N 14,,1,0-=N k 同样，对)(2k X 也可进行类似的分解。一直分解下去，最后是２点的DFT ，２点DFT 的运算也可用碟形符号来表示。这样，对于一个823
==N 的DFT 运算，其按时间抽取的分解过程及完整流图如下图所示。
这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。
分析上面的流图，M
N 2=，一共要进行M 次分解，构成了从x(n)到X(k)的M 级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N 次复加，则按时间抽取的M 级运算后总共需要
复数乘法次数：N N
M N m F 2log 2
2=?=
复数加法次数：N N M N a F 2log =?=
根据上面的流图，分析ＦＦＴ算法的两个特点，它们对ＦＦＴ的软硬件
构成产生很大的影响。 （１） 原位运算 也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。
（２） 变址
分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。见图。
码位倒置的变址处理
在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序