第四章学习目标 ◆理解按时间抽选的基-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 jbc jd ac bd j ad cb