快速傅里叶变换

Fast Fourier Transform FFT 是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法。FFT 算法显著减少了执行 DFT 所需的乘法和加法次数，从而提高了计算效率。

FFT 的基本原理

FFT 算法基于 DFT 的递归分解，将 DFT 分解为多个较小的 DFT 问题，然后递归地解决这些较小的问题。这种分解利用了“蝶形操作”（butterfly operation），它是一种特定的计算模式，可以减少所需的乘法次数。

FFT 的主要算法

1. Cooley-Tukey 算法：这是最常用的 FFT 算法，它使用分而治之的策略，将 DFT 分解成较小的 DFT，通常是偶数点和奇数点的 DFT。

2. Good-Thomas 算法：这种算法适用于处理矩形数据集，例如二维 FFT。

3. Rader 算法：当输入数据是周期性的或已知具有某些对称性质时，Rader 算法可以减少计算量。

4. Swinney 算法：这种算法适用于处理具有对称性的信号。

FFT 的计算复杂度

FFT 算法将 DFT 的计算复杂度从 ( O (N^2) ) 降低到 ( O (N \log N) )，其中 ( N ) 是输入数据的长度。这意味着对于长度为 ( N ) 的序列，FFT 算法的计算时间与 ( N ) 成线性对数关系，而不是与 ( N^2 ) 成二次方关系。

FFT 的应用

1. 信号处理：FFT 是信号分析中的核心工具，用于频谱分析、滤波和信号检测。

2. 图像处理：在图像压缩和图像分析中，FFT 用于快速变换到频域。

3. 音频处理：在音频分析和处理中，FFT 用于分析音频信号的频率成分。

4. 数据压缩：FFT 用于数据压缩算法中，以减少数据的存储和传输需求。

5. 量子计算：在量子算法中，FFT 是量子傅里叶变换的基础。

6. 机器学习：在某些机器学习算法中，FFT 用于快速计算卷积和相关性。

FFT 算法的高效性使其成为现代计算中不可或缺的一部分，特别是在需要处理大量数据的应用中。

---

AI 结构化补充（2026-05-02）

Fast Fourier Transform FFT 是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法。若把 DFT 写成 Fourier 矩阵乘法 $y=F_{n}c$，直接相乘需要 $n^2$ 次量级的乘法；FFT 利用单位根的递归结构，把核心复乘数降到

$$\frac{1}{2}n{\log }_{2}n$$

量级。

FFT 的基本原理

本页采用正号单位根约定

$$w_n=e^{2\pi i/n},(F_n{)}_{j,k}=w_n^{jk},j,k=0,\dots ,n-1.$$

若采用工程软件中常见的负号单位根，得到的是共轭 Fourier 矩阵；递归结构相同，只是旋转因子取共轭。

FFT 的核心不是改变 DFT 的定义，而是把同一个矩阵乘法重新因式分解。对 $n=2^{\ell }$，每一步把长度 $n$ 的问题拆成两个长度 $m=n/2$ 的问题，再用少量旋转因子合并。这个 radix-2 分解通常称为 Cooley-Tukey 算法，思想也可追溯到 Gauss 对三角插值计算的分解。

定义约定与适用边界

DFT 本身由长度 $n$、单位根符号和归一化约定唯一决定；FFT 只是计算同一个线性变换的快速算法，不是近似算法。常见归一化有三种：正变换不归一、逆变换除以 $n$；正变换除以 $n$；或正逆都除以 $\sqrt{n}$。只有最后一种使 Fourier 矩阵本身成为酉矩阵。

radix-2 FFT 要求 $n=2^{\ell }$。若 $n$ 不是二的幂，仍可用混合基 Cooley-Tukey、Rader、Bluestein 等分解处理；若 $n$ 是素数，不能直接做偶奇递归。补零可以把数据嵌入更长的 DFT 以便使用高效长度，但它改变的是采样频率网格，不等同于原长度 DFT 的值。

输入可以是实数或复数。实输入的 DFT 满足共轭对称

$$y_{n-j}=\overline{y_j},$$

