FFT最详细的源代码和解释.docx
- 文档编号:16083264
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:56
- 大小:169.88KB
FFT最详细的源代码和解释.docx
《FFT最详细的源代码和解释.docx》由会员分享,可在线阅读,更多相关《FFT最详细的源代码和解释.docx(56页珍藏版)》请在冰点文库上搜索。
FFT最详细的源代码和解释
我自己的一些详细标注,有利于深入了解FFT,后面附加几位网友对FFT的理解及源代码,让广大朋友更迅速的掌握FFT
#include"DSP281x_Device.h"//DSP281xHeaderfileIncludeFile,添加所有头文件
#include"DSP281x_Examples.h"//DSP281xExamplesIncludeFile,条件编译而已
#include"f2812a.h"//一些变量的宏定义而已
#include"math.h"
#definePI3.1415926//前变后常
#defineSAMPLENUMBER128
//#defineSAMPLENUMBER512
voidInitForFFT();
voidMakeWave();
//voidFFT(floatdataR[SAMPLENUMBER],floatdataI[SAMPLENUMBER]);
intINPUT[SAMPLENUMBER],DATA[SAMPLENUMBER];
floatfWaveR[SAMPLENUMBER],fWaveI[SAMPLENUMBER],w[SAMPLENUMBER];
floatsin_tab[SAMPLENUMBER],cos_tab[SAMPLENUMBER];
//逐级计算FFT,一级一级递推
voidFFT(floatdataR[SAMPLENUMBER],floatdataI[SAMPLENUMBER])
{
intx0,x1,x2,x3,x4,x5,x6,xx;
inti,j,k,b,p,L;
floatTR,TI,temp;
/**********followingcodeinvertsequence************///倒序
for(i=0;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 { dataR[i]=dataI[i];dataI[i]=0;//对应过来 } /**************followingcodeFFT*******************/ 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];//递推嘛,防止立马调用结果, }/*ENDfor(3)*///引入一个中间变量存原始值, }/*ENDfor (2)*///防止上一步对下一步的影响 }/*ENDfor (1)*/ for(i=0;i { w[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i]); } }/*ENDFFT*/ main() { inti; InitForFFT(); MakeWave(); for(i=0;i { fWaveR[i]=INPUT[i]; fWaveI[i]=0.0f; w[i]=0.0f; } FFT(fWaveR,fWaveI);//输入波形进行FFT变换,此处引入起始实参即可递推下去 for(i=0;i { DATA[i]=w[i];//变换后的波形转换到输出接口 } while (1);//breakpoint } //旋转因子事先初始化好,方便调用 voidInitForFFT() { inti; for(i=0;i { sin_tab[i]=sin(PI*2*i/SAMPLENUMBER); cos_tab[i]=cos(PI*2*i/SAMPLENUMBER);//旋转因子事先初始化好,方便调用 } } //利用这个,确实能产生各种各样的谐波 voidMakeWave()//利用这个,确实能产生各种各样的谐波 { inti; for(i=0;i { 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☺ 基2FFT总的思想是将输入信号对半分割, 再对半分割, 再再对半分割(以下省略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 for(j=0;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实现流程图分析(N=8, 以8点信号为例) FFTimplementationofan8-pointDFTastwo4-pointDFTsandfour2-pointDFTs 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]; X_I[k]=x_i[k]-tw_i*x_r[k+N/2]+tw_r*x_i[k+N/2]; LayerII部分, 具有2个颗粒, 每个颗粒4个输入 (注意4个输入的来源, 由LayerI友情提供, 感谢感谢☺) LayerIII部分, 具有1个颗粒, 每个颗粒8个输入 (注意8个输入的来源, 由LayerII友情提供, 感谢感谢☺) LayerI,LayerII,LayerIII从左往右, 蝶形信号运算流非常明显! 假令输入为x[k],x[k+N/2], 输出为X[k],X[k+N/2].x[k]分解为x_r[k],x_i[k]部分 则该蝶形运算为 X[k] =(x_r[k]-j*x_i[k])+(x_r[k+N/2]-j*x_i[k+N/2])*(cos(2*PI*k/N)-j*sin(2*PI*k/N)); 再令cos(2*PI*k/N)为tw1,sin(2*PI*k/N)为tw2 则 X[k]=(x_r[k]-j*x_i[k])+(x_r[k+N/2]-j*x_i[k+N/2])*(tw1-j*tw2); X_R[k]=x_r[k]+x_r[k+N/2]*tw1- x_i[k+N/2]*tw2; X_I[K]=x_i[k] x_r[k]=x_r[k]+x_r[k+b]*tw1+x_i[k+b]*tw2; x_i[k]=x_i[k]-x_r[k+b]*tw2+x_i[k+b]*tw1; 譬如8点输入x[8] 1. 先分割成2部分: x[0],x[2],x[4],x[6] 和 x[1],x[3],x[5],x[7] 2. 信号x[0],x[2],x[4],x[6]再分割成x[0],x[4] 和 x[2],x[6] 信号x[1],x[3],x[5],x[7]再分割成x[1],x[5] 和 x[3],x[7] 3. 无法分割了, 已经分割成2点了☺. 如上图: 在LayerI的时候, 我们是对2点进行DFT.( 一共4次DFT) 输入为 x[0]&x[4]; x[2]&x[6]; x[1]&x[5]; x[3]&x[7] 输出为 y[0],y[1]; Y[2],y[3]; Y[4],y[5]; Y[6],y[7]; 流程: I. 希望将输入直接转换为x[0],x[4],x[2],x[6],x[1],x[5],x[3],x[7]的顺序 II. 对转换顺序后的信号进行4次DFT 步骤I代码实现 /** * 反转算法. 这个算法效率比较低! 先用起来在说, 之后需要进行优化. */ static void bitrev( void ) { int p=1,q,i; int bit_rev[N]; float xx_r[N]; bit_rev[0]=0; while(p { for(q=0;q { bit_rev[q] =bit_rev[q]*2; bit_rev[q+p]=bit_rev[q]+1; } p*=2; } for(i=0;i for(i=0;i } //------------------------ 此刻序列x重排完毕------------------------ 步骤II代码实现 intj; floatTR; // 临时变量 floattw1; // 旋转因子 /* 两点DFT*/ for(k=0;k { // 两点DFT简化告诉我们tw1=1 TR=x_r[k]; //TR就是A,x_r[k+b]就是B. x_r[k] =TR+tw1*x_r[k+b]; x_r[k+b]=TR-tw1*x_r[k+b]; } 在LayerII的时候, 我们希望得到z, 就需要对y进行DFT. y[0],y[2]; y[1],y[3]; y[4],y[6]; y[5],y[7]; z[0], z[1]; z[2],z[3]; z[4],z[5]; z[6],z[7]; 在LayerIII的时候, 我们希望得到v, 就需要对z进行DFT. z[0],z[4]; z[1],z[5]; z[2],z[6]; z[3],z[7]; v[0],v[1]; v[2],v[3]; v[4],v[5]; v[6],v[7]; 准备 令输入为x[s],x[s+N/2], 输出为y[s],y[s+N/2] 这个N绝对不是上面的8, 这个N是当前颗粒的输入样本总量 对于LayerI而言N是2; 对于LayerII而言N是4; 对于LayerIII而言N是8 复数乘法: (a+j*b)*(c+j*d) 实部 =a*c–bd; 虚部 =ad+bc; 旋转因子: 实现(C描述) #include #include #include //#include"complex.h" //-------------------------------------------------------------------------- #define N 8 //64 #define M 3 //6 //2^m=N #define PI 3.1415926 //-------------------------------------------------------------------------- float twiddle[N/2]={1.0,0.707,0.0,-0.707}; float x_r[N]={1,1,1,1,0,0,0,0}; float x_i[N]; //N=8 /* float twiddle[N/2]={1, 0.9951,0.9808,0.9570,0.9239,0.8820,0.8317,0.7733, 0.7075,0.6349, 0.5561, 0.4721, 0.3835, 0.2912, 0.1961, 0.0991, 0.0000,-0.0991,-0.1961,-0.2912,-0.3835,-0.4721,-0.5561,-0.6349, -0.7075,-0.7733,0.8317,-0.8820,-0.9239,-0.9570,-0.9808,-0.9951}; //N=64 float x_r[N]={1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,}; float x_i[N]; */ FILE*fp; //-----------------------------------func----------------------------------- /** * 初始化输出虚部 */ static void fft_init( void ) { int i; for(i=0;i } /** * 反转算法.将时域信号重新排序. * 这个算法有改进的空间 */ static void bitrev( void ) { int p=1,q,i; int bit_rev[N]; // float xx_r[N]; // bit_rev[0]=0; while(p { for(q=0;q { bit_rev[q] =bit_rev[q]*2; bit_rev[q+p]=bit_rev[q]+1; } p*=2; } for(i=0;i for(i=0;i } /*------------addbysshc625------------*/ static void bitrev2( void ) { return ; } /* */ void display( void ) { printf("/n/n"); int i; for(i=0;i printf("%f/t%f/n",x_r[i],x_i[i]); } /** * */ void fft1( void ) { fp=fopen("log1.txt", "a+"); int L,i,b,j,p,k,tx1,tx2; float TR,TI,temp; // 临时变量 float tw1,tw2; /* 深M. 对层进行循环.L为当前层, 总层数为M.*/ for(L=1;L<=M;L++) { fprintf(fp,"----------Layer=%d----------/n",L); /*b的意义非常重大,b表示当前层的颗粒具有的输入样本点数 */ b=1; i=L-1; while(i>0) { b*=2; i--; } //-------------- 是否外层对颗粒循环, 内层对样本点循环逻辑性更强一些呢! -------------- /* *outter对参与DFT的样本点进行循环 *L=1, 循环了1次(4个颗粒, 每个颗粒2个样本点) *L=2, 循环了2次(2个颗粒, 每个颗粒4个样本点)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FFT 详细 源代码 解释