傅里叶变换 | InverseDa Blog

type

status

date

slug

summary

连续傅里叶变换

从介绍可以知道连续的傅里叶变换是：

其中是频率，表示的是频谱，同时是特定频率下信号的强度。傅里叶变换是将时域变换到频域。是傅里叶变换。

傅里叶逆变换是将频域转换到时域：

离散傅里叶变换

概念

离散傅里叶变换（DFT）可以被看作是多项式乘法的一种形式。具体来说，DFT 将一个长度为的序列转换为另一个长度为的序列，这两个序列之间的关系可以看做是多项式及其点值之间的转换。

更具体地说，假设我们有两个长度为的多项式和，它们的系数分别为 a0, a1, ..., a(N-1) 和 b0, b1, ..., b(N-1)，则这两个多项式的乘积可以通过以下步骤来计算：

将和视为长度为的序列，分别进行 DFT，得到两个频域序列和。

对于每个，计算。

对序列进行 IDFT，得到多项式的系数。

先引入多项式：

如果定义多项式之和为，因此满足，所以：

如果定义多项式乘积为，定义为多项式乘积，其方法是将的每一项都和的每一项相乘，然后再合并同类项。如果和都有项，根据组合数学，可以知道有项，因此可以这样表示：

在计算机中表示多项式，一般用两种方法。

系数表示法

对于多项式

其系数表示就是一个系数组成的向量：

注意的是，我们一般将他表示为列向量。

采用系数表示法在求解多项式在某点的值是很快的，只需要：

另外，两个多项式相加，只需要将两个多项式的系数向量相加即可，即：

两个多项式相乘，需要将向量的每个系数都要和相乘，所以需要的时间，更严谨来说，此时的为和的卷积：

这是否太慢了？

点值表示法

一个次数为的多项式的点值表示就是个点值对形成的集合：

其中各不相同，当的时候，有：

所以，如果我们有个点对组成的点集，那么就可以表示这个多项式，这是为什么？这是因为这种运算的方法本质上是一种求值运算的逆（从多项式的点值表示确定其系数表示中的系数），这种叫做插值（也就是从已知推未知）。具体证明如下：

证明：

假如多项式为：

那么就有：

由于点集确定，可以知道是已知的，因此这个线性方程组可以表示为矩阵乘法：

根据克拉默法则，只需要系数行列式不为0就有解，而看出来这是范德蒙行列式，所以：

又因为各不相同，所以这个值始终不等于0，因此方程有解，而且这个矩阵可逆，因此可以确定：

其中：

令：

那么：

因为是可解的，所以只要个点值对，就可以确定次多项式（这不就是插值吗！所以其实没有那么高大上）。

既然是插值，那我们不是学过最基本的插值算法拉格朗日吗？那多项式其实用拉格朗日插值也可以得到的。拉格朗日插值概念为：

其中每个为拉格朗日多项式：

假如

要利用插值求f(18)，可以：

然后得到f的插值函数L：

代入18：

这样就避免了求解线性方程组，直接使用拉格朗日插值：

理论上可以用来确定拉格朗日插值后的多项式。

我们通过两种方法证明了点值表示法可以表示多项式，现在可以研究怎么进行多项式乘法。

QED

从证明可以看出，求值运算和插值运算时一种互逆运算，他们可以将多项式的系数表示与点值表示进行相互转换。那为什么需要点值表示？系数表示不就够了？

这是因为点值表示天生适合多项式的加法和乘法。假如存在的点值表示：

的点值表示：

这里假设A和B相同的个点进行求值，不难得出C的点值表示为：

不难看出，只需要时间即可解决。

同理，点值表示法进行乘法，但前面提到过，A和B的次数上界为，如果C是A和B的乘法结果，那么C的次数上界应该为，因此我们有必要对A和B的点值表示进行扩充，使得每个多项式都含有个点值对。

A的扩充后点值表示：

B的扩充后点值表示：

则C的点值表示为：

可以看出来，如果将已知的两个扩充点值形式的输入多项式，只需要即可完成多项式乘法。

问题来了，如何获得扩充后的点值表示？

最简单的办法是，先把该点值表示形式多项式转换为其系数表示形式，然后再求其在新点处的值。因为在将系数表示的时候，我们知道他在求一个点的多项式值是很快的，只需要。

