离散傅里叶变换

1、第 3 章 离散傅里叶变换在第二章讨论了利用序列的傅里叶变换和z 变换来表示序列和线性时不 变 系 统 的 方 法 ， 公 式 分 别 为 ：X ( z)x( n) z n和nX (e jw )x( n)e jwn 。对于有限长序列，也可以用序列的傅里叶变换和nz 变换来分析和表示，但还有一种方法更能反映序列的有限长这个特点，即离散傅叶里变换。 这就是我们这一章要讨论的问题。 离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外， 而且由于存在着计算离散傅里叶变换的有效快速算法， 因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。这一章讨论的问题有：1、傅里叶变换的

2、几种可能形式：至今学过很多种傅里叶变换形式，到底之间有什么不同，需要分析一下；2、周期序列的离散傅里叶级数(DFS)：通常的周期信号都可以表示成傅里叶级数，然后根据傅里叶级数可以得到傅里叶变换；也就是说傅里叶级数与傅里叶变换之间有一定的关系；3、有限长序列的离散傅里叶变换(DFT) ：这是我们的重点，我们会对其性质等作分析讨论；4、DFT 的应用：学习了这种傅里叶变换，怎么用？计划作一个实验。3.1 傅里叶变换的几种形式傅里叶变换就是建立以时间为自变量的 " 信号 " 与以频率为自变量的 " 频率函数 "之间的某种变换关系。都是指在分析如何综合一个信号时

3、，各种不同频率的信号在合成信号时所占的比重。如连续时间周期信号f (t)f (tmT ) ，可以用指数形式的傅里叶级数来表示， 可以分解成不同次谐波的叠加， 每个谐波都有一个幅值， 表示该谐波分量所占的比重。傅里叶表示形式为：1Tf (t)Fne jn tFn12f (t )ejn t dt （ Fn 离散、衰减、非周期） 。nTT2例如周期性矩形脉冲，其频谱为 Fnsin( n/ T ) ,n 0, 1, 。画出图Tn/ T形。对于非周期信号，如门函数，存在这样的关系式：f (t)1F ( jw)e jwt dwF ( jw)f (t)e jwt dt ，时域非周期连续，2频率连续非周期。画

4、出图形。例如序列的傅里叶变换，变换关系为：X (e jw )x(n)e jwn，nx( n)1X (ejw )e jwn dw ，时域为非周期离散序列，频域为周期为22的连续周期函数。以上三种傅里叶变换都是符合傅里叶变换所谓的是建立以时间为自变量的 "信号 " 与以频率为自变量的" 频率函数 " 之间的某种变换关系。不同形式是因为时间域的变量和频域的变量是连续的还是离散而出现的。这三种傅里叶变换因为总有一个域里是连续函数，而不适合利用计算机来计算。 那么如果时间域里是离散的， 而频域也是离散的， 就会适合在计算机上应用了，那么傅里叶变换会是什么形式？见书

