我自己的一些详细标注，有利于深入了解FFT，后面附加几位网友对FFT的理解及源代码，让广大朋友更迅速的掌握FFT
#include "DSP281x_Device.h"    // DSP281x Headerfile Include File，添加所有头文件
#include "DSP281x_Examples.h"  // DSP281x Examples Include File，条件编译而已
#include "f2812a.h"  //一些变量的宏定义而已
#include"math.h"
#define PI 3.1415926  //前变后常
#define SAMPLENUMBER 128
//#define SAMPLENUMBER 512
void InitForFFT();
void MakeWave();
//void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER]);
int INPUT[SAMPLENUMBER],DATA[SAMPLENUMBER];
float fWaveR[SAMPLENUMBER],fWaveI[SAMPLENUMBER],w[SAMPLENUMBER];
float sin_tab[SAMPLENUMBER],cos_tab[SAMPLENUMBER];
//逐级计算FFT，一级一级递推
void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER])
{
    int x0,x1,x2,x3,x4,x5,x6,xx;
    int i,j,k,b,p,L;
    float TR,TI,temp;
   
    /********** following code invert sequence ************///倒序
    for ( i=0;i<SAMPLENUMBER;i++ )//就是码位倒置嘛，二进制各个位独立出来再反向
    {                            //128七位二进制表示，/号代表右移嘛
        x0=x1=x2=x3=x4=x5=x6=0;
        x0=i&0x01; x1=(i/2)&0x01; x2=(i/4)&0x01; x3=(i/8)&0x01;x4=(i/16)&0x01; x5=(i/32)&0x01; x6=(i/64)&0x01;
        xx=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6;//最低位，最高位反过来
        dataI[xx]=dataR[i];
    }
    for ( i=0;i<SAMPLENUMBER;i++ )
    {
        dataR[i]=dataI[i]; dataI[i]=0; //对应过来
    }
    /************** following code FFT *******************/
    for ( L=1;L<=7;L++ )
    { /* for(1) */
        b=1; i=L-1;/* b的意义非常重大,b表示当前层不同旋转因子的个数  */
        while ( i>0 )
        {
            b=b*2; i--;
        } /* b= 2^(L-1) */
        for ( j=0;j<=b-1;j++ ) /* for (2) */
        {
            p=1; i=7-L;
            while ( i>0 ) /* p=pow(2,7-L)*j; */
            {
                p=p*2; i--;
            }
            p=p*j;
            for ( k=j;k<128;k=k+2*b ) /* for (3) */
            {
                TR=dataR[k]; TI=dataI[k]; temp=dataR[k+b];
                dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+dataI[k+b]*sin_tab[p];
                dataI[k]=dataI[k]-dataR[k+b]*sin_tab[p]+dataI[k+b]*cos_tab[p];
                dataR[k+b]=TR-dataR[k+b]*cos_tab[p]-dataI[k+b]*sin_tab[p];
                dataI[k+b]=TI+temp*sin_tab[p]-dataI[k+b]*cos_tab[p];  //递推嘛，防止立马调用结果，
            } /* END for (3) */                                      //引入一个中间变量存原始值，
        } /* END for (2) */                                          //防止上一步对下一步的影响
    } /* END for (1) */
    for ( i=0;i<SAMPLENUMBER/2;i++ )  //对称性，前半部分即可
    {
        w[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i]);
    }
} /* END FFT */
main()
{
    int i;
   
    InitForFFT();
    MakeWave();
    for ( i=0;i<SAMPLENUMBER;i++ )
    {
        fWaveR[i]=INPUT[i];
        fWaveI[i]=0.0f;
        w[i]=0.0f;
    }
    FFT(fWaveR,fWaveI);//输入波形进行FFT变换,此处引入起始实参即可递推下去
    for ( i=0;i<SAMPLENUMBER;i++ )
    {
        DATA[i]=w[i];//变换后的波形转换到输出接口
    }
    while ( 1 );    // break point
}
//旋转因子事先初始化好，方便调用
void InitForFFT()
{
    int i;
   
    for ( i=0;i<SAMPLENUMBER;i++ )
    {
        sin_tab[i]=sin(PI*2*i/SAMPLENUMBER);
        cos_tab[i]=cos(PI*2*i/SAMPLENUMBER);//旋转因子事先初始化好，方便调用
    }
}
//利用这个，确实能产生各种各样的谐波
void MakeWave()  //利用这个，确实能产生各种各样的谐波
{
    int i;
   
    for ( i=0;i<SAMPLENUMBER;i++ )//1024是相应的幅值嘛，只要弄出个基波，以之为标准即可
    {
        INPUT[i]=sin(PI*2*i/SAMPLENUMBER)*1024
                +sin(PI*2*i/SAMPLENUMBER*3)*1024/3
                +sin(PI*2*i/SAMPLENUMBER*5)*1024/5
                +sin(PI*2*i/SAMPLENUMBER*7)*1024/7
                  +sin(PI*2*i/SAMPLENUMBER*9)*1024/9;
           
   
    //INPUT[i]=sin(PI*2*i/SAMPLENUMBER*3)*1024;
   
    }
}
FFT原理及实现(Radix-2)
 