那该挑选哪些点呢？结论是单位根。单位根是一种复数，结合单位根，我们就可以采用DFT和FFT的策略了。

从这图可以看出来，FFT就是处理系数表示转换到点值表示(Coeff to Value)，以及点值表示转换到系数表示(IFFT, Value to Coeff)。

单位根

数学上，次单位根是次幂为1的复数。他们位于复平面的单位圆上。

复数在欧拉公式的表示为：

其中：

在电路和信号中，我们常常采用表示虚数防止与电流混淆。但这篇文章都涉及到，所以我们用j

对于单位根，我们用特殊的记号表示这类复数而不用z。因为单位根的模为1，所以：

而n次单位根，是满足的复数，n次单位根刚好有n个，他们是。

而：

称为主次单位根，即所有其他次单位根都是主次单位根的k次幂：

其中规定，这是因为。

举例子：

1次单位根只有一个根，这个根同时是主1次单位根（）：

2次单位根只有两个根：+1和-1，其中-1是主1次单位根（）：

3次单位根只有三个根（）：

其中第二个是主三次根

如图为八次单位根的复平面图：

综上，n个n次单位根为，根据群论可以知道他们在乘法运算中形成了一个闭合的群，这是由于欧拉公式的三角函数是具有周期性的，使得如下式子成立：

这是因为：

可以知道：

因此上式成立。比如。

为了引入DFT和FFT，我们要介绍两种性质：

相消引理：

对任何整数，，：

折半引理：

如果n为偶数，那么n个n次单位根的平方等于n/2个n/2次单位根，这是因为，根据相消引理：

如果对所有n次单位根进行平方，每个n/2次单位根刚好获得两次，这是因为：

所以与的平方值相等。这个性质非常适合用分治思想来优化DFT。

求和引理：

对于整数和不能被整除的非负整数，有：

这是因为等比级数：

只要保证不能被整除，分母就不为0。

有了这三个引理就可以引入DFT和FFT了

DFT

多项式：

在的值，假设是2的幂，故定义：

这就是DFT，写作向量形式：

我们的任务就是计算这个式子。

FFT

FFT是快速离散傅里叶变换，可以在的时间内计算，而暴力法需要用。FFT主要采用了我们提到的三个单位根引理，核心思路就是分治法。假设是2的幂。

FFT使用的分治策略，就是将的偶数下标系数和奇数下标系数按照新的次数上界分开：

为什么要这么做？因为我们要构造平方项的。

因此：

这样，求在的值就转换为：

求次数上界为的多项式在和在点：

的值.

由：

根据相消引理和折半引理得到：

所以我们求出和，就可以同时求出和。于是分别对和递归求解即可。

也就是将个元素的划分为两个个元素的的计算过程，注意始终是2的幂。

具体CPP代码：

为什么取点要取单位根而不取整数？

为什么是单位根？试想一下，假设我们不取单位根，而是取整数。假设多项式是：

这个多项式是二次函数，更严格来说是个偶函数，所以我们可以用对称的方式去点：

假设我们要取8个点，我们其实只需要取4个点就可以了。

对于另外一个多项式：

这个函数是奇函数，我们同样可以采用对称的方式取点：

那对于任意多项式呢？

在之前我们知道，对于任意多项式，我们可以采用拆分为奇和偶多项式：

即：

如果我们取整数点，那么需要求出就可以同时求出：

但这样有个问题，两个子问题都是平方的，因为负数的平方依然是正数，这样就会导致他们不能成一对（正负成对）。因此无法进行迭代计算。另外，也难以分治。

那有什么办法能够让他们被平方后依然成一对呢？你也应该知道了，使用单位根就可以了：

其中：

进一步化简：

这时候，就可以用递归计算了，因为有明显的分治n/2.

DFT矩阵与FFT的本质

本质上FFT是一种快速求解DFT的方法，并且可以用DFT矩阵表示这个步骤。

于是就可以理解为，FFT是快速进行DFT矩阵乘法计算的方法。因为矩阵的乘法计算，加速的思路经典上会使用分治，所以这就是FFT的本质了。本质上就是矩阵乘法的加速。