小镇上有家“频谱餐厅”，主厨阿傅能把任何一首歌拆成一盘盘“频率小菜”——低音是醇厚的底味，高音是跳跃的香气。他的绝活叫傅里叶变换，但这门绝活有个硬伤：每出一道菜，他都要把整首歌从头到尾重新“听”一遍。一首歌有 1000 个时间采样点，要出 1000 道频率小菜，就得听 100 万遍；歌还没听完，客人已经走光了。直到帮厨小哥 Cooley 想出一个“分桌合菜”的妙招：把时间点按奇偶分成两桌，每桌先各自处理，再逐层合并。这么一改，跑腿次数从“百万级”掉到“万级”，阿傅的餐厅从此改名“FFT 快餐店”，实时出菜不再是梦。 这个故事讲的就是快速傅里叶变换（FFT），更准确的名字叫 Cooley-Tukey 算法。它不是一种新变换，而是让傅里叶变换“快起来”的省力算法。接下来的旅程，我们一起拆解它怎么分、怎么合，以及为什么它能成为现代频谱分析的心脏。

岗位关联

对 AI 从业者：FFT 是语音识别、音频增强、振动监测等一切频谱类任务的地基。看懂 Cooley-Tukey 的分治与蝶形，你才能在真实数据上设计出“毫秒级响应”的信号处理管线。

目录
  1. 可视化演示
  2. DFT计算瓶颈：老厨师的笨功夫
  3. Cooley-Tukey分治：分桌合菜的妙招
  4. 蝶形运算：两口锅互相借味
  5. 基2与基4：两桌合并还是四桌合并
  6. 频率分辨率：菜谱上的口味刻度
  7. 频谱分析应用：FFT 快餐店开业
  8. 性能对比：从蜗牛到猎豹的数字
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

分步展示FFT核心原理：DFT到FFT复杂度优化(O(n²)→O(nlogn))、Cooley-Tukey蝶形运算数据流、时域到频域频谱变换，交互切换理解算法本质。

本节配有交互动效（进入视口后自动加载，约 3KB）。

DFT到FFT复杂度优化 DFT直接计算O(n²)，FFT利用分治降到O(nlogn) X[k]=Σx[n]·W_N^(nk), W_N=e^(-2πi/N) N=1024时加速比约93倍。

DFT计算瓶颈：老厨师的笨功夫

阿傅的笨办法其实不难理解：他想知道“这段音乐里有没有钢琴的高音 C”，就把整段音乐从头到尾再听一遍，心里打个勾；下一个问题“有没有小提琴的高音 E”，又把整段音乐再听一遍。问题有 N 个，音乐也有 N 个采样点，于是每天要做 N×N 遍“听力训练”，耳朵都快起茧了。

在数字信号处理里，这段“音乐”就是 N 个采样点，那 N 个问题就是要算 N 个频点。离散傅里叶变换（DFT）就是回答这些问题的标准公式，它把 N 个时间采样点完整地换算成 N 个频率成分：

每个 X[k] 都要把 N 个采样点逐个乘上旋转因子再累加，N 个频点一共就要 N² 次复数乘法。N=1000 时是 100 万次，N=100 万时是 10¹² 次，普通电脑算到手抖。DFT 的正确率没话说，但速度让人绝望——这正是阿傅每天下班耳朵嗡嗡响的原因。

X[k]=∑n=0N−1x[n] e−i2πkn/NX[k] = \displaystyle\sum_{n=0}^{N-1} x[n] \, e^{-i 2\pi k n / N}
  1. X[k] 的含义这是第 k 个频率成分的复数结果，同时包含幅度和相位信息。
    X[k]\displaystyle X[k]
  2. x[n] 的输入这是第 n 个时间采样点的信号值，是整个公式的输入。
    x[n]\displaystyle x[n]
  3. 旋转因子的相位e 的指数部分表示频率 k 的“节拍器”在第 n 个采样点转到的角度。
    e−i2πkn/N\displaystyle e^{-i 2\pi k n / N}
  4. 求和的累加把所有采样点上的“信号值 × 相位角度”逐项累加起来。
    ∑n=0N−1\displaystyle \sum_{n=0}^{N-1}
  5. N 的总点数N 既是采样点总数，也是输出频点的个数，输出与输入数量相同。
    N\displaystyle N