所以实际软件常用 real FFT 只计算一半频谱；复输入则没有这个对称性。

FFT 的主要算法

1. Cooley-Tukey 算法：本页主线采用 radix-2 情形，把输入按偶数下标和奇数下标分成两个半长 DFT，再通过蝶形合并得到完整输出。

2. Good-Thomas、Rader 等变体：这些算法处理不同长度分解或素数长度等情形；在这里只作为 FFT 家族的补充背景，不作为本页推导主线。

一步偶奇分解

令 $m=n/2$，把输入向量按下标奇偶拆成

$$c^{\prime }=(c_0,c_2,\dots ,c_{n-2}{)}^{\mathsf{T}},c^{\prime \prime }=(c_1,c_3,\dots ,c_{n-1}{)}^{\mathsf{T}}.$$

先计算两个半长 Fourier 变换

$$y^{\prime }=F_m{c}^{\prime },y^{\prime \prime }=F_m{c}^{\prime \prime }.$$

那么完整输出 $y=F_{n}c$ 的前半和后半由

$$y_j=y_j^{\prime }+w_n^j{y}_j^{\prime \prime },y_{j+m}=y_j^{\prime }-w_n^j{y}_j^{\prime \prime },j=0,\dots ,m-1$$

给出。

推导直接来自把求和按偶数项与奇数项分开：

$$y_j=\sum _{k=0}^{n-1}{w}_n^{jk}{c}_k=\sum _{r=0}^{m-1}{w}_n^{2jr}{c}_{2r}+w_n^j\sum _{r=0}^{m-1}{w}_n^{2jr}{c}_{2r+1}.$$

关键关系是

$$w_n^2=e^{2\pi i/m}=w_m,$$

因此两个求和正是 $F_m{c}^{\prime }$ 与 $F_m{c}^{\prime \prime }$。对后半输出 $y_{j+m}$，偶数项仍给出同一个 $y_j^{\prime }$，奇数项多出因子

$$w_n^m=e^{\pi i}=-1,$$

所以合并公式中的第二项变为负号。这就是蝶形合并的代数来源。

Fourier 矩阵分解形式

把上面的偶奇拆分写成矩阵乘积，令 $P_{\mathrm{eo}}$ 表示 even-odd permutation，把输入重排为

$$(c_0,c_2,\dots ,c_{n-2},c_1,c_3,\dots ,c_{n-1}{)}^{\mathsf{T}}.$$

若 $w^n=1$ 且 $F_n$ 的条目为 $(F_n{)}_{j,k}=w^{jk}$，则

$$F_n=\left[\begin{array}{cc}I& D\\ I& -D\end{array}\right]\left[\begin{array}{cc}{F}_{n/2}& 0\\ 0& F_{n/2}\end{array}\right]P_{\mathrm{eo}},$$

其中

$$D=\mathrm{diag}(1,w,w^2,\dots ,w^{n/2-1}).$$

第一因子完成蝶形合并，第二因子执行两个半长 Fourier 变换，第三因子只改变输入顺序。未归一化 Fourier 矩阵的列正交性可写成

$$F_n^{\ast }{F}_n=nI,$$

等价地，归一化矩阵 $F_n/\sqrt{n}$ 是酉矩阵。

当 $n=2^{\ell }$ 时，这个分解可递归 $\ell$ 层。每一层只有 $n/2$ 个来自对角矩阵 $D$ 的核心复乘法，因此计算 $F_{n}x$ 的核心乘法数约为

$$\frac{1}{2}n\ell =\frac{1}{2}n{\log }_{2}n.$$

$F_4$ 的三因子分解

四点情形已经包含 FFT 的完整结构。设 $w_4=i$，则

$$F_4=\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 1& 0& i\\ 1& 0& -1& 0\\ 0& 1& 0& -i\end{array}\right)\left(\begin{array}{cccc}1& 1& 0& 0\\ 1& -1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& -1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right).$$

