首页 > 编程知识 正文

数字信号处理实验报告,8点fft蝶形图例题

时间:2023-05-06 20:11:05 阅读:120046 作者:462

数字信号处理通常需要离散傅立叶变换(DFT )来获取信号的频域特征。 传统的DFT算法可以获得信号的频域特征,但算法计算量大,耗时长,不利于计算机实时处理信号。 因此,自DFT被发现以来,长期未能应用于实际工程项目。 自从快速离散傅立叶计算方法——FFT被发现后,离散傅立叶变换在实际工程中得到了广泛的应用。 需要强调的是,FFT是DFT的快速实现算法,而不是新的频域特征获取方式。 本文详细说明FFT的原理和具体实现过程。

DFT的计算公式本文没有导出,直接给出DFT的计算公式:

其中,x(n )表示输入的离散数字信号序列,WN是旋转因子,x(k )是对应于输入序列x(n )的n个离散频率点的相对宽度。 一般而言,x(n )来源于低通滤波,x ) k表示从-fs/2频率到频率间隔为fs/N、fs/2-fs/N的n个频率点的相对宽度。 因为通过DFT计算得到的一组离散的频率振幅值实际上在频率轴上周期性变化。 即x(kn )=x (k )。 因此,如果任意取连续n个点,则能够表现DFT的计算效果,负的频率分量抽象且难以理解,但根据x(k )的周期特性,x(k )从频率零到频率间隔fs/N、fs-fs/N的n个频率点的相对宽度

n点DFT的计算量根据(1)式给出的DFT计算式,每次计算频率点x(k )时需要n次复数乘法和N-1次复数加法,计算n各点的x(k )时需要N^2次复数乘法和n* ) N-1次复数加法当x(n )为实数时,计算n点的DFT需要2*N^2次实数乘法,2*n*(n-1 )次实数加法。

旋转因子WN的特性1.WN的对称性

2.WN周期性

3.WN约定性

根据以上性质,可以得到式(5)的一系列有用的结果

基-2 FFT算法假设采样序列点数为N=2^L,l为整数,如果不满足这个条件,可以人为地增加一些0使采样序列点数满足这个要求。 首先,让我们根据奇偶校验将系列x(n )分为两组。

因此根据DFT计算公式(1),如下所示。

至此,我们将一个n点的DFT转换为公式(7)的形式。 此时,k的可取值为0到N-1。 这里分为两部分进行讨论。 k为0~N/2-1时,x1(r )、x1(r )是N/2点的系列,因此此时式(7)可以写为:

另一方面,当k取N/2~N-1的值时,k被k’n/2置换,k’取0~N/2-1的值。 公式(7)简化如下

综合以上推导,可以得出一个n点DFT变换过程可以用两个N/2点DFT变换过程表示,其具体公式类似于公式(10 )所示的DFT快速算法的迭代公式。

上式中x'(k ' ) )是偶数项分支的离散傅立叶变换,x'(k ' ) ) )是奇数项分支的离散傅立叶变换。 可以通过图1的蝶形算法的流程图直观地表示式(10 )的计算过程。

图1时间提取法蝶式运算流程图

在图1中,输入为2个N/2点的DFT输出为1个n点的DFT结果,输入输出点数一致。 使用该显示方法,8点的DFT可以如图2所示表示:

图2 8点DFT的4点分解

公式(10 )表明,一个n点的DFT可以由两个N/2点的DFT运算组成,并结合图1的蝶形信号流程图得到图2的8点DFT的第一次分解。 可以在下一步中描述分解。

1 .将n点输入序列按奇偶校验分为两组,分别取N/2点序列

对每个2.1序列进行DFT变换,得到两组点数为N/2的DFT变换值X1和X2

3 .根据蝶形信号流程图,将2的结果合并为一个n点DFT变换结果

通过式(10 ),可以进一步分解图2中的4个点的DFT,可以得到图3的结果,分解步骤与前面一致。

图3 8点DFT的两点分解

最后进一步分解两点DFT,得到最终的8点FFT信号,计算流程图:

图4 8点DFT的全分解

需要在图2至图4的过程中说明旋转系数的变化规律。 看起来是前进了一个阶段,但是在奇数分组的部分中的旋转系数因子的增加量可能会变大,但事实并非如此。 事实上,奇数分组部分的旋转系数指数每次都固定为1,因为每次前进都会分组

序列的数据个数变少了,为了统一使用以原数据N为基的旋转因子就进行了变换导致的。每一次分组奇数部分的系数WN,这里的N均为本次分组前的序列点数。以上边的8点DFT为例,第一次分组N=8,第二次分组N为4,为了统一根据式(4)进行了变换将N变为了8,但指数相应的需要乘以2。

N点基-2 FFT算法的计算量

