fft2.cpp

基2 fft的基本原理

#include "fft2.h"


void reverse(complex *X,int N)
{
    //complex *X1=new complex [N];
    int i=0,j=0,k=0;
    complex temp(0,0);
    for(i=0;i<N-1;i++)
    {
        if(i<j)
        {
           temp=X[i];
           X[i]=X[j];
           X[j]=temp;
        }
        k=N>>1;
        while(k<=j)
        {
            j-=k;
            k>>=1;
        }
        j+=k;
    }
}


void fft2(complex *X,int N)
{
    complex WNR(1,1);
    int i=0,r=0,k=0,m=0,M=0;
    M=(int)log2(N);
    reverse(X,N);
    for(m=0;m<M;m++)
    {
        k=(int)pow(2.0,m);
        for(r=0;r<k;r++)
        {
            complex temp(cos(r*PI/k),-sin(r*PI/k));
            for(i=r;i<N;i+=k*2)
            {
                WNR=X[i+k]*temp;
                X[i+k]=X[i]-WNR;
                X[i]=X[i]+WNR;
            }
        }
    }
}