FFT里那个老被念错的“基”，到底是什么？
做信号处理的人，几乎没有不认识快速傅里叶变换（FFT）的。但很多人用了很久FFT，问他“你用的基几？DIT还是DIF？”往往答不上来。这不怪大家，教材上关于“按时间抽取（DIT）的基2算法”这半句话，常常被一笔带过，仿佛这是理所当然的常识。实际上，理解这句话的每一个字，对你真正吃透FFT、甚至是在嵌入式板子上手写优化实现时，都极其关键。
这篇文章，我就专门盯着“快速傅里叶变换（FFT）——按时间抽取DIT的基”这句话里“基”这个字往下讲。带你从最底层的分治原理出发，把基2 DIT-FFT的蝶形运算、旋转因子、位序重排这些环节彻底捋清楚，顺便把我实际写代码、调数据时踩过的坑和积累的经验一并说了。不管你是正在啃数字信号处理教材的学生，还是搞嵌入式、通信、音频处理要自己撸FFT的工程师，这篇都能帮你把最后那层窗户纸捅破。
1. 先把“DIT的基”这个说法彻底讲明白
初学者最容易懵的地方，就是“基”（radix）这个概念。教科书上一般写“按时间抽取（DIT）的基2 FFT算法”，意思是：这种算法把一个N点序列的DFT，通过不断地“按时间序号奇偶分组”拆成小序列，每一次拆分都把一个大DFT化成两个规模一半的DFT，这种每次一分为二的策略，就是基2。
1.1 基2到底“基”在哪里
所谓“基2”，本质是指蝶形运算的“岔路数”是2。你可以把FFT当成一棵倒过来的树，根是N点序列，叶子是1点序列（1点DFT就是它本身）。每次一个节点分裂出两个子节点，就是基2；如果分裂出4个子节点，就是基4。
那为什么大家天天挂在嘴边的基2最普遍？关键原因是硬件和代码上非常好实现。基2要求序列长度N必须是2的整数次幂，比如256、1024、4096。数字系统天生是二进制的，地址对齐、循环次数、蝶形间距控制都能用移位和位操作完成，效率极高。从算法复杂度的角度看，基2 FFT把原先需要N²次复数乘法的DFT降到了(N/2)log₂N次，以1024点为例，DFT要104万次乘法，FFT只要5120次，差了200多倍。这买卖做得很划算。
1.2 DIT和DIF到底差在哪
说完基，再看抽取方式。DIT（Decimation-In-Time，按时间抽取）是按输入序列的下标n是奇数还是偶数来重新排列数据；另一种常见的DIF（Decimation-In-Frequency，按频率抽取）则是把输出序列的频点X(k)按奇偶拆开。
DIT的核心特点是：输入序列被打乱之后重新排列（这就是大家常说的位序倒置），输出则是自然顺序；而DIF恰好反过来，输入是自然顺序，输出被打乱。所以很多人偷懒记成“DIT——输入乱输出顺，DIF——输入顺输出乱”。这两者本质上只是时间抽取和频率抽取的镜像操作，计算量一样，实现上代码的转置方向相反。
我实际写代码时，偏爱DIT。原因很朴素：很多传感器采集数据时是顺序采样的，DIT需要先做位序重排再计算，但如果我在采集过程中就按倒序存放，那计算前就完全不需要额外重排，省去一个耗时步骤。当然这只是实现技巧，后面细说。
1.3 一个关于“基”字的准确补充
还得顺嘴提一句，“基”不是“基数”的省略，原始语境里它表示一个蝶形单元一次合并几条数据流。常见的不只有基2，还有基4、基8，以及混合基和分裂基。混合基的意思是大点数情况下先用基4划几轮，最后剩几级再退回基2，比如1024点可以先做5级基4再做1级基2。这样能减少旋转因子乘法次数，但控制逻辑复杂度明显上升。
所以“基”这个字，解决的是“怎么拆、拆成几路”的排列组合问题。理解了它，你再回头看FFT的各种变体，思路会瞬间清晰很多。
2. 核心原理拆解：从DFT公式到蝶形单元的每一步推导
光记住“基2是两路合并”肯定不够，你得能自己把公式推出来，才算真正掌握DIT-FFT。这一段我用最直白的方式，完整走一遍推导流程。
2.1 从DFT的定义出发，先看最原始的N点计算
N点序列x[n]的N点DFT定义为：
X[k] = Σ_{n=0}^{N-1} x[n] · W_N^{nk}， k = 0, 1, ..., N-1
其中W_N = e^{-j(2π/N)}，也就是旋转因子。直接按这个公式算，每一个X[k]都要做N次复数乘法，算完全部N个k，总计算量是N²次。1024点就超过100万次，放在实时系统里基本不可接受。
2.2 奇数位与偶数位分开：第一次分解
DIT的第一步，是按下标n的奇偶性把x[n]拆成两个子序列。令n = 2r（偶数）和n = 2r+1（奇数），其中r从0取到N/2 - 1：
x_even[r] = x[2r]， x_odd[r] = x[2r+1]
代回DFT定义，转动因子拆分一下：
X[k] = Σ_{r=0}^{N/2-1} x[2r] · W_N^{2rk} + Σ_{r=0}^{N/2-1} x[2r+1] · W_N^{(2r+1)k}
注意W_N^{2rk} = W_{N/2}^{rk}，这个性质至关重要——它说明偶数位子序列的DFT，本质上是一个N/2点的DFT，只是旋转因子的“底”从N换成了N/2。于是：
X[k] = X_even[k] + W_N^k · X_odd[k]， k = 0, 1, ..., N-1
其中X_even[k]和X_odd[k]分别是N/2点序列x_even[r]和x_odd[r]的N/2点DFT。
这个式子看似简单，但它只说了k从0到N-1的情况。而X_even[k]和X_odd[k]本身是周期为N/2的序列，因为它们是N/2点DFT，天然满足周期性。利用这一点，可以进一步把完整的N点X[k]表示成两个半段。这就是蝶形运算的核心公式：
X[k] = X_even[k] + W_N^k · X_odd[k]， k = 0, ..., N/2-1
X[k + N/2] = X_even[k] - W_N^k · X_odd[k]， k = 0, ..., N/2-1
2.3 旋转因子的关键性质：为什么能省这么多乘法
那为什么这个等式成立？关键在于旋转因子的两个基本性质。
第一是周期性：W_N^{k+N/2} = -W_N^k。这一点可以直接验证：W_N^{N/2} = e^{-jπ} = -1，所以乘以这个因子就是取负。第二是可约性：W_N^{2rk} = W_{N/2}^{rk}。这保证了拆分后子序列的DFT规模逐级减半。
因为X_even和X_odd都是N/2点序列的DFT，所以它们的每个值只需要N/2次运算。而利用负号性质，X[k]的前半段和后半段可以共用X_even和X_odd的同一批计算结果，只是相加和相减的区别。这就是所谓的“蝶形”：两个输入（一个来自偶数子序列、一个来自奇数子序列），乘以旋转因子后，一个加一个减，输出两个点。一次蝶形只需要1次复数乘法、2次复数加法，却计算了X[k]和X[k+N/2]两个输出点。
2.4 递归拆分：N = 2^M最终拆到2点蝶形
上面只做了一层拆分，把一个N点DFT变成了两个N/2点DFT。两个N/2点DFT继续各自按下标奇偶性再拆，就得到4个N/4点DFT。一直拆下去，直到序列长度为1，不需要再算。对于N = 2^M，一共可以拆M = log₂N级。每一级一共有N/2个蝶形运算，每个蝶形1次复数乘法，所以总乘法次数为(N/2)log₂N。
以8点为例：第1级是4个2点DFT（2点DFT本身也是一个蝶形），第2级是2个4点DFT，第3级是1个8点DFT。整个流程像一张三角形的网，网上每个节点都是一个蝶形。手工画图时你一定会发现，数据流的顺序从“自然序号”变成了“位序倒置”，这也是DIT最直观的视觉特征。
3. 蝶形运算的手工推演与第4级扩展
脑子过完公式，手还得跟上。我建议初学者至少手工完整推一遍4点DIT-FFT，因为它是所有大点数的缩影。4点推完再上8点，整个过程就有画面感了。
3.1 4点DIT-FFT的完整计算过程
假设输入是x[0], x[1], x[2], x[3]。按奇偶分组：
x_even = [x[0], x[2]]， x_odd = [x[1], x[3]]
2点DFT公式非常简单，a和b两个点的DFT结果是：
X[0] = a + b， X[1] = a - b
于是：
对x_even做2点DFT得到A[0] = x[0]+x[2]，A[1] = x[0]-x[2]
对x_odd做2点DFT得到B[0] = x[1]+x[3]，B[1] = x[1]-x[3]
然后输出X[k]按蝶形公式组合：
X[0] = A[0] + W_4^0 · B[0]
X[1] = A[1] + W_4^1 · B[1]
X[2] = A[0] - W_4^0 · B[0]
X[3] = A[1] - W_4^1 · B[1]
这里W_4^0 = 1，W_4^1 = -j。所以完整结果一目了然。
你会发现，4点DFT总共只需要2个2点DFT和2个带旋转因子的蝶形组合。手推一遍之后你自然明白：所谓“按时间抽取”，本质上就是不断二分时间下标，直到只剩两个点，然后逐级合并。
3.2 8点DIT-FFT的层级划分
再扩展到8点。整个计算分成3级，每级4个蝶形。
第一级：8个点按下标奇偶性分成4组，每组2点。因为偶数下标组是x[0], x[2], x[4], x[6]，奇数下标组是x[1], x[3], x[5], x[7]。每组2点做蝶形，本级的旋转因子都是W_2^0 = 1，所以第一级不需要复数乘法，只需要加减法。
第二级：把四个2点结果合并成两个4点结果。这时候每一组的2个2点DFT之间，用旋转因子W_4^0和W_4^1连接。这一级有2个旋转因子乘法。
第三级：两个4点合并成8点。这一级的旋转因子是W_8^0, W_8^1, W_8^2, W_8^3，分别对应-1的逆时针4等分位置。
你看，旋转因子的指数在逐级变大，但每一级用到的旋转因子数量正好是N/2个。我当年手推完8点之后才意识到，FFT实现代码里真的只需要维护一个旋转因子表，按级数依次取用即可。
3.3 蝶形运算的统一表达与编程要点
把上面所有蝶形抽象成同一段逻辑。对于每一级m（m从1到M），蝶形间距step = 2^m，组内蝶形的两个输入下标相差step/2 = 2^{m-1}，旋转因子的底是W_{step}，指数从0取到step/2 - 1。
用伪代码表示最内层的蝶形操作：
temp = input[index + offset] * twiddle[half]
output[index] = input[index] + temp
output[index + offset] = input[index] - temp
这里input[index + offset]对应奇数下标子序列的值。实际操作时需要注意，input和output必须用两块缓冲区交替读写，否则会出现数据覆盖导致后续计算错误。
3.4 为什么蝶形运算那么好用
之所以每个蝶形都能“一对二”地计算两个输出，本质是因为旋转因子W_N^{half_index} = -W_N^0 这种对称性。只要乘以负号，加法就能变成减法，一次复数乘法同时喂饱两个输出。这也就是DFT重复计算被消除的关键。
我在工程上最常被问到的就是：“DFT是O(N²)，FFT是O(NlogN)，这NlogN到底省在哪？”答案就在这里：省在利用了旋转因子的周期性和对称性，让大量相同的中间计算被复用。蝶形结构就是这种复用的物理载体。
4. 实操过程：用Python从零手写一个基2 DIT-FFT
讲完原理和蝶形，直接进入代码环节。我下面给出一个完整的、可运行的Python实现，尽量不依赖现成库，让你看清楚每一步到底在干嘛。整个实现分三块：位序重排、旋转因子预计算、蝶形迭代。
4.1 位序重排到底是在干嘛
DIT要求输入先按“位序倒置”（bit-reversal）重新排列。什么意思？以8点为例，自然下标0到7的二进制分别是000, 001, 010, 011, 100, 101, 110, 111。把每个二进制位倒过来，得到000, 100, 010, 110, 001, 101, 011, 111，也就是0, 4, 2, 6, 1, 5, 3, 7。
这个方法在Python里可以这样实现：
def bit_reverse_index(num, bits):
rev = 0 for _ in range(bits): rev = (rev << 1) | (num & 1) num >>= 1 return rev对N点序列，bits = int(log2(N))，然后把原数组下标映射到倒序后的新下标，完成重排。
4.2 完整实现
下面给一段完整的、可以直接跑的代码。我按常见约定，输入是复数数组。为了不引入复杂依赖，旋转因子用Python原生复数直接计算。
import cmath
import math
def dit_fft(x):
""" 按时间抽取的基2 FFT实现 x: 长度为N的复数序列，N必须为2的整数次幂 返回: 长度为N的复数频谱序列 """ N = len(x) M = int(round(math.log2(N))) if (1 << M) != N: raise ValueError("长度必须是2的整数次幂") # 1. 位序重排 arr = [0j] * N for i in range(N): rev_i = bit_reverse_index(i, M) arr[i] = x[rev_i] # 2. 预先算好各旋转因子，避免循环里重复调用三角函数 twiddles = {} for m in range(1, M + 1): halflen = 1 << (m - 1) # 间隔的一半 step = 1 << m # 本级的间隔 for k in range(halflen): angle = -2 * math.pi * k / step twiddles[(m, k)] = complex(cmath.cos(angle), cmath.sin(angle)) # 3. 蝶形迭代 m = 1 step = 2 while m <= M: halflen = step // 2 for start in range(0, N, step): for k in range(halflen): t = twiddles[(m, k)] * arr[start + k + halflen] u = arr[start + k] arr[start + k] = u + t arr[start + k + halflen] = u - t m += 1 step *= 2 return arr配合构造测试信号：
N = 8
x = [complex(i % 3, 0) for i in range(N)]
result = dit_fft(x)
for k, v in enumerate(result):
print(k, v)你可以拿它跟numpy.fft.fft的结果对比，幅值应该一致。归一化问题后面再细说。
4.3 关于旋转因子表的实现要点
上面代码里我先用字典缓存了所有旋转因子。这一举动的目的在于：FFT循环里如果每次重新计算cos/sin，成本极其高昂。对1024点来说，总旋转因子数约N/2log₂N=5120个，实际不同的角度很多，预先计算一遍存起来，后面直接查表，速度能快一个量级。
在嵌入式C语言实现里，更常用的做法是把旋转因子的实部和虚部提前算成两个float数组，放在RAM里，需要时直接取。你甚至可以固化到代码常量里，省去运行时计算。这就是为什么很多开源DSP库的FFT函数都要传一个“twiddle table”进去，本质上就是把这个表预先准备好。
4.4 性能验证与复杂度对比
我实测了一下，用纯Python跑这个DFT直接算8点、64点、1024点的耗时，发现N=1024时，DFT需要约几秒钟，而DIT-FFT只需要几十毫秒。原因在于乘法次数从N²降到(N/2)log₂N，而Python的复数乘法本身开销又大，所以差距非常显著。
验证方法很简单：先计算直接DFT结果，再计算FFT结果，所有频率点的幅度差小于1e-10，相位差小于1e-8，就能确定实现正确。如果你发现中间某几个频点结果不对，多半是位序重排出了问题，或者蝶形的输入和输出下标写反了。
5. 常见问题排查与避坑实录
写FFT过程中，有几个巨坑几乎每个人都会踩。我把自己实际调试时总结的经验记录下来，希望你能少走弯路。
5.1 位序重排容易出错的地方
最容易犯的错是：把输入数组元素移动了，却没有对齐下标。比如对x = [a,b,c,d]，你可能直接变成[d,b,c,a]，这样下标乱了，后面蝶形全部错位。
正确做法是：新建一个数组arr，arr[i] = x[bit_reverse(i)]。原来数组保持不变。这样能避免在原地交换时出现重复交换的问题。有一个常见的原地swap技巧（把i和rev_i互换，并加一个条件i < rev_i防止重复交换），但新手容易漏条件导致序列乱掉。建议第一阶段先用临时数组，相信我不会慢到哪里去。
5.2 旋转因子符号搞反了
DFT定义里的指数是负的：W = e^{-j(2π/N)}。如果你用的FFT是正指数（e^{+j2π/N}），那结果就是逆变换方向。很多库的IFT和FFT只差一个负号，用错的话谱会和真实的共轭翻转。
我的自查办法是：输入一个纯实数的信号，比如x[0]=1，其余为0，FFT结果应该全是1；输入x[0]=1, x[1]=1，其他为0（相当于两个脉冲叠加），FFT结果实部应该对应cos，虚部是周期交替的。如果发现虚部符号和预期相反，就是旋转因子方向反了。
5.3 归一化到底要不要做
很多人问FFT输出的幅值怎么比预期大好多倍。标准FFT没有除以N，所以一个直流为1的信号，X[0]会等于N而不是1。要在幅值上得到真实的幅度，得做归一化：除以N。我一般习惯在FFT之后，所有频点除以N再取模。但在需要多次级联变换（比如做卷积）的时候，中间过程中不除以N，只在最后一步归一化，这样能减少舍入误差。
实际工程里，你用某嵌入式DSP库时经常能看到“缩放标志位”，比如让库自动在第2级、第6级做右移。这种分段缩放是为了防溢出，同时近似等价于最终除以N。这一点和纯学术公式并不一样，需要特别注意。
5.4 输入长度不是2的幂怎么处理
基2算法严格要求N = 2^M。如果你手头的数据长度是1000这种非2幂，有两个选择。
第一，补零：把长度补到1024。补零不会改变频谱分辨率（bin间隔还是Fs/1024），但会让频谱看起来更“密”，也就是插值效应。
第二，用混合基算法处理任意长度，这属于更进阶的内容。我建议项目初期直接补零，简单可靠，补零在频域上相当于理想带限插值，不会损失信息，也不会带来频谱泄漏。唯一要注意的是补零后总采样时长变了，频率分辨率要按新的N重新计算。
5.5 多通道实时处理时如何避免内存碎块
你在嵌入式里做多路ADC采样并行FFT时，缓存区的复用尤其要小心。我踩过的一个坑：把输入数组和输出数组直接复用同一块内存，结果上一级蝶形输出的数据被下一级当作输入覆盖了。正确的做法是每级用一个独立的输出数组，或者采用乒乓缓冲：第m级写到buffer B，读buffer A；第m+1级写在buffer A，读buffer B。如此交替，保证没有覆盖风险。
5.6 精度损失和溢出小技巧
用定点DSP做FFT时，最容易出现中间结果溢出。因为每级蝶形中间乘法会把数据幅度放大到原来的2倍，N=1024时，10级算完，理论峰值可能放大到N倍。如果采取每级右移一位的固定缩放策略，信噪比会损失不少，但工程上简单可靠。想尽量保留精度，可以改用块浮点（block floating point）——用一个共享指数记录所有数据的放缩因子，每级动态调整整体指数。这个技巧在需要对动态范围敏感的音频FFT中特别常见。
6. 从理论到工程落地：DIT-FFT的现实考量
前面把DIT-FFT的推导和实现讲透了。这一节我聊一下当你在真实项目中用它时，最常遇到的几个工程化问题。毕竟教材里的图和代码是干干净净的，但现场数据从来都不干净。
6.1 窗函数：为什么FFT之前要先加窗
你在做频谱分析时，如果信号不是整周期截断，FFT会产生严重频谱泄漏。处理办法是加窗。常见窗函数有汉宁窗、海明窗、布莱克曼窗。
加窗后信号幅度会被改变，所以幅值恢复时需要乘以一个修正系数。以汉宁窗为例，其幅度恢复系数是2，也就是要把窗后的FFT幅值乘以2再除N。如果是功率谱，则要恢复功率，恢复系数是1.633。这些系数查手册或自己算一下，切勿盲目套通用系数。我当年就吃过这个亏：直接用幅度恢复系数去算功率谱，结果整体偏小约1.9dB，折腾了一天才定位到。
6.2 频率分辨率、采样率与FFT点数三者的关系
频率分辨率Δf = Fs / N。要做高分辨率，只能增加N（增加采样时长）或降低Fs（注意满足奈奎斯特定律）。
很多刚入行的同学以为补零能提高分辨率，这是误解。补零只能让频谱看起来更平滑，原本分不开的两个频率分量依然分不开。想分辨两个很近的谱峰，必须加长实际采样时长。这个我在实际频谱分析项目中反复验证过，补零不能代替真实采样时长，这点希望对你有帮助。
6.3 实数输入的优化技巧
实际采集的信号几乎都是实数的。实数FFT可以仅计算一半的点，因为实信号的频谱具有共轭对称性。你大可以只用N/2点复数FFT去算N点实数FFT，速度几乎翻倍。某些DSP库的rfft函数就是干这个的。
还有一种常见的优化思路：把两个实序列分别包装成复数序列的实部和虚部，做一次复数FFT，再通过对称性拆出两路的频谱。这样做的计算量大约只有各自做FFT的一半多一点，相当划算。我建议你做到N=1024以上、且实时性要求高时，去实现或借用现成的rfft，不要傻傻地用复数FFT硬算。
6.4 基于缓存友好的迭代式实现
处理大点数FFT时，内存访问模式对性能影响极大。教材里最朴素的实现，在每一级蝶形中会跨大步长访问内存，造成cache miss严重。优化思路是把蝶形运算局部化，典型手法是分块处理或使用“四步算法”（4-step FFT），把大FFT拆分成多次小FFT和矩阵转置，从而让数据尽量保留在cache里。
比如在嵌入式处理器上做一个4096点FFT，直接按教科书实现可能要用几百微秒，而优化后的库可能只需要几十微秒。差距主要来自两个层面：一是查表旋转因子而不是现场计算三角函数，二是内存访问的局部性。这些都值得你在优化时重点关注。
6.5 从一维到多维：DIT思想在二维FFT中的应用
图像处理里常遇到二维FFT。二维FFT其实可以先对每一行做一维FFT，再对每一列做一维FFT。每行每列的FFT依然可以用DIT基2算法。这时候DIT的位序重排会被执行两次，一次在行方向、一次在列方向。不过工程上很多二维FFT实现是先转置再做行FFT，转置那一步做好cache优化，性能就能提升明显。
对于大尺寸图像（比如4096×4096），纯行-列FFT的计算量很大，得考虑分块、并行和GPU加速。但不管硬件怎么变，DIT基2这个内核始终是基础，理解了一维实现，二维只是对它的一层包装。
7. 一段个人经验总结
我在不同硬件平台上用DIT-FFT处理过不少真实的信号，包括振动数据的频谱分析、音频均衡器、雷达回波的距离-多普勒处理。每次遇到性能瓶颈，我都会先回到DIT-FFT的基本结构上去想，优化往往就藏在那些看似不起眼的蝶形组合和存储策略里。
分享一个经常被我用的调试小技巧：调试FFT实现时，先从2点、4点开始逐步测试。如果2点对了，说明位序重排只对一半；如果4点不对，多半问题出在旋转因子的指数映射上。建议在代码里临时打印每个蝶形的输入输出值，跟手算结果比对，定位非常快。不要一上来就跑到1024个点，那样出了问题根本无从排查。
还有一点在实际工作中的体会：FFT的“基”选择不只影响速度，还影响定点精度。基4虽然乘法次数更少，但每次蝶形有3个旋转因子，定标误差积累方式和基2不一样。我做过一次对比，用16位定点做8192点FFT时，基4的噪声性能比基2好一点，原因是乘法次数少，舍入误差积累少；但基4的控制器复杂度高不少。所以在工程项目里，很大一部分情况我们还是选择基2。它的逻辑最简单、最不容易出错、调试成本最低，而且对大部分优化场景已经足够了。
8. 关于“基”的进一步扩展：什么时候该考虑基4和分裂基
既然说到了基4，这里稍微展开讲讲。
基4 DIT-FFT每次把序列按时间下标mod 4分成4组，递归深度只有基2的一半，即M/2级。每一级分成4个子序列的DFT组合，每个蝶形有3个不同的旋转因子。
从计算量上看，基4复数乘法数是(3/8)Nlog₂N次乘以某个系数，比基2少大约25%。但代码复杂度提升不少。很多库中，大点数FFT首先进行基4分解，最后留一级基2处理非4倍数的尾巴。
分裂基（split-radix）是另一个方向，它把偶序号部分继续用基2，奇序号部分用基4，号称乘加次数接近理论极限，比纯基2节省约1/3的乘法。如果你的项目对功耗和速度要求极高，而你的数学功底又够扎实，可以深入研究一下分裂基。
但对我这种实践派来说，大部分AGCM噪声抑制、音频均衡器、电力谐波分析，用基2配合合理优化已经绰绰有余。真正决定系统性能的往往是把FFT用好比单纯换FFT变种更重要，比如配合合适的窗函数、合理的块长选点、做零填充、用实数FFT优化等。基4、分裂基更像进阶玩具，你对它们了解即可，不要一开始就用复杂度换收益。
9. 写在最后：一个小彩蛋
最后分享一个我经常拿来检验FFT实现是否正确的信号：x[n] = cos(2π · 3n / N) + 0.5cos(2π · 5n / N)。对这个信号做FFT，你应当在第3根和第5根谱线处看到清晰的峰值，幅值分别是N/2和N/4。如果看到峰值位置偏移了，先检查位序重排是否有误；如果看到全谱乱了，再检查旋转因子指数映射。这个小信号既是测试用例，也是我向别人解释FFT功能时最直观的例子。
我还建议你在实际开发里把FFT函数封装成带注释的库，输入参数包含指针、点数、窗函数、缩放模式、旋转因子表，而不是做成只有一个数组参数的裸函数。封装好之后，整个项目的可维护性会提升很多。这个经验来自一次大型项目重构，那时我面对三千行裸FFT调用代码，差点想离职重写。封装之后，后续加窗、补零、幅值恢复全部变成几行配置，舒服太多。
希望这篇文章能帮你彻底搞懂“按时间抽取DIT的基2 FFT”到底在说什么。如果你在调试自己的实现时遇到问题，不必客气，多拆几遍蝶形图，多打印几个中间值，可能比对着書本看十遍还要有效。
：通信乱码排查实战)
