第三章傅里叶分析(修订)讲解

1、第3章傅里叶分析傅里叶分析是利用傅里叶变换来分析信号的一种通用工具，其实质是将信号分解成若干个不同频率的正弦波之和。它在信号处理的理论和应用中具有重要意义。3.1傅里叶变换概述我们知道，傅里叶变换定义了以时间为自变量的“信号”与以频率为自变量的“频谱函数”之间的某种变换关系，也就是说，傅里叶变换建立了时域和频域之间的联系。所以当自变量“时间”或“频率”取连续值或离散值时，就形成了各种不同形式的傅里叶变换对。一、时间连续、频率连续的傅里叶变换( FT)其傅里叶变换公式为：正变换X(j,)=x(t)e-jl tdt1 二K反变换x(t) =X( j'J)ej td'J2二二连续时间

2、非周期信号 x的傅里叶变换结果是连续的非周期的频谱密度函数X(jQ),如图所示。-3-55 -可见，时域函数的连续性造成频域函数的非周期性，而时域的非周期性造成频谱的连续性。二、时间连续、频率离散的傅里叶变换一一傅里叶级数( FS)周期为T的周期性连续时间函数x(t)可展开成傅里叶级数，其系数为X(jk Q 0), X(jk Q o)是离散频率的非周期函数。x(t)和X(jk a。)组成变换对，其变换公式为：1T/2. .正变换X(jk1,10)=-二x(t)e dt00反变换x(t) = '、X(jkfl0)ejkl-0tk =-二式中，k时一谐波序号；Q 0=2兀/T时一两条相邻的

3、离散谱线之间角频率的间隔;x(t)和X(jkQo)之间的变换关系如图所示。1X6* *】可见，时域函数的连续性造成频域函数的非周期性，而时域函数的周期性造成频域函数的离散化。三、时间离散、频率连续的傅里叶变换一一序列的傅里叶变换( DTFT )1. DTFT的定义序列的傅里叶变换公式为:oCi正变换X(ej ) = '、 x(n)enn j一1 二 i i反变换x(n)= X(e )e d 2 二-二注意:序列x(n)只有当n为整数时才有意义，否则没有定义。由于存在关系DTFTx(n) = X(ej ) = X(z)工因此，序列的傅里叶变换也就是单位圆上的Z变换。x(n)和X(ej3)

4、之间的变换关系如图所示。可见，时域的离散化造成频谱函数的周期性延拓，而时域的非周期性造成频域的连续性。2. DTFT的性质(1) 线性定理DTFTax1(n) bx2(n) =aX1(ej ) bX2(ej ')(2) 时移定理DTFT x(n -n0) = e-j n0X(ej )(3) 频移定理j 0nj( ；."? ：/.0)xDTFT x(n)e = X(e )(4) 对称性定理对于复数序列x(n),则当它满足：x(n)=x*(-n)时，该序列称为 共轲对称序列xe(n);对于实序列而言，此条件变为x(n)=x(-n),即xe(n)又称为偶对称序列。x(n)=-x*(

5、-n)时，该序列称为 共轲反对称序列 xo(n);对于实序列而言，此条件变为x(n)=-x(-n),即x°(n)又称为奇对称序列。任意一个序列总能表示成一个共轲对称序列与一个共轲反对称序列之和，即x( n)= xe(n)+ xo(n)证：欲证明这一点，只需找到x4n)和xo(n)即可，则令1xe(n) x(n) x (-n)21xo(n) ="x(n) -x (-n)2不难看出，这里的Xe(n)与xo(n)分别满足共轲对称与共轲反对称的条件，且二者之和为x(n),由此得证。类似地，序列x(n)的傅里叶变换X(ej ")也可分解成共轲对称与共轲反对称分量之和，即X(

6、ejw)= Xe(g")+ Xo(g").一 ：1：其中，Xe(ej ) =X(ej ) X (e)1Xo(ej ) =5X(ej ) -X (e)有关序列的傅里叶变换的对称性定理，参见P59表3.1.1所示。其中，性质4表明：序列实部的傅里叶变换等于序列傅里叶变换的共轲对称分量；性质5表明：序列虚部乘j后的傅里叶变换等于序列傅里叶变换的共轲反对称分量；反过来，性质6、性质7则表明：序列的共轲对称和共轲反对称分量的傅里叶变换分别等于序列傅里叶变换的实部和 j乘虚部；性质10表明：对于任意实序列x(n),其傅里叶变换X后")满足共轲对称性，且可以得出，实序列傅里叶变

