第一章 离散时间信号与系统
第二章 z变换和离散时间傅里叶变换(DTFT)
第三章 离散傅里叶变换
第四章 快速傅里叶变换（FFT）
第五章 数字滤波器的基本结构
第六章 无限长单位冲激响应(IIR)数字滤波器的设计方法
第七章 有限长单位冲激响应(FIR)数字滤波器的设计方法
第八章 序列的抽取与插值——多抽样率数字信号处理基础

第三章 离散傅里叶变换（DFT）

3.1 傅里叶变换的四种可能形式

---

3.2 离散傅里叶级数（DFS）

DFS定义

• 正变换：

  \begin{aligned} \tilde{X}(k)&=\mathrm{DFS}[\tilde x(n)]\\&=\sum\limits^{N-1}_{n=0}\tilde x(n)e^{-\mathrm j\frac{2\pi}{N}nk}\\&=\sum\limits^{N-1}_{n=0}\tilde x(n)W_N^{nk} \end{aligned}

• 反变换：

  \begin{aligned} \tilde{x}(n)&=\mathrm{IDFS}[\tilde X(k)]\\&=\frac{1}{N}\sum\limits^{N-1}_{n=0}\tilde X(k)e^{\mathrm j\frac{2\pi}{N}nk}\\&=\frac{1}{N}\sum\limits^{N-1}_{n=0}\tilde X(k)W_N^{-nk} \end{aligned}

其中W_N=e^{-\mathrm j\frac{2\pi}{N}}称为旋转因子，有以下特性：

• 共轭对称性

  W_N^n=(W_N^{-n})^*

• 周期性

  W_N^n=W_N^{n+iN},i为整数

• 可约性

  W_N^{in}=W_{N/i}^{n},\quad W_{Ni}^{in}=W_N^{n}

• 正交性

  \frac{1}{N}\sum_{k=0}^{N-1}W_{N}^{n k}\left(W_{N}^{m k}\right)^{*}=\frac{1}{N}{\sum_{k=0}^{N-1}}W_{N}^{(n-m)k}=\left\{\begin{array}{l l}{1,}&{n-m=i N}\\ {0,}&{n-m\neq i N}\\ \end{array}\right.

DFS性质

这里的许多性质都和z变换和DTFT重复，最好联合记忆

• 线性

  \mathrm{DFS}\Big[a\tilde{x}_{1}(n)+b\tilde{x}_{2}(n)\Big]=a\tilde{X}_{1}(k)+b\tilde{X}_{2}(k)

• 周期序列移位

  \operatorname{DFS}\left[\tilde{x}(n+m)\right]=W_N^{-mk}\tilde{X}(k)=\operatorname{e}^{\mathrm j\frac{2\pi}{N}mk}\tilde X(k)

• 调制特性

  \operatorname{DFS}\Big[W_{N}^{ln}\tilde{x}\left(n\right)\Big]=\tilde{X}(k+l)

• 对偶性

  \operatorname{DFS}\Big[\tilde{X}(n)\Big]=N\tilde{x}(-k)

• 对称性

  \begin{array}{c c c}{x(n)}&=&\mathrm{Re}\bigl[x(n)\bigr]&+&\mathrm{jIm}\bigl[{x(n)}\bigr]&\\ {\updownarrow}&&{\updownarrow}&&{\updownarrow}&\\ X(\mathrm{e}^{\mathrm j\omega})&=&X_{e}(e^{\mathrm j\omega})&+&{X_{o}(e^{\mathrm j\omega})}&\end{array}

  \begin{array}{c c c}{x(n)}&{=}&{x_{e}(n)}&+&{x_{o}(n)}&\\ {\updownarrow}&&{\updownarrow}&&{\updownarrow}&\\ X(e^{\mathrm j\omega})&=&\mathrm{Re}\left[X(e^{j\omega})\right]&+&\mathrm{jIm}\left[X(\mathrm{e}^{j\omega})\right]\\ \end{array}

• 周期卷积和

  \tilde{x}_1(n)*\tilde{x}_2(n)=\sum_{m=0}^{N-1}\tilde{x}_2\left(m\right)\tilde{x}_1\left(n-m\right)

• 周期卷积和的不进位乘法：以\hat x(n)=\{\underline4,3,2,1,...\}\hat h(n)=\{\underline1,1,1,1,...\}h(n)=\{\underline1,1,1,1\}举例：

\begin{array}{c c c c c}{x(n)}&{}&{}&{}&{4}&{3}&{2}&{1}\\ {h(n)}&{}&{}&{}&{1}&{1}&{1}&{1}\\ \hline&{}&{}&{}&{4}&3&{2}&1\\ &{}&{}&{4}&{3}&{2}&{1}&{}\\ &{}&{4}&{3}&{2}&{1}&{}&{}\\&{4}&{3}&{2}&{1}&{}&{}\\ \hline&{4}&{7}&{9}&{10}&\underline{6}&\underline{3}&\underline{1}\\&\underline{6}&\underline{3}&\underline{1}\\ \hline{y(n)}&10&10&10&10\end{array}

在圆周卷积会再次用到并详细解释

3.3 离散傅里叶变换

DFT定义

1. 主值区间、主值序列

   设一个有有限长序列x(n)：

   x(n)=\begin{cases}x(n),&0\leq n\leq N-1\\[0.3em]0,&其他n\end{cases}

   然后把x(n)看作是周期序列\tilde x(n)的一个周期：

   \tilde{x}(n)=\sum\limits_{r=-\infty}^\infty x(n+rN),r是整数

   \tilde x(n)的主值区间：0\sim N-1

   \tilde x(n)的主值序列：主值区间上的序列

2. DFT定义

正变换：

X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk}\\\quad 0\le k\le N-1

