《直接计算DFT的问题.ppt》由会员分享，可在线阅读，更多相关《直接计算DFT的问题.ppt（10页珍藏版）》请在三一办公上搜索。
1、第四章 快速傅里叶变换,快速傅里叶变换,是离散傅里叶变换（DFT)的一种快速算法FFT:Fast Fourier Transform1965年，Cooley,Tukey机器计算傅里叶级数的一种算法,第四章学习目标,掌握按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点掌握按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法掌握线性卷积的FFT算法及分段卷积方法,直接计算DFT的问题及改进途径,运算量,例4-1 假定计算一个DFT所需的时间主要由乘法所需的时间决定，并设一次复乘需要。试求直接计算一个8点的DFT需多少时间，直接计算一个1024
2、点的DFT需多少时间？,例4-2 根据式（3-1），对一幅NN点的二维图像进行DFT变换，如用每秒可做100万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解 直接计算DFT所需复乘次数为（N2)21012次，因此用每秒可做100万次复数乘法的计算机，则需要近300小时。这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算速度的要求太高了。另外，只能通过改进对DFT的计算方法，以大大减少运算次数。,FFT快速算法的基本思路:,1、把长序列分解成短序列，以减小运算量,分解成,2、充分利用旋转因子 的周期性，对称性来减小重复 计算，使有些项合并，以提高速度,FFT算法分类:,时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency,