7、换的实部是 3的偶函数，而虚部是 3的奇函数；性质11、性质12表明：实序列x(n)的偶对称序列分量 xe(n)和奇对称序列分量 x0(n)的傅里叶 变换分别为序列x(n)的傅里叶变换的实部和j乘虚部。(5) 卷积定理注意：此处的卷积又称为线性卷积。1. 时域卷积定理若 y(n) = x(n) * h(n),则Y(ej ) =X(ej )H(ej )证：已知y(n); x(n) h(n)= ' x(m)h(n - m)m二：QOY(ej ) =DTFTy(n) = _y(n)e nn 二二二QO oo="% x(m)h(n - m)e-j nn 二.：二 m =二oOQO=&

8、#163; x(m) Z h(n-m)eT8m -：二n ='、x(m) h(n -m)e-j'(n"m)e-j mm =-二n =-二=-x(m)e-j m；'h(n-m)e-j (n'm)m =-： ：n=")= X(ej )H (ej )复习：序列的运算序列的运算包括翻褶、移位、和、积等。(a) 翻褶如果序列为x(n),则x(-n)是以n=0的纵轴为对称轴将序列x(n)加以翻褶。(b) 移位如果序列为x(n),当m为正时，则序列 x(n+m)是指将序列x(n)依次逐项左移 m位；当 m为负时，则右移 m位。(c) 和两序列的和是指同序号

9、(n)的序列值逐项对应相加。(d) 积两序列的积是指同序号(n)的序列值逐项对应相乘。线性卷积的几何意义：若两序列x(n)和h(n)的卷积和定义为y(n); x(n) h(n)二、x(m)h(n - m)m 二，：则卷积的运算过程包含以下四步：C1翻褶：先在坐标系上作出h(m),将h(m)以m=0的纵轴为对称轴翻褶成h(-m);C2移位：将h(-m)移位n,即得h(n-m);注意:h(-m)与h(m)的移位规律恰女?相反，当 n为正时，则右移 n位；当n为负时，则左移n彳立。.相乘：再将相同 m值所对应的h(n-m)和x(m)值相乘；相加：将上述所有对应点的乘积叠加，即得 y(n)值；y(n)