反变换：

x(n)=\dfrac{1}{N}\sum_{k=0}^{N-1}X(k)W_N^{-nk}\\\quad0\leq n\leq N-1

DFT与序列z变换、DTFT的关系

X(k)=X(z)\Big|_{z=W_N^{-k}=e^{j\frac{2\pi}{N}k}}=X(e^{\mathrm j\omega})\Big|_{\omega=\frac{2\pi}{N}k}

• x(n)的N点DFT是x(n)的z变换在单位圆上N点等间隔抽样
• x(n)的N点DFT是x(n)的DTFT在区间[0,2\pi]上N点等间隔抽样

序列的隐含周期性

DFT处理的有限长序列都是作为周期序列的一个周期来表示的，也就是说离散傅里叶变换隐含着周期性。

模拟频率f_k 与抽样点数N抽样频率f_s的关系

• 频率分辨率F_0
• 时域周期T_0=\frac 1{F_0}
• 抽样点数N
• 样点间增量T=\frac{T_0}{N}
• 抽样频率f_s=\frac{1}{T}=\frac{N}{T_0}=NF_0
• 模拟频率f_k=k\frac{f_s}N=\frac{k}{NT}=kF_0

3.4 DFT的性质

线性

\begin{aligned} X_3(k)&=\mathrm {DFT}[ax_1(n)+bx_2(n)]\\&=aX_1(k)+bX_2(k) \end{aligned}

圆周移位性质

• 时域移位定理：

  \mathrm {DFT}[x((n+m))_NR_N(n)]\\ =X(k)W_N^{-km}=X(k)e^{\mathrm j\frac{2\pi}{N}km}

• 频域移位定理（调制定理）：

  \mathrm {IDFT}[X((k+l))_NR_N(k)]=x(n)W_N^{nl}=x(n)e^{\mathrm j\frac{2\pi}{N}nl}

圆周翻褶序列及其DFT

\mathrm {DFT}[x(N-n)]=X(N-k)

对偶性

\mathrm {DFT}[x(n)]=X(k)\\ \mathrm {DFT}[X(n)]=N\cdot x((N-k))_NR_N(k)

圆周奇对称、偶对称、共轭对称、共轭反对称

• 圆周对称中心：有限长序列x(n)的圆周对称中心为n=0（在圆上）或n=\frac N2（在直角坐标系上）。

• 圆周偶对称：

  x(n)=x(N-n)=x((-n))_NR_N(n)

💡 圆周偶对称的例子：x(n)=(\underline {1+\mathrm j},2-\mathrm j,3+2\mathrm j,3+2\mathrm j,2-\mathrm j)，基本方法就是在后面补n=0的样值，观察是否偶对称，奇对称也同理。