Cooley-Tukey分治：分桌合菜的妙招

Cooley 小哥观察到一个规律：厨房里最累的不是做菜，而是“返工”。偶数号食材和奇数号食材明明可以分开准备，为什么每道菜都要全部重新过一遍？他提出：把食材按奇偶分成两堆，分别做成两锅半成品，再合到一起调味。

数学上，把采样点按下标奇偶拆开：偶数点 n=2m，奇数点 n=2m+1。代入 DFT 公式整理后，一个 N 点 DFT 变成两个 N/2 点 DFT 再加一个合并步骤：

拆一次，计算量从 N² 变成约 N²/2——已经省了一半。更妙的是，两个 N/2 点 DFT 可以继续按奇偶拆成四个 N/4 点 DFT，一路拆到底，每拆一层省一半，拆 log₂N 层后总计算量变成 Nlog₂N。这正是分治的威力：大问题分解成小问题，小问题递归求解，再合并答案。Cooley 小哥对阿傅说：您不是厨艺不行，是流程太原始。

X[k]=E[k]+WNk O[k]X[k] = E[k] + W_N^k \, O[k]
  1. E[k] 的来源偶数位置采样点组成的新序列，做一次 N/2 点 DFT 得到的结果。
    E[k]=∑m=0N/2−1x[2m] e−i2πkm/(N/2)\displaystyle E[k] = \sum_{m=0}^{N/2-1} x[2m] \, e^{-i 2\pi k m / (N/2)}
  2. O[k] 的来源奇数位置采样点组成的新序列，同样做一次 N/2 点 DFT。
    O[k]=∑m=0N/2−1x[2m+1] e−i2πkm/(N/2)\displaystyle O[k] = \sum_{m=0}^{N/2-1} x[2m+1] \, e^{-i 2\pi k m / (N/2)}
  3. 旋转因子 W负责给奇数子序列的结果调整相位，再与偶数结果对齐合并。
    WNk=e−i2πk/N\displaystyle W_N^k = e^{-i 2\pi k / N}
  4. 加法合并把偶数结果和经过旋转因子调整后的奇数结果相加，得到第 k 个频点。
    X[k]=E[k]+WNkO[k]\displaystyle X[k] = E[k] + W_N^k O[k]

蝶形运算：两口锅互相借味

合并这一步长得像蝴蝶：两口锅各舀一勺汤，互相交换一半，再各自出锅。这个“换味”的动作在 FFT 里有个专门名字——蝶形运算。设 A 是偶数子序列算出的中间结果 E[k]，B 是奇数子序列的中间结果 O[k]。利用旋转因子的周期性质，第 k 个和第 k+N/2 个频点可以一次算出来，它们共用同一个旋转因子 W，只是一个做加法、一个做减法：

一次蝶形运算只包含 1 次复数乘法和 2 次复数加法。8 点 FFT 每层有 4 个蝶形，3 层共 12 个；而直接 DFT 需要 64 次乘法。整个 FFT 网络画出来就像一张蝴蝶翅膀叠成的网，所以叫“蝶形信号流图”——一次操作服务两个客人，这就是合菜的精髓。

X[k]=A+W⋅B,X[k+N/2]=A−W⋅BX[k] = A + W \cdot B, \qquad X[k + N/2] = A - W \cdot B
  1. A 的中间结果A 是偶数子序列算出的中间值 E[k]，作为蝶形的一个输入。
    A=E[k]\displaystyle A = E[k]
  2. B 的中间结果B 是奇数子序列的中间值 O[k]，作为蝶形的另一个输入。
    B=O[k]\displaystyle B = O[k]
  3. 旋转因子 W为 B 调整相位，W 同时被加法和减法两条支路共用。
    W=WNk\displaystyle W = W_N^k
  4. 加法支路输出A 加上 W·B，得到第 k 个频点 X[k]。
    X[k]=A+WB\displaystyle X[k] = A + W B
  5. 减法支路输出A 减去 W·B，得到第 k+N/2 个频点，一次蝶形出两个结果。
    X[k+N/2]=A−WB\displaystyle X[k + N/2] = A - W B

