FFT 算法介绍 | My Sharings

date

icon

password

博客链接

Hide-in-Web

网址

type

slug

category

bottom

Hide-in-Config

comment

status

summary

本篇内容除了参考了陈后金老师的课程外，还参考了通信小马哥的视频，大家也可以前去参考。

旋转因子的三个性质：

FFT 的公式是基于上面的三个性质进行的，要理解上面三个公式，只需要将代入即可。

FFT 的几个特点：

在进一步介绍 FFT 的推导以及最终的流图之前，我们先需要知道 FFT 内部的一些特点。

这些特点在初学 FFT 时可能无法看懂，但是，当你在后面 FFT 的推导过程、计算过程中有不明白的点或是学完 FFT 再回来看时，会有更深的理解。

我们最初的离散序列 x[n] 都是时域的，因此在 FFT 中，第一级都是先计算 DFT，即将时域的 x[n] 转换为频域的中间值序列（之所以是中间值是因为它不是最终的结果），后面的几级都是频域间的相互转换；

FFT 运算每一级做的都是奇偶序列间的 2 点 DFT。在 FFT 中，是通过不断的取奇偶序列进行 2 点 DFT 来实现 4 点以及 8 点或更多点数的 DFT 运算的。

序列中的奇和偶是相对于位置而言的，而非看 x[n] 中 n 是奇的还是偶的。

FFT 的推导过程：

首先，需要假定输入的序列长度，对于输入序列不是这个长度的序列，可以通过补 0 使序列的长度满足条件。

第一步是将 DFT 拆解为奇序列的 DFT 和偶序列的 DFT 。下面的过程看起来很复杂，其实很好懂，耐心看完就能理解。

图中相当于是。通过上面的方式，就将长度为 N 的 DFT 拆分为了两半。前半部分和后半部分只有奇序列系数的符号是不一样的（一个为正一个为负）。

可以通过矩阵或是蝶形图的方式来表达上面两个公式（这样显得更简洁）：

矩阵主要是在能够清晰的看出公式中所蕴含的对称性，这种对称性在后面的 FFT 流图中也能看出来，是 FFT 美的一种体现。

图中的矩阵可以理解为蝶形图中输入的两项交叉相加减的过程，矩阵与蝶形图的对应关系可以通过下图来理解：

需要注意的是，上面的式子中无论是输入还是输出都是频域的值，并没有体现时域向频域转换的过程，因此还需要加入时域序列转换为频域序列的表示，如下图所示：

上图是左图公式的推导过程，实际上就是普通的 2 点 DFT 运算。

从矩阵形式中，我们又见到了和前面矩阵形式中相同的部分，这其实就是 FFT 中对称性的一种体现。在后续的时域信号转换为频域信号的过程中，都是利用了上面的公式进行转换，虽然转换的过程中输入不一定是 x[0] 和 x[1] ，但实际上是一样的，要学会灵活变通。

有了上面的两组公式后，我们就可以进行 FFT 流图的绘制了，首先尝试进行简单的 4 点 FFT 的绘制。

💡

下面绘制 FFT 流图的过程，都是按照从右往左逆推的顺序进行的，这有利于我们更清晰的了解 FFT 的架构。

下面进行 4 点 FFT 变换流图的绘制，第一步，绘制输出的 2 点 DFT 变换：

从图中可以看出，最终的结果都是通过偶序列的 DFT 、和奇序列的 DFT 、来表示的，这符合上图中左上角黑色的公式。

但要想要得到绿色部分的偶序列的值和橙色部分的奇序列的值就需要先通过前一步的点的 DFT 变换，这一步的 DFT 变换其实与最后这一步的变换是相同的，要将看作是最后结果中的，将看作是最后结果中的，将他们都拆分为 2 点的 DFT 以得到结果。

