数字信号处理器(基于DSP的FFT算法实现)

数字信号处理器

课程报告

题目：基于DSP的FFT算法实现

姓名：

学号：130405100xx

专业：测控技术与仪器

任课教师：陈晓龙

二〇一六年十二月

∑-==

1

)()1(N n n

N

W

n x X 一．快速傅里叶变换（FFT ）的用途

快速傅立叶变换（FFT ）广泛用于数字信号处理系统当中，特别是电力仪器仪表行业，FFT 是早期最为广泛使用的一种算法。快速傅立叶变换（FFT ）是将信号从时域变换到频域的一种方法，广泛运用于各种信号分析领域，提高了系统的数据处理能力。

二．快速傅里叶变换（FFT ）的基本原理

FFT 并不是一种新的傅立叶变换，只是DFT 的一种快速算法。首先，我们来简单说明下DFT 。

假设k=1，则

需要进行N 次复数乘法、 (N-1)次复

数加法。这样的话，整个DFT 运算量就是N*N 次复数相乘+N*(N-1)次复数加法。这对实时性很强的信号处理(如雷达信号处理)来讲，显然不能满足要求，FFT 则很好地解决这一问题。

FFT 就是不断地把长序列的DFT 分解成几个短序列的DFT ，并利用周期性和对称性来减少DFT 的运算次数。 （1）周期性：

（2）对称性：

最常用的是基2-FFT算法。

FFT上可分为2类：时域抽取法(DIT-FFT)与频域抽取法(DIF-FFT)。以时域抽取法(DIT-FFT)为例说明，

假定N=2M，将序列x(n)按n的奇偶分解为两组，一组为偶数项，一组为奇数项：x1(n)=x(2r) ，r=0，1，…，N/2-1

x2(n)=x(2r+1) ，r=0，1，…，N/2-1

将DFT运算也相应分为两组：

由于X1(k)和X2(k)均以N/2为周期，且由于DFT的周期性（) X(k)可表示为

可见，一个N点的DFT被分解为两个N/2点的DFT。将X1(k)和X2(k) 合成X(k)运算可归结为：a+bw与a-bw，

用流图表示，如下图，称为蝶形运算符号。

完成一次蝶形运算需要一次复数乘和两次加法。

经过一次分解后，计算N点DFT共需计算两个N/2点的DFT和N/2个蝶形运算，而计算一个N/2点的DFT需要(N/2)*2次复数乘和(N/2)*(N/2-1)次复数加法。所以计算N点DFT总共需要：

2(N/2)2+N/2=N(N+1)/2≈N2/2(N>>1) 次复乘

N(N/2-1)+2N/2= N2/2次复数加法

由此可见，仅经过一次分解，就使运算量减少仅一半。

对于N=M2，总是可以通过M次分解最后成为2点的DFT运算。这样构成从x(n)到X(k)的M级运算过程。每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复乘和N次复加，这样，经过时间抽取后M级运算总共需要的运算：

一般而言，DIT-FFT和DIF-FFT两种FFT算法的区别是旋转因子出现的位置不同，DIT-FFT中旋转因子在输入端，DIF-FFT中旋转因子在输出端，除此之外，两种算法是一样的。在本处中实现的是时间抽取FFT算法。

DIF-FFT它有三个运算规律，（1）原位计算：利用同一存储单元存储蝶形计算输入、输出数据的方法称为原位（址）计算。它可节省大

W

量内存。（2）旋转因子的变换规律：在N点DIT-FFT运算流图中，P N 称其为旋转因子，p称为旋转因子的指数。用L表示从左到右的运算级数（L=1，2，…，M）。第L级共有1

2-L个不同的旋转因子。对N=M2的一般情况，第L级的旋转因子为

（3）蝶形运算的规律:同一个旋转因子对应着间隔为L2点的L

M-

2个蝶形。

三．快速傅里叶变换（FFT）的硬件结构

对信号进行FFT变换，首先要对模拟信号采样将其转换为数字信号。输入的连续模拟信号经信号调理电路后输出到DSP的ADC模拟输入通道，经过ADC数据采集，模数转换的结果存放于ADC结果寄存器中。信号调理电路主要是为了信号的抗混叠滤波以及电路阻抗的匹配。信号调理电路对输入信号进行调理处理，包括信号的滤波、跟随输出以及信号的稳定。DSP对采集的数字信号进行FFT运算处理，同时对运算结果进行相应的数据显示和数据存储。

电路设计时要考虑数字信号处理存在的信号完整性问题、信号线之间的串扰及电磁干扰、模数信号间的相互影响。主要包括进行合理走线、适当的板层数和去耦电容、完整的地层及必要的终端匹配。一般来说有以下的措施：

（1）采用多层板，电源与地都可以考虑采用专门的层，尽量用大面积地。电源与地换层时，过孔的孔径要足够大，或者多留几个过孔，合理布放去耦电容。（2）对于重要信号线，比如时钟信号，要在不降低片内主频的条件下，降低外部时钟频率。（3）为了减小信号之间的干扰，要在空间分开彼此，最好提供双方互不干扰的返回途径，比如地或电源，含地线的双绞线、屏蔽线就能做到这点。为了减小信号与外界的干扰，应远离干扰源或采取屏蔽措施等。（4）要考虑数模混合时数字电路产生的开关噪声对模拟电路的影响，避免使用同一电源等等。

四．快速傅里叶变换（FFT）的软件结构

用c语言实现，如下：

#include

#define word32 int

#define word16 short

void fft(double*x,double*y,word32 n,word32 sign)

{

word32 i,j,k,l,m,n1,n2;

double c,s,tr,ti,pi=4.0*atan(1.0);

for(j=i=1;i<16;i++) //倒序算法的实现{

m=i;

j=2*j;

if(j==n)break;

}

for(n1=n-1,j=0,i=0;i

{

if(i

{

tr=x[j]；ti=y[j];x[j]=x[i];

y[j]=y[i];x[i]=tr;y[i]=ti;

}

k=n/2;

while(k<=j)

{

j=j-k;k=k/2;

}

j=j+k;

}

for(n1=l=1;l<=m;l++) //蝶形运算的实现{

n1=2*n1;n2=n1/2;

for(j=0;j

{

c=cos(j*pi/n2);

s=-sign*sin(j*pi/n2);

for(i=j;i

{

k=i+n2;

tr=c*x[k]-s*y[k];

ti=c*y[k]+s*x[k];

x[k]=x[i]-tr;

y[k]=y[i]-ti;

x[i]=x[i]+tr;

y[i]=y[i]+ti;

}

}

}

if(sign==-1)

{

for(i=0;i

{x[i]/=n；

y[i]/=n;}

}

}