离散傅里叶变换.doc

第3章 离散傅里叶变换在第二章讨论了利用序列的傅里叶变换和z变换来表示序列和线性时不变系统的方法，公式分别为：和。对于有限长序列，也可以用序列的傅里叶变换和z变换来分析和表示，但还有一种方法更能反映序列的有限长这个特点，即离散傅叶里变换。这就是我们这一章要讨论的问题。离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外，而且由于存在着计算离散傅里叶变换的有效快速算法，因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。这一章讨论的问题有：1、 傅里叶变换的几种可能形式：至今学过很多种傅里叶变换形式，到底之间有什么不 同，需要分析一下；2、 周期序列的离散傅里叶级数(DFS)：通常的周期信号都可以表示成傅里叶级数，然后根据傅里叶级数可以得到傅里叶变换；也就是说傅里叶级数与傅里叶变换之间有一定的关系；3、 有限长序列的离散傅里叶变换(DFT)：这是我们的重点，我们会对其性质等作分析讨论；4、 DFT的应用：学习了这种傅里叶变换，怎么用？计划作一个实验。3.1 傅里叶变换的几种形式傅里叶变换就是建立以时间为自变量的信号与以频率为自变量的频率函数之间的某种变换关系。都是指在分析如何综合一个信号时，各种不同频率的信号在合成信号时所占的比重。如连续时间周期信号，可以用指数形式的傅里叶级数来表示，可以分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。傅里叶表示形式为：（Fn离散、衰减、非周期）。例如周期性矩形脉冲，其频谱为。画出图形。对于非周期信号，如门函数，存在这样的关系式：，时域非周期连续，频率连续非周期。画出图形。例如序列的傅里叶变换，变换关系为：，时域为非周期离散序列，频域为周期为2的连续周期函数。以上三种傅里叶变换都是符合傅里叶变换所谓的是建立以时间为自变量的信号与以频率为自变量的频率函数之间的某种变换关系。不同形式是因为时间域的变量和频域的变量是连续的还是离散而出现的。这三种傅里叶变换因为总有一个域里是连续函数，而不适合利用计算机来计算。那么如果时间域里是离散的，而频域也是离散的，就会适合在计算机上应用了，那么傅里叶变换会是什么形式？见书上90页图形，可见时域和频域都对应为序列的形式。3.2 周期序列的离散傅里叶级数（DFS）回顾一下，对于周期信号，通常都可以用傅里叶级数来描述，如连续时间周期信号，用指数形式的傅里叶级数来表示为，可以看成信号被分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。其中为基波，基频为=2/T（T为周期）。设是周期为N的一个周期序列，即=，r为任意整数，用指数形式的傅里叶级数表示应该为=，其中0=2/N是基频，基频序列为。下面来分析一下第（K+rN）次谐波和第（k）次谐波之间的关系。因为0=2/N，代入表达式中，得到=，r为任意整数。这说明第（K+rN）次谐波能够被第（k）次谐波代表，也就是说，在所有的谐波成分中，只有N个是独立的，用N个谐波就可完全的表示出。K的取值从0到N-1。这样=，是为了计算的方便而加入的。下面来看看如何根据来求解。先来证明复指数的正交性： ，注意该表达式是对n求和，而表达式的结果取决于（k-r）的值。在=两边都乘以，并且从n=0到n=N-1求和，得到 交换求和顺序，再根据前面证明的正交性结论可以得出：，换一个变量，有=，从的表达式可以看出也是周期为N的周期序列，即=。为周期序列的傅里叶级数对=在上面的傅里叶级数对中，n和k的范围是从-到。为了表示的方便，引入变量，N表示周期。重新写上面的级数对。讨论如下内容：1），以N为周期。，；2）求和只对序列的一个周期的值进行，但求出的或却是无限长的；3）由以N为周期推导出以N为周期；4）对于周期序列=，因为z变换不收敛，所以不能用z变换，但若取的一个周期，则z变换是收敛的。，当取时，而，当时，=，这相当于在=0到=2的范围内，以2/N的频率间隔在N个等间隔的频率上对傅里叶变换进行采样。5）引入主值序列的概念，即序列在0N-1区间的序列称为主值序列。举例：例1 求的DFS系数。设为周期冲激串=，对于0nN-1，=，可以求出=1，即对于所有的k值，均相同。表示成级数形式为=。例2 设的周期为N=10，在主值区间内，0n4时，=1，在5n9时，=0。画出的图形，则=，画出的幅值图。(0)=5，(1)=3.23，(2)=0，(3)=1.24，(4)=0，(5)=1，(6)=0，(7)=1.24，(8)=0，(9)=3.23，这是一个周期内的值。设n取514，即不是取主值周期，随便取一个周期，计算傅里叶级数，得到的结果和在主值周期中的结果一样。下面计算有限长序列=的傅里叶变换。=，如果将=2k/10代入上式，则结果和一样。的幅度一个周期图如下所示： 可以看出相当于在=0到=2的范围内，以2/10的频率间隔在10个等间隔的频率上对傅里叶变换进行采样。例3 例题中得到这样一个结论，对于以N为周期的周期序列，任取一个周期求得的傅里叶系数与在主值区间（n=0N-1）中求得的傅里叶系数相同。现在已知的周期为N，=，=，m1=rN+n1，m2=rN+n1+N-1，0n1N-1，证明=。证明：=（令n-m=rN或m=n-rN）= =（后一个分量作变量m-N=n）= =例4（留作作业）的周期为N，其DFS系数为。也是周期为N的周期序列，试利用求的DFS系数。解：= =，所以=。3.3 离散傅里叶级数（DFS）的性质 离散傅里叶级数的某些性质对于它在信号处理问题中的成功使用是因为DFS与z变换和序列的傅里叶变换关系密切，所以很多性质和z变换的性质相似，而DFS是和周期性序列联系在一起，所以存在一些重要差别。另外，在DFS表达式中时域和频域之间存存在着完全的对偶性，而在序列的傅里叶变换和z变换的表示式中这一点不存在。考虑两个周期序列、，其周期均为N，若，1、 线性a+ba+b，周期也为N。由定义式证明。2、 序列的移位 ，那么。证明：=3、 调制特性因为周期序列的傅里叶级数的系数序列也是一个周期序列，所以有类似的结果，为整数，有。证明：。4、 对称性给出几个定义：1） 共扼对称序列满足的序列2） 共扼反对称序列满足=的序列3） 偶对称序列、奇对称序列若和为实序列，且满足=和=。4） 任何一个序列都可表示成一个共扼对称序列和一个共扼反对称序列之和（对实序列，就是偶对称序列和奇对称序列之和）。即有=+，其中=（+）/2，=（-）/2 下面为对称性： ；=（+）/2 证明：=（任意一个周期的DFS系数和主值区间中的DFS系数是一样的）=； =； +=5、 周期卷积如果=，则=；这是一个卷积和公式，但与线性卷积有所不同，首先在有限区间0mN-1上求和，即在一个周期内进行求和；对于在区间0mN-1以外的m值，的值在该区间上周期的重复。看书上的图解周期卷积。3.4 非周期序列和周期序列的一般关系非周期序列（非周期序列不一定是有限长序列）具有傅里叶变换的形式，周期序列的DFS系数对应于在频率上等间隔的采样。考虑非周期序列x(n)的傅里叶变换为，并且假定序列是通过对在频率处采样得到的（即是构造出来的一个序列），即=|=因为傅里叶变换是w的周期函数，周期为2，所以得出的序列是k的周期函数，周期为N。这样，可以看出样本序列是周期序列，周期为N，它可以是一个序列的离散傅里叶级数的系数序列。为得到，可以将代入公式中：=，已经假定存在的傅里叶变换，所以=，借助=|=，有=，根据，=。由此可以看出与对应的周期序列是把无数多个平移后的加在一起而形成的，是对采样而得到的。N为序列的周期，而不是非周期序列的长度M。这样就可能出现这种情况，当序列的周期N大于非周期序列的长度M时，延时后的序列没有重叠在一起，并且周期序列的一个周期就是，这时符合一个周期序列的傅里叶级数系数就是一个周期上的傅里叶变换的抽样值。如果NM时，平移后的序列相互重叠，的一个周期不再与的周期相同，但式子=|=依然成立。这和我们讨论过的时域采样定理有点类似，当NM时，原来的序列可以从中抽取一个周期来恢复，同样，傅里叶变换也可以从频率上以2/N等间隔的采样来恢复。当NM时，序列就不能从中抽取一个周期来恢复，也不能由它的采样来恢复。这主要是采样的点数不够。但只要是有限长的，就可以选择采样点数，避免混叠。也就是说，只要是有限长，就没有必要知道在所有频率处的值。若给出一个有限长序列，就能根据=形成一个周期序列，从而可以用傅里叶级数来表示。另外，如果给出傅里叶系数，就可以求出，取出其主值序列得到。当利用傅里叶级数以这种方式来表示有限长序列时，就称它为离散傅里叶变换（DFT），所以在讨论或应用DFT时应明白，通过傅里叶变换的采样值来表示，实际上是用一个周期序列来表示有限长序列，该周期序列的一个周期就是我们要表示的有限长序列。3.5 有限长序列的傅里叶表示：离散傅里叶变换（DFT） 上面讨论了=，即有限长序列可看作是周期序列的一个周期。周期序列和有限长序列的关系可表示成：=，；同样离散傅里叶级数系数也是一个周期为N的周期序列，我们将与有限长序列相联系的傅里叶系数选取为与的一个周期相对应的有限长序列，则有以下关系：=，=。和相联系的关系式为：=，=，因为两个式子中的求和都只涉及到0(N-1)这个区间，所以根据前面有限长序列和周期序列的关系可以得到：=和=，即=，=。这意味着：对于区间0kN-1之外的k，=0。而且，对于区间0nN-1之外的n，=0。注意：对于有限长序列时域和频域的关系式中蕴含有周期性，从关系式=，=可以看出其实有限长序列都是作为周期序列的一个周期来表示，隐含有周期性意义。当利用=式子来计算时，如去掉后缀，那么对于0nN-1之外的n，并不等于零，而是的周期延拓。只是我们感兴趣的的值只是在0nN-1区间内，因为在该区间之外的确为零，并且认为所感兴趣的值也只是在区间0kN-1内，因为在式子=中只需要这些值。隐含周期性：假设长为N的序列是由对x(t)取样得来的，则频域上已经意味着以为周期作周期延拓。现对频域作等间隔取样，则时间序列按周期N延拓为，因此利用DFT对的时间序列展开，相当于对此序列作周期性处理。由以上的讨论可见，DFT的时域和频域都是有限长的、离散的，故可利用计算机完成两者间的变换，这是DFT的最大优点之一。例：为了说明有限长序列的DFT，考虑有限长序列=1，0n4，=0，n为其它值时，画图。在确定DFT时，我们可以将看作是一个长度5的任意有限长序列（如长度为6或10等等）。设想为长度为N=5的序列，周期序列在所有n上取值都为1，画图。根据公式，可以得到：=等，即只有在k=0和k=N的整数倍处才有非零的DFS系数。画出图形。在上面的图中画出对应的采样值。的5点DFT对应于抽取的一个周期而得到的有限长序列。画出图形。只有在k=0时，有一个值为5，其它点上为0。如果考虑将换成长度N=10的序列，则基本的周期序列情况为：的一个周期中，0n4时，=1，5n9时，=0，然后开始下一个周期。这时得到的上图中02中进行等间隔采样的10个点。3.6 离散傅里叶变换的性质由于DFT是从DFS中得来的，所以很相像，都是根据有限长序列DFT的隐含周期性得出。1） 线性注意特殊情况下如何定线性组合后序列的长度。以长度大的为周期。2） 序列的圆周/循环移位定义：（1） 与线性移位、周期移位作比较（2） 理解：l 将拓成，将右移m位得=，取主值；l 一端出另一端进，因为是有限长；l 均匀分布在一个圆上，顺时针或逆时针旋转3） 圆周/循环移位定理若DFTx(n)=X(k), ，则DFTy(n)=X(k)形式与DFS的周期移位相同，表明序列圆周移位后的DFT为乘上相移因子，即时域中圆周移m位，仅使频域信号产生的相移，而幅度频谱不发生改变，即|=|4） 对称性见书上100页，和DFS中讨论的相似，都是按照DFS来解，然后取主值区间值即可。对着书把这些性质理一遍。然后看书上例题3-1。书上习题6：解：（1）要使所有的为实数，即要求=，对应时域则有。从图可见，为实序列，所以要求=。所以选择图（b）； （2）要使所有的为虚数，即要求=，对应时域有=-。从图可见，为实序列，所以要求=-。所以没有选择； （3）(a)和（c）满足。待入到的公式中计算。(a)图，=，当k=2，4，时，=0；(c)图对应(a)图序列减去（a）图序列平移4位后的序列，所以。结果=0。时域里移4位（左移），频域乘以，N=8，看作是右移也可以，答案一样。5） 圆周卷积和/循环卷积定理 和的长度都为N，如果Y(k)=，则根据定理可以求出圆周卷积，当然求圆周卷积，可以借助DFT来计算，即IDFTY(k)=y(n)。可见圆周卷积与周期卷积的关系，在主值区的结果相同，所以求圆周卷积是可以把序列延拓成周期序列，进行周期卷积，然后取主值的方法来求。也可以根据圆周移位的理解来做，见下面例题：例1：令为长度是N的有限长序列，且=，则可以看作为一个长度为N的有限长序列，定义为=，如果=，则=，即是在0nN-1内顺时针旋转n0个取样间隔得到的序列。将放在一个内圆周上，将放在外圆周上，零点重合，然后进行顺时针旋转，看结果。与上面分析一样的结果。例2：=，若N=L，则N点DFT为 ，如果将X1(k)和X2(k)直接相乘，得 =，由此可得=N，0nN-1。也可以画图旋转来解答。 以上两个例题都是根据DFT来计算圆周卷积，用定义式无疑较难，用图形旋转功能也有限。 考虑上面的例2，我们可以把和看作是2L点序列，只要增补L个零即可。现在来计算增长序列的2L点圆周卷积。计算出结果。然后计算一下和的线性卷积，看结果与前面2L点圆周卷积结果关系。假设L=4，则2L=8，则线性卷积和根据定义式有y(n)=，0m3,0n-m3,得出0n6。当0n3时,0mn，y(n)=n+1；当4n6时，n-3m3，y(n)=7-n。计算8点圆周卷积，结果和线性卷积一样。后面我们会证明一般情况下的结论。3.7 有限长序列的线性卷积和圆周卷积已知N，M，作线性卷积y(n)=x1(n)*x2(n)= ，其中0mN-1，0n-mM-1，得出0nM+N-2，即y(n)长度最大为M+N-1。对、分别补零，使之长度为L，然后进行L点周期卷积（圆周卷积等于周期卷积的主值区间）。这样有：=，=，则进行周期为L的周期卷积得=（将其中的N改为L） =（将其中x1(n)换成x1(m)） =（求和之在一个周期，所以x1(m+qL)中只能取q=0） =上式说明了有限长序列、的线性卷积的周期延拓构成了周期序列、的周期卷积，其中和分别是由有限长序列、形成的。这要L满足一定条件，线性卷积就等于周期卷积的主值周期，而这也正好是圆周卷积的结果。也就是说，只要LN+M-1，线性卷积就等于圆周卷积。写出线性卷积和圆周卷积的定义式。因为在实际情况中，除里的多半是信号通过一个线性时不变系统，求输出的信号形式。即实际情况中常常要求线性卷积，而知道圆周卷积可以在某种条件下代替线性卷积，并且圆周卷积有快速算法，所以常利用圆周卷积来计算线性卷积。频域抽样理论在前面我们讨论过周期序列的离散傅里叶级数的系数的值和的一个周期的z变换在单位圆（即序列的傅里叶变换）的N个均匀点上的抽样值相等。这其实就是频域的抽样。因此我们得到一个结论：可以用N个点的X(k)来代表序列的傅里叶变换。但是要注意：不是所有的序列都可以这样。我们已经证明过=，即周期序列可以看作是非周期序列的以某个N为周期进行延拓而成。只有在N大于非周期序列x(n)的长度时，延拓后才不会发生重叠。所以我们要求x(n)为有限长序列，且长度小于等于N，这样我们就可以用来代表X(ejw)。其实的一个周期就可以代表X(ejw)或X(z)。所以我们只看一个周期，即X(k)。分析如何用X(k)来表示X(ejw)或X(z)。有限长序列x(n)（0nN-1）的z变换为 ，而，代入得= =这就是用N个频率抽样值来恢复X(z)的插值公式。上式中把z换成ejw就变成用N个频率抽样值来恢复X(ejw)的插值公式。利用DFT计算模拟信号的傅里叶分析 DFT的主要应用之一就是分析连续时间信号的频率成分，如在语音的分析和处理中语音信号的频率分析有助于音腔谐振的辨识与建模。那么要求我们知道在DFT中代表的频率成分有哪些。 例如，任意画一个X(k)的图形，横坐标为k，纵坐标为X(k)的值，那么k代表的频率是多少？两个离散点间隔代表什么意思？如果是88页所示的图形，则很容易知道信号是由哪些频率的基本信号（正弦信号）合成的。而在X(k)中不容易看出。下面要解决的问题就是分析X(k)上对应的模拟频率。u 有一模拟信号(可以是非周期信号，也可以是周期信号)，我们要用DFT来分析它的频率成分。先对该信号作等间隔采样（如果是非周期信号，则进行截断，取有限长；周期信号，则取一个周期进行采样），采样周期为T，画图，fs=1/T。得到x(nT)。时域离散对应频域的周期延拓，周期为，其实这时的频域曲线就是序列的傅里叶变换X(ejw)。是模拟域角频率，对应的数字域角频率为w=T=2。画出图形。提到奈氏抽样定理。频率是连续的、周期的，为得到X(k)，只需对频率进行等间隔采样即可。取出一个周期，对一个周期进行N点采样。让w=(2/N)k就可以得到X(k)。这样两个离散点间间隔用频率表示为：w0=2/N，这是数字基频。对应的模拟基频为=2。=fs/N，相当于模拟频率为。即频域中两个点的频率间隔为。x(n)d(n)与xN(n)不一定同，体现在长度上利用DFT对连续时间傅里叶变换逼近的全过程 频域离散对应时域的周期延拓，周期为。如何得来？x(n)d(n)是一个有限长序列，令为x(n)，则周期延拓后得到的序列（周期为N）有关系：=，将与时间有关的量换为nT或NT，则周期为NT=N/fs=T0。u 利用DFT计算连续时间信号时可能出现的几个问题（结合上面的图来解释） 频率响应的混叠失真抽样定理要求，一般取。