数组实现FFT需将实数信号转为复数数组并原地蝶形运算，索引映射决定频点物理意义，N须为2的幂以保障效率，输出X[k]对应频率k·fs/N，需依此提取幅度、相位及主频等可解释变量。
用数组实现快速傅里叶变换（FFT），核心是把信号数据存成一维复数数组，再通过原地蝶形运算完成频域转换。它不是“调个函数就完事”，而是要理解数组索引如何映射到频点、实部虚部如何组织、采样长度为何影响分辨率——这些都直接决定你拿到的频域变量是否可解释、可复用。
数组结构与数据准备：实数输入怎么转复数序列
大多数实际信号（如音频、传感器读数）是实数序列，但FFT要求复数输入。常见做法是：将实数数组 x[0..N−1] 视为复数数组的实部，虚部全置零。例如：
- 定义复数数组 data[N]，其中 data[i].real = x[i]，data[i].imag = 0
- 若使用 C/C++ 或 Python 的
numpy.complex64，需显式构造；MATLAB 中fft(x)自动处理，但底层仍按复数数组运算 - 注意长度 N 最好是 2 的整数幂（如 1024、4096），否则需补零（zero-padding）或截断，否则标准基-2 FFT 无法高效执行
频域采样点的物理对应：从数组下标到真实频率
FFT 输出是一个长度为 N 的复数数组 X[0..N−1]，每个元素 X[k] 对应一个离散频率分量，但不是任意频率——它严格由采样率 fs 和数组长度 N 决定：
- 频率分辨率：Δf = fs / N，即相邻频点间隔
- X[0] 是直流分量（0 Hz），X[1] 对应 fs/N，X[k] 对应 k × fs/N
- 对实数输入，频谱共轭对称：|X[k]| = |X[N−k]|，因此通常只取前 N/2 + 1 点画单边幅度谱
- 若需精确定位峰值（如测50Hz工频），不能只取最大值下标，还要做插值（如抛物线拟合），因为真实频率可能落在两个离散频点之间
关键计算步骤：位逆序重排 + 蝶形迭代
高效 FFT 不靠递归，而靠两步数组原地操作：
- 位逆序重排（Bit-reversal permutation）：将原始数组按索引的二进制位翻转后重新排序。例如 N=8 时，索引 3（二进制 011）→ 翻转得 110 → 十进制 6，就把 data[3] 和 data[6] 交换。这步确保后续蝶形运算能顺序访问数据
- 蝶形运算（Butterfly stage）：按级数（log₂N 层）循环，每层内对每组间距固定的数对做复数加减与旋转因子乘法。所有运算均在原 data[] 数组上完成，无需额外大内存
- 旋转因子 W_N^k = cos(2πk/N) − i·sin(2πk/N) 可预先计算并存入数组，避免重复调用三角函数
输出解读与变量提取：不只是画个图
得到 X[k] 后，频域变量需明确提取逻辑：
- 幅度谱：取模 |X[k]|，反映各频率能量强度；常归一化为 |X[k]|/N 或 |X[k]|²/N（功率谱）
- 相位谱：用 atan2(X[k].imag, X[k].real) 计算，单位为弧度，对时延估计、滤波器设计至关重要
- 主频识别：在有效频带（如 20 Hz–20 kHz 音频）内搜索 |X[k]| 峰值，结合 k × fs/N 换算为实际频率
- 频带能量统计：对某段下标范围（如 k=10～50）求和 ∑|X[k]|²，用于特征提取或异常检测
