台交大信息论 Lecture 10

课程主页：https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页：http://shannon.cm.nctu.edu.tw/

课程视频：https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第十讲，这一讲主要介绍了香农信道编码定理，对应视频17，18。

通过DMC进行数据传输的分组码

定长数据传输码

给定正整数$n$和$M$，以及具有输入字母$\mathcal X$和输出字母$\mathcal Y$的离散信道，此信道的固定长度数据传输码（或块码）的块长为$n$，每个信道符号的速率为$\frac{1}{n} \log _{2} M$比特，块码用$\mathcal{C}_{n}=(n, M)$表示，由如下内容组成：

1. $M$个用于传输的消息的信息

2. 编码函数

   $$f:\{1,2, \ldots, M\} \rightarrow \mathcal{X}^{n}$$

   生成长度为$n$的码字$f(1), f(2), \cdots, f(M) \in \mathcal{X}^{n}$。这$M$个码字被称为codebook，通常写成$\{f(1), f(2), \cdots, f(M)\}$

3. 解码函数$g: \mathcal{Y}^{n} \rightarrow\{1,2, \ldots, M\}$

平均误差概率

$\mathcal{C}_{n}=(n, M)$的平均误差为（编码函数为$f(.)$，解码函数为$g(.)$）：

$$P_{e}\left(\mathcal{C}_{n}\right):=\frac{1}{M} \sum_{w=1}^{M} \lambda_{w}\left(\mathcal{C}_{n}\right)$$

其中

$$\begin{aligned} \lambda_{w}\left(\mathcal{C}_{n}\right) :&=\operatorname{Pr}[\hat{W} \neq W | W=w]\\ &=\operatorname{Pr}\left[g\left(Y^{n}\right) \neq w | X^{n}=f(w)\right] \\ &=\sum_{y^{n} \in \mathcal{Y}^{n}: g\left(y^{n}\right) \neq w} P_{Y^{n} | X^{n} }\left(y^{n} | f(w)\right) \end{aligned}$$

是在消息$w$通过信道发送的情况下编码发生解码错误的条件概率。

最大误差概率

$$\lambda\left(\mathcal{C}_{n}\right):=\max _{w \in\{1,2, \cdots, M\} } \lambda_{w}\left(\mathcal{C}_{n}\right)$$

显然

$$P_{e}\left(\mathcal{C}_{n}=(n, M)\right) \leq \lambda\left(\mathcal{C}_{n}=(n, M)\right)$$

根据$\lambda_{w}\left(\mathcal{C}_{n}\right)$从大到小排序，将前一半的对应的码字丢弃，得到$\mathcal{C}_{n}^{\prime}$，那么