最右侧矩阵是 even-odd permutation，把 $(c_0,c_1,c_2,c_3{)}^{\mathsf{T}}$ 变成 $(c_0,c_2,c_1,c_3{)}^{\mathsf{T}}$。中间矩阵是两个 $F_2$ 的块对角和，分别计算偶项与奇项的二点变换。最左侧矩阵执行蝶形合并：用 $1,i$ 乘奇项半变换，并与偶项半变换相加或相减，得到 $y_0,y_1,y_2,y_3$。

FFT 的计算复杂度

直接计算 $F_{n}c$ 需要 $n^2$ 次量级的乘法，因为 $F_n$ 有 $n^2$ 个非零元素。FFT 的一次拆分只把工作量近似减半还不够，真正的节省来自继续递归：

$$F_n\to 2F_{n/2}\to 4F_{n/4}\to \cdots \to n{F}_1.$$

若 $n=2^{\ell }$，共有 $\ell ={\log }_{2}n$ 层。每一层的蝶形合并需要 $n/2$ 个旋转因子乘法，因此核心复乘数为

$$\frac{1}{2}n\ell =\frac{1}{2}n{\log }_{2}n.$$

例如 $n=1024=2^{10}$ 时，直接乘法约为

$$1024^2=1048576$$

次，约一百万次；FFT 的旋转因子乘法为

$$\frac{1}{2}\cdot 1024\cdot 10=5120$$

次，节省约两个数量级。

位反转顺序

每一层都先把偶数下标放在奇数下标之前。把所有层的 even-odd permutation 合起来，会得到二进制位反转顺序。以 $n=8$ 为例，把下标写成三位二进制并反转：

$$\begin{array}{ccc}\text{原下标}& \text{二进制}& \text{反转后}\\ 0& 000& 0\\ 1& 001& 4\\ 2& 010& 2\\ 3& 011& 6\\ 4& 100& 1\\ 5& 101& 5\\ 6& 110& 3\\ 7& 111& 7\end{array}$$

所以

$$0,1,2,3,4,5,6,7⟼0,4,2,6,1,5,3,7.$$

许多迭代式 FFT 实现先按这个顺序重排输入，再逐层执行蝶形合并。

线性代数解释与唯一性

从矩阵分解角度看，FFT 把稠密 Fourier 矩阵写成置换矩阵、块对角小 Fourier 矩阵、对角旋转因子和蝶形矩阵的乘积。每个因子都很稀疏或结构化，因此整体乘法比直接使用 $F_n$ 便宜得多。归一化后，整个变换保持二范数：

$${\Vert \frac{1}{\sqrt{n}}{F}_{n}x\Vert }_2=\Vert x{\Vert }_2,$$

这就是 Parseval 恒等式的矩阵形式。

FFT 分解不唯一。可以按时间抽取或频率抽取组织蝶形，可以选择不同 radix，也可以把同一组旋转因子分配到不同层。只要符号和归一化一致，这些算法计算的是同一个 DFT；差异主要体现在内存访问顺序、常数因子、并行性和舍入误差分布。

边界情形中，$n=1$ 时 DFT 是恒等变换，不需要蝶形；$n=2$ 时只有一次加减法。数值上，FFT 的误差通常随层数增长，约与 $\log n$ 相关，而直接乘法有更多运算但舍入路径不同。因此在高精度或病态频谱问题中，仍要明确归一化、缩放和浮点精度。

FFT 的应用

1. 信号处理：FFT 是信号分析中的核心工具，用于频谱分析、滤波和信号检测。

2. 图像处理：在图像压缩和图像分析中，FFT 用于快速变换到频域。

3. 音频处理：在音频分析和处理中，FFT 用于分析音频信号的频率成分。

4. 数据压缩：FFT 用于数据压缩算法中，以减少数据的存储和传输需求。

5. 量子计算：在量子算法中，FFT 是量子傅里叶变换的基础。

6. 机器学习：在某些机器学习算法中，FFT 用于快速计算卷积和相关性。

FFT 算法的高效性使其成为现代计算中不可或缺的一部分，特别是在需要处理大量数据的应用中。