快速傅里叶变换(FFT)c语言实现

基���原理在这里就不多讲了，可以看看其他高浏览量的博文，这篇文章针对c语言的实现

复数运算算子

        我们都知道C语言本身是没有复数运算的，很多DSP、单片机要用到也没有开源库可以使用复数运算，针对FFT在硬件上运行只能手动从底层开始

定义复数类型

        这里用最简单高效的方法——结构体

struct complex{    double real;    double image;};

复数加法

struct complex complex_add(struct complex c1,struct complex c2)     //复数加法{    struct complex p;    p.real = c1.real + c2.real;    p.image = c1.image + c2.image;    return p;}

复数减法

struct complex complex_sub(struct complex c1,struct complex c2)     //复数减{    struct complex p;    p.real = c1.real - c2.real;    p.image = c1.image - c2.image;    return p;}

复数乘法

struct complex complex_multi(struct complex c1,struct complex c2)  //复数乘法{    struct complex c3;    c3.real=c1.real*c2.real - c1.image *c2.image;    c3.image = c2.real* c1.image + c1.real*c2.image;    return c3;};

复数取模

double mold_length(struct complex c)        //幅度{    return sqrt(c.real * c.real + c.image * c.image);};

旋转因子

    教科书上的旋转因子一般长成这样把它变成可以运算的形式   

struct complex rotation_factor(int N,int n,int k)       //旋转因子{    struct complex w;    w.real = cos(2* PI * n * k /N);    w.image = - sin(2* PI * n * k /N);        //这里的PI是宏定义    return w;}

反位序操作

        我用的方法是基于时间抽取的基2FFT （DIT-FFT）所以开始进入FFT之前要先把序列顺序取反位序

int reverse_num(int l,int oringin_num)          //反位序{    int q=0,m=0;    for(int k=l-1;k>=0;k--)    {        q = oringin_num % 2;        m += q*(1