Digital Signal Processing 1 Basic Concepts and Algorithms Week4

课程主页：https://www.coursera.org/learn/dsp1

这一讲介绍了Fourier Analysis: the Basics。

DFS(离散傅里叶序列)

DFS是DFT的周期扩展，公式如下：

合成公式：

$\mathbf x[n]=\frac{1}{N} \sum_{k=0}^{N-1}\mathbf X[k] e^{j \frac{2 \pi}{N} n k}, \quad n\in \mathbb Z$

分析公式：

$\mathbf X[k]=\sum_{n=0}^{N-1}\mathbf x[n] e^{-j \frac{2 \pi}{N} n k}, \quad k\in \mathbb Z$

不难看出$\mathbf x[n]$和$\mathbf X[k]$的周期均为$N$，连续$ N $个傅立叶系数可捕获所有信息。

DFT,DFS,DTFT

$L$周期的DFT

假设原始信号为$\bar {\mathrm x}[n]$，考虑其周期扩张$\mathrm y[n]$：

$\mathrm y[n]= \bar {\mathrm x}[n \mod M]$

现在对其做DFT得到

$\begin{aligned} X_{L}[k] &=\sum_{n=0}^{L M-1} y[n] e^{-j \frac{2 \pi}{L M} n k} \quad k=0,1,2 \ldots, L M-1 \\ &=\sum_{p=0}^{L-1} \sum_{n=0}^{M-1} y[n+p M] e^{-j \frac{2 \pi}{L M}(n+p M) k} \\ &=\sum_{p=0}^{L-1} \sum_{n=0}^{M-1} y[n] e^{-j \frac{2 \pi}{L M} n k} e^{-j \frac{2 \pi}{L} p k} \\ &=\left(\sum_{p=0}^{L-1} e^{-j \frac{2 \pi}{L} p k}\right) \sum_{n=0}^{M-1} \bar{x}[n] e^{-j \frac{2 \pi}{ M} n \frac kL} \end{aligned}$

注意到如下事实

$\sum_{p=0}^{L-1} e^{-j \frac{2 \pi}{L} p k}=\left\{\begin{array}{ll} L & k=uM, u\in \mathbb Z\\ 0 &其他 \end{array}\right.$

所以

$X_{L}[k]=\left\{\begin{array}{ll} L \bar{X}[k / L] & \text { if } k=0, L, 2 L, 3 L, \ldots \\ 0 & \text { otherwise } \end{array}\right.$

DFTF(离散时间傅里叶变换)

定义：

$\mathrm x[n] \in \ell_{2}(\mathbb{Z})$
定义$\omega \in \mathbb{R}$的函数
$F(\omega)=\sum_{n=-\infty}^{\infty} \mathrm x[n] e^{-j \omega n}$
逆变换（如果$F(\omega)$存在）：
$\mathrm x[n]=\frac{1}{2 \pi} \int_{-\pi}^{\pi} F(\omega) e^{j \omega n} d \omega, \quad n \in \mathbb{Z}$

基本性质

$F(\omega)$以$2\pi$为周期
为了表达这点，记$F(\omega)$为
$X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}$
为了方便起见，$X\left(e^{j \omega}\right)$定义在区间$[-\pi, \pi]$

例子

$x[n]=\alpha^{n} u[n]$

那么DTFT为

$\begin{aligned} X\left(e^{j \omega}\right) &=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \\ &=\sum_{n=0}^{\infty}\left(\alpha e^{-j \omega}\right)^{n} \\ &=\frac{1}{1-\alpha e^{-j \omega}} \end{aligned}$

三者比较

有限长度信号：DFT
周期序列：DFS
无限序列：DTFT

DTFT：直觉和性质

存在性

对于绝对可和序列，DFTF存在，因为

$\begin{aligned} \left|X\left(e^{j \omega}\right)\right| &=\left|\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}\right| \\ & \leq \sum_{n=-\infty}^{\infty}\left|x[n] e^{-j \omega n}\right| \\ &=\sum_{n=-\infty}^{\infty}|x[n]| \\ &<\infty \end{aligned}$

现在计算逆变换可得

$\begin{aligned} \frac{1}{2 \pi} \int_{-\pi}^{\pi} X\left(\mathrm{e}^{j \omega}\right) \mathrm{e}^{j \omega n} d \omega &=\frac{1}{2 \pi} \int_{-\pi}^{\pi}\left(\sum_{k=-\infty}^{\infty} x[k] e^{-j \omega k}\right) e^{j \omega n} d \omega \\ &=x[n] \end{aligned}$

