Board logo

标题: FFT [打印本页]

作者: look_w    时间: 2017-11-18 12:27     标题: FFT

二、 快速傅立叶变换(FFT)
  快速傅立叶变换(FFT)是实施离散傅立叶变换的一种及其迅速而有效的算法。FFT算法通过仔细选择和重新排列中间结果,在速度上较之离散傅立叶变换有明显的优点。忽略数学计算中精度的影响时,无论采用的是FFT还是DFT,结果都一样。


  如果直接应用上式计算离散傅立叶变换,将花费很多时间,因此很长的一段时间里DFT的使用受到了限制。直到1965年美国的J.W.CooleyJ.W.Turkey提出了一种离散的傅立叶变换的快速算法,即FFT(Fast Fourier Transformation),才使得DFT的计算工作量大为减少。


  为简化表达,且不失一般性,将离散傅立叶变换公式简写成<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image60.gif" width="368" height="38">
由于<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image61.gif" width="52" height="20">,所以
X(k+N)=X(k)
表明X(k)是以N为周期的序列和频谱。


  若令旋转因子<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image62.gif" width="80" height="22">,则上式又可写成

<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image63.gif" width="122" height="38">
对计算的各频率点进行展开,有:
<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image64.gif" width="292" height="97">
用矩阵表示可写成
<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image65.gif" width="304" height="89">

<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image66.gif" width="74" height="21">
由于<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image67.gif" width="25" height="24">是复数,x(n)也可能是复数形式,这样,要完成上面矩阵运算共需N2次复数乘法和N(N-1)复数加法。可见,计算量与N2成正比,随着的增加,总运算次数将会急剧增加。
 
N=2B,于是可将[W]分解成B个矩阵的连乘,即
 

<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image68.gif" width="124" height="21">

其中每个矩阵的各行元素都包含有两个非零项。例如,对于N=64的情况有:

<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image69.gif" width="153" height="86">

注意这里利用了关系,<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image70.gif" width="118" height="21">,因此W4=W0W6=W2,将[W]分解成
<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image71.gif" width="277" height="88">
由于上式在分解时充分利用了旋转因子<img title="6.5 DFT与FFT" style="BORDER-LEFT-WIDTH: 0px; LIST-STYLE-TYPE: none; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px; PADDING-LEFT: 0px; MARGIN: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px" alt="6.5 DFT与FFT" src="http://course.cug.edu.cn/21cn/%E6%9C%BA%E6%A2%B0%E5%B7%A5%E7%A8%8B%E6%B5%8B%E8%AF%95%E6%8A%80%E6%9C%AF/c6/Image72.gif" width="22" height="21">具有周期性及合理分解的特点,从而使总的计算次数从N2量级减少到Nlog2N量级,极大地提高了运算速度,故形成了快速傅立叶变换。
  最常见的FFT算法要求N2的幂次。假定信号分析仪中的采样点数为1024点,DFT要求一百万次以上的计算工作量,而FFT则只要求10240次计算。显然,FFT可大大节约计算量,故在信号处理中中广泛采用FFT算法。目前FFT算法已有专用硬件芯片和软件模块,使用中直接选用就可以了。









欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0