《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-1 引言 §4-2 直接计算DFT的问题和改善DFT运算效率的途径

第四章快速傅里叶变换

第四章 快速傅里叶变换

学习要点·快速计算DFT的基本思路和方法，基2时间抽取FFT算法基2频率抽取FFT算法·实序列FFT算法分裂基FFT算法Chirp-Z 变换·FFT的应用：卷积、相关计算

3 / 30 学习要点 • 快速计算DFT的基本思路和方法 • 基2时间抽取FFT算法 • 基2频率抽取FFT算法 • 实序列FFT算法 • 分裂基FFT算法 • Chirp-Z 变换 • FFT的应用：卷积、相关计算

S4-1 引言0<n≤N-1DFT: x(n) X(k)0≤k≤N-1频域分析：一种有效的信号分析工具X(k) = X(ej°)2元0:NX(ej)～ X.(ejo)= FT[x.(nT)问题：有效的一→快速的→实时处理Vx(n),0≤n≤N-1↓ Cooley-Tukey, 19651FFTEX(k)0≤k≤N-1

4 / 30 §4-1 引言 频域分析：一种有效的信号分析工具 DFT: x(n)  X(k) 0  n  N 1 0  k  N 1 k N j X k X e    2 ( ) ( )         j j X e X e FT x nT a a         △ 问题： x(n), 0  n  N 1 X (k) 0  k  N 1 有效的快速的实时处理 FFT  CooleyTukey,1965

S 4-2直接计算DFT的问题和改善DFT运算效率的途径一、直接计算DFT的问题N-1X(k)=Zx(n)Wkm0≤k≤N-1n=0P124N-X(k)W-knZ0<n≤N-1c(mNNk-0设N=10248092*: N2=10665.5×106= 10665.5×106+: N(N-I)

一、直接计算DFT的问题 ( ) ( ) 0 1 1 0        X k x n W k N N n kn N ( ) ( ) N kn N k x n X k W n N N 1 0 1 0 1 §4-2 直接计算DFT的问题和改善 DFT运算效率的途径 2 ：N ：N(N 1) 6 6 10 65.510 6 6 10 65.510 设 N 1024 8092 P124

问题的提出Example:compute 4点序列[2,3,3,2]之DFTN-1X[m] = a[K;]W",m=0,1,..,N -1k=0terrible!X[0] = 2 + 3W6-+ 3W% -+2W)=10NDFTX[1] = 2W% +-3-+ 3W?-+-21V3416=-1- J321024X[2] = 2W% +-3-+ 3WVA-+21V = 0212816384X[3] = 2 +-33+ 3W---2?10241048576=-1+2复数乘法:N2复数加法:N（N-1)如何提高计算效率？

1 0 [ ] [ ] , 0,1, , 1 N km N k X m x kW m N 0 0 0 0 0 1 2 3 0 2 4 6 0 3 6 9 [0] 2 3 3 2 10 [1] 2 3 3 2 1 [2] 2 3 3 2 0 [3] 2 3 3 2 1 N N N N N N N N N N N N N N N N X W W W W X W W W W j X W W W W X W W W W j 复数加法:N (N  1) 复数乘法: N 2 Example: compute 4点序列{2, 3, 3, 2}之DFT 如何提高计算效率？ 问题的提出 N DFT 4 16 32 1024 128 16384 1024 1048576