基变换视角

将DFTF视为$\mathbb{C}^{\infty}$的内积：
$\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}=\left\langle e^{j \omega n}, x[n]\right\rangle$
“基”是无限不可数集$\left\{e^{j \omega n}\right\}_{ \omega \in \mathbb{R}}$

DFT,DFS,DTFT的比较

DFT

DFS

DFTF

性质

linearity
$\text { DTFT}\{\alpha x[n]+\beta y[n]\}=\alpha X\left(e^{j \omega}\right)+\beta Y\left(e^{j \omega}\right)$
time shift
$\text { DTFT}\{x[n-M]\}=e^{-j \omega M} X\left(e^{j \omega}\right)$
modulation (dual)
$\text { DTFT}\left\{e^{j \omega_{0} n} x[n]\right\}=X\left(e^{j\left(\omega-\omega_{0}\right)}\right)$
time reversal
$\text { DTFT}\{x[-n]\}=X\left(e^{-j \omega}\right)$
conjugation
$\text { DTFT}\left\{x^{*}[n]\right\}=X^{*}\left(e^{-j \omega}\right)$
如果$x[n]$对称，那么DTFT对称
$x[n]=x[-n] \Longleftrightarrow X\left(e^{j \omega}\right)=X\left(e^{-j \omega}\right)$
如果$x[n]$Hermitian对称，那么DTFT是Hermitian对称
$x[n]=x^{*}[n] \Longleftrightarrow X\left(e^{j \omega}\right)=X^{*}\left(e^{-j \omega}\right)$
如果$x[n]$是实数，DTFT的模长是对称的
$x[n] \in \mathbb{R} \Longleftrightarrow\left|X\left(e^{j \omega}\right)\right|=\left|X\left(e^{-j \omega}\right)\right|$
如果$x[n]$是实对称，那么$X\left(e^{j \omega}\right)$也是实对称

证明：

$\begin{aligned} \text { DTFT}\{x[n-M]\} &=\sum_{n=-\infty}^{\infty} \mathrm x[n-m] e^{-j \omega n}\\ &=\sum_{n=-\infty}^{\infty} \mathrm x[n] e^{-j \omega (n+m)}\\ &=e^{-j \omega M} X\left(e^{j \omega}\right) \end{aligned}$

$\begin{aligned} \text { DTFT}\{e^{j \omega_{0} n} x[n]\} &=\sum_{n=-\infty}^{\infty} e^{j \omega_{0} n}\mathrm x[n] e^{-j \omega n}\\ &=\sum_{n=-\infty}^{\infty} \mathrm x[n] e^{-j (\omega-\omega_0) n}\\ &=X\left(e^{j\left(\omega-\omega_{0}\right)}\right) \end{aligned}$

例子

1

$\text { DTFT}\{\delta[n]\}=\left\langle e^{j \omega n}, \delta[n]\right\rangle=1$

2.Dirac delta函数

$\text { DTFT}\{1\}=\sum_{n=-\infty}^{\infty} e^{-j \omega n}=?$

可以看到$1$的DTFT暂时没有定义，为了解决这点，引入Dirac delta函数:

$\int_{-\infty}^{\infty} \delta(t-s) f(t) d t=f(s)$

定义

$\tilde{\delta}(\omega)=2 \pi \sum_{k=-\infty}^{\infty} \delta(\omega-2 \pi k)$

那么

$\begin{aligned} \operatorname{IDTFT}\{\tilde{\delta}(\omega -\omega_0)\} &=\frac{1}{2 \pi} \int_{-\pi}^{\pi} \tilde{\delta}(\omega-\omega_0) e^{j \omega n} d \omega \\ &= \int_{-\pi}^{\pi}\sum_{k=-\infty}^{\infty} \delta(\omega-\omega_0-2 \pi k)e^{j \omega n} d \omega\\ &=\int_{-\pi}^{\pi} \delta(\omega-\omega_0-2\pi s) e^{j \omega n} d \omega,(\omega-\omega_0-2\pi s\in [-\pi ,\pi]) \\ &=\left.e^{j (\omega_0+2\pi s) n}\right|_{\omega=0}\\ &=e^{j \omega_0 n} \end{aligned}$

即

$\operatorname{IDTFT}\{\tilde{\delta}(\omega) \} = 1$