• 圆周奇对称：

  x(n)=-x(N-n)=-x((-n))_NR_N(n)

• 圆周共轭对称分量（x_{ep}）和圆周共轭反对称分量（x_{op}）：

  \begin{aligned} x_{ep}(n)&=\tilde{x}_e(n)R_N(n)\\ &=\frac 12 [x((n))_N+x^*((N-n))_N]R_N(n) \end{aligned}

  \begin{aligned} x_{op}(n)&=\tilde{x}_o(n)R_N(n)\\ &=\frac 12 [x((n))_N-x^*((N-n))_N]R_N(n) \end{aligned}

💡 求x_{ep}或x_{op}，先求出x_e或x_o，然后进行混叠。

• 圆周对称的性质：

  x_{ep}(n)的实部圆周偶对称，虚部圆周奇对称

  x_{ep}=x^*_{ep}((N-n))_NR_N(n)

  x_{op}(n)的实部圆周奇对称，虚部圆周偶对称

  x_{op}=-x^*_{op}((N-n))_NR_N(n)

圆周对称性质

• 序列圆周偶对称，序列DFT圆周偶对称。
• 序列圆周奇对称，序列DFT圆周奇对称。

圆周共轭对称性质

• 共轭对称性

  \mathrm {DFT}[x^*(n)]=X^*((N-k))_NR_N(k)

  \mathrm{IDFT}[X^*(k)]=x^*((N-n))_NR_N(n)

• 复数序列的DFT

  \begin{array}{c c c}{x(n)}&=&\mathrm{Re}\bigl[x(n)\bigr]&+&\mathrm{jIm}\bigl[{x(n)}\bigr]&\\ {\updownarrow}&&{\updownarrow}&&{\updownarrow}&\\ X({k})&=&X_{ep}(k)&+&{X_{op}({k})}&\end{array}

  \begin{array}{c c c}x({n})&=&x_{ep}(n)&+&{x_{op}({n})}&\\ {\updownarrow}&&{\updownarrow}&&{\updownarrow}&\\ {X(k)}&=&\mathrm{Re}\bigl[X(k)\bigr]&+&\mathrm{jIm}\bigl[{X(k)}\bigr]&\end{array}

💡 简记：实部对应共轭对称，虚部乘\mathrm j对应共轭反对称。

DFT形式下的帕赛瓦定理

\sum^{N-1}_{n=0}x(n)y^*(n)=\frac 1N\sum^{N-1}_{n=0}X(k)Y^*(k)

如果令y(n)=x(n)，则：

\sum^{N-1}_{n=0}|x(n)|^2=\frac 1N\sum^{N-1}_{n=0}|X(k)|^2

表明序列在时域的能量与在频域的能量相等。

序列和

\sum^{N-1}_{n=0}x(n)=X(0)

初值定理

x(0)=\frac1N\sum^{N-1}_{n=0}X(k)

圆周卷积和与圆周卷积和定理

• 圆周卷积和定义：

  \begin{aligned} x_1(n)\text{\textcircled N}x_2(n)&=\sum^{N-1}_{m=0}x_1(m)x_2((n-m))_NR_N(n)\\ &=\sum^{N-1}_{m=0}x_2(m)x_1((n-m))_NR_N(n) \end{aligned}

• 圆周卷积等于周期卷积取主值序列。

• 此外，计算圆周卷积还可以使用矩阵的方法。
  例如x_1(n)=\{1,1,1\}，x_2(n)=\{1,1,2,2\}，求x_1(n)\text{\textcircled 5}x_2(n)。

  \begin{pmatrix} y(0)\\y(1)\\y(2)\\y(3)\\y(4) \end{pmatrix}= \begin{pmatrix} 1&0&2&2&1\\1&1&0&2&2\\2&1&1&0&2\\2&2&1&1&0\\0&2&2&1&1 \end{pmatrix} \begin{pmatrix} 1\\1\\1\\0\\0 \end{pmatrix}=\begin{pmatrix} 3\\2\\4\\5\\4 \end{pmatrix}

• 时域圆周卷积定理

  \mathrm {DFT}[x_1(n)\text{\textcircled N}x_2(n)]=X_1(k)X_2(k)

