傅里叶变换:每个信号都是正弦波之和

傅里叶变换:每个信号都是正弦波之和

本节摘要:每个信号都是正弦波之和,傅里叶变换告诉你是由哪些组成的。音频是压力随时间的测量,股价是逐日数值,图像是空间像素强度——这些都是时域(或空域)数据,许多模式在时域里隐形(这音频是纯音还是和弦?股价有周周期吗?图像有重复纹理吗?)。傅里叶变换把数据从时域转到频域,把信号分解成不同频率的正弦波,每个有幅度(多强)与相位(从哪开始)。本节从 DFT 定义 X[k] = Σ x[n]·e^(-2πi·kn/N) 讲起,揭示每个系数的含义(X[0] 是 DC 分量、X[N/2] 是 Nyquist、实信号的负频率是正频率的镜像);给逆 DFT(符号翻转 + 除 N,完美重建无信息丢失,本质是换基);推导 Cooley-Tukey FFT 把 O(N²) 降到 O(N log N)(分治:偶奇拆分 + 蝶形组合 + 旋转因子),N=100 万时从 10¹² 降到约 2000 万次运算;讲清卷积定理(时域卷积 = 频域逐点乘,这是 CNN 大核加速与 FNet 用 FFT 替代注意力的根源);覆盖加窗(Hann/Hamming/Blackman 降谱泄漏)、Parseval 定理(能量守恒)、混叠(Nyquist 之上频率伪装为低频)、零填充不增分辨率;最后连上 Transformer 正弦位置编码、CNN 卷积与音频模型的频谱图(STFT)。

对应原课程:Phase 01 · Lesson 20 · fourier-transform(原英文 phases/01-math-foundations/20-fourier-transform/docs/en.md)。前置:第 1~4、19 节(复数)。

学习目标

阅读完本节,你应当能够:

1. 从零实现 DFT,并对照 O(N log N) 的 Cooley-Tukey FFT 验证。
2. 解读频率系数:从信号提取幅度、相位、功率谱。
3. 应用卷积定理用 FFT 乘法做卷积。
4. 把傅里叶频率分解连上 Transformer 位置编码与 CNN 卷积层。

一、问题与直觉

音频录音是压力随时间的测量序列,股价是逐日数值,图像是空间像素强度网格——这些都是时域(或空域)数据,你看到值随某下标变化。但许多模式在时域里隐形:这音频是纯音还是和弦?这股价有周周期吗?这图像有重复纹理吗?这些是关于频率内容的问题,时域把它藏起来。傅里叶变换把数据从时域转到频域,它取一个信号把它分解成不同频率的正弦波——每个有幅度(多强)与相位(从哪开始)。这对 ML 要紧,因为频域思维无处不在:CNN 做卷积(在频域是乘法);Transformer 位置编码用频率分解表示位置;音频模型(语音识别、音乐生成)操作频谱图(声音的频率表示);时间序列模型找周期模式。

1.1 DFT 定义

给定 N 个样本 x[0], x[1], ..., x[N-1],DFT 产生 N 个频率系数 X[0], X[1], ..., X[N-1]:X[k] = Σ_{n=0}^{N-1} x[n]·e^(-2πi·k·n/N),k=0,...,N-1。每个 X[k] 是复数:模 |X[k]| 告诉你频率 k 的幅度,相位 angle(X[k]) 告诉你该频率的相位偏移。

关键洞见:e^(-2πi·k·n/N) 是频率 k 的旋转相量。DFT 算信号与 N 个等距频率各自的相关——若信号在频率 k 有能量,相关大;否则近零。

1.2 每个系数的含义

• X[0]:DC 分量。所有样本之和(正比于均值),代表信号的常量(零频)偏移:X[0] = Σx[n]·e⁰ = 全部样本之和。
• X[k](1 ≤ k ≤ N/2):正频率。X[k] 代表每 N 样本 k 周期的频率,k 越大频率越高(振荡越快)。
• X[N/2]:Nyquist 频率。N 个样本能表示的最高频率,超过即混叠(高频伪装成低频)。
• X[k](N/2 < k < N):负频率。对实信号 X[N-k] = conj(X[k]),负频率是正频率的镜像——这就是有用信息在前 N/2+1 个系数里的原因。