所以可得如下性质

$\text{DTFT}\{1\}=\tilde{\delta}(\omega)$
$\text{DTFT}\left\{e^{j \omega_{0} n}\right\}=\tilde{\delta}\left(\omega-\omega_{0}\right)$
$\text{DTFT}\left\{\cos \omega_{0} n\right\}=\left[\tilde{\delta}\left(\omega-\omega_{0}\right)+\tilde{\delta}\left(\omega+\omega_{0}\right)\right] / 2$
$\text{DTFT}\left\{\sin \omega_{0} n\right\}=-j\left[\tilde{\delta}\left(\omega-\omega_{0}\right)-\tilde{\delta}\left(\omega+\omega_{0}\right)\right] / 2$

变换之间的关系

周期信号

$\tilde{x}[n]=x[n \quad \bmod N]$

那么

$\begin{aligned} \tilde{X}\left(e^{j \omega}\right) &=\sum_{n=-\infty}^{\infty} \tilde{x}[n] e^{-j \omega n} \\ &=\sum_{n=-\infty}^{\infty}\left(\frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j \frac{2 \pi}{N} n k}\right) e^{-j \omega n} \\ &=\frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k]\left(\sum_{n=-\infty}^{\infty} e^{j \frac{2 \pi}{N} n k} e^{-j \omega n}\right) \\ &= \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k]\text{ DTFT}\{e^{j \frac{2 \pi}{N} n k}\}\\ &= \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k]\tilde{\delta}\left(\omega-\frac{2 \pi}{N} k\right) \end{aligned}$

紧支集信号

$\bar{x}[n]=\left\{\begin{array}{ll}x[n] & 0 \leq n<N \\ 0 & \text { otherwise }\end{array}\right.$

那么

$\begin{aligned} \bar{X}\left(e^{j \omega}\right) &=\sum_{n=-\infty}^{\infty} \bar{x}[n] e^{-j \omega n}\\ &=\sum_{n=0}^{N-1} x[n] e^{-j \omega n} \\ &=\sum_{n=0}^{N-1}\left(\frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2 \pi}{N} n k}\right) e^{-j \omega n}\\ &=\frac{1}{N} \sum_{k=0}^{N-1} X[k]\left(\sum_{n=0}^{N-1} e^{-j\left(\omega-\frac{2 \pi}{N} k\right) n}\right)\\ &= \frac{1}{N} \sum_{k=0}^{N-1} X[k] \bar{R}\left(e^{j\left(\omega-\frac{2 \pi}{N} k\right)}\right) \end{aligned}$

其中

$\begin{aligned} \bar{R}\left(e^{j\omega}\right) &= \text{DTFT}(\bar r[n])\\ \bar{r}[n] &=\left\{\begin{array}{ll} 1 & 0 \leq n<N \\ 0 & \text { otherwise } \end{array}\right. \end{aligned}$

利用定义可得

$\begin{aligned} \bar{R}\left(e^{j \omega}\right) &=\sum_{n=0}^{N-1} e^{-j \omega n} \\ &=\frac{1-e^{-j \omega N}}{1-e^{-j \omega}} \\ &=\frac{e^{-j \frac{\omega N}{2}}\left[e^{j \frac{\omega N}{2}}-e^{-j \frac{\omega N}{2}}\right]}{e^{-j \frac{\omega}{2}}\left[e^{j \frac{\omega}{2}}-e^{-j \frac{\omega}{2}}\right]} \\ &=\frac{\sin \left(\frac{\omega}{2} N\right)}{\sin \left(\frac{\omega}{2}\right)} e^{-j \frac{\omega}{2}(N-1)} \end{aligned}$

0填充

考虑

${x}'[n]=\left\{\begin{array}{ll}x[n] & 0 \leq n<N \\ 0 & N\le n < M \end{array}\right.$

那么

$\begin{aligned} X_{M}[h] &=\sum_{n=0}^{M-1} x^{\prime}[n] e^{-j \frac{2 \pi}{M} n h}\\ &=\sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{M} n h} \\ &=\sum_{n=0}^{N-1}\left(\frac{1}{N} \sum_{k=0}^{N-1} X_{N}[k] e^{j \frac{2 \pi}{N} n k}\right) e^{-j \frac{2 \pi}{M} n h} \\ &=\frac{1}{N} \sum_{k=0}^{N-1} X_{N}[k]\left(\sum_{n=0}^{N-1} e^{-j\left(\frac{2 \pi}{M} h-\frac{2 \pi}{N} k\right) n}\right) \\ &=\left.\bar{X}\left(e^{j \omega}\right)\right|_{\omega=\frac{2 \pi}{M} h} \\ \end{aligned}$

