[Matlab科学计算] 频谱分析和FFT算法总结—理论基础

101 阅读 0 评论 67 点赞

我是靠谱客的博主时尚羊，最近开发中收集的这篇文章主要介绍[Matlab科学计算] 频谱分析和FFT算法总结—理论基础，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

名词解释请看这篇博客：频谱分析和FFT算法总结

一.离散傅里叶变换（DFT）的理论

已知傅里叶变换和傅里叶逆变换，变换如下：

正变换：

逆变换：

离散傅里叶变换（DFT）顾名思义就是对傅里叶变换进行离散化，包括频率和时间的离散化，我们令 $t=nDelta t$ 和 $f=kDelta f$ ，代入傅里叶正变换中，得：

将积分变为求和得：

取N点进行时域截断得：

考虑到 $xleft ( nDelta t right )$ 就是离散化后第n点的时间函数值 $xleft ( n right )$ ， $Xleft ( kDelta f right )$ 就是离散化后第k点的傅里叶变换值 $Xleft ( k right )$ ， $Delta t$ 进行归一化处理，所以DFT的定义如下：

其中用到了欧拉公式。

DFT的实部和虚部分别为：

令 $W_{N}=e^{-jfrac{2pi }{N}}$ , 则有

其中 $W_{N}^{kn}$ 算子的周期为N，模为1的复数。上式写成矩阵形式会更容易理解，如下：

上式中 $W_{N}^{kn}$ 是已知的，可以很容易根据 $xleft ( n right )$ 计算出 $Xleft ( k right )$ ，当N取值很大的很大的时候，上述方程组的求解计算量很大， $Oleft ( N^{2} right )$ 级的计算复杂度，由于 $W_{N}^{kn}$ 的周期性，主动选择合适的N可以更快的求解方程组，于是出现了基2型FFT算法。

二.快速傅里叶变换（FFT）的实现流图

FFT算法的基本思路，本质上就是怎么更快的计算上面的方程组。

先来看一下FFT算法的速度有多快，如表1所示

FFT算法有种二分的思想，首先将数据分为奇数序列和偶数序列两部分，然后再对每个序列进行二分，直到最后分成2个点的计算，也就是求解一元二次方程组。步骤如下：

其中， $W_{N}^{2}=e^{frac{-j2(2pi ))}{N}}=e^{frac{-j2pi }{N/2}}=W_{N/2}$

式中， $Xleft ( k right )$ 为 $xleft ( n right )$ 的N点DFT，用两个N/2点DFT的 $Gleft ( k right )$ 和 $Hleft ( k right )$ 表示，两者分别是 $xleft ( n right )$ 偶数样本和奇数样本的DFT。