快速傅里叶变换FFT算法的用途

正好复习信号到FFT了,想起来前段时间放了挺久的FFT大数乘法,顺便研究下。

普通的高精度乘法的复杂度需要$O(n^2)$,用了押位之后,一般押4位的话能够达到$O(n^2/16)$,看上去可能效果不错,但仍然是同一个数量级的。

对付更大一点的变态数据(。。。ACM赛场上很少有卡这货的吧。。。-_-////)就需要用的$O(nlogn)$的FFT大数乘法算法了。

数学基础


首先基础是DFT,FFT是DFT的一种快速算法。

从N点DFT出发:

$$\begin{align}
X[K]&=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi K}{N}n}\\
&=\sum_{n=0}^{\frac{N}{2}-1}x[2n]e^{-j\frac{2\pi K}{N}2n}+\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]e^{-j\frac{2\pi K}{N}(2n+1)}\\
&=\sum_{n=0}^{\frac{N}{2}-1}x_1[n]e^{-j\frac{2\pi K}{\frac{N}{2}}n}+\sum_{n=0}^{\frac{N}{2}-1}x_2[n]e^{-j\frac{2\pi K}{\frac{N}{2}}n}e^{-j\frac{2\pi K}{N}}\\
&=X_1[K]+e^{-j\frac{2\pi K}{N}}X_2[K]
\end{align}$$

也就是说,通过上述变换,我们成功地将一个N点得DFT拆成了2个$\frac{N}{2}$点的DFT

分析一下复杂度:

首先N点DFT的结果$X[K]$有N点,每个点的计算都要对$x[n]$的n个序列值乘上负指数求和,复杂度是$O(n^2)$

如果每一步都采用上面的那种变换方式,那么可以把多出来的一维降掉,变成$O(nlogn)$,这也就是快速傅里叶变换(FFT)了!

更进一步

然而上面这个式子简化到最后是有问题的。

我们把一个N点的DFT拆成$\frac{N}{2}$点的DFT之后,下面得到的两个序列$X_1[K]$和$X_2[K]$都只有$\frac{N}{2}$点。

也就是说直接这么写,当K大于$\frac{N}{2}-1$之后,放在代码里面,后面部分就会出现数组越界的问题!!

继续分析后面部分:

$$\begin{align}
X_1[K]&=\sum_{n=0}^{\frac{N}{2}-1}x_1[n]e^{-j\frac{2\pi K}{\frac{N}{2}}n}\\
X_1[\frac{N}{2}+K]&=\sum_{n=0}^{\frac{N}{2}-1}x_1[n]e^{-j\frac{2\pi}{\frac{N}{2}}(\frac{N}{2}+K)n}\\
&=\sum_{n=0}^{\frac{N}{2}-1}x_1[n]e^{-j\frac{2\pi K}{\frac{N}{2}}n}e^{-j2\pi n}\\
&=-\sum_{n=0}^{\frac{N}{2}-1}x_1[n]e^{-j\frac{2\pi K}{\frac{N}{2}}n}\\
&=-X_1[K]
\end{align}$$

好,这样问题就解决了。

令:

$$W_N^K=e^{-j\frac{2\pi K}{N}}$$

则重新整理上面的运算单元可以得到:

蝶形运算

这就是著名的蝶形运算了。

然后整个图画出来是这样的:

8

8点FFT

或者:

16

16点FFT

FFT的用途

综上,FFT就是专门为计算机快速运算而设计的,1点变2点,2点变4点,4点变8点……这样就能在原始数据(原数组)的基础上不断计算下一层的结果,最终完成整个DFT的快速计算。

写代码的话,第一步是处理一下最左边一排原始数据的摆放顺序,是按照二进制逆序排过来的,然后一层一层求和迭代即可。

多项式


讲完FFT之后,下面重点来了。

多项式的系数表示法

关于变量$x$的多项式可以表示成:

$$A(x)=a_0+a_1x+a_2x^2+…+a_{n-1}x^{n-1}=\sum_{j=0}^{n-1}a_jx^j$$

多项式是个广泛的概念,如果把大数对应到多项式上面去那就是类似这样:

$$1234=4+3*10+2*10^2+1*10^3$$

若有:

$$B(x)=\sum_{j=0}^{n-1}b_jx^j$$

则:

$$A(x)+B(x)\Rightarrow C(x)=\sum_{j=0}^{n-1}c_jx^j$$

$$c_j=a_j+b_j$$

$$A(x)\cdot B(x)\Rightarrow C(x)=\sum_{j=0}^{2n-2}c_jx^j$$

$$c_j=\sum_{k=0}^{j}a_kb_{j-k}$$

分别是多项式加法和多项式乘法

注意:多项式乘法的过程就是多项式系数卷积

多项式的点值表示法

令:

$$y_k=A(x_k)$$

则一个次数界为n的多项式$A(x)$的点值表示就是n个这样的点值(任意n个)对所形成的集合:

$$\{(x_0,y_0),(x_1,y_1),…,(x_{n-1},y_{n-1})\}$$

从系数表示法写成点值表示法就是简单地说找n个不同的$x$代进去求出$y$,然后写在一起就行了。

然而用点值确定系数就是个线性求解的过程,称为插值,也是可以算的。

那么点值表示法有什么好处呢?

设上面的点值表示是$A(x)$的,如果已知$B(x)$的是:

$$\{(x_0,y’_0),(x_1,y’_1),…,(x_{n-1},y’_{n-1})\}$$

那么:

$$A(x)+B(x)\Rightarrow C(x)=\{(x_0,y_0+y’_0),(x_1,y_1+y’_1),…,(x_{n-1},y_{n-1}+y’_{n-1})\}$$

$$A(x)\cdot B(x)\Rightarrow C(x)=\{(x_0,y_0y’_0),(x_1,y_1y’_1),…,(x_{n-1},y_{n-1}y’_{n-1})\}$$

分别是多项式加法和多项式乘法

关键在于,这里的多项式乘法的复杂度是$O(n)$!!!!!

因此只要能够想办法快速地进行两种表示法之间的转换,那么就可以先从系数表示法转换成点值表示法,用$O(n)$相乘之后,再快速转换回去,即可做到快速的多项式相乘


所以!!!!

转换的关键就是!!!!

FFT!!!!


以下是多项式乘法的过程:

  1. 次数界增加一倍:通过加入n个值为0的高阶系数,将整个次数界扩充至$2n$
  2. 求值,两次FFT分别求出$A(x)$和$B(x)$的长度为$2n$的点值表示$A(\omega)$和$B(\omega)$
  3. 逐个相乘得到$C(\omega)$
  4. 再做一次FFT,求逆傅里叶变换得到$C(x)$

实现代码详见模板题:HDU 1402 A * B Problem Plus 快速高精度乘法(FFT)

0%