注意最后一步由定义得到：

$X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}$

Sinusoidal Modulation

FFT

DFT的时间复杂度为$O(N^2)$，现在希望减少其时间复杂度，这里介绍FFT。

记

$W_N=e^{-j \frac{2 \pi}{N}}$

如果$N$明确，那么简记为$W$。

假设$N$为$2$的幂，对DFT进行变形：

$\begin{aligned} X[k]=& \sum_{n=0}^{N / 2-1} x[2 n] W^{2 n k}+\sum_{n=0}^{N / 2-1} x[2 n+1] W^{(2 n+1) k} \\ =& \sum_{n=0}^{N / 2-1} x[2 n] W^{2 n k}+\sum_{n=0}^{N / 2-1} x[2 n+1] W^{2 n k+k} \\ =& \sum_{n=0}^{N / 2-1} x[2 n] W_{N / 2}^{n k}+W^{k} \sum_{n=0}^{N / 2-1} x[2 n+1] W_{N / 2}^{n k} \\ =& X_{k}^{\prime}+W^{k} X^{\prime \prime}_{k}, \quad k=0,1, \ldots, N-1 \end{aligned}$

所以$X[k]$可由两个DFT($X_k’,X_k’’$)计算得到，现在对其变形可得：

$\begin{aligned} X[k]&=X_{k}^{\prime}+W^{k} X^{\prime \prime}_{k}, \quad k=0,1, \ldots, \frac{N}{2}-1 \\ X[k+N / 2]&= \sum_{n=0}^{N / 2-1} x[2 n] W_{N / 2}^{n(k+N / 2)}+W^{k+N / 2} \sum_{n=0}^{N / 2-1} x[2 n+1] W_{N / 2}^{n(k+N / 2)} \\ &=\sum_{n=0}^{N / 2-1} x[2 n] W_{N / 2}^{n k}-W^{k} \sum_{n=0}^{N / 2-1} x[2 n+1] W_{N / 2}^{n k} \\ &=X_{k}^{\prime}-W^{k} X^{\prime \prime}_{k}, \quad k=0,1, \ldots, \frac{N}{2}-1 \end{aligned}$

所以不难得到时间复杂度$T(N)$的关系为

$T(N)=2T(N/2) + O(N)$

所以

$T(N)=O(N\log N)$

DFT的矩阵分解视角

分离偶数和奇数样本
计算两个大小为$N、2$的DFT，分别输出$ X ^ {\prime} [k] $和$ X ‘’[k] $
计算$ X’ [k] $和$ W ^ {k} X’’ [k] $的和与差

来看一个具体例子：

$\mathbf{W}_{8}=\left[\begin{array}{cccccc} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & W^{1} & W^{2} & W^{3} & \dots & W^{7} \\ 1 & W^{2} & W^{4} & W^{6} & \dots & W^{14} \\ 1 & W^{7} & W^{14} & W^{21} & \dots & W^{49} \end{array}\right]$

第一个步骤对应的矩阵为

$\mathbf{D}_{8}=\left[\begin{array}{llllllll} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right]$

第二个步骤对应的矩阵为

$\left[\begin{array}{cc} \mathrm{W}_{4} & 0_{4} \\ 0_{4} & \mathrm{W}_{4} \end{array}\right]=\left[\begin{array}{ccccccc} 1 & 1 & 1 & 1 & & & \\ 1 & j & -1 & -j & & & & \\ 1 & -1 & 1 & -1 & & & & \\ 1 & -j & -1 & j & & & & \\ & & & & 1 & 1 & 1 & 1 \\ & & & & 1 & j & -1 & -j \\ & & & & 1 & -1 & 1 & -1 \\ & & & & 1 & -j & -1 & j \end{array}\right]$

第三个步骤的第一部分对应如下矩阵

$\left[\begin{array}{ll} I_{4} & 0_{4} \\ 0_{4} & \Lambda_{4} \end{array}\right]= \left[\begin{array}{cccccccc} 1 & & & & \\ & 1 & & \\ & & 1 & \\ & & & 1& \\ & & & & 1\\ & & & && W \\ & & & &&& W^2 \\ & & & &&&& W^{3} \end{array}\right]$