1.3 逆 DFT

逆 DFT 从频率系数重建原信号:x[n] = (1/N)·Σ_{k=0}^{N-1} X[k]·e^(2πi·k·n/N),n=0,...,N-1。与正向 DFT 的唯一差别:指数符号为正、有 1/N 归一化因子。逆 DFT 是完美重建,无信息丢失——DFT 是换基,把同样的信息用不同坐标系重新表达。

1.4 FFT:让它快

按定义 DFT 是 O(N²):N 个输出系数各对 N 个输入求和,N=100 万时是 10¹² 次运算。快速傅里叶变换(FFT) 在 O(N log N) 算出同样结果,N=100 万时约 2000 万次而非万亿——这就是让频率分析可行的东西。

Cooley-Tukey 算法(最常用 FFT)用分治:① 把信号拆成偶下标与奇下标样本;② 递归算各自的 DFT;③ 用「旋转因子」e^(-2πi·k/N) 组合两个半尺寸 DFT:

X[k]       = E[k] + e^(-2πi·k/N)·O[k]       k=0,...,N/2-1
X[k+N/2]   = E[k] - e^(-2πi·k/N)·O[k]       k=0,...,N/2-1
其中 E = 偶下标样本的 DFT,O = 奇下标样本的 DFT
​

对称性使每层递归 O(N) 工作量,共 log₂(N) 层,总计 O(N log N)。

FFT 要求信号长度是 2 的幂,实战中信号零填充到下一个 2 的幂。

1.5 谱分析

功率谱是 |X[k]|²(每个频率系数模的平方),显示每个频率有多少能量。相位谱是 angle(X[k]),多数分析任务只关心功率谱而忽略相位:P[k] = |X[k]|² = X[k].real² + X[k].imag²。

1.6 频率分辨率

DFT 的频率分辨率取决于样本数 N 与采样率 fs:频率 f_k = k·fs/N;分辨率 Δf = fs/N;最高频率 f_max = fs/2(Nyquist)。要分辨两个相近的频率需更多样本;要捕获高频需更高采样率。

1.7 卷积定理

这是信号处理最重要、且与 CNN 直接相关的结果之一:时域卷积等于频域逐点乘。

x * h = IFFT(FFT(x) · FFT(h))     ← * 是卷积,· 是逐点乘
​

为何要紧:① 长 N 与 M 的两信号直接卷积需 O(N·M);② 基于 FFT 的卷积需 O(N log N):变换两者、相乘、变回;③ 大核时 FFT 卷积极快;④ 这正是大感受野卷积层里发生的事。注意:DFT 算的是循环卷积(信号环绕);要线性卷积(不环绕),先把两信号零填充到 N+M-1 再算。

1.8 加窗

DFT 假定信号周期性——把 N 个样本当作无限重复信号的一个周期。若信号起止值不同,边界产生不连续,表现为虚假高频内容,这叫谱泄漏。加窗通过在算 DFT 前把信号两端渐变到零来减少泄漏。常见窗:矩形(无窗,主瓣最窄、旁瓣最高 -13dB);Hann(升余弦,通用谱分析,旁瓣 -31dB);Hamming(改良余弦,音频/语音,旁瓣 -42dB);Blackman(三余弦,旁瓣抑制关键时,旁瓣 -58dB)。加窗方式:窗与信号逐元素相乘再做 DFT。

1.9 DFT 性质

Parseval 定理说两域总能量相同——变换保能量。

1.10 与位置编码的联系

原始 Transformer 用正弦位置编码:PE(pos, 2i) = sin(pos/10000^(2i/d_model)),PE(pos, 2i+1) = cos(pos/10000^(2i/d_model))。每对维度 (2i, 2i+1) 以不同频率振荡,频率从高(维度 0,1)到低(末维度)几何分布。这给每个位置在所有频带上的唯一模式——类似傅里叶系数唯一标识信号。它提供的关键性质:唯一性(无两位置编码相同)、有界值(sin/cos 恒在 [-1,1])、相对位置(位置 p+k 的编码可表为位置 p 编码的线性函数,模型能学会注意相对位置)。

