一、实验目的
1、掌握FFT算法和卷积运算的基本原理；
2、掌握用C语言编写DSP程序的方法；
3、了解利用FFT算法在数字信号处理中的应用。
二、实验设备
    1.    一台装有CCS软件的计算机；
    2.    DSP实验箱的TMS320C5410主控板；
    3.    DSP硬件仿真器。
三、实验原理
（一）快速傅里叶变换
傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。离散傅里叶变换（DFT）是傅里叶变换在离散系统中的表示形式。但是DFT的计算量非常大， FFT就是DFT的一种快速算法, FFT将DFT的N2 步运算减少至 ( N/2 )log2N步。
    离散信号x(n)的傅里叶变换可以表示为　
，　
式中的WN 称为蝶形因子，利用它的对称性和周期性可以减少运算量。一般而言，FFT算法分为时间抽取（DIT）和频率抽取（DIF）两大类。两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。本实验以时间抽取方法为例。
时间抽取FFT是将N点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。这样x(n) 的N点DFT可写成：
    考虑到WN的性质，即
    因此有：
    或者写成：
    由于X1(k) 与X2(k) 的周期为N/2，并且利用WN的对称性和周期性，即：
    可得：
对X1(k) 与X2(k)继续以同样的方式分解下去，就可以使一个N点的DFT最终用一组2点的DFT来计算。在基数为2的FFT中，总共有log2(N) 级运算，每级中有N/2 个2点FFT蝶形运算。
单个蝶形运算示意图如下：
    以N＝8为例，时间抽取FFT的信号流图如下：
    从上图可以看出，输出序列是按自然顺序排列的，而输入序列的顺序则是“比特反转”方式排列的。也就是说，将序号用二进制表示，然后将二进制数以相反方向排列，再以这个数作为序号。如011变成110，那么第3个输入值和第六个输入值就要交换位置了。一种比较常用有效的方法就是雷德算法。
（二）卷积运算
卷积是数字信号处理中经常用到的运算。其基本的表达式为：   
编写实现程序时需要注意两点：（1）序列数组长度的分配，尤其是输出数组y (n) 要有足够的长度；（2）循环体中变量的位置，即n和m的关系。
（三）IDFT的FFT实现
    IDFT与DFT的关系为
即
    那么直接调用FFT子程序计算IDFT的方法是：
（四）线性卷积的FFT实现
    当有限长序列x(n)与h(n)的圆周卷积长度L≥N+M时，其中N、M分别为x(n)和h(n)的长度，L点的圆周卷积能够代表它们的线性卷积，即x(n)h(n)=x(n)*h(n)。再利用DFT的圆周卷积性质
x(n)h(n)=IDFT{X(k)H(k)}
就可以利用FFT计算两个有限长序列的线性卷积。
（五）分段卷积
直接利用DFT计算的缺点是：(1) 信号要全部输入后才能进行计算，延迟太多；(2) 内存要求大；(3) 算法效率不高。解决问题方法是采用分段卷积，分段卷积可采用重叠相加法和重叠保留法来实现。
1. 重叠相加（overlap add）
将长序列x[k] 分为若干段长度为L的序列
其中
记 ，那么，
y0[k]的非零范围为，y1[k-L]的非零范围为。序列y模块电源图片0[k]、y1[k]的重叠部分为，重叠的点数L+M-2-L+1=M-1。依次将相邻两段的M-1个重叠点相加，即得到最终的线性卷积结果。
2.重叠保留法(overlap save)
方法：
(1) 将x[n]长序列分段，每段长度为L； 
(2) 各段序列xn[k]与 M点短序列h[k]循环卷积；
(3) 从各段循环卷积中提取线性卷积结果。
因 yn[k]=xn [k] L h[k] 前M-1个点不是线性卷积的点，故分段时每段与其前一段有M-1个点重叠。
记yn[k] =xn [k]h[k]，y0[k]中的[M-1, L-1]点对应于线性卷积x[k]*h[k]中的[0 , L-M]点，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。