EE261 Lecture 17 and Lecture 18

课程主页：https://see.stanford.edu/Course/EE261

这次回顾第十七讲，十八讲，这两讲介绍了采样。

周期分布和傅里叶级数

我们称一个分部周期为$p$，如果

$$\tau_{p} S=S$$

所以

$$\tau_{p} \text{III}_{p}=\sum_{k=-\infty}^{\infty} \tau_{p} \delta_{k p}=\sum_{k=-\infty}^{\infty} \delta_{k p+p}=\sum_{k=-\infty}^{\infty} \delta_{p(k+1)}=\sum_{k=-\infty}^{\infty} \delta_{k p}=\text{III}_{p}$$

注意到周期化函数使用了$\text{III}$的卷积：

$$\Phi(x)=\left(\varphi * \text{III}_{p}\right)(x)$$

更一般的，假设$f$的周期为$p$，那么

$$(f * g)(x+p)=\int_{-\infty}^{\infty} f(x+p-y) g(y) d y=\int_{-\infty}^{\infty} f(x-y) g(y) d y=(f * g)(x)$$

$\text{III}$的傅里叶系数

由之前讨论，我们得到

$$\mathcal{F} \text{III} =\sum_{k=-\infty}^{\infty} e^{2 \pi i k t}$$

注意到$\mathcal{F} \text{III}=\text{III}$，所以

$$\text{III} =\sum_{k=-\infty}^{\infty} e^{2 \pi i k t}$$

不难看出右边定义了一个分布。

采样和插值

现在讨论采样问题，假设已知$f\left(t_{0}\right), f\left(t_{1}\right), f\left(t_{2}\right), \ldots$，我们希望计算出其他点上的值，为了后续讨论，引入如下概念：

带宽有限：

信号$f(t)$带宽有限，如果存在$p$，使得$\mathcal F f(s)=0, |s|\ge p/2$，最小的$p$被称为$f(t)$的带宽。

对带宽有限的信号采样和插值

后续讨论之前，给出如下结论：

• 一个信号不能同时是时间有限和带宽有限

证明：假设$f$带宽有限，即$\mathcal F f(s)=0, |s|\ge p/2$，那么

$$\mathcal{F} f=\Pi_{p} \cdot \mathcal{F} f$$

取傅里叶逆变换可得

$$f(t)=p \operatorname{sinc} p t * f(t)$$

显然$f(t)$不是时间有限的。

采样定理

如果$f(t)$带宽有限，$\mathcal F f(s)=0, |s|\ge p/2$，我们周期化并截断得到恒等式

$$\mathcal{F} f=\Pi_{p}\left(\mathcal{F} f * \text{III}_{p}\right)$$

对两边取傅里叶变换得到

$$\begin{aligned} f(t) &=\mathcal{F}^{-1} \mathcal{F} f(t) \\ &=\mathcal{F}^{-1}\left(\Pi_{p}\left(\mathcal{F} f * \text{III}_{p}\right)\right)(t) \\ &=\mathcal{F}^{-1} \Pi_{p}(t) * \mathcal{F}^{-1}\left(\mathcal{F} f * \text{III}_{p}\right)(t) \\ &=p \operatorname{sinc} p t *\left(f(t) \cdot \frac{1}{p} \text{III}_{1 / p}(t)\right) \\ &=\operatorname{sinc} p t * \sum_{k=-\infty}^{\infty} f\left(\frac{k}{p}\right) \delta\left(t-\frac{k}{p}\right) \\ &=\sum_{k=-\infty}^{\infty} f\left(\frac{k}{p}\right) \operatorname{sinc} p t * \delta\left(t-\frac{k}{p}\right)\\ &=\sum_{k=-\infty}^{\infty} f\left(\frac{k}{p}\right) \operatorname{sinc} p\left(t-\frac{k}{p}\right) \end{aligned}$$

将结论总结如下：

• 如果$f(t)$带宽有限：$\mathcal F f(s)=0, |s|\ge p/2$，那么 $$f(t)=\sum_{k=-\infty}^{\infty} f\left(\frac{k}{p}\right) \operatorname{sinc} p\left(t-\frac{k}{p}\right)$$

如果记

$$t_k=\frac k p$$

那么上式也可以表示为

$$f(t)=\sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc} p\left(t-t_{k}\right)$$

