文档介绍：李洁《数字信号处理》2005®
数字信号处理
Digital Signal Processing
第四章快速Fourier变换(FFT)
主讲教师:李洁
首先,FFT并不是一种新的Fourier变换,只是DFT的一种快速算法。
N −1
kn 6
X (k) = DFT[x(n)] = ∑ x(n)WN k = 0,1,L, N −1 W8
5 7
n=0 W8 W8
kn
直接计算DFT 由于WN 的周期性和对
0
W8
称性,会使计算过程出现许多冗余 4
W8
直接计算DFT总共需要N2次
3 W 1
! W8 8
复数乘法和( )次复数 2
N N-1 D W
AD 8
加法! B
RY
VE
2000
1500 N DFT Radix-2
DFT ∝ N2
1000 4 16 4
FFT ∝ N log2N
500 32 1024 80
128 16384 448
0
Number of Operations 0 10203040 1024 1048576 5120
Number of samples, N
李洁-- 《数字信号处理》-- 第四章快速Fourier变换 2 / 30
Digital Signal Processing__Jie Li
2005® 1
李洁《数字信号处理》2005®
例
李洁-- 《数字信号处理》-- 第四章快速Fourier变换 3 / 30
§ 基2FFT算法当当当N=2M时,???
1. m 怎样减少DFT的计算量?
WN 的特性 22ππ
−+jmlN() − jm
mlN+ NN m
周期性 WeNN=== e W
N
−m N −m N −m m m+ m
= ( )* = 2 =
对称性 W N W N W N W N W N −W N
nk = mnk nk = nk / m
可约性 W N W mN W N W N / m
6 12
W16 13
W8 11 W16
W16
5 7 10 14
W8 W8 W16 W16
15
W 9 W16
0 16
W8 0
4 8 W16
W8 W16
1
7 W16
W16
3 1 2
W8 6 W
W8 W16 16
5 3
2 W16 4 W16
W8 W16
李洁-- 《数字信号处理》-- 第四章快速Fourier变换 4 / 30
Digital Signal Processing__Jie Li
2005® 2
李洁《数字信号处理》2005®
2. 时域抽取法基2FFT基本原理
N −1
kn
X (k) = DFT[x(n)] = ∑ x(n)WN k = 0,1,L, N −1
n=0 6
W8
5 7
W8 W8
x(n)
1 0
W8
4
W8
0 1 2 3 4 5 6 7 8 9 10 n
3 1
0 N W8 W8
3 2
kn W
X (k) = x (r) , k = 0,1,2,3 8
x1(r) = x(2r), r = 0,1,2,3 1 ∑ 1 W 4
n=0
3 2π 2π
kn − j kn − j 2kn
x (r) = x(2r +1), r = 0,1,2,3 X (k) = x (r) , k = 0,1,2,3 kn = e 4 = e 8 = 2kn
2 2 ∑ 2 W 4 W 4 W 8
n=0
7
X (k) = x(n) kn = x(0) 0k + x(2) 2k + x(4) 4k + x(6) 6k + x(1) 1k + x(3) 3k + x(5) 5k + x(7) 7k
∑ W 8 W 8 W 8 W 8 W 8 W 8 W 8 W 8 W 8
n=0
= (x(0) 0k + x(2) 2k + x(4) 4k + x(6) 6k) + 1k (x(1) 0k + x(3) 2k + x(5) 4k + x(7) 6k)
W 8 W 8 W 8 W 8 W 8 W 8 W 8 W 8 W 8
= (x(0) 0k + x(2) 1k + x(4) 2k + x(6) 3k) + 1k (x(1) 0k + x(3) 1k + x(5) 2k + x(7) 3k)
W