基2与基4：两桌合并还是四桌合并

两只手能同时炒两口锅，四只手是不是更快？基 2 是每层两两合并，基 4 是每层四四合并，相当于把跑腿的次数再砍一半。Cooley-Tukey 的分治思想并不限定“每次拆 2 份”，把 N 点序列按下标模 4 分成 4 组，每组 N/4 点，先算 4 个 N/4 点 DFT，再合并：

基 4 的层数变成 log₄N，也就是 log₂N 的一半。比如 1024 点，基 2 要 10 层，基 4 只要 5 层。每层合并稍微复杂，但总乘法数比基 2 少约 25%；不过加法略多，程序也更绕。工程上还有基 8、混合基、Split-Radix 等，本质都是“更聪明的分堆方式”——四桌同时上菜虽复杂，但上下楼次数少了一半。

X[k]=E0[k]+W E1[k]+W2 E2[k]+W3 E3[k]X[k] = E_0[k] + W \, E_1[k] + W^2 \, E_2[k] + W^3 \, E_3[k]
  1. 四个子序列E0 到 E3 是按 n 模 4 分成的四组子序列各自做 N/4 点 DFT 的结果。
    Er[k]=∑m=0N/4−1x[4m+r] e−i2πkm/(N/4)\displaystyle E_r[k] = \sum_{m=0}^{N/4-1} x[4m+r] \, e^{-i 2\pi k m / (N/4)}
  2. W 的幂次四个入口分别乘旋转因子的 0、1、2、3 次方，对应各自的相位偏移。
    Wr=e−i2πr/N,r=0,1,2,3\displaystyle W^r = e^{-i 2\pi r / N}, \quad r = 0,1,2,3
  3. 加权组合四路结果加权相加，一个基 4 蝶形一次给出四个频点。
    X[k]=∑r=03WrEr[k]\displaystyle X[k] = \sum_{r=0}^{3} W^r E_r[k]

频率分辨率：菜谱上的口味刻度

菜谱上写“微辣、中辣、特辣”，口味刻度越细，越能精准调出客人想要的辣度。频率分辨率就是频谱上的“辣度刻度”。FFT 输出的 N 个频点均匀分布在 0 到采样率之间，相邻两个频点的间隔就是频率分辨率：

要提高分辨率，要么增大 N（采集更长时间），要么降低 fs（在满足奈奎斯特的前提下）。但注意：如果 N 增大只是因为“补零”，真实信息没有增加，分辨率不会变好。另外，实际数据有限长，直接截断等于乘了一个矩形窗，会产生频谱泄漏——旁瓣把能量“漏”到邻近频点。加汉宁窗等窗函数能缓解泄漏，但窗函数不能提高分辨率，只是让谱线更干净。阿傅想尝出更细的味道，得把菜多炖一会儿，而不是把同一口汤反复舀起来倒回去。

Δf=fsN\Delta f = \dfrac{f_s}{N}
  1. Δf 的定义频率分辨率，表示频谱上能区分的最小频率差，单位是 Hz。
    Δf\displaystyle \Delta f
  2. fs 的采样率每秒采集多少个点，它决定了分析的最高频率上限 fs/2。
    fs\displaystyle f_s
  3. N 的点数参与 FFT 的采样点数量，也就是把总带宽等分成多少份。
    N\displaystyle N
  4. 除法关系总带宽 fs 被 N 等分，N 越大每个格子越细，分辨率越高。
    Δf=fsN\displaystyle \Delta f = \frac{f_s}{N}

频谱分析应用：FFT 快餐店开业

有了 FFT，阿傅的餐厅终于能“现场出菜”：客人点歌，几毫秒后频谱小菜就端上桌。实时频谱分析的流水线是：采集一段信号 → 加窗 → FFT → 取幅值。幅值谱告诉我们每个频率成分有多强：

1024 点 FFT 只需要约 1 万次复数乘法，在现代 CPU 上是微秒到毫秒级别，足以支撑每秒 30-60 帧的频谱刷新。这正是音乐播放器的频谱柱、降噪耳机的频段分析、工厂振动监测的“实时频谱图”能转起来的原因。对 AI 系统来说，FFT 也常常是特征提取环节的起点——把原始波形变成频域特征，再喂给神经网络。