$$P_{e}\left(\mathcal{C}_{n}\right)=\frac{1}{M} \sum_{w=1}^{M} \lambda_{w}\left(\mathcal{C}_{n}\right) \ge \frac 1 M \frac M 2 \lambda\left(\mathcal{C}_{n}'\right)=\frac{1}{2} \lambda\left(\mathcal{C}_{n}^{\prime}\right)$$

从而

$$\frac{1}{2} \lambda\left(\mathcal{C}_{n}^{\prime}\right) \leq P_{e}\left(\mathcal{C}_{n}\right) \leq \lambda\left(\mathcal{C}_{n}\right)$$

其中码率分别为

$$\begin{aligned} R&=\frac{1}{n} \log _{2}(M)\\ R^{\prime}&=\frac{1}{n} \log _{2}(M / 2)\\ &=R-\frac{1}{n} \end{aligned}$$

联合典型集

$n$元组对$\left(x^{n}, y^{n}\right)$关于无记忆分布

$$P_{X^{n}, Y^{n} }\left(x^{n}, y^{n}\right)=\prod_{i=1}^{n} P_{X, Y}\left(x_{i}, y_{i}\right)$$

的$\delta$联合典型集$\mathcal{F}_{n}(\delta)$定义为

$$\begin{aligned} \mathcal{F}_{n}(\delta):=&\left\{\left(x^{n}, y^{n}\right) \in \mathcal{X}^{n} \times \mathcal{Y}^{n}:\right.\\ &\left|-\frac{1}{n} \log _{2} P_{X^{n} }\left(x^{n}\right)-H(X)\right|<\delta \\ &\left|-\frac{1}{n} \log _{2} P_{Y^{n} }\left(y^{n}\right)-H(Y)\right|<\delta \\ & \text { and } \left.\left|-\frac{1}{n} \log _{2} P_{X^{n}, Y^{n} }\left(x^{n}, y^{n}\right)-H(X, Y)\right|<\delta\right\} \end{aligned}$$

联合AEP

$\left\{\left(X_{i}, Y_{i}\right)\right\}_{i=1}^{\infty}$是DMS的无记忆独立对，那么随着$n\to \infty$，我们有

$$\begin{aligned} -\frac{1}{n} \log _{2} P_{X^{n} }\left(X_{1}, X_{2}, \ldots, X_{n}\right) \rightarrow H(X) \quad \text { in probability } \\ -\frac{1}{n} \log _{2} P_{Y^{n} }\left(Y_{1}, Y_{2}, \ldots, Y_{n}\right) \rightarrow H(Y) \quad \text { in probability } \\ -\frac{1}{n} \log _{2} P_{X^{n}, Y^{n} }\left(\left(X_{1}, Y_{1}\right), \ldots,\left(X_{n}, Y_{n}\right)\right) \rightarrow H(X, Y) \quad \text { in probability } \end{aligned}$$

证明：

利用大数定律即可。

Shannon-McMillan-Breiman定理

$\left\{\left(X_{i}, Y_{i}\right)\right\}_{i=1}^{\infty}$是DMS的无记忆独立对，联合熵为$H(X, Y)$，$\forall \delta >0$，我们可以选择充分大的$n$，使得联合$\delta$典型集$\mathcal{F}_{n}(\delta)$满足如下性质：

1. 对于充分大的$n$，我们有$P_{X^{n}, Y^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right)<\delta$

2. 对于充分大的$n$，$\left|\mathcal{F}_{n}(\delta)\right|>(1-\delta) 2^{n(H(X)-\delta)}$；对于每个$n$，$\left|\mathcal{F}_{n}(\delta)\right| \leq 2^{n(H(X)+\delta)}$

3. 如果$\left(x^{n}, y^{n}\right) \in \mathcal{F}_{n}(\delta)$，那么

   $$2^{-n(H(X, Y)+\delta)}<P_{X^{n}, Y^{n} }\left(x^{n}, y^{n}\right)<2^{-n(H(X, Y)-\delta)}$$

证明：

同Lecture 6 AEP的推论。

操作容量（Operational capacity）

对于离散系统，比率$R$是可达的，如果存在$\left(n, M_{n}\right)$信道编码$\mathcal{C}_{n}$，满足

$$\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} \geq R \quad \text { and } \quad \lim _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)= 0$$

信道的操作容量$C_{op}$是所有可达比率的上确界：

$$C_{o p}=\sup \{R: R \text { is achievable }\}$$

香农信道编码定理

考虑具有有限输入字母$\mathcal X$，有限输出字母$\mathcal Y$和转移分布概率$P_{Y | X}(y |x)$的DMC。定义信道容量（或信息容量）

$$C:=\max _{P_{X} } I(X ; Y)=\max _{P_{X} } I\left(P_{X}, P_{Y | X}\right)$$

那么如下事实成立。

1. Forward（可达性）：对于任意$0<\varepsilon<1$，存在$\gamma>0$以及数据传输分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$，满足

   $$(C>) \quad \liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} \geq C-\gamma$$

   以及对于充分大的$n$，我们有

   $$P_{e}\left(\mathcal{C}_{n}\right)<\varepsilon$$

   其中$P_{e}\left(\mathcal{C}_{n}\right)$表示关于分块码$\mathcal{C}_{n}$的平均误差概率。

