阅读 18

快速傅里叶变换——理论

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

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

再考虑 在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的性质,有:

整理可得:

根据上式列出矩阵形式:

可以得到递推公式:

作者:月见樽

原文链接:https://www.jianshu.com/p/edfc8269e54d

文章分类
后端
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 gxwowoo@163.com 举报,一经查实,本站将立刻删除。
相关推荐