同济大学：《数字信号处理（DSP）》课程教学资源（PPT课件讲稿）第四章 快速傅里叶变换（1/9）

第四章学习目标 ◆理解按时间抽选的基-2FFT算法的算法原理、运 算流图、所需计算量和算法特点 ◆理解按频率抽选的基-2FFT算法的算法原理、运 算流图、所需计算量和算法特点 ◆理解IFFT算法 ◆了解混合基、分裂基和基-4FFT算法 ◆了解CZT算法 ◆理解线性卷积的FT算法及分段卷积方法

第四章学习目标 ¨ 理解按时间抽选的基-2FFT算法的算法原理、运 算流图、所需计算量和算法特点 ¨ 理解按频率抽选的基-2FFT算法的算法原理、运 算流图、所需计算量和算法特点 ¨ 理解IFFT算法 ¨ 了解混合基、分裂基和基-4FFT算法 ¨ 了解CZT算法 ¨ 理解线性卷积的FFT算法及分段卷积方法

本章作业练习 P200: 1237 ◆13

本章作业练习 P200: ¨ 1 ¨ 2 ¨ 3 ¨ 7 ¨ 9 ¨ 13

Q第四章快速傅里叶变换 FFT: Fast Fourier Transform 1965年, Cooley, Tukey 《机器计算傅里叶级数的一种算法》

第四章 快速傅里叶变换 FFT: Fast Fourier Transform 1965年，Cooley, Tukey 《机器计算傅里叶级数的一种算法》

Q一、直按计算DFT的间题及改进途径 N点有限长序列x(m) DET X(k)=DFT[x(n)]=2x(n)WNR(k) IDET x(n)=IDFTIX(k)]=2X(K)WwRM(n)

一、直接计算DFT的问题及改进途径 1 0 : ( ) [ ( )] ( ) ( ) N nk N N n DFT X k DFT x n x n W R k      1 0 : 1 ( ) [ ( )] ( ) ( ) N nk N N k IDFT x n IDFT X k X k W R n N       N点有限长序列x(n)

运算 复数乘法复数加法 个X(k) N-1 ∑x(n)xN个X(k) N(N-1) (N点DFT) (a+jb)(c+ jd)=(ac-bd)+j(ad+cb) 实数乘法实数加法 次复乘4 一次复加 个X(k)4N 2N+2(N-1)=2(2N-1) N个(k)4N 2N(2N-1) (N点DFT

运算量 复数乘法 复数加法 一个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 n x n W   a  jbc  jd   ac  bd  j ad  cb 

W的特性W=e 对称性(Ww)=W=W(=n=WmN=6) WN.WN k W· nk 周期性WM=WN+m)=WN 可约性WW=WmWW=WMbm j-mnk 特殊点:W=1W2=-1W+N2)=-Wk

nk WN 的特性 * ( ) ( ) ( ) nk nk N n k n N k WN WN WN WN    对称性    nk (N n )k n(N k ) WN WN WN   周期性   nk mnk 可约性 WN WmN / / nk nk m WN WN m 0 / 2 ( / 2) 1 1 N k N k WN WN WN WN  特殊点：      2 j nk nk N WN e    Nk nk WN WN    nN nk WN WN    2 j mnk mN e    2 2 1 N j N j e e         

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

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