第1章 FFT基础与数学原理

一、FFT基础与数学原理

各位同学好，我是你们的老朋友。今天咱们开始聊FFT预处理CNN推理优化这个话题。说实话，我第一次接触这个方向时，也觉得有点玄乎——好好的卷积为什么要转到频域去做？但后来在实际项目中踩过几次坑，才真正体会到它的价值。

这一章，我们先打好基础。把傅里叶变换、DFT、FFT这些概念彻底搞明白。嗯，别急着翻代码，数学原理通了，后面优化才能得心应手。

傅里叶变换到底在干什么？说白了，就是把一个信号拆解成不同频率的正弦波。

我打个比方。你听到一首交响乐，耳朵里听到的是所有乐器同时演奏的混合声音。但你的大脑其实能分辨出小提琴、大提琴、长笛各自的声音。傅里叶变换做的就是这件事——把一个复杂的信号，分解成不同频率的"纯音"。

在图像处理里，这个思想同样适用。一张图片可以看作二维信号，高频部分对应边缘、纹理这些细节，低频部分对应平滑区域、背景。我在做AI芯片部署时，经常利用这个特性来做预处理加速。

核心思想：时域（或空域）中复杂的卷积运算，在频域中会变成简单的逐元素乘法。这就是FFT加速CNN的理论基础。

计算机只能处理离散数据，所以我们需要离散傅里叶变换。公式长这样：

X[k] = Σ(n=0 to N-1) x[n] · e^(-j·2π·k·n/N)

别被这个公式吓到。我来拆解一下：

这个公式的计算量有多大？对于每个k，都要做N次复数乘法和加法。总共N个k，所以复杂度是O(N²)。

我记得第一次在嵌入式芯片上实现DFT时，处理一张256×256的图像，等了快10秒才出结果。当时我就想，这玩意儿不优化根本没法用。后来才知道，FFT就是来解决这个问题的。

FFT的核心思想就四个字：分而治之。

怎么分？把N点DFT拆成两个N/2点DFT。怎么治？用蝶形运算把结果合并起来。

蝶形运算的图示长这样：

    a ──→ (+)──→ A = a + b·W
          ↗
    b ──→ (×W)──→ B = a - b·W

其中W是旋转因子。这个结构像蝴蝶的翅膀，所以叫蝶形算法。

具体步骤：

递归下去，直到分解成2点DFT。2点DFT的计算就简单了：

X[0] = x[0] + x[1]
X[1] = x[0] - x[1]

这样一分解，复杂度从O(N²)降到了O(N·log₂N)。N=1024时，DFT需要约100万次运算，FFT只需要约1万次。差距有多大？你想想看。

避坑指南：我曾经在部署时直接用标准FFT库处理非2的幂次长度的数据，结果性能反而更差。后来才意识到，FFT要求输入长度是2的幂次。如果数据长度不对，需要做补零或截断处理。

时域和频域，其实是同一个信号的两种观察角度。

域	含义	在图像中的体现
时域/空域	信号随时间或空间变化	像素值在空间位置上的分布
频域	信号在不同频率上的能量分布	低频=平滑区域，高频=边缘纹理

为什么这对CNN优化很重要？

因为卷积在空域是滑动窗口计算，复杂度是O(K²·N²)，K是卷积核大小。但在频域，卷积变成了逐元素乘法，复杂度只有O(N²)。

我做过一个实验：用3×3卷积核处理512×512的图像。空域计算需要约2.3亿次乘法，而FFT方法只需要约5000万次。速度提升了4倍多。

当然，FFT也有代价——需要额外的内存来存储频域数据，而且对非2的幂次尺寸要做处理。这些细节我们后面章节会逐一展开。

注意：FFT加速卷积并非万能。当卷积核很小时（比如1×1），空域计算反而更快。我建议在卷积核尺寸≥5×5时再考虑FFT方案。

好了，这一章的基础知识就讲到这里。下一章我们会深入FFT在CNN中的具体应用，包括如何把卷积操作映射到频域、如何处理多通道数据。到时候我会分享一些实际部署中的调优经验。

记住一句话：理解原理，才能做好优化。别急着调参数，先把这些数学概念吃透。