离散傅里叶变换

1、第三章离散傅里叶变换离散傅里叶变换不仅具有明确的物理意义，相对于DTFT他更便于用讣算机 处理。但是，宜至上个世纪六十年代，山于数字计算机的处理速度较低以及离散傅里叶变换的汁算M较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的 发展，同时在数字信号处 理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。§3-1引言DFT是重要的变换1 ?分析有限长序列的有用工具。2 .在信号处理的理论上有重要意义。3 .在运算方法上起核心

2、作用，谱分析、卷积、相关都可以通DFT在讣算机上实现。二.DFT是现代信号处理桥梁DFT要解决两个问题：一是离散与M化，二是快速运算。傅氏变换§3-2Dr HFr i傅氏变换的几种可能形式?连续时间、连续频率的傅氏变换傅氏变换1/32x(t)X(yQ) = C x(t)e-jntdtJ co) 反：x(t) = -r X(jG)地dG 2/r J8时域信号连续的 非周期的非周期的连续的对称性：时域连续，则频域非周期。反之亦然。二?连续时间、离散频率傅里叶变换傅氏级数2/32|x (购 o) |一< I 11 < I ( I - 11 1Q02兀Co= 丁正：X （购0）二

3、8反：垃）=iXOKl。）k=Ao*时域周期为Tp.频域谱线间隔为2Ji/Tp时域信号频域桁号连续的非周期的周期的离散的、连续频率的傅氏变换-序列的傅氏变换x(nT)3/32-T 0 T 2Too正：X0E尸工x（nT）户gt反:x（叫& J-_/2 pG$x（eQT）ej 叫。*时域抽样间隔为八频域的周期为2吕时域信号频域指号离散的周期的非周期的连续的4/32四?离散时间、离散频率的傅氏变换-DFT0 T 2TNTNN1 2(2 1)%(2 1)111上述分析可知，要想在时域和频域都是离散的，那么两域必须是周期 的。时域信号频域指号离散的周期的周期的离散的*时域是周期为坊函数，频域的

4、离散间隔为 Qo=-；Tp时域的离散间隔为八频域的周期为2二莘？5/32DFT的简单推演:在一个周期内，可进行加I下变换：X(/E)二 Ax(nT)e-j,ATx(nT)=_L x(&g 丁0$ J-O "n ：从 0 N lQ:Q = mo = ? MF,k=O N dO: dd AQ = QoX0KV )=X x(nT)ejnkQ °rn=0x(nT) = # X严7比川如S k=0又 O0T = = 0*= Tp% N2江nk N因此J- JX(e a ) - / xnT)exknT)"=0Ik jnk X(e N N6/32x(M)视作 n 的函数

5、，%(nT) t x(n) j iA kj iA k X2 ")视作k的函数，X(e N )TX彳火)这样，土 -jALnkX (上尸( M ) e Nn=O1 . JJ-nk乂 3)=苻艺X(吃)e nZ花二o§ 33周期序列的DFS一?周期序列 DFS的引入导出周期序列DFSJI勺传统方法是从连续的周期信号的复数傅氏级数开始的：X(t)=伙。0)饲七。0对上式进行抽样，得:xnT)=f 去(Klo)?gM a-00jA-nk=工X伙° 。比NR=-oc，代入e n ? “2 切7/32所以求和可以在一个周期内进行,BPN-l2K式仃）=苫刈2。/4k=0这就是

6、说，当在k=0，N-1求和与在k=N_,2N-l求和所得的结果是一致的。考虑到:x(nT) - x(n), X (mo)-X 伙)；则有，壬何NT ihnk=丫去伙)£ Nk=0菊*谐波系数的嶷伙）i ?预备知识N-1 ? 2/7J7?=0N, r = mN,加为任意整数O,其他厂气即2A +0+? ? +ill令(N7)A/i=0=N(r =力口 M 寸)同样，当k-rAipN也为任意整数，贝9NT ? 2龙小、? N =N = 25(0)=呦伙-r)- pNn=0，壬/等 s w= 5( r) _ pN"k pN) Nn=Q=Sk-(r+ 刃 V)8/32所以工去(k)

