例如 10点 DFT 100次 复数乘；
1024点 DFT 1,048,576次 复数乘，即100万次的复数乘运算！
二、DFT的高效计算
j 2π
W
N
W
k N
e
e
N j 2πk
N
N
WN2
•
• WNk
0
2 k N
•WN0
WN•k
周期性 WWN0NkrNWNrNWNk1
对称性:
N WWN2N(k N2)W
n0
n0
k 0,1,....N 1
N次 复数乘 计算一个X(k)工作量： 或4N次 实数乘
( N-1)次 复数加 2N+2(N-1)=4N-2次 实数加
全部计算N个X(k) N²次 复数乘
N( N-1)次 复数加
或 4N ²次 实数乘
N(4N-2)次 实数加
结论：直接计算DFT的计算量和N的平方成正比
用下面的蝶形图也可清楚地说明这种运算。
A
A+BC X1(k)☉ •
C
B
A-BC
X2(k)☉
W
k
N•
蝶形运算符号
运算量：几次乘？几次加？ 一个蝶形运算：一次复数乘、两次复数加
经过一次时域抽取计算量：
X(k)
•☉
N
-1
X(k ) •☉ 2
复数乘： 2 ( N / 2)2 N / 2 N ( N 1) / 2
(2l
1)W
k N
(2l /2
1)
l0
l0
N / 41
N / 41
x3
(l
)W
kl N/
4
WNk
/
2
x4
(l
)W
kl N/
4
l0
l0
于是
X3(k) WNk / 2 X4(k) ,
k 0,1,... N 1 2
X1(k) X 3(k) WNk /2 X4(k)
X1(k
N
/
4)
X3(k)
碟形运算
复数加： 2N / 2( N / 2 1) 2N / 2 N 2 / 2
运算量减少近一半
以N＝8为例
x(0) ☉ x(1) ☉ x(2) ☉
.☉ .☉ .☉
☉
DFT
(N=8)
x(7) ☉
☉ X(0) ☉ X(1) ☉ X(2) ☉. ☉. ☉.
☉
☉ X(7)
直接计算需要8×8次复数乘、8×7次复数加
r0
r0
其中X1 (k)和X2 (k)分别为 x(2r)和x(2r＋1) 的N/2点DFT：
N 1 2
X1(k) x(2r)WNkr/2 DFT[x(2r)] r0
, k 0,1,... N 1 2
N 1 2
X2(k) x(2r 1)WNkr/2 DFT[x(2r 1)] r0
0 N
1
WNk
可约性:
WWNnNnkk
WmmNnk
W
nk N/
/m m
利用WN 因子的周期性和对称性，可导出一个高效的快速算法
1965年 Cooley & Tukey 奠定FFT，把长序列短分解，
使得乘法计算量由N 2 次降为
N 2 log2 N
次。
以1024点为例，计算量降为5120 次，仅为原来的4.88%。
x(0) ☉
X1(0)
x(2) ☉ DFT X1(1)
x(4) ☉ (N=4) X1(2)
•
x(6) ☉ x(1) ☉ x(3) ☉
DFT
X1(3) W80
X2(0) X2(1)
W81
•
x(5) ☉ (N=4) X2(2)
x(7) ☉
X2(3)
☉ X(0) ☉ X(1) ☉ X(2) ☉ X(3) ☉ X(4) ☉ X(5) ☉ X(6) ☉ X(7)
36次复数乘 32次复数加
3、第二次抽取
将 x1(r) 按奇偶分解成两个N/4长的子序列x3(l ) 和 x4(l )
x3 (l )
x1(2l )
,
x4 (l ) x1(2l 1)
l 0,1,... N 1 4
N / 41
N / 41
X1(k)
x1 (2l
)W
2kl N /2
x1
6
(k
)
X2(k
N
/
4)
X5(k)
W
k N
/
2
X
6
(
k
)
k 0,1,... N 1 4
经过第二次分解，将N/2点的DFT分解成两个N/4点的DFT和N/4个蝶形运算。
数字信号处理
第四章 快速傅立叶变换(FFT)
§4.1 引言 § 4.2 按时间抽取(DIT)的FFT算法 § 4.3 按频率抽取(DIF)的FFT算法 § 4.4 离散傅立叶反变换(IDFT)的快速计算方法 § 4.5 进一步减少运算量的措施
§4.1 引言
一、DFT直接计算工作量很大
N 1
N 1
X (k) x(n)WNkn {(Re x(n) ReW Im x(n) Im W ) j(Re x(n) Im W Im x(n) ReW )}
r 0,1,... N 1 2
x(n)的DFT为：
N 1
N 1
2
2
X (k)
x(n)WNkn
x(n)WNkn＝ x(2r )WN2kr x(2r 1)WNk(2r1)
n偶 数
n奇 数
r0
r0
N 1
N 1
2
2
x1
(r
)W
kr N/
2
W
k N
x2(r)WNkr/ 2 X1(k) WNk X 2(k) , k 0,1,...N 1
, k 0,1,... N 1 2
由于X1 (k)和X2 (k)都是N/2点DFT，而X (k)有N点，所以得计算后N/2点.
由于它们均以N/2为周期，且
X1(k
N) 2
N 1 2
(k N )r
x1(r )WN / 2 2
r0
X1
(k
WN
(k)
N 2
)
W 同理
k N
，因此
N X2(k 2
)
本章以基2 的FFT算法为重点
§4.2 按时间抽取(DIT)的FFT算法(库利-图基算法)
一、算法原理（时域奇偶分，频域前后分）
设x(n)长度N， N=2M， M为自然数
1、第一次抽取：
将x(n)按偶、奇分成两组，可得两各自长度为N/2的奇偶序列
x1(r) = x(2r)
x2(r) = x(2r+1)
பைடு நூலகம்
W
k N
/
2
X4(k)
k 0,1,... N 1 4
同样，将 x2 (r ) 按奇偶分解成两个N/4长的子序列 x5 (l ) 和 x6 (l )
x5 (l )
x2 (2l )
,
x6 (l ) x2 (2l 1)
l 0,1,... N 1 4
X 2 (k )
X
5
(
k
)
W
k N
/
2
X
X2(k)
X (k) X1(k) WNk X2(k),
k 0,1,... N 1 2
X1(k)☉ •
X(k
N 2
)
X1(k)
WNk
X2(k),
k 0,1,... N 1 2
X2(k)☉
W
k
N•
-1
X(k)
•☉
N X(k ) •☉ 2
这样，将一个N点DFT分解成两个N/2点 DFT。
2、蝶形运算