从图4可以看到N点DFT的FFT变换可以转为log2(N)级级联的蝶形运算,每一级均包含有N/2次蝶形计算。而每一个蝶形运算包含了1次复数乘法,2次复数加法。因此N点FFT计算的总计算量为:复数乘法——N/2×log2(N)    复数加法——N×log2(N)。假设被采样的序列为实数序列,那么也只有第一级的计算为实数与复数的混合计算,经过一次迭代后来的计算均变为复数计算,在这一点上和直接的DFT计算不一致。因此对于输入序列是复数还是实数对FFT算法的效率影响较小。一次复数乘法包含了4次实数乘法,2次实数加法,一次复数加法包含了2次复数加法。因此对于N点的FFT计算需要总共的实数乘法数量为:2×N×log2(N);总的复数加法次数为:2xNxlog2(N)。

N点基-2 FFT算法的实现方法

从图4我们可以总结出对于点数为N=2^L的DFT快速计算方法的流程:

   1.对于输入数据序列进行倒位序变换。

该变换的目的是使输出能够得到X(0)~X(N-1)的顺序序列,同样以8点DFT为例,该变换将顺序输入序列x(0)~x(7)变为如图4的x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)序列。其实现方法是:假设顺序输入序列一次村在A(0)~A(N-1)的数组元素中,首先我们将数组下标进行二进制化(例:对于点数为8的序列只需要LOG2(8) = 3位二进制序列表示,序号6就表示为110)。二进制化以后就是将二进制序列进行倒位,倒位的过程就是将原序列从右到左书写一次构成新的序列,例如序号为6的二进制表示为110,倒位后变为了011,即使十进制的3。第三步就是将倒位前和倒位后的序号对应的数据互换。依然以序号6为例,其互换过程如下:

temp = A(6); A(6) = A(3); A(3) = A(6);

实际上考虑到执行效率,如果对于每一次输入的数据都需要这个处理过程是非常浪费时间的。我们可以采用指向指针的指针来实现该过程,或者是采用指针数组来实现该过程。
 
2.蝶形运算的循环结构。
 从图4中我们可以看到对于点数为N = 2^L的fft运算,可以分解为L阶蝶形图级联,每一阶蝶形图内又分为M个蝶形组,每个蝶形组内包含K个蝶形。根据这一点我们就可以构造三阶循环来实现蝶形运算。编程过程需要注意旋转因子与蝶形阶数和蝶形分组内的蝶形个数存在关联。 

 3.浮点到定点转换需要注意的关键问题 
上边的分析都是基于浮点运算来得到的结论,事实上大多数嵌入式系统对浮点运算支持甚微,因此在嵌入式系统中进行离散傅里叶变换一般都应该采用定点方式。对于简单的DFT运算从浮点到定点显得非常容易。根据式(1),假设输入x(n)是经过AD采样的数字序列,AD位数为12位,则输入信号范围为0~4096。为了进行定点运算我们将旋转因子实部虚部同时扩大2^12倍,取整数部分代表旋转因子。之后,我们可以按照(1)式计算,得到的结果与原结果成比例关系,新的结果比原结果的2^12倍。但是,对于使用蝶形运算的fft我们不能采用这种简单的放大旋转因子转为整数计算的方式。因为fft是一个非对称迭代过程,假设我们对旋转因子进行了放大,根据蝶形流图我们可以发现其最终的结果是,不同的输入被放大了不同的倍数,对于第一个输入x(0)永远也不会放大。举一个更加形象的例子,还是以图4为例。从图中可以看出右侧的X(0)可以直接用下式表示: 




从上式我们可以看到不同输入项所乘的旋转因子 个数(注意这里是个数,就算是wn^0,也被考虑进去了,因为在没有放大时wn^0等于1,放大后所有旋转因子指数模均不为1,因此需要考虑)。这就导致输入不平衡,运算结果不正确。经查阅相关资料,比较妥善的做法是,首先对所有旋转因子都放大2^Q倍,Q必须要大于等于L,以保证不同旋转因子的差异化。旋转因子放大,为了保证其模为1,在每一次蝶形运算的乘积运算中我们需要将结果右移Q位来抵消这个放大,从而得到正确的结果。之所以采用放大倍数必须是2的整数次幂的原因也在于此,我们之后可以通过简单的右移位运算将之前的放大抵消,而右移位又代替了除法运算,大大节省了时间。 

   
    4.计算过程中的溢出问题 
最后需要注意的一个问题就是计算过程中的溢出问题。在实际应用中,AD虽然有12位的位宽,但是采样得到的信号可能较小,例如可能在0~8之间波动,也就是说实际可能只有3位的情况。这种情况下为了在计算过程中不丢失信息,一般都需要先将输入数据左移P位进行放大处理,数据放大可能会导致溢出,从而使计算错误,而溢出的极限情况是这样:假设我们数据位宽为D位(不包括符号位),AD采样位数B位,数字放大倍数P位,旋转因此放大倍数Q位,FFT级联运算带来的最大累加倍数L位。我们得到: 

 
假设AD位宽12,数据位宽32,符号位1位,因此有效位宽31位,采样点数N,那么我们可以得到log2(N)+P+Q<=19,假设点数128,又Q>=L可以得到放大倍数P<=5。 

   
FFT代码示例 
根据以上的分析,我整理了一份128点的FFT代码如下,该代码在keil中仿真运行,未发现问题。