10、值。依次取n=- -, -2, -1, 0, 1, 2,，即可得到全部的y(n)值。II.频域卷积定理若 y(n) = x(n)h(n),则_X(ejU)H(ej( -，duY(ej ) =4© ) H(ej )上述两个卷积定理表明：离散时间序列的时域卷积对应频域相乘，而时域相乘则对应其频域卷积。(6)Parseval (帕塞瓦)定理.21n 小2X( x(n)=X(e 0) do n-o2n H证：二 X(ejej nd . 一2 二-二2 二二、x(n) =，x (n)x(n)八 x (n)n ：n -.： ：n二二二= ；_X(ej ) 、 x (n)ejn d .2"

11、;_n=fJ1 一 ：=X(ej )X (ej )d =f71 X(ej°) 2d© 2n/Parseval (帕塞瓦)定理表明：信号在时域的总能量就等于其频域的总能量。四、时间离散、频率离散的傅里叶变换一一离散傅里叶变换( DFT )除了三种傅里叶变换的形式以外，其实还有一种情况一一时间离散、频率离散的傅里叶变换(即：我们在后续章节中将要介绍的离散傅里叶变换DFT)。由上述讨论的四种傅里叶变换的形式，我们不难得出这样的结论：一个域(时域或频 域)的离散化必然造成另一个域的周期延拓习题：3.1, 3.2, 3.3思考题：P102 3.1, 3.3, 3.43.2周期序列的离

12、散傅里叶级数(DFS)既然一个域的离散化会造成另一个域的周期延拓，我们不妨从周期序列的离散傅里叶 级数开始讨论，然后再讨论可视为是周期序列的一个周期的有限长序列的离散傅里叶变换。 一、DFS的定义1 .周期序列的概念设(帝是周期为N的一个周期序列，即(n) = (n+rN ) , r为任意整数因为在任何z值下，周期序列z变换的和式都不收敛，即Z (n)z = Z |(n) z1 =o0n 二. ： ：n 二二也就是说，周期序列不是绝对可和的，所以不能用Z变换表示。但是，和连续时间周期信号一样，周期序列可以用离散傅里叶级数来表示，也就是用周期为N的复指数序列来表示。2 .周期序列的离散傅里叶级数

13、变换对(1)数学推导(可略，参见教材 P6162)I.(n)的推导周期为N的复指数序列为j(£)n e1(n) = e N其k次谐波序列j(三)kn ek(n)=e N由于j2S(k：rN)nj23kne N =e N , r为任意整数ek rN (n)=ek(n)因而，离散傅里叶级数的所有谐波分量中只有N个是独立的。这里，我们取k=0 (N-1)的N个独立谐波分量来构成 (n)的离散傅里叶级数，即1 Nj 2_ kn(32.1J(n)=NLX(k)eN ,一、式中，X(k)为k次谐波的系数。II.X(k)的推导欲求解系数X(k),就要利用等比级数的求和性质/ N 11 '

14、eN n3,2 二jrnN2 j一rN.2 二j rN一(322)1,r =mN, m为任意整数0, r为其他值.2二 j rn将(321)式两端同乘以e N,然后从n=0 (N-1)的一个周期内求和，则N1产rn'、x(n)e Nn =01NNj三：(k_r)nJ' '、 X(k)e NN n =0 k =0尸1N二 X(k)Nn.j(k -r)n e Nk =0=X(r)工.由性质公式(3.2.2),可知当k r =mN,即 k=r +mN时,1 N 1 j=：(k _r)nv e N =1N n=0又由于 k H(N -1),则m=0,故有k三成立将上式中的r换成

15、k,可得 N 金knX(k)=£ (n)e Nn z0 、通过推导，我们可以看出，周期序列x(n)与其离散傅里叶级数的系数X(k)组成一个 . .变换对，且 X(k)也是一个周期为 N的周期序列。 结论一般，我们习惯采用符号J2Z：L-j ”knWn = e N , W；n = e N 则周期序列的离散傅里叶级数变换公式为：N 二 正变换X(k) = DFS(n) =£ (n)W；nn =0N1 一反变换x(n)=IDFSX(k)X(k)WNN «上述表达式求和时，都只取N个序列值，这表明：虽然周期序列是无限长序列，但只要研究其一个周期(有限长)的性质，则其他周期

16、的性质也就不难得知了，因而周期序列和有限长序列有着本质的联系。3. W；n的性质(简单介绍，参见教材 P63)(1) 周期性(2)对称性WNknWN(kN)n =WNk(nN)W-knkn(N -k)nn (Wn ) - Wn= WNk"(3)正交性(重点强调)1 NZ WNkn =&(k - mN)=，N n/1,0,k = mN, m为任意整数 k*其他值DFS的性质设5)和y(n)均是周期为N的周期序列,且有X(k)= DFS(n) , Y(k) = DFS(n)1 .线性性质 DFSax(n) +by(n) =aX(k) +bY(k)2 .移位性质_ -mk DFSx

17、(n+m) =Wn X(k)(时移)DFSW；l(n) =X(k+l)(频移，又称调制特性)3 .周期卷积(1) 时域卷积N 1换元N A若 f (n)= (n)O (n) =£ (m)(n m)=2 (m)(n m),则m=O令n -m山m卫 F(k)=DFS (n) =X(k) Y(k)证：(可略，参见教材 P63)由于N f(n)=x(n) Oy(n)=£ x(m)y(n-m) m=0则N _J 一F(K)=DFSf(n) =、f (n)W：kn=ON A N J=£ Z (m)(n -m)WNnk n =0 m =0N 1N 1=£ (m)Z (

18、n -m)wNnHkWNmk m =0n =0N 1N 1=X (m)WNmkZ (n -m)wjnum k m z0n=0= X(k)Y(k)注意：此处的卷积为周期卷积。它和前面所介绍的非周期序列的线性卷积的区别在于：参与周期卷积运算的两个序列都是周期为N的周期序列，则其卷积结果仍是一个以N为周期 的周期序列；2求和运算只在一个周期(m=0N-1)的范围内进行。周期卷积的运算过程(参见P64图322):运算在m=0N-1区间内进行，先计算出 n=0, 1,，N-1的卷积结果，然后将所得的 结果进行周期延拓，即可得到所求的整个周期序列。注意:计算过程中，一个周期的某一序列值移出计算区间时，相邻

19、的一个周期的同一位置的 序列值就移入计算区间。(2) 频域卷积由于DFS和IDFS的对称性，同样可以证明：时域周期序列的乘积对应频域周期序列 的周期卷积，即：一 一 一 一，、右 f (n) = x(n)y(n),则 一1 NF(k) = X(K) Y(K)=m X(l)Y(k-1)N i卫N 1£ Y(1)X(k-1)N 7习题：3.4思考题：P102 3.5, 3.63.3 离散傅里叶变换(DFT)一、DFT的定义 由前述讨论可知，周期序列实际上只有有限个序列值有意义，因而其离散傅里叶级数表达式同样也适用于有限长序列，这就得到了我们将要介绍的有限长序列的离散傅里叶变换 。1 .有

20、限长序列和周期序列的关系设x(n)是长度为N的有限长序列。我们可以把它看成是周期为N的周期序列(n)的一个周期，而把(n)看成是以N为周期对x(n)进行周期延拓的结果，则有限长序列x(n)和周期序列(n)之间的关系可表示为x(n)；(n), a0 < n < N -1其他n通常，我们将周期序列 (n)的第一个周期(n=0N-1)定义为“主值区间”，故*何)是(门)对有限长序列进行周期 I图拓，可得到周期列的“主值序列”，且上述关系式可简写为x(n) =x(n)N式中，(n)N表示“ n对N求余数”，或称“ n对N取模值”；n=n1+mN,0Wn1MN_1, m为整数则n1为n对N的

21、余数，无论n1加上多少倍的N,其余数均为n1，也就是说，周期性重复出现的x(n)N数值是相等的。例如， (n)是周期N=9的序列，则n=25、-5的余数分别为n = 25 = 2X9 + 7,即(25)9 = 7n = -5 = -1X9 + 4,即(-5)9= 4因此，x(25) =x(25)9 =x(7),x(-5) = x( - 5)9 = x(4)利用长度为N的矩形序列符号RN(n),即Rn (n)；1,Q则(3.3.1)式又可写成x(n) =x(n)RN (n)每周期序列进行截'取, IM得到有限长序列户列同理，频域周期序列.一、X(k)也可看成是对有限长序列X(k)的周期延

22、拓，而有限长序列X(k)则可看成是周期序列X(k)的主值序列，即X(k)=X(k)N 或 X(k) =X(k)RN(k)2 .有限长序列的离散傅里叶变换对由DFS和IDFS的公式表达式可以看出， 其求和运算分别只限定在 n =0N-1和k = 0N-1 的主值区间内进行，则它们完全适用于主值序列x(n)和X(k)。因此，我们可以类推得到有限长序列的离散傅里叶变换公式为：N 1正变换X(k) = DFT x(n)八 x(n)W；n,0 < k < N -1n z01 N 1反变换x(n) = IDFT X(k) =£ X(k)WN"n,0 <n < N

23、 -1N «习题：3.5, 3.6, 3.7思考题：P102 3.7, 3.8二、DFT的性质由于DFT与DFS之间的密切关系，应注意其性质的异同之处以及与DFT所隐含的周期性之间的关系。1 .线性性质设x1(n)和x2(n)均是长度为N的有限长序列，且有X1(k) =DFTx1(n) , X2(k) = DFTx2(n)则DFT ax1 (n) bx2(n) = aX1 (k) bX2(k)说明:(1) 若x1(n)和x2(n)的长度均为 N,则ax1(n)+bx2(n)的长度也为N;(2) 若x1(n)和x2(n)的长度不等，设分别为N1和 刈，则ax1(n)+bx2(n)的长度

24、应为二者中的最大值，即 N = maxN，N2;例如，当N1<N2,则应取N = N2,且需要在x1(n)的尾部补上N2 - N1个零值点，使其变 为长度为N2的序列，再作 用点的DFT。2 .对称性与前面介绍的序列的傅里叶变换DTFT相似，有限长序列的离散傅里叶变换DFT也具有对称性(又称圆周共轲对称)，且这种对称性与周期序列的共轲对称性密切相关。(1) 时域对称性不难证明(参见教材 P7172的数学推导)：任意一个长度为 N的有限长序列x(n)总可以分解成两个长度相等的圆周共轲对称分量Xep(n)和圆周共轲反对称分量xop(n)之和，即x(n尸 Xep(n) + Xop(n)(3.3

25、.2)其中，(3.3.3)(3.3.4)1Xep(n) =Xe(n)RN(n)=二x(n)N X (N -叽氏 21、 一I -一修Xop(n) =Xo(n)RN(n) =-X(n)N -x (N n)N1RN(n)2式中，式酎和。伯)分别是以N为周期对有限长序列 x(n)进行周期延拓后，所得到的周期序列(n)的共轲对称分量和共轲反对称分量。2 2)频域对称性利用(3.3.2)式、(3.3.3)式及(3.3.4)式，并考虑到 DFT和DFS的关系，就可以推 导出下列DFT的频域对称性质(证明从略，参见教材P7273)。设 X(k) =DFTx(n) = DFT Re x(n) + j Imx(

26、n),则有 DFTx (n) =X (N -k)/ Rn*)这表明：共轲复序列的 DFT等于序列DFT的逆象共轲。 DFTx (N -n) = X (k)N Rn*)这表明：复序列逆象共轲的DFT等于序列DFT的共轲。DFTRex(n) =*即%)DFTj Imx(n) =X.p(k)这表明：复序列实部的DFT等于序列DFT的圆周共轲对称分量；而复序列虚部乘以j的DFT 等于序列DFT的圆周共轲反对称分量。DFTXep(n) = ReX(k)DFTXop(n) = jImX(k)这表明：序列圆周共轲对称分量的DFT等于序列DFT的实部；而序列圆周共轲反对称分量的DFT等于序列DFT的虚部乘以j

27、。 若序列x(n)是实序列，则序列的 DFT只有圆周共轲对称分量，即满足X(k) =X (N -k)NRN (k)若序列x(n)是纯虚序列，则序列的 DFT只有圆周共轲反对称分量，即满足X(k) T (N -k)NR(k)根据该性质，不论属于哪一种情况， 只要知道一半数目的就可以了，另一半可利用对称性求得，这样在计算 DFT时可以节约计算时间，提高效率。3 .循环移位(又称圆周移位)(1) 循环移位的定义有限长序列x(n)左移m (m为正整数)位的循环移位定义为Xm(n) =x(n m)N RN(n)可见，上式的循环移位表示将序列x(n)周期延拓成周期序列(n) = x(n)N后，再左移 m位

28、并取其主值序列而得到的。注意：序列的循环移位始终限定在主值区间内进行。如图所示(P75图3.3.1),有限长序列循环移位的过程中，在主值区间(n=0N-1)内,当某序列值从区间的一端移出时， 与它同值的序列值又从区间的另一端移入，因而，此过程可以看成是将序列 x(n)按逆时针方向排列在一个 N等分的圆周上，则序列循环左移 m位就 相当于将该序列在圆周上顺时针旋转 m位。(2) 时域移位特性利用DFT与DFS的关系以及DFS的时移性质，不难证明：Xm(k) = DFTxm(n) =DFTx(n m)NRN(n) =WN"mkX(k)(3) 频域移位特性由时域与频域的对偶关系，可得IDF

29、TX(k 1)nRn (k) =W：x(n)(4) 环卷积(又称圆周卷积)(1)循环卷积的定义长度土匀为N的有限长序列x(n)和h(n)的循环卷积定义为y(n) =x(n) ® h(n) =x(n)N © h(n)nRn (n)N4' x(m)h(n -m)N Rn (n)(3.3.5),m=0N4h(m)x(n -m)N Rn (n)m=0可见，循环卷积就是周期卷积在主值区间(2) 循环卷积的运算方法n=0N-1)内的值利用求和定义式(3.3.5)直接求解;利用与周期卷积的关系求解；根据循环卷积的特点，利用图解法求解，其步骤如下：I.将序列x(n)按逆时针方向均匀

30、地(N等分)分布在一个圆周(内圆)上，而将序列h(n)按顺时针方向均匀地(N等分)分布在另一个圆周(外圆)上，如图( a)所示；II .求两个圆上相应序列的乘积，并叠加 N项乘积作为n=0时循环卷积值y(0);III .若求n=1时循环卷积值y(1),则将外圆h(n)固定，把内圆上的序列x(n)顺时针旋转一个单位(或将内圆 x(n)固定，把外圆上的序列 h(n)逆时针旋转一个单位，即内、外圆相对旋转一个单位)，并将对应项的乘积叠加，即为所求的y(1)值，如图(b)所示；IV .类似地，依次取n=2N-1,重复步骤出，直到将内圆序列循环移位一周，便可以求得所有的y(n)值;(3) 时域和频域循环

31、卷积定理I .时域循环卷积定理利用DFT与DFS的关系以及DFS的时域周期卷积性质，可以证明：若 y(n) =x(n) h(n),则 Y(k) =X(k)H (k)这表明：两序列循环卷积的离散傅里叶变换等于其傅里叶变换的乘积。II .频域循环卷积定理由时域与频域的对偶关系，可得1 一右 y(n) =x(n)h(n),则 Y(k) =X(k)® H (k)N这表明：两序列乘积的离散傅里叶变换等于其傅里叶变换的循环卷积乘以1/N。(4) 循环卷积、周期卷积和线性卷积的关系利用周期卷积计算循环卷积先计算两序列的周期卷积(列表法，参见例3.2.3),再对卷积结果取其主值区间(n=0N-1)内

32、的值即可。利用循环卷积计算线性卷积I.用循环卷积代替线性卷积的条件设两个有限长序列 x(n)、h(n)的点数分别为N和M,其循环卷积的长度为 L,则要 用循环卷积代替线性卷积的条件是： 循环卷积白长度 L必须不小于线性卷积的长度 N + M-1, 即L/ + M-1否则，在循环卷积周期延拓时会产生混叠。II.用循环卷积实现线性卷积的具体步骤i)根据上述条件，取L=N+M-1,分别将序列x(n)、h(n)补零扩展为L点序列，即ii)iii)性卷积，即x(n)=；x(n)， 0,0<n<N -1，h(n)=N <n < L -1'h(n), 0 <n <

