08 FFT实验.docVIP

快速傅立叶变换（FFT）实验 一 实验目的 了解FFT的原理； 了解使用Matlab语言实现FFT的方法； 了解在DSP中FFT的设计及编程方法； 熟悉对FFT的调试方法； 二 实验内容 本试验要求使用FFT变换求一个时域信号的频域特性，并从这个频域特性求出该信号的频率值。使用Matlab语言实现对FFT算法的仿真，然后使用DSP汇编语言实现对FFT的DSP编程。 三 实验原理 对于有限长离散数字信号{x[n]}，0≤x≤N-1，它的频谱离散数学值{X（K）}可由离散傅氏变换（DFT）求得。DFT定义为： k=0,1,…,N-1 也可以方便的把它改写成如下形式： 式中WN（有时简写为W）代表。不难看出，是周期性的，且周期为N，即 m，l=0，±1，±2，…… Wnk的周期性是DFT 的关键之一。为了强调起见，常用表达式WN取代W以便明确地给出Wnk的周期为N。 由DFT的定义可以看出，在x[n]为复数序列的情况下，完全可以直接运算N点DFT需要次复数乘法和N（N-1）次复数加法。因此，对于一些相当大的N值（如1024点）来说，直接计算它的DFT所需要的计算量是很大的。一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成一个N点的复序列，然后对复序列进行N点的FFT运算，最后再由N点复数输出拆散成2N点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT输出一致。 FFT的基本思想在于：将原来的N点序列分成两个较短的序列，这些序列的DFT可很简单地组合起来得到原序列的DFT。例如，若N为偶数，将原有的N点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约[（N/2）2*2]=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）2表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点DFT（假定N/2为偶数），从而又少作一半乘法。使用这种方法，在组合输入和拆散输出的操作中，FFT的运算量减半。这样，利用实数FFT算法来计算实输入序列的DFT的速度几乎是一般复FFT算法的两倍。 假定序列{x[n]}的点数N是2的幂，按上述处理方法，定义两个分别为x[n]的偶数项和奇数项的（N/2）点序列x1[n]和x2[n]，即： x1[n]=x[2n] n=0，1，…，（N/2）-1 x2[n]=x[2n+1] n=0，1，…，（N/2）-1 {x[n]}的N点DFT可写成： + （n为偶数） （n为奇数） = + 因考虑到可写成： = = = 故X（k）可写为： + = 式中和是和的（N/2）点DFT。上式表明，N点DFT X（k） 可分解为按上式的规则加以组合的两个（N/2）点DFT。 四．FFT的DSP实现 通过上述原理分析可知：对于点的FFT运算是非常有规律的，可以同过下面3个循环来完成。 FOR L＝1 To m For k＝0 To 2L-1-1 For i=k To 2m-1 Step 2L J=I+2L-1 式4－1 Next I Next k Next L 上面的语句中m为FFT运算的级数，k为每一级运算中每个子DFT运算中蝶形运算的个数，I为每一级运算过程中子DFT运算的个数。这里利用伪代码的形式来说明FFT运算的规律。在用实际的编程语言实现FFT算法时，要注意式4－1需要通过中间变量进行缓存，并且、和是复数形式。在第1次循环时式4－1中的的值是原始序列x（n）经过码位倒序排列后的数据，经过上面的三重循环后最后放在中的数正好对应X（k）的值。 考虑到式（4－1）是复数运算，令： （4－2） （4－3） 则式（4－1）可以化为： （4－4） 上述过程是实现一个蝶形运算的迭代过程。为了用DSP控制器来实现上述过程，还需要考虑数据的大小以免发生溢出。假设原始时间序列x（n）已经进行了归一化，即为Q15的格式（最高位为符号位，其余是小数位）。可以推出，式（4－1）或式（4－4）可能的最大值为： 这将超出Q15的格式范围。因为很多情况下是实数的FFT，这个值不超过2，因此在每一级用因子2进行归