信息与编码理论 第2版 课件 4.2 无失真信源编码

§4.2无失真信源编码

无失真的信源编码定理既是存在性定理也是构造性定理，它给出了构造信源编码的原理性方法，使构造出的码的平均码长与信源统计特性相匹配。

为此，香农、费诺、霍夫曼都按上述思路设计出各自不同的具体编码方法，分别称之为香农编码、费诺编码和霍夫曼编码，其中霍夫曼编码最好。除此之外，常用的编码方法还有游程编码、算术编码、Lempel-Ziv算法等。4.2.1香农编码

4.2.2霍夫曼码1952年，霍夫曼提出了一种构造最佳码的方法，它是每个信源符号与其码字一一对应的一种编码方法。由它所得的码字是异前置码的变长码，其平均码长最短，是最佳变长码，又称霍夫曼码。通常情况下，将编码符号集中符号数等于2的称为二元码，等于3的称为三元码，……等于m的称为m元码。其中，二元码是数字通信和计算机系统中最常用的。二元霍夫曼码霍夫曼编码是用概率匹配方法进行信源编码。它有两个明显特点：一是霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。

m元霍夫曼码霍夫曼码编码构造出来的码不是唯一的，可是其平均码长却是相同的，所以不影响编码效率和数据压缩性能。霍夫曼码对不同信源其编码效率也不尽相同。当信源概率是2的负次幂时，霍夫曼码的编码效率达到100%；当信源概率相等时，其编码效率最低。因此，在使用霍夫曼码方法编码时，只有当信源概率分布很不均匀时，霍夫曼编码才会收到显著的效果。因为信源符号与码字之间不能用某种有规律的数字方法对应起来，所以只能通过某种查表方法建立它们的对应关系。信源符号增多时，所需存储的容量增大，使设备复杂化，同时也会使编译码时查表搜索时间有所增加。

尽管如此，霍夫曼方法还是一种较具体、有效的无失真信源编码方法，并且可以编成程序在计算机上实现。因此，霍夫曼编码在文件传真、语音处理和图像处理等的数据压缩中获得了广泛的应用。4.2.3费诺编码4.2.4香农-费诺-埃利斯码香农码、费诺码、霍夫曼码等都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；香农码有系统的、唯一的编码方法，但在很多情况下编码效率不是很高；费诺码和霍夫曼码的编码方法都不唯一；费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以进行进制编码，但越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码也未必能得到充分利用；香农-费诺-埃利斯码不是最佳码，但由其扩展得到的算术编码在数据压缩中得到了广泛的应用。霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码、费诺码以及香农-费诺-埃利斯码。数字序列中连续出现相同符号的一段称为游程。二元序列只有两种值，分别用“0”和“1”表示，这两种符号可连续出现，就形成了“0”游程和“1”游程。“0”游程和“1”游程总是交替出现的，连续出现的“0”符号的个数称“0”游程长度，连续出现的“1”符号的个数称“1”游程长度。这样可把二元序列变换为游程长度序列，且二者是可逆的。对于随机二元序列，各游程长度将是随机变量，其取值可为1，2，3，…，直至无穷。游程长度序列（游程序列）：用交替出现的“0”游程和“1”游程长度表示任意二元序列。游程变换：将二元序列变成为游程长度序列。4.2.5游程编码【例4-9】二元序列为000011111001111110000000111111…

对其进行游程编码。【解】该序列对应的游程序列为452676…

如果规定序列从“0”开始，那么很容易将游程序列恢复成二元序列。可见，这种变换是可逆的，是无失真的。游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如霍夫曼编码，进一步压缩信源，提高通信效率。游程序列是多元序列，如果计算出各个游程长度的概率，就可对各游程长度进行霍夫曼编码或用其他编码方法进行处理，以达到压缩编码的目的。

因此，编码方法为：测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行霍夫曼编码。算术编码原理信源符号的累积概率将区间分成许多互不重叠的小区间，每个信源符号对应一个不同的小区间，每个小区间的长度等于这个信源符号的概率，在此小区间内取一点，该点的取值可作为这个信源符号的码字。这个原理同样适用于信源序列。把信源序列的累积概率映射到区间上，使每个序列对应该区间内的一个点，这些点把区间分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配，因而达到高效编码的目的。4.2.6算术编码Lempel-Ziv算法隐含的逻辑如下：通过对由一连串0和1组成的预先串（前缀串），另加一个新的比特进行编码，对任意比特序列的压缩是可能的。然后，由原来的前缀串添加一