由于在这里进行的是 4 点的 FFT 变换（N = 4），因此这里的点 DFT 恰好就是 2 点的 DFT ，这一级其实是 FFT 变换的第一级（m=1），是将 x[n] 时域序列转换为频域序列的一级。内部的具体变换过程如下图橙线部分所示：

之所以是 x[0] 与 x[2] 进行 2 点 DFT，x[1] 与 x[3] 进行 2 点 DFT ，是因为需要先将时域序列中的偶数项和奇数项分开排列。

对哪两个输入做 2 点的 DFT 变换，那么这两个输入就分别替换下面的 x[0] 与 x[1]。

下面进行 8 点 FFT 流图的绘制：

首先也是绘制输出的 2 点 DFT：

然后对图中红框部分的 4 点 DFT 进行扩展：

上图的过程其实就是将看作是最后结果中的，看作是最后结果中的，对奇序列值与偶序列值 [0] 做 2 点 DFT 变换即可计算他们的值，其中奇序列值与偶序列值 [0] 是我们假设存在的一组奇偶变量，将看作是最后结果中的，其他的点也是一样。这样， ~ 以及 ~ 的值就可以通过这些中间量计算出来了。

那么这些中间量怎么求呢，他们的求解需要利用前一级的 2 点 DFT 来求，在这里前一级已经是时域分量了，因此这一级进行的是时域的 DFT 变换。

💡

在上图中，一定不要忘记轴线上的权重值，这个值的选取与需要进行的 DFT 的点数有关。

在上图中最具疑惑点的地方就是这些时域输入位置了，刚开始我也没弄清，在进行了大量的搜索后，我明白了。不能被 x[n] 括号中的 n 给迷惑了。对于这些位置的排列，我们需要先将时域序列中的偶数项和奇数项先分开，看偶数项中和奇数项内部是否各自能够凑成一对（即偶数项是否刚好是两个，奇数项也刚好是两个），如果偶数项中刚好能够凑成一对，那么就是这两个进行 2 点 DFT ，如果他们不能凑成一对，就需要对它们进行位置标号，然后根据位置的奇偶再进行拆分，看是否能凑一对。如下图所示：

于是最终就是 x[0] 与 x[4] 一起进行 2 点 DFT 转换为和，其他同理。

这就是上面 FFT 中输入序号那样的原因。当然，未来在进行排序的时候，并不需要像上图一样复杂的推一遍，而是有更加快速的方法，这里我介绍两种方法：

① 倒序算法；

这个方法是先将所有的输入标上位置标号（比如 x[0] 标号是 0，x[1] 标号是 1），然后将这些位置标号用二进制写出来。将二进制数中的最高有效位作为最低位，而最低有效位作为最高位，每次都在最高位加 1 ，进位进在次高来得到下一个数的序号。

比如我们要进行 8 点的 FFT，那么第一个序号为 000（这个不管几点的 FFT 都是默认的），第二个序号为 100，第三个序号为 010（最高位加 1 后次高位进 1），第四个序号为 110…

② 对称法；

本质上与倒序算法是一样的，这种方法需要先找到二进制数的中心轴，奇数个二进制数的中心轴为最中间的数，偶数个则为两边二进制数相同的点，然后(以 8 点 FFT 为例)按照 000、001、010、011、100… 的顺序从大到小写出二进制数，最后以中心轴为对称轴翻转，如下图所示：

上面介绍的均是输入倒序、输出顺序的 FFT ，当然也可以输入顺序、输出倒序，不过就是将输入的顺序调一调而已。最终转换出来的 FFT 图与前面的类似（这里以 4 点 FFT 为例）：

可以看到，输入顺序、输出倒序的 FFT 是先进行 4 点的伪 DFT（之所以是伪 DFT 是因为输入的两个权重都是，如果是 4 点 FFT 应该一个是一个是），然后再进行 2 点的 DFT，要注意的是权重的位置需要变化。

如果上面的回答对你有帮助，可以 请我吃根棒棒糖🍭 吗 😘