DSP 课件 5.8 快速傅立叶变换FFT.ppt

《DSP 课件 5.8 快速傅立叶变换FFT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.8快速傅立叶变换FFTN×N点的二维图像进行DFT变换，N=1024时直接计算DFT所需复乘次数为（N2)2≈1012次，如用每秒可做10万次复数乘法的计算机，即使不考虑加法运算时间，也需要近3000小时。这对实时性很强的信号处理来说，要么提高计算机的计算速度，而这样，对计算速度的要求太高了。另外，就只能通过改进对DFT的计算方法，以大大减少运算次数。DFT的运算量：1965年，J.W.Cooley和J.W.Tukey首次提出了DFT运算的一种快速算法，“AnAlgorithmfortheMachineComputationoftheComplexFourierSeries”

2、；此后相继出现了各种用于计算机平台的改进FFT算法；FFT出现后使DFT的运算大大简化，运算时间一般可缩短一、二个数量级之多，从而使DFT的运算在实际中真正得到了广泛的应用。按时间抽取（Decimation-in-Time，缩写为DIT）法按频率抽取（Decimation-in-Frequency，缩写为DIF）法线性调频Z变换（Chirp-z），即CZT法；或基－2，基－4，分裂基FFT法设序列点数为N＝2M，M为整数。若不满足条件，可以加上若干个零值点。N为2的整数幂的FFT称为基-2FFT。按时间抽取法设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)

3、分解为两个N/2点的子序列：基本思想：将2N点的DFT运算分解为两个N点的DFT运算，不断重复这个过程到N=1为止。时间抽取法蝶形运算流图符号一次乘法，两次加法按时间抽取将一个N点DFT分解为两个N/2点DFT（N=8）两点的DFT都可以用一个蝶形结x(0)x(1)X(0)X(1)-1N=8按时间抽取的FFT运算流图运算量分析：FFT：每级有N/2次复乘和N次复加；FFT共有log2N级，因此，共有Nlog2N次复加和(N/2)log2N次复乘；FFT的运算难度系数与Nlog2N成正比；一幅N×N（N=1024）点的二维图像的DFT，如用每秒可做10万次复数乘法的计算机（不考虑加

4、法运算时间），直接计算DFT所需时间为3000小时，用FFT算法只需要2分钟。时间抽取FFT的特点：1、原位运算：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出，节省存储单元。2、码位倒读规则：码位倒读后的顺序刚好是数据送入计算机内的顺序。以N=8为例：01234567000001010011100101110111二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537按时间抽取（DIT）的基-2FFT算法的基本出发点是：利用旋转因子WNnk的对称性和周期性，将一个长序列的DFT分解为一些逐次变小的DFT

5、来计算。分解过程遵循两条规则：①对时间进行奇偶分解；②对频率进行前后分解。这种按频率抽取（DIF）的基-2FFT算法算法推导过程遵循两个规则：①对时间进行前后分解；②对频率进行偶奇分解。设序列点数为N＝2M，M为整数。把输入序列按前一半、后一半分开（不是按偶数、奇数分开），把N点DFT写成两部分。k=0,1,…,N-1按k的奇偶可将X(k)分为两部分:按频率抽取的FFT（N=8）信号流图IFFT算法只要把DFT运算中的每一个系数WNnk改为WN-nk，并乘以系数1/N，就可以用FFT算法来计算IDFT，也就得到了IFFT的算法IFFT算法本章小结DTFT，性质，频率响应，相位；D

6、FT，概念，性质，FFT算法