欢迎来到天天文库
浏览记录
ID:37716815
大小:25.41 KB
页数:5页
时间:2019-05-29
《傅里叶转换理解》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一、彻底理解傅里叶变换快速傅里叶变换(Fast Fourier Transform)是离散傅里叶变换的一种快速算法,简称FFT,通过FFT可以将一个信号从时域变换到频域。模拟信号经过A/D转换变为数字信号的过程称为采样。为保证采样后信号的频谱形状不失真,采样频率必须大于信号中最高频率成分的2倍,这称之为采样定理。假设采样频率为fs,采样点数为N,那么FFT结果就是一个N点的复数,每一个点就对应着一个频率点,某一点n(n从1开始)表示的频率为:fn=(n-1)*fs/N。举例说明:用1kHz的采样频率采样128点,则FFT结果的128
2、个数据即对应的频率点分别是0,1k/128,2k/128,3k/128,…,127k/128 Hz。这个频率点的幅值为:该点复数的模值除以N/2(n=1时是直流分量,其幅值是该点的模值除以N)。二、傅里叶变换的C语言编程1、对于快速傅里叶变换FFT,第一个要解决的问题就是码位倒序。 假设一个N点的输入序列,那么它的序号二进制数位数就是t=log2N. 码位倒序要解决两个问题:①将t位二进制数倒序;②将倒序后的两个存储单元进行交换。①将t=3位二进制数倒序②将倒序后的两个存储单元进行交换 如果输入序列的自然顺序号i用二进制
3、数表示,例如若最大序号为15,即用4位就可表示n3n2n1n0,则其倒序后j对应的二进制数就是n0n1n2n3,那么怎样才能实现倒序呢?利用C语言的移位功能!程序如下,我不多说,看不懂者智商一定在180以下!复数类型定义及其运算#define N 64 //64点#define log2N 6 //log2N=6/*复数类型*/typedef struct{ float real; float img;}complex;complex xdata x[N]; //输入序列/*复数加法*/complex add(comp
4、lex a,complex b){ complex c; c.real=a.real+b.real; c.img=a.img+b.img; return c;}/*复数减法*/complex sub(complex a,complex b){ complex c; c.real=a.real-b.real; c.img=a.img-b.img; return c;}/*复数乘法*/complex mul(complex a,complex b){ complex c; c.real=a.real*b.real - a.img*b.i
5、mg; c.img=a.real*b.img + a.img*b.real; return c;}/***码位倒序函数***/void Reverse(void){ unsigned int i,j,k; unsigned int t; complex temp;//临时交换变量 for(i=0;i6、1; j7、=(k&1);//j左移一位然后加上k的最低位 k>>=1;//k右移一位,次低位变为最低位 } if(j>i)//如果倒序后大于原序数,就将两个存储单元进行交换(判断j>i是为了防止重复交换) { temp=x; x=x[j]; x[j]=temp; } }}2、第二个要解决的问题就是蝶形运算①第1级(第1列)每个蝶形的两节点“距离”为1,第2级每个蝶形的两节点“距离”为2,第3级每个蝶形的两节点“距离”为4,第4级每个蝶形的两节点“距离”为8。由此推得, 第m级蝶形运算,每个蝶形的两节点“距8、离”L=2m-1。②对于16点的FFT,第1级有16组蝶形,每组有1个蝶形;第2级有4组蝶形,每组有2个蝶形;第3级有2组蝶形,每组有4个蝶形;第4级有1组蝶形,每组有8个蝶形。由此可推出,对于N点的FFT,第m级有N/2L组蝶形,每组有L=2m-1个蝶形。③旋转因子的确定以16点FFT为例,第m级第k个旋转因子为,其中k=0~2m-1-1,即第m级共有2m-1个旋转因子,根据旋转因子的可约性,,所以第m级第k个旋转因子为,其中k=0~2m-1-1。为提高FFT的运算速度,我们可以事先建立一个旋转因子数组,然后通过查表法来实现。co9、mplex code WN[N]=//旋转因子数组{ //为节省CPU计算时间,旋转因子采用查表处理 //★根据实际FFT的点数N,该表数据需自行修改 //以下结果通过Excel自动生成 // WN[k].real=cos(2
6、1; j
7、=(k&1);//j左移一位然后加上k的最低位 k>>=1;//k右移一位,次低位变为最低位 } if(j>i)//如果倒序后大于原序数,就将两个存储单元进行交换(判断j>i是为了防止重复交换) { temp=x; x=x[j]; x[j]=temp; } }}2、第二个要解决的问题就是蝶形运算①第1级(第1列)每个蝶形的两节点“距离”为1,第2级每个蝶形的两节点“距离”为2,第3级每个蝶形的两节点“距离”为4,第4级每个蝶形的两节点“距离”为8。由此推得, 第m级蝶形运算,每个蝶形的两节点“距
8、离”L=2m-1。②对于16点的FFT,第1级有16组蝶形,每组有1个蝶形;第2级有4组蝶形,每组有2个蝶形;第3级有2组蝶形,每组有4个蝶形;第4级有1组蝶形,每组有8个蝶形。由此可推出,对于N点的FFT,第m级有N/2L组蝶形,每组有L=2m-1个蝶形。③旋转因子的确定以16点FFT为例,第m级第k个旋转因子为,其中k=0~2m-1-1,即第m级共有2m-1个旋转因子,根据旋转因子的可约性,,所以第m级第k个旋转因子为,其中k=0~2m-1-1。为提高FFT的运算速度,我们可以事先建立一个旋转因子数组,然后通过查表法来实现。co
9、mplex code WN[N]=//旋转因子数组{ //为节省CPU计算时间,旋转因子采用查表处理 //★根据实际FFT的点数N,该表数据需自行修改 //以下结果通过Excel自动生成 // WN[k].real=cos(2
此文档下载收益归作者所有