快速傅里叶变换

2021-04-23 10:43:41 浏览:439

快速傅里叶变换原理

在一维的傅里叶变换中,算法的复杂度是O(N2),而在快速傅里叶变换中,算法的复杂度为O(Nlog2N),因此快速傅里叶变换能够实现更快的计算速度。

快速傅里叶变换基于逐次加倍的方法,其中原始的一维傅里叶变换公式(1)能够写成两个递推的公式(2)、(3):

其中M=2n=2K

 

从递推公式来看,其实快速傅里叶变换的工作原理是,将一个M点的变换分成两个部分来计算,其中奇部和偶部的和能得到F(u)的前M/2个值,而奇部和偶部的差能得到F(u)的后M/2个值。换句话说,对于任意M=2n的离散傅里叶变换计算,可以通过计算M/2个点的值,来计算M个点的DFT,最后从2个单点的DFT出发,递推得到4个单点的DFT、8个单点的DFT,直到M个点的DFT。而二维的傅里叶变换可由连续2次一维傅里叶变换得到。

快速傅里叶变换的代码实现

快速傅里叶变换的算法主要分成两步:

(1)根据M个点的顺序的二进制值进行按位倒序。举个例子,在8点的快速傅里叶变换中,f(1)的顺序是1,原地址写成二进制是001,按照按位倒序,倒序后的新地址值是100,写成十进制是4,即在顺序1号位应该放置f(4)。这种做法其实是完成多次奇偶分组后的结果,将0作为偶分组,1作为奇分组。

(2)蝶形运算。以8点计算来说,蝶形运算如图1所示:

图 1 蝶形运算的图示

其中,在每一次计算后,蝶形运算时的地址增量是2n,其中M=2n+1.

具体的代码实现如图2所示:

图 2 快速傅里叶变换具体步骤的代码实现

而傅里叶逆变换的过程,实际上是在频域中取了共轭之后,再进行快速傅里叶变换并最后除以总点数,即完成傅里叶的逆变换。

作          者: 泮桥成像光电商城

出          处: https://www.ipanqiao.com/entry/683

版          权:本文版权归泮桥成像光电商城所有

免责声明:本文中使用的部分文字内容与图片来自于网络,如有侵权,请联系作者进行删除。

转          载:欢迎转载,但必须保留上述声明;必须在文章中给出原文链接;否则必究法律责任。

Copyright © 2019-2022 南京超维景生物科技有限公司 版权所有 www.ipanqiao.com苏ICP备20009590号-1
联系我们
立即做合同
微信客服
电话咨询

400-998-9826

17302548620

快速留言

泮桥成像光电商城专业人员会在24小时之内联系您

关闭 提交