33、M -10, M <n<L-1分别计算序列x(n)、h(n)的L点离散傅里叶变换，即X(k) = DFTx(n) , H (k) = DFT h(n)利用时域循环卷积定理计算序列x(n)、h(n)的L点循环卷积，且它就等于其线y(n) =x(n)* h(n) = x(n)CD y(n) = IDFT X(k)H(k)用循环卷积实现线性卷积的过程如图所示。(5) 长序列卷积的计算(可略，参见教材 P8184)在长序列x(n)通过数字系统h(n)得到隼出y(n)=x(n)* h(n)的过程中，尽管数字系统的单位采样响应h(n) 一般较短(如FIR数字滤波器)，但是由于输入序列x(n)较

34、长而造成无法对信号进行实时处理，因此，我们必须将长序列划分为若干个短序列来进行卷积。其方法一般有两种：重叠相加法和重叠保留法。重叠相加法将长序列x(n)划分成长度为 N的相互连接但互不重叠 的若干个小段，并将每一段分别与长度为M的h(n)作L点循环卷积(取 L=N + M-1),然后将各段的卷积结果相加，即可得 到输出序列y(n)(参见P82图3.3.6所示)。注意:相邻两端的卷积Z果中必有M-1个点发生重叠，因此应将这些重叠部分叠加才能得到正确的输出结果。重叠保留法将长序列x(n)划分成长度为L的若干个小段，且 相邻两段重叠 M-1个点(即每段开始的M-1个点是前一段最后的 M-1个点，但第

35、一个分段的前M-1个点为零)，再将每一段分别与长度为M的h(n)作L点循环卷积，并将各段的卷积结果的前M-1个点舍去，然后将各段的卷积结果的后 N个点依次连接，即可得到输出序列y(n)(参见P83图3.3.7所示)。注意:若每段作L+M-1点循环卷积，则其结果与线性卷积结果一致。但这里每段作L点循环卷积，则其结果中前M-1个点必然发生混叠现象，与线性卷积结果不一致，因此应将这 些点舍去，才能得到正确的输出结果。5. Parseval (帕塞瓦)定理N 1N 1,*1 _*x(n)y (n) X(k)Y (k)n=0N k=0证:由DFT的逆变换和正变换的定义，可得N 1一 *x(n)yn =0

