用c语言蝶形变换实现FFT

蝶形变换（Butterfly Operation）是实现快速傅里叶变换（FFT）的重要步骤之一。下面是使用C语言实现FFT蝶形变换的示例代码：

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

void butterfly(float *real, float *imag, int n, int m)
{
    int i, j, k;
    int size = 1 << n;
    float *w_real, *w_imag;
    float temp_real, temp_imag;
    float angle;

    // 分配存储旋转因子的数组
    w_real = (float *)malloc(sizeof(float) * size / 2);
    w_imag = (float *)malloc(sizeof(float) * size / 2);

    // 计算旋转因子
    for (i = 0; i < size / 2; i++) {
        angle = -2 * M_PI * i / size;
        w_real[i] = cos(angle);
        w_imag[i] = sin(angle);
    }

    // 蝶形变换
    for (i = 0; i < m; i++) {
        for (j = 0; j < size / 2; j++) {
            for (k = 0; k < (1 << (m - i - 1)); k++) {
                temp_real = real[j * (1 << (m - i)) + k];
                temp_imag = imag[j * (1 << (m - i)) + k];

                real[j * (1 << (m - i)) + k] = temp_real + real[j * (1 << (m - i)) + k + (1 << (m - i - 1))] * w_real[j * (1 << (m - i - 1))] - imag[j * (1 << (m - i)) + k + (1 << (m - i - 1))] * w_imag[j * (1 << (m - i - 1))];
                imag[j * (1 << (m - i)) + k] = temp_imag + imag[j * (1 << (m - i)) + k + (1 << (m - i - 1))] * w_real[j * (1 << (m - i - 1))] + real[j * (1 << (m - i)) + k + (1 << (m - i - 1))] * w_imag[j * (1 << (m - i - 1))];
            }
        }
    }

    // 释放内存
    free(w_real);
    free(w_imag);
}

int main()
{
    int n, m;
    int size;
    float *real, *imag;
    int i;

    printf("请输入FFT的阶数n：");
    scanf("%d", &n);

    size = 1 << n;
    m = n;

    // 分配存储实部和虚部的数组
    real = (float *)malloc(sizeof(float) * size);
    imag = (float *)malloc(sizeof(float) * size);

    printf("请输入FFT输入序列的实部和虚部：\n");
    for (i = 0; i < size; i++) {
        scanf("%f %f", &real[i], &imag[i]);
    }

    // 调用蝶形变换函数
    butterfly(real, imag, n, m);

    printf("FFT变换结果为：\n");
    for (i = 0; i < size; i++) {
        printf("%.2f + %.2fi\n", real[i], imag[i]);
    }

    // 释放内存
    free(real);
    free(imag);

    return 0;
}

以上代码实现了一个简单的FFT蝶形变换，并输出变换结果。你可以根据需要进行修改和扩展。希望对你有帮助！