快速傅立叶变换(FFT).ppt

快速傅立叶变换(FFT)
理论及算法实现
直接计算DFT的问题及改进途径
设x(n)为N点有限长序列,其DFT为
一般来说,x(n)和都是复数,X(k)也是复数,
因此每计算一个X(k)值,需要N次复数乘法以及
(N-1)次复数加法。而X(k)一共有N个点,所以
完成整个DFT运算总共需要次复数乘法及
N(N-1)次复数加法。
直接计算DFT的问题及改进途径
由于一次复数乘法需用四次实数加法;一次复数
加法则需二次实数加法。因此每运算一个X(k)需
要4N次实数乘法及2N+2(N-1)=2(2N-1)次实数加
法。所以整个DFT运算总共需要次实数乘法和
次加法。
例如:N=1024时,DFT需要复乘1,048,576次。所
以,直接计算DFT对实时性很强的信号处理来说,
对计算速度要求是太高了。
直接计算DFT的问题及改进途径
仔细观察DFT的运算就可以看出,利用系数
的以下固有特性,就可以减小DFT的运算量:
1、的对称性
2、的周期性
由此可得出
直接计算DFT的问题及改进途径
这样,(1)利用这些特性,使DFT运算中有些项可
以合并;(2)利用的对称性和周期性,可以将
长序列的DFT分解为短序列的DFT。前面已经说
过,DFT的运算量与成正比,所以N越小越有
利。
快速傅立叶变换就是在这种思路下发展起来的。
下面将详细介绍。
按时间抽取的FFT算法
先设序列长度为,L为整数。
将的序列x(n)(n=0,1,..,N-1),先按n的奇偶分
成两组
r=0,1,…, -1
则将DFT化为
按时间抽取的FFT算法
可以得到
由于

则上式可表示成
式中及分别是及的点DFT
由上式可以看出,一个N点DFT已分解为两个
点DFT,它们又可以组合成一个N点DFT。
按时间抽取的FFT算法
按时间抽取的FFT算法
但是, 以及都是点的序列
即r,k满足r,k=0,…, -1。而却有N点,而用上
面的式子计算得到的只是的前一半项数的结
果,要用来表达全部的值,还必
须应用系数的周期性,即
这样可得到
按时间抽取的FFT算法
同理可得:
上两式说明了后半部分k值( )所对应的
分别等于前半部分k值( )所
对应的。
再考虑到的对称性
这样,就可以得到分为前后两部分得表达:
前半部分