8点DIFFFT算法基于MATLAB实现.docxVIP

《信号分析与处理》课程设计说明书  PAGE \* MERGEFORMAT 20 摘要 快速傅里叶FFT是将一个大点数N的DFT分解为若干小点的DFT的组合。工作量会明显降低，从而大大提高离散傅里叶变换DFT的运算速度。因而各个学科技术领域广泛的使用了FFT技术，她大大推动了信号处理技术的进步，现已成为数字信号处理强有力的工具，而DIF是FFT算法中按频率抽取的方法。本课设比较全面的叙述快速傅里叶变换中DIF的算法、原理、特点，并完成了基于MATLAB的实现。 关键词：快速傅里叶变换FFT、MATLAB、DIF 1 FFT算法简介及原理特点 1.1 FFT算法简介 快速傅立叶变换（FFT）并不是一种新的变换，而是离散傅立叶变换（DFT）的一种快速算法。 DFT的计算在数字信号处理中非常有用。例如在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)计算h(n)，这就要计算DFT；信号的谱分析对通信、图像传输、雷达等都是很重要的，也要计算DFT。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大。 自从1965年图基（J. W. Tukey）和库利（T. W. Coody）在《计算数学》（Math. Computation , Vol. 19, 1965）杂志上发表了著名的《机器计算傅立叶级数的一种算法》论文后，桑德(G. Sand)-图基等快速算法相继出现，又经人们进行改进，很快形成一套高效运算方法，这就是快速傅立叶变换简称FFT（Fast Fourier Transform）。这种算法使DFT的运算效率提高1~2个数量级。 1.2 基2 FFT算法原理特点 1.2.1直接计算DFT的问题 设x(n)为N点有限长序列，其DFT正变换为 = ， k=0，1，…，N-1 其反变换(IDFT) x(n)= ，n=0，1，…，N-1 二者的差别只在于的指数符号不同，以及差一个常数乘因子1/N，因而下面我们只讨论DFT正变换的运算量，反变换的运算量是完全相同的。考虑x(n)为复数序列的一般情况，每计算一个X(k)，需要N次复数乘法以及（N-1）次复数加法。因此，对所有N个k值，共需N2次复数乘法及N（N-1）次复数加法运算。所以直接计算DFT，乘法次数和加法次数都是和N2成正比的，当N很大时，运算量是很可观的，因而需要改进对DFT的计算方法，以减少运算次数。 1.2.2改进的途径及DIF的引出 下面讨论减少运算工作量的途??。仔细观察DFT的运算就可看出，利用系数以下固有特性，就可减小DFT的运算量： （1）的对称性 （）*= （2）的周期性 == （3）的可约性 == 由此可得：==，=-1，=-。这样利用这些特性，可以将长序列的DFT分解为短序列的DFT。快速傅立叶变换算法正是基于这样的思路而发展起来的。它的算法基本上可以分成两大类：时域抽取法FFT（DIT-FFT）和频域抽取法FFT（DIF-FFT）。 2 按频率抽选DIF的基2 FFT算法 2.1 DIF的原理 设序列点数为N=2M ，M为整数。 ＝ ，k=0，1，…，N-1 先把输入按n 的顺序分成前后两半： ＝ ，k=0，1，…，N-1 =+ =+ =，k=0，1，…，N-1 1，k为偶数 =(-1)k= -1，k为奇数 将X（K）分解成偶数组与奇数组， 当k取偶数即k=2r时（r=0，1，…，N/2-1）， == 当k取奇数即k=2r+1时（r=0，1，…，N/2-1）， = = 令 n=0，1，…，N/2-1 =，r=0，1，…，N/2-1 = x1(n)、x2(n)和x(n)之间可用下图所示的蝶形运算符号表示： -1 图2.1 用下图表示，N=8的一次分解流图： 图2.2 由于N=2M，N/2仍是偶数，继续将N/2点DFT分成偶数组和奇数组。图2.3表示N=8时二次分解运算流图： 图2.3 最后完整的分解流图为下图： 图2.4 这种算法是对X（K）进行奇偶抽取分解的结果，所以称之为频域抽取法FFT。 DIF-FFT算法与DIT-FFT算法类似，不同的是DIF-FFT算法输入序列为自然顺序，而输出为倒序排列。另外，蝶形运算略有不同，DIT-FFT蝶形先乘后加，而DIF-FFT蝶形先加后乘。 上述两种FFT的算法流图形式不是唯一的。只要保证各节点所连支路及其传输系数不变，改变输入与输出点以及中间结点的排列顺序，就可以得到其他变形的FFT运算流图。 2.2 DIF的特点 1.