∣X[k]∣=Re(X[k])2+Im(X[k])2|X[k]| = \sqrt{\mathrm{Re}(X[k])^2 + \mathrm{Im}(X[k])^2}
  1. 实部与虚部X[k] 是复数，Re 是它的实部，Im 是它的虚部。
    Re(X[k]),Im(X[k])\displaystyle \mathrm{Re}(X[k]), \quad \mathrm{Im}(X[k])
  2. 平方求和实部和虚部分别平方后相加，把复数变成正的强度量。
    Re(X[k])2+Im(X[k])2\displaystyle \mathrm{Re}(X[k])^2 + \mathrm{Im}(X[k])^2
  3. 开根号得到该频率成分的幅值 |X[k]|，对应频谱图上的柱高。
    ∣X[k]∣\displaystyle |X[k]|

性能对比：从蜗牛到猎豹的数字

N² 和 NlogN 的差距，就是“让一万个人两两握手”和“排队传话”的差距。把两者的计算量写成公式，对比一目了然：

具体数字最有冲击力：N=1024 时，DFT 要 100 万次复数乘法，FFT 只要 1 万次，快约 100 倍；N=65536 时，DFT 约 43 亿次，要好几秒，FFT 约 100 万次，毫秒级，快 4000 多倍。点数越大，FFT 优势越夸张。这就是为什么今天的手机、耳机、振动传感器里 FFT 无处不在——分桌合菜让傅里叶变换从“理论武器”变成了“日常工具”。

TDFT=N2,TFFT=Nlog⁡2NT_{\mathrm{DFT}} = N^2, \qquad T_{\mathrm{FFT}} = N \log_2 N
  1. DFT 的复杂度N 个频点各做 N 次累乘，总乘法次数是 N 的平方。
    TDFT=N2\displaystyle T_{\mathrm{DFT}} = N^2
  2. FFT 的复杂度每一层约 N 次操作，一共 log₂N 层，总次数是 Nlog₂N。
    TFFT=Nlog⁡2N\displaystyle T_{\mathrm{FFT}} = N \log_2 N
  3. 加速比两者相除得到 N/log₂N，N 每翻一倍，FFT 的优势就翻一倍。
    TDFTTFFT=Nlog⁡2N\displaystyle \frac{T_{\mathrm{DFT}}}{T_{\mathrm{FFT}}} = \frac{N}{\log_2 N}

AI 应用场景

实时语音频段可视化

阶段：数据预处理 / 特征提取

解决的问题：音频 App 的频谱图要每秒刷新 30-60 次，如果每帧都做 N² 次乘法的直接 DFT，手机必然卡顿掉帧。FFT 把 1024 点分析压到毫秒级以内，让波形和频谱实时联动成为可能。

具体案例：K 歌 App 的实时频谱显示：麦克风以 48kHz 采样，每 21 毫秒取 1024 点做一次 FFT，输出 512 个频点幅值，对应屏幕上跳动的频谱柱。降噪耳机也用同样的流水线识别环境噪音频段，只是把 FFT 放进了数字信号处理器芯片里。

工业设备振动监测

阶段：特征工程

解决的问题：旋转机械的故障振动信号往往淹没在背景噪声里，直接看波形很难发现异常。把振动波形做 FFT 得到频谱，轴承磨损、齿轮断齿都有各自的特征频率。传统 DFT 算不过来，FFT 让每个传感器都能实时出频谱。

具体案例：工厂给电机加装加速度传感器，每 128 点一组做 FFT，持续监控 1 倍频、2 倍频的幅值变化。当某条谱线幅值突然超过阈值，系统提前三天预警轴承故障，避免整条产线停机。

医学脑电频带分析

阶段：信号预处理

解决的问题：脑电（EEG）是微伏级的微弱信号，医生需要实时观察 δ、θ、α、β 等频带的功率变化。FFT 让每帧 256 点脑电的频带拆分在几毫秒内完成，把复杂信号变成直观的频带功率曲线。

具体案例：睡眠监测仪把整晚脑电按 4 秒一帧做 FFT，输出各频带功率随时间的演变图，自动标记深睡、浅睡、快速眼动期，极大减轻医生人工判读负担。

Python 演示

