FFT算法前身DFT（离散傅里叶变换）

信号与系统又大又小，今天这个东西是实践的前提，DFT到FFT，DFT在理论上面是成功的，但是实践中这个计算太吃算力了。

DFT 是把一段有限长的离散时域信号转换为离散频域表示的数学工具。数学表达式是：

其中：

：时域信号，长度为 ；

：频域序列，表示信号在第 个离散频率分量上的强度和相位；

指数项 表示一组基底复指数函数。

如果把复指数展开：

那么：

这里就看得很清楚：DFT 就是信号与一组离散余弦波和正弦波的内积。

聊聊复指数展开

复指数展开就是用 欧拉公式 把指数函数表示为余弦和正弦的组合：

在 DFT 中的应用

DFT 的定义式为：

代入欧拉公式展开：

于是：

这样就把 DFT 拆成了 与余弦（实部）和正弦（虚部）的相关；复指数本质上是“正弦+余弦”的组合，因此 DFT 就是信号和一组不同频率的正弦/余弦基函数做内积。

几何意义

几何意义

这张图展示了复指数 在复平面上的几何意义：

红色箭头：复指数向量 ，在单位圆上旋转。

蓝色线段：投影到实轴，值为 。

绿色线段：投影到虚轴，值为 。

因此：

直观体现了 复指数就是“余弦 + 正弦”分解。

内积 / 投影的直观理解

内积运算本质上就是计算两个向量的相似度；我们把 和 看作一组基函数（就像几何里的“坐标轴”）；把信号 投影到这些基函数上，投影的系数就是该频率分量的“含量”。

实部：代表与余弦基函数的相似程度；

虚部：代表与正弦基函数的相似程度。

所以 的模值 就表示信号在“第 k 个离散频率”上的能量大小，相位则由实部与虚部的比值决定。

与连续傅里叶变换的类比

连续傅里叶变换：把信号投影到一组连续的正弦/余弦函数上，得到连续频谱。

DFT：因为采样和截断，投影基底变成了有限组离散频率的正弦/余弦函数，只得到 有限个频率点 的信息。

核心原理

DFT 可以看作把信号与一组离散正弦/余弦波做相关（内积），测出各个频率成分的“投影”；它产生的结果是 周期性的，频谱每 点重复一次；对实信号而言，频谱满足共轭对称：实部偶对称、虚部奇对称。

DFT 是信号频谱分析的基础；FFT 的出现使得大规模频谱分析成为可能（例如 N=1024 时，FFT 比直接 DFT 快 300 倍以上）。

相关法（Correlation Method）：双重循环，把输入和正弦余弦波逐点相乘累加，复杂度约为 。 示例代码（BASIC/Fortran）就是用循环加三角函数计算。（这就是从表面的公式来的）

为什么用 FFT：同样的 DFT，复杂度从 N² 降到 N·log₂N

直接相关法做复数 DFT：双重循环，运算量 ∝ N²，点数上千就几乎不可用。

FFT 是“如何高效计算同一个 DFT”的算法：通过分解与复用正弦子结构，把运算量降到 N·log₂N，N 越大优势越明显；同时更少的乘加也意味着更小的舍入误差。

实际计算一个

image-20251010180635552

image-20251010180635552

image-20251010180642774

image-20251010180642774

使用“纯循环相关法”的 DFT demo，并与 NumPy 的 FFT 做了对比；上面两张图分别是单边幅度谱与单边相位谱，打印了与 np.fft.fft 的复谱 RMSE（本例约 6e-12，基本等于浮点舍入误差）。

N=1024, 采样率 fs=1000.0 Hz
与 NumPy FFT 复谱的 RMSE = 6.054e-12
RMSE 应接近浮点舍入误差（本例通常 ~1e-10 量级）。