2. Converse：对于任意$0<\varepsilon<1$，以及满足如下条件的数据传输分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$

   $$R=\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n}>C$$

   对于充分大的$n$，都有

   $$P_{e}\left(\mathcal{C}_{n}\right)>(1-\epsilon) \mu$$

   其中

   $$\mu=1-\frac{C}{\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} }=1-\frac C R>0$$

   令$n\to \infty$，我们有

   $$\liminf _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right) \geq \lim _{\epsilon \downarrow 0}(1-\epsilon) \mu=\mu$$

   这说明对于所有足够大的$n$，编码的错误概率都无法任意趋于$0$。

补充说明：

1. 注意到

   $$I\left(P_{X}, P_{Y | X}\right)=\sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } P_{X}(x) P_{Y | X}(y | x) \log _{2} \frac{P_{Y | X}(y | x)}{\sum_{x^{\prime} \in \mathcal{X} } P_{X}\left(x^{\prime}\right) P_{Y | X}\left(y | x^{\prime}\right)}$$

   而$P_{Y|X}$是已知的，上述方法更容易计算信道容量。

2. 对于固定的$P_{Y | X}$，$I\left(P_{X}, P_{Y | X}\right)$关于$P_X$连续且凹，所以极值可取到。

证明：

Forward

Forward：

当$C=0$时，取$M_n=1$，此时

$$\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} =0 \geq -\gamma =C-\gamma$$

另一方面

$$\begin{aligned} P_{e}\left(\mathcal{C}_{n}\right) &=\frac{1}{M} \sum_{w=1}^{M} \lambda_{w}\left(\mathcal{C}_{n}\right)\\ &= \lambda_{1}\left(\mathcal{C}_{n}\right)\\ &=\sum_{y^{n} \in \mathcal{Y}^{n}: g\left(y^{n}\right) \neq 1} P_{Y^{n} | X^{n} }\left(y^{n} | f(1)\right)\\ &= \sum_{y^{n} \in \mathcal{Y}^{n}: g\left(y^{n}\right) \neq 1} P_{Y^{n} }\left(y^{n}\right) (利用C=0)\\ &=0(由于只能映射为一个值，所以错误率为0) \end{aligned}$$

所以结论成立。

当$C>0$时，固定$\varepsilon \in(0,1)$以及满足$0<\gamma<\min \{4 \varepsilon, C\}$的$\gamma$。

注意到存在$N_0$，对于$n>N_0$，我们可以选择整数$M_n$，使其满足（当$n$充分大时总是能成立的）

$$C-\frac{\gamma}{2} \geq \frac{1}{n} \log _{2} M_{n}>C-\gamma$$

定义

$$\delta:=\gamma / 8$$

令$P_{\hat{X} }$为满足如下条件的分布

$$C:=\max _{P_{X} } I\left(P_{X}, P_{Y | X}\right)=I\left(P_{\hat{X} }, P_{Y | X}\right)$$

令

$$P_{\hat{Y}^{n} }\left(y^{n}\right)=\sum_{x^{n} \in \mathcal{X}^{n} } P_{\hat{X}^{n}, \hat{Y}^{n} }\left(x^{n}, y^{n}\right)$$

其中

$$P_{\hat{X}^{n}, \hat{Y}^{n} }\left(x^{n}, y^{n}\right):=P_{\hat{X}^{n} }\left(x^{n}\right) P_{Y^{n} | X^{n} }\left(y^{n} | x^{n}\right)$$

注意到由DMC的性质，我们可得

$$P_{\hat{X}^{n} }\left(x^{n}\right)=\prod_{i=1}^{n} P_{\hat{X} }\left(x_{i}\right)$$

步骤1：编码构造

