快速傅立叶变换（FFT）是一种高效的算法，用于计算离散傅立叶变换（DFT）。在 C++ 中实现 FFT 可以从头开始编写，也可以使用已有的库来简化实现。以下是一个用纯 C++ 实现 FFT 的示例，适合对 FFT 原理有更深了解并希望实现自定义功能的场景。

1. 纯 C++ 实现 FFT

以下是一个使用递归方法实现一维 FFT 的示例代码：

#include <iostream>
#include <complex>
#include <vector>
#include <cmath>

const double PI = 3.141592653589793238460;

// 计算输入大小是否为2的幂
bool isPowerOfTwo(int n) {
    return n && (!(n & (n - 1)));
}

// FFT 递归实现
void fft(std::vector<std::complex<double>>& a) {
    int n = a.size();
    if (n <= 1)
        return;

    // 检查 n 是否为 2 的幂
    if (!isPowerOfTwo(n)) {
        throw std::runtime_error("Input size must be a power of 2");
    }

    // 将输入数组分成偶数和奇数的两个子数组
    std::vector<std::complex<double>> even(n / 2);
    std::vector<std::complex<double>> odd(n / 2);

    for (int i = 0; i < n / 2; i++) {
        even[i] = a[i * 2];
        odd[i] = a[i * 2 + 1];
    }

    // 递归调用 FFT
    fft(even);
    fft(odd);

    for (int k = 0; k < n / 2; k++) {
        std::complex<double> t = std::polar(1.0, -2 * PI * k / n) * odd[k];
        a[k] = even[k] + t;
        a[k + n / 2] = even[k] - t;
    }
}

int main() {
    // 示例输入数据，长度为8，必须是2的幂
    std::vector<std::complex<double>> data = {
        1, 1, 1, 1, 0, 0, 0, 0
    };

    // 打印输入数据
    std::cout << "Input:" << std::endl;
    for (const auto& c : data) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    // 计算 FFT
    fft(data);

    // 打印输出数据
    std::cout << "Output:" << std::endl;
    for (const auto& c : data) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码说明：

1. 递归方法：

   • 该实现使用递归分治方法计算 FFT，将问题分解为处理偶数和奇数索引的子问题。
   • 递归地计算每个子问题的 FFT，然后将它们组合起来得到最终结果。

2. 输入检查：

   • 输入向量的大小必须是 2 的幂。如果输入大小不是 2 的幂，FFT 将无法正确执行。

3. 复数处理：

   • FFT 计算涉及复数的操作，C++ 标准库提供了 std::complex 类型来处理复数运算。

4. 极坐标转换：

   • std::polar(1.0, -2 * PI * k / n) 用于计算复数指数，产生旋转因子 Wn。

2. 使用 FFTW 库（推荐）

虽然手动实现 FFT 可以帮助理解算法，但在实际项目中，建议使用经过高度优化的 FFT 库，如 FFTW。FFTW 是一个高性能的 C 库，支持多种平台。

使用 FFTW 的示例：

首先，需要安装 FFTW 库。你可以通过包管理器安装它（如 apt-get 或 brew），或者从 FFTW官网 下载并编译。

#include <iostream>
#include <complex>
#include <fftw3.h>

int main() {
    const int N = 8;  // 输入大小，必须为2的幂

    // 定义输入和输出数组
    fftw_complex in[N], out[N];

    // 初始化输入数组
    for (int i = 0; i < N; ++i) {
        in[i][0] = i % 2;  // 实部
        in[i][1] = 0;      // 虚部
    }

    // 创建计划
    fftw_plan plan = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);

    // 执行 FFT
    fftw_execute(plan);

    // 打印输出
    std::cout << "Output:" << std::endl;
    for (int i = 0; i < N; ++i) {
        std::cout << "(" << out[i][0] << ", " << out[i][1] << ") ";
    }
    std::cout << std::endl;

    // 释放计划
    fftw_destroy_plan(plan);

    return 0;
}

代码说明：

1. fftw_complex：

   • FFTW 使用 fftw_complex 类型来表示复数。每个复数由两个 double 数组成：实部和虚部。

2. fftw_plan：

   • fftw_plan 是 FFTW 的核心数据结构，表示一个 FFT 计算的计划。你可以使用 fftw_plan_dft_1d 创建一个 1D FFT 计划。

3. 执行 FFT：

   • 使用 fftw_execute 执行 FFT 计划，该函数将输入数组 in 转换为输出数组 out。

4. 释放资源：

   • 使用 fftw_destroy_plan 释放创建的 FFT 计划，以防止内存泄漏。

总结

• 纯 C++ 实现：适合学习和理解 FFT 的原理，但在性能和功能上不如专门的库。
• FFTW 库：是一个经过高度优化的 FFT 库，支持多种维度和数据类型的 FFT。推荐在实际项目中使用 FFTW，它提供了更高的性能和灵活性。

无论你选择自己实现还是使用现有的库，FFT 都是一个非常有用的工具，在信号处理、音频分析、图像处理等领域有广泛应用。