C语言实现快速傅里叶变换

C语言中实现快速傅里叶变换（Fast Fourier Transform, FFT）通常使用的是Cooley-Tukey算法，这是一种分治的递归方法，它将一个大尺寸的FFT分解为多个小尺寸的FFT和一些简单的卷积操作。在C语言中，最流行的库之一是`fftw3`，它是专为计算提供高效的FFT实现的。

以下是基本步骤概述：

1. **选择库**：如果你没有现成的库，FFTW是一个常用的开源选项，提供单精度和双精度的FFT实现。

#include <fftw3.h>

2. **创建计划**：使用`fftw_plan_dft_r2c_1d`或`fftw_plan_dft_c2r_1d`创建一个计划，分别用于从实数到复数域（离散正弦变换DST）或从复数到实数域（离散余弦变换DCT）的变换。

3. **数据准备**：确保数组的维度是2的幂，这样可以利用库的优化。

4. **执行变换**：调用`fftw_execute`来实际计算变换。

5. **检查错误**：在执行后，用`fftw_error_code`检查是否有错误。

6. **处理结果**：根据需要对结果进行存储或进一步处理。

以下是一个简单的单通道一维DFT的例子：

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

void fft_example(int n) {
    double *in = fftw_malloc(sizeof(double) * n);
    // 初始化输入数据...
    fftw_complex *out = fftw_malloc(sizeof(fftw_complex) * n);

    fftw_plan plan = fftw_plan_dft_r2c_1d(n, in, out, FFTW_ESTIMATE);
    fftw_execute(plan);
    fftw_destroy_plan(plan);

    // 处理输出...
    fftw_free(in);
    fftw_free(out);
}

int main() {
    int n = 8; // 一个常见的示例大小
    fft_example(n);
    return 0;
}