哈! 经过连续几个晚上的奋战, 终于弄懂了FFT推导过程及实现!  Happy☺
基2 FFT总的思想是将输入信号对半分割, 再对半分割, 再再对半分割(以下省略10000个再再...☺) 直至分割到2点.
 
两点DFT简化
假设输入为x[0],x[1]; 输出为X[0],X[1].  伪代码如下 :
// ------------------------------------------------------------------
#define    N      2
#define    PI     3.1415926
 
// ------------------------------------------------------------------
int i, j
for(i=0, X[i]=0.0; i<N; i++)
    for(j=0; j<N; j++)
       X[i] += x[j] * ( cos(2*PI*i*j/N) - sin(2*PI*i*j/N) );
     
注意到(我想Audio编解码很多时候都是对cos,sin进行优化!)
 
j=0
j=1
 
i=0
cos  1
sin  0
 
tw   1
cos  1
sin  0
 
tw   1
 
i=1
cos  1
Sin  0
 
tw   1
cos  -1
sin  0
 
tw   -1
 
X[0] =   x[0]*(1-0) + x[1]*(1-0)  = x[0] + 1*x[1];
X[1] =   x[0]*(1-0) + x[1]*(-1-0) = x[0] - 1*x[1];
这就是单个2点蝶形算法.
 
FFT源代码1080p在线实现流程图分析(N=8, 以8点信号为例)
FFT implementation of an 8-point DFT as two 4-point DFTs and four 2-point DFTs
8点FFT流程图(Layer表示层, gr表示当前层的颗粒)
 
 
下面以LayerI为例.
LayerI部分, 具有4个颗粒, 每个颗粒2个输入
(注意2个输入的来源, 由时域信号友情提供, 感谢感谢☺)
我们将输入x[k]分为两部分x_r[k], x_i[k]. 具有实部和虚部, 时域信号本没有虚部的, 因此可以让x_i[k]为0. 那么为什么还要画蛇添足分为实部和虚部呢? 这是因为LayerII, LayerIII的输入是复数, 为了编码统一而强行分的.当然你编码时可以判断当前层是否为1来决定是否分. 但是我想每个人最后都会倾向分的.
旋转因子 tw = cos(2*PI*k/N)-j*sin(2*PI*k/N); 也可以分为实部和虚部, 令其为tw_r, tw_i;
则tw = tw_r - j*tw_i;
 
X[k] = (x_r[k] + j*x_i[k]) + (tw_r–j*tw_i) * (x_r[k+N/2]+j*x_i[k+N/2])
则
           X_R[k] = x_r[k] + tw_r*x_r[k+N/2] + tw_i*x_i[k+N/2];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。