第四章学习目标
理解按时间抽选的基 -2FFT算法的算法原理、运算流图、所需计算量和算法特点
理解按频率抽选的基 -2FFT算法的算法原理、运算流图、所需计算量和算法特点
理解 IFFT算法
了解混合基、分裂基和基 -4FFT算法
了解 CZT算法
理解线性卷积的 FFT算法及分段卷积方法本章作业练习
P200:
1
2
3
7
9
13
第四章 快速傅里叶变换
FFT,Fast Fourier Transform
1965年,Cooley,Tukey
,机器计算傅里叶级数的一种算法,
一、直接计算 DFT的问题及改进途径
1
0
:
( ) [ ( ) ] ( ) ( )
N
nk
NN
n
DF T
X k DF T x n x n W R k

1
0
:
1
( ) [ ( ) ] ( ) ( )
N
nk
NN
k
I DF T
x n I DF T X k X k W R n
N

()N x n点有限长序列运算量 复数乘法 复数加法一个 X(k) N N – 1
N个 X(k)
(N点 DFT)
N 2 N (N – 1)
实数乘法 实数加法一次复乘 4 2
一次复加 2
一个 X (k) 4N 2N+2 (N – 1)=2 (2N – 1)
N个 X (k)
(N点 DFT)
4N 2 2N (2N – 1)
1
0
()
N
nk
n
x n W
a j b c j d a c b d j a d c b
nkNW 的特性
* ( ) ( ) ( )n k n k N n k n N kN N N NW W W W对称性
( ) ( ) n k N n k n N kN N NW W W周期性
n k m n kN m NWW?可约性 //n k n k mN N mWW?
0 / 2 ( / 2 ) 1 1N k N kN N N NW W W W特殊点：
2j n k
nk N
NWe

N k nk
NNWW
n N n kNNWW?
2j mn k
mNe

2
2 1
Nj
jNee

FFT算法分类,
时间抽选法
DIT,Decimation-In-Time
频率抽选法
DIF,Decimation-In-Frequency
FFT
D F T D F T
D F T D F T?
算法的基本思想：
利用 系数的特性，合并 运算中的某些项，
把长序列 短序列,从而减少其运算量。