《(快速傅里叶变换)C语言程序汇编.doc》由会员分享，可在线阅读，更多相关《(快速傅里叶变换)C语言程序汇编.doc（16页珍藏版）》请在三一文库上搜索。
1、#i nclude #in elude vintrin sics.h /* 快速傅立叶变换 C 函数 函数简介：此函数是通用的快速傅里叶变换 C 语言函数，移植性强，以下部分不依 赖硬件。此函数采用联合体的形式表示一个复数，输入为自然顺序的复 数(输入实数是可令复数虚部为 0)，输出为经过 FFT 变换的自然顺序的 复数 使用说明：使用此函数只需更改宏定义 FFT_N 的值即可实现点数的改变， FFT_N 应该为 2 的 N 次方，不满足此条件时应在后面补 0 函数调用：FFT(s); 时 间：2010-2-20 版 本：Ver1.0 参考文献： * #in clude #defi ne PI
2、 3.1415926535897932384626433832795028841971 #define FFT_N 128 变换的点数 定义圆周率值 /定义傅立叶 struct compx float real,imag; struct compx sFFT_N; 出：从 S1开始存放，根据大小自己定义 /定义一个复数结构 /FFT 输入和输 /* 函数原型： struct compx EE(struct compx b1,struct compx b2) 函数功能：对两个复数进行乘法运算 输入参数：两个以联合体定义的复数 a,b 输出参数：a 和 b 的乘积，以联合体的形式输出 */ str
3、uct compx EE(struct compx a,struct compx b) struct compx c; c.real=a.real*b.real-a.imag*b.imag; c.imag=a.real*b.imag+a.imag*b.real; return(c); /* 函数原型：void FFT(struct compx *xi n,int N) 函数功能：对输入的复数组进行快速傅里叶变换( FFT) 输入参数：*xin 复数结构体组的首地址指针， struct 型 */ void FFT(struct compx *xi n) int f,m, nv2,n m1,i,k
4、,l,j=O; struct compx u,w,t; /变址运算，即把自然顺序变成倒位序，采用雷德算 如果 ij,即进行变址 /求 j 的下一个倒位序 如果 k=j,表示 j 的最高位为 1 /把最高位变成 0 /k/2，比较次高位，依次类推，逐个比较，直到某个位为 0 /把 0 改为 1 /FFT 运算核，使用蝶形运算完成 FFT 运算 /计算 I 的值，即计算蝶形级数 /控制蝶形结级数 /m 表示第 m 级蝶形，I 为蝶形级总数 /le 蝶形结距离，即第 m 级蝶形的蝶形结 /同一蝶形结中参加运算的两点的距离 /u 为蝶形结运算系数，初始值为 1 /w 为系数商，即当前系数与前一个系数的
5、商 /控制计算不同种蝶形结，即n v2=FFT_N/2; 法 n m 仁 FFT_N-1; for(i=0;i n m1;i+) if(ij) t=xi nj; xi nj=xi n i; xin i=t; k=nv2; while(k=j) j=j-k; k=k/2; j=j+k; int le,lei,ip; f=FFT_N; for(l=1;(f=f/2)!=1;l+); for(m=1;m=l;m+) l=log ( 2)N le=2(m-1); 相距 le 点 lei=le/2; u.real=1.0; u.imag=0.0; w.real=cos(PI/lei); w.imag=-
6、si n( PI/lei); for(j=0;j=lei-1;j+) 计算系数不同的 si.real=sqrt(si.real*si.real+si.imag*si.imag); while(1); #i nclude #in elude vintrin sics.h /* 蝶形结 for(i=j;i=FFT_N-1;i=i+le) 控制同一蝶形结运算，即计算系数相同蝶形 ip=i+lei; t=EE(xi n ip,u); xi nip.real=xi n i.real-t.real; xin ip.imag=x in i.imag-t.imag; xi ni.real=xi n i.rea
7、l+t.real; xi ni.imag=xi ni.imag+t.imag; u=EE(u,w); /i，ip分别表示参加蝶形运算的两个节点 /蝶形运算，详见公式 /改变系数，进行下一个蝶形运算 /* 函数原型 函数功能 输入参数 输出参数 void mai n() 测试 FFT 变换，演示函数使用方法 无 无 */ void mai n() int i; for(i=0;iFFT_N;i+) si.real=si n(2*3.141592653589793*i/FFT_N); / si.imag=0; /给结构体赋值 实部为正弦波 FFT_N 点采样，赋值为 1 虚部为 0 FFT(s);
8、 /进行快速傅立叶变换 for(i=0;iFFT_N;i+) 部部分 /求变换后结果的模值，存入复数的实 快速傅立叶变换 C 程序包 函数简介：此程序包是通用的快速傅里叶变换 C 语言函数，移植性强，以下部分不依 赖硬件。此程序包采用联合体的形式表示一个复数，输入为自然顺序的复 数(输入实数是可令复数虚部为 0)，输出为经过 FFT 变换的自然顺序的 复数.此程序包可在初始化时调用 create_sin_tab()函数创建正弦函数表， 以后的可采用查表法计算耗时较多的 sin 和 cos 运算，加快可计算速度 使用说明：使用此函数只需更改宏定义 FFT_N 的值即可实现点数的改变， FFT_N
9、 应该为 2 的 N 次方，不满足此条件时应在后面补 0。若使用查表法计算 sin 值和 cos 值，应在调用 FFT 函数前调用 create_sin_tab()函数创建正弦表 函数调用：FFT(s); 时 间：2010-2-20 版 本：Ver1.1 参考文献： */ #in clude #define FFT_N 128 / 定义傅立叶 变换的点数 #defi ne PI 3.1415926535897932384626433832795028841971 / 定义圆周率值 struct compx float real,imag; / 定义一个复数结构 struct compx sFF
10、T_N; /FFT 输入和输出：从 S0开始存放，根据大小自己定义 float SIN_TABFFT_N/2; /定义正弦表的存放空间 /* 函数原型： struct compx EE(struct compx b1,struct compx b2) 函数功能：对两个复数进行乘法运算 输入参数：两个以联合体定义的复数 a,b 输出参数：a 和 b 的乘积，以联合体的形式输出 */ struct compx EE(struct compx a,struct compx b) struct compx c; c.real=a.real*b.real-a.imag*b.imag; c.imag=a.
11、real*b.imag+a.imag*b.real; return(c); /* 函数原型：void create_sin_tab(float *sin_t) 函数功能：创建一个正弦采样表，采样点数与傅立叶变换点数相同 输入参数：*sin_t 存放正弦表的数组指针 输出参数：无 */ void create_s in _tab(float *sin_t) int i; for(i=0;i=0&n =FFT_ N/2&n 2*PI) pi2-=2*PI; a=s in _tab(pi2); return a; * 函数原型：void FFT(struct compx *xi n,
12、int N) 函数功能：对输入的复数组进行快速傅里叶变换( FFT) 输入参数：*xin 复数结构体组的首地址指针， struct 型 输出参数：无 */ void FFT(struct compx *xi n) int f,m, nv2,n m1,i,k,l,j=O; struct compx u,w,t; /变址运算，即把自然顺序变成倒位序，采用雷德算法 /求 j 的下一个倒位序 如果 k=j,表示 j 的最高位为 1 /把最高位变成 0 /k/2，比较次高位，依次类推，逐个比较，直到某个位为 把 0 改为 1n v2=FFT_N/2; n m 仁 FFT_N-1; for(i=0;i n
13、 m1;i+) if(ij) t=xi nj; xi nj=xi n i; xin i=t; k=nv2; while(k=j) j=j-k; k=k/2; j=j+k; 如果 ij,即进行变址 int le,lei,ip; f=FFT_N; for(l=1;(f=f/2)!=1;l+) J for(m=1;m=l;m+) le=2(m-1); lei=le/2; u.real=1.0; u.imag=0.0; w.real=cos(PI/lei); / w.imag=-si n( PI/lei); w.real=cos_tab(PI/lei); w.imag=-sin_tab(PI/lei)
14、; /FFT 运算核，使用蝶形运算完成 FFT 计算 I 的值，即计算蝶形级数 /控制蝶形结级数 /m 表示第 m 级蝶形，I 为蝶形级总数 l=log /le 蝶形结距离，即第 m 级蝶形的蝶形结相距 同一蝶形结中参加运算的两点的距离 /u 为蝶形结运算系数，初始值为 1 不适用查表法计算 sin 值和 cos 值 /w 为系数商，即当前系数与前一个系数的商 运算 (2) N le 点 for(j=0;j=lei_1;j+) for(i=j;i=FFT_N-1;i=i+le) ip=i+lei; t=EE(xi n ip,u); xi nip.real=xi n i.real-t.real;
15、 xin ip.imag=x in i.imag-t.imag; xi ni.real=xi n i.real+t.real; xi ni.imag=xi ni.imag+t.imag; u=EE(u,w); /* 函数原型：void mai n() 函数功能：测试 FFT 变换，演示函数使用方法 输入参数：无 输出参数：无 */ void mai n() int i; create_sin_tab(SIN_TAB); for(i=0;iFFT_N;i+) / 给结构体赋值 si.real=sin(2*3.141592653589793*i/FFT_N); / 实部为正弦波 FFT_N 点采样
16、，赋值为 1 si.imag=0; /虚部为 0 FFT(s); /进行快速傅立叶变换 for(i=0;iFFT_N;i+) 求变换后结果的模值，存入复数的实部部分 si.real=sqrt(si.real*si.real+si.imag*si.imag); while(1);/控制计算不同种蝶形结，即计算系数不同的蝶形结 控制同一蝶形结运算，即计算系数相同蝶形结 i, ip 分别表示参加蝶形运算的两个节点 /蝶形运算，详见公式 /改变系数，进行下一个蝶形运算 #i nclude #in elude vintrin sics.h /* 快速傅立叶变换 C 程序包 函数简介：此程序包是通用的快速
17、傅里叶变换 C 语言函数，移植性强，以下部分不依 赖硬件。此程序包采用联合体的形式表示一个复数，输入为自然顺序的复 数(输入实数是可令复数虚部为 0)，输出为经过 FFT 变换的自然顺序的 复数.此程序包可在初始化时调用 create_sin_tab()函数创建正弦函数表， 以后的可采用查表法计算耗时较多的 sin 和 cos 运算，加快可计算速度.与 Ver1.1 版相比较，Ver1.2 版在创建正弦表时只建立了 1/4 个正弦波的采样值， 相比之下节省了 FFT_N/4 个存储空间 使用说明：使用此函数只需更改宏定义 FFT_N 的值即可实现点数的改变， FFT_N 的 应该为 2 的 N
18、 次方，不满足此条件时应在后面补 0。若使用查表法计算 sin 值和 cos 值，应在调用 FFT 函数前调用 create_sin_tab()函数创建正弦表 函数调用：FFT(s); 时 间：2010-2-20 版 本：Ver1.2 参考文献： */ #in clude #define FFT_N 128 / 定义傅立叶 变换的点数 #defi ne PI 3.1415926535897932384626433832795028841971 / 定义圆周率值 struct compx float real,imag; / 定义一个复数结构 struct compx sFFT_N; /FFT
19、输入和输出：从 S0开始存放，根据大小自己定义 float SIN_TABFFT_N/4+1; /定义正弦表的存放空间 /* 函数原型： struct compx EE(struct compx b1,struct compx b2) 函数功能：对两个复数进行乘法运算 输入参数：两个以联合体定义的复数 a,b 输出参数：a 和 b 的乘积，以联合体的形式输出 */ struct compx EE(struct compx a,struct compx b) struct compx c; c.real=a.real*b.real-a.imag*b.imag; c.imag=a.real*b.i
20、mag+a.imag*b.real; return(c);/* 函数原型：void create_sin_tab(float *sin_t) 函数功能：创建一个正弦采样表，采样点数与傅立叶变换点数相同 输入参数：*sin_t 存放正弦表的数组指针 输出参数：无 */ void create_s in _tab(float *sin_t) int i; for(i=0;i=0&nFFT_N/ 4&* FFT_N/2) n-=FFT_N/4; a=SIN_TABFFT_N/4-n; else if(n =FFT_N/2&n=3*FFT_N/4&n2*PI) pi2-
21、=2*PI; a=s in _tab(pi2); return a; /* 函数原型：void FFT(struct compx *xi n,int N) 函数功能：对输入的复数组进行快速傅里叶变换( FFT) 输入参数：*xin 复数结构体组的首地址指针， struct 型 输出参数：无 */ void FFT(struct compx *xi n) int f,m, nv2,n m1,i,k,l,j=0; struct compx u,w,t; /变址运算，即把自然顺序变成倒位序，采用雷德算 如果 ij,即进行变址 /求 j 的下一个倒位序 如果 k=j,表示 j 的最高位为 1 /把最高
22、位变成 0 /k/2，比较次高位，依次类推，逐个比较，直到某个位为 0 n v2=FFT_N/2; 法 n m 仁 FFT_N-1; for(i=0;i n m1;i+) if(ij) t=xi nj; xi nj=xi n i; xin i=t; k=nv2; while(k=j) j=j-k; k=k/2; j=j+k; /* 把 0 改为 1 /FFT 运算核，使用蝶形运算完成 FFT 运算 /计算 I 的值，即计算蝶形级数 /控制蝶形结级数 /m 表示第 m 级蝶形，I 为蝶形级总数 /le 蝶形结距离，即第 m 级蝶形的蝶形结 /同一蝶形结中参加运算的两点的距离 /u 为蝶形结运算系
23、数，初始值为 1 /不适用查表法计算 sin 值和 cos 值 /w 为系数商，即当前系数与前一个系数的商 控制计算不同种蝶形结， 即计算系数不同的蝶 控制同一蝶形结运算，即计算系数相同蝶形 /i，ip 分别表示参加蝶形运算的两个节点 /蝶形运算，详见公式 /改变系数，进行下一个蝶形运算 /* 函数原型：void mai n() 函数功能：测试 FFT 变换，演示函数使用方法 输入参数：无 输出参数：无 int le,lei,ip; f=FFT_N; for(l=1;(f=f/2)!=1;l+) J for(m=1;m=l;m+) l=log (2) N le=2(m-1); 相距 le 点
24、lei=le/2; u.real=1.0; u.imag=O.O; w.real=cos(PI/lei); / w.imag=-si n( PI/lei); w.real=cos_tab(PI/lei); w.imag=-sin_tab(PI/lei); for(j=0;j=lei_1;j+) 形结 for(i=j;i=FFT_N-1;i=i+le) 结 ip=i+lei; t=EE(xi n ip,u); xi nip.real=xi n i.real-t.real; xin ip.imag=x in i.imag-t.imag; xi ni.real=xi n i.real+t.real;
25、 xi ni.imag=xi ni.imag+t.imag; u=EE(u,w); * void mai n() int i; create_sin_tab(SIN_TAB); for(i=0;iFFT_N;i+) si.real=si n(2*3.141592653589793*i/FFT_N); / si.imag=0; FFT(s); for(i=0;iFFT_N;i+) 部部分 si.real=sqrt(si.real*si.real+si.imag*si.imag); while(1); /给结构体赋值 实部为正弦波 FFT_N 点采样，赋值为 1 /虚部为 0 /进行快速傅立叶变换 /求变换后结果的模值，存入复数的实