• 对于分块长$n$，根据分布$P_{\hat{X}^{n} }\left(x^{n}\right)$独立选择$M_{n}$个信道输入。

• 选择的$M_{n}$个信道输入产生codebook

  $$\mathcal{C}_{n}:=\left\{c_{1}, c_{2}, \ldots, c_{M_{n} }\right\}$$

  定义编码和解码函数$f_n(.),g_n(.)$，其中

  $$f_{n}(m)=c_{m} \quad \text { for } 1 \leq m \leq M_{n}$$

  以及

  $$g_{n}(y^n)= \begin{cases} m, & 如果c_m是\mathcal C中唯一满足\left(\boldsymbol{c}_{m}, y^{n}\right) \in \mathcal{F}_{n}(\delta)的码字\\ \left\{1,2, \ldots, M_{n}\right\}中任意值 &其余情形 \end{cases}$$

  其中

  $$\begin{aligned} \mathcal{F}_{n}(\delta):=&\left\{\left(x^{n}, y^{n}\right) \in \mathcal{X}^{n} \times \mathcal{Y}^{n}:\right.\\ &\left|-\frac{1}{n} \log _{2} P_{X^{n} }\left(x^{n}\right)-H(X)\right|<\delta \\ &\left|-\frac{1}{n} \log _{2} P_{Y^{n} }\left(y^{n}\right)-H(Y)\right|<\delta \\ & \text { and } \left.\left|-\frac{1}{n} \log _{2} P_{X^{n}, Y^{n} }\left(x^{n}, y^{n}\right)-H(X, Y)\right|<\delta\right\} \end{aligned}$$

步骤2：计算条件错误率

$$\begin{aligned} \lambda_{m}\left(\mathcal{C}_{n}\right) \leq &\sum_{y^{n} \in \mathcal{Y}^{n}:\left(c_{m}, y^{n}\right) \notin \mathcal{F}_{n}(\delta)} P_{Y^{n} | X^{n} }\left(y^{n} | c_{m}\right)\\ & +\sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} } \sum_{y^{n} \in \mathcal{Y}^{n}:\left(c_{m^{\prime} }, y^{n}\right) \in \mathcal{F}_{n}(\delta)} P_{Y^{n} | X^{n} }\left(y^{n} | c_{m}\right) \end{aligned}$$

第一项表示输出不是联合典型的，第二项表示多于联合典型的元素不止一个。

计算平均误码率可得

$$\begin{aligned} \sum_{c_{m} \in \mathcal{X}^{n} } P_{\hat{X}^{n} }\left(c_{m}\right) \lambda_{m}\left(\mathcal{C}_{n}\right) \leq & \sum_{c_{m} \in \mathcal{X}^{n} } \sum_{y^{n} \notin \mathcal{F}_{n}\left(\delta | c_{m}\right)} P_{\hat{X}^{n} }\left(c_{m}\right) P_{Y^{n} | X^{n} }\left(y^{n} | c_{m}\right) \\ &+\sum_{c_{m} \in \mathcal{X}^{n} } \sum_{m^{\prime}=1 \atop m^{\prime} \neq m} \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n} }\left(c_{m}\right) P_{Y^{n} | X^{n} }\left(y^{n} | c_{m}\right)\\ =& P_{ {\hat{X^{n} }}, {\hat{Y^{n} }} }\left(\mathcal{F}_{n}^{c}(\delta)\right) \\ &+\sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} } \sum_{c_m \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n}, \hat{Y}^{n} }\left(c_{m}, y^{n}\right) \end{aligned}$$

其中

$$\mathcal{F}_{n}\left(\delta | x^{n}\right):=\left\{y^{n} \in \mathcal{Y}^{n}:\left(x^{n}, y^{n}\right) \in \mathcal{F}_{n}(\delta)\right\}$$

步骤3：计算平均错误率