#define N 128 #define POWER 6//该值代表了输入数据首先被放大的倍数,放大倍数为2^POWER #define P_COEF 8//该值代表了旋转因子被放大的倍数,放大倍数为2^POWER #if (N == 4) #define L 2//L的定义满足L = log2(N) #elif (N == 8) #define L 3//L的定义满足L = log2(N) #elif (N == 16) #define L 4//L的定义满足L = log2(N) #elif (N == 32) #define L 5//L的定义满足L = log2(N) #elif (N == 64) #define L 6//L的定义满足L = log2(N) #elif (N == 128) #define L 7//L的定义满足L = log2(N) #endif //AD采样位数为12位,本可以采用s16 x[N]定义数据空间,但是为了节省存储空间,fft结果也将存储在该变量空间。由于受 //fft影响变量需要重新定义,定义的方式及具体原因如下: //fft过程会乘以较大旋转因子,因此需要32位定义 //fft过程会产生负数,因此需要有符号定义 //fft过程会出现复数,因此需要定义二维数组,[][0]存放实部,[][1]存放虚部 s32 x[N][2] = {}; //定义*p[N]是为了在第一次指针初始化以后,该数组指针按照位倒序指向数据变量x //p[i][0]代表了指向数据的实部,p[i][1]代表了指向数据的虚部 s32 *p[N]; //定义旋转因子矩阵 //旋转因子矩阵存储了wn^0,wn^1,wn^2...wn^(N/2-1)这N/2个复数旋转因子 s16 w[N>>1][2] = {256,0,256,-13,255,-25,253,-38,251,-50,248,-62,245,-74,241,-86,237,-98,231,-109,226,
                  -121,220,-132,213,-142,206,-152,198,-162,190,-172,181,-181,172,-190,162,-198,152,
                  -206,142,-213,132,-220,121,-226,109,-231,98,-237,86,-241,74,-245,62,-248,50,-251,38,
                  -253,25,-255,13,-256,0,-256,-13,-256,-25,-255,-38,-253,-50,-251,-62,-248,-74,-245,-86,
                  -241,-98,-237,-109,-231,-121,-226,-132,-220,-142,-213,-152,-206,-162,-198,-172,-190,-181,
                  -181,-190,-172,-198,-162,-206,-152,-213,-142,-220,-132,-226,-121,-231,-109,-237,-98,-241,
                  -86,-245,-74,-248,-62,-251,-50,-253,-38,-255,-25,-256,-13}; void init_pointer(void) { unsigned char i = 0; unsigned char j = 0; unsigned char k = 0; for(i = 0; i < N; i++) { j = 0; for(k = 0; k < L; k++) { j |= (((i >> k)&0x01)<<(L-k-1)); } p[i] = &x[j][0]; } } /* *description:基2fft主函数,该函数将借助指针数组p对全局变量数组x进行fft计算 * 并将结果存储在数组x中 *global var:rw->x; r->p,w。(r表示读,w表示写,rw表示读写) */ void fft2(void) { u8 i;//i用于表示蝶形图级联的阶数 u8 j;//表示蝶形分组起始点序列,蝶形分组跨度为2^i u8 k;//k表示蝶形组内偶数分支序列点号 u8 gp_distance = 1;//蝶形分组跨度 u8 temp;//temp用于记录当前组间距离的一半,同时也表示了同一碟形两分支间的距离 u8 gp_hf = 0;//记录当前组的中间点序号 u8 delta = N;//旋转因子下标增量,本来下标初始值应该为N/2,但是。。 s16 *pw = &(w[0][0]); int tp_result[2]; //用于临时存放旋转因子和奇数分组的乘积 //输入信号序列放大 for(i = 0; i < N; i++) { x[i][0] <<= POWER; x[i][1] <<= POWER; } for(i = 0; i < L; i++) { temp = gp_distance; gp_distance <<= 1; for(j = 0; j < N; j+=gp_distance) { gp_hf = temp + j; pw = &(w[0][0]); for(k = j; k < gp_hf; k++)//完成一组内的所有蝶形运算 { //蝶形运算中的一组复数乘法过程 tp_result[0] = pw[0] * (p[k+temp][0]) - pw[1] * (p[k+temp][1]); tp_result[1] = pw[0] * (p[k+temp][1]) + pw[1] * (p[k+temp][0]); tp_result[0] >>= P_COEF; tp_result[1] >>= P_COEF; //蝶形运算中的2组复数加法过程 p[k+temp][0] = p[k][0] - tp_result[0]; p[k+temp][1] = p[k][1] - tp_result[1]; p[k][0] += tp_result[0]; p[k][1] += tp_result[1]; pw += delta; } } delta >>= 1; } }

转载于:https://www.cnblogs.com/luoqingyu/p/5930181.html

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。