Information Theory, Inference and Learning Algorithms Lecture 8

课程主页：http://www.inference.org.uk/mackay/itprnn/，http://www.inference.org.uk/itprnn_lectures/

课程视频：https://www.bilibili.com/video/BV14b411G7wn?from=search&seid=1786094286746981315，https://www.youtube.com/watch?v=BCiZc0n6COY&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6

课程书籍：https://book.douban.com/subject/1893050/

这次回顾第八讲，第八讲介绍了噪声信道编码定理。

备注：笔记参考了中文书籍。

噪声信道编码定理

1. 对于每个离散的无记忆信道，信道容量

   $$C=\max _{\mathscr{P}_{X} } I(X ; Y)$$

   具有如下性质。对于任意 $\varepsilon>0$ 和 $R<C,$ 当 $N$ 足够大时,存在一个长度为 $N$ 的码 $,$ 码率 $\geqslant R$ 和一个译码算法，使得最大分组差错概率 $<\varepsilon$。

2. 如果误码率$p_{\mathrm{b} }$是可接受的，则不高于 $R\left(p_{\mathrm{b} }\right)$的码率是可达的，其中

   $$R\left(p_{\mathrm{b} }\right)=\frac{C}{1-H_{2}\left(p_{\mathrm{b} }\right)}$$

3. 对于任意 $p_{\mathrm{b} },$ 高于$R\left(p_{\mathrm{b} }\right)$的码率是不可达的：

   

   在 $R, p_{\mathrm{b} }$平面上，可证明区域(1,2)可达，而区域(3)不可达。

备注：

特定码$\mathscr B$的分组差错概率为

$$p_{\mathrm{B} }(\mathscr{B}) \equiv P(\hat{s} \neq s | \mathscr{P})$$

误码率 $p_{\mathrm{b} }$的定义为

$$\left\langle p_{\mathrm{B} }\right\rangle\equiv\sum_{\mathscr{E} } P(\hat{\boldsymbol{s} } \neq \boldsymbol{s} | \mathscr{B}) {P}(\mathscr{B})$$

最大分组差错概率定义为

$$p_{\mathrm{BM} }(\mathscr{B}) \equiv \max P(\hat{s} \neq s | s, \mathscr{B})$$

联合典型序列

基本概念

联合典型性：一对长度为$N$的序列$\boldsymbol{x}$和$\boldsymbol{y}$, 被定义为关于分布 $P(x, y)$ 是联合典型的(容差为 $\beta),$ 如果满足

$$\begin{array}{c} \boldsymbol{x} \text { 是 } P(\boldsymbol{x}) \text { 的典型, 即 }\left|\frac{1}{N} \log \frac{1}{P(x)}-H(X)\right|<\beta \\ \boldsymbol{y} \text { 是 } P(\boldsymbol{y}) \text { 的典型, 即 }\left|\frac{1}{N} \log \frac{1}{P(\boldsymbol{y})}-{H}(Y)\right|<\boldsymbol{\beta} \\ \boldsymbol{x}, \boldsymbol{y} \text { 是 } P(\boldsymbol{x}, \boldsymbol{y}) \text { 的典型, 即 }\left|\frac{1}{N} \log \frac{1}{P(\boldsymbol{x}, \boldsymbol{y})}-H(X, Y)\right|<\boldsymbol{\beta} \end{array}$$

联合典型集：$J_{N \beta}$ 是长度为$N$的所有联合典型序列对的集合。

联合典型性定理

总体$(XY)^N$定义为

$$P(x, y)=\prod_{n=1}^{N} P\left(x_{n}, y_{n}\right)$$

从总体$(X Y)^{N}$中选择$\boldsymbol{x}$和$\boldsymbol{y}$，则有

1. 当 $N \rightarrow \infty$ 时，$\boldsymbol{x}$和$\boldsymbol{y}$是联合典型序列 (容差$\beta$)的概率趋向于 $1_{\circ}$

2. 联合典型序列的数量$|J_{N\beta}|$接近 $2^{N H(X, Y)}$，精确地有

   $$\left|J_{N \beta}\right| \leqslant 2^{N(H(X, Y)+\beta)}$$

3. 如果 $\boldsymbol{x}^{\prime} \sim X^{N}$ 和 $\boldsymbol{y}^{\prime} \sim Y^{N}$，即 $\boldsymbol{x}^{\prime}$ 和 $\boldsymbol{y}^{\prime}$ 是与 $P(\boldsymbol{x}, \boldsymbol{y})$ 具有相同边缘分布的独立样本，则$(\boldsymbol{x}^{\prime}, \boldsymbol{y}^{\prime})$ 属于联合典型集的概率约为 $2^{-N I\left(X; Y\right)}$ 。更精确的表示为

   $$P\left(\left(x^{\prime}, y^{\prime}\right) \in J_{N \beta}\right) \leqslant 2^{-N(I(X ; Y)-3 \beta)}$$

证明：