7、3k-(r + pAA)= X(r + pN) = X (r)k=02.达式N_1 iS,? 2将式左5)=工加端康"一%k=0,然后从n=0到N-1求和，则：匕？ -i-nr AAx(n)eN n=0筹地？出("迄工XZ N/?=0 R=0NHN71=0n=0 k=0N-l £ 去伪 ENk=0n=0Nr-工 X 伙)N ? *k -(r + pn) k=0二 NX (厂+ENM(厂)9/32因此，弘）号何叙N77=0将r换成k则有去伙）n=0N-1 一舟也去伙）x(n)e nN Ln=0xn)e n他以，对于周期 序列nt -jAkn?召？j JA knx(n

8、) X(k)e nk=0通常将定标因子1/N移到壬俄步式中。X-j -kn即:X伙）二工左（川）幺N/?=0jknX(k)e n3 ?离散傅氏级数的习惯表示法10通常用符号. *.Wn = e-J 入，则:正变换：去伙)=DFSx(n)琴？-Lnk 口？ 上=才左(M)W N -八 x(n)WAz?=0n=0反变换：x(n) = IDFsX 伙)1 匚？ JAnk冷工X?£ =0伙灯k=04.去 I期性与用Z变换的求法周期性： 左伙+测=壬讣)茅71=0? 2兀_ / kn “=Ax(n)e N?厂 Jn=0N-l? 2/r-J kn ,)壬(71)幺n=0=x(k)这就是说，去伙)

9、只有N个不同值。用z变换的求文伙)对兀怖b变换,12ooNX(Z)=工心)z-n=QO=AxnZn=0Jim Z-jAknN2 兀N-1J - k yX(e n ) = y xri)en=0二壬伙)可见，?% 1变换陋优碉上抽样，抽样点在单位圆上的13N个等分点上，且第一个抽样点为 &=0。§ 3-4 DFS 的性质一线性如果 左1伙)二DFS国(M)X2(k) = DFSx2(n)则有 DFSax (n) + bx2(n) = aXx (k)-、bX2 (k)其中，a,b为任意常数。二.序列的移位如果 DFSx(n)=X 伙)则有：DFSx(n + m) = Wr,1kX(

10、k)jA-mk ?=e n x 伙)N7证明：DFSx(n + m) = Ax(n + m)WAkn=o令 i=m+，01)n=i-mo n=0, i=m; n=N-l 时，i=N? l+mN-l+ i所以 DFSx(n + m)=为左 w# -WAtk i=m N-=ANnk x壬呼="pH火)7=0第(i)都是榨为周期的周期函数.三?调制特性14如果DFSx(n)=X(k)则有DFsvAtlx(n)= X(k + m)N - l证明:DFSWAx(n) = AWA,lx(n)WAn=0N=Ax(n)WA+m)n77=0=X(k + m)2冗jinnW,=e N.2/r 2 兀-/

11、nm /nen =( £ j时域乘以虚指数（？鼐 m次幕，频域搬移心调制特性。四.周期卷积和i?如果 Y（k） = Xx伙）去2伙）则：y(n) = IDFSY 伙)NHXj （/?）X2（卅加）2 ?两个周期序列的周期卷积过程X2 （加）左1 （斤 加）(1)画出! (?) 饴卿;将禺（W总得到x2 （-m）5可计算出：y （0）=左（加）左2=电（0-加）(0 加)加=0=1x0 +1x0 +1x0144A1 + 0x2 + 0x1=1计算区gO15/32壬1 （加）1111丸2 (加)点2 （-力口）y(i) = 丫=lxl + lxO + IxO + IxO + Oxl +

12、Oxl可计算出:左1（加）左2 （加）程（1-力口）计算区（4）将玄（刁耐）移一位、得到 X2 （2-m）5可计算出：孑二（m）X2（2-m）加=0=1x2 + 1x1 + 1x04-1x0 + 0x0 + 0x1=35以此类推，亍=力左（加）左2 （3 "2）m=0=1x1 + 1x2 + 1x14-1x0 + 0x0 + 0x0=4同样）可计算出：亍=4, y（5） = 316/323 ?频域卷积定理如果 y(n) = xA)X2(n)%) = DrsyCn)=艺 2 $(n)w 弃n=O文(Z)文2伙一 Z)z=o1 _=符 W5C 2(Z)文 1(吃一 Z) /v /=o&#

