第三章离散傅里叶变换及其快速算法ppt课件

.,1,第三章,离散傅立叶变换,.2004,讨论：,实际当中，我们在计算机上实现信号的频谱分析时，要求：时域、频域都是离散的；时域、频域都是有限长的；FT、FS、DTFT、DFS都不符合要求，但我们可以利用DFS的时域、频域周期性，各自取一个周期，就形成新的变换对：DFT,.2004,3.2离散傅立叶变换（DFT),3.2.1有限长序列的离散傅立叶变换一.DFT的定义长度为N的序列x(n)其频谱为在上从0开始等间隔的取N个点，相应的（k=0,N-1),则上式变为,.2004,（k=0,N-1),令,并采用记号,可得有限长序列x(n)(n=0,1,2,N-1)的离散正反傅立叶变换,.2004,离散傅立叶变换，简称DFT傅立叶反变换，简称IDFT,（k=0,N-1),（k=0,N-1),.2004,二.周期性以及与DFS的关系,1.余数运算表达式如果，m为整数；则有：,.2004,此运算符表示n被N除，商为m，余数为。是的解,或称作取余数,简称为对n取模值N。,例如：N=8N=16,.2004,2.有限长序列x(n)和周期序列的关系有限长序列x(n)是周期序列的主值序列，而是x(n)的周期延拓。,.2004,3.周期序列与有限长序列的关系同样，周期序列是有限长序列的周期延拓而有限长序列是周期序列的主值序列。,.2004,DFT与Z变换的关系长度为N的序列x(n)其Z变换：与傅立叶变换相比较有：,.2004,可见序列的N点DFT是x(n)的Z变换在单位圆上N点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其DFT的值也不同。,.2004,3.2.2DFT的一些性质,一.线性性,若x(n)与y(n)是同样长的序列，则对任何实数或复数有,.2004,二.循环移位性质如果那么,.2004,图3-2-1循环移位示意图,.2004,证明：令n+m=nl,则有,.2004,同理可证明频域移位定理：若则=,.2004,三.共轭复序列的DFT设为的共轭复序列，则证明：,.2004,四.共轭对称性,用和分别表示实部与虚部序列的DFT:,.2004,共轭对称性：共轭反对称性：,.2004,由于x(n)和均是有限长序列，其定义区间为（0N-1），注意，与在第二章中的对称性不同，这里所谓的对称性是指关于N/2点的对称性，而不是关于原点的对称，见右图。,图3-2-2关于N/2点的共轭对称性,.2004,若x(n)为实序列，则其DFT满足共轭对称特性若x(n)为纯虚序列，则其DFT满足共轭反对称性,.2004,五.循环卷积定理设和是两个具有相同长度N的有限长序列，定义循环卷积：n=0,N-1记为同时满足交换率,.2004,循环卷积定理；若，则,.2004,同理可以证明频域卷积定理：若则,.2004,六.循环相关定理n=0,N-1,设两个有限长实序列,具有相同的长度N,称为序列的循环互相关,.2004,循环相关定理：若，则有,.2004,当x(n)=y(n)时，称为序列的循环自相关,是有限长序列的离散功率谱，注意,中没有相位的信息。,.2004,七.帕思瓦定理(Parseval)帕思瓦定理的离散傅立叶变换形式,.2004,证明：=,.2004,当x(n)=y(n)时，则有：说明时域中的能量与频域中的能量相等,.2004,3.3频域采样定理,频域采样是指对一有限序列（时间有限序列）进行DFT所得x(k)，也就是序列傅氏变换的采样。频域采样定理讨论两个基本问题：a：频域采样（DFT）不失真恢复的条件，即由X(k)不失真地恢复x(n)的条件b：用X(k)表示X(z)和的插值公式,.2004,1.频域采样不失真恢复x(n)的条件：采样点数N必须大于序列的长度L假定x(n)的长度为L（没有限制）频率采样=0kN-1令=IDFTX(k)（0nN-1）,由于=DFS=IDFS=,.2004,因而有取主值区=故有由上式可知，是原序列的周期延拓周期为N，然后取主值，如图3-3-1所示。,.2004,图3-3-1时域恢复示意图,结论：若序列长度为L，频域采样点数（或DFT的长度）为N，且LN，则频域采样后不能不失真地恢复原序列。,.2004,2.用表示和的内插公式（1）用表示设序列长度为N，由傅里叶变换对得=,.2004,=,其中,.2004,（2）用表示的内插公式将分别代入式（3-3-6）和（3-3-7），即可得到用表示的内插公式如下=其中=,.2004,例：已知=,01,对的z变换在单位圆上等间隔采样N点，k=0，N-1，求IDFT。解：,.2004,3.4DFT的快速算法FFT,3.4.1时域抽曲基-2FFT算法（DIT-FFT）所谓基-2是指要求长度N满足（M为整数），若不满足可将序列补零延长，使其满足。FFT运算分为：,.2004,1.算法的推导按n的奇偶把时间序列x(n)分解为两个长为N/2点的序列，即因此,.2004,由于所以即其中分别为的N/2点DFT这是前N/2点DFT,.2004,图3-4-1蝶式运算图,那么后N/2的DFT：由于（周期性）因此我们用蝶式运算图来表示上述前N/2和后N/2两式，如图3-4-1所示,.2004,3.FFT算法的特点（1）倒码码位倒置是指将原二进制数的码位倒过来按从低位到高位排列如：序号4用3位二进制表示正常码为100倒码为001，变成了1顺序与倒序对照表如下：,.2004,.2004,（2）原位运算利用同一存储单元存放蝶式运算输入和输出数据的方法。（3）DIF-FFT算法其他形式的流图输入的数据为正序，输出是倒码排列。如下图所示,.2004,.2004,3.4.2频域抽取基-2FFT算法(DIF-FFT)1.算法：,.2004,由于N点DFT按k的奇偶分组可分为两个N/2的DFTk取偶数时（k=2r，r=0,1,.,N/2-1）,.2004,k取奇数时（k=2r+1，r=0,1,.,N/2-1)2.蝶形运算和进行如下蝶形运算,.2004,如下图：x(n)x(n)+x(n+N/2)x(n+N/2)x(n)-x(n+N/2)3.N=8时,按k的奇偶分解过程先蝶形运算,后DFT,.2004,如下图：,.2004,4.DIF-FFT的二次分解将N/2点DFT按k的奇偶分解为两个N/4点的DFT，如此进行直到分解为2点DFT,如下图：,.2004,例如:N=8时的DFT,可以分解为两个N/2=4点DFT如图所示:,.2004,由于,因而N/2仍是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列从而可表示为,.2004,因而有其中对也可进行同样的分解：k=0,1,.,N/4-1,.2004,其中这样又一次的分解得到4个N/4点DFT,.2004,如下图所示：那么依次类推，经过M-1次分解后，将N点DFT分解成N/2个两点DFT,.2004,下图为N=8时的一个完整基-2DIT-FFT运算流图,.2004,2.运算量当N=时，总共有M级分解，每级有N/4个蝶式运算。每个蝶式运算需一次复乘两次复加，这样M级总共需要的运算量为复乘次数复加次数,.2004,3.4.3逆DFT的快速算法（IFFT）,1.比较DFT与IDFT的计算公式比较两式可知只要将FFT中的旋转因子为，再乘以1/N即可得到IDFT的快速算法IFFT。,.2004,另外，可将常数1/N分配到每级运算中，因为，也就是每级蝶形运算均乘以1/22.直接利用FFT程序因为所以,.2004,两边取共轭有：此方法只需要一个FFT程序即可进行正逆变换的快速计算。,.2004,FFT（IFFT）算法的实现：1.纯软件实现2.硬件实现3.DSP（软硬件结合）,.2004,3.4.4N为合数的FFT算法1.算法的实现长度N是复合数，共V个因子。令其中将x(n)每隔点抽取一点,.2004,序列x(n)的N点DFT为将代入，则,.2004,令则由于继续令如此进行下去直到最后变为点的DFT,.2004,2.算法的运算量第一次抽取后：代替N，代替第二次抽取后:最后总运算量：,.2004,3.5DFT与FFT的应用DFT和FFT在信号和信息处理的各个领域都具有广泛的应用。本节主要介绍它们在频域分析、卷积与相关计算中的应用，并讨论chirp-z变换及其快速算法,.2004,3.5.1利用FFT计算序列的频谱一.利用FFT进行频谱分析的基本方法极坐标表示：幅度谱：相位谱：,.2004,FFT对模拟信号进行频谱分析的框图如下：,.2004,1.频率分辨率：2.模拟频率分辨率：3.用于FFT的点数：4.频率刻度值：5.模拟信号长度：6.分辨率：,.2004,例3-5-1,用FFT来计算信号的频谱，已知信号的最高频率为，要求频率分辨率为，试确定：1.采样间隔T；2.采用基-2FFT的最小样点数N，以及与此相对应的最小记录长度；3.按你确定的参数所获得的实际分辨率。,.2004,解：(1)按采样定理，采样间隔T：(2)基-2FFT的最小样点数N：,.2004,当采用基-2FFT算法时，要求：与此相对应的最小记录长度为：（3）按确定的参数所获得的实际分辨率：,.2004,二.用FFT进行频谱分析存在的问题1.频谱泄漏解决办法：采用其它形式的窗函数,在实际应用中，通常将所观测的信号限制在一定的时间间隔内,也就是说在时域对信号进行截断操作,或称作加时间窗,亦即用时间窗函数乘以信号,由卷积定理可知，时域相乘,频域为卷积,这就造成拖尾现象,称之为频谱泄漏.,.2004,2.栅栏效应用DFT计算频谱时，只是知道为频率的整数倍处的频谱。在两个谱线之间的情况就不知道,这相当通过一个栅栏观察景象一样，故称作栅栏效应。解决办法：补零点加大周期，可使F变小来提高辨力，以减少栅栏效应。,.2004,3.5.2用FFT计算线性卷积1.利用循环卷积计算线性卷积的条件设是x(n)和y(n)长为L的循环卷积：其中所以,.2004,利用循环卷积计算线性卷积如下图：,.2004,利用FFT进行线性卷积的步骤如下：1.将序列x(n)和h(n)补零延长，使其长度若采用基-2FFT，还应使L大于或等于的2的最小整数次幂。2.做x(n)和h(n)的长为L点的FFT得到X(k)和Y(k)，求它们的积Y(k)=X(k)H(k)3.求Y（k）的IFFT并取前N1点获得线性卷积的结果为,LN1=N+M-1,N1,=IFFT，0nN,.2004,二.长序列FFT卷积的计算方法1.重叠相加法h(n)长度为N，x(n）长度为无限长，取M与N尽量接近x(n)与y(n)的卷积为,.2004,重叠相加法的卷积示意图：,.2004,重叠相加法的步骤如下：3.计算，并求长为L的反变换，即4.将的重叠部分相加，最后得到结果为,1.将补零延长到L=M+N-1，并计算长为L的FFT，得到,2.分别将补零延长到L=M+N-1，并计算长为L的FFT，得到,.2004,2.重叠保留法,.2004,输入的每段序列重叠N-1点，而每段的循环卷积的输出只保留了M点,.2004,3.5.3用FFT计算线性相关1.循环相关也线性相关的关系线性相关：取非零值的长度为,.2004,循环相关：若则那么,.2004,上述结果说明，在0nN-L范围内，循环相关与线性相关相等,若相关输出长度为N1，相关序列长度为L，为了利用循环相关得到正确的线性相关性结果，那么循环相关的长度N至少应取,N=N1+L-1,.2004,2.利用FFT计算相关函数的方法步骤：1.FFT的长度N满足且2.补零延长，构造周期为N的序列3.分别做的N点FFT计算后求其反变换,.2004,3.用FFT计算长序列相关函数的分段求和法当信号序列很长时，FFT长度很长这不利于信号的实时处理，因此为了提高速度采用分段求和法进行设输出的相关长度为，记录信号y(n)的长度为L=JP,.2004,则有：那么,.2004,总结分段法求和的步骤如下：1.分段补零，做2.分别计算长度为的3.4.作和需做J-1次N/2点复加5.求需一个N点