直接计算DFT的问题

《直接计算DFT的问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章快速傅里叶变换快速傅里叶变换是离散傅里叶变换（DFT)的一种快速算法FFT:FastFourierTransform1965年，Cooley,Tukey《机器计算傅里叶级数的一种算法》第四章学习目标掌握按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点掌握按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法掌握线性卷积的FFT算法及分段卷积方法4.1.1直接计算DFT的问题及改进途径运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法

2、实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)[例4-1]假定计算一个DFT所需的时间主要由乘法所需的时间决定，并设一次复乘需要。试求直接计算一个8点的DFT需多少时间，直接计算一个1024点的DFT需多少时间？例4-2根据式（3-1），对一幅N×N点的二维图像进行DFT变换，如用每秒可做100万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解直接计算DFT所需复乘次数为（N2)2≈1012次，因此用每秒可做100万次复

3、数乘法的计算机，则需要近300小时。这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算速度的要求太高了。另外，只能通过改进对DFT的计算方法，以大大减少运算次数。FFT快速算法的基本思路:1、把长序列分解成短序列，以减小运算量4个N/4点DFT…N点DFT分解成2个N/2点DFT分解成合成2个N/2点DFT合成N点DFT2、充分利用旋转因子的周期性，对称性来减小重复计算，使有些项合并，以提高速度FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Freque

4、ncy