第03章-2 离散傅里叶变换及其性质.ppt

第03章离散傅里叶变换及其快速算法,邹江zoujiang,3.2离散傅里叶变换及其性质,3.2.1离散傅里叶变换DFT有限长序列的傅里叶变换称为离散傅里叶变换，简写为DFT。DFT可以按3个步骤由DFS推导出来①将有限长序列延拓成周期序列；②求周期序列的DFS；③从DFS中取出一个周期便得到有限长序列的DFT。,将xn延拓成周期为N的周期序列,如上图所示。,显然有,的第一个周期，即n＝0到N-1的序列称为主值序列，n0到,N-1的范围称为主值区间。,上述两式可分别表示为,其中RNn是矩形序列。符号nN表示n对模N的余数，即,这里k是商。,同理，可以认为周期序列的DFS系数是有限长序列Xk周期延拓的结果，而Xk是的主值序列。即,由此便可以得出有限长序列的离散傅里叶变换DFT的表示式为,由此可见，有限长序列xn的DFT即Xk仍是有限长序列。,在一般情况下，Xk是一个复量，可表示为,或,式中,例3.1求有限长序列,的DFT，其中a0.8，N8。,解,因此得,X04.16114X10.71063-j0.92558X20.50746-j0.40597X30.47017-j0.16987,X40.46235X50.47017j0.16987X60.50746j0.40597X70.71063j0.92558,Matlab实现fft1.m,将xn的Z变换,与xn的DFT,进行对比，可以看出,式中，,表示z平面单位圆上辐角,k0,1,N-1的N个等间隔点。,Z变换在这些点上的取样值就是Xk。在图3.4b中的虚线包络是单位圆zejω上的Z变换，即傅里叶变化Xejω。,关于离散傅里叶变换DFT,序列xn在时域是有限长的长度为N，它的离散傅里叶变换Xk也是离散、有限长的长度也为N。n为时域变量，k为频域变量。离散傅里叶变换与离散傅里叶级数没有本质区别，DFT实际上是离散傅里叶级数的主值，DFT也隐含有周期性。离散傅里叶变换DFT具有唯一性。DFT的物理意义序列xn的Z变换在单位圆上的等角距取样。,3.2.2离散傅里叶变换的性质,DFT隐含着周期性，因此在讨论DFT的性质时，常与DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。设x1n和x2n的长度都为N，且它们对应的DFT分别为X1k和X2k。,1．线性,设x3nax1nbx2n，a和b都为常数，则,若它们长度不等，取长度最大者，将短的序列通过补零加长，注意此时DFT与未补零的DFT不相等。此性质可以直接由DFT的定义进行证明。,2．对称性,最常遇到的是实序列。设xn是一个长度为N的实序列，且DFT[xn]Xk，则有,这意味着,或,这就是说，实序列的DFT系数Xk的模是偶对称序列，辐角是奇对称序列。对于复序列也有相应的共轭对称性。,3．序列的循环移位,一个长度为N的序列xn的循环移位定义为,循环移位分3步计算,1将xn延拓成周期为N的周期序列；2将移位得或xnmN；3对xnmN取主值得xnmNRNn。这个过程如下图所示。,从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移m个样本时，从右边会同时移进m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名“循环移位”。显然，循环移位不同于线性移位,动画演示,序列循环移位后的DFT为,证明由周期序列的移位性质得,因xnmNRNn是的主值序列，所以它的DFT就是,的主值，即,根据时域和频域的对偶关系，可以得出,若,则,4．循环卷积,设YkXlkX2k，则,或,由上式表示的卷积称为循环卷积，常记为,证明,利用DFT的隐含周期性，将Yk周期延拓计算后再取主值m取值的0N-1范围是主值区间，故因此,循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。,循环卷积的计算可用图3.6来说明。在图3.6a中，x1n的N个值按顺时针方向均匀分布在内圆周上，x2n的N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到y0。若将外圆周顺时针方向转动一格如图3.6b所示，将内外圆周上对应的数值两两相乘并把乘积相加，便得到y1。依次类推，可以得出yn的其它值。因此循环卷积也叫做圆卷积。,图3.7表示的是序列x1n和x2n的4点即N4循环卷积的计算过程。图中，x1nδnδn-1δn-2，x2n＝δn1.5δn-12δn-22.5δn-3。,这一计算过程分5步1周期延拓2折叠3移位和取主值4相乘5相加,动画演示,考虑到DFT关系的对偶性，可以证明，长为N的两序列之积的DFT等于它们的DFT的循环卷积除以N，即,3种卷积线性卷积线性卷积不受主值区间限制点击观看动画周期卷积循环卷积是周期卷积取主值，在一定条件下与线性卷积相等。两个长度都为N的因果序列的循环卷积仍是一个长度为N的序列，而它们的线性卷积却是一个长度为2N-1的序列。点击观看动画,