c语言fft变换底层代码 加注释的

下面是一个简单的C语言FFT变换的底层代码，我加上了注释：

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535897932384626433832795

// 计算Wn的实部和虚部
void calcWn(int k, int n, double *realWn, double *imagWn)
{
    *realWn = cos(2 * PI * k / n);
    *imagWn = -sin(2 * PI * k / n);
}

// 计算FFT
void FFT(double *real, double *imag, int n)
{
    int i, j, k, m;
    double tempr, tempi, realWn, imagWn;

    // 倒位置置换
    j = 0;
    for (i = 0; i < n; i++)
    {
        if (j > i)
        {
            // 交换实部
            tempr = real[j];
            real[j] = real[i];
            real[i] = tempr;
            // 交换虚部
            tempi = imag[j];
            imag[j] = imag[i];
            imag[i] = tempi;
        }
        // 计算下一个j，用于交换下一组复数
        k = n / 2;
        while (k <= j)
        {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    // 计算FFT
    m = 1;
    while (m < n)
    {
        // 计算Wn的实部和虚部
        calcWn(0, 2 * m, &realWn, &imagWn);
        // 初始化旋转因子
        double tempr = 1.0, tempi = 0.0;
        // 对每个分组进行计算
        for (k = 0; k < n; k += 2 * m)
        {
            for (i = k, j = i + m; j < k + 2 * m; i++, j++)
            {
                // 计算蝴蝶变换
                double t1 = tempr * real[j] - tempi * imag[j];
                double t2 = tempr * imag[j] + tempi * real[j];
                real[j] = real[i] - t1;
                imag[j] = imag[i] - t2;
                real[i] += t1;
                imag[i] += t2;
            }
            // 更新旋转因子
            double tempreal = tempr * realWn - tempi * imagWn;
            tempi = tempr * imagWn + tempi * realWn;
            tempr = tempreal;
        }
        m *= 2;
    }
}

int main()
{
    double real[8] = {0.707, 1.0, 0.707, 0.0, -0.707, -1.0, -0.707, 0.0};
    double imag[8] = {0.0};
    FFT(real, imag, 8);
    for (int i = 0; i < 8; i++)
    {
        printf("real[%d] = %f, imag[%d] = %f\n", i, real[i], i, imag[i]);
    }
    return 0;
}

在这段代码中，calcWn函数用于计算旋转因子Wn的实部和虚部，FFT函数用于进行FFT变换，main函数用于测试。

在FFT函数中，首先进行了倒位置置换，然后进行了FFT变换。其中，倒位置置换用于将输入序列中的数据重新排列，以便进行后续的FFT计算；FFT变换使用了蝴蝶变换算法，对每个分组进行计算，更新旋转因子并计算蝴蝶变换，最终得到变换后的结果。