第二部分对应如下矩阵

$\mathbf{S}_{8}=\left[\begin{array}{cc} \mathbf{I}_{4} & \mathbf{I}_{4} \\ \mathbf{I}_{4} & -\mathbf{I}_{4} \end{array}\right]=\left[\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 \end{array}\right]$

综上，矩阵分解如下

$\mathrm{W}_{8}= \left[\begin{array}{cc} \mathrm{I}_{4} & \mathrm{I}_{4} \\ {\mathrm{l}_{4}} & -\mathrm{I}_{4} \end{array}\right] \cdot \left[ \begin{array}{cc} \mathrm{I}_{4} & 0_{4} \\ 0_{4} & \Lambda_{4} \end{array} \right] \cdot \left[\begin{array}{cc} \mathrm{W}_{4} & 0_{4} \\ 0_{4} & \mathrm{W}_{4} \end{array}\right] \cdot \mathrm{D}_{8}$

习题

1

(Difficulty: $\star$ ) Consider the magnitude DTFTs $\left|X\left(e^{j \omega}\right)\right|$ and $\left|Y\left(e^{j \omega}\right)\right|$ shown below, where vertical lines represent Dirac deltas:

Both underlying signals $x[n]$ and $y[n]$ are periodic. Find their periods and write them below, separated by a space. Please write the smallest period, i.e. a 5 -periodic signal is also obviously 15 -periodic but we’re interested in 5.
Enter the period of $x[n]$ and $y[n]$ with a unique white space in between.

查看频率即可，$x$的频率为

$\pm \frac {k\pi}{6},k=0,\ldots ,6$

对应的周期为

$\frac{12}{k } ,k=1,\ldots, 6$

所以$x$的周期为

$12$

$y$的频率为

$\pm \frac {2\pi }3$

所以$y$的周期为

$3$

答案为

12 6

2

(Difficulty: $\star$ ) We will see in later lectures that communication systems must fulfill what is called the “bandwidth constraint”, that is, the energy of the signals that they transmit must strictly fit into pre-defined frequency bands. In this problem we will look at the bandwidth constraint in the discrete-time domain.

The signal $x[n]$ is real-valued and its spectrum is nonzero only over the $[-\pi / 8, \pi / 8]$ interval. Due to the bandwidth constraint we need to “fit” the signal over the bands indicated in green in the following figure

To this aim, we need to design a processing block $\mathcal{H}$ in order to convert $x[n]$ into a sequence $s[n]$ satisfying the following requirements:
The support of the DTFT of $s[n]$ must be limited to $[-3 \pi / 4,-\pi / 2] \cup[\pi / 2,3 \pi / 4]$
The sequence $s[n]$ must be real-valued $(x[n]$ is real-valued)
Which of the following input/output relationships for $\mathcal{H}$ meet both requirements? (check all correct answers):

$s[n]=e^{j \frac{5 \pi}{8} n} \cdot x[n]$
$s[n]=\sin \left(\frac{21 \pi}{8} n\right) \cdot x[n]$
$s[n]=\cos \left(\frac{5 \pi}{8} n\right) \cdot x[n]$
$s[n]=\operatorname{IDTFT}\left\{X\left(e^{j(\omega-5 \pi / 8)}\right)\right\}$

回顾如下公式

$\begin{aligned} \text { DTFT }\left\{x[n] \cos \left(\omega_{c} n\right)\right\} &=\text { DTFT}\left\{\frac{1}{2} e^{j \omega_{c} n} x[n]+\frac{1}{2} e^{-j \omega_{c} n} x[n]\right\} \\ &=\frac{1}{2}\left[X\left(e^{j\left(\omega-\omega_{c}\right)}\right)+X\left(e^{j\left(\omega+\omega_{c}\right)}\right)\right]\\ \text { DTFT }\left\{x[n] \sin \left(\omega_{c} n\right)\right\} &=\text { DTFT}\left\{\frac{1}{2j} e^{j \omega_{c} n} x[n]-\frac{1}{2j} e^{-j \omega_{c} n} x[n]\right\} \\ &=\frac{1}{2j}\left[X\left(e^{j\left(\omega-\omega_{c}\right)}\right)-X\left(e^{j\left(\omega+\omega_{c}\right)}\right)\right] \end{aligned}$

而

$\sin \left(\frac{21 \pi}{8} n\right) = \sin \left( \frac {5\pi} 8\right)$

