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

第页共NUMPAGES13页
第五章快速傅立叶变换(FFT)
§1引言
实际中,处理一段,采入一段,要处时采时.
§2DFT的直算量,减量途经

需次复数乘,次加法;
减量依据:的周期性

和的对称性:
如是圆上6个点,可直接验证之.

§3基2FFT算法
变换区间长度取;或是采样点数.
时域抽取
FFT=DecimationInTimeFFT=DIT-FFT;
频域抽取
FFT=DecimationInFrequencyFFT=DIF-FFT.
1.DIT-FFT算法
分为

则

由的周期为
和(如右图)
可得
前半
后半
,.
蝶形
运算

一个蝶形运算量=1乘2加;

例

继续分解见下图.
先分析一下计算量
一次分解中运算量为
的DFT:次乘,次加;
的DFT:次乘,次加;
个蝶形:次乘,次加;
故总共有:次乘,次加
以此类推
分解1次,2个点的DFT,计量
分解2次,个点的DFT,计量
……
分解次,个点的DFT,
计量.
即经过一次奇偶抽取,计算量减一半和喋形;
二次……………………..四分之一
……
经过M级奇偶抽取,可分解为N个1点的DFT
而一个点的DFT值=该点值本身.

再利用,得

2.DIT-FFT的运算效率
观察图5.3.3的8点DIT-FFT的流程图,可推出
共有M=3级,每级有N/2个蝶形,每蝶1乘2加,
乘法:;
加法:

当时,有

一般有计算量
之比见右图.

可见FFT之省.
例子用“同学好”之程序—txmh.m来验证.
Matlab中可用tic和toc来计时.

处理同样的问题
常规DFT用了17.266000seconds.
而FFT用了2.312000seconds.

编程略.