Shannon–Hartley theorem

有噪信道编码定理只适用于离散的数字信道，若要将其应用于真实的物理信道还需要费一番功夫。当然其结果就是著名的香农极限。

对于某个物理信道，若：

  1. 其带宽为 $W$.
  2. 其噪声为功率谱密度为 $N_0$ 的高斯白噪声。
  3. 信号的平均功率为 $P$.

则该信道的容量为 $C = W\log(1+\frac{P}{N_0W})$ 比特每秒。

Convert to AWGN

物理信道与之前的数学模型中的信道主要有两点差别，1，信源为连续时间上的函数；2，信源为模拟信号，即取值连续。这里我们先消除第1点差别，将其转换为一个离散时间，模拟信号的信道（AWGN），即进行采样。

根据采样定理，如果不存在噪声干扰，我们以 $2W$ 的频率对信源 $x(t)$ 进行采样，得到 $\left\{x_k\right\}$ ，信宿只需后者便能将前者完整地还原。现在我们希望在每个 $x_k$ 上叠加一个高斯噪声 $n_k \sim \mathcal{N}(0, \delta)$ 来模拟之前的高斯白噪声 $n(t)$ 所带来的干扰，在信源功率保持不变（$\int_0^T x^2(t) dt = \sum_{i=0}^{2WT} x_k^2$）的情况下，若要使前后的噪声等效，则噪声的功率也需要保持不变，即：
$$
\delta^2 = \frac{N_0 \cdot W \cdot T}{2WT} = \frac{N_0}{2}\tag{1}\label{eq1}
$$.
上述分析符合直觉，且其定量分析结果也正确，但要更严格地证明两者的等效性，不如换个方式思考。这次我们通过“离散-模拟信道”传递的是频域的采样而不再是时域的采样。由于时域与频域的对称性，有采样定理的如下推论：对于一个时长不超过 $T$ 的信号，可以在其频谱上每隔 $1/T$（或更短）的频率进行一次采样，便能完整地还原信号，对于带宽为 $W$ 的信号，其频谱区域为 $[-W, W]$，因此总采样次数为 $2WT$，与前面保持一致。

换句话说，通过“离散-模拟”信道传递 $y(t) = x(t) + n(t)$ 的傅里叶级数 $\left\{x_k + n_k\right\}, k \in [0, WT)$, 其中 $n_k = \frac1T \int_0^T n(t) e^{-i\frac{2\pi kt}{T}} dt$ 为信道噪声 , $x_k$ 同理，实部加虚部共 $2WT$ 个模拟量，如果在 $n(t)$ 为高斯白噪声的情况下，$n_k$ 服从同一个高斯分布，则说明我们可以通过 AWGN 来模拟物理信道，定量分析的结果与 $\eqref{eq1}$ 相同。

令 $n(\tau) \sim \mathcal{N}(0, \delta’)$, 考虑其某个傅里叶系数
$$
Re(n_k) = \frac1T \int_0^T n(t) cos(2\pi kt/T) dt = \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{j = 0}^N n(jT/N) cos(2\pi kj/N)
$$
即 inverse DTFT 是 DFT 的极限形式，若后者得到的系数服从高斯分布，则前者亦然。令
$$
z_j^k \equiv n(jT/N) cos(2\pi kj/N) \sim \mathcal{N}(0, \delta’cos(2\pi kj/N))
$$
则只需证明 $\sum_j z_j^k$ 服从某个与 $k$ 无关的高斯分布即可。为了标记方便，将 $\mathcal{N}(0, \delta)$ 的概率分布函数记作 $G_\delta$, 并将 $cos(2\pi kj/N)$ 记作 $c_{j, k}$ . 由于两个随机变量之和的分布为两个分布函数的卷积，于是
$$
P(\sum_j z_j^k = z) \propto (G_{\delta’c_{0, k}} \otimes \cdots \otimes G_{\delta’c_{N, k}})(z)
$$

又由于傅里叶变换满足性质 $\mathcal{F}(f \otimes g) = \mathcal{F}(f) \cdot \mathcal{F}(g)$. 且方差为 $\delta$ 高斯函数的傅里叶变换为方差 $1/\delta$ 的高斯函数「1」。 于是
$$
\begin{align*}
G_{\delta’c_{0, k}} \otimes \cdots \otimes G_{\delta’c_{N, k}} &= \mathcal{F}^{-1}(\prod\limits_j \mathcal{F}(G_{\delta’c_{j, k}})) \\
&= \mathcal{F}^{-1}(\prod\limits_j G_{1/(\delta’c_{j, k})}) \propto \mathcal{F}^{-1}(G_{1/\sqrt{\sum_j (\delta’c_{j, k})^2}}) \\
&= G_{\sqrt{\delta’^2 \sum_j cos^2(2\pi kj/N)}} = G_{\sqrt{\delta’^2 N/2}}
\end{align*}
$$

即 $n(t)$ 的傅里叶级数确实服从同一个高斯分布「2」。因此，信道的等效成立。总结起来就是：

