C语言实现傅里叶变换算法详解

傅里叶变换是一种将信号从时域转换到频域的算法，可以用于信号处理、图像处理等领域。下面是一个用C语言实现傅里叶变换的例子。

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

#define PI 3.14159265358979323846

// 复数结构体
typedef struct {
    double re;  // 实部
    double im;  // 虚部
} complex;

// 求两个复数的乘积
complex c_mul(complex a, complex b) {
    complex c;
    c.re = a.re * b.re - a.im * b.im;
    c.im = a.re * b.im + a.im * b.re;
    return c;
}

// 求两个复数的和
complex c_add(complex a, complex b) {
    complex c;
    c.re = a.re + b.re;
    c.im = a.im + b.im;
    return c;
}

// 傅里叶变换实现
void fft(complex *x, int n) {
    if (n <= 1) {
        return;
    }
    // 分别对偶数项和奇数项做傅里叶变换
    complex even[n/2], odd[n/2];
    for (int i = 0; i < n/2; i++) {
        even[i] = x[2*i];
        odd[i] = x[2*i+1];
    }
    fft(even, n/2);
    fft(odd, n/2);
    // 计算每个频率分量的值
    for (int k = 0; k < n/2; k++) {
        complex t = c_mul(odd[k], (complex){cos(-2*PI*k/n), sin(-2*PI*k/n)});
        x[k] = c_add(even[k], t);
        x[k+n/2] = c_add(even[k], c_mul(t, (complex){1, -1}));
    }
}

int main() {
    int n = 8;
    complex x[n];
    // 初始化输入信号
    for (int i = 0; i < n; i++) {
        x[i].re = sin(2*PI*i/8);
        x[i].im = 0;
    }
    // 傅里叶变换
    fft(x, n);
    // 输出频域表示
    for (int i = 0; i < n; i++) {
        printf('%g + %gi
', x[i].re, x[i].im);
    }
    return 0;
}

这个例子实现了一个递归的傅里叶变换算法，通过对输入信号逐层分治，最终计算出每个频率分量的值。在实际使用中，还需要对结果进行归一化和进行逆变换等操作。