C语言FFT算法详解（手把手教你用C语言实现快速傅里叶变换）

前置知识

• 基本C语言语法（变量、循环、函数）
• 复数的基本概念（实部、虚部）
• 数组的使用

实现思路

我们将采用基2时间抽取（Decimation-in-Time, DIT）的Cooley-Tukey算法，这是最经典的FFT实现方式。要求输入数据长度 N 必须是 2 的整数次幂（如 8、16、32...）。

完整C语言FFT代码实现

下面是一个完整的、可直接编译运行的C语言FFT算法实现：

#include <stdio.h>#include <math.h>#include <stdlib.h>#define PI 3.14159265358979323846typedef struct {    double real;    double imag;} Complex;// 复数加法Complex add(Complex a, Complex b) {    Complex c;    c.real = a.real + b.real;    c.imag = a.imag + b.imag;    return c;}// 复数减法Complex sub(Complex a, Complex b) {    Complex c;    c.real = a.real - b.real;    c.imag = a.imag - b.imag;    return c;}// 复数乘法Complex mul(Complex a, Complex b) {    Complex c;    c.real = a.real * b.real - a.imag * b.imag;    c.imag = a.real * b.imag + a.imag * b.real;    return c;}// 位逆序置换void bit_reverse(Complex *x, int N) {    int bits = 0;    int temp = N;    while (temp >>= 1) bits++;    for (int i = 0; i < N; i++) {        int j = 0;        for (int k = 0; k < bits; k++) {            if (i & (1 << k))                j |= 1 << (bits - 1 - k);        }        if (j > i) {            Complex t = x[i];            x[i] = x[j];            x[j] = t;        }    }}// 快速傅里叶变换（基2 DIT）void fft(Complex *x, int N) {    // 位逆序重排    bit_reverse(x, N);    // 蝴蝶运算    for (int s = 1; s <= log2(N); s++) {        int m = 1 << s;          // 当前组大小        int m2 = m / 2;          // 半组大小        double theta = -2 * PI / m;        Complex w_m = {cos(theta), sin(theta)}; // 主根        for (int k = 0; k < N; k += m) {            Complex w = {1.0, 0.0};            for (int j = 0; j < m2; j++) {                Complex t = mul(w, x[k + j + m2]);                Complex u = x[k + j];                x[k + j] = add(u, t);                x[k + j + m2] = sub(u, t);                w = mul(w, w_m);            }        }    }}// 测试主函数int main() {    const int N = 8;    Complex x[N] = {        {1, 0}, {1, 0}, {1, 0}, {1, 0},        {0, 0}, {0, 0}, {0, 0}, {0, 0}    };    printf("输入信号:\n");    for (int i = 0; i < N; i++) {        printf("%.2f + %.2fi\n", x[i].real, x[i].imag);    }    fft(x, N);    printf("\nFFT结果:\n");    for (int i = 0; i < N; i++) {        printf("X[%d] = %.2f + %.2fi\n", i, x[i].real, x[i].imag);    }    return 0;}  

代码说明

上述代码包含以下几个关键部分：

1. Complex结构体：用于表示复数。
2. 复数运算函数：add、sub、mul 分别实现加、减、乘。
3. bit_reverse函数：对输入序列进行位逆序重排，这是DIT-FFT的关键预处理步骤。
4. fft函数：核心算法，通过多级“蝴蝶运算”完成变换。

如何编译和运行？

将上述代码保存为 fft.c，然后在终端执行：

gcc fft.c -o fft -lm./fft

注意：必须链接数学库 -lm，因为使用了 sin、cos 等函数。

应用场景

掌握快速傅里叶变换C实现后，你可以将其应用于：

• 音频频谱分析
• 滤波器设计
• 通信系统调制解调
• 图像压缩（如JPEG）

总结

本文详细讲解了如何用C语言从零实现FFT算法，并提供了完整可运行的代码。通过这个FFT代码教程，你不仅理解了算法原理，还掌握了实际编码技巧。希望你能在此基础上继续深入学习数字信号处理C语言的更多高级内容！

提示：实际工程中可考虑使用FFTW等成熟库，但手写FFT有助于深入理解信号处理本质。