python77 行
import cmathimport mathimport time  def dft_naive(x):    # 直接按定义计算 DFT, 复杂度 O(N^2)    n = len(x)    return [sum(x[t] * cmath.exp(-2j * math.pi * k * t / n) for t in range(n))            for k in range(n)]  def fft_recursive(x):    # 递归版基2 Cooley-Tukey FFT    n = len(x)    if n <= 1:        return x[:]    even = fft_recursive(x[0::2])   # 偶数位子序列    odd = fft_recursive(x[1::2])    # 奇数位子序列    w = [cmath.exp(-2j * math.pi * k / n) for k in range(n // 2)]    left = [even[k] + w[k] * odd[k] for k in range(n // 2)]    right = [even[k] - w[k] * odd[k] for k in range(n // 2)]    return left + right  def fft_iterative(x):    # 迭代版基2 FFT, 用蝶形运算逐层合并    n = len(x)    j = 0    for i in range(1, n):        # 比特反转: 把输入重排到自然序        bit = n >> 1        while j & bit:            j ^= bit            bit >>= 1        j ^= bit        if i < j:            x[i], x[j] = x[j], x[i]    length = 2    while length <= n:        wlen = cmath.exp(-2j * math.pi / length)        half = length // 2        for i in range(0, n, length):            w = 1            for j in range(i, i + half):                u = x[j]                v = x[j + half] * w                x[j] = u + v                x[j + half] = u - v                w *= wlen        length <<= 1    return x  def main():    n = 1024    signal = [cmath.exp(2j * math.pi * 3 * t / n) +              0.5 * cmath.exp(-2j * math.pi * 7 * t / n)              for t in range(n)]    r0 = dft_naive(signal)    r1 = fft_recursive(signal)    r2 = fft_iterative(signal[:])    d1 = max(abs(a - b) for a, b in zip(r0, r1))    d2 = max(abs(a - b) for a, b in zip(r0, r2))    assert d1 < 1e-8 and d2 < 1e-8, "FFT result differs from DFT"    print("three implementations match, max err %.2e" % max(d1, d2))    t0 = time.perf_counter()    dft_naive(signal)    t1 = time.perf_counter()    fft_iterative(signal[:])    t2 = time.perf_counter()    print("DFT %.3fs, FFT %.5fs, speedup %.0fx"          % (t1 - t0, t2 - t1, (t1 - t0) / (t2 - t1)))  if __name__ == "__main__":    main()
目的：用暴力 DFT、递归 FFT、迭代 FFT 三种方式计算同一信号的频谱，验证结果一致并直观对比速度差距。
  1. even = fft_recursive(x[0::2])用 Python 切片取偶数位采样点，递归成一半规模的问题，这是分治的第一步。
  2. odd = fft_recursive(x[1::2])取奇数位采样点，与偶数位形成一对子问题，各自独立求解。
  3. w = [cmath.exp(-2j * math.pi * k / n) for k in range(n // 2)]预计算 N/2 个旋转因子，避免递归中重复算指数。
  4. left = [even[k] + w[k] * odd[k] for k in range(n // 2)]蝶形加法支路，合并偶数与旋转后的奇数结果。
  5. right = [even[k] - w[k] * odd[k] for k in range(n // 2)]蝶形减法支路，与加法支路共用同一批旋转因子。
  6. bit = n >> 1比特反转初始化，迭代版 FFT 要求把输入按位反转重排，才能在原地做蝶形。
  7. wlen = cmath.exp(-2j * math.pi / length)当前蝶形层的旋转因子步长，每层跨度翻倍。
  8. v = x[j + half] * w蝶形中“奇数支路先乘旋转因子”，对应公式里的 W·B。
  9. x[j] = u + v` 和 `x[j + half] = u - v蝶形单元的一加一减，一次完成两个频点的更新。

常见误区

误区我刚开始学 FFT 时，以为它是和 DFT 并列的一种新变换，名字里带“快速”两个字，应该是换了一套更高级的数学公式吧，算出来的东西可能也不完全一样。

正解不是的。FFT 和 DFT 算出的结果一模一样，它只是把 DFT 里的重复计算省掉的算法，不是新的变换。就像 7×8 和 8×7 结果相同，只是计算顺序不同。Cooley-Tukey 只是改变运算次序，没有改变数学本质。

为何常见：教材把 FFT 和 DFT 分章讲，名字里都有“傅里叶变换”，很容易让人误以为是两个数学定义不同的东西。

误区我只要把 FFT 点数 N 调大，频率分辨率就一定会变高，那我不停加 N 不就好了？反正 FFT 够快。

正解分辨率 Δf = fs/N。在采样率 fs 固定时增大 N（即采集更长时间），分辨率确实变高。但如果只是把一段 1 秒信号“补零”到 8192 点，分辨率不会变好——补零只是插值，没有增加真实信息。真正要看原始信号采集了多久。

为何常见：大家习惯把“点数 N”当成一个旋钮，以为拧大就万事大吉，忽略了 N 本质上是“采样率 × 时长”的产物。

误区我手里的数据长度是 1000，不是 2 的幂，是不是就只能用慢吞吞的 DFT 了？那我做实时分析还有希望吗？

正解Cooley-Tukey 基 2 要求 N 是 2 的幂，但工程上还有混合基、Bluestein 算法（chirp-z）、以及更一般形式的库利-图基算法，任何合数都能拆成素因子分别处理。numpy 这类库会自动为任意长度选择最优策略。N 是 2 的幂只是最方便的情况，不是唯一选择。

为何常见：教材以基 2 为切入点，示例全是 2 的幂，容易留下“只有 2 的幂才能用 FFT”的错觉。

误区基 4 一层合并 4 个点，层数只有基 2 的一半，乘法也少了约 25%，那是不是所有场景都应该无脑用基 4？

正解基 4 的乘法数确实更少，但加法略多、程序更复杂；而在现代 CPU 上，乘法和加法的耗时差距很小，真正的瓶颈往往是访存和缓存。成熟的 FFTW 库会针对硬件自动选基数，甚至混合使用基 2、基 3、基 5。盲目用基 4 不一定更快。

为何常见：只盯着理论乘法数的减少，容易忽略硬件上访存、流水线、指令开销这些“隐性成本”。

误区采样率 fs 越高，频谱上的刻度就越细，所以频率分辨率就是采样率吧？把 fs 调大不就行了吗？

正解采样率决定的是“最高能看多高的频率”（奈奎斯特频率 fs/2），而不是“能区分多近的两个频率”。后者是 Δf = fs/N，取决于采样时长：1 秒数据分辨率 1Hz，0.1 秒数据分辨率 10Hz。在 N 不变时提高 fs，频点间隔反而变宽。

为何常见：fs 和 Δf 都出现在公式里，字母又像，初学者很自然会把“采样率”和“频率分辨率”这两个概念混在一起。

面试题

Q1. FFT 相比直接计算 DFT，时间复杂度从什么降到什么？

单选题 · easy

  • A.O(N²) 降到 O(NlogN)← 正确答案
  • B.O(N) 降到 O(logN)
  • C.O(N²) 降到 O(N)
  • D.O(NlogN) 降到 O(N)

答案：A。FFT 的核心贡献就是让复杂度从 O(N²) 降到 O(NlogN)。这就像阿傅从“每道菜重听整首歌”变成“分桌合菜”，跑腿次数从百万级降到万级。其他选项的降幅方向不对或起点不对。

Q2. Cooley-Tukey 算法的核心思想是什么？

单选题 · mid

  • A.分治：按奇偶拆分再合并← 正确答案
  • B.分治：随机采样减少点数
  • C.用查表替代所有乘法
  • D.用迭代替代所有递归

答案：A。Cooley-Tukey 的妙招是把序列按下标奇偶拆成两个子序列，各自递归做 DFT，再用旋转因子合并。B 是降采样，不是精确算法；C 查表只能部分优化常数；D 迭代只是实现方式，不是算法思想本身。

Q3. 基2 FFT 要求输入点数 N 满足什么条件？

单选题 · easy

  • A.N 是 2 的幂← 正确答案
  • B.N 是任意正整数
  • C.N 是 4 的倍数
  • D.N 是素数

答案：A。基2 的"2"就是每次拆两份，所以要一路拆到 1 点，N 必须是 2 的幂，如 256、1024、4096。N 是 4 的倍数是基 4 的要求；任意长度需要混合基或 Bluestein 算法。

Q4. 一个标准蝶形运算单元输入 A 和 B，输出是什么？

单选题 · mid

  • A.A+WB 和 A-WB 两支路← 正确答案
  • B.A×B 和 A÷B 两支路
  • C.A+B 和 A×B 两支路
  • D.A-B 和 A+B 两支路

答案：A。蝶形运算的精髓是：B 先乘旋转因子 W，再分别与 A 做加法和减法，得到两个频点 X[k] 和 X[k+N/2]。加减两支路共用同一个旋转因子，这是计算量减半的关键。C 和 D 要么漏了旋转因子，要么不是蝶形的结构。

Q5. 采样率 fs=8000Hz，做 N=1024 点 FFT，频率分辨率约为多少？

单选题 · mid

  • A.约 7.8 Hz（8000/1024）← 正确答案
  • B.约 1024 Hz（点数本身）
  • C.约 0.13 Hz（倒数关系）
  • D.约 4000 Hz（奈奎斯特频率）

答案：A。Δf = fs/N = 8000/1024 ≈ 7.8Hz，表示频谱上相邻两个频点相隔约 7.8Hz。D 的 4000Hz 是能分析的最高频率（奈奎斯特频率），不是分辨率；B 和 C 把分子分母弄反了。

Q6. 关于 FFT 的蝶形运算，下列说法正确的有哪些？

多选题 · mid

  • A.一次蝶形只做一次复数乘法← 正确答案
  • B.加减支路共用同一个旋转因子← 正确答案
  • C.每层蝶形个数等于总点数 N
  • D.蝶形运算只存在于基 2 算法中

答案：AB。一次蝶形单元只有 W·B 这一次复数乘法，加减各一次，所以 A 正确；B 是蝶形能省计算量的原因。C 错误，基 2 每层是 N/2 个蝶形；D 错误，基 4 也有蝶形，只是入口出口更多。

Q7. N=65536 时，FFT 比直接 DFT 快约多少倍？

单选题 · hard

  • A.约 4096 倍← 正确答案
  • B.约 512 倍
  • C.约 65536 倍
  • D.约 16 倍

答案：A。加速比 = N/log₂N = 65536/16 = 4096 倍。65536 的 log₂ 是 16，所以 DFT 的约 43 亿次乘法缩到 FFT 的约 100 万次，正好差 4096 倍。这就是为什么大点数下 FFT 是不可替代的。

Q8. 关于频率分辨率和采样率，下列说法正确的有哪些？

多选题 · hard

  • A.频率分辨率 Δf = fs/N← 正确答案
  • B.相同点数下提高 fs 会降低分辨率← 正确答案
  • C.增加采样时长可以变高分辨率← 正确答案
  • D.采样率越高能分析的频率上限越低

答案：ABC。A 是基本公式；B 中 N 不变时 fs 增大，Δf 变大，分辨率变差；C 中采样时长增长意味着 N 变大，Δf 变小，分辨率变高。D 错误：采样率越高，奈奎斯特频率 fs/2 越高，能分析的上限越高。

Q9. FFT 输出 X[k] 的幅值 |X[k]| 表示什么？

单选题 · easy

  • A.频率成分 k 的强度← 正确答案
  • B.时间成分 k 的强度
  • C.输入信号总功率
  • D.相位角的度数

答案：A。X[k] 是第 k 个频率成分的复数，取幅值得到该频点的强度，也就是频谱图上柱子的高度。B 混淆了时域和频域；C 是全体频点能量的总和；D 是复数辐角，不是幅值。

Q10. 基4 FFT 相比基2 FFT，下列说法正确的有哪些？

多选题 · extreme

  • A.每层合并四个子序列← 正确答案
  • B.层数只是基2 的一半← 正确答案
  • C.总乘法数少约 25%← 正确答案
  • D.对任意长度都适用

答案：ABC。基4 每层四路合并，层数 log₄N = (log₂N)/2，乘法数约少四分之一，所以 A、B、C 正确。D 错误：基4 要求 N 是 4 的幂，并非任意长度；选择哪个基数要结合硬件特性，这也是工程上常用混合基的原因。