一般的插值

考虑定义在$L^2(\mathbb R)$上的内积

$$(f, g)=\int_{-\infty}^{\infty} f(t) \overline{g(t)} d t$$

Parseval等式告诉我们

$$\int_{-\infty}^{\infty} f(t) \overline{g(t)} d t=\int_{-\infty}^{\infty} \mathcal{F} f(s) \overline{\mathcal{F} g(s)} d s$$

所以

$$\begin{aligned} \int_{-\infty}^{\infty} \operatorname{sinc}(t-n) \operatorname{sinc}(t-m) d t &=\int_{-\infty}^{\infty}\left(e^{-2 \pi i s n} \Pi(s)\right) \overline{\left(e^{-2 \pi i s m} \Pi(s)\right)} d s \\ &=\int_{-\infty}^{\infty} e^{2 \pi i s(m-n)} \Pi(s) \Pi(s) d s\\ &=\int_{-1 / 2}^{1 / 2} e^{2 \pi i s(m-n)} d s \end{aligned}$$

即$\operatorname{sinc}(t-n)$构成正交基。现在使用内积的方式重写采样定理

$$\begin{aligned} (g(t), \operatorname{sinc}(t-n)) &=\int_{-\infty}^{\infty} g(t) \operatorname{sinc}(t-n) d t \\ &=\int_{-\infty}^{\infty} \mathcal{F} g(s) \mathcal{F}(\operatorname{sinc}(t-n)) d s \quad(\text { by Parseval }) \\ &=\int_{-\infty}^{\infty} \mathcal{F} g(s) \overline{\left(e^{-2 \pi i s n} \Pi(s)\right)} d s \\ &=\int_{-1 / 2}^{1 / 2} \mathcal{F} g(s) e^{2 \pi i n s} d s \\ &=\int_{-\infty}^{\infty} \mathcal{F} g(s) e^{2 \pi i n s} d s &有限带宽\\ &=g(n) \end{aligned}$$

所以

$$g(t)=\sum_{n=-\infty}^{\infty} g(n) \operatorname{sinc}(t-n)=\sum_{n=-\infty}^{\infty}(g(t), \operatorname{sinc}(t-n)) \operatorname{sinc}(t-n)$$

一般情形也可以由类似上式进行推广。

带宽有限信号的有限采样

考虑实傅里叶级数

$$f(t)=\sum_{k=-N}^{N} c_{k} e^{2 \pi i k t / q}, \quad c_{-k}=\overline{c_{k}}$$

取傅里叶变换得到

$$\mathcal{F} f(s)=\sum_{k=-N}^{N} c_{k} \delta\left(s-\frac{k}{q}\right)$$

另一方面，利用采样定理，我们有

$$f(t)=\sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc} p\left(t-t_{k}\right)$$

假设

$$t_k=\frac{kq}{M}$$

现在选择$p$，使得包含整个函数，考虑下图

利用上图的取法得到

$$\frac{p}{2}=\frac{1}{2}\left(\frac{N}{q}+\frac{N+1}{q}\right)=\frac{(2 N+1)}{2 q}, \quad \text { or } \quad p=\frac{2 N+1}{q}$$

令

$$M=2N+1 = pq$$

那么

$$t_{k}=\frac{k}{p}=\frac{k q}{M}$$

注意到

$$t_{k+k^{\prime} M}=t_{k}+k^{\prime} q$$

而$f(t)$周期为$q$，所以

$$f\left(t_{k+k^{\prime} M}\right)=f\left(t_{k}+k^{\prime} q\right)=f\left(t_{k}\right)$$

带入采样定理得到

$$\begin{aligned} \sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc} p\left(t-t_{k}\right) &=f\left(t_{0}\right) \sum_{m=-\infty}^{\infty} \operatorname{sinc}(p t-m M)+f\left(t_{1}\right) \sum_{m=-\infty}^{\infty} \operatorname{sinc}(p t-(1+m M))+ \\ &f\left(t_{2}\right) \sum_{m=-\infty}^{\infty} \operatorname{sinc}(p t-(2+m M))+\cdots+f\left(t_{M-1}\right) \sum_{m=-\infty}^{\infty} \operatorname{sinc}(p t-(M-1+m M)) \end{aligned}$$

第$k$项的和为

