Information Theory, Inference and Learning Algorithms Lecture 1

课程主页：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/

最近开始补充信息论的知识，选择了David J.C. MacKay老师的课程以及书籍。

这次回顾第一讲，第一讲介绍了信息论导论。

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

如何在非理想的噪声信道上实现理想的通信

信息专递

在信道上发送数据（比特串），有一定概率接受到的消息不同于被发送的消息，考虑二进制对称信道：

解决方法

为了解决上述问题，可以设计一个系统，该系统中涉及编码解码：

信息论关注上述系统的理论极限，编码理论关心如何创建编码器和译码器。

备注：注意这里只考虑二进制信息。

二进制对称信道的纠错码

重复码

重复码的思路很简单，将消息中的每个比特重复多次，例如重复码$R_3$：

源序列	发送序列
$s$	$t$
$0$	$000$
$1$	$111$

编码之后，会通过噪声信道，可以将上述过程描述为在发送序列上叠加噪声向量$n$，其中叠加过程是在模2意义下的，来看具体的例子：

译码过程很简单，选择3个比特中出现次数较多的类别作为结果，例如010译成0，111译成1。

这来补充一个重要概念——码率，码率是指原始编码长度和编码后的编码长度之比，例如$R_3$的码率为$\frac 1 3$。

分组码——(7,4)汉明码

分组码是将长度为$K$的一个源比特序列$s$转换成长度为$N$比特的发送序列$t$的一条规则（一般假定$N>K$）。如果多出来的$N-K$比特是原有$K$比特的线性函数，那么称为线性分组码，多出来的比特叫做奇偶校验比特。$(7,4)$汉明码每收到$4$比特，就发送$7$比特，规则如下图所示：

$(7,4)$汉明码规则是，保证上图每个圆内的比特和为$0$（模$2$意义下），写成代数形式为

$$t=G^{\mathrm{T}} s$$

其中

$$\boldsymbol{G}^{\mathrm{T}}=\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]=\left[\begin{array}{l} \boldsymbol{I}_{4} \\ \boldsymbol{P} \end{array}\right]$$

不难看出(7,4)汉明码的码率为$\frac 4 7 $。

(7,4)汉明码的译码

(7,4)汉明码将$s$映射到$t$，然后经过噪声信道变成接受向量$r$，译码的任务是翻转最少的比特，使得翻转后的编码为合理的(7,4)汉明码。（奇偶校验错误的模式称为校正子，可以写成二进制向量，例如图(b)的校正子为$(1,1,0)$）

如果只有一个比特得到翻转，那么很容易进行译码：

穷举全部情形不难得到校正子和翻转比特的关系：

校正子译码

可以用矩阵来描述线性码的译码问题。前4个接收比特 $r_{1} r_{2} r_{3} r_{4}$称为4个源比特 ; 接收比特 $r_{5} r_{6} r_{7}$称为源比特的校验 $,$ 如生成矩阵$G$所定义。先求接收比特$r_{1} r_{2} r_{3} r_{4}$的$3$个奇偶校验比特，并看它们是否和3个接收比特$r_{5} r_{6} r_{7}$匹配。这两个三元组之间的(模 2)差称为接收向量的校正子（图(b)的校正子为$(1,1,0)$）。如果校正子为$(0,0,0)$，即所有3个奇偶校验都是正确的，那么接收向量是一个码字，最有可能的译码就是直接读出其前4个比特。如果校正子非零，则这个分组的噪声序列是非零的，而且校正子会指示出最可能的错误模式。

校正子向量的代数表示为

$$\boldsymbol z=\boldsymbol{H} \boldsymbol{r}$$

其中

$$\boldsymbol{H}=\left[\begin{array}{ll} -\boldsymbol{P} & \boldsymbol{I}_{3} \end{array}\right]\overset{模2}= \left[\begin{array}{ll} \boldsymbol{P} & \boldsymbol{I}_{3} \end{array}\right]=\left[\begin{array}{lllllll} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{array}\right]$$

不难出所有码字$t=G^{\mathrm{T}} s$满足

$$\boldsymbol{H} \boldsymbol{t} =(-\boldsymbol P+ \boldsymbol P)\boldsymbol s =\left[\begin{array}{l} 0 \\ 0 \\ 0 \end{array}\right]$$

注意接受向量为

$$\boldsymbol{r}=\boldsymbol{G}^{\mathrm{T}} \boldsymbol{s}+\boldsymbol{n}$$

所以译码问题为求解

$$\boldsymbol H\boldsymbol r=\boldsymbol H\boldsymbol n=\boldsymbol z$$

的最可能噪声$\boldsymbol n$。

一些概念

如果4个译码后的比特$\hat{s}_{1}, \hat{s}_{2}, \hat{s}_{3}, \hat{s}_{4}$和源比特$s_{1}, s_{2}, s_{3}, s_{4}$不完全相同，就称出现了译码错误，与此相关有两个重要的概念。

分组差错概率：

$$p_{\mathrm{B}}=P(\hat{\boldsymbol{s}} \neq \boldsymbol{s})$$

误码率：

$$p_{\mathrm{b}}=\frac{1}{K} \sum_{k=1}^{K} P\left(\hat{s}_{k} \neq s_{k}\right)$$

最佳码能达到何种性能?

将码率和误码率$\left(R, p_{b}\right)$在平面上作图可以得到可达区域以及不可达区域，香农证明了一个重要结论：可达区域和不可达区域之间的分界线（香农极限）和$R$轴交于一个非零点$R=C$，其中$C$被称为信道的容量。具体来说误码率$p_{\mathrm{b}}$可以任意小的最大通信码率称为信道的容量，噪声水平为$f$的二进制对称信道的容量公式为

$$C(f)=1-H_{2}(f)=1-\left[f \log _{2} \frac{1}{f}+(1-f) \log _{2} \frac{1}{1-f}\right]$$

上述结论的图示如下：

其中图示香农极限的方程为

$$R=\frac C {1-H_2(p_b)}$$

香农噪声信道编码定理

上述内容的正式描述即为香农噪声信道编码定理：

• 信息可以在一个噪声信道上以一个非零速率进行通信，并使得差错概率为任意小。