延安大学：《数字信号处理》课程教学讲稿（DigitalSignal Processing，DSP）第3章 离散傅里叶变换

第三章离散傅里叶变换 Discrete fourier Transform 在计算机上实现信号的频谱分析及其他方面的处理工作时,要求信号在时域和 频域都应是离散的,且都应是有限长的。 3.1离散傅里叶变换(DT)的定义 DFT实质上是有限长序列 Fourier变换的有限点离散采样,从而使利用计算机 进行信号分析成为可能。 3.11DFT的定义 1、DFT和IDFT 设x(m)是一个长度为M的有限长序列,则定义x(n)的M点离款傅里叶变换为 X(k)=DFT[x()]=∑x(m)形,k=0,1…N X(k)的离散傅里叶逆变换(IDFT, Inverse discrete fourier transform)为 x(n)=DFT[X(k)]=∑X(k),n=0,1…,N-1 其中,W=eN,N称为DT变换区间的长度,N≥M 2、唯一性证明 3、例题 3.1.2DFT和Z变换的关系 设序列x(n)的长度为N,其Z变换和DT分别为: X(=)=Z[x(m)]=∑x(n)

第三章 离散傅里叶变换 Discrete Fourier Transform 在计算机上实现信号的频谱分析及其他方面的处理工作时，要求信号在时域和 频域都应是离散的，且都应是有限长的。 3.1 离散傅里叶变换（DFT）的定义 DFT 实质上是有限长序列 Fourier 变换的有限点离散采样，从而使利用计算机 进行信号分析成为可能。 3.1.1 DFT 的定义 1、DFT 和 IDFT 设 x n  是一个长度为 M 的有限长序列，则定义 x n  的 N 点离散傅里叶变换为       1 0 , 0,1, , 1 N kn N n X k DFT x n x n W k N             (1.1) X k  的离散傅里叶逆变换（IDFT，Inverse Discrete Fourier Transform）为       1 0 1 , 0,1, , 1 N kn N k x n IDFT X k X k W n N N              (1.2) 其中， 2 j N W e N    ，N 称为 DFT 变换区间的长度， N M 。 2、唯一性证明 3、例题 3.1.2 DFT 和 Z 变换的关系 设序列 x n  的长度为 N，其 Z 变换和 DFT 分别为：       1 0 N n n X z ZT x n x n z          

X(k)=DF[x(m)]=∑x(m)如,0≤k≤N 比较可得 x(k)=X(二) 0≤k≤N-1 (1.3) 点 x (k)=x(el 0≤k≤N-1 (1.3)式表明:列x(n)的N点DF是x(m)的2变换在单位國上的N点等间隔采 样,(1.4)式则说明X(k)为x(n)的傅里叶变换X()在区间[2]上的N点等间 隔采样。由此可见,DFT的变换区间长度N不同,表示对X(e")在2]区间上的 采样间隔和采样点数不同,所以DFT的变换结果不同。 (a)x(n)的幅频特性曲线 0.2040.60.8 12141.61.8 (b)X(n)的8点DFT (c)x(n)的16点DFT 图3.1.1R4(n)的FT和DFT的幅度特性关系

      1 0 , 0 1 N kn N n X k DFT x n x n W k N             比较可得     2 , 0 1 j k z e N X k X z k N       (1.3) 或     2 , 0 1 k N j X k X e k N         (1.4) (1.3)式表明：序列 x n  的 N 点 DFT 是 x n  的 Z 变换在单位圆上的 N 点等间隔采 样。(1.4)式则说明 X k  为 x n  的傅里叶变换   j X e  在区间 0,2  上的 N 点等间 隔采样。由此可见，DFT 的变换区间长度 N 不同，表示对   j X e  在 0,2  区间上的 采样间隔和采样点数不同，所以 DFT 的变换结果不同。 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 2 4 / 幅 度 (a)x(n)的幅频特性曲线 0 1 2 3 4 5 6 7 0 2 4 k 幅 度 (b)x(n)的 8点 DFT 0 5 10 15 0 2 4 k 幅 度 (c)x(n)的 16点 DFT 图 3.1.1 R4（n）的 FT 和 DFT 的幅度特性关系

3.1.3DFT的隐含周期性 x(k)的周期性 由于 W=Wm),k,m,N均为整数 所以 Y(k+mN= r(n)wltmN)n =∑x(m)W=(k) 同理,有 x(n+mN)=x(n) 实际上,任何周期为N的周期序列(m)都可以看作长度为N的有限长序列 x(rn)的周期延拓序列,而x(m)则是式(n)的一个周期,即 )=∑x(m+mN) x(n)=x(n)R、() 2、主值区间与主值序列 般定义周期序列x(n)中从n=0到N1的第一个周期为x(m)的主信区闯,而 主值区间上的序列称为(m)的主值序型。因此,上述关系可以叙述为:x(n)是 x()的周延拓序列x(m)是x(m)的主值序列 为了叙述方便,将(1.5)表示为 (n)=x(n) (1.7) 式中x()表示x()以N周期的周期延拓序列,x(n)表示n对N求余,即如 n=MN+n1,0≤n1≤N-1,M为整数

