【FFT】快速傅里叶变换

一、复数

1、定义

复数：设 $a$，$b$??为实数，$i^{2}=?1$?，形如 $a+bi$?的数叫复数，其中 $i$?被称为虚数单位，复数域是目前已知最大的域

在复平面中，$x$?代表实数，$y$?轴（除原点外的点）代表虚数，从原点 $(0,0)$ 到 $(a,b)$ 的向量表示复数 $a+bi$

模长：从原点 $(0,0)$ 到点 $(a,b)$ 的距离，即 $sqrt{a^2+b^2}$

幅角：假设以逆时针为正方向，从 $x$?轴正半轴到已知向量的转角的有向角叫做幅角

2、运算法则

加法：$(a+bi)+(c+di)=(a+c)+(b+d)i$

减法：$(a+bi)-(c+di)=(a-c)+(b-d)i$

乘法：$(a+bi)?(c+di)=(ac?bd)+(bc+ad)i$

3、单位根

在复平面上，以原点为圆心，$1$?为半径作圆，所得的圆叫单位圆。以圆点为起点，圆的 $n$?等分点为终点，做第 $n$?个向量，设幅角为正且最小的向量对应的复数为 $omega_{n}^{1}$，称为 $n$?次单位根。

根据复数乘法的运算法则，其余 $n?1$ 个复数为?$omega_{n}^{2}$，?$omega_{n}^{3}$，?$omega_{n}^{4}$……?$omega_{n}^{n}$

那么如何计算它们的值呢？这个问题可以由欧拉公式解决

$omega_{n}^{k}=cos k *frac{2pi}{n}+isin k*frac{2pi}{n}$

4、单位根的性质

• $omega_{n}^{k}=cos k *frac{2pi}{n}+isin k*frac{2pi}{n}$
• $omega_{2n}^{2k}=omega_{n}^{k}$
• $omega_{n}^{k+frac{n}{2}}=-omega_{n}^{k}$
• $omega_{n}^{0}=omega_{n}^{n}=1$