没想到被催更了，本来都打算不更第八章了，都是应用的东西，但是既然有朋友想看，我就速度更新。

第八章-无失真信源编码

嘿嘿，终于到最后一章了，这章要与第五章结合食用，如果有通信原理的基础，那这章不要太简单。好吧它其实不简单，只是我们学校比较仁慈。

香农第一定理告诉我们，对于一个的信源，我们总能找到一种编码方式实现无冗余编码（最低冗余编码）。那这种编码是什么呢，香农不知道，但是来自MIT的本科生给出了霍夫曼编码。

霍夫曼编码

霍夫曼编码到底怎么编码？这里真的是一个数字游戏，自己多玩几次就一定会了

霍夫曼编码有一些细节会对结果造成影响，如果严格按照从最小的两个开始以此编码，那么得到的一定是紧致码，在编码过程中，合并的新元素如果和旧元素概率一样，谁在上谁在下呢？通过尝试和计算我们可以得到，新元素在上的方差更小，因为减少了重复编码，使得各个码字长度更平均。

那么在例题中大家会发现有时候答案会一次对四个进行编码，或者那个箭头到处飞，是什么情况呢。一次对四个编码一般是最后两个编码之后升上去了，下次编码就是倒数第三和倒数第四，那么这四个小概率符号在一次进行编码，是等价，一样可以得到紧致码，这样写主要是节约时间比较快速。

但是如果倒数第一和倒数第二合并之后还在倒数行列中，那直接对倒数四个符号同时编码，就会让整个编码结果变成非紧致码。

紧致码的条件就是严格按照从小到大顺序每次仅一次编码，在不影响的前提一下可以同时进行。

箭头到处飞主要是同概率符号的顺序问题，它会影响到最后输出的霍夫曼码的方差。

那么有的题目会给出两个信源分布，说这两个霍夫曼编码等价吗？有的同学编出来是完全一样的，有的不是，那究竟是不是等价的，答案是等价的。

只要码长分布是一样的，里面的01还是012都不会影响，例如码长分布是”22344“，只要码长分布是这样的，究竟是”00“还是”01“和还是”01111“还是”0011“都是等价的，这里也揭示了霍夫曼码是一种即时码，在编码过程中01可以互换，仅仅是二叉树镜像反转了一下，树的外形是等价的。

编码效率：

多元霍夫曼码同理。

书上搞了个香农-费诺-埃利斯编码，和上课讲的香农码有出入，所以以课件为准，它们都是算术编码。

同样是数字游戏，多玩就会。每个符号码字长度由公式导出：

最后通过加权相加也能计算出平均长度和效率。

有点像霍夫曼编码，只能说差点，它遵循的思路是尽可能将符号50%比50%进行划分，如果正好能这么理想，也能得到紧致码，但一般情况下不行。

非常简单，特点是码字是正着阅读，霍夫曼码是编完要逆序回去阅读。

对积累概率编码的都是算术编码，算术编码和分组码是同等级别的概念，介绍了香农码再讲算术编码是因为香农码是对一个符号集进行编码，而算术编码具有一套更普适的方法可以对长序列直接编码不需要列出整个符号集。

例如序列“11110000”，长度为8，符号集大小为256，显然不可能全部列出来，然后考虑它们的累积概率，那我们有没有一种办法直接从序列“11110000”出发，算出它的编码呢？这样我就不需要字典，发送方和接收方都可以通过计算直接编码译码。

首先累积函数有如下性质，真想计算累积概率笔者觉得画树图最简单，假如题目给了一个长度为8的序列，那么可以画出一个深度为8的树图，把指定序列右边的概率全部加一起就是累加概率，如果序列结尾有0，则可以利用性质等效，但是这样的话新的树图深度应该是7，在新的树图再进行累加或者减去左边的分支。

这个例题的第一行就是把原始树图的右边分支全部相加，第三行就是把左边分支全部减去，而第四行就是将末尾的两个0等效掉，之后再把左边的分支剪掉，这种方式更快捷。

算术编码原始序列越长，越接近紧致码，也是一种效率很高的编码方式。