05-第五章 快速傅里叶变换
- 格式:ppt
- 大小:1.84 MB
- 文档页数:53
信号分析与处理课后习题答案第五章 快速傅里叶变换1.如果一台通用计算机的速度为平均每次复乘需要50us ,每次复加需要10us ,用来就散N=1024点的DFT ,问:(1)直接计算需要多少时间?用FFT 计算呢?(2)照这样计算,用FFT 计算快速卷积对信号进行处理是,估计可实现实时处理的信号最高频率? 解:分析:直接利用DFT 计算:复乘次数为N 2,复加次数为N(N-1);利用FFT 计算:复乘次数为20.5log N N ,复加次数为2log N N ;(1) 直接DFT 计算:复乘所需时间2215010245052.4288T N us us s =⨯=⨯=复加所需时间2(1)101024(10241)1010.47552T N N us us s =-⨯=-⨯= 所以总时间1262.90432DFT T T T s =+=FFT 计算:复乘所需时间3220.5log 500.51024log 1024500.256T N N us us s =⨯=⨯⨯⨯= 复加所需时间422log 101024log 1024100.1024T N N us us s =⨯=⨯⨯= 所以总时间为340.3584FFT T T T s =+= (2) 假设计算两个N 长序列1()x n 和2()x n 的卷积计算过程为如下:第一步:求1()X k ,2()X k ;所需时间为2FFT T ⨯第二步:计算12()()()X k X k X k =•,共需要N 次复乘运算所需时间为501024500.0512To N us us s =⨯=⨯=第三步:计算(())IFFT X k ,所需时间为FFT T所以总时间为230.35840.0512 1.1264FFT T T To s s s =⨯+=⨯+= 容许计算信号频率为N/T=911.3Hz2.设x(n)是长度为2N 的有限长实序列,()X k 为x(n)的2N 点得DFT 。
快速傅⾥叶变换快速傅⾥叶变换快速傅⾥叶变换(FFT )是根据计算量的最⼩化原理来设计和实施离散傅⾥叶变换(DFT)计算的⽅法。
1965年,库利(T.W.Cooley )和图基(J.W.tukey )发表了著名的《计算机计算傅⾥叶级数的⼀种算法》论⽂。
从此掀起了快速傅⾥叶变换计算⽅法研究的热潮。
快速傅⾥叶变换(FFT )的出现,实现了快速、⾼效的信号分析和信号处理,为离散傅⾥叶变换(DFT)的⼴泛应⽤奠定了基础。
1.1离散傅⾥叶变换(DFT)的计算设x(n)是⼀个长度为M 的有限长序列,则定义x(n)的N 点离散傅⾥叶变换为∑-===10)()]([)(N n kn NW n x n x DFT k X 其中由于计算⼀个X(k)值需要N 次复乘法和(N-1)次复数加法,因⽽计算N 个X(k)值,共需N2次复乘法和N(N-1)次复加法。
每次复乘法包括4次实数乘法和2次实数加法,每次复加法包括2次实数加法,因此计算N 点的DFT 共需要4N2次实数乘法和(2N2+2N ·(N-1))次实数加法。
当N 很⼤时,这是⼀个⾮常⼤的计算量。
1.2减少DFT 计算量的⽅法减少DFT 的计算量的主要途径是利⽤k N W 的性质和计算表达式的组合使⽤,其本质是减少DFT 计算的点数N 以便减少DFT 的计算量。
k N W 的性质:(1)对称性: (2)周期性: (3) 可约性: (4) 特殊点:选择其中⼀个证明N N j k N j N k N j N k N e e e W 222)2(22πππ--+-+==ππj k N j e e --=2k N j e π2--=k N W -=FFT 算法是基于可以将⼀个长度为N 的序列的离散傅⾥叶变换逐次分解为较短的离散傅⾥叶变换来计算这⼀基本原理的。
这⼀原理产⽣了许多不同的算法,但它们在计算速度上均取得了⼤致相当的改善。
0,1,,1k N =-()*nk nk N N W W -=()()nk N n k n N k N N NW W W ++==nk mnk N mN W W =//nk nk m N N mW W =01N W =/21N N W =-(/2)k N k N NW W +=-在这⾥讨论两类基本的FFT 算法。