快速傅里叶变换——理论

本文公式较多，欢迎大家勘误

1.周期离散信号的傅里叶变换

离散信号傅里叶变换的公式如下所示：

离散傅里叶变换的原理是将原本非周期的信号复制扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为N，即N为信号

的周期，对于有限长周期信号，其离散傅里叶变换有如下性质：

其中

为周期信号的傅里叶级数，而

表示当且仅当

时有

，因此可以将傅里叶变换转为离散表达，如下所示：

考虑

以N为周期，因此仅需要计算k从0到N-1即可，取

此公式写成矩阵乘法模式如下所示：

W为一个

的方阵，该计算的复杂度为

2.快速傅里叶变换（分治法）

2.1.系数W性质

对于系数矩阵中的元素

，其公式如下所示：

考虑

，推导公式如下所示：

再考虑

和

的情况：

再考虑

和

的情况：

最后考虑

且

或

的情况：

根据上述推导，可以得出系数W具有以下四条性质，这三条性质会在后续推导中用到：

，同理有

，同理有

和

2.2.频域抽取基2快速傅里叶变换

基n快速傅里叶变换用于一个长度N为

的序列，例如基2快速傅里叶作用在

的序列上，基4快速傅里叶作用在

的序列上。现在考虑基2FFT的推导（硬件实现一般使用基4或基8FFT实现），首先写出有限长离散序列的傅里叶变换，记一个信号

的FFT变换为

：

快速傅里叶变换的核心思想为分而治之，即分治法，该思想的核心是将一个长度为N的问题，分级为两个长度为

的问题，应用在这里即是需要将一个序列长度为N的FFT变换问题分解为两个序列长度为

的FFT变换。首先进行如下变换：

矩阵的形式如下所示：

根据W的性质

，代入后有：

矩阵形式的表达如下所示，现在的矩阵为两个个高度为N，长度为N/2的矩阵。

代入

，根据W的性质

有：

矩阵表达如下所示：

代入

，根据W的性质

有：

矩阵表达如下所示：

根据上述推导，一个长度为N点的离散傅里叶变换被变为一个长度为

的离散傅里叶变换，取

公式如下所示：

2.3.时域抽取基2快速傅里叶变换

根据频域抽取基2FFT的算法，除了按前后分类外，还可以直接按奇偶进行分类，公式如下所示：

对应的矩阵表示为：

取序列

，

代入上述表达式，取

再代入W的变换性质可得：

其对应的矩阵为：

即将对F[k]的上半部分结果分解为两个FFT结果的和，即：

现在考虑F[k]的下半部分，公式如下所示：

取

，代入有：

代入W的性质

和

，有：

将变量i更换为k，其矩阵形式为：

最终可以将结果汇总为：

3.快速傅里叶变换的实现

3.1.蝶形运算

蝶形运算的公式如下，蝶形运算输入为

和

，输出为

和

，系数为

：

其转换为矩阵表达为：

蝶形公式对应着2点FFT的计算，2点FFT的计算如下所示：

转换为矩阵表达为：

对应到蝶形运算有：

3.2.频域抽取基2FFT的实现

首先列出基2频域抽取FFT的分治公式：

以一个8点FFT为例，输入序列为：

进行第一次分治，分为两个4点FFT，序列为：

示意图如下所示，偶数标号的结果由第一个FFT生成，奇数标号的结果由第二个FFT生成：

tu1.png

随后进行第二次分治，将每个4点FFT分解为两个2点FFT，每个序列为：

示意图如下所示：

tu2.png

最终通过2点FFT计算出结果，但如上图所示，计算出的结果位置与标号并不对应，例如计算输出的标号为2的数据（Y10[1]）应当位于输出序列（X）的标号4（X[4]）。其变换规律为计算输出的标号为n的数据（第n+1个数据）对应到输出序列标号为m的数据，n为m的二进制反序。以计算输出标号为6（第七个数据）的数据Y13[0]为例，6的二进制为110，反序为011，对应十进制数为3，即有

。

3.3.时域抽取基2FFT的实现

首先列出时域抽取FFT的分治公式：

和频域抽取不同，时域抽取为先进行FFT，再进行结果的累加。同样以8点FFT为例，要想获取8点FFT的结果，首先将其分为两个4点FFT，分别处理标号为奇数和标号为偶数的序列，示意图如下所示：

tu3.png

随后进行第二次分治，将每个4点的FFT再分解成2点FFT，示意图如下所示：

tu4.png

与频域抽取类似，时域抽取的输入序列（x）和计算输入序列（X1*）的标号不统一，二者同样存在二进制倒序的关系，例如x[1]，标号为001，二进制倒序后为100，对应十进制5，对应计算输入序列的X12[0]。

4.其他基的快速傅里叶变换

4.1.不同基下系数W的性质

对于基4的FFT，先推导W系数的性质：

对于不同的m有以下情况：

再考虑

在m取1,2,3下的情况，将

代入W的表达式：

考虑

在r取1,2,3下的情况，代入：

考虑

且周期为

的情况：

4.2.基4的快速傅里叶变换

4.2.1.基4FFT蝶形运算

在实际的硬件实现中，由于每一步的结果都需要保存，对于流水线式的FFT而言，则分解的次数就是流水线的级数，此若使用基2FFT，则需要消耗大量的寄存器或RAM空间保存中间数据，因此实际ASIC实现时多使用基4的FFT和基8的FFT。首先考虑基4FFT，4点DFT的计算公式如下所示：

考虑量化系数，将其展开为矩阵模式，可以发现每个结果的计算均不包含乘法：

其蝶形运算如下所示，左右分别是保持输入顺序和保持输出顺序的蝶形运算示意图：

tu5.png

4.2.2.频域抽取

现在考虑将一个长度为

的傅里叶变换进行基4分解，首先考虑频域抽取的方法，将计算序列按先后分为四段：

代入W的变换性质，有：

再进行间隔抽取，代入

和W的性质有：

取序列

，其表达为：

使用矩阵形式为，其使用的系数矩阵和蝶形计算相同：

取其FFT为：

则可获得基4的FFT递推公式，即：

以16点FFT为例，基4FFT将其分为两级实现，如下图所示：

tu6.png

4.2.3.时域抽取

对于离散傅里叶计算公式，进行间隔抽取，将

代入：

代入W的性质，取

，有：

取序列

有：

代入有：

现在考虑

的情况，代入

和W的性质，有：

整理可得：

根据上式列出矩阵形式：

可以得到递推公式：