快速傅里叶变换的理解及C++实现

（看不懂很正常，我也没搞得很明白，就数学老师提了一嘴我就多看了两眼而已（bushi

引子：（粘的

在数字信号处理领域，快速傅里叶变换（Fast Fourier Transform，FFT）是一种高效计算离散傅里叶变换（Discrete Fourier Transform，DFT）的算法。它能够迅速将一个N维的离散信号序列转换为其频域表示，广泛应用于信号分析、图像处理和数字通信等领域。

基本理论

先说DFT吧

DFT是将一个N维的离散信号序列转换为其频域表示的算法。DFT的矩阵向量陈述形式为：

$$ X = Fx $$

在这里面呢，$x$是输入信号序列，$F$是一个$N×N$的傅里叶变换矩阵，$X$是变换后的频域表示。在DFT计算中，直接使用矩阵向量乘法计算复杂度为$O(N^2)$，当$N$很大时，计算代价可想而知。

接下来说FFT:

FFT是一种高效计算DFT的算法（至少炸的不是很惨），它通过利用DFT矩阵的对称性和周期性，将一个N维的DFT计算分解为多个规模较小的DFT计算。FFT的核心思想是将信号分解为偶数位置上的部分和奇数位置上的部分，然后递归地将这两部分分别再次分解，最后合并所有分解的结果得到最终的频域表示。其中最常用的FFT算法为基于蝶形运算的Cooley-Tukey算法（什么乱七八糟的名字，其实记住一个傅里叶就行），其计算复杂度为$O(N logN)$。

FFT的个人理解（

使用FFT进行DFT计算时，我们可以将其理解为通过乘以傅里叶变换矩阵F来完成信号变换的过程。这里，傅里叶变换矩阵F的每一个元素表示频率的振幅和相位的组合。通过将输入信号序列与傅里叶变换矩阵F相乘，我们可以得到变换后的频域表示。
（感觉说的好乱七八糟）

C++code

一定要记得FFTW！！！！！！！！！！！！！！！！

#include <fftw3.h>

int main() {
    int N = 8; // 输入信号序列的长度
    fftw_complex *in, *out;
    fftw_plan p;

    // 分配内存
    in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
    out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);

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

    // 设置输入信号
    for (int i = 0; i < N; i++) {
        in[i][0] = i; // 实部
        in[i][1] = 0; // 虚部
    }

    // 执行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);
    fftw_free(in);
    fftw_free(out);

    return 0;
}

一定要记得正确安装和链接FFTW库！！！！！

end：

祝各位Rp++