第一部分：

类似Lecture 3的思路即可：

首先定义：

$$\begin{aligned} T_{N \beta}^{(x)} &=\left\{\boldsymbol{x} \in \mathscr{H}_{X}^{N}:\left|\frac{1}{N} \log \frac{1}{P(x)}-H(X)\right|<\beta\right\}\\ T_{N \beta}^{(y)} &=\left\{\boldsymbol{y} \in \mathscr{H}_{Y}^{N}:\left|\frac{1}{N} \log \frac{1}{P(y)}-H(Y)\right|<\beta\right\}\\ T_{N \beta}^{(xy)} &=\left\{\boldsymbol{xy} \in \mathscr{H}_{XY}^{N}:\left|\frac{1}{N} \log \frac{1}{P(x,y)}-H(X,Y)\right|<\beta\right\}\\ \sigma_x^2&= \operatorname{var}\left[\log _{2}\left(1 / P\left(x\right)\right)\right]\\ \sigma_y^2&= \operatorname{var}\left[\log _{2}\left(1 / P\left(y\right)\right)\right]\\ \sigma_{xy}^2&= \operatorname{var}\left[\log _{2}\left(1 / P\left(x,y\right)\right)\right] \end{aligned}$$

利用弱大数定律，我们有

$$\begin{aligned} P(x\in T_{N\beta}^{(x)})&\ge 1-\frac {\sigma_x^2 }{\beta^2N}\\ P(y\in T_{N\beta}^{(y)})&\ge 1-\frac {\sigma_y^2 }{\beta^2N}\\ P(xy\in T_{N\beta}^{(xy)})&\ge 1-\frac {\sigma_{xy}^2 }{\beta^2N}\\ \end{aligned}$$

注意到我们有

$$J_{N \beta}= T_{N\beta}^{(x)} \cap T_{N\beta}^{(y)} \cap T_{N\beta}^{(xy)}$$

所以

$$\begin{aligned} P(x\in J_{N\beta}) &= P(x\in T_{N\beta}^{(x)} \cap T_{N\beta}^{(y)} \cap T_{N\beta}^{(xy)})\\ &= 1- P\left(x\in \overline{T_{N\beta}^{(x)} } \cup \overline{T_{N\beta}^{(y)} } \cup \overline{T_{N\beta}^{(xy)} }\right)\\ &\ge 1- P\left(x\in \overline{T_{N\beta}^{(x)} }\right)- P\left(y\in \overline{T_{N\beta}^{(y)} }\right)- P\left(xy\in \overline{T_{N\beta}^{(xy)} }\right)\\ &\ge 1- \frac {\sigma_x^2 }{\beta^2N} -\frac {\sigma_y^2 }{\beta^2N} -\frac {\sigma_{xy}^2 }{\beta^2N}\\ &\to 1 \end{aligned}$$

第二部分：

将Lecture 3的$P(x)$替换为$P(x,y)$即可

第三部分：

$$\begin{aligned} P\left(\left(\boldsymbol{x}^{\prime}, \boldsymbol{y}^{\prime}\right) \in J_{N \beta}\right) &=\sum_{(x, y) \in J_{N \beta} } P(\boldsymbol{x}) P(\boldsymbol{y}) \\ & \leqslant\left|J_{N \beta}\right| 2^{-N(H(X)-\beta)} 2^{-N(H(Y)-\beta)} \\ & \leqslant 2^{N(H(X, Y)+\beta)-N(H(X)+H(Y)-2 \beta)}\\ &=2^{-N(I(X ; Y)-3 \beta)} \end{aligned}$$

典型集的图示如下：

两个独立的典型向量是联合典型的概率为

$$P\left(\left(x^{\prime}, y^{\prime}\right) \in J_{N \beta}\right) \simeq 2^{-N(I(X ; Y))}$$

因为独立典型对的总数是虚线矩形的面积 $2^{N H(X)} 2^{N H(Y)}$，联合典型对的数量约为$2^{NH(X,Y)}$，所以出现一个典型对的概率约为

$$2^{N H(X, Y)} / 2^{N H(X)+N H(Y)}=2^{-N I(X ; Y)}$$

噪声信道编码定理的证明

随机编码和典型集译码

考虑如下译码系统：

1. 固定$P(x)$，并按照如下概率随机地产生$\left(N, N R^{\prime}\right)=(N, K)$码$\mathscr{B}$ 中的$S=2^{N{R}^{\prime} }$个码字（即均匀分布）：

   $$P(x)=\prod_{n=1}^{N} P\left(x_{n}\right)$$

2. 发送方和接收方都知道该码字。

3. 从 $\{1,2, \cdots, 2^{N R}\}$ 中选择消息$s$，并传输$\boldsymbol{x}^{(s)}$。接收信号为 $\boldsymbol{y}$，满足：

   $$P\left(y | x^{(s)}\right)=\prod_{n=1}^{N} P\left(y_{n} | x_{n}^{(s)}\right)$$

