DFT 与 FFT

​ 时隔 1 年，梦幻的知识又以新的形态向我袭来，重新体验 FFT 算法的巧夺天工...

DFT：离散傅里叶变换，离散的时域 变换得到 离散周期的频域

FFT：快速傅里叶变换，借助 分治递归 来提高计算速度的快速 DFT

​ 首先先复习一下 DFT 的引入过程，因为我们的计算系统是离散的存储方式，输入的是离散的 时域 数据，也希望输出的是离散的 频域 信息，然而普通的 DTFT（时域离散信号的傅里叶变换）得到的是连续的频域，所以 DFT 就此诞生。

DFT 的定义

​ 我们先不急着引入公式，从 DTFT（） 的角度出发，我们的连续频域无法被离散的系统保存起来，所以我们也希望像时域抽样一样抽样频域，因为 DTFT 时域离散、频域周期（ 为周期），我们只需要讨论一个周期的离散即可，定义一个 将一个周期的频域分成 份，也就是说 是 上的 的采样点数。

​ 上述的内容是以 DTFT 的角度出发思考的，我们现在换一种思维来思考这个问题，从多项式乘法的角度出发来审视这个问题。可能你会有所疑惑多项式和傅里叶变换有什么关系吗，先别着急听我细细道来。

多项式乘法

系数乘法，时间复杂度

点值乘法，时间复杂度

多项式乘法例如以下步骤

​ 显而易见点值乘法的运算速率是极快的，但是我们需要将系数乘法先转换到点值乘法，这是否有点熟悉的感觉，时域卷积困难转到频域相乘，可以看出来系数乘法转到点值乘法只需要确定 然后带入 和 即可但是这个过程是 ，之后我们会使用 FFT 降低它的复杂度为 ，这里先跳过这部分。

​ 现在我们再回到对于 DFT 的讨论，首先离散的时域得到周期的频域，而周期的时域将会得到离散的频域，我们可以构造一个周期的输入来获取一个离散的频域，这时伟大的傅里叶就赐予我们 个神奇的点 ，这是一个神奇的东西，有着周期性、对称性、折半性优良性质，其数学表示式：

我们将这些点和我们原有的时域的那些点相乘然后再相加，诶这是什么，多项式乘法！我们将 带入到多项式乘法的 里面我们就得到了我们想要的 DFT 变换式：

例如在多项式乘法里我们将这 个点 带入到 中就是这个样子：

用矩阵乘法的形式就是这个样子：

FFT

详见 奇妙的快速傅里叶变换