首页  技术文章  快速傅里叶变换

快速傅里叶变换

发布时间:2020-12-24 14:26:28 浏览量:424 作者:Paul

正文



快速傅里叶变换


模拟信号使用傅里叶变化公式,数字信号可以采用离散傅里叶变化公式,但是离散傅里叶变化公式计算量大,所以对于离散的信号,现

在都是采用快速傅里叶变化(Fast Fourier Transformation)


这里以一个随机信号表示离散的信号

依据上述公式,如果计算X(k),乘法计算8(num)次,加法计算7(num-1)次,计算所有的频谱,需要乘法64(num^2)次,加

法计算56(num×(num-1))次。假设乘法使用四个时间周期T,加法使用一个时间周期T,那么8个数据占据的周期大约是312T


将这个公式和一些软件计算的结果进行对比,结果是一样的

FFT

下述公式,首先将系数奇数项和偶数项分开,然后偶数想提出公因式e^(-I 2π/N k),保持两个多项式的e指数有相同的形式,最后合并

2和N,奇数和偶数项构成新的多项式。



假设序列的长度为8,按照上述规则,将序列按照奇偶不断的分裂,直到最后



观察最后一个等号后的公式,从小括号,到中括号,到大括号,每个括号作为一层,可以得到网上的蜘蛛图



首先从小括号看起,小括号内x0,x2,x4,x6没有系数,而x1,x3,x5,x7的系数是exp(-8iπk/N),k从0到7内取任何整数,exp(-8iπk/N)无

非是+1或者是-1,所以看到在x1,x3,x5,x7后面可能跟随着两个系数W_N^0或者-1,就是表示相乘的意思,然后在红色方框内相遇

,相遇代表相加。他们是第一层,同时作为下一层的输入。下一层输入的系数是exp(-8iπk/N),k从0到7改变,系数可出现四种,


按照图上的表示应该是,同时它也作为第二层结果,同理可以得到第三层结构。每一层结构有8个数据,每个数据

都结构都是做了一次乘法和一次加减法。相对于DFT而言,DFT做乘法64次,而这里做的乘法只有不到8*lg8,也就是大约24次左右

,因此能够节省很多时间。


上面的叉形图中,最后的数字排列也是存在规律的。



二维傅里叶变化FFT2是对一个二维矩阵,先做一次FFT,然后转置后再做一次FFT。这里以一个实际的例子作为参考,输入的信号是一个3*3的矩阵

如果用matlab表示信号x,两次FFT变化可以写为fft(fft(x),3,2),一次FFT变化可以记作fft2(x)

您可以通过我们的官方网站了解更多的产品信息,或直接来电咨询4006-888-532