36、N 11 N 4J(n)R：/(k)WN 1N 11Y (k)i. x(n)WNN k=0n =01 N *Y (k)X(k)N k=0如果令y(n) = x(n),则上式变为N 11*1 一 *x(n)x (n) X(k)X (k)nfN kHIN t-彳 fKF X(k)N -1k =0这表明：序列在时域的能量与在频域的能量是相等的。习题：3.8, 3.9, 3.10思考题：P103 3.17, 3.18三、 DFT与DTFT及Z变换的关系离散傅里叶变换 DFT、序列的傅里叶变换 DTFT以及Z变换可以从不同角度对有限长 序列进行分析，因而它们之间必然有一定的联系。1. Z变换与DTFT的

37、关系我们在前面介绍 DTFT时曾经提到：它与 Z变换之间存在关系DTFTx(n) =X(ej ) =X(z)z.，即：若Z变换的收敛域包含单位圆，则序列的 DTFT也就是单位圆上的 Z变换。因此，在 计算序列的DTFT时，我们可以先求序列的 Z变换，再将其结果中的变量 z用ej"代替即可。2. Z变换与DFT的关系有限长序列x(n)的DFT为NX(k) =£ x(n)W；n, k =0,1,，N -1n=0其Z变换为X(z) = ' x(n)zn 二-二对照上述公式，可知X(k)=X(z)L-=X(z)匕孑,k = 0,1,，N -1这表明：序列的DFT也就是其Z变

