3. 傅里叶变换基础：从连续到离散
好，咱们进入正题。傅里叶变换，这个词你肯定听过。但说实话，我当年刚接触时也是一头雾水——这东西到底跟卷积加速有什么关系？
别急，我带你一步步拆解。说白了，傅里叶变换就是一把「手术刀」，能把信号从时域切到频域。在频域里做卷积，比在时域里快得多。这就是FFT加速的核心逻辑。
3.1 连续傅里叶变换：理论根基
先看连续情况。一个连续信号 \( f(t) \)，它的傅里叶变换长这样：
F(ω) = ∫_{-∞}^{∞} f(t) · e^{-jωt} dt嗯，公式看着有点吓人。但你想想看，它其实在做什么？
它把信号 \( f(t) \) 分解成不同频率的正弦波。\( e^{-jωt} \) 就是旋转因子，积分的过程就是在「匹配」每个频率成分的强度。
时域 vs 频域：
- 时域：横轴是时间，看信号怎么随时间变化
- 频域：横轴是频率，看信号包含哪些频率分量
我在项目中遇到过一个问题：一个音频信号在时域里看起来全是噪声，但转到频域后，发现其实是50Hz的工频干扰。这就是频域分析的价值——有些东西在时域里看不清，换个角度就一目了然。
核心思想：时域里的卷积，等价于频域里的乘法。这是FFT加速卷积的数学基础。
3.2 离散傅里叶变换(DFT)：计算机能处理的形式
连续信号很美，但计算机不认。计算机只能处理离散的、有限长的数据。所以就有了DFT。
DFT的公式：
X[k] = Σ_{n=0}^{N-1} x[n] · e^{-j(2π/N)kn}其中：
- \( x[n] \)：输入序列，长度N
- \( X[k] \)：输出频谱，k=0,1,...,N-1
- \( e^{-j(2π/N)kn} \)：旋转因子，也叫「基」
说白了，DFT就是把N个时域点，映射到N个频域点。每个频域点代表一个特定频率的强度。
DFT的几个关键点：
| 概念 | 说明 |
|---|---|
| 频率分辨率 | Δf = fs / N，fs是采样率，N是点数 |
| 频谱对称性 | 实信号的DFT，幅度谱是偶对称的 |
| 计算复杂度 | 直接DFT是O(N²)，N大时慢得离谱 |
我曾经踩过的坑：直接拿DFT做卷积加速，N=1024时还能忍，N=4096时直接卡死。后来才意识到，DFT的O(N²)复杂度在工程上根本不可行。这就是为什么需要FFT。
3.3 时域与频域的关系：卷积定理
好，现在讲最核心的部分——卷积定理。
卷积定理：
时域卷积 → 频域乘法
x(t) * h(t) ⇔ X(ω) · H(ω)反过来也成立：
时域乘法 → 频域卷积
x(t) · h(t) ⇔ X(ω) * H(ω)这意味着什么？
你想想看，在时域里做卷积，每个输出点都要做N次乘加，复杂度O(N²)。但转到频域后，只需要做一次逐元素乘法，复杂度O(N)。
当然，转来转去也有开销。但FFT的出现，让这个「转」的过程变得极快——O(N log N)。
完整的加速流程：
- 对输入x和卷积核h分别做FFT，转到频域
- 在频域做逐元素乘法：Y = X · H
- 对Y做IFFT，转回时域
总复杂度：O(N log N) + O(N) + O(N log N) ≈ O(N log N)
相比直接卷积的O(N²)，当N很大时，优势巨大。
我的个人习惯：在工程实现时，我会先判断卷积核大小。如果核很小（比如3×3），直接卷积反而更快。FFT加速适合大核卷积，比如7×7以上。别盲目用FFT，要因地制宜。
3.4 离散卷积与循环卷积：一个容易忽略的细节
嗯，这里要注意。DFT对应的卷积，其实是循环卷积，不是线性卷积。
什么意思？
线性卷积：信号和核在时间轴上滑动，边缘补零。
循环卷积：信号和核在圆周上滑动，边缘会「卷回来」。
如果你直接用DFT做卷积，得到的是循环卷积的结果。这会导致边缘出现混叠——信号尾部会污染头部。
解决办法：补零。
把信号长度从N扩展到N+M-1（M是核长度），再做DFT。这样循环卷积就等价于线性卷积了。
# 伪代码示例
N = len(x)
M = len(h)
L = N + M - 1 # 补零后的长度
X = FFT(x, L) # 补零到L长度
H = FFT(h, L)
Y = X * H
y = IFFT(Y) # 取前N+M-1个有效值我曾经犯过的错：第一次实现FFT卷积加速时，忘了补零。结果输出结果在边缘处全是错的，排查了半天才发现是循环卷积在作怪。从那以后，我每次写FFT卷积都会先检查补零长度。
3.5 小结：从理论到实践的桥梁
回顾一下：
- 连续傅里叶变换：理论基石，把信号从时域映射到频域
- 离散傅里叶变换(DFT)：计算机能处理的形式，但O(N²)太慢
- 时域与频域的关系：卷积定理是加速的核心——时域卷积等价于频域乘法
- 循环卷积陷阱：补零是必须的，否则结果会出错
下一章，我会带你深入FFT的具体实现——如何把O(N²)的DFT变成O(N log N)的FFT。到时候你会看到，Cooley-Tukey算法到底有多巧妙。
记住一句话：理解频域，你就拿到了加速卷积的钥匙。