相关数学知识

参考内容[超详细易懂FFT]

[超详细易懂FFT]：https://blog.csdn.net/Flag_z/article/details/99163939

Fast Fourier Transformation (FFT)

• 快速傅里叶变换

多项式表示方法

• 系数表示法
• 点值表示法（n个点能够确定一条多项式）

多项式相乘

• 系数表示法，枚举，复杂度为\(O(n^2)\)
• 点值表示法
  • 假如两个多项式取相同的x，得到不同的y值，只需要将对应的y值相乘即可
  • 此时枚举复杂度只有\(O(n)\)

这时问题转换为如何将多项式的系数表示法，转换成点值表示法

• 朴素系数转点值的算法叫离散傅里叶变换（DFT）
• 优化后为快速傅里叶变换（FFT）
• 点值转系数的算法叫离散傅里叶逆变换（IDFT）

• 优化后为快速傅里叶逆变换（IFFT）

• 傅里叶变换的基本思想

  • 一个复杂的时域信号能够分解成若干个简单的正弦波和余弦波

离散傅里叶变换（DFT）

\[X[k]=\sum^{N-1}_{n=0}x[n]\cdot e^{-i\frac{2\pi}{N}kn}\]

• \(x[n]\):时域信号
• \(X[k]\):频域信号
• \(k\):频率索引\((k=0,1,\dots)\)

由于不同频率的正弦波的内积为0，只有频率相同的波才能得到内积值

所以计算的过程实际上是在问“信号和这个频率的正弦波有多相似”