38、换在单位圆上的等间隔采样，其角度间隔为3 =2兀/N,即将单位圆N等分，各序列的DFT值均匀分布在单位圆上。因此，在计算序列的 DFT时，我三k们也可以先求序列的 Z变换，再令z=e N即可。3. DTFT与DFT的关系由于Z变换在单位圆上的取值就等于序列的傅里叶变换X(ejw),则aX(k) =X(z)z："=X(e N )=X(e)_2取，k=0,1, ,N1 N这表明：序列的DFT也就是其DTFT的等间距采样，其采样间距为3=2兀/N。序列的Z变换、DFT以及DTFT的关系如图所示(P68图325)。RdJ四、频域采样1 .频域采样定理由上述讨论可知，有限长序列x(n)的离散傅

39、里叶变换(DFT) X(k),实际上就是其傅里叶变换(DTFT) X(ej")在主值区间内的等间距采样值。那么，如何采样才能确保由频域采样 值X(k)不失真地恢复其连续频谱X(ej”)呢？其依据也就是频域采样定理。频域采样定理：对于长度为M的有限长序列，频域采样不失真白条件是：频域采样点数N不小于序列N _M2 .数学推导(见教材 P6970,可略)利用X(k)表示X(z)的内插公式来证明，即N 4X(z) - X(k) k(z)k=011式中，内插函数.k(z) = -1 ； /N 1 -WN z五、DFT在实际应用中的问题由于DFT实现了频域采样，且存在快速算法，所以在实际应用中

40、，可以利用DFT来分析时域连续信号。在此过程中，可能遇到的问题有：混叠失真、栅栏效应、频谱泄漏等。I .混叠失真现象前面曾经讨论过，假设信号最高频率为fh,根据采样定理，采样频率 fs应满足fs>2fh即时域采样间隔T应满足IIT =W(3.3.6)fs2fh如果不满足上述要求，就会产生频率响应的周期延拓分量互相重叠的现象，即混叠失真现象。设有限长序列的记录长度为To=NT (N为采样点数)。对DFT来说，频率函数也要经采样成为离散的序列，其频域采样间隔(即频率分辨率)为Fo,则To =1Fo(3.3.7)由公式（3.3.6）和（3.3.7）可见，信号最高频率fh与频率分辨率Fo存在矛盾

41、。要使fh1 . 一一一一 、. 一 ,，11 一一. 一,.，增加，则时域采样间隔 T就必须减小 T = < ，而采样频率fs就增加，由于采样点、fs2fh J数N满足N*fsFo则当N给定时，Fo必然增加，即频率分辨力下降。反之，若要提高频率分辨力（减小Fo）,就要增加To,当N给定时，必然导致 T增加（fs减小），因此要不产生混叠失真，则必然应 减小信号最高频率fh。通过上述分析可知， 要想兼顾信号最高频率 fh与频率分辨率Fo,即保持其中一个不变， 而提高另一个性能的唯一方法就是增加采样点数N,使其满足fs 2fhN - 一FoFo上述公式是在未采用任何特殊数据处理（比如加窗处理

42、）的情况下，实现基本DFT算法所必须满足的最低条件。2 .栅栏效应因为DFT计算信号频谱，只给出了基频整数倍处的离散谱，而不是连续频谱，这就象通过一个“栅栏”观看景象一样，只能在离散点上看到真实景象，这种现象称为“栅栏效应”。减小栅栏效应的一个方法就是要使频域采样更密，即增加频域采样点数，这样必然使各谱线间的距离更近，从而使原来被“栅栏”挡住的频谱分量显露出来，为此，我们可以在不改变原有数据记录的基础上，采用在时域数据的末尾补零的方法来实现。 补零的好处在于： 使频域采样更密，减小栅栏效应；。2使采样点数N变为2的整数次哥，便于利用计算机 实现快速傅里叶变换（FFT）。习题：3.11, 3.1

43、2, 3.13思考题：P102 3.203.4快速傅里叶变换（FFT）由于离散傅里叶变换 （DFT）实现了有限长序列的频域离散化，因而可应用于信号的频谱分析、数字滤波器的设计以及系统的分析、设计和实现等方面。但是在相当长的时间里， 由于DFT的计算量太大，即使采用计算机也很难对问题进行实时处理，所以没有得到真正 的运用。直到1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在计算数学杂志上发 表了著名的“机器计算傅里叶级数的一种算法”的文章，提出了 DFT的一种快速算法，后 来又相继出现了桑德（G.Sande和图基快速算法等一系列高速有效的运算方法，使 DFT的 计算大大简化

44、，运算时间缩短了一、 二个数量级，从而DFT在实际中真正得到广泛的应用。一、直接计算DFT的问题及改进途径N点有限长序列x（n）的离散傅里叶变换公式为：N 二正变换X(k) = DFT x(n) =£ x(n)wNkn, k=。, 1,，N 1n o1 N 反变换x(n) = IDFT X(k) =£ X(k)WN*n, n =。, 1,，N 1N y二者的差别只在于 Wn的指数符号不同，以及相差一个常数因子1/N,因而它们的运算量完全相同。这里，我们只讨论DFT正变换的运算问题。一般来说，x(n)、 wNkn和X(k)均为复数，则每计算一个X(k)值，都需要进行 N次复数

45、乘法(x(n)与 wN1n相乘)以及N-1次复数加法。而 X(k)共有N个点(k=0N-1),所以实现整个DFT运算需要进行N 2次复数乘法和 N(N-1)次复数加法。由此可见，直接计算DFT时， 其乘法次数和加法次数都与N 2成正比，当N很大时，其运算量是很可观的，例如当N=1024时，DFT所需的复数乘法为1048576次，即一百多万次，这对于实时性很强的信号处理来说，对计算速度的要求是太高了。因而我们需要改进DFT的计算方法，以便减少其运算量。kn通过观察，我们发现通过利用系数Wn所固有的周期性、对称性等特性，可以将长序列的DFT分解为短序列的 DFT,这样就可以大大减少 DFT的运算量

46、。正是基于这种基本思 路而形成了快速傅里叶变换算法( Fast Fourier Transform,缩写为FFT),这种算法基本上可 分为两大类：按时间抽取法(Decimation-In-Time ,缩写为 DIT )和按频率抽取法 (Decimation-In-Frequency ,缩写为 DIF)。注意:快速傅里叶变换(FFT)并不是一种新的变换，而是离散傅里叶变换(DFT)的一种快速算法。二、按时间抽取(DIT )的基-2FFT算法(库利-图基算法)1.算法的原理先假设序列x(n)的长度N=2M (M为整数)。如果不满足这个条件，可以人为地在序列末尾补上若干个零值点，使其达到这一要求。这

47、种N为2的整数哥的FFT也称基-2FFT。将长度为N=2M的序列按n的奇偶分为两组，即令 n=2r和n=2r+1 (r =0, 1,，N/2-1), 则x(n)的DFT可表示为N 1N 4N 1X(k) = DFTx(n) - x(n)W：n = x(n)W：nx(n)W；nn -0n =0n -0n为偶数n为奇数k = 0,1,N -1N/2N/2=' x(2r)W；rk% x(2r 1)WN2r 1)kr =0r =0N/2kN/24k=2 x1(r)W； )r +W；2 x2(r)WN2 r r =0r =0N/2 4N/24rkkrk备系数wNnk的性质，得；=X1()Wn/2

48、 WnX2()Wn/2r z0r Hk = X1(k) WNXz(k),k =0,1, ,N /2 -1(3.4.1)式中，X1(k)、X2(k)分别是 x1(r)、X2(r) (r, k =0, 1,，N/2-1)的 N/2 点 DFT ,即N/2rkXi(k) =、Xi(r)WN/2r =0N/ 2 1rk=、x(2r)WN/2r=0(3.4.2)N/2 JN/2 JX2(k) = '、X2(r)wNk/2 = " x(2r 1)W，/2r 0r =0由于xi(r)、X2(r)、Xi(k)、X2(k)均为N/2点的序列，而 x(n)、X(k)为N点的序列,则由(3.4.1

49、)式可见，一个N点DFT可分解成两个 N/2点的DFT,且这只是X(k)前半部分的结果(k =0,NNNNX k + I = X1 k + | +<2<2 1N N )X2 k+ I2 J(3.4.3)r k N由(3.4.2)式和系数的周期性，即 WN% 2 = Wrrk/2,可得X1 k +N1=工22 J r =0x(r)WN/N /2 J='、' x1(r)W| r =0rkN/2 =X1(k)(3.4.4)1,，N/2-1),所以我们还应计算X(k)后半部分的结果(k = N/2,，N-1),即同理，可得(3.4.5)N-=X2(k)又由于系数Wnn/2