注意第四项不满足实数的要求，所以选择2,3

3

(Difficulty: $\star$ ) Consider the length- $L$ signal
$x[n]=\left\{\begin{array}{ll}1 & 0 \leq n \leq M-1 \\ 0 & M \leq n \leq L-1\end{array}\right.$
Write out the closed-form analytical expression for its DFT coefficients $X[k]$
Be careful with your typing since the regular-expression parser can be a bit picky. Check Coursera help to enter math expression. In particular, remember that in the Coursera platform the symbols are different:
$I(\text { capital i) is used for the imaginary unit instead of } j$

Euler’s number is $E$ instead of $e$
you can also use the exponential function $\exp (\cdot)$
$\pi$ is defined as $p i$
The only other symbols you’ll need for the answer are the case-sensitive variables $k, M, L$
Finally, do not forget to validate your syntax by clicking “Preview” before submitting your answer.
For instance, the expression $e^{j(\pi L+3 \pi)} /(k+M)$ should be entered as

利用定义可得

$\begin{aligned} \mathbf X[k] &=\sum_{n=0}^{L-1}\mathbf x[n] e^{-j \frac{2 \pi}{L} n k}\\ &=\sum_{n=0}^{M-1}e^{-j \frac{2 \pi}{L} n k}\\ &= \frac{1-e^{-j\frac{2\pi}{L}kM}}{1-e^{-j\frac{2\pi}{L}k}}\\ &= \frac{\sin \frac{\pi kM}{L}}{\sin \frac{\pi k}{L}}e^{-\frac{j\pi k(M-1)}{L}} \end{aligned}$

E^(-I*pi/L*(M-1)*k)*sin(pi/L*M*k)/sin(pi/L*k)

4

The real and imaginary parts of $X\left(e^{j \omega}\right)$ are:

After examining the plots, check all the correct statements below.

$x[n]$ is Hermitian-symmetric $x[n]=x^{*}[-n]$
$x[n]$ is 0-mean, i.e. $\sum_{n \in \mathbb{Z}} x[n]=0$
$x[n]$ is real-valued.

回顾如下性质：

如果$x[n]$Hermitian对称，那么DTFT是Hermitian对称
$x[n]=x^{*}[n] \Longleftrightarrow X\left(e^{j \omega}\right)=X^{*}\left(e^{-j \omega}\right)$
如果$x[n]$是实数，DTFT的模长是对称的
$x[n] \in \mathbb{R} \Longleftrightarrow\left|X\left(e^{j \omega}\right)\right|=\left|X\left(e^{-j \omega}\right)\right|$

另一方面

$\sum_{n \in \mathbb{Z}} x[n]=\text{DFT}\left(X^{*}\left(e^{-j \omega}\right)\right)\big |_{\omega=0}=0$

所以选2,3

5

(Difficulty: $\star \star)$ Consider a signal $x[n]$ and its DTFT $X\left(e^{j \omega}\right) .$ Assume $X\left(e^{j \omega}\right)$ is differentiable. Compute the inverse DTFT of
$j \frac{d}{d \omega} X\left(e^{j \omega}\right)$

注意到

$X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}$

所以

$j \frac{d}{d \omega} X\left(e^{j \omega}\right) =\sum_{n=-\infty}^{\infty}n x[n] e^{-j \omega n}$

即

$\text{IDTFT}\left(j \frac{d}{d \omega} X\left(e^{j \omega}\right)\right)=nx[n]$

n*x[n]

6

(Difficulty: $\star$ ) Which property of the DTFT allows you to easily compute the inverse DTFT of $4 X\left(e^{j \omega}\right) / \pi-2$ once you know $x[n] ?$ Just type the name of the property.

linearity

7

(Difficulty: $\star$ ) Take a length- $N$ signal $x[n]$ and its DFT $X[k],$ with $0 \leq n, k, \leq N-1$. Next, consider its periodized version $\tilde{x}[n]=x[n \bmod N]$ with its DFS $\tilde{X}[k]$ where now $n, k \in \mathbb{Z}$
Which of the following statements are true?

$\tilde{X}[-2]=X[2]$ for all $x[n]$ and $N>2$
$\tilde{X}[l]=X[l \bmod N],$ for all $l \in \mathbb{Z}$
$\tilde{X}[k+l N]=X[k],$ for all $l \in \mathbb{Z}$ and $k=0, \ldots, N-1$