5、上90 页图形，可见时域和频域都对应为序列的形式。3.2 周期序列的离散傅里叶级数（DFS）回顾一下，对于周期信号，通常都可以用傅里叶级数来描述，如连续时间周期信号f (t )f (tmT ) ，用指数形式的傅里叶级数来表示为f (t)Fne jn t ，可以看成信号被分解成不同次谐波的叠加，每个谐波n都有一个幅值， 表示该谐波分量所占的比重。其中 e j t 为基波， 基频为 =22rN ) ， /T（ T 为周期）。设 x (n) 是周期为 N 的一个周期序列， 即 x (n) = x (nr 为任意整数，用指数形式的傅里叶级数表示应该为jkw0 n，x (n) =X k ek其中 0=2

6、 /N 是基频，基频序列为 e jw0 n 。下面来分析一下第（K+rN ）次谐波 e j (krN )w0n 和第（ k ）次谐波 e jkw 0n 之间的关系。因为 0=2 /N ，代入表达式中，得到 e j (krN )w0n = e jkw 0 n ， r 为任意整数。这说明第（K+rN ）次谐波能够被第（ k）次谐波代表，也就是说，在所有的谐波成分中，只有N 个是独立的，用N 个谐波就可完全的表示出到 N-1 。这x(n) 。 K 的取值从 01N1 jkw 0n1是为了计算的方便而加入的。样 x(n) =N kX k e，N0下面来看看Xk 如何根据 x(n) 来求解。先来证明复指

7、数的正交性：N 121,kr为整数j ()( k r )n，注意该表达式是对 neN0, 其它n 0求和，而表达式的结果取决于（k-r ）的值。1N1 jkw0 nj (2 / N ) rn，并且从 n=0到 n=N-1在 x(n) =X k e两边都乘以 eN k0求和，得到N 1 j (2 / N )rnN 1 1N 1 j ( 2 / N )( k r )n交换求和顺x (n)eX k en 0n 0 N k 0N 1序，再根据前面证明的正交性结论可以得出：j (2 / N ) rnx (n)eX (r ) ，n 0N12knjN换一个变量， 有 X (k ) =x (n)e，从 X (

8、k ) 的表达式可以看出X (k )n0也是周期为 N 的周期序列，即(k)N ) 。X= X (k31 N1jkw0 nx (n) =X k eN k 0为周期序列的傅里叶级数对X ( k)N1=x(n) e2j knNn 0在上面的傅里叶级数对中，n 和 k 的范围是从 -到。为了表示的方便，引入变量WNe j ( 2/ N ) ，N 表示周期。重新写上面的级数对。讨论如下内容：1） WNe j ( 2 / N ) ，以 N 为周期。 WNNk1， WN2WN/2；2）求和只对序列的一个周期的值进行，但求出的 X ( k ) 或 x(n) 却是无限长的；3）由 x (n) 以 N 为周期推

9、导出X ( k) 以 N 为周期；rN ) ，因为 z 变换不收敛，所以不能用4）对于周期序列 x(n) =x (nz 变换，但若取 x( n)的一个周期， 则 z 变换是收敛的。 X (z)nx (n) z，n当 取 zej ( 2/ N ) kX (ejw)X ( z) |z e jw ， 当时 ，X (z) X (k ) ， 而w (2/ N )k 时， X (ejw) = X ( k ) ，这相当于在 =0 到 =2的范围内，以 2 /N 的频率间隔在 N 个等间隔的频率上对傅里叶变换进行采样。5）引入主值序列的概念，即序列在0N-1区间的序列称为主值序列。举例：例 1 求(n rN

10、) ，对x(n) 的 DFS 系数。设 x (n) 为周期冲激串x (n) =r于 0 nN-1 ， ( )x n =(n) ，可以求出 X (k) =N1(n)WNkn =1，即对于所n 0有 的k 值 ，(k) 均 相 同 。Xx (n) 表 示 成 级 数 形 式 为41 N 1kn1 N 1j (2 / N )kn1, n rN 。x( n) = r(n rN )= N k 0 WNN k 0 e= 0,其它例 2 设()N=10 ，在主值区间内，在 5xn 的周期为0n 4 时， x(n) =1 n 9 时 ，=0。 画 出x (n)x( n) 的 图 形 ， 则X (k) =44j

11、 (4 k / 10) sin( k / 2)knej (2/ 10) kn= e(k ) 的幅W10sin( k /10)，画出 Xn 0n 0值图。X(±1)=3.23 ，X(± 2)=0XXXX (0)=5 ，(± 3)=1.24 ，(± 4)=0， (±5)=1 ，X (± 6)=0， X(± 7)=1.24 ， X (± 8)=0 ， X (± 9)=3.23 ，这是一个周期内的值。设 n 取 514，即不是取主值周期，随便取一个周期，计算傅里叶级数X 2 (k ) ，得到的结果和在主值周期中的

12、结果X (k ) 一样。下面计算有限长序列x( n) =1,0n4的傅里叶变换。0,5n941eX (e jw )x( n)e jwn =e jwn =nn 01ej 5w jwej (5 / 2) wsin(5w / 2)，如果将 =2 k/10代入上式， 则结果和(k) 一样。=j (1 / 2 ) wsin(w / 2)XeX (e jw ) 的幅度一个周期图如下所示：5可以看出 X ( k) 相当于在 =0 到 =2 的范围内，以2 /10 的频率间隔在10 个等间隔的频率上对傅里叶变换进行采样。例 3 例题中得到这样一个结论，对于以 N 为周期的周期序列x(n) ，任取一个周期求得的

13、傅里叶系数）中求得的X 2(k ) 与 x (n) 在主值区间（ n=0N-1傅里叶系数(k)X 1相 同 。 现 在 已 知 x (n) 的 周 期 为 N ，N 1( k) =X1x (n)en 02m2jknN，(k ) =X 2n m1j2knN， m1=rN+n1，x (n) em2=rN+n1+N-1 ， 0n1 N-1 ，证明 X1 (k ) = X 2 (k ) 。 rN n1 N 1证 明 ： X 2 (k ) =nrNn1x (n) ej 2knN（ 令n-m=rN或m=n-rN ）j ( 2 ) k( m rN )=rN )eNx (mn1 N12mkN 1n1N1j()

14、() （后一个分量作变量=Nm-N=n ）x (m)em n1m n1mNn1 1n1 1=(n N )k=nkx (n N )WNx( n)WNn0n0N1=nk(k )x ( n)WN = X 1no(n)例 4（留作作业） x的周期为 N，其 DFS 系数为 X ( k) 。 X ( k) 也是周期为 N 的周期序列，试利用x(n) 求 X (k ) 的 DFS 系数。N 1解：(k )nkX=x (n)W Nn o6N 1 kr=N1N1knkr=N 1 N 1k(n r )X (r ) =X (k )WN x ( n)WNWNx (n) WN，k 0k 0 n 0n 0k 0N 1N

15、 , n r lNk (n r )，所以rlN )r ) 。WN0, 其余X(r ) = Nx (Nx (k 03.3 离散傅里叶级数（DFS ）的性质离散傅里叶级数的某些性质对于它在信号处理问题中的成功使用至关重要，因为 DFS与 z 变换和序列的傅里叶变换关系密切， 所以很多性质和 z 变换的性质相似，而 DFS 是和周期性序列联系在一起， 所以存在一些重要差别。 另外，在 DFS表达式中时域和频域之间存存在着完全的对偶性，而在序列的傅里叶变换和z 变换的表示式中这一点不存在。考虑两个周期序列n(n)(n)(k)x1x2，其周期均为N，若x1X 1，( ) 、2( k)x2(n)X1、 线

16、性(n)a x1(n) +b x22、 序列的移位(k ) ，周期也为 N。由定义式证明。a X1( k) +b X 2kmx (n)X (k ) ，那么 x (n m)WNX (k ) 。证明：N1nk=x (nm)WNn0N 1 mN 1kiWNmk(i m n) W Nmkkimkx(i )WNx (i )WNWN X (k )i mi 03、 调制特性因为周期序列的傅里叶级数的系数序列也是一个周期序列，所以有类似的 结 果 ， l为整数，有nlWNx( n)X ( k l ) 。 证 明 ：7N 1N1nl kn( k l ) nWN x( n)WNx (n)WNX (k l ) 。n

17、 0n04、 对称性给出几个定义：1） 共扼对称序列()*() 的序列满足xenxe (n)xe n2） 共扼反对称序列满足 xo (n) =xo* (n) 的序列 xo (n)3） 偶对称序列、奇对称序列若 xe (n)和 xo (n)为 实 序 列 ， 且 满 足 xe (n) = xe (n) 和xo (n) =xo (n) 。4） 任何一个序列都可表示成一个共扼对称序列和一个共扼反对称序列之和（对实序列，就是偶对称序列和奇对称序列之和）。即有x(n) = xe (n) + xo (n) ，其中xe (n) =（ x(n) + x* ( n) ） /2， xo (n) =（ x(n) -

18、 x* ( n) ） /2下面为对称性：*(n) *(*( n)xXk ) ； x/2Re(X ( k)*(n) ）X( k) ； xe (n) = （ x( n) + xN 1N 10证明： *knkn *=km *（任意一个x(n)WN x(n)WNx ( m)WN n 0n 0m 1 N周 期 的DFS系数和主值区间中的DFS系数是一样的）N 1 *km*( k ) ；= x ( m)WNXm 0N1N10*knkn*=kn' *=x(n)WNx (n)WNx (n' )W Nn0n0n' 1N8N 1 *kn '*(k) ； x (n')WN=

19、Xn '0N 1 knN11 *kn1 *( k) =xe ( n)WN( x (n)x(n)WN X (k ) +Xn 0n 0 22Re( X (k )5、 周期卷积如果( k)·(k)，Y ( k )=X1X2则N 1N 1(n m) =(nm) ；这是一个卷积和公y(n)x1(n) x2x2(m) x1m 0m 0式，但与线性卷积有所不同，首先在有限区间0 m N-1 上求和， 即在一个周期内进行求和；对于在区间0m N-1 以外的 m 值，()nmx2的值在该区间上周期的重复。看书上95 页的图解周期卷积。证明：见书 94 页。3.4 非周期序列和周期序列的一般关系

20、非周期序列（非周期序列不一定是有限长序列）具有傅里叶变换X (e jw ) 的形式，周期序列的 DFS 系数对应于 X (e jw ) 在频率上等间隔的采样。9考虑非周期序列x(n) 的傅里叶变换为X (ejw) ，并且假定序列X (k )是通过对 X (ejw)在 2 k / N 频率处采样得到的 （即 X (k) 是构造出来的一个序列），即jw) | w ( 2 / N )k = X (ej ( 2/ N ) k)X (k ) = X (e因为傅里叶变换是w 的周期函数，周期为2 ，所以得出的序列是k 的周期函数，周期为N 。这样，可以看出样本序列X (k ) 是周期序列，周期为N ，它可

21、以是一个序列(n) 的离散傅里叶级数的系数序列。为得到xx(n) ，可以将X (k) 代入公式中：1N1kn，已经假定存在x(n) 的傅里叶变换， 所x (n) =X (k )WNN k 0以X (e jw )=x( m)em= X (ejw)| w(2 / N )kX (k)jwm，借助=X ( e j ( 2 / N ) k ) ， 有1 N 1j ( 2 / N )kmkn1 N 1k (n m)x(m)eW N=x(m)WN ，x( n) =N k 0mmN k 01N 11,n mrN根据WN k( nm)，0, 其它N k 0x(nrN ) =x(nx( n) =rN ) 。由此可

22、以看出与 X (k ) 对应的周期序rr(n) 是 把无数 多个平移后的 x(n) 加 在一起 而形成的列 x， X ( k) 是 对X (ejw) 采样而得到的。x(n) 的N 为序列 X (k) 的周期，而不是非周期序列长度 M 。这样就可能出现这种情况，当序列(k ) 的周期 N 大于非周期序X10列 x( n) 的长度M 时，延时后的x(n) 序列没有重叠在一起，并且周期序列x( n) 的一个周期就是x(n) ，这时符合一个周期序列的傅里叶级数系数就是一个周期上的傅里叶变换的抽样值。如果 N<M 时，平移后的 x(n) 序列相互 ( )重 叠 ， x n 的 一 个 周 期 不

23、再 与 x(n) 的 周 期 相 同 ， 但 式 子jw) | w(2/ N )k = X (ej (2 / N ) k) 依然成立。这和我们讨论过X (k) = X (e的时域采样定理有点类似，当 N M 时，原来的序列 x( n) 可以从 x (n) 中抽取一个周期来恢复，同样，傅里叶变换X (e jw ) 也可以从频率上以 2 /N 等间隔的采样来恢复。当N<M 时，序列x(n) 就不能从 x (n) 中抽取一个周期来恢复， X (ejw ) 也不能由它的采样来恢复。这主要是采样的点数不够。但只要 x(n) 是有限长的，就可以选择采样点数，避免混叠。也就是说，只要x( n) 是有限

24、长， 就没有必要知道在所有频率处的X (e jw ) 值。若给出一个有限长序列 x(n) ，就能根据()x(n rN ) 形成一个周期序列，从而可xn =r以用傅里叶级数来表示。另外，如果给出傅里叶系数X (k ) ，就可以求出x( n) ，取出其主值序列得到x(n) 。当利用傅里叶级数以这种方式来表示有限长序列时，就称它为离散傅里叶变换（DFT ），所以在讨论或应用DFT 时应明白， 通过傅里叶变换的采样值来表示， 实际上是用一个周期序列来表示有限长序列，该周期序列的一个周期就是我们要表示的有限长序列。113.5 有限长序列的傅里叶表示：离散傅里叶变换（ DFT ）上面讨论了x(nrN )

25、，即有限长序列可看作是周期序列x (n) =r的一个周期。周期序列和有限长序列的关系可表示成：(n) = x(n) N ，xN 的x( n) x (n) RN (n) ；同样离散傅里叶级数系数X (k) 也是一个周期为周期序列，我们将与有限长序列x( n) 相联系的傅里叶系数选取为与X (k )的一个周期相对应的有限长序列，则有以下关系：X (k ) = X (k ) N ，(k) 。X (k) = X ( k ) RN1N 1 jkw0nX ( k) 和 x (n) 相 联 系 的 关 系 式 为 ： x (n)=X k e，Nk 0N1j2knN0(N-1)，因为两个式子中的求和都只涉及到

26、这个区X (k) =x (n)en0间，所以根据前面有限长序列和周期序列的关系可以得到：X ( k) = N1x( n)WNkn RN (k ) 和 x(n) =1 N 1X ( k)WN kn RN (n) ， 即n0N k 0(k)，x(n) =()RN (n)。这意味着： 对于区间 0k N-1X (k) = X ( k ) RNxn之外的 k， X (k) =0。而且，对于区间 0 nN-1 之外的 n， x( n) =0。注意：对于有限长序列时域和频域的关系式中蕴含有周期性，从关系可以看出其实有限长序列都是式 X (k ) = X (k) RN (k) ，x(n) = x ( n)

27、RN (n)作为周期序列的一个周期来表示，隐含有周期性意义。当利用12x( n) =1 N 1X (k )WN kn RN (n) 式子来计算 x(n) 时，如去掉后缀 RN (n) ，那N k 0么对于0 nN-1 之外的 n， x(n) 并不等于零，而是x(n) 的周期延拓。只是我们感兴趣的x(n) 的值只是在 0nN-1 区间内， 因为 x( n) 在该区间之外的确为零，并且认为所感兴趣的X (k) 值也只是在区间 0k N-1 内，因为在式子 x(n) =1 N 1()knRN(n) 中只需要这些值。Xk WNN k 0隐含周期性：假设长为N 的序列 x(n) 是由对 x(t) 取样得

28、来的，则频域上已经意味着以s2/ T 为周期作周期延拓。现对频域X (e jw ) 作等间隔取样， 则时间序列 x(n) 按周期 N 延拓为 x (n) ，因此利用 DFT 对 x(n)的时间序列展开，相当于对此序列作周期性处理。由以上的讨论可见，DFT的时域和频域都是有限长的、离散的，故可利用计算机完成两者间的变换，这是DFT 的最大优点之一。例：为了说明有限长序列的DFT ，考虑有限长序列x(n) =1 ， 0 n 4 ，x( n) =0，n 为其它值时，画图。在确定DFT 时，我们可以将x(n) 看作是一个长度 5 的任意有限长序列（如长度为6 或 10 等等）。设想 x(n) 为长度为

29、 N=5 的序列，周期序列 ( )x n 在所有 n 上取值都为 1，画图。13根据公式，可以得到：N 1j ( 2 / N )kn1 ej (2/ N ) kNN , k 0, N , 2Ne等，即只有在X (k) =1 e j ( 2 / N) k0, 其它n 0k=0 和 k=N 的整数倍处才有非零的DFS 系数。画出图形。在上面的图中画出对应的采样值。 x(n) 的 5 点 DFT X (k ) 对应于抽取X (k ) 的一个周期而得到的有限长序列。画出图形。 只有在 k=0 时，有一个值为5，其它点上为0。如果考虑将 x(n) 换成长度 N=10 的序列，则基本的周期序列情况为：x

30、(n)，然后开始下的一个周期中， 0n 4 时， x (n) =1， 5n 9时， x (n) =0一个周期。这时得到的X ( k) 上图中 02 中进行等间隔采样的10 个点。3.6 离散傅里叶变换的性质由于 DFT 是从 DFS 中得来的， 所以很相像， 都是根据有限长序列 DFT 的隐含周期性得出。1） 线性注意特殊情况下如何定线性组合后序列的长度。以长度大的为周期。2） 序列的圆周 /循环移位定义： y( n)x(nm) N RN (n)（ 1） 与线性移位、周期移位作比较（ 2） 理解：14将x(n) 拓 成(n) ， 将m 位 得xx ( n) 右 移x(nm)x (nm) =N

31、，取主值；一端出另一端进，因为是有限长；均匀分布在一个圆上，顺时针或逆时针旋转3） 圆周 /循环移位定理若DFTx(n)=X(k),y( n)x(nm) N RN ( n)，则DFTy(n)= WNmk X(k)形式与 DFS 的周期移位相同， 表明序列圆周移位后的DFT 为 X (k )乘上相移因子 WNmk ，即时域中圆周移m 位，仅使频域信号产生 WNmk的相移，而幅度频谱不发生改变，即|WNmk X (k) |=| X ( k ) |4） 对称性见书上 100 页，和 DFS 中讨论的相似，都是按照 DFS 来解，然后取主值区间值即可。对着书把这些性质理一遍。然后看书上例题 3-1。书

32、上习题6：解：（1）要使所有的X (k ) 为实数，即要求X * (k) =X (k ) ，对应*(n)时域则有 xx (n)。从图可见，x (n) 为实序列，所以要求x (n) = x ( n) 。所以选择图（ b）；（ 2）要使所有的X (k ) 为虚数，即要求X * ( k) = (1) X (k ) ，对应时域有*x( n) =- x (n) 。从图可见，x (n) 为实序列，所以要求 x( n) =- x (n) 。所以没有选择；（ 3 ） (a)和（ c）满足。待入到X ( k ) 的公式中计算。 (a)图，15321(1)kejkn，当 k= ± 2，±X (

33、 k) =8=j k4， 时， X (k ) =0；n01e4(c) 图对应 (a)图序列减去（a）图序列平移 4位后的序列，所以(1ejkX c (k ) X a ( k) 。结果 =0。时域里移 4 位（左移），频域乘以 WN4k ， N=8 ，看作是右移也可以，答案一样。5） 圆周卷积和 /循环卷积定理x1 (n) 和 x2 (n) 的长度都为 N，如果 Y(k)=X 1 (k) X 2 (k ) ，则N1y(n) x1 (m) x2 (nm)N RN (n)m 0N1x2 (m) x1 (nm) N RN ( n)m 0x1 (n)x2 (n)根据定理可以求出圆周卷积， 当然求圆周卷积

34、， 可以借助 DFT 来计算，即 IDFTY(k)=y(n)。可见圆周卷积与周期卷积的关系，在主值区的结果相同，所以求圆周卷积是可以把序列延拓成周期序列，进行周期卷积，然后取主值的方法来求。也可以根据圆周移位的理解来做，见下面例题：例 1 ： 令 x2 (n) 为 长 度 是 N 的 有 限 长 序 列 ， 且x1 (n) =( n n0 ),0n0N ，则 x1 ( n) 可以看作为一个长度为N 的0,0 nn0有 限 长 序 列 ， 定 义 为 x1 (n) = 1, n n0，0, n0 nN1x1 (n)X1 ( k)WNkn0 ，如果X 3 ( k) = X 1 (k ) X 2 (k ) =WNkn0 X 2 (k) ，则x3 (n) = x2 (nn0 ) ，即 x3 (n) 是 x2 (n) 在 0 nN-1内顺时针旋转n0 个取样间隔得到的序列。16将 x2 (n) 放在一个内圆周上，将x1 (n) 放在外圆周上，零点重合，然后进行顺时针旋转，看结果。与上面分析一样的结果。( ) =1,0n L 1例 2：，若 N=L ，则 N 点 DFTx2 nx1 ( n)0, 其它为N1WNknN , k 0X 1 (k )X 2 ( k)X1(k) 和 X2(k) 直接相，如果将n00,其它乘，得X 3 (k ) =