关于FFT运算时间的问题

yijinxiaoyou

我用的是下面的整点算法   计算64点花费400us的时间  计算256时居然涨到2ms（理论上是按log2N 64点是400us 256点应该是500us左右）可这函数的运算时间怎么按2N增长啊 是我那里弄错了吗？ 计算结果什么的都没问题 看这算法感觉也没什么问题但时间涨的


/********************************************************************************
函数原型：void fft(struct compx *xin,unsigned char M,unsigned short FFT_N )
函数功能：对输入的复数组进行快速傅里叶变换（FFT）
输入参数：*xin复数结构体组的首地址指针，struct型 M表示蝶形的级数 FFT_N表示点数
输出参数：无
********************************************************************************/
void fft(struct compx *xin, unsigned char M, unsigned short FFT_N)
{
    int TempReal1, TempImag1, TempReal2, TempImag2;
    unsigned short k, i, j, z;
    unsigned short Butterfly_NoPerColumn;                        //每级蝶形的蝶形组数
    unsigned short Butterfly_NoOfGroup;                        //蝶形组的第几组
    unsigned short Butterfly_NoPerGroup;                        //蝶形组的第几个蝶形
    unsigned short ButterflyIndex1, ButterflyIndex2, P, J;
    unsigned char L;

    z = FFT_N / 2;                                                      //变址运算，即把自然顺序变成倒位序，采用雷德算法
    for (i = 0, j = 0; i<FFT_N - 1; i++)
    {
        if (i<j)                                                    //如果i<j,即进行变址 i=j说明是它本身，i>j说明前面已经
        {                                                                      //变换过了，不许再变化
            TempReal1 = xin[j].real;                 //注意这里一般是实数 有虚数部分 设置成结合体
            xin[j].real = xin.real;
            xin.real = TempReal1;
        }
        k = z;                                                       //求j的下一个倒位序
        while (k <= j)                                                 //如果k<=j,表示j的最高位为1   
        {
            j = j - k;                                                    //把最高位变成0
            k = k / 2;                                                    //k/2，比较次高位，依次类推，逐个比较，直到某个位为0，通过下面那句j=j+k使其变为1
        }
        j = j + k;                                                      //求下一个反序号，如果是0，则把0改为1
    }
    /*第L级蝶形(M)第Butterfly_NoOfGroup组(Butterfly_NoPerColumn)第J个蝶形(Butterfly_NoPerGroup)*******/
    /*蝶形的组数以2的倍数递减Butterfly_NoPerColumn，每组中蝶形的个数以2的倍数递增Butterfly_NoPerGroup*/
    Butterfly_NoPerColumn = FFT_N;                                //在计算蝶形时，每L列的蝶形组数,一共有M列，
    Butterfly_NoPerGroup = 1;                                    //每组蝶形中蝶形的个数
    for (L = 0; L < M; L++)                                 //蝶形的阶数(0,1,2.....M-1)
    {
        Butterfly_NoPerColumn >>= 1;                           //蝶形组数     假如N=8，则(4,2,1)
        //第L级蝶形 第Butterfly_NoOfGroup组    （0,1，....Butterfly_NoOfGroup-1）                    
        for (Butterfly_NoOfGroup = 0; Butterfly_NoOfGroup < Butterfly_NoPerColumn; Butterfly_NoOfGroup++)
        {
            for (J = 0; J < Butterfly_NoPerGroup; J++)        //第 Butterfly_NoOfGroup 组中的第J个
            {                                                   //第 ButterflyIndex1 和第 ButterflyIndex2 个元素作蝶形运算,WNC
                ButterflyIndex1 = ((Butterfly_NoOfGroup * Butterfly_NoPerGroup) << 1) + J;//(0,2,4,6)(0,1,4,5)(0,1,2,3)
                ButterflyIndex2 = ButterflyIndex1 + Butterfly_NoPerGroup;//两个要做蝶形运算的数相距Butterfly_NoPerGroup                                                //(ge=1,2,4)
                P = J * Butterfly_NoPerColumn;                //这里相当于P=J*2^(M-L),做了一个换算下标都是N (0,0,0,0)(0,2,0,2)(0,1,2,3)
                //计算和转换因子乘积
                TempReal2 = (xin[ButterflyIndex2].real * costab[P] + xin[ButterflyIndex2].imag * sintab[P]) >> 15;
                TempImag2 = (xin[ButterflyIndex2].imag * costab[P] - xin[ButterflyIndex2].real * sintab[P]) >> 15;
                TempReal1 = xin[ButterflyIndex1].real;
                TempImag1 = xin[ButterflyIndex1].imag;
                //蝶形运算
                xin[ButterflyIndex1].real = TempReal1 + TempReal2;
                xin[ButterflyIndex1].imag = TempImag1 + TempImag2;
                xin[ButterflyIndex2].real = TempReal1 - TempReal2;
                xin[ButterflyIndex2].imag = TempImag1 - TempImag2;

            }
        }
        Butterfly_NoPerGroup <<= 1;                            //一组中蝶形的个数(1,2,4)
    }
}

eric2013

蝶形运算时间有专门讲解这个的，以前上学的时候有搞过，现在没什么影响了，网上搜些资料搞下，对比下总的蝶形运算次数就行