4. 信号由典型集译码法来译码：

   如果 $\left(\boldsymbol{x}^{(\hat s)}, \boldsymbol{y}\right)$ 是联合典型的且没有其他 $s^{\prime}$ 使得 $\left(\boldsymbol{x}^{\left(s^{\prime}\right)}, \boldsymbol{y}\right)$ 是联合典型的，则$y$被译码为$\hat s$；否则认为译码失败($\hat s=0$)

5. 如果$\hat s\neq s$，则出现一个译码错误。

证明的第一部分

在上译码系统的基础上进行证明，即我们希望证明

$$p_{\mathrm{BM} }(\mathscr{E}) \equiv \max P(\hat{s} \neq s | s, \mathscr{R}) <\epsilon$$

不失一般性，假设$s=1$。

我们首先证明误码率

$$\left\langle p_{\mathrm{B} }\right\rangle\equiv\sum_{\mathscr{E} } P(\hat{\boldsymbol{s} } \neq \boldsymbol{s} | \mathscr{B}) \boldsymbol{P}(\mathscr{B})$$

可以任意小，这里注意译码一共有两种错误：

• (a)输出$y$和输入$x^{(s)}$不是联合典型的
• (b)$\mathscr{B}$有其他码字与$y$是联合典型的

(a)令输入$x^{(1)}$和输出$y$不是联合典型的概率为$\delta$，那么根据联合典型定理的第一部分，当$N\to \infty$时$\delta \to 0$，所以对于任意$\delta $，都存在$N(\delta)$，使得

$$P\left(\left(x^{(1)}, y\right) \notin J_{N \beta}\right) \leqslant \delta$$

(b)根据联合典型定理的第三部分，对于$s’\neq 1$，$x^{(s’)}$和$y$是联合典型的概率$\le 2^{-N(I(X ; Y)-3 \boldsymbol{\beta})}$，注意到$s’$一共有$2^{NR’}-1$个值可以考虑。

综合上述两点，误码率 $p_{\mathrm{b} }$满足

$$\begin{aligned}\left\langle p_{\mathrm{B} }\right\rangle & \leqslant \delta+\sum_{s^{\prime}=2}^{2^{N R^{\prime} } } 2^{-N(I(X ; Y)-3 \beta)} \\ & \leqslant \delta+ 2^{N R^{\prime} }2^{-N(I(X ; Y)-3 \beta)} \\ & \leqslant \delta+2^{-N\left(I(X ; Y)-R^{\prime}-3 \beta\right)} \end{aligned}$$

所以如果

$$R^{\prime}<I(X ; Y)-3 \beta$$

那么随着$N$增加，$p_{\mathrm{B} }$必然小于$2\delta$。

现在进行三个改动：

1. 选择输入$P(x)$为最优输入分布。于是$R’ < I(X;Y)-3\beta$变成$R’<C-3\beta$（注意$\beta$是任意值，所以$R’$可以和$C$任意逼近）

2. 因为

   $$\left\langle p_{\mathrm{B} }\right\rangle\equiv\sum_{\mathscr{E} } P(\hat{\boldsymbol{s} } \neq \boldsymbol{s} | \mathscr{B}) {P}(\mathscr{B})<2\delta$$

   所以必然存在一个码，使得

   $$p_{\mathrm{B} }(\mathscr{B}) \equiv P(\hat{s} \neq s | \mathscr{P}) < 2\delta$$

3. 为了证明最大差错概率$p_{\text{BM} }$也可以很小，现在对码进行修改：将$P(\hat{s} \neq s | \mathscr{P}) $从大到小排列，记为$P_1\le P_2\le \ldots \le P_{2^{NR’} }$，对应的先验概率为记为$P^{(i)}$，那么由于先验是均匀分布（我们的假设），所以

   $$\begin{aligned} \left\langle p_{\mathrm{B} }\right\rangle &=\sum_{\mathscr{E} } P(\hat{\boldsymbol{s} } \neq \boldsymbol{s} | \mathscr{B}) {P}(\mathscr{B})\\ &=\sum_{i=1}^{2^{NR'} } P_i P^{(i)}\\ &\ge \sum_{i=2^{NR'-1}+1}^{2^{NR'} } P_i P^{(i)} \\ &\ge P_{2^{NR'-1} } \sum_{i=2^{NR'-1}+1}^{2^{NR'} }P^{(i)} \\ &= \frac 1 2 P_{i=2^{NR'-1} } \end{aligned}$$

   注意$p_{\text{B} }<2\delta$，所以

   $$P_{2^{NR'-1} } < 4\delta$$

   现在删除$P_{i}, i> 2^{NR’-1}$的码字，用剩下的码字定义一个新码，该新码有$2^{NR’-1}$个码字，最大分组差错概率$<4\delta$，码率为$(NR’-1)/N= R’-1/N$。

定理的第二第三部分暂时还没吃透，这部分的笔记后续补充。