BMF 是一种非常高妙的程序演算。我们用它来简单推导一下 FFT。

基本运算符号

  • 表示将一个列表中所有元素变为应用了之后的结果(map)。
  • 表示将列表中的元素按照具有结合律的运算合并(reduce)。
  • 表示将某个元素转化为一个长度为 1 的仅包含它自己的列表(singleton)。
  • 表示连接两个序列。
  • 表示二维列表的转置(transpose)。
  • 表示将两个等长的列表对应项通过二元运算计算出结果形成的新的列表(zip with)。
  • 表示的长度。
  • 的变换规则如下:,其中是一个映射,表示迭代次。
  • 的变换规则如下:
  • 表示
  • 表示一个长度为全是的列表。

基本定理

map 对有分配律:

关于的一系列性质:

  1. 的一个等价形式:
  2. 对 map 有分配律:
  3. 对 reduce 的影响:。因此可以把前者理解为竖着的 reduce。

我们称为 pointwise 运算,下面的均为 pointwise 运算:

  1. 关于交换律:若,那么
  2. ,那么,并且有。而且这也可以推导出

有关的一个性质是

有关的性质:

  1. 分解:,其中
  2. 交换:
  3. 假设操作对象是一个矩阵(二维列表),那么对于高维列表来说相当于交换第一二维的坐标,因此得到的结果是),再转置一下就能得到

描述 DFT

对于序列的离散傅里叶变换可以描述为

理解方式如下:

  • 表示将序列变成
  • 表示将第个序列变成
  • 表示分别求和。

分治

观察上面的 specification,我们首先要处理的是形如的变换。考虑分治。

先考虑一个简单的情况:对一维列表做变换。将这个过程分治,相当于将其切成若干段,不妨考虑切出来的段等长。那么把原列表做变换就可以转换为,把矩阵每行分别做变换,再连起来。写成 BMF 就是

同理,是针对二维列表的变换:

  • 相当于对第行第列的元素迭代次。
  • 相当于对第行第列的元素迭代次。
  • 相当于对第行第列的元素迭代次。

这个过程也可以分治。这里我们的分治方法是:对于一行,按照一维的情况来做。此外,我们也可以将所有行分成若干组,每一组行数相等。分割后我们拿到的其实是一个四维列表。把四维列表拼成二维列表的变换是

接下来做一些 BMF 推导:

这里我们单独把拿出来给大家变换一下:

根据基本定理,(可交换)因此

在 FFT 当中,。我们假设应用到的列表是一个的四维列表,且。那么

相当于啥都不干。

推导 FFT

作用于一个的二维列表。那么

这里我们设

最后一步用到了加法结合律。然后我们推导一下后面的。注意到作用于的结果是得到一个的列表,因此

的类型为。接下来来推导

最后一步用到了加法交换律。注意到

  • 分配律:

因此

因此

表示将一个长度为的序列分成一个的二维列表,我们就得到了 FFT 的最终表示

平时我们写的 FFT 是取或者(二分治),这时就会退化为(不需要乘法)。

参考文献

Deriving the fast Fourier Algorithm