Board logo

标题: FFT [打印本页]
作者: look_w    时间: 2017-11-18 12:27     标题: FFT

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


　　如果直接应用上式计算离散傅立叶变换，将花费很多时间，因此很长的一段时间里DFT的使用受到了限制。直到1965年美国的J.W.Cooley和J.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=W0，W6=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算法要求N是2的幂次。假定信号分析仪中的采样点数为1024点，DFT要求一百万次以上的计算工作量，而FFT则只要求10240次计算。显然，FFT可大大节约计算量，故在信号处理中中广泛采用FFT算法。目前FFT算法已有专用硬件芯片和软件模块，使用中直接选用就可以了。








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