$$\begin{aligned} E_{\mathcal C_{n} }\left[P_{e}\left(\mathcal{E}_{n}\right)\right]=& \sum_{\mathcal{C}_{n} } \operatorname{Pr}\left[\mathcal{C}_{n}\right] P_{e}\left(\mathcal{C}_{n}\right) \\ =& \sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} } \in \mathcal{X}^{n} } P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right)\left(\frac{1}{M_{n} } \sum_{m=1}^{M_{n} } \lambda_{m}\left(\mathcal{C}_{n}\right)\right) \\ =& \frac{1}{M_{n} } \sum_{m=1}^{M_{n} } \sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{m-1} \in \mathcal{X}^{n} } \sum_{c_{m+1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} } \in \mathcal{X}^{n} } \\ & P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{m-1}\right) P_{\hat{X}^{n} }\left(c_{m+1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right) \\ & \times\left(\sum_{c_{m} \in \mathcal{X}^{n} } P_{\hat{X}^{n} }\left(c_{m}\right) \lambda_{m}\left(\mathcal{C}_{n}\right)\right)\\ \leq & \frac{1}{M_{n} } \sum_{m=1}^{M_{n} } \sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{m-1} \in \mathcal{X}^{n} } \sum_{c_{m+1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} \in \mathcal{X}^{n} }} \\ & P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{m-1}\right) P_{\hat{X}^{n} }\left(c_{m+1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right) \\ & \times P_{\hat{X}^{n}, \hat{Y}^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right) \\ +& \frac{1}{M_{n} } \sum_{m=1}^{M_{n} } \sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{m-1} \in \mathcal{X}^{n} } \sum_{c_{m+1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} } \in \mathcal{X}^{n} } \\ & P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{m-1}\right) P_{\hat{X}^{n} }\left(c_{m+1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right) \\ & \times \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} } \sum_{c_{m} \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n}, \hat{Y}^{n} }\left(c_{m}, y^{n}\right)\\ =&P_{\hat{X}^{n}, Y^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right) \\ +&\frac{1}{M_{n} } \sum_{m=1}^{M_{n} }\left\{\sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left[\sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{m-1} \in \mathcal{X}^{n} } \sum_{c_{m+1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} } \in \mathcal{X}^{n} } \ldots\right.\right. \\ &P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{m-1}\right) P_{\hat{X}^{n} }\left(c_{m+1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right) \\ &\left.\left.\times \sum_{c_{m} \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n}, Y^{n} }\left(c_{m}, y^{n}\right)\right]\right\} \end{aligned}$$

现在对大括号内部的项进行化简

