傅里叶变换 蝶形算法 c语言实现

傅里叶变换是一种重要的数学工具，可以将时域（时间）上的信号转换到频域（频率）上。通过傅里叶变换，我们可以分析一个信号中包含的不同频率成分，常用于信号处理、图像处理、通信等领域。

蝶形算法是一种计算傅里叶变换的常用算法，它采用迭代的方式实现了快速计算傅里叶变换的过程。蝶形算法由于其高效性和通用性被广泛应用。

C语言中可以使用FFT库实现傅里叶变换，例如fftw库。同时也可以自己编写代码实现，以下是一个简单的蝶形算法实现代码片段：

#include <math.h>

void FFT(int n, double *x, double *y)
{
    int i, j, k, n1, n2;
    double c, s, t1, t2;

    for (i = 0, j = 0; i < n; i++) {
        if (j > i) {
            t1 = x[j];
            t2 = y[j];
            x[j] = x[i];
            y[j] = y[i];
            x[i] = t1;
            y[i] = t2;
        }
        k = n;
        while (j >= k) {
            j -= k;
            k >>= 1;
        }
        j += k;
    }
    for (i = 1; i < n; i <<= 1) {
        n1 = i << 1;
        n2 = n1 << 1;
        for (j = 0; j < i; j++) {
            c = cos(M_PI * j / i);
            s = sin(M_PI * j / i);
            for (k = j; k < n; k += n2) {
                t1 = c * x[k + i] - s * y[k + i];
                t2 = s * x[k + i] + c * y[k + i];
                x[k + i] = x[k] - t1;
                y[k + i] = y[k] - t2;
                x[k] += t1;
                y[k] += t2;
            }
        }
    }
}