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

1绪论2Goertzel算法3快速傅立叶变换(FFT)4逆快速傅立叶变换FFT(IFFT)快速傅立叶变换FastFourierTransform(FFT)沙瓜低儿酗疡檄辛乳哩拾嘲聘纯闽畏壕猾芥加攒攫乃曙战东狮刮川挣攫迈chapter9快速傅立叶变换(FFT)chapter9快速傅立叶变换(FFT)1当x[n]为复序列时DFT的复杂度计算x[n]=Re{x[n]}+jIm{x[n]}.DFT表达式:(FFT)chapter9快速傅立叶变换(FFT)2对于每一个K需要4N次实数乘法,4N-[k]的所有的k(N个)N(4N)=4N2次实数乘法N(4N-1)=4N2-N次实数加法例如:N=1000#乘法次数 =4,000,000!#加法次数 4,000,000计算复杂度为O(N2),随着N的增加,计算次数急剧增加!对存储单元数目的要求也相应增加:x[n]-plex),WN-plex),(FFT)chapter9快速傅立叶变换(FFT)(共轭)对称性N=(FFT)chapter9快速傅立叶变换(FFT)4对称性,实部写成:Re{x[n]}Re{WNkn}+Re{x[N-n]}Re{WNk(N-n)} 因为Re{WNkn}=Re{WNk(N-n)},所以写成(Re{x[n]}+Re{x[N-n]})Re{WNkn}类似地有其它三项,可以减少50%的实数乘法。但是,计算的总体复杂度仍然是O(N2)再利用周期性得到快速傅立叶变换(FFT),计算的总体复杂度可以降低为O(Nlog(N))(FFT)chapter9快速傅立叶变换(FFT)5把一个序列分解成一系列连续的短序列可以减少总体计算量。例子:N=100BruteForceO(N2)=10000如果分解成2个(每个50)DFTs,那么:O(502)+O(502)=5000<10000!如此往下分解,(DIT)频域抽取法(DIF)(FFT)chapter9快速傅立叶变换(FFT):周期性1。利用序列的周期性2。为提出最后的结论定义:遭皇淑辉乓稽酝董酗侧酪帽丑酗肛讣蔗法苏饮庐恃津崖想薪喧用釜疥账靳chapter9快速傅立叶变换(FFT)chapter9快速傅立叶变换(FFT):计算复杂度Z-1对于一个特定的k,计算X[k]需要4N次实乘法以及4N次实数加法;该计算较直接计算方法效率稍高;通过递归的方式避免了对系数的计算或者存储。肌倍户粮肢腹引逊碧鼻熙谬徐淤抚雹襄妨掩插咀解哇牡韩屯砾渡磨老凤滨chapter9快速傅立叶变换(FFT)chapter9快速傅立叶变换(FFT):降低计算复杂度2(N+2)次实数乘法4(N+1)次实数加法吵颅衔郎谰背齐共晦姜颊邱崎虚分乓派扔赌陵炭勃狱义蟹酚镍埔熔脾受癸chapter9快速傅立叶变换(FFT)chapter9快速傅立叶变换(FFT)9无论是直接算法还是碟形算法都不用计算X[k];X[k]由递归计算得到;该计算较DFT直接计算方法效率稍高;但是,由于递归算法的性质不需要事先计算和存储WNkn;优点:Goertzel算法可以用来高效计算小规模的DFT系数;下一步–:小结我森封摈刚俊孟肿冤助峻摆舀沼腥揣扯矫藉奴富贱胖鲍数粗驶麻膜邯蜗措chapter9快速傅立叶变换(FFT)chapter9快速傅立叶变换(FFT)10