跳转到内容
← 返回算法
经典算法计算机科学 · 数学 · 信号处理约 27 分钟阅读

快速傅里叶变换

Fast Fourier Transform (FFT)

1965 年，James Cooley 和 John Tukey 在 Mathematics of Computation 上发表了一篇五页的论文"An Algorithm for the Machine Calculation of Complex Fourier Series"，提出了快速傅里叶变换（FFT）算法。…

FFT傅里叶变换分治信号处理

1965 年，James Cooley 和 John Tukey 在 Mathematics of Computation 上发表了一篇五页的论文"An Algorithm for the Machine Calculation of Complex Fourier Series"，提出了快速傅里叶变换（FFT）算法。

据 IBM 研究员 Cooley 回忆，算法的关键思路来自统计学家 John Tukey——1963 年，Tukey 在肯尼迪总统科学顾问委员会（PSAC）讨论"如何用环绕苏联的传感器探测其地下核试验"的会议上，把这套快速计算傅里叶变换的想法写了下来；随后 IBM 的 Cooley 将其整理成可在计算机上运行的算法并发表。

几十年后，IEEE 将 FFT 列为 20 世纪十大算法之一。从 MP3 音频压缩，到 JPEG 图像、5G 通信、医学 MRI 图像重建、天文信号处理——FFT 无处不在，是数字时代基础设施的核心算法之一。

什么是傅里叶变换？

约瑟夫·傅里叶（Joseph Fourier）在 1822 年的《热的解析理论》中提出：任何周期信号都可以分解为一系列正弦波和余弦波的叠加。这个思想的意义在于：时域（time domain）和频域（frequency domain）是同一信号的两种等价表示。在时域中，信号是随时间变化的波形；在频域中，信号是各频率成分的强度分布（频谱）。

离散傅里叶变换（DFT）将长度为 $n$ 的离散信号 x0,x1,…,xn−1x_0, x_1, \ldots, x_{n-1} 变换为频域表示：

Xk=∑j=0n−1xj⋅e−2πijk/n,k=0,1,…,n−1X_k = \sum_{j=0}^{n-1} x_j \cdot e^{-2\pi i jk / n}, \quad k = 0, 1, \ldots, n-1

其中 i=−1i = \sqrt{-1}，e−2πijk/n=cos⁡(2πjk/n)−isin⁡(2πjk/n)e^{-2\pi i jk/n} = \cos(2\pi jk/n) - i \sin(2\pi jk/n) 是单位根。

直接计算 DFT：对每个 XkX_k 需要 $n$ 次复数乘法，共 $n$ 个输出，总计 O(n2)O(n^2) 操作。对 n=106n = 10^6（百万点 DFT），O(n2)=1012O(n^2) = 10^{12} 次操作，以每秒 10910^9 操作计，需要约 16 分钟。

FFT：$O(n \log n)$ 的奇迹

FFT 利用 DFT 的数学结构，用分治将 O(n2)O(n^2) 降至 O(nlog⁡n)O(n \log n)。

关键观察（Cooley-Tukey）：设 n=2mn = 2^m（$n$ 是 2 的幂），将 DFT 分成奇偶两半：

Xk=∑j=0n/2−1x2j⋅ωn2jk+ωnk∑j=0n/2−1x2j+1⋅ωn2jkX_k = \sum_{j=0}^{n/2-1} x_{2j} \cdot \omega_n^{2jk} + \omega_n^k \sum_{j=0}^{n/2-1} x_{2j+1} \cdot \omega_n^{2jk}

其中 ωn=e−2πi/n\omega_n = e^{-2\pi i/n}（$n$ 次单位根）。注意 ωn2jk=ωn/2jk\omega_n^{2jk} = \omega_{n/2}^{jk}，所以：

Xk=DFTn/2(偶数项)k+ωnk⋅DFTn/2(奇数项)kX_k = \text{DFT}_{n/2}(\text{偶数项})_k + \omega_n^k \cdot \text{DFT}_{n/2}(\text{奇数项})_k

