一、FFT 算法概述
快速傅里叶变换（Fast Fourier Transform，FFT）是离散傅里叶变换（DFT）的高效算法，通过分治策略将 DFT 的时间复杂度从 O(N²) 降至 O(N log N)，使其在信号处理、图像处理、通信等领域具有广泛应用。本文将详细介绍如何用 C 语言实现基 - 2 时域抽取（DIT）FFT 算法，并提供完整的代码示例与解析。
二、FFT 算法原理（基 - 2 DIT）
基 - 2 FFT 算法的核心思想是将长度为 N=2M 的序列逐次分解为两个长度为 N/2 的子序列，通过蝶形运算递归合并结果。关键步骤包括：
- 蝶形运算：利用旋转因子 WNk=e−j2πk/N 合并子序列的 DFT 结果。
- 位反转置换：将输入序列按奇偶分组的顺序转换为自然顺序，便于迭代计算。
三、C 语言实现步骤
3.1 数据结构定义
使用结构体表示复数，包含实部和虚部：
typedef struct {double real;double imag;
} Complex;
3.2 旋转因子计算
利用欧拉公式计算旋转因子 WNk=cos(2πk/N)−jsin(2πk/N)：
Complex make_complex(double r, double i) {Complex c;c.real = r;c.imag = i;return c;
}Complex multiply(Complex a, Complex b) {