C 语言如何实现FFT算法，你知道吗？

只看该作者 · 2023-5-11 14:31

FFT (Fast Fourier Transform) 是一种高效计算离散傅里叶变换的算法。在 C 语言中，实现 FFT 算法通常需要用到复数和递归。

下面是一个简单的 C 语言代码实现 FFT 算法：

#include <math.h>

#include <stdio.h>

#include <stdlib.h>



#define PI 3.14159265358979323846



typedef struct {

    double real, imag;

} Complex;



Complex add(Complex a, Complex b) {

    Complex result = { a.real + b.real, a.imag + b.imag };

    return result;

}



Complex subtract(Complex a, Complex b) {

    Complex result = { a.real - b.real, a.imag - b.imag };

    return result;

}



Complex multiply(Complex a, Complex b) {

    Complex result = { a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real };

    return result;

}



void fft(Complex *x, int n) {

    if (n == 1) {

        return;

    }

    Complex *even = (Complex*) malloc(n / 2 * sizeof(Complex));

    Complex *odd = (Complex*) malloc(n / 2 * sizeof(Complex));

    for (int i = 0; i < n / 2; i++) {

        even[i] = x[2 * i];

        odd[i] = x[2 * i + 1];

    }

    fft(even, n / 2);

    fft(odd, n / 2);

    for (int i = 0; i < n / 2; i++) {

        Complex t = multiply(odd[i], (Complex) { cos(-2 * PI * i / n), sin(-2 * PI * i / n) });

        x[i] = add(even[i], t);

        x[i + n / 2] = subtract(even[i], t);

    }

    free(even);

    free(odd);

}



int main() {

    int n = 8;

    Complex x[] = { {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8, 0} };

    fft(x, n);

    printf("FFT:\n");

    for (int i = 0; i < n; i++) {

        printf("%f + %fi\n", x[i].real, x[i].imag);

    }

    return 0;

}

这段代码实现了一个简单的 FFT 算法，输入为一个长度为 2 的幂次方的复数数组，输出为其 FFT 的结果。其中，add、subtract、multiply 函数分别实现了复数的加、减、乘法运算。FFT 函数使用递归的方式计算 FFT，将输入数组分成偶数项和奇数项两部分，对其进行 FFT，然后将结果组合起来得到最终的 FFT 结果。注意，由于 C 语言没有原生的复数类型，这里使用一个结构体来表示复数，其中 real 表示实部，imag 表示虚部。