Digital Signal Processing 1 Basic Concepts and Algorithms Week3

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

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

通过改变基向量进行探索

数学设置

• 让我们从有限长度的信号开始（即$ \mathbb {C} ^ {N} $中的向量）
• 傅立叶分析是对基向量的简单变换
• 基向量的改变会改观点
• 改变观点可以揭示事物（如果基向量选的好）

$\mathbb C^N$中的傅里叶基向量

$\left\{\mathbf{w}^{(k)}\right\}_{k=0,1}, \ldots, N-1$是$\mathbb C^N$中正交基，其中$\mathbf w_{n}^{(k)}=e^{j \frac{2 \pi}{N} n k}$，也记作$\mathbf w_k[n]$。

证明：

$$\begin{aligned} \begin{aligned} \left\langle\mathbf{w}^{(k)}, \mathbf{w}^{(h)}\right\rangle &=\sum_{n=0}^{N-1}\left(e^{j \frac{2 \pi}{N} n k}\right)^{*} e^{j \frac{2 \pi}{N} n h} \\ &=\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N}(h-k) n}\\ &=\left\{\begin{array}{ll} N & \text { for } h=k \\ \frac{1-e^{j 2 \pi(h-k)}}{1-e^{j \frac{2 \pi}{N}(h-k)}}=0 & \text { otherwise } \end{array}\right. \end{aligned} \end{aligned}$$

注意上述基向量不是标准正交的，要得到标准正交基需要乘以$\frac 1 {\sqrt N}$

DFT(离散傅里叶变换)

基本公式

利用坐标变换的原理得到基本公式。

分析公式：

$$\mathbf X_{k}=\left\langle\mathbf{w}^{(k)}, \mathbf{x}\right\rangle$$

合成公式：

$$\mathbf{x}=\frac{1}{N} \sum_{k=0}^{N-1}\mathbf X_{k} \mathbf{w}^{(k)}$$

向量形式

定义

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

那么基变换矩阵为$\mathbf{W}$，其中$\mathbf{W}[n, m]=W_{N}^{n m}$：

$$\mathbf{W}=\left[\begin{array}{cccccc} 1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & W^{1} & W^{2} & W^{3} & \cdots & W^{N-1} \\ 1 & W^{2} & W^{4} & W^{6} & \cdots & W^{2(N-1)} \\ & & & \cdots & & \\ 1 & W^{N-1} & W^{2(N-1)} & W^{3(N-1)} & \ldots & W^{(N-1)^{2}} \end{array}\right]$$

那么基本公式的向量形式如下。

分析公式：

$$\mathbf X=\mathbf W\mathbf x$$

合成公式：

$$\mathbf x=\frac{1}{N}\mathbf W^{H}\mathbf X$$

信号形式

分析公式：

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

合成公式：

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

例子

例1

$$\mathbf x[n]=\delta[n], \quad\mathbf x[n] \in \mathbb{C}^{N}$$

进行DFT得到：

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

例2

$$\mathbf x[n]=1, \quad\mathbf x[n] \in \mathbb{C}^{N}$$

进行DFT得到：

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

例3

$$\mathbf x[n]=3 \cos (2 \pi / 16 n), \quad \mathbf x[n] \in \mathbb{C}^{64}$$

首先对形式进行改写：

$$\begin{aligned} \mathbf x[n] &=3 \cos \left(\frac{2 \pi}{16} n\right) \\ &=3 \cos \left(\frac{2 \pi}{64} 4 n\right) \\ &=\frac{3}{2}\left[e^{j \frac{2 \pi}{64} 4 n}+e^{-j \frac{2 \pi}{64} 4 n}\right] \\ &=\frac{3}{2}\left(\mathbf w_{4}[n]+\mathbf w_{60}[n]\right) \end{aligned}$$

进行DFT得到：

$$\begin{aligned} \mathbf X[k] &=\left\langle\mathbf w_{k}[n], \mathbf x[n]\right\rangle \\ &=\langle \mathbf w_{k}[n], \frac{3}{2}\left(\mathbf w_{4}[n]+\mathbf w_{60}[n]\right)\rangle \\ &=\frac{3}{2}\left\langle \mathbf w_{k}[n], \mathbf w_{4}[n]\right\rangle+\frac{3}{2}\left\langle \mathbf w_{k}[n], \mathbf w_{60}[n]\right\rangle \\ &=\left\{\begin{array}{ll} 96 & \text { for } k=4,60 \\ 0 & \text { otherwise } \end{array}\right. \end{aligned}$$

例4

$$\mathbf x[n]=3 \cos (2 \pi / 16 n+\pi /3), \quad \mathbf x[n] \in \mathbb{C}^{64}$$

首先对形式进行改写：

$$\begin{aligned} \mathbf x[n] &=3 \cos \left(\frac{2 \pi}{16} n+\frac{\pi}{3}\right) \\ &=3 \cos \left(\frac{2 \pi}{64} 4 n+\frac{\pi}{3}\right) \\ &=\frac{3}{2}\left[e^{j \frac{2 \pi}{64} 4 n} e^{j \frac{\pi}{3}}+e^{-j \frac{2 \pi}{64} 4 n} e^{-j \frac{\pi}{3}}\right] \\ &=\frac{3}{2}\left(e^{j \frac{\pi}{3}}\mathbf w_{4}[n]+e^{-j \frac{\pi}{3}}\mathbf w_{60}[n]\right) \end{aligned}$$

进行DFT得到：

$$\begin{aligned} \mathbf X[k] &=\left\langle\mathbf w_{k}[n], \mathbf x[n]\right\rangle \\ &=\left\{\begin{array}{ll} 96e^{j\frac \pi 3} & \text { for } k=4 \\ 96e^{-j\frac \pi 3} & \text { for } k=60 \\ 0 & \text { otherwise } \end{array}\right. \end{aligned}$$

例5

$$\mathbf x[n]=\sum_{h=0}^{M-1} \delta[n-h], \quad n=0,1, \ldots, N-1$$

进行DFT得到：

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

DFT图的解释

能量分布

回顾Parseval等式：

$$\|\mathbf{x}\|^{2}=\sum\left|\alpha_{k}\right|^{2}$$

所以

$$\sum_{n=0}^{N-1}|\mathbf x[n]|^{2}=\frac{1}{N} \sum_{k=0}^{N-1}|\mathbf X[k]|^{2}$$

（注意这里基向量的模长为$N$）

实信号的DFT

对于实信号，我们有

$$\mathbf x[n]^\star = \mathbf x[n]$$

所以

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

所以

$$|\mathbf X[k]|=|\mathbf X[N-k]| \text { for } k=1,2, \ldots,\lfloor N / 2\rfloor$$

习题

1

(Difficulty: $\star$ ) Write out the phase of the complex numbers $a_{1}=1-\mathrm{j}$ and $a_{2}=-1-\mathrm{j}$
Express the phase in degrees and separate the two phases by a single white space. Each phase should be a number in the range [-180,180]

-45 -135

2

(Difficulty: $\star$ ) Let $W_{N}^{k}=e^{-\mathrm{j} \frac{2 \pi} Nk} $ and $N>1$. Then $W_{N}^{N / 2}$ is equal to…

• -1
• 1
• $-\mathrm{j}$
• $e^{-j(2 \pi / N)+N}$

$$W_{N}^{N / 2}=e^{-\mathrm{j} \frac{2 \pi} N N/2}= e^{-\mathrm{j}\pi}=-1$$

3

(Difficulty: $\star$ ) Which of the following signals (continuous- and discrete-time) are periodic signals?
Note that $t \in \mathbb{R}$ and $n \in \mathbb{Z}$

• $x[n]=\sin (n)$
• $x(t)=t- \text{floor} (t)$
• $x[n]=e^{-\mathrm{j} f_{0} n}+e^{+\mathrm{j} f_{0} n},$ where $f_{0}=\sqrt{2}$
• $x(t)=\cos \left(2 \pi f_{0} t+\phi\right)$ with $f_{0} \in \mathbb{R}$
• $x[n]=1$

周期函数如下：

• $x(t)=t- \text{floor} (t)$
• $x(t)=\cos \left(2 \pi f_{0} t+\phi\right)$ with $f_{0} \in \mathbb{R}$
• $x[n]=1$

4

(Difficulty: $\star \star \star)$ Choose the correct statements from the choices below.

• Consider the length- $N$ signal $x[n]=(-1)^{n}$ with $N$ even. Then $X[k]=0$ for all $k$ except $k=N / 2$
• If we apply the DFT twice to a signal $x[n],$ we obtain the signal itself scaled by $N$, i.e. $N x[n]$
• Consider the length- $N$ signal $x[n]=\cos \left(\frac{2 \pi}{N} L n+\phi\right),$ where $N$ is even and $L=N / 2 .$ Then $X[k]=\left\{\begin{array}{ll}\frac{N}{2} e^{\mathrm{j} \phi} & \text { for } k=L \\ 0 & \text { otherwise }\end{array}\right.$

选项1：

$$\begin{aligned} X[k]&=\sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n k}\\ &=\sum_{n=0}^{N-1} (-1)^n e^{-j \frac{2 \pi}{N} n k}\\ &=\sum_{n=0}^{N-1} e^{-j\pi n} e^{-j \frac{2 \pi}{N} n k}\\ &=\sum_{n=0}^{N-1} e^{-j\pi n(1+\frac{2k}{N})}\\ &=\left\{\begin{array}{lc} 0, & k\neq \frac N 2 \\ N, & k= \frac N 2 \end{array}\right. \end{aligned}$$

所以该选项正确。

选项2：

见补充习题1，该选项错误。

选项3：

$$\begin{aligned} X[k]&=\sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n k}\\ &=\sum_{n=0}^{N-1}\cos \left(\frac{2 \pi}{N} L n+\phi\right)e^{-j \frac{2 \pi}{N} n k}\\ &=\sum_{n=0}^{N-1} \frac{e^{-j\left(\frac{2 \pi}{N} L n+\phi\right)} +e^{j\left(\frac{2 \pi}{N} L n+\phi\right)} }{2}e^{-j \frac{2 \pi}{N} n k}\\ &=\frac 1 2 e^{-j\phi} \sum_{n=0}^{N-1}e^{-j\frac{2 \pi}{N} (L+k) n}+ \frac 1 2 e^{j\phi} \sum_{n=0}^{N-1}e^{j\frac{2 \pi}{N} (L-k) n}\\ &=\left\{\begin{array}{lc} \frac N 2 \left(e^{j\phi}+ e^{-j\phi}\right), & k=L \\ 0, & k\neq L \end{array}\right. \end{aligned}$$

所以该选项正确。

5

(Difficulty: $\star$ ) Consider the Fourier basis $\left\{\mathbf{w}^{k}\right\}_{k=0, \ldots, N-1},$ where $\mathbf{w}^{k}[n]=e^{-j \frac{2 \pi}{N} n k}$ for $0 \leq n \leq N-1$
Select the correct statement below.

• The orthogonality of the vectors depends on the length $N$ of the elements of the basis

• The elements of the basis are orthogonal:

  $\left\langle\mathbf{w}^{i}, \mathbf{w}^{j}\right\rangle=\left\{\begin{array}{ll}N & \text { for } i=j \\ 0 & \text { otherwise }\end{array}\right.$

• The elements of the basis are orthonormal:
  $\left\langle\mathbf{w}^{i}, \mathbf{w}^{j}\right\rangle=\left\{\begin{array}{ll}1 & \text { for } i=j \\ 0 & \text { otherwise }\end{array}\right.$

显然第二项正确

6

(Difficulty: $\star \star)$ Consider the three sinusoids of length $N=64$ as illustrated in the above figure; note that the signal values are shown from $n=0$ to $n=63$

Call $y_{1}[n]$ the blue signal, $y_{2}[n]$ the green and $y_{3}[n]$ the red. Further, define $x[n]=y_{1}[n]+y_{2}[n]+y_{3}[n]$
Choose the correct statements from the list below. Note that the capital letters indicate the DFT vectors.

• $Y_{1}[k]=\left\{\begin{array}{ll}N & \text { for } k=4,60 \\ 0 & \text { otherwise }\end{array}\right.$
• $Y_{3}[k]=\left\{\begin{array}{ll}32 & \text { for } k=0 \\ 32 & \text { for } k=64 \\ 0 & \text { otherwise }\end{array}\right.$
• $Y_{2}[k]=\left\{\begin{array}{ll}16 j & \text { for } k=8 \\ 16 j & \text { for } k=56 \\ 0 & \text { otherwise }\end{array}\right.$
• $|x|_{2}^{2}=|X|_{2}^{2}=12800$

首先写出信号：

$$\begin{aligned} y_1[n]&=2 \cos \frac{2 \pi}{64} 4 n=e^{j\frac{2\pi}{64}4n} +e^{-j\frac{2\pi}{64}4n} =w_{4}[n]+w_{60}[n]\\ y_2[n]&=\frac 1 2 \sin \frac{2 \pi}{64} 8 n=-\frac j 4\left (e^{j\frac{2\pi}{64}8n} -e^{-j\frac{2\pi}{64}8n}\right) =-\frac j 4\left (w_{8}[n]-w_{56}[n]\right)\\ y_3[n]&= 1 \end{aligned}$$

所以

$$\begin{aligned} Y_{1}[k]&=\left\{\begin{array}{ll}N & \text { for } k=4,60 \\ 0 & \text { otherwise }\end{array}\right.\\ Y_{2}[k]&=\left\{\begin{array}{ll}-16j & k=8 \\ 16j&k=56\\ 0 & \text { otherwise }\end{array}\right.\\ Y_{3}[k]&=64\delta[k] \end{aligned}$$

另一方面

$$\begin{aligned} \|X\|_2^2 &=\| Y_{1}\|_2^2+\| Y_{2}\|_2^2+\| Y_{3}\|_2^2\\ &=2\times64^2 +2\times 16^2+64^2\\ &=12800\\ \|x\|_2^2 &= \|X\|_2^2/64\\ &=200 \end{aligned}$$

因此选则第1项

7

(Difficulty: $\star \star \star)$ Consider the length- $N$ signal

$$x[n]=\cos \left(2 \pi \frac{L}{M} n\right)$$

where $M$ and $L$ are integer parameter with $0<L \leq N-1,0<M \leq N$
Choose the correct statements among the choices below.

• Consider the circularly shifted signal $y[n]=x[(n-D) \bmod N] .$ In the Fourier domain, since the DFT operator is shift invariant, it is $Y[k]=X[k]$
• In general, it will be easier to compute the norm of the signal $|\mathbf{x}|_{2}$ in the Fourier domain, using the Parseval’s Identity.
• If $M=N$ and $2 L<N$, the signal has exactly $L$ periods for $0 \leq n<N$
• For every choice of $N$ and $M$, the DFT $X[k]$ has two elements different from zero.

注意在选项3的条件下，周期为$ \frac M L$，所以在$0 \leq n<N$该区间内有$L$个周期，第四项由前一题的讨论可知正确。

选择3,4

8

(Difficulty: $\star$ ) Consider an orthogonal basis $\left\{\phi_{i}\right\}_{i=0, \ldots, N-1}$ for $\mathbb{R}^{N}$. Select the statements that hold for any
vector $\mathbf{x} \in \mathbb{R}^{N}$.

• $|\mathbf{x}|_{2}^{2}=\sum_{i=0}^{N-1}\left|\left\langle x, \phi_{i}\right\rangle\right|^{2}$
• $|\mathbf{x}|_{2}^{2}=\sum_{i=0}^{N-1}\left|\left\langle x, \phi_{i}\right\rangle\right|^{2}$ if and only if $\left|\phi_{i}\right|_{2}=1 \forall i$.
• $\begin{array}{l}|\mathbf{x}|_{2}^{2}=\frac{1}{P} \sum_{i=0}^{N-1}\left|\left\langle x, \phi_{i}\right\rangle\right|^{2} , \text { if and only if }\left|\phi_{i}\right|_{2}=P \forall i \text { . }\end{array}$
• $|\mathbf{x}|_{2}^{2}=\frac{1}{P} \sum_{i=0}^{N-1}\left|\left\langle x, \phi_{i}\right\rangle\right|^{2}$ if and only if $\left|\phi_{i}\right|_{2}^{2}=P \forall i$

利用如下公式即可

$$\sum_{n=0}^{N-1}|x[n]|^{2}=\frac{1}{N} \sum_{k=0}^{N-1}|X[k]|^{2}$$

其中

$$\left\langle\mathbf{w}^{(h)}, \mathbf{w}^{(h)}\right\rangle=N$$

所以选2,4

9

(Difficulty: $\star \star)$ Pick the correct sentence(s) among the following ones regarding the DFT $\mathbf{X}$ of a signal $\mathbf{x}$ of length $N,$ where $N$ is odd.
Remember the following definitions for an arbitrary signal (asterisk denotes conjugation):
hermitian-symmetry: $x[0]$ real and $x[n]=x[N-n]^{}$ for $n=1, \ldots, N-1$
hermitian-antisymmetry: $x[0]=0$ and $x[n]=-x[N-n]^{}$ for $n=1, \ldots, N-1$

• If the signal $\mathbf{x}$ is hermitian-symmetric, then its DFT is real.
• If the signal $\mathbf{x}$ is purely real, then the DFT $\mathbf{X}$ is purely imaginary.
• If the signal $\mathbf{x}$ is hermitian antisymmetric, then its DFT $\mathbf{X}$ is purely imaginary.
• If the signal $\mathbf{x}$ is hermitian-symmetric, then the DFT $\mathbf{X}$ is also hermitian-symmetric.

回顾DFT：

$$X[k]=\sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n k}$$

如果$\mathrm x$满足hermitian-symmetric，那么

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

所以$X[k]$为实数。

如果$\mathrm x$满足hermitian antisymmetric,那么

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

所以$X[k]$为纯虚数。

如果$\mathrm x$是实数，那么

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

补充习题

1

计算

$$\mathbf{y}=\operatorname{DFT}\{\mathrm{DFT}\{\mathbf{x}\}\}$$

利用定义可得

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

注意到

$$\sum_{k=0}^{N-1} e^{-j \frac{2 \pi}{N}(i+n) k}=\left\{\begin{array}{ll} N & \text { for }(i+n)=0, N, 2 N, 3 N, \ldots \\ 0 & \text { otherwise } \end{array}=N \delta[(i+n) \bmod N]\right.$$

那么

$$\begin{aligned} y[n] &=\sum_{i=0}^{N-1} x[i] N \delta[(i+n) \bmod N] \\ &=\left\{\begin{array}{ll} N x[0] & \text { for } n=0 \\ N x[N-n] & \text { otherwise } \end{array}\right. \end{aligned}$$

2

考虑$\mathbf x\in \mathbb C^N$，$N$为偶数，DFT为$\mathbf X$，定义

$$Y[k]=X[2 k], k=0, \ldots, N / 2-1$$

计算$\mathbf y$

利用定义可得：

$$\begin{aligned} y[n] &=\frac{1}{N / 2} \sum_{l=0}^{\frac{N}{2}-1} Y[l] e^{j \frac{2 \pi}{N / 2} n l} \\ &=\frac{2}{N} \sum_{l=0}^{\frac{N}{2}-1} X[2 l] e^{j \frac{2 \pi}{N} 2 n l} \end{aligned}$$

这里要使用如下技巧：

$$1+(-1)^{n}=\left\{\begin{array}{ll}2 & \text { if } n \text { is even } \\ 0 & \text { if } n \text { is odd }\end{array}\right.$$

那么

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