13、167; 3-5 DFT 一有限长序列的离散频域表示一 ？预备知识1 ?余数运算表达式如果n -勺+mN 0 <n W N l m为整数；则有：(n)A =(HJ)18/32此运算符表示n被N除，商为m,余数为(nJ一有限长序列x(n)和周期序列系讣)二£兀刃+朋户m=Ax)MS)周期序列F(厕有限长序列x(n)的周期延拓。x(n)x(n)= <0或 x( )=,0<n<N-1其他nxn)RN (m)有限长序列x(n)是周期序列壬(口的主值序列。如:三.周期序列 X (佥*限长序列x(k)的关系19/32文伙)=X(亿)NX(k) = X(k)RN(k)同样，

14、周期序列限长序列X(k)的周期延拓。而有限长序列X伙J是周期序列 X伙去值序列。四？从 DFS到DFT'7V-1< X(k) = DFSx(n)=工 x(n)W八(/?) = IE>Fsxkk)=£又")叼村 N k=on=0x从上式可知，DFSJDFS的求和只限定在I匚0至U n=N? l,及k=0到N? 1的主值区 间进 行。因此可得到新的定义，即有限序的离散傅氏变换 (DFT)的定义。N 1X(k) = DFTx(n)=Ax(n)WA k77=0N_1a(h)= IDFTx (k)= AXAWAk? n k=o 或者：Xp= f(k)/?N (k)

15、x(n) = x(n)RN (n)20/32§3-6DFT的性质一线性1 ?两序列都是 N点时如果 DFTx(n) = X彳火)DFT X2 =X2 彳)则有：uxx (n) + bx2 (n) = aXx (Zc) + bX2 (A)2?兀机）期日&/）1和N2不等时，选择 N = m日勺修凰WT进行补零达到 N点。二?序列的圆周移位1?定义一个有限长序列双的庐I周移位定义为Xm (?)=HS + 力口)N RN S)这里包括三层意思:0先将X傩片周期延拓左)=X (C) ) N（比 +加）=兀（ +加）N子最后取主值序列：Xm （n） =兀（斤 +血）N RN （斤）21

16、/32x<n)t 宜)=X()N0f M5 + 2) = x( + 2)n左移222/322 .圆周位移的含义由于我们取主值序列，即只观察 n=0到N-1这一主值区间，当莫一抽样从 此区间一 端移出时，与它相同值的抽样乂从此区间的另一端进来。如果把排列一个N等分的圆周上，序列的移位就相半于兀(滋圆上旋转，故称作圆周移位。当围着圆周观察儿圈时，看到就是周期序列：左()三、共轨对称性1 .周期序列共辘对称分M与共辘反对称分M周期为N的周期序列的共辘对称分M与共辘反对称分M分别定义为(N-心“户A-1*1 *Xe(n) = "x(n) + x (-H)J = -x(n)八 +xx(n

17、)-x*(-/z)J = +X(S)N -兀*(N-斤)加 J A J同样'有 x(n) - xe(H)+ xo(H)*(j *( )2 .有限长序列的圆周共辘对称分M与圆周共辘反对称分M有限长序列的圆周共辘对称分M与圆周共轨反对称分M分别定义为1*xep(n) = x e(n)R N(n) = -x(n)n +x (N-n)N|RN(n)?1甲xop(n) = x o(n)RN(n) = - x(w)at x (N-n) N|RN(n)由于 x(n) = x(n)RN (n) = xe(n) + xo (n)RN (n) =xe(n)RN (n) + xo (n)RN (n)所以 x

18、(n) = xep(n) + xop(n)这表明长为N的有限长序列可分解为两个长度相同的两个分23/323 .共辄对称特性之一如果 X (k) = DFTx(n) 则 DFTx'n)=X *( 一幻加 RN(k) = X(N-k) N rn 伙)NJ证明：DFTxn)=K=0N-l=心=工口)1巾严心伙) " =0?=0N-l二I 工心)r Rn 伙尸Xf (N _k)N RN (k) ” =04 ?共辄对称特性之二如果 X(k) = DFTx(n)则 DFTx(-n) NRN(n) = Xk)N-l证明：DFTx (一町加Rn=工x* (一町加Rn S)W严n=0N-l-(

19、N-l)二工心)w工心)呼r " =0n=0N-l=AA(n)IVA* = X*(fc)n=0可知：X*(小 d X*(-k)N RN(k) * *兀(-n)NRN(n)A>X 伙)5 .共辄对称特性之三如果 X 伙尸 DFTx(nn 贝!)DFTRex(n) d *24/32=F(Q) n + x 3 幻加心= xepg.1 r *、证刖：优那则而2? ? DFTRex(n) =-DFTx(n) +DFTxn)1 *=#X(灯+ X (N 幻加心(灯1 *=-X(k) n + X (N 灯)NRn伙尸心伙)*复数序列实部的DFT =该序列QFT的圆周共轨对称分量。6 .共辄对

