离散傅里叶变换.pptx

离散傅里叶变换
快速傅里叶变换(Fast Fourier Trasform。简称FFT)是一种减少DFT计算时间的算法。在此出现之前，虽然DFT为离散信号的分析从理论上提供了变换工具，但是很难实现，因为计算时间很长。例如，对采样点 N＝l000，DFT算法运算量约需200万次，，可见FFT方法大大地提高了运算效率。因此，FFT方法于1965年由美国库利—图基(—)首先提出时，曾被认为是信号分析技术的划时代的进步。
FFT: Fast Fourier Transform
1965 年，James W. Cooley 和 John W. Tukey 在《计算数学》（《Mathematics of Computation》）上发表了“ 一种用机器计算复序列傅立叶级数的算法（An algorithm for the machine calculation of complex Fourier series）” 论文。
Dr. James W. Cooley
John W. Tukey (1915-2000)
W. M. GENTLEMAN & G. SANDE, Fast Fourier Transforms-For Fun and Profit, Fall Joint Computer Conference AFIPS Proc., 1966, ,563-578.
自此之后，新的算法不断涌现。一种是对N等于 2 的整数次幂的算法，如基 2 算法，基 4 算法。另一种是N不等于 2 的整数次幂的算法，例如 Winagrad 算法，素因子算法。
计算DFT复数运算量
计算一个X (k)值，运算量为
例k=1则
要进行N次复数乘法，(N-1)次复数加法
所以，要完成整个DFT运算，其计算量为：
N*N次复数相乘，N*(N-1)次复数加法
利用 的固有对称性和周期性改善DFT的运算效率
的对称性：
的周期性：
因为：
由此可得出：
时间抽取基-2FFT算法Decimation-in-Time (DIT)
一、算法原理
设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。
其中基数2----N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M。
二 、按时间抽选的基-2FFT算法
1、算法推导
设序列点数 N = 2M，M 为整数。
若不满足，则补零
将序列x(n)按n的奇偶分成两组：
N为2的整数幂的FFT算法称基-2FFT算法。
则x(n)的DFT: