基2-FFT简记

快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 $O(nlogn)$ 时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法。

复数单位根 $w^k_n$

横轴为实轴，纵轴为虚轴的复平面上， $e^{i\theta }=cos\theta +i\cdot sin\theta$

(将复平面单位圆均分成n份，以单位圆与实轴正半轴的交点一个等分点，以原点为起点，n个等分点为终点，做n个单位向量，其中幅角为正且最小的向量被称为n次单位向量，记为 $w^1_n$ )

易知 $w^n_n=w_n^0=1$

所以， $w^k_n= e^{k\cdot \frac{2\pi}{n} i }$

（复平面中复数加法满足平行四边形法则，乘法满足幅角相加，模长相乘）根据这性质易几何证明以下两性质

复数单位根性质：

1、折半引理： $w^{2k}_{2n}=w^k_n$ $\Rightarrow$ $w^{mk}_{mn}=w^k_n$

2、消去引理： $w_n^{k+\frac{n}{2} }=-w^k_n$

离散傅里叶变换的复杂度为 $O(n^2)$

快速傅里叶变换的复杂度为 $O(NlogN)$

$N$ 点FFT阶段数为 $logN$ 而每一阶段的复杂度为 $N$ ，故复杂度为 $O(NlogN)$

以8点FFT为例，绿色的列表示一个阶段，每个空心圈表示一次乘加，一列共N个

先看离散傅里叶变换（DFT）表达式 ( $x_n$ 时域， $x_k$ 频域)：

$x_k = \sum_{n=0}^{N-1}x_n\cdot e^{-i \frac{2\pi kn}{N} }$ , k=0,1,...N-1

$e^{-i \frac{2\pi kn}{N} } = w^{nk}_N$

通过上述DFT的表达式，其可以用复数单位根表示成：

$x_k=\sum_{n=0}^{N-1}x_n\cdot w_N^{nk}$ , $k=0,1,2,...,N-1$

$=\sum_{n \in even} x_n w_N^{nk}+\sum_{n \in odd} x_n w_N^{nk}$

$=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_N^{2rk}+\sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_N^{(2r+1)k}$

$=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_N^{2rk}+w_N^{k} \sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_N^{2rk}$

$=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_{\frac{N}{2}} ^{rk}+w_N^{k} \sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_{\frac{N}{2} }^{rk}$

$=G_k +w^k_NH_k$

在这边我们要注意的是，我们所替换的G[k]与H[k]具有周期性：

此性质根据单位根的几何意义得证

上述的推导可以划成下面的图，以8点DFT为例(N=8，左边一列为时域，右边一列为频域）：

划红框处所示的 $\frac{N}{2}$ 点DFT架构如下图所示：

划红框处所示的 $\frac{N}{4}$ 点DFT架构如下图所示：

综上，下图是一个8点DIT FFT的完整架构图：

图中应用性质，例如左边的

库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2算法。

参考：库利－图基快速傅里叶变换算法

FFT还能用来加速多项式乘法。朴素计算两个N-1次（N项）多项式复杂度为 $O(N^2)$

多项式系数表达法

多项式的点值表达法

设 $F(x) = f(x)\ast g(x)$

点值表达法的多项式乘积十分方便，复杂度为

这里有个点就是点值表示法的乘积，按理说两个n次的多项式乘积的最高次为2n，而点值表示法就像是解方程，2n次方程式需要2n个点值点才能唯一确定，所以我理解的是需要两次上图的点值表示法乘积才能确定结果。

而是用DFT和IDFT可以分别转换系数表达法到点值表达法和点值表达法到系数表达法，FFT可以加速这两个转换过程。

大概过程是，先将两个系数表示法的多项式分别转化为点值表达式，再进行点值表达法的多项式乘积运算，再将结果转换回系数表达法。

需要注意的是，在求两个次数分别为 $n_1-1$ 和 $n_2-1$ 的多项式的乘积时，需要分别求出在至少 $n_1+n_2-1$ 个点处的值，这样才能保证相乘后唯一确定一个 $n_1+n_2-2$ 次多项式。

假设 $C(x) = A(x)\ast B(x)$ ,A（x）、B(x)的点值表达式均有N个点，而他们的乘积C（x）因为次数为 $2N$ 所以需要2N个点值点，那么怎么出现2N个点呢，多选一些点即可。所以在计算N次多项式的点值表达法时要取2N个点值点，我的理解是这2N个点在复平面上直接取 $w_{2N}^k$ ，分成两组N个点（保证了两组中每个点均不同），对于一个系数表达式进行两次N点FFT，最终一个N次系数表达式得到2N个点值点。这一步通过4次FFT完成了两个待乘系数表达式到点值表达式的转换。然后进行后续计算。

至于为什么将2N个点要分成两组N计算，是因为系数表达式有N个点，所以通过FFT一次只能计算N个点值点，需要算两次完成一个表达式的转换，因为需要算的是两个N-1阶表达式的乘积，需要转换两个式子，所以这一步共需4次FFT。而后面的点值表示法再转回稀疏表示法可以直接一次2N点FFT搞定。个人理解，有待考证

关于FFT加速多项式乘法具体见下文：

快速傅里叶变换FFT

FFT(快速傅里叶变换)0基础详解