$$\begin{aligned} &\sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} } \left[\sum_{c_{1} \in \mathcal{X}^{n} } \cdots \sum_{c_{m-1} \in \mathcal{X}^{n} } \sum_{c_{m+1} \in \mathcal{X}^{n} } \cdots \sum_{c_{M_{n} } \in \mathcal{X}^{n} }\right. \\ &P_{\hat{X}^{n} }\left(c_{1}\right) \cdots P_{\hat{X}^{n} }\left(c_{m-1}\right) P_{\hat{X}^{n} }\left(c_{m+1}\right) \cdots P_{\hat{X}^{n} }\left(c_{M_{n} }\right) \\ &\left.\times \sum_{c_{m} \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n}, \hat{Y}^{n} }\left(c_{m}, y^{n}\right)\right]\\ =& \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left[\sum_{c_{m} \in \mathcal{X}^{n} } \sum_{c_{m^{\prime} } \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n} }\left(c_{m^{\prime} }\right) P_{\hat{X}^{n}, \hat{Y}^{n} }\left(c_{m}, y^{n}\right)\right] \\ =& \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left[\sum_{c_{m^{\prime} } \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n} }\left(c_{m^{\prime} }\right)\left(\sum_{c_{m} \in \mathcal{X}^{n} } P_{\hat{X}^{n}, \hat{Y}^{n} }\left(c_{m}, y^{n}\right)\right)\right] \\ =& \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left[\sum_{c_{m^{\prime} } \in \mathcal{X}^{n} } \sum_{y^{n} \in \mathcal{F}_{n}\left(\delta | c_{m^{\prime} }\right)} P_{\hat{X}^{n} }\left(c_{m^{\prime} }\right) P_{\hat{Y}^{n} }\left(y^{n}\right)\right]\\ =& \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left[\sum_{\left(c_{m^{\prime} }, y^{n}\right) \in \mathcal{F}_{n}(\delta)} P_{\hat{X}^{n} }\left(c_{m^{\prime} }\right) P_{\hat{Y}^{n} }\left(y^{n}\right)\right] \\ \leq & \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} }\left|\mathcal{F}_{n}(\delta)\right| 2^{-n(H(\hat{X})-\delta)} 2^{-n(H(\hat{Y})-\delta)} \\ \leq & \sum_{m^{\prime}=1 \atop m^{\prime} \neq m}^{M_{n} } 2^{n(H(\hat{X}, \hat{Y})+\delta)} 2^{-n(H(\hat{X})-\delta)} 2^{-n(H(\hat{Y})-\delta)} \\ =&\left(M_{n}-1\right) 2^{n(H(\hat{X}, \hat{Y})+\delta)} 2^{-n(H(\hat{X})-\delta)} 2^{-n(H(\hat{Y})-\delta)} \\ <& M_{n} \cdot 2^{n(H(\hat{X}, \hat{Y})+\delta)} 2^{-n(H(\hat{X})-\delta)} 2^{-n(H(\hat{Y})-\delta)} \\ \leq & 2^{n(C-4 \delta)} \cdot 2^{-n(I(\hat{X} ; \hat{Y})-3 \delta)}\\ =&2^{-n \delta} \end{aligned}$$

最后一个不等号是因为

$$\frac{1}{n} \log _{2} M_{n} \le C-\frac{\gamma}{2}= C-4\delta$$

因此对于充分大的$n$，我们有

$$E_{\mathcal{C}_{n} }\left[P_{e}\left(\mathcal{C}_{n}\right)\right] \leq P_{\hat{X}^{n}, \hat{Y}^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right)+2^{-n \delta} \to 0$$

所以必然存在$\mathcal C_n$，满足

$$P_{e}\left(\mathcal{C}_{n}\right) \leq P_{\hat{X}^{n}, \hat{Y}^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right)+2^{-n \delta} \to 0$$

Converse

Converse：

回顾第四讲的Fano不等式：

令$X,Y$为两个相关随机变量，$X$取值于$\mathcal X$，$Y$取值于$\mathcal Y$，$\mathcal X$有限，$\mathcal Y$可数无限。假设$\hat{X}:=g(Y)$为通过观测$Y$得到对于$X$的估计，其中$g: \mathcal{Y} \rightarrow \mathcal{X}$是给定的估计函数。定义误差概率

$$P_{e}:=\operatorname{Pr}[\hat{X} \neq X]$$

那么如下不等式成立

$$H(X | Y) \leq h_{b}\left(P_{e}\right)+P_{e} \cdot \log _{2}(|\mathcal{X}|-1)$$

其中

$$h_{\mathrm{b} }(x):=-x \log _{2} x-(1-x) \log _{2}(1-x)$$

给定信息$W$（$W$关于$\left\{1,2, \cdots, M_{n}\right\}$服从均匀分布），在DMC上通过码字$X^{n}(W)=f_{n}(W)$传输信息，$Y^{n}$是信道输出，在接收端，得到信息$\hat{W}=g_{n}\left(Y^{n}\right)$，那么误差率为

$$\operatorname{Pr}[W \neq \hat{W}]=P_{e}\left(\mathcal{C}_{n}\right)$$

利用Fano不等式可得