对于上边定义的物理信道，每使用时间 $T$，等效于 $2WT$ 次使用某 AWGN，其信源的平均能量为 $P/2W$，高斯噪声服从 $\mathcal{N}(0, N_0/2)$.

Channel Capacity of AWGN

接下来我们希望通过计算 AWGN 的信道容量来给出香农极限。那么每次使用 AWGN 到底能够传递多少比特的信息呢？

Differential Entropy

为了回答上面的问题，我们首先需要将信息熵和互信息量的定义扩展到连续的模拟量上。直观的做法就是将原来的求和改为积分，也就是说，对于服从概率分布 $P(x)$ 的连续随机变量 $X$, 定义它的信息熵为 $H(X) = - \int P(x) \log P(x)$. 这个积分可能是发散的，但当 $X$ 的方差（也就是信源的平均能量）不超过 $P$ 时，$H(X)$ 的最大值为 $\frac12 \log{(2\pi e P)}$, 当且仅当 $X \sim \mathcal{N}(\mu, \sqrt{P})$ 时取到。

令 $g = G_{\sigma}$, $f$ 为任意方差不超过 $\sigma^2$ 的概率分布函数，由于平移并不改变信息熵的大小，不妨设两个分布的均值均为 0，计算两者的 K-L divergence, 有：
$$
\begin{align*}
0 \leq D_{KL}(f || g) &= \int_{-\infty}^\infty f(x) \log \left( \frac{f(x)}{g(x)} \right) dx = -H(f) - \int_{-\infty}^\infty f(x)\log(g(x)) dx \\
&= -H(f) - \int_{-\infty}^\infty f(x)\log\left( \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}}\right) dx \\
&= -H(f) - \int_{-\infty}^\infty f(x) \log\frac{1}{\sqrt{2\pi\sigma^2}} dx - \log(e)\int_{-\infty}^\infty f(x)\left( -\frac{x^2}{2\sigma^2}\right) dx \\
&\leq -H(f) + \tfrac{1}{2}\log(2\pi\sigma^2) + \log(e)\frac{\sigma^2}{2\sigma^2} \\
&= -H(f) +\tfrac{1}{2}\left(\log(2\pi\sigma^2) + \log(e)\right) \\
&= -H(f) +\tfrac{1}{2}\log(2\pi e \sigma^2) = -H(f)+H(g)
\end{align*}
$$
上式中等号当且仅当 $f = g$ 时成立。

像之前一样定义互信息量 $I(X; Y) = H(Y) - H(Y|X)$, 由于 $Y = X + N$, 于是
$$
I(X; Y) = H(Y) - H(X + N|X) = H(Y) - H(N) = H(Y) - \frac12 \log(\pi eN_0)
$$
当 $X$ 的平均能量不超过 $P/2W$ 时，$Y$ 的平均能量不超过 $P/2W + N_0/2$, 于是信道容量
$$
C = \frac12 \log(\pi e (P/W + N_0)) - \frac12 \log(\pi e (N_0)) = \frac12 \log(1 + \frac{P}{N_0W})
$$

算上单位时间内的 AWGN 使用次数便得到了香农极限。

Sphere Packing

分析到此，我们是将取值连续的随机变量看成是无穷多级的离散随机变量处理，已经足够自圆其说。然而我们可以通过如下方式更加直观地考察其正确性：

  1. 求信道容量就是求使用信道 $N \to \infty$ 次，接收端根据 $N$ 维向量最多能够准确地还原多少个不同的码字，当这个数量为 $M$ 时，$C = \log_2(M)$.
  2. 对于上述 AWGN, 其码字空间为 $\mathbb{R}^N$, 在某个码字 $\mathbf{x}$ 上叠加一个 $N$ 维的高斯噪声，得到输出向量 $\mathbf{y}$, 输出的分布为以 $\mathbf{x}$ 为中心的N维高斯分布，其置信区间为一个半径为 $\sqrt{N\cdot N_0/2}$ 的球。根据上篇中提到过的 AEP, $N$ 足够大时，$\mathbf{y}$ 几乎必然落入球中。
  3. 我们希望找到尽可能多的码字，使得对应的输出的置信区间不重叠，如此一来，我们只需要寻找离 $\mathbf{y}$ 最近的码字便能正确地将其译码。
  4. 由于输出的能量不超过 $N(\frac{P}{2W} + \frac{N_0}{2})$, 因此它将几乎必然落入一个半径 $\sqrt{\frac12 N(P/W+N_0)}$ 的球中。
  5. $\mathbb{R}^N$ 中半径为 $r$ 的球的体积 $\propto r^N$, 因此4中的大球至多包含 $\sqrt{1+\frac{P}{N_0W}}^N$ 个两两不交的代表置信区间的小球。
  6. $C \leq \frac12 \log(1 + \frac{P}{N_0W})$.

至于如何取得等号，需要通过类似有噪信道编码定理的 JT 性质来加以证明「3」，此处略去。这样一来便得到了与之前完全一致的结论，happy ending.

Reference