1.11 与 CNN 的联系

卷积层通过在信号或图像上滑动学到的滤波器(核)做卷积,数学上就是卷积运算。按卷积定理,这等价于:① FFT 输入;② FFT 核;③ 频域相乘;④ IFFT 结果。标准 CNN 实现用直接卷积(小 3×3 核更快),但大核或全局卷积时基于 FFT 显著更快。某些架构(如 FNet)完全用 FFT 替代注意力,以 O(N log N) 复杂度达到有竞争力的准确率。

1.12 频谱图与短时傅里叶变换(STFT)

单个 FFT 给整个信号的频率内容,却不说这些频率何时出现。一个 chirp(频率随时间增的信号)与一个和弦(所有频率同时存在)可能有相同幅度谱。短时傅里叶变换(STFT) 通过在信号重叠窗口上算 FFT 解决:结果是频谱图——一个 2D 表示,一轴时间、一轴频率,每点强度显示该时该频的能量。频谱图是音频 ML 模型的标准输入表示:语音识别模型(Whisper、DeepSpeech)操作 mel 频谱图(频率映到 mel 尺度,更贴合人耳音高感知)。

1.13 混叠

若信号含高于 fs/2(Nyquist 频率)的频率,以 fs 采样会产生混叠副本。90 Hz 信号以 100 Hz 采样看起来与 10 Hz 信号完全相同——仅从样本无法区分。这就是模数转换器在采样前加抗混叠滤波器(去除 Nyquist 之上频率)的原因。ML 里,下采样特征图而不加适当低通滤波时出现混叠——某些架构用抗混叠池化层应对。

1.14 零填充不增分辨率

常见误解:FFT 前零填充提升频率分辨率。并非如此——零填充在已有频率格点间插值,给你看起来更平滑的谱,但无法揭示原样本里没有的频率细节。真频率分辨率只取决于观测时间 T = N/fs——要分辨相隔 Δf 的两频率需至少 T = 1/Δf 秒数据,零填充改变不了这一根本限制。

二、从零实现

完整源码见 phases/01-math-foundations/20-fourier-transform/code/fourier.py(复用第 19 节的 Complex 类)。

2.1 DFT

def dft(x):
    N = len(x); result = []
    for k in range(N):
        total = Complex(0, 0)
        for n in range(N):
            angle = -2 * math.pi * k * n / N
            total = total + Complex(x[n], 0) * Complex(math.cos(angle), math.sin(angle))
        result.append(total)
    return result
​

2.2 逆 DFT

同结构,正指数,除 N。

2.3 FFT(Cooley-Tukey)