$$\begin{aligned} H\left(W | Y^{n}\right) & \leq 1+P_{e}\left(\mathcal{C}_{n}\right) \log _{2}\left(M_{n}-1\right) \\ &<1+P_{e}\left(\mathcal{C}_{n}\right) \log _{2} M_{n} \end{aligned}$$

回顾下图

所以对于任意$\left(n, M_{n}\right)$分块信道码$\mathcal C_n$，

$$W \rightarrow X^{n} \rightarrow Y^{n}$$

是马尔可夫链，所以由数据处理不等式，我们有

$$I\left(W ; Y^{n}\right) \leq I\left(X^{n} ; Y^{n}\right)$$

另一方面

$$\begin{aligned} I\left(X^{n} ; Y^{n}\right) & \leq \max _{P_{X^{n} }} I\left(X^{n} ; Y^{n}\right) \\ & \leq \max _{P_{X^{n} }} \sum_{i=1}^{n} I\left(X_{i} ; Y_{i}\right) \\ & \leq \sum_{i=1}^{n} \max _{P_{X^{n} }} I\left(X_{i} ; Y_{i}\right) \\ &=\sum_{i=1}^{n} \max _{P_{X_{i} }} I\left(X_{i} ; Y_{i}\right)\\ &= nC \end{aligned}$$

注意$W$服从均匀分布，所以

$$\begin{aligned} \log _{2} M_{n} &=H(W) \\ & =H\left(W | Y^{n}\right)+I\left(W ; Y^{n}\right)(由定义) \\ &\leq H\left(W | Y^{n}\right)+I\left(X^{n} ; Y^{n}\right)(由信息处理不等式) \\ &\leq H\left(W | Y^{n}\right)+n C \\ &<1+P_{e}\left(\mathcal{C}_{n}\right) \cdot \log _{2} M_{n}+n C(由\text{Fano}不等式) \end{aligned}$$

对其变型可得

$$P_{e}\left(\mathcal{C}_{n}\right)>1-\frac{C}{(1 / n) \log _{2} M_{n} }-\frac{1}{\log _{2} M_{n} }=1-\frac{C+1 / n}{(1 / n) \log _{2} M_{n} }$$

如果

$$\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n}=\frac{C}{1-\mu}$$

即满足定理中的定义

$$\mu=1-\frac{C}{\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} }>0$$

那么对任意$0<\varepsilon<1$，存在$N$，使得$n\ge N$时，都有

$$\frac{1}{n} \log _{2} M_{n} \geq \frac{C+1 / n}{1-(1-\varepsilon) \mu}$$

这是因为如果上式不成立，那么存在无限多个$n$，满足

$$\frac{1}{n} \log _{2} M_{n} <\frac{C+1 / n}{1-(1-\varepsilon) \mu}$$

所以

$$\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n} \leq \liminf _{n \rightarrow \infty} \frac{C+1 / n}{1-(1-\varepsilon) \mu}=\frac{C}{1-(1-\varepsilon) \mu} < \frac {C}{1-\mu}$$

这就与

$$\liminf _{n \rightarrow \infty} \frac{1}{n} \log _{2} M_{n}=\frac{C}{1-\mu}$$

矛盾。

结合该不等式可得

$$P_{e}\left(\mathcal{C}_{n}\right)>1-[1-(1-\varepsilon) \mu] \frac{C+1 / n}{C+1 / n}=(1-\epsilon) \mu>0$$

图示：

定义

$$\underline{R}=\liminf _{n \rightarrow \infty} R_{n}=\liminf _{n \rightarrow \infty}(1 / n) \log _{2} M_{n}$$

上述定理实际上是说明

$$\left\{\begin{array}{ll} \lim _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)=0, & \text { for } \underline{R}<C \\ \lim \inf _{n \rightarrow \infty} P_{e}\left(\mathcal{C}_{n}\right)>0, & \text { for } \underline{R}>C \end{array}\right.$$