DSP 原理及应用大作业——快速傅立叶变换专业：XXXX 姓名：XXX 学号：08201081XX 指导老师：XX 时间：2XXXX快速傅立叶变换(FFT )实验一、设计目的1.在理论学习的基础上，通过本实验，加深对FFT的理解，熟悉FFT子程序。

2.熟悉应用FFT对典型信号进行频谱分析的方法3•了解应用FFT进行信号频谱分析过程中可能出现的问题以便在实际中正确应用FFT。

4.掌握用窗函数法设计FFT快速傅里叶的原理和方法；5 •熟悉FFT快速傅里叶特性；二、所需设备PC 兼容机一台，操作系统为Windows2000(或Windows98 , WindowsXP，以下默认为Windows2000)，安装Code Composer Studio 2.0 软件。

三、设计内容本试验要求使用FFT变换求一个时域信号的频域特性，并从这个频域特性求出该信号的频率值。

使用c语言实现对FFT算法的仿真，然后使用DSP汇编语言实现对FFT 的DSP 编程。

本实验采用软件仿真，不需设置硬件。

四、设计原理在各种信号序列中，有限长序列信号处理占有很重要地位，对有限长序列，我们可以使用离散Fouier变换(DFT)。

这一变换不但可以很好的反映序列的频谱特性,而且易于用快速算法在计算机上实现，当序列x(n)的长度为N时，它的DFTN 1 1 N-1X(k)=》x(nW,n⑷x(n)=石送X(kW「n定义为：心，WN =e反换为：N心有限长序列的DFT是其Z变换在单位圆上的等距采样，或者是序列Fourier变换的等距采样，因此可以用于序列的谱分析。

FFT并不是与DFT不同的另一种变换，而是为了减少DFT运算次数的一种快速算法。

它是对变换式进行一次次分解，使其成为若干小点数的组合，从而减少运算量。

常用的FFT是以2为基数的，其长度N=2L，它的效率高，程序简单使用非常方便，当要变换的序列长度不等于2的整数次方时，为了使用以2为基数的FFT,可以用末位补零的方法，使其长度延长至2的整数次方。

在运用DFT进行频谱分析的过程中可能产生几种问题：⑴混叠序列的频谱时被采样信号的周期延拓，当采样速率不满足Nyquist定理时，就会发生频谱混叠，使得采样后的信号序列频谱不能真实的反映原信号的频谱。

避免混叠现象的唯一方法是保证采样速率足够高，使频谱混叠现象不致出现，即在确定采样频率之前，必须对频谱的性质有所了解，在一般情况下，为了保证高于折叠频率的分量不会出现，在采样前，先用低通模拟滤波器对信号进行滤波。

⑵泄漏实际中我们往往用截短的序列来近似很长的甚至是无限长的序列，这样可以使用较短的DFT来对信号进行频谱分析，这种截短等价于给原信号序列乘以一个矩形窗函数，也相当于在频域将信号的频谱和矩形窗函数的频谱卷积，所得的频谱是原序列频谱的扩展。

泄漏不能与混叠完全分开，因为泄漏导致频谱的扩展，从而造成混叠。

为了减少泄漏的影响，可以选择适当的窗函数使频谱的扩散减至最小。

DFT是对单位圆上Z变换的均匀采样，所以它不可能将频谱视为一个连续函数，就一定意义上看，用DFT来观察频谱就好像通过一个栅栏来观看一个图景一样，只能在离散点上看到真实的频谱，这样就有可能发生一些频谱的峰点或谷点被尖桩的栅栏”所拦住，不能别我们观察到。

减小栅栏效应的一个方法就是借助于在原序列的末端填补一些零值，从而变动DFT的点数，这一方法实际上是人为地改变了对真实频谱采样的点数和位置，相当于搬动了每一根尖桩栅栏”的位置，从而使得频谱的峰点或谷点暴露出来。

用FFT可以实现两个序列的圆周卷积。

在一定的条件下，可以使圆周卷积等于线性卷积。

一般情况，设两个序列的长度分别为N1和N2，要使圆周卷积等于线性卷积的充要条件是FFT的长度N> N1 + N2对于长度不足N的两个序列，分别将他们补零延长到N。

当两个序列中有一个序列比较长的时候，我们可以采用分段卷积的方法。

有两种方法：重叠相加法。

将长序列分成与短序列相仿的片段，分别用FFT对它们作线性卷积，再将分段卷积各段重叠的部分相加构成总的卷积输出。

重叠保留法。

这种方法在长序列分段时，段与段之间保留有互相重叠的部分，在构成总的卷积输出时只需将各段线性卷积部分直接连接起来，省掉了输出段的直接相加。

(3)栅栏效应DFT是对单位圆上z变换的均匀采样，所以它不可能将频谱视为一个连续函数，从某种意义上讲，用DFT来观察频谱就如同通过一个栅栏来观看景象一样，只能在离散点上看到真实的频谱，这样一些频谱的峰点或谷点就可能被"尖桩的栅栏"挡住，也就是正好落在两个离散采样点之间，不能被观察到。

减小栅栏效应的一个方法是在原序列的末端填补一些零值，从而变动DFT的点数，这一方法实际上是人为地改变了对真实频谱采样的点数和位置，相当于搬动了"尖桩栅栏"的位置，从而使得频谱的峰点或谷点暴露出来。

⑷DFT的分辨率填补零值可以改变对DTFT的采样密度，人们常常有一种误解，认为补零可以提高DFT的频率分辨率，事实上，DFT的频率分辨率通常规定为©N，这里的N 是指信号X n U勺有效长度，而不是补零的长度。

不同长度的x，n I其DTFT的结果是不同的；而相同长度的X，n I尽管补零的长度不同其DTFT的结果应是相同的，它们的DFT只是反映了对相同的DTFT采用了不同的采样密度。

总结一下：要提高DFT分辨率只有增加信号X，n I的截取长度N。

五、实验内容1、原来的程序下做出的图| QK | Cancel HelpFFT将程序改为四个节点时的程序如下：#include "myapp.h"#include "csedu.h"#include "scancode.h"#include <math.h>#define PI 3.1415926#define SAMPLENUMBER 128 void FFT(float dataR[SAMPLENUMBER],floatdataI[SAMPLENUMBER]){int x0,x1,x2,x3,xx;int i,j,k,b,p,L;float TR,TI,temp;void InitForFFT();void MakeWave();intINPUT[SAMPLENUMBER],DATA[SA MPLENUMBER]; floatfWaveR[SAMPLENUMBER],fWaveI[S AMPLENUMBER],w[SAMPLENUMB ER];float sin_tab[SAMPLENUMBER],cos_tab[S AMPLENUMBER];main(){int i;InitForFFT();MakeWave();for( i=0;i<SAMPLENUMBER;i++ ){ fWaveR[i]=INPUT[i]; fWaveI[i]=0.0f;w[i]=0.0f;}FFT(fWaveR,fWaveI);for( i=0;i<SAMPLENUMBER;i++ ){DATA[i]=w[i];}while ( 1 ); // break pointfollowing code invert sequencefor( i=0;i<SAMPLENUMBER;i++ ){ x0=x1=x2=x3=0;x0=i&0x01; x1=(i/2)&0x01;x2=(i/4)&0x01; x3=(i/8)&0x01;xx=x0*8+x1*4+x2*2+x3;dataI[xx]=dataR[i];}for( i=0;i<SAMPLENUMBER;i++ ){dataR[i]=dataI[i]; dataI[i]=0;}FFTfollowing code for ( L=1;L<=4;L++ ){ /* for(1) */ b=1; i=L-1; while( i>0 ){ b=b*2; i--;} /* b= 2A(L-1) */for ( j=0;j<=b-1;j++ ) /* for (2) */{p=1; i=4-L;while ( i>0p=pow(2,8-L)*j; */{p=p*2; i--;) /*p=p*j;for ( k=j;k<128;k=k+2*b ) /* for (3) */{TR=dataR[k];Tl=datal[k]; temp=dataR[k+b];dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+datal[k+b]*sin_tab[p];datal[k]=datal[k]-dataR[k+b]*sin_tab[p]+datal[k+b]*cos_tab[p];dataR[k+b]=TR-dataR[k+b]*cos_ta b[p]-datal[k+b]*sin_tab[p];datal[k+b]=TI+temp*sin_tab[p]-datal[k+b]*cos_tab[p];} /* END for (3) */} /* END for (2) */} /* END for (1) */for(i=0;i<SAMPLENUMBER/2;i++ ){w[i]=sqrt(dataR[i]*dataR[i]+datal[i] *datal[i]);} } /* END FFT */void ln itForFFT(){int i;for(i=0;i<SAMPLENUMBER;i++ ){sin_tab[i]=si n(PI*2*i/SAMPLENU MBER);cos_tab[i]=cos(PI*2*i/SAMPLENU MBER);}}void MakeWave(){int i;for(i=0;i<SAMPLENUMBER;i++ ){lNPUT[i]=s in( Pl*2*i/SAMPLENUMBER*3)*1024;}}得出的图为:3 3e+4.2 2e+4-1.1 e+4-0--1.1e+4--2.2e+4：程序改为八个节点时：#include ER];"myapp.h" float#i nclude "csedu.h" sin_tab[SAMPLENUMBER],cos_tab[S #in clude "sca ncode.h" AMPLENUMBER];#in clude <math.h>mai n()#define PI 3.1415926 {#defi ne SAMPLENUMBER 128 int i;void In itForFFT();void MakeWave();intINPUT[SAMPLENUMBER],DATA[SA MPLENUMBER]; float fWaveR[SAMPLENUMBER],fWaveI[S AMPLENUMBER],w[SAMPLENUMBIni tForFFT();MakeWave();for(i=O;i<SAMPLENUMBER;i++ ) {fWaveR[i]=INPUT[i];fWaveI[i]=0.0f; w[i]=0.0f;}FFT(fWaveR,fWaveI);for( i=0;i<SAMPLENUMBER;i++ ){DATA[i]=w[i];}while ( 1 ); // break point} void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER]){int x0,x1,x2,x3,x4,x5,x6,x7,xx;int i,j,k,b,p,L;float TR,TI,temp;for ( i=0;i<SAMPLENUMBER;i++ ){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;x7=(i/128)&x01;while ( i>0 ){b=b*2; i--;} /* b= 2A(L-1) */for ( j=0;j<=b-1;j++ ) /* for (2) */{p=1; i=8-L;while ( i>0 ) /*p=pow(2,8-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_ta b[p]-dataI[k+b]*sin_tab[p];xx=x0*128+x1*64+x2*32+x3*16+x4*8+x5*4+x6*2+x7; dataI[xx]=dataR[i];}for( i=0;i<SAMPLENUMBER;i++ ){dataR[i]=dataI[i]; dataI[i]=0;}FFTfor ( L=1;L<=8;L++ ){ /* for(1) */ b=1; i=L-1;dataI[k+b]=TI+temp*sin_tab[p]-dat aI[k+b]*cos_tab[p];} /* END for (3) */} /* END for (2) */} /* END for (1) */for( i=0;i<SAMPLENUMBER/2;i++ ){w[i]=sqrt(dataR[i]*dataR[i]+dataI[i] *dataI[i]);}} /* END FFT */following code invert sequencefollowing codevoid In itForFFT(){int i;for(i=O;i<SAMPLENUMBER;i++ ) {sin_tab[i]=si n(PI*2*i/SAMPLENU void MakeWave(){int i;for(i=0;i<SAMPLENUMBER;i++ ){MBER);cos_tab[i]=cos(PI*2*i/SAMPLENUINPUT[i]=s in( PI*2*i/SAMPLENU MBER*3)*1024;MBER);出的图为得六、总结信号频率和采样频率之间需要满足奈奎斯特采样定理。