N /4 1

l 0
2 kl x3 (l )WN /2
N /4 1

l 0
(2 l 1) x4 (l )WNk /2 N /4 1
N /4 1

l 0
x3 (l )W
kl N /4
W
k N /2

l 0
kl x4 (l )WN /4
X 3 (k ) WNk /2 X 4 (k )
第4章 快速傅里叶变换(FFT)
当 N 1 时，N(N－1)≈N2。由上述可见，N点
DFT的乘法和加法运算次数均为N2。当N较大时，运算 量相当可观。例如N=1024时，N2=1 048 576。这对于 实时信号处理来说，必将对处理设备的计算速度提出 难以实现的要求。所以，必须减少其运算量，才能使
k
N 2
k ，因此 WN
X (k ) X 1 (k ) WNk X 2 (k )
k 0,1,2,
, N -1
第4章 快速傅里叶变换(FFT)
X (k ) X 1 (k ) WNk X 2 (k )，
N X (k ) X 1 (k ) WNk X 2 (k )， 2
(4.2.11)
其中：
X 5 (k ) X 6 (k )
N / 4 1

l 0 l 0
x5 (l )WNkl/ 4 DFT[ x5 (l )]N x6 (l )WNkl/ 4 DFT[ x6 (l )]N
4
N / 4 1

4
x5 (l ) x2 (2l ) ，l 0， 1， x6 (l ) x2 (2l 1)
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言
4.2 基2FFT算法
4.3 进一步减少运算量的措施 4.4 其他快速算法简介
第4章 快速傅里叶变换(FFT)
4.1 引
言
DFT是数字信号分析与处理中的一种重要变换。但
直接计算DFT，当N较大时，计算量太大，所以在快速
傅里叶变换FFT(Fast Fourier Transform)出现以前，直
数乘法和两次复数加法运算。由图4.2.2容易看出，经过 一次分解后，计算1个N点DFT共需要计算两个N/2点DFT 和N/2个蝶形运算。而计算一个N/2点DFT需要(N/2)2次复 数乘法和N/2(N/2－1)次复数加法。所以，按图4.2.2计算
N点DFT时，总共需要的复数乘法次数为
N2 N N N ( N 1) 2 2 2 2 2 N 1
第4章 快速傅里叶变换(FFT)
4.2 基2FFT
4.2.1 直接计算DFT的特点及减少运算量的基本
有限长序列x(n)的N点DFT为
kn X (k ) x(n)WN n 0 N 1
k 0， 1， ， N 1
（4.2.1）
考虑x(n)为复数序列的一般情况，对某一个k值，直接按 (4.2.1)式计算X(k)的1个值需要N次复数乘法和 (N－1)次复数加法。因此，计算X(k)的所有N个值，共需N2次 复数乘法和N(N－1)次复数加法运算。
X 2 (k )
N / 2 1

r 0
kr x1 (r )WN / 2 DFT[ x1 (r )]N
2
(4.2.5)
N / 21

r 0
kr x2 (r )WN / 2 DFT[ x2 (r )]N
2
(4.2.6)
由于X1(k)和X2(k)均以N/2为周期，且WN X(k)又可表示为
DFT
如前所述，N点DFT的复乘法次数等于N2。显然， 把N点DFT分解为几个较短的DFT，可使乘法次数大大
第4章 快速傅里叶变换(FFT)
另外，旋转因子具有明显的周期性和对称性。其周期性表现为
mlN WN e j 2π ( mlN ) N
e
j
2π m N
m WN
其对称性表现为
N m * m m N m [ W ] W WN WN 或者 N N
k 0， 1， ，
N 1 2
(4.2.7)
(4.2.8)
N k 0， 1， ， 1 2
这样，就将N点DFT分解为两个N/2点DFT和(4.2.7)式以及
(4.2.8)式的运算。(4.2.7)和(4.2.8)式的运算可用图4.2.1所示
的流图符号表示，称为蝶形运算符号。采用这种图示法， 经过一次奇偶抽取分解后，N点DFT运算图可以用图4.2.2 表示。图中，N=23=8， X(0)~X(3)由(4.2.7)式给出，而 X(4)~ X(7)则由(4.2.8)式给出。
接用DFT算法进行谱分析和信号的实时处理是不切实际 的。直到1965年提出DFT的一种快速算法以后，情况才 发生了根本的变化。
第4章 快速傅里叶变换(FFT)
自从1965年库利和图基在《计算数学》杂志上发
表了著名的《机器计算傅里叶级数的一种算法》论文 后，桑德—图基等快速算法相继出现，又经人们进行 改进，很快形成一套高效计算方法，这就是现在的快 速傅里叶变换（FFT）。 这种算法使DFT的运算效率提高了1 ~ 2个数量级， 为数字信号处理技术应用于各种信号的实时处理创造
第4章 快速傅里叶变换(FFT) 4.2.3 DIT-FFT算法与直接计算DFT运算量的比较
由DIT-FFT算法的分解过程及图4.2.4可见，当N=2M 时，其运算流图应有M级蝶形，每一级都由N/2个蝶形运算 构成。因此，每一级运算都需要N/2次复数乘和N次复数加 (每个蝶形需要两次复数加法)。所以，M级运算总共需要 的复数乘次数为
x3 (l ) x1 (2l ) x4 (l ) x1 (2l 1)
l 0， 1，
N ， 1 4
第4章 快速傅里叶变换(FFT)
X1(k)又可表示为
X 1 (k )
N /4 1