3.1.3 DFT 的隐含周期性 1、 X k  的周期性 由于   , , , k k mN W W k m N N N   均为整数 所以           1 1 0 0 N N k mN n kn N N n n X k mN x n W x n W X k            同理，有 x n mN x n      实际上，任何周期为 N 的周期序列 x n   都可以看作长度为 N 的有限长序列 x n  的周期延拓序列，而 x n  则是 x n   的一个周期，即     m x n x n mN       (1.5) x n x n R n       N   (1.6) 2、主值区间与主值序列 一般定义周期序列 x n   中从 n=0 到 N-1 的第一个周期为 x n   的主值区间，而 主值区间上的序列称为 x n   的主值序列。因此，上述关系可以叙述为： x n   是 x n  的周期延拓序列； x n  是 x n   的主值序列。 为了叙述方便，将(1.5)表示为    N x n x n   (1.7) 式中  N x n 表示 x n  以 N 周期的周期延拓序列，  N x n 表示 n 对 N 求余，即如 果 1 1 n MN n n N      , 0 1，M 为整数

(n) 3、离散傅里叶变换与离散傅里叶级数的关系 如果x(n)的长度为N,且(n)=x(m),则 X()=∑x(m=x()=∑x() (1.8) x (k)h (1.9) 式中 (k)=X(k)R3(k) (1.10) 为X()主值序列。可得:有限长序列x(n)的离散傅里叶变換X(k),正好是x(m) 的周期延拓序列x(m)的离散傅里叶级数系数X(k)的主值序列,即 X(k)=X(k)R、( 4、 MATLAB计算 fft(x) fft(x, n) 【例3.1.2】

则   1 N n n  3、离散傅里叶变换与离散傅里叶级数的关系 如果 x n  的长度为 N，且    N x n x n   ，则         1 1 1 0 0 0 N N N kn kn kn N N N N n n n X k x n W x n W x n W               (1.8)       1 1 0 0 1 1 N N kn kn N N k k x n X k W X k W N N             (1.9) 式中 X k X k R k      N    (1.10) 为 X k   主值序列。可得：有限长序列 x n  的离散傅里叶变换 X k  ，正好是 x n  的周期延拓序列  N x n 的离散傅里叶级数系数 X k   的主值序列，即 X k X k R k      N    。 4、MATLAB 计算 fft(x) fft(x,n) 【例 3.1.2】

(a)16点DFT幅频特性 (b)16点DFT相频特 005 0.51 1.5 (c)32点DFT幅频特性 (d)32点DFT相频特性 00.5 15 0.5 1.5 3.2离散傅里叶变换的基本性质 321线性性质 若x(n)和x(m)是两个有限长序列,长度分别为N和N2,且 式中,a,b为常数,取N=max[N,N2],则y(n)的N点DFT为 y(k)=DFTLy(n)=aX, (k)+bx2(k),0sksN (2.1) 其中X1(k)和X2()分别为x(n)和x(n)的N点DFT 3.2.2循环移位性质 1、序列的循环移位 设x(m)为有限长序列,长度为N,则x(m)的循环移位定义为:

0 0.5 1 1.5 2 0 1 2 3 4 / 幅 度 (a)16点 DFT幅频特性 0 0.5 1 1.5 2 -2 -1 0 1 2 / 相 位 (b)16点 DFT相频特性 0 0.5 1 1.5 2 0 1 2 3 4 / 幅 度 (c)32点 DFT幅频特性 0 0.5 1 1.5 2 -4 -2 0 2 4 / 相 位 (d)32点 DFT相频特性 3.2 离散傅里叶变换的基本性质 3.2.1 线性性质 若 x n 1   和 x n 2   是两个有限长序列，长度分别为 N1 和 N2 ，且 y n ax n bx x     1 2     式中，a,b 为常数，取 N N N  max ,  1 2 ，则 y n  的 N 点 DFT 为 Y k DFT y n aX k bX k            1 2    ,   ０ k N-1 (2.1) 其中 X k 1   和 X k 2   分别为 x n 1   和 x n 2   的 N 点 DFT。 3.2.2 循环移位性质 1、序列的循环移位 设 x n  为有限长序列，长度为 N，则 x n  的循环移位定义为：

(n)=x(n+m), R(n) 即:将x(n)以N为周期进行周期延拓得到(n)=x(n),再将(n)左移m位得到 (n+m),最后取x(n+m)的主值序列就得到有限长序列x(n)的循环移位序列 y(n)。即:循环移位的实质是将x(n)左移m位,而移出主区间(0≤n≤N-1的 房列值又依次从右侧进入主区周。 2、时域循环移位定理 设x(m)是长度为N的有限长序列,y(m)为x(n)的循环移位,即 y(n)=x((n+m),RN (n) ( k)=DFTLy(n)]=W x(k) 其中X(k)=DF7[x(n)0≤ksN-1 3、频域循环移位定理证明 若 X(k)=DFT[x(n).OsksN (k)=X(k+1)R(k) y(n)=IDFTLY(k)=Wx(n) (2.4) 32.3循环卷积性质 1、循环卷积 有限长序列x(m)和x(n),长度分别为N和M2,N=max[N,N2]。x(n)和 x2()的N点DFT分别为

      N N y n x n m R n   (2.2) 即：将 x n  以 N 为周期进行周期延拓得到    N x n x n   ，再将 x n   左移 m 位得到 x n m    ，最后取 x n m    的主值序列就得到有限长序列 x n  的循环移位序列 y n  。即：循环移位的实质是将 x n  左移 m 位，而移出主治区间 0 1    n N  的 序列值又依次从右侧进入主治区间。 2、时域循环移位定理 设 x n  是长度为 N 的有限长序列， y n  为 x n  的循环移位，即     N   N y n x n m R n   则       kn Y k DFT y n W X k N        (2.3) 其中 X k DFT x n k N           ,0 1   。 3、频域循环移位定理证明 若 X k DFT x n k N           ,0 1       N   N Y k X k l R k   则       nl N y n IDFT Y k W x n       (2.4) 3.2.3 循环卷积性质 1、循环卷积 有限长序列 x n 1   和 x n 2   ，长度分别为 N1 和 N2 ， N N N  max ,  1 2 。 x n 1   和 x n 2   的 N 点 DFT 分别为：

X,(k)=DFT[x(n) X2(k)=DFT[=(n) 如果 X(k)=X1(k)K2(k) 则 x(n)=IDFTLX(k)=2*(m)*2(n-m)) RN(n) 或 x(n)=IDFTLX()=2x2(m)x(n-m)),RN(n) 一般称(2.5)式为所表示的运算为x(n)和x2(m)的循环卷积。 2、循环卷积的公式证明 对(2.5)式两边进行DFT,则有 X(k)=DFTLx(n)] =∑x(m)∑x(m-m)W如 令n-m=n,则有 y (k)=∑x(m)∑x1(n) ∑x(m)x(m 因为上式中x2(m)环是以N为周期的,所以对其在任一个周期商丘和的结果不 变。因此

X k DFT x n 1 1          X k DFT x n 2 2          如果 X k X k X k     1 2     则           1 1 2 0 N N N m x n IDFT X k x m x n m R n           (2.5) 或           1 2 1 0 N N N m x n IDFT X k x m x n m R n           一般称(2.5)式为所表示的运算为 x n 1   和 x n 2   的循环卷积。 2、循环卷积的公式证明 对(2.5)式两边进行 DFT，则有               1 1 1 2 0 0 1 1 1 2 0 0 N N kn N N N n m N N kn N N m n X k DFT x n x m x n m R n W x m x n m W                            令 n m n   ，则有             1 1 1 2 0 1 1 1 2 0 N N m k n m N m n m N N N m kn kn N N m n m N X k x m x n W x m W x n W                       因为上式中 2   kn N N x n W   是以 N 为周期的，所以对其在任一个周期商丘和的结果不 变。因此

X(k)=∑x1(m)W∑x2(mW=x1(k)X2(k),0≤k≤N 3、循环卷积的实现 step1:先将x(m)周期化,形成x(m),再反转形成x2(-m),并取主 值序列x2(-m)R(m) step2:对x1(m)的循环反转序列循环移位n,形成x(n-m)R(m),当 n=0,1,…,N1时,分别将x(m)与x(n-m)、R(m)相乘,并对m在0-(N-1) 区间商求和,便得。 4、循环卷积的表示 x(n)=2x,(m)x2(n-m)),R(n)=x(n)@x2(n) 5、循环卷积定理 有限长序列x(m)和x(m)的长度分别为N和N,N=max[N,N],x(m)和 x2(n)的N点循环卷积为 x(n)=x, (n)8x2(n)=2*(m)*(n-m)),RN(n) 则x(m)的N点DFT为 X(k)=DFT[x(n)I=X,(k)X2(k) (2.7) 其中, X,()=DFT[,(n) X2(k)=DFTLx2(n) 6、时域循环卷积定理 若

          1 1 1 2 1 2 0 0 , 0 1 N N kn kn N N m n X k x m W x n W X k X k k N               3、循环卷积的实现 Step 1: 先将 x m 2   周期化，形成 2  N x m ，再反转形成 2  N x m ，并取主 值序列 2   N   N x m R m  。 Step 2: 对 x m 2   的循环反转序列循环移位 n，形成 2   N   N x n m R m  ，当 n=0,1,„,N-1 时，分别将 x m1   与 2   N   N x n m R m  相乘，并对 m 在 0 1  N   区间商求和，便得。 4、循环卷积的表示             1 1 2 1 2 0 N N N m x n x m x n m R n x n x n        5、循环卷积定理 有限长序列 x n 1   和 x n 2   的长度分别为 N1和 N2， N N N  max ,  1 2 ， x n 1   和 x n 2   的 N 点循环卷积为             1 1 2 1 2 0 N N N m x n x n x n x m x n m R n        (2.6) 则 x n  的 N 点 DFT 为     1 2     N X k DFT x n X k X k       (2.7) 其中，         1 1 2 2 N N X k DFT x n X k DFT x n           6、时域循环卷积定理 若

x(n)=x1(n)x2(m) 则 x(k)=DFTLx(n)=yX, (k)ox2 (k) (2.8) ∑X1(0)x2(k-1)、R(k) 或 x(k)=DFT[x(n)=xX2(k)ox,(k) ∑x:()x(k-D)R( 其中 X,()=DFTLx,(n)] x2()=DFT[x2(n)I 0≤k≤N-1 3.24复共轭序列的DFT 设x(n)是x(n)的复共轭序列,长度为N X(k)=DFTx(n) 则 DFTIx'(n)=X(N-k 0≤k≤N-1 且 X(N)=X(0 3.25DFT的共轭对称性 1、有限长共轭对称序列和共轭反对称序列 分别用x(n)和x(n)分别表示有限长共对称序列和热反对称序烈,则有 如下定义式

x n x n x n    1 2     则               1 2 1 1 2 0 1 1 N N N l X k DFT x n X k X k N X l X k l R k N             (2.8) 或               2 1 1 2 1 0 1 1 N N N l X k DFT x n X k X k N X l X k l R k N             其中         1 1 2 2 , 0 1 X k DFT x n k N X k DFT x n                3.2.4 复共轭序列的 DFT 设   * x n 是 x n  的复共轭序列，长度为 N， X k DFT x n          则     * * DFT x n X N k       ,   0 k N-1 且 X N X    0 3.2.5 DFT 的共轭对称性 1、有限长共轭对称序列和共轭反对称序列 分别用 x n ep   和 x n op   分别表示有限长共轭对称序列和共轭反对称序列，则有 如下定义式：

xn/(n)=xn(N-n),0≤n≤N (2.9) n)=xm(N-n),0≤n≤N 当N为偶数时,将上式中的n换成N/2-n,可得 0<n N n n 可以证明: 如同任何实函数都可以分解成偶对称分量和奇对称分量一样,任何有限长序 列x(n)也都可以表示成其共轭对称序列和共轭反对称序列之和,即 (n)=x2(m)+xn(m,0≤n≤N-1 将上式中的n换成N-n,并取复共轭,再将(2.9和(2.10)式代入,得到 x(N 将(2.11)是减去(2.12),可得: (n)=[x(m)+x(-n)] 2、DFT的共轭对称性 (1)若x(n)=x,(m)+fx(n) 其中 x(n)=Re[x(n)]=[x(m)+x(n)] x()=m[x(n)]=[x(n)-x(n) 两边同时取DFT,可得

    * ep ep x n x N n     ， ０ n N-1 (2.9)     * , 0 1 op op x n x N n n N       (2.10) 当 N 为偶数时，将上式中的 n 换成 N/2-n，可得： * , 0 1 2 2 2 ep ep N N N x n x n n                   * , 0 1 2 2 2 op op N N N x n x n n                    可以证明： 如同任何实函数都可以分解成偶对称分量和奇对称分量一样， 任何有限长序 列 x n  也都可以表示成其共轭对称序列和共轭反对称序列之和，即      , 0 1 ep op x n x n x n n N      (2.11) 将上式中的 n 换成 N-n，并取复共轭，再将(2.9)和(2.10)式代入，得到：           * * * ep op ep op x N n x N n x N n x n x n        (2.12) 将(2.11)是减去(2.12)，可得：       1 * 2 ep x n x n x N n        (2.13)       1 * 2 op x n x n x N n        (2.14) 2、DFT 的共轭对称性 （1）若 x n x n jx n     r i     其中         1 * Re 2 r x n x n x n x n                    1 * Im 2 i jx n j x n x n x n            两边同时取 DFT，可得