《数字信号处理第四章1快速傅里叶变换》课件.ppt

数字信号处理 数字信号处理 * 数字信号处理 第四章学习目标 理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 理解IFFT算法 了解混合基、分裂基和基-4FFT算法 了解CZT算法 理解线性卷积的FFT算法及分段卷积方法 * 数字信号处理 第四章 快速傅里叶变换 FFT: Fast Fourier Transform 1965年，Cooley, Tukey 《机器计算傅里叶级数的一种算法》 * 数字信号处理 一、直接计算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) * 数字信号处理 * 数字信号处理 FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 谢谢！ * 离散时间信号—序列 数字信号处理 数字信号处理 * 离散时间信号—序列