《数字信号处理》课程教学课件（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

S 4-2直接计算DFT的问题和改善DFT运算效率的途径二、改善DFT运算效率的基本途径1.利用Wkm的特性Wk(N-n)=W-kn（共轭）对称性EWNN=Wn(k+N)Wk(n+M)周期性NA

二、改善DFT运算效率的基本途径 ① WN k(Nn ) WN kn (WN kn )  （共轭）对称性 1.利用WN kn的特性 ② WN kn WN k(nN) WN n(kN) 周期性 §4-2 直接计算DFT的问题和改善 DFT运算效率的途径

解决问题的思路mWi2WiaWieWi4WioWi对称性Wi6!WieWeRe[W" ]woWoW?WeWi?1周期性WeWeW?WeWeWa参考P96图3-21

解决问题的思路 14 W16 15 W16 Re[ ] 16 Wm 16 Im[ ] Wm 0 W16 1 W16 2 W16 3 4 W16 W16 5 W16 6 W16 7 W16 8 W16 9 W16 10 W16 11 W16 12 W16 13 W16 17 W16 1 W16  3 W8 18 W32 参考P96 图3-21 对称性 周期性

Revisit the first example+3W+3W+2W°X[0] = 2V°10X[1] = 2W°3WW3+X[2] = 2W0A3W)+ 3W+2gX[3] = 2W° / 3W3W.21+3An observation used in the earlierFFTwork：e.g.戈泽尔算法

Revisit the first example 0 0 0 0 4 4 4 4 0 1 2 3 4 4 4 4 0 2 4 6 4 4 4 4 0 3 6 9 4 4 4 4 [0] 2 3 3 2 10 [1] 2 3 3 2 1 [2] 2 3 3 2 0 [3] 2 3 3 2 1 X W W W W X W W W W j X W W W W X W W W W j An observation used in the earlier FFT work：e.g. 戈泽尔算法

$ 4-2直接计算DFT的问题和改善DFT运算效率的途径2.长序列分解Decimation-in-TimeN(DIT)4NN2Decimation-in4NFrequencyN(DIF)N42N4N2N?N2(N)(N)NN×8x4:2.228448N2N2N2N2222322

2．长序列分解 N 2 N 4 N 2 N 4 N 4 N 4 N Decimation-in-Time (DIT) Decimation-in￾Frequency (DIF) 2 2 2 2 2 2 2 N N N N                2 2 N v N 2 2  2 3 2 N           8 8 8 2 2 N N 2 2 2 N 4 4 4 2 2 N N          §4-2 直接计算DFT的问题和改善 DFT运算效率的途径

解决问题的途径和算法(since1965)分而治之** 按时间抽取 （Decimation in time）DIT-FFT[[2r]Nr[n] -1r = 0,1, 2a[2r + 1]将时域序列逐-Cooley-Tukey(库利-图基,美,1965）次分解为一组子序列，利用旋转因子的特**按频率抽取 (Decimation in frequency) DIF-FFT性，由子序列[X[2k;]的离散傅立叶X[K] X[2k + 1]变换来实现整个序列的离散-Sand-Tukey（桑德-图基,美,1966）傅立叶变换**分裂基方法Duhamel-Hollmann（杜哈梅尔-霍尔曼,法,1984)

将时域序列逐 次分解为一组 子序列，利用 旋转因子的特 性，由子序列 的离散傅立叶 变换来实现整 个序列的离散 傅立叶变换 解决问题的途径和算法 (since 1965) 分而治之 ** 按时间抽取 (Decimation in time) DIT-FFT [2 ] [ ] 0,1, , 1 [2 1] 2 x r N x n r x r - Cooley-Tukey (库利-图基,美,1965 ） ** 按频率抽取 (Decimation in frequency) DIF-FFT [2 ] [ ] [2 1] X k X k X k - Sand-Tukey (桑德-图基,美,1966 ） ** 分裂基方法 - Duhamel-Hollmann (杜哈梅尔-霍尔曼,法,1984)