第四章
快速傅立叶变换
Fast Fourier Transform
第一节 直接计算DFT的问题及改进途径
1、问题的提出
设有限长序列x(n)，非零值长度为N，若 对x(n)进行一次DFT运算，共需多大的运算 工作量？ 计算成本? 计算速度?
2. DFT的运算量
回忆DFT和IDFT的变换式：
X ( k ) DFT[ x( n)]
以DFT为例：
X ( k ) DFT[ x( n)]
N 1 n 0 nk x( n)W N
0 k N 1
计算机运算时（编程实现）：
k 0 k 1 k 2
0 1 ( X (0) x(0)WN 0 x(1)WN0 x( N 1)WN N 1)0
偶序列 (l 0... N 4 1) 此处，l 0,1 奇序列 偶序列 (l 0... N 4 1) 此处，l 0,1 奇序列
那么，X1(k)又可表示为
X 1 (k )
N / 4 1 l 0
2 x1 ( 2l )WN lk2 /
N / 4 1 l 0
k X (k ) X 1 (k ) WN X 2 (k ) k X ( k N / 2) X 1 ( k ) W N X 2 ( k )
k 0,, N / 2 1
得到X1(k)和X2(k)需要： 复乘：(N/2)2+ (N/2)2次 = 32次 复加：N/2(N/2-1)+N/2(N/2-1) =12+12 =24次 此外，还有4个蝶形结，每个蝶形结需要1次复乘，2次复加。 一共是：复乘4次，复加8次。 用分解的方法得到X (k)需要： 复乘：32+4 = 36次 复加：24+8 = 32次
X1 (k ) W X 2 (k )
k N
k X1 (k ) WN X 2 (k )
1个蝶形运算需要1次复乘，2次复加
分解后的运算量：
复数乘法 复数加法
一个N 点DFT
一个N / 2点DFT 两个N / 2点DFT 一个蝶形 N / 2个蝶形 总计
N2
(N / 2)2 N 2/ 2 1 N/2 N2/2 + N/2 ≈ N2/2

N次复乘，N-1次复加
运算量
一个X(k)
复数乘法 N N2
复数加法 N–1 N (N – 1)
x(n)W
n 0
N 1
nk N
N个X(k) (N点DFT)
(a+jb)(c+jd)=(ac-bd)+j(bc+ad)
实数乘法 一次复乘 一次复加 一个X (k) N个X (k) (N点DFT) 4N 4N 2 4 实数加法 2 2 2N+2 (N – 1)=2 (2N – 1) 2N (2N – 1)
N/4点 DFT
复乘：
N
2
N N 2 2
2
2
N N N N 4 4 4 4
2
2
2
2
N2 2
N2 4
FFT算法的基本思想：
利用DFT系数的特性，合并DFT运算中的某些项
把长序列DFT→短序列DFT，从而减少运算量。
rk x1 (r )WN / 2
X 1 ( N / 2 k ) X 1 (k ) X 2 ( N / 2 k ) X 2 (k )
k 又考虑到 W N 的对称性：
W
有：
( N / 2 k ) N
W
N /2 N
W W
k N
k N
前半部分
k X (k ) X 1 (k ) WN X 2 (k )
第二节
改善DFT运算效率的基本途径
kn 1、利用DFT运算的系数 W N 的固有对称性和周期
性，改善DFT的运算效率。 1）对称性 2）周期性
3）可约性
W 的特性
nk N
nk WN e
j
2 nk N
对称性
(W ) W
nk * N
nk N
W W nN WN WN nk WNNk WN nk
例：计算一个 N点DFT ，共需N2次复乘。以做一次 复乘1μs计，若N =4096，所需时间为
(4096) 16777216s 17 s
2
例：石油勘探，有24个通道的记录，每通道波形记 录长度为5秒，若每秒抽样500点/秒，
1）每道总抽样点数：500*5=2500点
2）24道总抽样点数：24*2500=6万点
3）DFT复乘运算时间：N2=(60000)2=36*108次
(60000) 36 * 10 s 3600s
2 8
由于计算量大，且要求相当大的内存，难以实现实 时处理，限制了DFT的应用。长期以来，人们一直在寻 求一种能提高DFT运算速度的方法。 FFT便是 Cooley & Tukey 在1965 年提出的的快速 算法，它可以使运算速度提高几百倍，从而使数字信号 处理学科成为一个新兴的应用学科。
nk N
N 1 n 0 nk x ( n)W N
nk x ( n)W N
n为 偶 数
n为 奇 数