• 频域圆周卷积定理

  \mathrm {IDFT}[X_1(k)\text{\textcircled N}X_2(k)]=N\cdot x_1(n)x_2(n)

• 利用DFT计算圆周卷积
  1. 长度不够补0；
  2. 取DFT后相乘；
  3. 取IDFT后得到卷积结果。

线性卷积和与圆周卷积和之间的关系

线性卷积以L为周期进行周期延拓得到周期卷积，周期卷积取主值序列得到圆周卷积。如果L<N_1+N_2-1，周期延拓会出现混叠。出现混叠要左移相加。比如说圆周卷积的不进位乘法：

\begin{array}{c c c c c}{x(n)}&{}&{}&{}&{4}&{3}&{2}&{1}\\ {h(n)}&{}&{}&{}&{1}&{1}&{1}&{1}\\ \hline&{}&{}&{}&{4}&3&{2}&1\\ &{}&{}&{4}&{3}&{2}&{1}&{}\\ &{}&{4}&{3}&{2}&{1}&{}&{}\\&{4}&{3}&{2}&{1}&{}&{}\\ \hline&{4}&{7}&{9}&{10}&\underline{6}&\underline{3}&\underline{1}\\&\underline{6}&\underline{3}&\underline{1}\\ \hline{y(n)}&10&10&10&10\end{array}

3.5 频域抽样理论

频域抽样与频域抽样定理

x(n)\xrightarrow{DTFT}X(e^{\mathrm j w})\xrightarrow{N点采样}X(k)\xrightarrow{IDFT}x_N(n)

通过上图我们可以知道，IDFT还原出的x_N(n)是一个有限长序列，那就要求我们采样的原序列也是有限长序列。

• 当x(n)为无限长序列，时域的周期延拓必然会造成混叠而产生误差，只能随着采样点N的增加而逐渐接近x(n)。
• 当序列x(n)为长度为M的有限长序列，且N\ge M时，X(k)能够不失真的恢复原序列x(n)。
• 当序列x(n)为长度为M的有限长序列，且N< M时，仍有混叠失真，X(k)不能不失真的恢复原序列x(n)。

由此推出频域抽样定理：

若时域序列长度为M，则只有当频域采样点数N满足N\ge M，才有：

x_N(n)=\widetilde{x}_N(n)R_N(n)=x((n))_N R_N(n)=x(n)

即可由频域采样X(k)不失真的恢复出原信号x(n)，否则会出现时域混叠的现象。

频域的插值恢复

• X(k)还原X(z)的方法：

  \begin{aligned} X(z)&=\sum_{n=0}^{N-1}x(n)z^{-n}\\ &=\sum_{n=0}^{N-1}\bigg[\dfrac{1}{N}\sum_{k=0}^{N-1}X(k)W_N^{-nk}\bigg]z^{-n}\\ &=\dfrac{1}{N}\sum_{k=0}^{N-1}X(k)\sum_{n=0}^{N-1}\left(W_N^{-k}z^{-1}\right)^n\\ &=\dfrac{1}{N}\sum\limits_{k=0}^{N-1}X(k)\dfrac{1-W^{-kN}_Nz^{-N}}{1-W^{-k}_Nz^{-1}}\\ &=\dfrac{1-z^{-N}}{N}\sum_{k=0}^{N-1}\dfrac{X(k)}{1-W_N^{-k}z^{-1}} \\&=\sum_k^{N-1}X(k)\Phi_k(z) \end{aligned}

  其中，\Phi_k(z)=\dfrac{1}{N}\dfrac{1-z^{-N}}{1-W_N^{-k}z^{-1}}称为插值函数。插值函数只在本身采样点r=k处不为零，其他的采样点上都是零点。

