第4章 快速傅里叶变换(FFT).ppt

第4章快速傅里叶变换(FFT)
引言
基2FFT算法
进一步减少运算量的措施
分裂基FFT算法
离散哈特莱变换(DHT)
引言
DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时,计算量太大,所以在快速傅里叶变换(简称FFT)出现以前,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后,情况才发生了根本的变化。
基2FFT算法
直接计算DFT的特点及减少运算量的基本途径
长度为N的有限长序列x(n)的DFT为
考虑x(n)为复数序列的一般情况,对某一个k值,直接按()式计算X(k)值需要N次复数乘法、(N-1)次复数加法。
()
如前所述,N点DFT的复乘次数等于N2。显然,把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有明显的周期性和对称性。其周期性表现为
()
其对称性表现为
或者
时域抽取法基2FFT基本原理
FFT算法基本上分为两大类:时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIF―FFT)。下面先介绍DIF―FFT算法。
设序列x(n)的长度为N,且满足
为自然数
按n的奇偶把x(n)分解为两个N/2点的子序列
则x(n)的DFT为
由于
所以
其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即
()
()
由于X1(k)和X2(k)均以N/2为周期,且
,所以X(k)又可表示为
()
()
蝶形运算符号
N点DFT的一次时域抽取分解图(N=8)
与第一次分解相同,将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l),即
那么,X1(k)又可表示为
()