N / 2 1 r 0
x(2r )W
r 0Biblioteka 2 rk NN / 2 1 r 0
x(2r 1)W
N / 2 1 r 0
( 2 r 1) k N

N / 2 1
k N
k 0,, N / 2 1
先将N=8点的DFT分解成2个4点DFT： 可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)~X(3)，由X(k)给出 X(4)~X(7)，由X(k+N/2)给出
N=8点的直接DFT的计算量为： 复乘：N2次 = 64次 复加：N(N-1)次 = 8×7=56次
其中基2表示：N=2M，M为整数.若不满足这个 条件，可以人为地加上若干零值（加零补长）使其 达到 N=2M。
2、算法步骤
分组，变量置换
X ( k ) DFT[ x( n)]
N 1 n 0 nk x( n)W N
0 k N 1
先将x(n)按n的奇偶分为两组，作变量置换:
N 1 n 0 nk x( n)W N N 1 k 0
0 k N 1 0 n N 1
1 x( n) IDFT[ X ( k )] N
X ( k )W nk
注意：
1）x(n)为复数， W nk
N
e
j
2 nk N
也为复数。
2）DFT与IDFT的计算量相当。
FFT算法分类:
时间抽选法
DIT: Decimation-In-Time
频率抽选法 DIF: Decimation-In-Frequency
第三节 按时间抽选的基2-FFT算法 1、算法原理
设输入序列长度为N=2M(M为正整数，将该序列 按时间顺序的奇偶分解为越来越短的子序列，称为 基2按时间抽取的FFT算法。也称为Coolkey-Tukey 算法。
0 11 ( X (1) x(0)WN 1 x(1)WN x( N 1)WN N 1)1
X (2) x(0)W
02 N
x(1)W
12 N
x( N 1)W
( N 1)2 N
N个点
1 k N 1 X ( N 1) x(0)WN0N 1 x(1)WNN 1 x( N 1)WN( N 1)N 1
2、将长序列DFT利用对称性和周期性分解为短 序列DFT的思路
因为DFT的运算量与N2成正比的，如果一个大 点数N的DFT能分解为若干小点数DFT的组合，则 显然可以达到减少运算工作量的效果。
N/4点 DFT N点 DFT
N/2点 DFT N/2点 DFT N/4点 DFT N/4点 DFT
…….
k 0,1,, N 2 1
( N / 2 k ) N
X ( N / 2 k ) X1 ( N / 2 k ) W
后半部分
X2 ( N / 2 k)
k X 1 (k ) WN X 2 (k )
k 0,1,, N 2 1
k X ( k ) X 1 ( k ) WN X 2 ( k )
当n=偶数时，令n=2r; 当n=奇数时，令n=2r+1; 得到：
x( 2r ) x1 ( r ) r 0,..., N 2 1 x( 2r 1) x2 ( r )
带入DFT中
X ( k ) DFT [ x ( n)]

N 1 n 0
x(n)W
N 1 n 0
却有N个点，以N为周期。要用X1(k)、X2(k)表达全部的
X (k) 值，还必须利用WN系数的周期特性。
r rk WN(/N / 2 k ) WN / 2 2
X1 ( N / 2 k )
N / 2 1 r 0
r x1 ( r )WN (/N / 2 k ) 2
N / 2 1 r 0
( N n ) k N
n ( N k ) N
nk ( n 周期性 WN WN N n ) k WN ( N k )
可约性
nk mnk WN WmN
2 j mnk mN
nk nk / WN WN / mm
j 2 N N 2

e
e
e j 1
0 ( k 特殊点： WN 1 WNN / 2 1 WNk N / 2) WN