• X(k)还原X(e^{\mathrm j\omega})的方法：

  由X(e^{\mathrm j\omega})=X(z)\big |_{z=e^{\mathrm j\omega}}我们能够算出:

  \begin{aligned} \Phi_k(e^{\mathrm j\omega})&=\Phi_k(z)|_{z=e^{\mathrm j\omega}}\\&=\frac{1}{N}\frac{1-z^{-N}}{1-W_N^{-k}z^{-1}}\Bigg|_{z=e^{\mathrm j\omega}}\\ &=\dfrac1N\dfrac{\sin[\dfrac N2(\omega-\dfrac2\pi N)]}{\sin[\dfrac12(\omega-\dfrac{2\pi}N k)]}e^{-\mathrm j\frac{N-1}2(\omega-\frac{2\pi}{N} k)} \end{aligned}

  \Phi(\omega)=\dfrac{1}{N}\dfrac{\sin(\omega N/2)}{\sin(\omega/2)}e^{-\mathrm j\left(\frac{N-1}{2}\right)\omega}

用离散频谱X(k)来表示X(e^{\mathrm j\omega})为：

X(e^{\mathrm j\omega})=\sum\limits_{k=0}^{N-1}X(k)\Phi\bigg(\omega-\dfrac{2\pi}{N}k\bigg)

函数\Phi\bigg(\omega-\dfrac{2\pi}{N}k\bigg)本采样点\omega_k=\dfrac{2\pi}{N}k中\Phi\bigg(\omega_k-\dfrac{2\pi}{N}k\bigg)=1，在其他采样点上函数值为0。

3.6 DFT的应用

DFT计算线性卷积

用DFT计算线性卷积就是用圆周卷积来代替线性卷积，为了不产生混叠，我们需要把x(n)和h(n)都补零到L\ge N_1+N_2-1。为了方便，我们通常会取L=2^m\ge N_1+N_2-1。总体方法为：

1. 补零。
2. 计算圆周卷积x(n)\text{\textcircled L}h(n)。
3. 求出X(k)和H(k)。
4. 利用时域卷积定理，求Y(k)=X(k)H(k)。
5. 用IDFT求出y(n)=x(n)\text{\textcircled L}h(n)。

DFT计算线性相关

该部分内容不做要求。

利用DFT对模拟信号傅里叶变换对的逼近

1. 对连续时间非周期信号的傅里叶变换的DFT逼近

   逼近过程：时域抽样——时域截断——频域抽样

   近似逼近：

   X(\mathrm jk\Omega_0)=X(\mathrm j\Omega)\Big|_{\Omega=k\Omega_0}\approx T\cdot DFT[x(n)]

   x(n)=\left.x(t)\right|_{t=nT}\approx\dfrac{1}{T}\cdot\text{IDFT}[X(\mathrm jk\Omega_0)]

   x(t)由x(n)经时域插值函数内插得到；

   X(\mathrm j\Omega)由X(\mathrm jk\Omega_0)经频域插值函数内插得到。

2. 对连续时间周期信号的傅里叶级数的DFS逼近

   逼近过程：时域抽样——频域截断

   X(\mathrm jk\Omega_0)\approx\frac1N\mathrm{DFS}[x(n)]

   x(n)=x(t)\big|_t=nT\approx N\cdot\mathrm{IDFS}[X(\mathrm jk\Omega_0)]

   x(t)由x(n)经时域插值函数内插得到。

用DFT对模拟信号做谱分析时的几个问题

1. 混叠失真

   时域采样应满足f_s>2f_h，否则会出现频谱的混叠失真。（奈奎斯特采样定理）

2. 频谱泄露

   当时域进行数据截断的时候，频谱会产生泄露。

   减少方法：

   1. 截取更长的数据。
   2. 不要突然截断，改变窗的形状。

3. 栅栏效应

   频谱限制到离散点的时候不是连续的，就像是通过“栅栏”看景象一样。

   减少方法：

   在不改变时域数据的情况下，在末端添加零值点。

   • 例子：

     比如序列x=\{1,1,1,1\}，其DTFT和DFT如图所示：

     

     黑点表示DFT，曲线表示DTFT，由于序列只有4个值，那么DFT也只有4个值。

     现在我们将序列x补零，x=\{1,1,1,1,0,0,0,0\},然后再做DFT和DTFT，得到结果如下：

     

     可见采样点间隔减小了。

用DFT对模拟信号做谱分析时参数的选择

• 频率分辨力F_0 ：频域的采样间隔。频率分辨力越小，误差越小。
• 提高频率分辨力的方法：
  1. 时域补零；
  2. T_0不变，提高f_s和N；
  3. 提高物理分辨力。

习题