20、称特性之四如果 X 伙尸 DFTx(n) 9 则 DFTjImx(n)=*X (伙)加-X"(N-k)N WN二 X p伙)证 v ylmx(n) = x(/2)-x*(/?)2?呵加如冷0(讣呵讪=|x伙)-xl(N 灯)川心伙)=£凶 N-X(N-k)NRN(k) = Xop(k)*复数序列虚部乘以J的ar =该序列dft的 圆周共轨反对称 分量。25/327 .共辄对称特性之五、六同样，可证明：ReX(k) = DFTx ep(nn jlmlX(k) = DFTx op(n)&x(k)圆周共辄对称分量与圆周共辘反对称分量的对称性(1)、Xg = Xep(灯 +

21、 X° p(Q26/32jk(2)、Xa = Xep(-k) = Xep(-k)NRN伙)*=X"(N")N 心伙)(3)、X p 伙户 X; (-P) = -X; )p (P)n Rn 伙)=_X： p(N_ )N 心伙)9.实、虚序列的对称特性 当x(n)为实序列时，根据特性之三，则X(k)=Xep(k)又据如闵的对称性：x切伙尸X、(N-k)NRN(k)当x(n)为纯虚序列时，根据特性之四，则X(k)=Xop(k)乂据余田伙1的对称性： Xop(k)=( 一幺勺加心 伙)*:.X(k) = -X (-k) nRn4焙四？圆周卷积和1 ?时域卷积定理设兀(和)

22、帧炖度为N的有限长序列，且 DFTxx(h) = Xj(k) DFTx 2(n) = X2(k)y(n) = IDFTY 伙)工"(力口)兀2(5-加)n心(司=兀1何m=026 / 32N-工兀2 （加）"（m=0一同）N 心（）=兀2 （兀）X1 W五?有限长序列的线性卷积与圆周卷积1.线性卷积讷为M（0KN-1）碱为N2（0<n<N 2-i）它们线性卷积为ooN-l力）二二工兀i （加）七（“ 一加）二，“（加）兀 2 （"一 mj）力口=yom=0坷（iwh零区间为 0 W加W TV】1X2伯俳零区间为Osn-mSN”'两不等式相加得0

23、SnSN+N22也就是y （用）为零的区间。2.用圆周卷积计算线性卷积 圆周卷积是线性卷积的周期延拓序列的主值序列。 别滩度为， 他长度2何，先构造长1朋为L长的序列，即将坷（料），袂寮耐然后再对它们进行周期延拓，即"（砒）L （何）AL 一 1 y （?） = Xxi 伽）A七（S -力口）A 加=0所以得到周期卷积：28/32由于 0 <m<L-l,故 Y （m） l =兀 1 （m）,因此A - iA - i oo=为“（加）勺（S - mS）L =工 X（加）工 X2（，7 + ?"L - m） w=0m=0 =-x00 A 1 =X为兀1（加）兀2（刃

24、+江-加）,=YO 加=000 =工 y/S + ）,=-00§ 3-7抽样Z变换一频域抽样理论一.如何从频域抽样恢复原序列1 ?两种抽样时域抽样：对一个频带有限的信号，根据抽样定理对其进行抽样，所得抽样信号的频谱是原带限信号频谱的周期延拓，因此，完全可以山抽样信号恢复原信号。频域抽样：对一有限序列(时间有限序列)进彳f DFT所得兀伙J就是序列傅氏变换的采样 . 所以DFT就是频域抽样。2 .由频域抽样恢复序列一个绝对可和的非周期序列皿Z的 z变换为00X(Z)= Ax(n)Zn=00山于皿1绝对可和，故其傅氏变换存在且连续，也即其Z变换收敛域包括单位 圆。这样，对X(Z)在单位圆

25、上N等份抽样，就得到00去伙)= X(Z) 匚叱厂乞 =YO3 .频域抽样不失真的条件6当珈砒不是有限长时，无法周期延拓；? X x(n)为长度只有N>M时，才能不失真的恢复信号，即29/32xn(?)= xn (n)RN (n)x(n + rN)RN (n) = x(n), N > MF=Y)§ 38利用DFT对连续时间信号的逼近一.用DFT讣算连续时间信号的傅氏变换可能造成的误差1 ?混叠现象为避免混叠，由抽样定理可知，须满足fs > 2fh其中，/为抽样频率；为悬号的最高频率分M；或者T = -<-*-fs 2 办其中，T为抽样间隔。2 .频谱泄漏在实际应用中，通常将所观测的信号习 （脱制在一定的时间间隔内，也就是 说， 在时域对信号进行截断操作，或称作加时间窗，亦即用时间窗函数乘以信号,山卷积定理可知，时域相乘，频域为卷积，这就造成拖尾现象，称之为频谱泄漏。3 .栅