C语言快速傅里叶变换

快速傅里叶变换（Fast Fourier Transform，FFT）是一种高效的算法，用于计算离散傅里叶变换（Discrete Fourier Transform，DFT）。在C语言中，我们可以使用标准的库函数来实现FFT。

C语言中，常用的实现FFT的库函数是FFTW（Fastest Fourier Transform in the West）。FFTW是一个高性能、开源的库，提供了多种实现FFT的函数。

下面是一个使用FFTW库计算FFT的示例代码：

#include <stdio.h>
#include <fftw3.h>

#define N 8

int main()
{
    fftw_complex in[N], out[N];
    fftw_plan p;

    // 初始化输入信号
    for (int i = 0; i < N; i++) {
        in[i][0] = i;
        in[i][1] = 0;
    }

    // 创建FFT计算方案
    p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);

    // 执行FFT变换
    fftw_execute(p);

    // 打印输出结果
    for (int i = 0; i < N; i++) {
        printf("Output[%d]: %f + %fi\n", i, out[i][0], out[i][1]);
    }

    // 销毁计算方案
    fftw_destroy_plan(p);

    return 0;
}

上述代码中，我们首先初始化了一个长度为N的复数数组in，并创建了一个用于存储FFT结果的数组out。然后，使用fftw_plan_dft_1d函数创建了一个FFT计算方案p。接下来，使用fftw_execute函数执行FFT变换，并使用for循环打印输出结果。最后，使用fftw_destroy_plan函数销毁计算方案。

需要注意的是，使用FFTW库需要先安装该库，并在编译时链接对应的库文件。具体的安装和链接方法可以参考FFTW的官方文档。

除了FFTW库，还有其他一些C语言的FFT库可供选择，如KissFFT和CUFFT（用于并行计算）。根据实际需求和平台选择适合的库函数进行FFT计算。