50、= 1 ,则kNWn 2=wN；Wnn/2WNk(3.4.6)将(3.4.4)、(3.4.5)、(3.4.6)式代入(3.4.3)式中，可得N 7k(3.4.7)X k +一尸 X1(k) WNX2(k),k =0,1，N/211 2 )综上所述，(3.4.1)式和(3.4.7)式分别是X(k)前半部分和后半部分的运算表达式。显 然，只要求出k =0 N/2-1范围内的X1(k)和X2(k)值，就可以求出 k =0 N范围内的所有 X(k) 值，这就大大节省了运算。(3.4.(1) (3.4.7)式的运算可用如图所示的蝶形信号流图来表示。注意:当支路上没有标出系数时，则该支路的传输系数为1。如

51、果采用这种蝶形图来表示上述分解过程，如图所示，对于N=23=8的情形，其中输出值X(0) X(3)是由(3.4.1)式给出的，而 X(4) X是由(3.4.7)式给出的。尸 1" A 1 . * f 力、，N2点DFTX,T fl，一Zkf9、M(l)rr f J 1 a- J凡（2）注 1% 心 Jrjfr A ) «*T) ftN2感DFT片，叱皿 j VUZ ¥ 1 f VJF-优 x tn工上(3)= j(7) !w1 r * r xjzLNXjUr3 wX(O)X(DX(3)X(4>X(5>X(6)X(将一个N点DFT分n q * .八 |

52、iB iFiWin*1i解为两个N/2点DFT )由于N=2m,则N/2仍是偶数。因此，我们可以仿照上面的做法，进一步将每个N/2点子序列再按奇偶部分分解成两个N/4点的子序列。类似地有，Xi（k）前半、后半部分的运算式分别为Xi（k） =X3（k） W；/2X4（k）N Nkk = 0,1，N/41Xi k+ =X3（k）W；/2X4（k）< 4） , 其中N/ 4 二IX3%)= ' x(2I)Wn/4 - 1 =0N/41 _IkX4(k) =、X1(2I1)Wn/4i kN/4' X3 (I )Wn /4I =0N /4 J=' X4(I)W|I日l = 0,1, , N/4-1IkN/4同理,X2（k）前半、后半部分的运算式分别为X2（k） =X5（k） W；/2X6（k）其中X2 k+N=X5(k)W<4 JkN/2X6(k)0,1，N/4 -1X5(k)X6(k)N /4 4=' X2(2I)Wn/4 二 l =0N /4 4 .Ik=、X2(2I1)Wn/4l =0N /4x X5 (l )Wn /41fN/4=' x6 (l