快速傅立叶变换(FFT)

《快速傅立叶变换(FFT)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章快速傅立叶变换(FFT)§1引言实际中,处理一段,采入一段,要处时采时.§2DFT的直算量,减量途经需次复数乘,次加法;减量依据:的周期性第13页共13页和的对称性:如是圆上6个点,可直接验证之.第13页共13页§3基2FFT算法变换区间长度取;或是采样点数.时域抽取FFT=DecimationInTimeFFT=DIT-FFT;频域抽取FFT=DecimationInFrequencyFFT=DIF-FFT.1.DIT-FFT算法分为第13页共13页则由的周期为第13页共13页和(如右图)可得前半后

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

3、,得第13页共13页2.DIT-FFT的运算效率观察图5.3.3的8点DIT-FFT的流程图,可推出共有M=3级,每级有N/2个蝶形,每蝶1乘2加,乘法:;加法:第13页共13页当时,有一般有计算量之比见右图.可见FFT之省.例子用“同学好”之程序—txmh.m来验证.Matlab中可用tic和toc来计时.第13页共13页处理同样的问题常规DFT用了17.266000seconds.而FFT用了2.312000seconds.编程略.第13页共13页