list.7.txt

来自「This archive contains circuit diagram an」· 文本 代码 · 共 40 行

//*****************************************
//  FFT function
//  x - input N complex values
//  X - output N complex values
//*****************************************
void FFT(cplx *x, cplx *X)
{
        int stc;        //stages counter
        int blc;        //blocks of butterflys in stage counter
        int bfc;        //butterflys in block counter

        int NumOfStages;        //Number of stages = log2(N)
        int NumOfBlocks;        //in stage
        int NumOfButterflys;    //in block

        //Determining number of stages - counting log2(N)
        for(NumOfStages=0;NumOfStages<32;NumOfStages++)
                if(N==(1<<NumOfStages))
                        break;

        //Copying input data to output buffer
        //to perform in-place computing
        for(stc=0;stc<N;stc++)
                X[stc]=x[BitShift(stc,NumOfStages-1)];

        //Main FFT loop
        for(stc=0;stc<NumOfStages;stc++)
        {
                NumOfButterflys=(1<<stc);
				NumOfBlocks=N>>(stc+1);

                for(blc=0;blc<NumOfBlocks;blc++)
                {
                        int base=(1<<(stc+1))*blc;
                        for(bfc=0;bfc<NumOfButterflys;bfc++)
                                Butterfly(X+base+bfc,X+base+bfc+NumOfButterflys,NumOfBlocks*bfc);
                }
        }
}