Xk+n/2=DFTn/2(偶数项)k−ωnk⋅DFTn/2(奇数项)kX_{k+n/2} = \text{DFT}_{n/2}(\text{偶数项})_k - \omega_n^k \cdot \text{DFT}_{n/2}(\text{奇数项})_k

这意味着：$n$ 点 DFT 可以分解为两个 $n/2$ 点 DFT，再用 $O(n)$ 合并。递推式 $T(n) = 2T(n/2) + O(n)$ 由主定理给出 T(n)=O(nlog⁡n)T(n) = O(n \log n)。对同样的 n=106n = 10^6，O(nlog⁡n)≈2×107O(n \log n) \approx 2 \times 10^7 操作——约 0.02 秒。加速比超过 5 万倍。

"蝶形运算"可视化

FFT 最底层的计算单元是"蝶形运算（Butterfly Operation）"：

a ───┬──────── a + W·b
     │
b ───┴── W ─── a - W·b
```

其中 $W$ 是单位根因子。长度为 $n$ 的 FFT 由 log⁡2n\log_2 n 层、每层 $n/2$ 个蝶形运算构成——总计 n2log⁡2n\frac{n}{2} \log_2 n 次复数乘法。

这个规则的蝶形结构使得 FFT 易于硬件实现（VLSI、DSP 芯片），是 FFT 成为工程标准的重要原因。

手算走查：$n = 4$ 的 DFT 与 FFT

公式看懂了不等于知道它在算什么。取最小的非平凡例子 $x = [1, 2, 3, 4]$，把两条路都走完。

第一步：把旋转因子写成具体的数。 $n = 4$ 时 W4=e−2πi/4=cos⁡(−π/2)+isin⁡(−π/2)=−iW_4 = e^{-2\pi i/4} = \cos(-\pi/2) + i\sin(-\pi/2) = -i。它的幂只有四个值，循环出现：

$k$0123456…
W4kW_4^k$1$$-i$$-1$$i$$1$$-i$$-1$每 4 个一循环

路线 A：直接算 DFT。 按定义 Xk=∑j=03xjW4jkX_k = \sum_{j=0}^{3} x_j W_4^{jk}，逐个展开：

$k$展开式化简XkX_k
01⋅1+2⋅1+3⋅1+4⋅11{\cdot}1 + 2{\cdot}1 + 3{\cdot}1 + 4{\cdot}1$1+2+3+4$$10$
11⋅1+2⋅(−i)+3⋅(−1)+4⋅i1{\cdot}1 + 2{\cdot}(-i) + 3{\cdot}(-1) + 4{\cdot}i$(1-3) + (-2+4)i$$-2 + 2i$
21⋅1+2⋅(−1)+3⋅1+4⋅(−1)1{\cdot}1 + 2{\cdot}(-1) + 3{\cdot}1 + 4{\cdot}(-1)$1-2+3-4$$-2$
31⋅1+2⋅i+3⋅(−1)+4⋅(−i)1{\cdot}1 + 2{\cdot}i + 3{\cdot}(-1) + 4{\cdot}(-i)$(1-3) + (2-4)i$$-2 - 2i$

注意 $k=2$ 那行：指数 $jk$ 分别是 $0, 2, 4, 6$，而 W44=W40=1W_4^4 = W_4^0 = 1、W46=W42=−1W_4^6 = W_4^2 = -1——这个循环正是 FFT 能省下工作量的全部来源。同样的旋转因子被反复用到，直接算就是在重复做同一批乘法。

另外 X3=X1‾X_3 = \overline{X_1}（共轭）。这不是巧合：实数输入的 DFT 满足 Xn−k=Xk‾X_{n-k} = \overline{X_k}，所以实信号的频谱只有一半是独立信息。这条性质是"实数 FFT"（rfft）能省掉近一半计算和存储的依据。

路线 B：Cooley-Tukey 分治。 先按下标奇偶拆开：偶数项 [x0,x2]=[1,3][x_0, x_2] = [1, 3]，奇数项 [x1,x3]=[2,4][x_1, x_3] = [2, 4]。两个 2 点 DFT（W2=e−πi=−1W_2 = e^{-\pi i} = -1，所以 2 点 DFT 就是"和与差"）：

E=DFT2([1,3])=[1+3, 1−3]=[4, −2]E = \text{DFT}_2([1,3]) = [1+3,\ 1-3] = [4,\ -2] O=DFT2([2,4])=[2+4, 2−4]=[6, −2]O = \text{DFT}_2([2,4]) = [2+4,\ 2-4] = [6,\ -2]

然后用蝶形合并，$k = 0, 1$：

蝶形公式代入结果
$k=0$ 上支E0+W40O0E_0 + W_4^0 O_04+1⋅64 + 1{\cdot}6X0=10X_0 = 10
$k=0$ 下支E0−W40O0E_0 - W_4^0 O_04−1⋅64 - 1{\cdot}6X2=−2X_2 = -2
$k=1$ 上支E1+W41O1E_1 + W_4^1 O_1$-2 + (-i)(-2)$X1=−2+2iX_1 = -2 + 2i
$k=1$ 下支E1−W41O1E_1 - W_4^1 O_1$-2 - (-i)(-2)$X3=−2−2iX_3 = -2 - 2i

四个值和路线 A 完全一致。

数一数各花了多少次运算：

复数乘法复数加减
直接 DFTn2=16n^2 = 16$n(n-1) = 12$
基 2 FFTn2log⁡2n=4\frac{n}{2}\log_2 n = 4nlog⁡2n=8n\log_2 n = 8

但这张表还没说出最有意思的一点：$n = 4$ 时两条路线上的旋转因子全部落在 {1,−1,i,−i}\{1, -1, i, -i\} 里，而乘这四个数只是符号翻转和实虚部交换，一次浮点乘法都不需要。也就是说，一个手写的 4 点 FFT 可以做到零次实数乘法。

真正的差距要到 $n = 8$ 才露出来。直接 DFT 用到的旋转因子是 W8jk mod 8W_8^{jk \bmod 8}，只有当 $j$ 和 $k$ 都是奇数时指数才落在 {1,3,5,7}\{1,3,5,7\} 上、需要真乘法——奇数的 $j$ 有 4 个、$k$ 有 4 个，所以 64 次乘法里有 16 次是真的。而 8 点 FFT 的 12 个蝶形里，只有 2 个的旋转因子非平凡（见下一节）。真实数乘法上的差距是 8 倍，比 $16 : 4$ 的名义差距更大。

"小尺寸 FFT 里绝大多数乘法都是假的"这件事，正是后面 FFTW 的 codelet 能远超通用循环的根本原因：通用循环必须老实地执行 t = W[k] * b，而针对固定尺寸展开的直线代码可以在编译期就把所有乘 1、乘 ±i\pm i 的地方删掉。

位反转置换：为什么 FFT 的输入要被打乱

原地实现的 FFT（不额外开数组）有一个几乎所有教程都提一句、却很少说清的步骤：先把输入按位反转（bit reversal）重排。

原因很直观：分治每一层都按"下标奇偶"拆分，也就是按二进制最低位分组；递归 log⁡2n\log_2 n 层，等于依次按第 0 位、第 1 位、第 2 位……分组。递归到底时，元素落在哪个位置，取决于它下标的二进制反过来读是多少。

$n = 8$（3 位）的完整索引表：

原下标二进制反转新下标
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117

所以 8 点 FFT 的输入顺序是 [x0,x4,x2,x6,x1,x5,x3,x7][x_0, x_4, x_2, x_6, x_1, x_5, x_3, x_7]，之后三级蝶形就可以完全就地、按固定步长（1、2、4）进行，输出自然是正序。表里 0、2、5、7 是不动点（反转后等于自己），实际只需交换 $(1,4)$ 和 $(3,6)$ 两对——位反转置换里恰好有一半左右的元素不动，实现时要用 if (i < j) swap(...) 避免换两次换回去。

顺带说清 8 点 FFT 的旋转因子有哪些具体值（W8=e−iπ/4W_8 = e^{-i\pi/4}）：

$k$0123
W8kW_8^k$1$22(1−i)≈0.7071−0.7071i\tfrac{\sqrt2}{2}(1-i) \approx 0.7071 - 0.7071i$-i$−22(1+i)≈−0.7071−0.7071i-\tfrac{\sqrt2}{2}(1+i) \approx -0.7071 - 0.7071i

三级蝶形一共 82×3=12\frac{8}{2}\times 3 = 12 个，其中第一级的旋转因子全是 1，第二级是 {1,−i}\{1, -i\}，只有第三级的 W81W_8^1 与 W83W_8^3 需要真正的乘法。12 个蝶形，2 次实质复数乘法——直接算 8 点 DFT 要 64 次。

多项式乘法：FFT 最核心的应用

问题：两个 $n-1$ 次多项式 A(x)=∑i=0n−1aixiA(x) = \sum_{i=0}^{n-1} a_i x^i 和 $B(x)$ 相乘，得到 $2n-2$ 次多项式 C=A⋅BC = A \cdot B。朴素做法是逐项相乘再合并同类项，O(n2)O(n^2)。

FFT 方法：

  1. 在 $2n$ 个点（$2n$ 次单位根处）求值（用 FFT）：O(nlog⁡n)O(n \log n)
  2. 逐点相乘（点值表示下，乘法是逐点的）：$O(n)$
  3. 插值（逆 FFT，IFFT）回系数表示：O(nlog⁡n)O(n \log n)

总计 O(nlog⁡n)O(n \log n)。这不仅用于数学计算，还直接影响： - 大整数乘法：数字可以看成多项式系数，$n$ 位乘法由 O(n2)O(n^2)（Karatsuba O(n1.585)O(n^{1.585})）进一步降至 O(nlog⁡nlog⁡log⁡n)O(n \log n \log \log n)（Schönhage–Strassen 1971，自 1971 年起保持渐近最快纪录达数十年）。2019 年 Harvey 与 van der Hoeven 终于给出 O(nlog⁡n)O(n \log n) 的算法，恰好达到了 Schönhage 和 Strassen 当年猜想的理论下界形式。 - 卷积：数字信号处理的核心操作（滤波、互相关）本质是多项式乘法，FFT 加速后称为快速卷积

失败现场：浮点 FFT 算不准整数乘法

上一节说"大整数乘法可以用 FFT"，实际写起来会撞上一个很硬的墙：浮点数不够宽。

把一个大整数按 2162^{16} 进制切成 $n$ 个"位"（limb），每位的值域是 [0,216)[0, 2^{16})。两个这样的数相乘，卷积结果的某一项最大可以到 n⋅(216−1)2≈n⋅232n \cdot (2^{16}-1)^2 \approx n \cdot 2^{32}。而 IEEE 754 双精度浮点的尾数只有 53 位，能精确表示的整数上限是 2532^{53}。于是：

limb 数 $n$卷积项上界 ≈n⋅232\approx n\cdot 2^{32}与 2532^{53} 的关系
2102^{10}（约 5 千位十进制）2422^{42}安全
2202^{20}（约 500 万位十进制）2522^{52}已经贴到边上
2242^{24}2562^{56}溢出，结果直接是错的

更麻烦的是这个上界只是"能不能精确表示"，FFT 本身还会引入舍入误差：正向变换、逐点乘、逆变换三步下来，误差随规模缓慢增长。最后要把浮点结果四舍五入回整数——一旦某一项的累积误差超过 0.5，取整就取到隔壁去了，而且错误是静默的：程序不报错，只是答案不对。

解决办法是干脆不用浮点：把整个变换搬到有限域里，称为数论变换（Number-Theoretic Transform, NTT）。做法是找一个素数 $p$，使 Zp\mathbb{Z}_p 里存在 2k2^k 次单位原根——这样 $W$ 就是一个整数，所有运算都是模 $p$ 的整数加乘，精确无误差。竞赛与工程里最常用的两个素数：

$p$分解支持的最大变换长度原根
998 244 353998\,244\,353119×223+1119 \times 2^{23} + 12232^{23}3
167 772 161167\,772\,1615×225+15 \times 2^{25} + 12252^{25}3

"p=c⋅2k+1p = c \cdot 2^k + 1"这个形状不是凑出来的：Zp∗\mathbb{Z}_p^* 是 $p-1$ 阶循环群，要有 2k2^k 次单位原根就必须 2k∣p−12^k \mid p-1。

后量子密码把这件事用到了极致。NIST 在 FIPS 203 里标准化的 ML-KEM（前身是 CRYSTALS-Kyber）在环 Zq[x]/(x256+1)\mathbb{Z}_q[x]/(x^{256}+1) 上做多项式乘法，参数选的是 $q = 3329$、$n = 256$，而 3329=28⋅13+13329 = 2^8 \cdot 13 + 1。$q-1$ 里只有 28=2562^8 = 256 这么多个 2 的因子，所以 Z3329\mathbb{Z}_{3329} 有 256 次单位原根、没有 512 次的——这直接决定了 ML-KEM 只能做"不完全 NTT"：递归拆到长度 2 的多项式就必须停下，最后一层用普通乘法。参数不是随便选的，$q$ 的每一个因子都在为 NTT 服务。

该记住的是：FFT 的数学结构不依赖复数，它只需要一个"存在 $n$ 次单位原根"的环。复数域是最直观的选择，但当精确性比速度更重要时，有限域是更好的选择。

改变世界的应用

音频处理（MP3 等）：音频编码器用 FFT 分析各频率成分的能量，根据人耳的感知特性（听觉掩蔽效应）舍弃不重要的高频成分，实现 10:1 甚至 20:1 的压缩比。

JPEG 图像压缩：JPEG 用的是离散余弦变换（DCT），是 FFT 的实数版本，对每个 8×88 \times 8 像素块做变换，丢弃高频（细节）成分，保留低频（轮廓）成分。

无线通信（4G/5G OFDM）：现代移动通信使用正交频分复用（OFDM），IFFT/FFT 是调制/解调的核心——每个通话、每次上网，都在毫秒内完成成千上万次 FFT。

雷达与声呐：发射信号经目标反射后用 FFT 分析频移（多普勒效应），判断目标速度和距离。

MRI 医学成像：核磁共振扫描仪采集的原始数据天然在"k 空间"（频域），FFT 重建为空间图像是 MRI 的必要步骤。

天文学：射电望远镜数据分析（如 SETI@home 用志愿者计算机做的信号搜索）依赖 FFT 在海量数据中寻找周期信号。

现场一：FFTW 为什么要在运行时"规划"

大多数库的接口是"调用函数、拿到结果"。FFTW（Fastest Fourier Transform in the West）不是——它要求你先 fftw_plan_dft_1d(...) 造一个计划（plan），再用这个计划去做变换。这个多出来的步骤是它的核心设计。

Frigo 与 Johnson 在 2005 年《Proceedings of the IEEE》上的《FFTW3 的设计与实现》里讲清了两层机制：

codelet（小码块）：FFTW 的底层不是一个通用的蝶形循环，而是一大批针对特定尺寸（2、3、4、5、7、8、11、13、16…点）手工级优化的直线代码——没有循环、没有分支，所有旋转因子在生成时就已代入，乘 1 和乘 ±i\pm i 全部消掉。这些 codelet 不是人写的，而是由一个专门的"FFT 编译器" genfft 从抽象描述自动生成。上一节数出的"8 点 FFT 只有 2 次真乘法"就是 codelet 能榨到的极限。

planner（规划器）：一个长度 $n$ 的 DFT 有指数多种分解方式——$n = 1024$ 可以拆成 32×3232 \times 32、4×2564 \times 256、8×8×168 \times 8 \times 16……哪种最快取决于这台机器的缓存大小、SIMD 宽度、寄存器数量，无法在写库的时候预知。FFTW 的做法是把可选的求解器列成清单，对给定问题逐个问"你能给出什么计划"，然后按标志位决定怎么选：FFTW_ESTIMATE 用启发式代价模型猜一个，FFTW_MEASURE 则真的把候选方案跑一遍计时，选实测最快的。测出来的结论可以存成"wisdom"文件复用，避免每次启动都重测一遍。

这是一种在算法库里少见的姿态：承认"最优实现"不是一个可以静态写下来的东西，而是一个需要在目标机器上搜索的答案。同样的思路后来出现在 ATLAS（线性代数）、深度学习编译器的算子自动调优里。

现场二：为什么 JPEG 用 DCT 而不是 FFT

JPEG 对每个 8×88\times 8 像素块做的是离散余弦变换（DCT-II），不是 DFT。这不是"实数版本的 FFT"这么一句能说完的，两个理由都很实在：

  1. DFT 的隐含假设是信号周期延拓——把 8 个像素首尾相接绕成一圈。可 x0x_0 和 x7x_7 通常并不相等，接口处就出现一个人为的跳变；跳变在频域里意味着能量被摊到全部高频分量上。DCT 的隐含延拓是镜像对称（先把 8 个点反射成 16 个点再周期化），接口处天然连续，没有假跳变。结果是同样的图像块，DCT 的能量集中在更少的低频系数上——这正是压缩需要的性质。
  2. 实数输入给出实数输出。DFT 的输出是复数，虽然实信号的频谱有共轭对称、只需存一半，但流程里免不了复数运算与拆包；DCT 全程实数，硬件和定点实现都简单得多。

FFT 并没有被排除在外——DCT 本身通常就是用一个长度 $N/2$ 的复数 FFT 加上若干次旋转实现的。所以准确的说法是：JPEG 选的是更适合"块内能量集中"的基，而 FFT 是把这个基算快的手段。变换选哪个由信号性质决定，算法选哪个由计算量决定，两件事不要混。

现场三：一个 OFDM 符号只有 66.7 微秒

FFT 在通信里不是"用一下"，而是硬实时地、永不停歇地跑着。以 LTE 为例，参数是标准里写死的：

参数值来源
子载波间隔15 kHz3GPP 固定值
OFDM 符号长度（不含循环前缀）1/15 kHz=66.7 μs1/15\,\text{kHz} = 66.7\ \mu s子载波间隔的倒数
20 MHz 带宽的采样率30.72 MHz=2048×15 kHz= 2048 \times 15\ \text{kHz}
FFT 点数2048采样率 ÷ 子载波间隔
每毫秒符号数14（常规循环前缀，每 0.5 ms 时隙 7 个）3GPP 帧结构

把这些数字连起来：发射端每秒要做约 14 000 次 2048 点 IFFT，接收端同样做 14 000 次 2048 点 FFT，每个天线流各一份，4×44\times4 MIMO 就是四倍。而且这不是"平均每秒一万四千次"就够——每一次都必须在下一个符号到来之前完成，是硬期限。

5G NR 把这件事推得更紧：它支持可变子载波间隔 15×2μ15 \times 2^\mu kHz，最大 FFT 点数 4096。μ=3\mu = 3（120 kHz 子载波，用于毫米波）时符号长度缩到 66.7/8=8.33 μs66.7 / 8 = 8.33\ \mu s——几千点的 FFT 必须在个位数微秒内做完。这就是为什么 FFT 从来不是"调个库"，而是要落到专用 DSP、FPGA 流水线或基带芯片的硬件蝶形单元上。上文提到"规则的蝶形结构使 FFT 易于硬件实现"，这里是它的价码：算法结构规则，才能把它焊进硅片。

历史悬案：高斯早知道了？

Cooley 和 Tukey 的论文发表后，数学史家发现：Carl Friedrich Gauss 在 1805 年的未发表手稿中就描述了实质相同的算法（用于天文计算中的插值）——比 Cooley-Tukey 早 160 年。

这并不是孤立案例。许多算法的"发明者"其实是"重新发现者"——知识在历史中多次独立涌现，最终在合适的工程需求下被正式发表和推广。

跨域连接

  • 分治算法：它与归并排序的分治骨架相同，差别在合并步：归并靠比较，这里靠一条代数恒等式，使两个子问题的答案可以直接复用。这给出分治能否奏效的通用标准——不是问题能不能对半劈，而是子解能否被廉价拼起来。没有单位根的循环性质，同样的拆分只会退回平方复杂度。
  • 傅里叶分析：离散变换继承了连续理论的全部结构，包括帕塞瓦尔等式给出的时频能量守恒。最要紧的继承是卷积定理：时域卷积等于频域逐点相乘，于是滤波、互相关与多项式乘法被同一次变换加速。算得快的从来不是变换本身，而是被它变简单的那个乘法。
  • X 射线晶体学：衍射花样与电子密度互为变换对，解结构本质上就是做一次反变换。但探测器只记录强度，也就是振幅的平方，相位丢失——这就是相位问题。振幅对而相位错，重建出来的会是另一个分子；相位携带的结构信息远多于振幅，这是同一个数学结构在实验里最贵的一课。
  • 声学语音学：语谱图就是逐帧的短时变换，共振峰是频域上的峰。这里横着一条硬约束：窗口越短，时间分辨率越高而频率分辨率越低，两者的乘积有下限。所以宽带语谱图看得清爆破的瞬间却看不清基频，窄带反之。"两者都要"在数学上不可满足，只能换分析目标。
  • CT 与 MRI：磁共振采到的原始数据本来就在频域，重建就是做反变换，扫描时长因而直接由需要填满多少频域采样点决定。由此推出并行成像的原理：欠采样会造成折叠伪影，用多个线圈的空间灵敏度差异补足缺失信息即可解开，而加速倍数的上限由线圈数决定，不是由重建算法决定。

参考文献

  • Cooley, J.W. & Tukey, J.W. "An Algorithm for the Machine Calculation of Complex Fourier Series." Mathematics of Computation 19(90), 1965.
  • Schönhage, A. & Strassen, V. "Schnelle Multiplikation grosser Zahlen." Computing 7, 1971.
  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第30章 Polynomials and the FFT）
  • Frigo, M. & Johnson, S. G. "The Design and Implementation of FFTW3." Proceedings of the IEEE 93(2), 216–231, 2005.（codelet、genfft 与 planner 的设计）
  • NIST. FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. 2024.（ML-KEM 的 $q = 3329$、$n = 256$ 与不完全 NTT）
  • 3GPP TS 36.211, Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation.（LTE 15 kHz 子载波、66.7 μs 符号与帧结构）
  • Harvey, D. & van der Hoeven, J. "Integer multiplication in time O(nlog⁡n)O(n\log n)." Annals of Mathematics 193(2), 563–617, 2021. DOI: 10.4007/annals.2021.193.2.4

延伸阅读

  • Smith, J.O. Mathematics of the Discrete Fourier Transform (DFT). W3K Publishing, 2007. （免费在线版）
  • FFTW 官方文档 — https://www.fftw.org/fftw3doc/ （`FFTWMEASURE / FFTW_ESTIMATE` 与 wisdom 机制的用法）
  • Oppenheim, A. V. & Schafer, R. W. Discrete-Time Signal Processing. 3rd ed. Pearson, 2010.（DFT/DCT 的关系与快速卷积）
  • Wallace, G. K. "The JPEG Still Picture Compression Standard." Communications of the ACM 34(4), 30–44, 1991.

正文中引用本条 · 13 · 其中 11 条来自其他领域

数学表示论环解析数论的新进展欧拉恒等式
宇宙学双星系统引力波天文学宇宙大尺度结构
化学多萝西·霍奇金NMR：从核自旋到分子结构推断
语言学声学语音学与语音测量
宇宙物理全息术