数字信号处理——快速傅里叶变换FFT（第四章）.ppt

数字信号处理
张刚
办公室
通信与信息基础教学部(二)(二教三楼2313)
联系电话
62460295;62477416
快速傅里叶变换(FFT)
本章主要内容
基2FFT算法
进一步减少运算量的措施
分裂基FFT算法基本原理
基2FFT算法
直接计算DFT的特点及减少运算量的基本途径
长度为N的有限长序列x(n)的DFT为
考虑x(n)为复数序列的一般情况,对某一个k值,直接按()式计算X(k)值需要N次复数乘法、(N-1)次复数加法。
()
因此,N点DFT的复乘次数等于N2 ,加法次数为N(N-1)。
显然,把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子具有明显的周期性和对称性。
其周期性表现为
()
基2FFT算法
其对称性表现为
或者
时域抽取法基2FFT基本原理
FFT算法基本上分为两大类:时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIF―FFT)。下面先介绍DIF―FFT算法。
基2FFT算法
设序列x(n)的长度为N,且满足
为自然数
按n的奇偶把x(n)分解为两个N/2点的子序列
则x(n)的DFT为
基2FFT算法
由于
所以
其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即
()
()
基2FFT算法
由于X1(k)和X2(k)均以N/2为周期,且
所以X(k)又可表示为
()
()
蝶形运算符号
蝶形运算表示
一个蝶形运算
=
一次复数乘运算
+
两次复数加法运算
N=2M 一次分解
=
两个N/2点DFT
+
N/2个蝶形运算
基2FFT算法
N点DFT的一次时域抽取分解图(N=8)
N=8为例
基2FFT算法
第二次分解
与第一次分解相同,将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l),即
那么,X1(k)又可表示为
()
式中
基2FFT算法
用同样的方法可计算出:
同理,由X3(k)和X4(k)的周期性和的对称性
最后得到:
其中