l 0
x1 (2l )W
2 kl N /2

N /4 1

l 0
(2 l 1) x1 (2l 1)WNk /2
(4.2.10)
第4章 快速傅里叶变换(FFT)
用同样的方法可计算出
k X 2 (k ) X 5 (k ) WN / 2 X 6 (k ) N k X 2 k X 5 (k ) WN X ( k ) /2 6 4
N k 0， 1， ， 1 4
2
复数加法次数为
NN N N2 2 1 2 22 2 2
第4章 快速傅里叶变换(FFT)
由此可见，仅仅经过一次分解，就使运算量减少近 一半。既然这样分解对减少DFT的运算量是有效的，且
N=2M, N/2仍然是偶数，故可以对N/2点DFT再作进一步
分解。 与第一次分解相同，将x1(r)按奇偶分解成两个N/4 点的子序列x3(l)和x4(l)，即
In Time FFT，简称DIT－FFT )； 频域抽取法FFT (Decimation In Frequency FFT，简称DIF－FFT)。本节 介绍DIT－FFT 设序列x(n)的长度为N，且满足N=2M，M为自然数。 按n的奇偶把x(n)分解为两个N/2点的子序列
x1 (r ) x(2r )， x2 (r ) x(2r 1)，
kN / 4 k m W W 同理，由X3(k)和X4(k)的周期性和WN 的对称性 N /2 N /2 /2
4
最后得到：
，k 0， 1， ， N / 4 1 k X 1 (k N / 4) X 3 (k ) WN / 2 X 4 (k ) X 1 (k ) X 3 (k ) WNk / 2 X 4 (k )
kr WN /2
k N N /21

因为 所以

r 0
x(2r )W x1 (r )W
j
2 kr N

N / 2 1

r 0 k N
N / 2 1

r 0
2 kr N
W
N / 2 1

r 0

2 kr WN e
2π 2 kr N
e
j
2π kr N 2
X (k )
N /21
第4章 快速傅里叶变换(FFT)
偶数点的 N/2 DFT
序列DFT 的N/2个点
WNk
奇数点的 N/2 DFT
序列DFT 的后N/2个 点
图4.2.1 蝶形运算符号
第4章 快速傅里叶变换(FFT)
图4.2.2 8点DFT一次时域抽取分解运算流图
第4章 快速傅里叶变换(FFT)
由图4.2.1可见，要完成一个蝶形运算，需要一次复
r 0， 1 ， r 0， 1，
N ， 1 2 N ， 1 2
第4章 快速傅里叶变换(FFT)
则x(n)的DFT为 X (k ) x(n)WNkn
n 偶数 N / 2 1
n 奇数

x(n)WNkn x(2r 1)WNk (2 r 1) x2 (r )WN2 kr

r 0
x1 (r )W
kr N /2
W

r 0
kr x2 (r )WN /2
k X 1 (k ) WN X 2 (k )
k 0,1, 2,
, N -1
第4章 快速傅里叶变换(FFT)
其中Ｘ1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT, 即
X 1 (k )
N N CM M log 2 N 2 2
复数加次数为
CA N M N log2 N