信息论 | 3 信道容量

通信的流程: \[ \xymatrix@=5em{ *[F-,]{\hspace{3em}\mathclap{\textsf{Message}}\hspace{3em}\strut} \ar[r]^-{\textsf{source}}_-{\textsf{encoding}} & *[F-,]{\hspace{3em}\mathclap{\textsf{Source code}}\hspace{3em}\strut} \ar[r]^-{\textsf{channel}}_-{\textsf{encoding}} & *[F-,]{\hspace{3em}\mathclap{\textsf{Channel code}}\hspace{3em}\strut} \ar@{~>}[d]^-{\textsf{noisy channel}} \\ *[F-,]{\hspace{3em}\mathclap{\textsf{Message}'}\hspace{3em}\strut} & *[F-,]{\hspace{3em}\mathclap{\textsf{Source code}'}\hspace{3em}\strut} \ar[l]_-{\textsf{source}}^-{\textsf{decoding}} & *[F-,]{\hspace{3em}\mathclap{\textsf{Channel code}'}\hspace{3em}\strut} \ar[l]_-{\textsf{channel}}^-{\textsf{decoding}} } \] Shannon 的一大贡献是建立了有噪信道 (noisy channel) 的数学模型. 他假设有噪信道的输入和输出分别为随机变量 \(X,Y\), 有噪信道的模型为条件分布 \(P(Y\mid X)\).

6 Channel capacity

6.1 Shannon's theorem

给定一个有噪信道 \(P(Y\mid X)\), 每次传输 \(X\), 得到 \(Y\). 在 \(Y\) 中究竟能有多少关于 \(X\) 的信息? 一个自然的想法是互信息 \(I(X;Y)\) (即 \(Y\) 中包含了 \(X\) 中的多少信息, 或者 \(X\) 中包含了多少关于 \(Y\) 的信息). 信道容量 (channel capacity) 定义为互信息的最大值: \[ \Align{ C := \max_{P_X\in\mathcal{P}} I(X;Y). } \]

• 集合 \(\mathcal{P}\) 表示 \(\R\) 上所有离散 / 连续概率分布的集合.
• 为什么不直接研究 \(H(Y)\)? 因为 \(H(Y)\) 包含了噪声的信息, 可能有 \(H(Y)>H(X)\).

直观地讲, 输入 / 输出分布 \(X,Y\) 分别可以看作概率向量 \(P=(p_1,\dots,p_n)\T\) 和 \(Q=(q_1,\dots,q_m)\T\), 信道就是条件概率 (转移矩阵) \[ p(y\mid x) = \pmqty{ p{(y_1\mid x_1)} & \cdots & p{(y_1\mid x_n)} \\ \vdots & & \vdots \\ p{(y_m\mid x_1)} & \cdots & p{(y_m\mid x_n)} }. \] 给定一个输入分布 \(P\) 之后, 输出分布 \(Q\) 唯一确定为 \(p(y\mid x)P\), 此时就有一个互信息值 \(I(P;Q)\). 信道容量就是取遍所有 \(P\) 后, 互信息的最大值.

Example 设随机变量 \(X,Y\) 的取值分别为 \(x_1,\dots,x_n\) 和 \(y_1,\dots,y_n\).

考虑两个例子:

1. 对于无噪声的信道, 即 \(P(y_j\mid x_i)=\delta_{ij}\), 有 \(H(Y\mid X)=0\), 进而 \[ C = \sup_{P_X} I(X;Y) = \sup_{P_X} H(Y). \] 当 \(Y\) 为均匀分布时 (比如取 \(X\) 为均匀分布), \(H(Y)\) 取到最大值 \(\log{n}\). 故信道容量 \[ C = \log{n}. \]

2. 假设 \(X\) 的每个取值 \(x_i\), 它可能被扰动到任何一个 \(y_i\), 且满足 \[ \Align{ P(Y=y_i \mid X=x_i) &= 1-\varepsilon, \\ P(Y=y_j \mid X=x_i) &= \frac{\varepsilon}{n-1}, & j\neq i. } \] (传输错误率为 \(\varepsilon\)) 则条件熵 \[ \Align{ H(Y\mid X) &= \sum_{i} P(X=x_i) \cdot \underbrace{H(Y\mid X=x_i)}_{\textsf{constant}} \\ &= H(Y\mid X=x_1), } \] 因此 \[ \Align{ C &= \max_{P_X} [ H(Y) - H(Y\mid X) ] \\ &= \max_{P_X} H(Y) - H(Y\mid X=x_1), } \] 当 \(Y\) 为均匀分布时, \(H(Y)\) 取到最大值 \(\log{n}\). 故信道容量 \[ \Align{ C = \log{n} + (1-\varepsilon) \log(1-\varepsilon) + \varepsilon \log\frac{\varepsilon}{n-1} } \]

信道容量只是刻画了 \(Y\) 中含有的 \(X\) 的信息量, 但是并不能反映哪些东西是 \(X\) 的, 哪些东西属于噪声. 如果要还原 \(X\) 的信息, 还得依赖于纠错码, 即加入冗余. 冗余越少, 效率越高, 那么效率的上限在哪?

• 给定有噪信道. 给定效率值. 能否设计出 (效率不低于给定值的一系列) 纠错码, 使得其错误率可以任意小?

Theorem (Shannon) 设有噪信道的信道容量为 \(C\), 纠错码的比特率为 \(R\).

• 如果 \(R<C\), 则存在比特率为 \(R\) 的纠错码序列, 其错误率趋于 \(0\).
• 若比特率为 \(R\) 的纠错码序列错误率趋于 \(0\), 则 \(R\leq C\).

先做一些准备工作.

6.2 Typical sequences

回顾 Chebyshev 弱大数定律: 若随机变量列 \(\{X_i\}_{i\geq1}\) 独立同分布 \(X\), 且期望和方差存在, 则 \[ \frac1n\sum_{i=1}^n X_i \overset{P}{\to} \operatorname{E}(X), \qquad n\to\infty. \]

其中依概率收敛的含义是, 对任意 \(\varepsilon>0\), 有 \[ P\left( \Biggl| \frac1n\sum_{i=1}^n X_i - \operatorname{E}(X) \Biggr| > \varepsilon \right) \to 0, \qquad n\to\infty. \] 大数定律的推论是对于任意 (性质比较好的) 函数 \(g:\R\to\R\), 有 \(\frac1n\sum g(X_i)\overset{P}\to\operatorname{E}(g(X))\).

特别地, 考虑取值为有限字母表 \(\mathcal{X}\) 的随机变量 \(X\), 并取 \(g(x)=\log\frac1{p(x)}\), 其中 \(p(x)\) 是 \(X\) 的概率密度. 则 \[ P\Biggl( \Biggl| \frac1n\sum_{i=1}^n \log\frac{1}{p(X_i)} - \underbrace{\operatorname{E}\log\frac{1}{p(X)}}_{H(X)} \Biggr| > \varepsilon \Biggr) \to 0, \qquad n\to\infty. \] 绝对值中的第二项就是 \(X\) 的熵, 所以上式的含义就是随机变量列 \(\log\frac1{p(X_i)}\) 的均值收敛到 \(H(X)\). 这称为渐进均分性 (asymptotic equipartition property, AEP).

上式化为 \[ P\biggl( 2^{-n(H(X)+\varepsilon)} \leq p(X_1,\dots,X_n) \leq 2^{-n(H(X)-\varepsilon)} \biggr) \to 1, \qquad n\to\infty. \] 其中 \(p(x_1,\dots,x_n)=p(x_1)\cdots p(x_n)\) 是 \(X_1,\dots,X_n\) 的联合分布密度. 考虑 \(\mathcal{X}^n\) 的子集 \[ A^{(n)}_\varepsilon := \Bigl\{ (x_1,\dots,x_n)\in\mathcal{X}^n \Bigm| 2^{-n(H(X)+\varepsilon)} \leq p(x_1,\dots,x_n) \leq 2^{-n(H(X)-\varepsilon)} \Bigr\}, \] 则有 \(P(A^{(n)}_\varepsilon)\to1\) (当 \(n\to\infty\)). 也就是说, 当 \(n\) 增大时, 随机变量列 \((X_1,\dots,X_n)\) 的取值 (即长度为 \(n\) 的字母序列) 大概率出现在 \(A^{(n)}_\varepsilon\) 中, 不太可能出现在补集中. 集合 \(A^{(n)}_\varepsilon\) 称为典型集 (typical set), 其中的序列称为典型序列 (typical sequence).

典型集中任意序列的概率都约为 \(2^{-nH(X)}\), 而 \(P(A^{(n)}_\varepsilon)\approx1\), 所以可以猜测 \(A^{(n)}_\varepsilon\) 的元素个数为 \(2^{nH(X)}\).

一方面有 \[ \Align{ 1 &= \sum_{(x_i)\in\mathcal{X}^n} p(x_1,\dots,x_n) \\ &\geq \sum_{(x_i)\in A^{(n)}_\varepsilon} p(x_1,\dots,x_n) \\ &\geq |A^{(n)}_\varepsilon| \cdot 2^{-n(H(X)+\varepsilon)}, } \] 于是 \(|A^{(n)}_\varepsilon|\leq2^{n(H(X)+\varepsilon)}\).

另一方面, 因为 \(P(A^{(n)}_\varepsilon)\to1\) (\(n\to\infty\)), 根据极限的定义, 对于给定的 \(\varepsilon>0\) (该 \(\varepsilon\) 就是上面给出的, 这里 “一 \(\varepsilon\) 二用”), 当 \(n\) 充分大时就有 \[ P( (X_1,\dots,X_n) \in A^{(n)}_\varepsilon ) \geq 1-\varepsilon. \] 又因为 \[ P((X_1,\dots,X_n) \in A^{(n)}_\varepsilon) \leq 2^{-n(H(X)-\varepsilon)} \cdot |A^{(n)}_\varepsilon|, \] 所以 \(|A^{(n)}_\varepsilon|\geq(1-\varepsilon)2^{n(H(X)-\varepsilon)}\) 对于充分大的 \(n\).

因此 \(|A^{(n)}_\varepsilon|\approx 2^{nH(X)}\). 考虑它在 \(\mathcal{X}^n\) 中的占比: \[ \Align{ \frac{|A^{(n)}_\varepsilon|}{|\mathcal{X}^n|} \leq \frac{n(H(X)+\varepsilon)}{2^{n\log|\mathcal{X}|}} = 2^{-n(\log|\mathcal{X}| - H(X) - \varepsilon)}, } \] 注意除了均匀分布之外, 都有 \(H(X)<\log|\mathcal{X}|\), 此时上式就收敛到零 (\(n\to\infty\)), 即 \(A^{(n)}_\varepsilon\) 的占比可以任意小.

• 尽管典型集 \(A^{(n)}_\varepsilon\) 只占到 \(\mathcal{X}^n\) 的很小很小一部分, 但是 iid 随机采样 \((x_1,\dots,x_n)\) 却几乎必定出现在典型集中!
• 当 \(X\) 是 \(\mathcal{X}\) 上的均匀分布时, \(p(X)\equiv1/|\mathcal{X}|\), 有 \(A^{(n)}_\varepsilon=\mathcal{X}^n\).

Example 考虑 \(\mathcal{X}=\{0,1\}\) 上的 Bernoulli 分布 \(P(X=1)=p\), \(P(X=0)=1-p\), 其中 \(p\neq\frac12\), 则 \(X\) 的熵 \(H(X)=-p\log{p}-(1-p)\log(1-p)\).

设序列 \((x_1,\dots,x_n)\in\mathcal{X}^n\) 中有 \(m\) 个 \(1\) 和 \((n-m)\) 个 \(0\), 则它的概率为 \[ p(x_1,\dots,x_n) = p^m(1-p)^{n-m}, \] 该序列属于 \(A^{(n)}_\varepsilon\) 当且仅当 \(\log{p(x_1,\dots,x_n)}\approx-n(H(X)\pm\varepsilon)\), 即 \[ m\log{p} + (n-m)\log(1-p) \approx np\log{p} + n(1-p)\log(1-p) \pm n\varepsilon, \] 对比得到 \(m\approx np\).

例如当 \(n=10\) 及 \(p=0.7\) 时, \(A^{(n)}_\varepsilon\) (\(\varepsilon\) 充分小) 中包含了所有恰好有 \(7\) 个 \(1\) 的序列. 值得注意的是, 概率最大的那个序列 \((1,1,\dots,1)\) 并不在 \(A^{(n)}_\varepsilon\) 中.

6.3 Jointly typical sequences

设有限字母表 \(\mathcal{X}\times\mathcal{Y}\) 上的随机向量序列 \(\{(X_i,Y_i)\}_{i\geq1}\) 独立同分布 \(p(x,y)\). 它们的联合典型集定义为 \[ \Align{ A^{(n)}_\varepsilon := \Bigl\{ (x_1,y_1,\dots,x_n,y_n)\in(\mathcal{X}\times\mathcal{Y})^n \Bigm|{} & p(x_1,y_1,\dots,x_n,y_n) \approx 2^{-n(H(X,Y)\pm\varepsilon)} \\ & p(x_1,\dots,x_n) \approx 2^{-n(H(X)\pm\varepsilon)} \\ & p(y_1,\dots,y_n) \approx 2^{-n(H(Y)\pm\varepsilon)} \Bigr\}, } \] 其中的序列称为联合典型序列. 我们同样有结论 (联合 AEP):

1. \(P(A^{(n)}_\varepsilon)\to1\) (当 \(n\to\infty\)).
2. \(|A^{(n)}_\varepsilon|\approx2^{nH(X,Y)}\).
3. 如果 \(p(x,y)=p_X(x)p_Y(y)\) 独立, 且 \(X=(X_1,\dots,X_n)\) 和 \(Y=(Y_1,\dots,Y_n)\) 独立同分布 \(p_X,p_Y\), 则 \(P((X,Y)\in A^{(n)}_\varepsilon)\approx2^{-nI(X;Y)}\) (当 \(n\) 充分大).

直观上看, 一共有 \(2^{nH(X)}\) 个 \(X\)-典型序列, 有 \(2^{nH(Y)}\) 个 \(Y\)-典型序列. 然而在这 \(2^{n[H(X)+H(Y)]}\) 个序列对中, 只有 \(2^{nH(X,Y)}\) 个联合典型序列. 因此, 任取一个序列对 \((X,Y)\) (根据 AEP, \(X,Y\) 大概率都是典型序列), 它是联合典型序列的概率为 \[ \frac{2^{nH(X,Y)}}{2^{n[H(X)+H(Y)]}} = 2^{-nI(X;Y)}. \] (当 \(n\) 充分大且 \(p(x,y)=p_X(x)p_Y(y)\).)

事先给定序列 \(Y\), 对于任意给定的序列 \(X\), 它与 \(Y\) 构成联合典型序列的概率为 \(2^{-nI(X;Y)}\). 因此, 如果所有可能的序列 \(X\) 的数量少于 \(2^{nI(X;Y)}\), 则大概率只有一个 \(X\) 能够与 \(Y\) 构成联合典型序列, 不会搞混.

6.4 Proof of Shannon's theorem

6.4.1 Achievability

假设 \(R<C\), 我们需要证明存在一系列比特率不低于 \(R\) 的纠错码, 使得错误率趋于零.

假设信息集为 \(\{m_1,\dots,m_{2^{nR}}\}\), 且每条信息概率相等 (\(2^{nR}\) 理解为向上取整). 通讯流程为:

1. (想法一: 随机编码) 随机生成一个 \((2^{nR},n)\) 编码 (编码数量, 编码长度), 将其写作一个矩阵 \[ \mathcal{C} = \pmqty{ x_1\!\pqty{m_1} & \cdots & x_n\!\pqty{m_1} \\ \vdots & & \vdots \\ x_1\!\pqty{m_{2^{nR}}} & \cdots & x_n\!\pqty{m_{2^{nR}}} \\ }, \] 其中 \(x_i(m_j)\) 独立同分布 \(p(x)\) (某个给定的分布). 可知该编码的比特率为 \(R\).

2. 发送者等概率随机挑选一条信息 \(m_i\).

3. 信息编码为 \((x_1,\dots,x_n)=(x_1(m_i),\dots,x_n(m_i))\).

4. 信息传输 \(P((y_1,\dots,y_n)\mid(x_1,\dots,x_n))=\prod_{k=1}^n p(y_k\mid x_k)\).

5. (想法二: 联合典型序列解码最优的解码策略其实是最大似然估计 (MLE), 但这分析起来较困难. 所以我们采用渐进最优的策略.^[1]) 接收方收到 \((y_1,\dots,y_n)\). 他猜测发送的信息为 \(m_j\), 如果

   • \((x_1(m_j),\dots,x_n(m_j),y_1,\dots,y_n)\) 是联合典型序列.
   • 没有其他的 \(m_j\) 使得该序列为联合典型序列.

   如果不存在 / 存在多于一个这样的 \(m_j\), 则解码失败.

6. 若解码失败或者解码出的 \(m_j\neq m_i\), 则发生错误.

分析错误的概率. 错误率是所有随机编码错误率的均值: \[ P(\textsf{error}) = \sum_{\mathcal{C}} P(\mathcal{C})P(\textsf{error}\mid\mathcal{C}). \] 取定编码 \(\mathcal{C}\). 注意到各个 \(m_i\) 的概率相等, 不妨假设发送的是 \(m_1\). 记事件 \(E_i\) (\(i=1,\dots,2^{nR}\)) 表示 \[ (x_1(m_i),\dots,x_n(m_i),y_1,\dots,y_n) \] 构成联合典型序列. 则发生错误当且仅当 \(E_1^c\) 发生 (发送的编码与收到的编码不构成联合典型序列) 或者 \(E_2\cup\cdots\cup E_{2^{nR}}\) 发生 (收到的编码与其他编码构成联合典型序列). 错误的概率为 \[ \Align{ P(\textsf{error}\mid\mathcal{C}) &= P(E_1^c\cup E_2\cup\cdots\cup E_{2^{nR}}) \\ &\leq P(E_1^c) + \sum_{i=2}^{2^{nR}} P(E_i). } \] - 由联合 AEP, \(P(E_1^c)\to0\) (\(n\to\infty\)), 第一项可以任意小.

• 由 \(\mathcal{C}\) 的定义, \((x_1(m_i),\dots,x_n(m_i))\) 与 \((x_1(m_1),\dots,x_n(m_1))\) 独立, 进而 \((x_1(m_i),\dots,x_n(m_i))\) 与 \((y_1,\dots,y_n)\) 独立. 根据联合 AEP 的 (3), 有 \[ P(E_i) \approx 2^{-nI(X;Y)}. \] 因此 \[ \Align{ \sum_{i=2}^{2^{nR}} P(E_i) &\approx (2^{nR}-1) 2^{-nI(X;Y)} \\ &\leq 2^{nR}2^{-nI(X;Y)} \\ &= 2^{-n(I(X;Y)-R)}. \\ } \] 若取 \(\mathcal{C}\) 的分布 \(p=\argmax_{p}I(X;Y)\), 则上式中 \(I(X;Y)=C>R\), 故当 \(n\to\infty\) 时, 第二项也可以任意小.

总之, 错误率可以任意小. 最后我们将随机编码变成一个确定的编码. 因为任给 \(\varepsilon>0\), 对于充分大的 \(n\), 随机编码的平均错误率小于 \(\varepsilon\). 故存在 \((2^{nR},n)\) 编码 \(\mathcal{C}^*\), 其错误率小于 \(\varepsilon\). 这便证明了 achievability.

6.4.2 Necessity

需要证明, 若比特率为 \(R\) 的纠错码序列错误率趋于 \(0\), 则 \(R\leq C\).

思想是对错误率等于 \(0\) 的纠错码证明 \(R\leq C\), 再推广到错误率趋于 \(0\) 的纠错码.

---

1. 最优的解码策略其实是最大似然估计 (MLE), 但这分析起来较困难. 所以我们采用渐进最优的策略.↩︎