基2fft算法的C语言实现详细注释

以下是基于C语言实现的基2FFT算法代码，注释详细解释了算法的实现过程：

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

#define PI 3.14159265358979323846

// 基2FFT算法，输入为序列x，输出为序列y
void fft2(double *x, double *y, int n)
{
    int i, k;
    double *xe, *xo, *ye, *yo, *ae, *ao, *be, *bo, *we, *wo;
    double t, re, im;

    if (n == 1) { // 递归结束条件：序列长度为1
        y[0] = x[0];
        return;
    }

    // 分解偶数项和奇数项
    xe = (double *)malloc(n/2 * sizeof(double));
    xo = (double *)malloc(n/2 * sizeof(double));
    for (i = 0; i < n/2; i++) {
        xe[i] = x[2*i];
        xo[i] = x[2*i+1];
    }

    // 递归计算偶数项和奇数项的FFT
    ye = (double *)malloc(n/2 * sizeof(double));
    yo = (double *)malloc(n/2 * sizeof(double));
    fft2(xe, ye, n/2);
    fft2(xo, yo, n/2);

    // 计算旋转因子
    we = (double *)malloc(n/2 * sizeof(double));
    wo = (double *)malloc(n/2 * sizeof(double));
    for (i = 0; i < n/2; i++) {
        t = -2 * PI * i / n;
        we[i] = cos(t) + sin(t) * I;
        wo[i] = cos(t) - sin(t) * I;
    }

    // 合并结果
    ae = (double *)malloc(n/2 * sizeof(double));
    ao = (double *)malloc(n/2 * sizeof(double));
    be = (double *)malloc(n/2 * sizeof(double));
    bo = (double *)malloc(n/2 * sizeof(double));
    for (k = 0; k < n/2; k++) {
        ae[k] = creal(ye[k]);
        ao[k] = cimag(yo[k]);
        be[k] = creal(ye[k+n/2]);
        bo[k] = cimag(yo[k+n/2]);
        re = ae[k] + we[k] * ao[k];
        im = be[k] + wo[k] * bo[k];
        y[k] = re + im * I;
        y[k+n/2] = re - im * I;
    }

    // 释放内存
    free(xe);
    free(xo);
    free(ye);
    free(yo);
    free(we);
    free(wo);
    free(ae);
    free(ao);
    free(be);
    free(bo);
}

int main()
{
    int n = 8; // 序列长度
    double x[] = {1, 2, 3, 4, 4, 3, 2, 1}; // 输入序列
    double y[n]; // 输出序列
    int i;

    printf("Input sequence:\n");
    for (i = 0; i < n; i++) {
        printf("%f ", x[i]);
    }
    printf("\n");

    fft2(x, y, n);

    printf("Output sequence:\n");
    for (i = 0; i < n; i++) {
        printf("%f+j%f ", creal(y[i]), cimag(y[i]));
    }
    printf("\n");

    return 0;
}

在这个代码中，我们定义了一个名为fft2的函数来实现基2FFT算法。输入为序列x，输出为序列y，序列长度为n。

首先，我们检查递归结束条件：序列长度为1。如果是这种情况，我们将x[0]复制到y[0]中，并直接返回。

否则，我们将输入序列x分为偶数项xe和奇数项xo，并递归计算xe和xo的FFT，得到偶数项FFT ye 和奇数项FFT yo。

接下来，我们计算旋转因子we和wo，用于合并结果。这些因子通过欧拉公式计算得出。

最后，我们将结果合并到输出序列y中，通过线性组合得到FFT结果。在这个过程中，我们使用了旋转因子we和wo以及一些临时变量ae、ao、be和bo来计算FFT结果。

最后，我们释放了分配的内存，输出得到的FFT结果。

注意，这里使用了C语言的复数类型（double complex），这个类型包含实部和虚部两个部分。