def fft(x):
    N = len(x)
    if N <= 1: return [Complex(x[0]) if not isinstance(x[0], Complex) else x[0]]
    if N % 2 != 0: return dft(x)                      # 非二的幂则回退
    even = fft([x[i] for i in range(0, N, 2)])
    odd  = fft([x[i] for i in range(1, N, 2)])
    result = [Complex(0)] * N
    for k in range(N // 2):
        angle = -2 * math.pi * k / N
        twiddle = Complex(math.cos(angle), math.sin(angle))   # 旋转因子
        t = twiddle * odd[k]
        result[k]        = even[k] + t
        result[k + N//2] = even[k] - t
    return result
​

2.4 谱分析与 FFT 卷积

def power_spectrum(X):
    return [xk.real**2 + xk.imag**2 for xk in X]

def convolve_fft(x, h):
    N = len(x) + len(h) - 1
    padded_N = 1
    while padded_N < N: padded_N *= 2                  # 零填充到二的幂
    X = fft(x + [0.0]*(padded_N - len(x)))
    H = fft(h + [0.0]*(padded_N - len(h)))
    Y = [xk*hk for xk, hk in zip(X, H)]                # 频域逐点乘
    return [y.real for y in idft(Y)][:N]               # IFFT 取实部 = 线性卷积
​

三、框架对比

真实工作用 numpy 的 FFT(背后是高度优化的 C 库):

signal = np.sin(2 * np.pi * 5 * np.arange(256) / 256)
spectrum = np.fft.fft(signal)
freqs = np.fft.fftfreq(256, d=1/256)
power = np.abs(spectrum) ** 2
positive_power = power[:len(power)//2]                 # 实信号只需前半

from scipy.signal import windows, stft, fftconvolve
windowed = signal * windows.hann(256)                  # 加窗
result = fftconvolve(signal, kernel, mode='full')      # FFT 卷积
frequencies, times, Zxx = stft(signal, fs=sample_rate, nperseg=256)
spectrogram = np.abs(Zxx) ** 2                         # 频谱图矩阵 (n_freq, n_time)
​

频谱图矩阵的形状是 (n_frequencies, n_time_frames),每列是一个时间窗的功率谱——这正是音频 ML 模型作为输入消费的东西。

四、可复用产物

运行 code/fourier.py 生成 outputs/prompt-spectral-analyzer.md——一份谱分析提示,帮你对给定信号选择窗、读功率谱、识别频率成分。源码见 phases/01-math-foundations/20-fourier-transform/code/。

五、练习

1. (Easy) 纯音识别:造一个未知频率(1~50 Hz)单正弦波、128 Hz 采样 1 秒的信号,用你的 DFT 识别频率并验证;再加标准差 0.5 的高斯噪声重做,观察噪声如何影响谱。
2. (Medium) FFT vs DFT 验证:生成长 64 的随机信号,同时算 DFT 与 FFT,验证所有系数在 1e-10 内一致;在长 256、512、1024、2048 信号上计时两者,画 DFT/FFT 时间比。
3. (Medium) 卷积定理示例验证:信号 x=[1,2,3,4,0,0,0,0]、滤波 h=[1,1,1,0,0,0,0,0],直接算循环卷积(嵌套循环),再用 FFT(变换、乘、逆变换)算,验证一致;再做线性卷积(适当零填充)。
4. (Hard) 加窗效应:造 10 Hz 与 12 Hz(很近)两正弦之和、128 Hz 采样 1 秒,分别用无窗、Hann、Hamming 算功率谱,哪个窗最易区分两峰、为什么?
5. (Hard) 位置编码分析:生成 d_model=128、max_pos=512 的正弦位置编码,对每对位置 (p1,p2) 算其编码点积,证明点积只依赖 |p1−p2| 而非绝对位置;随距离增大点积如何变化?

本节要点回顾

1. 傅里叶变换把时域信号分解成不同频率的正弦波,每个有幅度与相位——时域藏的周期模式在频域显形。
2. DFT X[k] = Σx[n]·e^(-2πi·kn/N) 算信号与 N 个等距复正弦(旋转相量)的相关;X[0] 是 DC(均值)、X[N/2] 是 Nyquist、实信号负频是正频镜像。
3. 逆 DFT 翻符号 + 除 N 给完美重建,DFT 是换基,无信息丢失,两域能量守恒(Parseval)。
4. Cooley-Tukey FFT 用分治把 O(N²) 降到 O(N log N):偶奇拆分 + 旋转因子蝶形组合,N=100 万时从 10¹² 降到约 2000 万次。
5. 功率谱 |X[k]|² 显示能量分布;频率分辨率 Δf = fs/N 只取决于观测时间。
6. 卷积定理:时域卷积 = 频域逐点乘,大核卷积可用 FFT 加速,这是 FNet 用 FFT 替代注意力的根源。
7. 谱泄漏 来自把非周期信号当周期,DFT 前加窗(Hann/Hamming/Blackman)降低。
8. STFT/频谱图 在重叠窗口上算 FFT,给时间-频率 2D 表示,是音频 ML 模型的标准输入(mel 频谱图)。
9. 混叠:高于 Nyquist(fs/2)的频率伪装为低频,采样前要抗混叠滤波。
10. 零填充不增分辨率,只插值平滑;Transformer 正弦位置编码的 sin/cos 对是几何分布频率的复指数实虚部。

下一节,我们看连接的数据结构——面向机器学习的图论:邻接矩阵、BFS/DFS、图拉普拉斯(谱聚类)、消息传递(GNN 的核心运算)。