• 研究有限长序列的频域特性，可以采用( )变换和( )变换。如果希望序列的连续频谱是实偶函数，那么该信号应该满足的条件是（ ）。如果希望序列的离散频谱是实数，那么该信号应该满足的条件是（ ）。

  DTFT、DFT、虚偶函数、实部偶对称，虚部奇对称。

---

• 已知x(n)=\{\underline1,2,3,4,5,6\}，该序列的圆周移位序列x((n+2))_6R_6(n)=（ ），如果\mathrm{DFT}[x(n)]=X(k)，那么\mathrm {DFT}[x(n)]=（ ）。

  \{\underline 3,4,5,6,1,2\}、6\cdot x((6-n))_6R_6(n)。

---

• 利用DFT对非周期连续信号进行频谱分析时，可能引起的误差有（ ）（ ）和（ ）。

  混叠失真、频谱泄露、栅栏效应

---

• 写出四种傅立叶变换形式的名字及其缩写，并写出各种变换对应的信号时间域和频率域的特点。
  1. 傅里叶级数 CFS 时间域连续周期 频率域离散非周期
  2. 傅里叶变换 CFT 时间域连续非周期 频率域连续非周期
  3. 离散傅里叶级数 DFS 时间域离散周期 频率域离散周期
  4. 离散傅里叶变换 DTFT 时间域离散非周期 频率域连续周期

---

• 已知x(n)-a^nR_N(n)，求频谱X(e^{\mathrm j\omega})以及其N点的DFT，并说明他们的关系。

  

---

• 答案

---

• 已知序列x(n)的共轭对称分量x_e(n)=\{1,0,0.5,\underline2,0.5,0,1\}，圆周共轭反对称分量x_{op}=\{\underline 0,-0.5,0,0.5\}，X(k)为x(n)的4点DFT，x(n)的离散时间傅里叶变换为X(e^{\mathrm j\omega})，计算：
  （1）x(n)。
  （2）\int^\pi_{-\pi}|X(e^{\mathrm j\omega})|^2\mathrm d\omega。
  （3）\mathrm{IDTFT}\{\mathrm{RE}[X(e^{\mathrm j\omega})]\}。
  （4）\sum\limits^3_{k=0}X(k)。
  （5）\mathrm{IDTFT}[X_e(e^{\mathrm j\omega})]。
  （6）X(0)。
  （7）\sum\limits^{3}_{k=0}|X(k)|^2。
  （8）X(n)的4点DFT。

---

• 已知4点序列x(n)=\{\underline1,2-\mathrm j,3+2\mathrm j,\mathrm j\}，X(e^{\mathrm j\omega})=\mathrm{DTFT}[x(n)]，X(k)=X(e^{\mathrm j\omega})\bigg|_{\omega=\frac{2\pi}{3}k},k=0,1,2。序列y(n)DFT为Y(k)，序列z(n)的DFT为X(k)。已知Y(k)=\mathrm{Re}[X(k)]，Z(k)=\mathrm{Im}[X(k)]，求序列y(n)和z(n)。

---

• 已知序列x(n)=\delta(n)+2\delta(n-1)+\delta(n-2)+3\delta(n-3)，其6点DFT为X(k)，求：
  （1）y(n)的6点DFT为Y(k)，设Y(k)=X(k)(-1)^k，求y(n)。
  （2）序列z(n)的6点DFT为Z(k)=X(k)Y(k)，求z(n)。

  （3）若有限长序列q(n)的三点DFT满足Q(k)=X(2k)，求q(n)。（这一问可以不用FFT做）

---

• 有一调幅信号x_a(t)=[1+\cos(2\pi\times 50t)]\cos(2\pi\times 2000t)，用DFT做频谱分析。要求能分辨x_a(t)的所有频率分量，确定以下各参数。
  （1）最小记录时间；
  （2）最大取样间隔；
  （3）最少采样点数；
  （4）如果该信号以8khz的采样频率进行采样，对采样信号做200点的DFT的X(k)，则X(k)中k=100对应原连续信号的频谱多少Hz？
  （5）若对200点采样信号作400点的DFT的Y(k)，则Y(k)中k=100对应原连续信号的频谱多少Hz？此时的频率分辨率是多少Hz？

---