$$\sum_{m=-\infty}^{\infty} \operatorname{sinc}(p t-k-m M)=\operatorname{sinc}(p t-k) * \text{III}_{M / p}(t)=\frac{\operatorname{sinc}(p t-k)}{\operatorname{sinc}\left(\frac{1}{M}(p t-k)\right)} =\frac{\operatorname{sinc}(p t-k)}{\operatorname{sinc}\left(\frac{1}{pq}(p t-k)\right)} =\frac{\operatorname{sinc}\left(p\left(t-t_{k}\right)\right)}{\operatorname{sinc}\left(\frac{1}{q}\left(t-t_{k}\right)\right)}$$

（见引理）

所以得到另一个公式

$$f(t)=\sum_{k=0}^{2 N} f\left(t_{k}\right) \frac{\operatorname{sinc}\left(p\left(t-t_{k}\right)\right)}{\operatorname{sinc}\left(\frac{1}{q}\left(t-t_{k}\right)\right)}$$

其中

$$p=\frac{2 N+1}{q}, t_{k}=\frac{k}{p}=\frac{k q}{2 N+1}$$

例子

考虑

$$f(t)=\cos 2\pi t$$

此处$N=1, q=1, p=3$，所以

$$t_{0}=0, t_{1}=1 / 3, t_{2}=2 / 3$$

利用上式公式可得

$$\cos 2 \pi t=\frac{\operatorname{sinc} 3 t}{\operatorname{sinc} t}+\cos \left(\frac{2 \pi}{3}\right) \frac{\operatorname{sinc}\left(3\left(t-\frac{1}{3}\right)\right)}{\operatorname{sinc}\left(t-\frac{1}{3}\right)}+\cos \left(\frac{4 \pi}{3}\right) \frac{\sin c\left(3\left(t-\frac{2}{3}\right)\right)}{\operatorname{sinc}\left(t-\frac{2}{3}\right)}$$

引理

假设$p, q>0$，$N$为小于$pq /2$的最大整数。那么

$$\sum_{k=-\infty}^{\infty} \operatorname{sinc}(p t-k p q)=\operatorname{sinc}(p t) * \text{III}_{q}(t)=\frac{1}{p q} \frac{\sin ((2 N+1) \pi t / q)}{\sin (\pi t / q)}$$

这里证明上述结论：

$$\operatorname{sinc}(p t) * \text{III}_{q}(t)=\frac{1}{p q} \frac{\sin ((2 N+1) \pi t / q)}{\sin (\pi t / q)}$$

对左边取傅里叶变换可得（回顾$N$的定义）

$$\mathcal{F}\left(\operatorname{sinc}(p t) * \text{III}_{q}(t)\right) =\mathcal{F}(\operatorname{sinc}(p t)) \cdot \mathcal{F}\text{III}_{q}(t)=\frac{1}{p} \Pi_{p}(s) \cdot \frac{1}{q}\text{III}_{1 / q}(s)=\frac{1}{p q} \sum_{n=-N}^{N} \delta\left(s-\frac{n}{q}\right)$$

现在对右边取傅里叶逆变换可得

$$\mathcal{F}^{-1}\left(\frac{1}{p q} \sum_{n=-N}^{N} \delta\left(s-\frac{n}{q}\right)\right)=\frac{1}{p q} \sum_{n=-N}^{N} e^{2 \pi i n t / q}=\frac{1}{p q} \frac{\sin (\pi(2 N+1) t / q) )}{\sin (\pi t / q)}$$

采样的问题

假设原函数的带宽为$p$，如果我们用小于$p$的$q$进行采样，那么显然有

$$\mathcal{F} f\neq \Pi_{q}\left(\mathcal{F} f * \text{III}_{q}\right)$$

但是右边依然可以化成

$$\sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc}q\left(t-t_{k}\right)$$

其中

$$t_k =\frac k q$$

令$t=t_k$，我们得到

$$\left(\sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc}q\left(t-t_{k}\right)\right) \big |_{t=t_k} = f(t_k)$$

所以求出的函数在采样点上依然满足条件，但是显然有

$$f \neq \sum_{k=-\infty}^{\infty} f\left(t_{k}\right) \operatorname{sinc}q\left(t-t_{k}\right)$$

这就会产生无法区分的现象。