信息传递原理：通信论

第五章 信息传递原理：通信论本章介绍信息在空间中传递的基本原理，这就是通常所说的“通信论”。通信过程：信源编码信道译码信宿信源编码：把自然语言（如英语）编码成二元符号语言这样的能被信道理解的语言。对于编码，我们要讲这样几点：（1）编码的基本要求：在信宿接收到二进制信息后，我们能否把它正确译码成原来的英语信息（这是我们对编码规则最基本的要求），我们把满足这种要求的编码规则称为唯一可译码。如下面的编码规则肯定不是唯一可译码。 不是唯一可译码而是唯一可译码判断下面编码中哪些是唯一可译码： 即时码：我们在每接收到一个信源符号对应的二进制符号串，都能把它直接译成原来的信源符号。 不是即时码 是即时码判断下面编码中哪些是即时码： （2）设信源共有个符号，它们出现的概率分别为：。我们要考虑的问题是如何找到一种可变长度即时码的方法，使得在该种编码方法下，平均长度比其他的编码方法都要小。我们知道的编码方法叫哈夫曼编码方法（这里表示的是符号的编码长度）。哈夫曼是如何发现该种编码方法的呢？若把个符号看作一棵二叉树的个叶子结点，其中结点到根结点的路径长度为并设结点的权重为，则我们知道该二叉树的带权路径长度等于：。（这里要详细解释，一种编码方法与一棵二叉树之间的一一对应关系）我们这个发现的意义在于：我们把根据各信源符号出现的概率大小找到一种最佳的编码方法的过程转化为根据各叶子结点的权找到一棵带权路径长度最短的二叉树的过程。那么后一种过程比前一种过程简单在哪里呢？如果我们把个叶子结点看作棵二叉树，则我们可通过每次把两棵二叉树合并成一棵二叉树来在次合并后得到一棵以这个结点为叶子结点的二叉树。我们知道每次合并后的带权路径长度与原来两棵二叉树的带权路径长度之间的关系（在黑板上解释。例子：）。哈夫曼的发现是：如果我们每次都是把权最小的两棵二叉树合并成一棵二叉树，则最后得到的一定是一棵带权路径长度最短的二叉树。（用一个具体例子解释：这样我们得到如下的哈夫曼编码方法：(1):用0,1 码符号分别代表概率最小的两个信源符号,并将这两个概率最小的信源符号合并成一个,从而得到只包含个符号的新信源,称为缩减符号.(2): ：把缩减符号的符号中的最后两个概率最小的符号合并成一个,并分别用0与1码符号表示,这样又形成了个符号的缩减符号。(3)：反复执行(3),直到信源最后仅剩下两个符号,将这两个符号分别用二进制符号0与1表示.(4) ：然后,从最后一级缩减信源开始,向前返回,就得到各信源符号所对应的码符号序列,即相应的码字。（用具体的例子解释：）练习：设 七个源符号的概率分别为。请给出它们的哈夫曼编码。现在我们要讲信息在信道中的传输：当由于白噪声的影响，信息在信道中传输时有可能发生传输错误，而这会影响信息的传输速度。举个例子说明：设信道传输的不同符号只有两个：0与1，信道在传输0与1的时候错误概率均为，为了降低传输的错误概率到可以忽视不计，我们就需要在信道传输前在信息中加一些重复码，这样肯定会在降低错误概率的同时降低了传输的速度。 我们先考虑如何依据信道在传输信息时的错误概率来描述信道？设在信源编码后，信源符号的集合为：，一般来说，信宿的符号集合同样为（特殊情形就不一定了），但是一般来说，信源符号在经过信道传输到达信宿后仍然为的概率不会是。设用符号表示信源符号在经过信道传输到达信宿后变为的概率。则对于单个信源符号来说，我们可以用来描述信道。其次我们用信息量这个概念来描述信道：设，则平均一个信源符号包含的信息量为：比特，设，则平均一个信源符号在到达对方后所包含的信息量为：比特，显然信源发送的信息并没有全部通过信道发送到信宿；而信宿接收到的信息中也并不全是信源通过信道传输过来的；因此我们想要知道的是：信源发送的信息中有多少通过信道发送到了信宿或者信宿接收到的信息中有多少是信源通过信道发送过来的（显然这两者是相等的：都表示的是：信源通过信道发送而被信宿接收到的信息）？我们知道有这样三种信息：其中：表示的是当信宿确定时，信源还剩下的不知道的信息；即当输出端收到输出符号以后，对输入还存在的平均不确定程度。因此它称为是信道疑义度。显然这部分信息在信道中损失掉了，因此我们也把它称为损失熵。则表示的是：信息在信道传输过程中增加的无用信息（即噪音）。因而与都不能用来表示：信源通过信道发送而被信宿接收到的信息。最后我们发现：信宿与信源之间的平均互信息是我们要求的信源通过信道发送而被信宿接收到的信息。于是我们得到这样一个结论：越大，表示信道的性能越好。现在我们来具体考虑与信道错误概率的关系：设信源要发送的信号为1与0，且概率均为 而信道为：，这个信道无论在传输0还是传输1时错误概率均为，通过计算我们得到：比特，而这个计算结果说明了什么？其中躁声熵为：比特。最后我们考虑如何改进信道的通信质量。（1） 简单重复编码设一二元对称信道的信道矩阵为：，选择最佳译码规则为：。在输入分布为等概率分布条件下的平均错误概率为：。现采用简单重复编码，规定信源符号为“0”（或“1”）时，则重复发送三个“0”（或“1”），如此发送的信道可看成是二元对称信道的三次扩展信道，记，若采用极大似然译码规则进行译码，则我们得到平均错误概率为：（？）。第二种方法：通过让任意两个输入之间的距离都比较大来实现检错与纠错。该方法在译码时采用的方法是这样的：则在译码时必须求出与集合中每一个元素之间的距离，如果发现：，则会把翻译为。该方法基于如下两个假设：（1）：在发送端，每个码字的概率是一样的。（2）信道是对称的，即符号0与1在传送的过程中间出现错误的概率都是一样的。也就是说，如果这两个假设是成立的，则该译码规则是最佳的，但在一般情形，该译码规则不是最佳的。该方法的效果见书上题目6.8: 第三种方法：汉明编码方法。我们知道位运算具有如下特性：设是要传输的一些二进制位，如果在传输之前，而信宿在接收到收到信号后，发现，那么信宿在可以确定这些位中