由定义可得

$\begin{aligned} \tilde{\mathbf X}[k] &=\sum_{n=0}^{N-1} \tilde{\mathbf x}[n] e^{-j \frac{2 \pi}{N} n k}\\ &= \sum_{n=0}^{N-1} {\mathbf x}[n] e^{-j \frac{2 \pi}{N} n k}\\ &= \sum_{n=0}^{N-1} {\mathbf x}[n] e^{-j \frac{2 \pi}{N} n (k\mod N)}\\ &= {\mathbf X}[k\mod N] \end{aligned}$

所以选择2,3

8

(Difficulty: $\star$ ) In the class, we learned how the modulation theorem can help us tune a musical instrument. Martin showed us an example with a bass but of course the same works with a classical guitar. Listen carefully to these two samples (with earphones, if possible); each audio clip is the recording of two notes played together:

Addio clip A
Audio clip B

Select the correct options below.

The notes are in tune in both audio clips
The notes are in tune in audio clip $A$ and out of tune in audio clip $B$
The notes are out of tune in both audio clips
The notes are in tune in audio clip $\mathrm{B}$ and out of tune in audio clip $\mathrm{A}$

这题不太理解，选第二项

9

(Difficulty: $\star \star)$ A ringback tone is the sound you hear in your landline telephone when the remote phone you are trying to call is ringing.
In most European countries, the ringback tone is a single sinusoid turned on and off periodically while in the USA, the ringbback tone is the sum of 2 sinusoids with relatively close frequencies turned on and off periodically.
Here are two audio clips:

Sample $A$
Sample $B$

Just by listening to the clips, you should be able to identify the US ringback tone. Explain in the box below what helped you identify the US tone. Use the wording and concepts that appear in the lecture slides. No credit, without a proper explanation, e.g., “I live there” is not an answer.
(use only lowercase letters in your answer)

US tone has beats from the frequency

10

(Difficulty: $\star$ ) As explained in previous question, the European and US ringback tones are composed of one or two sinusoids respectively, multiplied by a square wave switching between 0 and $1 .$ This multiplication by a square wave periodically mutes the sinusoid(s).
Look at the following magnitude DTFT plots (each plot shows the interval $[-\pi, \pi]):$

Select the correct statement amongst the choices below.

Spectrum (a) corresponds to the European ringback tone.
Spectrum (a) corresponds to the US ringback tone.
Spectrum (b) corresponds to the European ringback tone.
Spectrum (b) corresponds to the US ringback tone.

选择第一项

11

(Difficulty: $\star$ ) Consider the sequences

$\begin{array}{l} x_{1}[n]=\cos (2 \pi n \cdot \sqrt{2} / 30) \\ x_{2}[n]=\cos (2 \pi n \cdot 1.41421356 / 30) \end{array}$

with $n \in \mathbb{Z}$
Select the correct statements below.

There exists $N \in \mathbb{N}$ for which $x_{1}[n]$ has a DFS of size $N$
There exists $N \in \mathbb{N}$ for which $x_{2}[n]$ has a DFS of size $N$

只要考虑周期性即可，选择第二项。

12

(Difficulty: $\star \star$ ) Consider a signal $x[n] ;$ the only thing we know about the signal is that its DTFT is strictly bandlimited between $-\frac{\pi}{10}$ and $\frac{\pi}{10} .$ We now modulate the signal to obtain $y[n]=x[n] \cos \left(\omega_{c} n\right)$
Among the possibilities below, select all the values for $\omega_{c}$ that allow us to perfectly demodulate $y[n]$

$\frac{\pi}{20}$
$\frac{\pi}{3}$
$\frac{9\pi}{10}$
$\frac{11 \pi}{12}$

条件是不重叠，并且频率为高频（小于等于$\pi$但接近$\pi $）

$|\frac{\pi}{20}-\frac \pi {10}| <\frac{\pi}{10}$
$|\frac{\pi}{3}-\frac \pi {10}| >\frac{\pi}{10},|\frac{\pi}{3}+\frac \pi {10}|<\pi $
$|\frac{9\pi}{10}-\frac \pi {10}| >\frac{\pi}{10},|\frac{9\pi}{10}+\frac \pi {10}|=\pi$
$|\frac{11\pi}{12}-\frac \pi {10}| >\frac{\pi}{10},|\frac{11\pi}{12}+\frac \pi {10}|>\pi$

所以选择2,3