数字信号处理实验报告6_离散傅里叶变换及其快速算法.doc

..页脚....实验六离散傅立叶变换及其快速算法一、实验目的:掌握快速傅立叶变换的应用方法;掌握离散余弦变换的应用方法;掌握Z变换的应用方法;了解Chipz变换的基本概念;掌握Hilbeit变换的初步应用;了解倒谱变换的基本概念。二、实验仪器:电脑一台,。三、实验内容:(FFT)DFT是信号分析与处理中的一种重要变换。但是直接计算DFT的运算量与变换的长度N的平方成正比,当N较大时,计算量太大。在快速傅里叶变换(简称FFT)出现之前,直接用DFT算法进行谱分析和信号的实时处理是不实际的。FFT使得DFT的运算效率大大提高,为数字信号处理技术应用于各种信号的实时处理创造了条件,推动了数字信号处理技术的发展。..页脚....FFT算法的MATLAB实现MATLAB提供fft函数来计算x(n)的DFT,fft函数是有机器语言,而不是以MATLAB指令格式写成的,因此它的执行速度很快。格式:y=fft(x),计算信号x的快速傅里叶变换y。当y为矩阵(多通道信号)时,计算x中每一列信号的离散傅里叶变换。当x的长度为2的幂时,有基2算法,否则采用较慢的分裂基算法。Y=fft(x,n),计算n点FFT,当x的长度大于n时,截断x否则补零。Y=fft(x,n),计算n点FFT,当x的长度大于n时,截断x,否则补零。IFFT可由ifft函数来计算。在信号处理中,DFT的计算具有举足轻重的地位,,信号的相关、滤波、谱估计等都要通过DFT来实现。然而,当N很大的时候,求一个N点的DFT要完成NN?次复数乘法和)1(?NN次复数加法,其计算量相当大。,构造了一个DFT快速算法,即快速傅立叶变换(FFT)。概念通过前面的知识,已经知道有限列长为N的序列)(nx的DFT变换为nknNnWnxkX????10)()(12,1,0??Nk?其逆变换为..页脚....?????10)(1)(NknkNWkXNnx1,1,0??Nn?由于MATLAB软件本身的特点,序列或向量元素下标从1开始记录,而不是从0开始。因此,上述两式在MATLAB中相应的表达式为nknNnWnxkX????10)()(12,1,0??Nk?????11)(1)(NknkNWkXNnx1,2,1??Nn?而下面所讨论使用的快速傅立叶变换)(FFT并不是与DFT不同的另外一种变换,而是为减少DFT计算次数的一种快速有效的算法。这种快速算法,主要是利用了nkNW下面两个特性使长序列的DFT分解为更小点数的DFT所实现的。利用nkNW的对称性使DFT运算中有些项合并?????)()(knNknNnNkN)()()(nNkNNnkNnkNWWW????快速傅立叶变换)(FFT算法正是基于这一基本思想而发展起来的。快速傅立叶变换算法形式很多,但是基本上可以分为两大类,即按时间抽取(Decimation-In-Time,简称DIT)法和按频率抽取(Decimation-In-Frequency)法。在这里,以时间抽取)(DIT的FFT算法(库利-图算法)为例,简单说明一下FFT算法的算法原理。..页脚....为了讨论方便,设?2?N,其中?为整数。如果不满足这个条件,可以认为得加上若干零点来达到。由DFT的定义知nknNnWnxkX????10)()(12,1,0??Nk?其中)(nx是列长为)11,0(??NnN?的输入序列,把它按n的奇偶分成两个序列??????)()12()()2(21rxrxrxrx12,1,0??Nr?又由于22222NNjNjNWeeW???????,则??????????102110)()()()()(NnnkNnkNnknNnnkXWkXWnxWnxkX为奇数为偶数上式表明了一个N点的DFT可以被分解为两个N/2点的DFT。同时,这两个N/2点的DFT按照上式又可以合成为一个N点的DFT。为了要用点数为N/2点的X1(k)、X2(k)来表达N点的X(k)值还必须要用W系数的周期性,即)2(22NkrNrkNWW??这样可得???????202021)2(211)()()2(NrNrrkNNkrNWrxWrxkNX即X1()()21kXkN??同理可得X2()()22kXkN??..页脚....另外再加上WkN的对称性kNkNNNkNNWWWW?????2)2(就可以将X(k)的表达式分为前后两个部分:前半部分)()()(21kXWkXkXkN??12,1,0??Nr?后半部分)2()2()2(2)2(1kNXWkNXkNXkNN??????)()(21kXWkXkN??12,1,0??Nr?由以上分析可见,只要求出区间?????