Information Theory, Inference and Learning Algorithms Lecture 7
课程主页：http://www.inference.org.uk/mackay/itprnn/，http://www.inference.org.uk/itprnn_lectures/
课程书籍：https://book.douban.com/subject/1893050/
这次回顾第七讲，第七讲介绍了噪声信道编码定理。
备注：笔记参考了中文书籍。
信道容量
信道$Q$的容量是：
来看一个具体例子：
考虑有噪声的打字机模型，输入输出均为$\{A, B, \cdots, Z,-\}$，对于每个输入，输出以相同概率取其相邻的$3$个字符，图示如下：
信道模型为
不难看出
因为
所以
注意到
当且仅当$X$服从均匀分布时等号成立。
所以
噪声信道编码定理
分组码
信道$Q$的$(N,K)$分组码是一列个数为$S=2^K$的码字：
每个码字的长度为$N$，分组码将$s \in\left\{1,2,3, \cdots, 2^{K}\right\}$编码为$x^{(s)}$，码率定义为：
$(N,K)$分组码的译码器将长度为$N$的串$\mathscr{B}_{Y}^{N}$映射为一个码字标号$\hat{s} \in\left\{0,1,2, \cdots, 2^{K}\right\}$，其中$\hat s=0$表示错误。
分组差错概率
最大分组差错概率
最优译码器
最优译码器是指能够对分组差错概率进行最小化的译码器：
香农噪声信道编码定理（第一部分）
对于每个离散无记忆信道，存在一个具有如下性质的非负数 $C$(称为信道容量) 。对于任意$\varepsilon>0$ 和$R<C$，当$N$足够大时，存在一个长度为$N$且码率$\ge R$的分组码以及一个译码算法，使得最大大分组差错概率 $<\varepsilon$，图示如下：
定理验证（举例）
依然考虑有噪声的打字机，考虑如下分组码：每隔$3$个字母取一个字母，取$B,E,H,\ldots, Z$（这些字母构成输入符号表的一个不易混淆子集），这样可以产生如下完全无误的通信策略，如下图所示：
上述分组码和定理的对应关系如下：
定理的直观证明
拓展信道
考虑$N$次信道所使用的的拓展信道，拓展信道有$\left|\mathscr{B}_{X}\right|^{N}$个可能的输入$x$和$\left|\mathscr{B}_{Y}\right|^{N}$的输出。
定理的直观想法如下：如果$N$很大，那么拓展信道看起来非常像一个有噪声的打字机，任何输出$x$所产生的输出很可能属于输出字符表的一个小子空间里（输入的典型输出集合），所以我们只要找到输入的一个不易混淆子集来产生不相交的输出序列。
下面进行定量分析。由Lecture 3的内容可得典型输出序列$y$的数目为$2^{NH(Y)}$；给定输入序列$x$，大约有$2^{NH(Y|X)}$个典型输出。
类似有噪声的打字机，我们需要选择$n$个输入$x\in X^N$（$n$为不易混淆输入的数量），使得输出不会引起混淆。注意每个$x$对应$2^{NH(Y|X)}$个典型输出，而总共的典型输出数目为$2^{NH(Y)}$，所以必然有如下不等式
如果$X$是使得$I(X;Y)$最大化的总体，那么可以得到上述界限的最大值，此时不易混淆输入的数量$\le 2^{NC}$。因此，渐进地最多可以用每周期$C$比特的速率，进行零差错概率通信。