信息论与编码第五章

信息论与编码第五章第一页，共一百八十五页，2022年，8月28日第5章信源编码5.1数据压缩概述5.2无失真信源编码的基本原理5.3无失真信源编码方法

主要内容第二页，共一百八十五页，2022年，8月28日第二次课第三次课第四次课第三页，共一百八十五页，2022年，8月28日本次课内容:5.1数据压缩概述5.2无失真信源编码的基本概念

5.2.1信源编码器5.2.2码的类型第四页，共一百八十五页，2022年，8月28日

对于信源来说，有三个重要问题需要解决：1、如何构建描述信源的模型；2、信源输出信息量的计算，即信源熵的问题；3、如何更有效的表示信源输出问题，即信源压缩编码问题。信源编码的主要任务就是：减少冗余，提高编码效率。

第5章信源编码第五页，共一百八十五页，2022年，8月28日

信源编码的基本途径有两个：

一是使序列中各个符号尽可能地相互独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。

具体来说，就是针对信源输出符号序列的统计特性，寻找一定的办法把信源输出符号序列变换为最短的码字序列。第六页，共一百八十五页，2022年，8月28日

但在许多情况下，并不要求在信宿精确重现信源的输出，只要满足一定的重建质量要求即可，既允许信息传输中出现一定失真，这就是限失真信源编码问题。例如，在电话通信中，只要能将通话内容送达对方就可以了，对音质并无太高要求。实际通信时，信道往往存在干扰，要完全精确地重现信源输出几乎是做不到的。这就允许接收信号有一定限度的失真。这就是限失真编码问题,我们不做重点介绍。第七页，共一百八十五页，2022年，8月28日

5.1数据压缩概述

数据压缩:就是用尽可能少的比特数来表示源信号（采样和量化后数字信号），并能将其还原。压缩的任务就是保持信源信号在一个可以接受的状况前提下,把需要的比特数减到最少程度，以达到减少存储、处理和传输成本的目的。4.1数据压缩概述第八页，共一百八十五页，2022年，8月28日

信息理论认为：若信源编码的熵大于信源的实际熵，则该信源中一定存在冗余度，去掉冗余不会减少信息量，仍可原样恢复数据；但若减少了熵，数据则不能完全恢复。但在允许的范围内损失一定的熵，数据可以近似地恢复。4.1数据压缩概述第九页，共一百八十五页，2022年，8月28日常用的压缩编码方法可以分为两大类：1、无损压缩编码法，也称冗余压缩法或熵编码法及无失真编码；2、有损压缩编码法，也称为熵压缩法或限失真编码。4.1数据压缩概述第十页，共一百八十五页，2022年，8月28日

无损压缩：

是利用数据的统计冗余进行压缩，可完全回复原始数据而不引起任何失真。但压缩率是受到数据统计冗余度的理论限制，一般为2:1到5:1。特殊应用场合的图像数据(如指纹图像，医学图像等)的压缩通常采用这种压缩。由于压缩比的限制，仅使用无损压缩方法是不可能解决图像和数字视频的存储和传输的所有问题。

4.1数据压缩概述第十一页，共一百八十五页，2022年，8月28日

经常使用的无损压缩方法有：

香农Shannon编码，哈夫曼Huffman编码，游程(Run-length)编码，LZW(Lempel-Ziv-Welch)编码和算术编码等。

无损压缩优点：可以做到100％的保存、没有任何信号丢失，并且转换方便。

无损压缩不足：占用空间大、压缩比不高而且缺乏硬件支持。4.1数据压缩概述第十二页，共一百八十五页，2022年，8月28日

有损数据压缩：经过压缩、解压的数据与原始数据不同,但是非常接近的压缩方法，又称破坏型压缩，即将次要的信息数据压缩掉，牺牲一些质量来减少数据量，使压缩比提高。如，利用人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响缩小，却换来了大得多的压缩比。4.1数据压缩概述第十三页，共一百八十五页，2022年，8月28日有损压缩广泛应用于语音，图像和视频数据的压缩。

在多媒体应用中，常见的压缩方法有：PCM(脉冲编码调制)，预测编码，变换编码，插值和外推法，统计编码，矢量量化和子带编码等。混合编码是近年来广泛采用的方法。4.1数据压缩概述第十四页，共一百八十五页，2022年，8月28日

有损压缩的优点：

在有些情况下能够获得比任何已知无损方法小得多的文件大小，同时又能满足系统的需要。有损压缩的不足：会影响图像质量，尤其是在仔细观察的时候，质量下降更加明显。4.1数据压缩概述第十五页，共一百八十五页，2022年，8月28日

5.2无失真信源编码的基本概念

5.2.1信源编码器

编码的实质：是对信源的原始符号按一定的数学规则进行的一种变换，以码字代替原始信源符号，使变换后得到的码符号接近等概率分布，从而提高信息的传输有效性。4.2无失真信源编码的基本概念第十六页，共一百八十五页，2022年，8月28日4.2无失真信源编码的基本概念信源编码：从信源符号到码符号的一种映射。

信源编码器：

编码器X=｛x1，x2…xq｝S=｛s1…sq｝

C=｛W1…Wq｝定义：信源编码器的输入信源符号集,是输入消息单元也可以是未编码的信号单元.

S的元素si，i=1，2…q叫做信号单元或消息（共有q个信源符号）。编码器输出的码,W的元素Wi,i=1,2,…q叫做码字。构成码字的符号集,其元素xi一般是适合信道传输的,称为码元.第十七页，共一百八十五页，2022年，8月28日

编码器X=｛x1，x2…xq｝S=｛s1…sq｝

C=｛W1…Wq｝编码器的作用：将信源符号集中的符号sj，i=1，2…q（或者长为N的信源符号序列）变换成由基本符号xj,j=1,2…r组成的长度为Li的一一对应的输出符号序列,即

C=｛W1,W2，…Wq｝，

si(i=1,2…q),Wi=(xi1,xi2,…xiL),xik∈X,(k=1,…L)L称为码字长度或简称码长,所有这些码字的集合C称为码.可见编码就是从信源符号到码符号的一种映射,若要实现无失真编码,必须这种映射是一一对应的,可逆的。

4.2无失真信源编码的基本概念第十八页，共一百八十五页，2022年，8月28日如：二元信道基本符号集为{0,1},将信源符号s变换成由0和1符号组成的码符号序列(码元),即编码。

编码器X=｛x1=0，x2=1｝S=｛s1…sq｝

C=｛W1…Wq｝4.2无失真信源编码的基本概念第十九页，共一百八十五页，2022年，8月28日例如，下表为信源编码所使用的码表，信源输出序列的长度为L=1，信源共有4个符号，对应的概率空间为信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)111114.2无失真信源编码的基本概念第二十页，共一百八十五页，2022年，8月28日以码1为例，将信源输出的符号按照固定的规则进行变换，即信源编码器输出共有4个码字，分别为00，01，10和11，码字的长度都为2，即li=2，（i=1，2，3，4）每个码字都是由取值于码符号集合{0，1}的两位二元码组成。也就是说，该码表将信源输出的每个符号映射成二元码。4.2无失真信源编码的基本概念信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)11111第二十一页，共一百八十五页，2022年，8月28日5.2.2码的类型1.二元(代)码:

码符号集为X={0,1},所得码字都是一些二元序列,则为二元码.它是数字通信和计算机系统中最常用的一种码。2.同价(代)码:

若符号集X:{x1,x2,…,xr}中每个码符号x所占的传输时间相同,则所得的码C为同价码.一般二元码是同价码.电报中常用的摩尔斯密码是非同价码，其码符号(·)和划(－)所占的传输时间不同.4.2.2码的类型第二十二页，共一百八十五页，2022年，8月28日3.定长码(固定长度码或等长码):

若一组码中所有(码字的)码长都相等,(即Li=L(i=1,2,…,q)),则称为定长码。见书表5-1码一。4.变长码:

码中的码字长短不一.见书表5-1码二。5.非奇异码：一组码中所有的码字都不相同。即xi≠xj，wi≠wj

4.2.2码的类型信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)11111第二十三页，共一百八十五页，2022年，8月28日6.奇异码：一组码中有相同的码字，即

xi≠xj，但wi=wj。见表码1奇异，码2非奇异。4.2.2码的类型信源符号xi符号出现的概率p(xi)码1码2码3码4x11/20011x21/411101001x31/80000100001x41/8110110000001第二十四页，共一百八十五页，2022年，8月28日7.唯一可译码：若码的任意一串有限长的码符号序列,只能被唯一的译成所对应的信源符号序列,则称为唯一可译码。4.2.2码的类型第二十五页，共一百八十五页，2022年，8月28日

码1:如码符号序列为码符号序列为0010

s1s3

唯一可译码si码1码2s1000s20101s310001s411111s1s2s1s3s1是非唯一可译码

码2.0010

可能译为4.2.2码的类型第二十六页，共一百八十五页，2022年，8月28日注:

奇异码不是唯一可译码;非奇异码有唯一可译码,又有非唯一可译码。

唯一可译码又分为非即时译码和即时码.非即时译码:

接收端收到一个完整的码字后,不能立即译码,而等下一码字开始接收后才判断是否可以码.4.2.2码的类型第二十七页，共一百八十五页，2022年，8月28日表中码3是非即时码,码4是即时码.只要收到1就表示码意完整。4.2.2码的类型信源符号Xi符号出现的概率P(Xi)码1码2码3码4X11/20011X21/411101001X31/80000100001X41/8110110000001

即时码(非延长码或非续长码):

任意一个码子都不是其它码字的前缀部分.

在延长码中有的是唯一可译,有的不是.如码3是唯一可译码。

第二十八页，共一百八十五页，2022年，8月28日综上所述，码的分类有：（非延时码）4.2.2码的类型第二十九页，共一百八十五页，2022年，8月28日信源符号Xi符号出现概率P(Xi)码1码2码3码4X11/20011X21/411101001X31/80000100001X41/8110110000001表5-2不同的码字1是奇异码，码2是非奇异码。

码3是唯一可译码，码2不是唯一可译码码3是非即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码，所以码4是即时码,又称为非延长码，任意一个码字都不是其他码字的前缀部分构.第三十页，共一百八十五页，2022年，8月28日上次课的内容:第5章信源编码5.1数据压缩概述5.2无失真信源编码的基本原理5.2.1信源编码器5.2.2码的类型第三十一页，共一百八十五页，2022年，8月28日一、常用的压缩编码方法可以分为两大类：1、无损压缩编码法，也称冗余压缩法或熵编码法及无失真编码；2、有损压缩编码法，也称为熵压缩法或有失真编码。二、码的分类复习第三十二页，共一百八十五页，2022年，8月28日本次课的内容5.2.3几个基本概念5.2.4等长编码定理5.2.5变长编码定理5.3无失真信源编码方法第三十三页，共一百八十五页，2022年，8月28日1、码树：

通常情况下可以用码树来表示各个码字的构成，如果码字序列符号为m进制的，可以用m个符号的码树来构造码字，每个码树有一个树根A,树根有m个树枝，树枝的尽头称为节点,每个节点生出是树枝的数量等于码符号的数量m，从而形成m进制的码树。几个基本概念几个基本概念第三十四页，共一百八十五页，2022年，8月28日图4-3（a）二进制码树图4-3（b）图是三进制码树

A为根分为两个支，有n=3级节点，其终端结点为23=8个表示信源符号，a图为满树.

b图为非满树，是一个三进码树，有三个支，码是不定长的。码树一定是即时码，反之，任何即时码都是用码树来表示。即时码的码树可以用来译码几个基本概念第三十五页，共一百八十五页，2022年，8月28日

【例5.2-1】某地二月份天气的概率分布统计如下：雨天的概率是1/8，雪天的概率也是1/8，阴天的概率是1/4，晴天的概率是1/2。设x1表示雨天，x2表示雪天，x3表示阴天，x4表示晴天，则其离散无记忆信源的概率空间为几个基本概念第三十六页，共一百八十五页，2022年，8月28日表5-3两种信源编码方案信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/2111几个基本概念采用两种信源编码方案编成的码字如表下所示。绘出方案一和方案二的码树，试比较方案1和方案2的码字哪个有效性更好一些？第三十七页，共一百八十五页，2022年，8月28日表5-3两种信源编码方案信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/2111几个基本概念第三十八页，共一百八十五页，2022年，8月28日编码后的每个信源符号平均所需的码元（码符号）个数。单位为“码元/信源符号”。对单个信源符号进行编码，设信源为2、平均码长几个基本概念第三十九页，共一百八十五页，2022年，8月28日几个基本概念每个码字对应的码长为Ki（i＝1，2……q）该码的平均码长为（码元/信源符号）方案1的平均码长

方案2的平均码长（码元/信源符号）（码元/信源符号）信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/2111第四十页，共一百八十五页，2022年，8月28日3、信息传输率

编码后信息传输率R又称为码率，是指编码后每个码元载荷的信息量。单位为“比特/码元”或“比特/码符号”。（比特/码元）码率--平均码长H(x)—信源熵几个基本概念第四十一页，共一百八十五页，2022年，8月28日

【例4.2-1】中信源熵H(x)＝1.75比特/符号，方案1编码后每个码元载荷的平均信息量：方案2编码后每个码元载荷的平均信息量：（比特/码元）（比特/码元）由于每个二进制码元所能携带的最大信息量为1比特，所以方案2是一种最佳编码。几个基本概念信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/2111第四十二页，共一百八十五页，2022年，8月28日4、编码效率编码效率：表示编码后实际信息量和能载荷最大信息量的比值。假设码元为m进制，即可取m种可能值，则每个码元所能载荷的最大信息量为logm比特/码元。二元编码效率几个基本概念第四十三页，共一百八十五页，2022年，8月28日方案2编码后每个码元载荷的平均信息量：（比特/码元）（比特/码元）方案1编码后每个码元载荷的平均信息量：从编码效率看，方案1的编码效率为0.875，方案2的编码效率为1。所以方案2比方案1的有效性要更好一些。第四十四页，共一百八十五页，2022年，8月28日5、克劳夫特不等式用码树的概念可以推导出唯一可译码存在的充要条件，即各码字的长度Ki应符合不等式m是进制数，n是信源符号数

称之为克劳夫特(Kraft)不等式几个基本概念第四十五页，共一百八十五页，2022年，8月28日

该不等式指出了即时码的码长必须满足的条件。麦克米伦证明惟一可译码也满足此不等式；在码长选择的条件上，即时码与唯一码是一致的。克劳夫特不等式给出了m元码中，信源序列中的消息数n与码字的各个码长之间的关系。说明，若三者满足上式，至少能构成一种这样码长的即时码或惟一可译码，否则无法构造即时码或惟一可译码。几个基本概念第四十六页，共一百八十五页，2022年，8月28日【例4.2-2】设二元码树中

不存在满足这种Ki的唯一可译码。如码字为{0，10，11，110}。试将码字长度改为，则此时这样的码就存在唯一可译码，如码字为{0，10，110，111}。几个基本概念第四十七页，共一百八十五页，2022年，8月28日

010110A0101011码字为不是唯一可译码

要实行上述码必须在中间放置码字010110A01010111111这样就产生了非延长码{0，10，110，111}.几个基本概念可以用码树进行检查第四十八页，共一百八十五页，2022年，8月28日注：

码字{0，10，010，111}虽然也满足克劳夫特不等式，却它并不是唯一可译码。这是因为，克劳夫特不等式并不能作为判别一种码是否为即时码或唯一可译码的依据。例如，码组中有长度相等的两个码字，则这两个码字无论是否相同，都有可能使不等式成立，然而，当这两个码字相同时，它们一定不是唯一可译码。因此，唯一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是唯一可译码。几个基本概念第四十九页，共一百八十五页，2022年，8月28日

可以用3个二进制码元对该信源进行无失真编码.即码长为K=3码元/符号例：某信源有8种等概符号，L=1，信源序列熵达到最大值，由最大熵定理H(X)≤㏒m，Hl(X)=㏒8=3比特/符号等长编码定理第五十页，共一百八十五页，2022年，8月28日

而取2.55码元/符号,只有22.55=5.856种可能码字,还有部分符号没有对应的码字,一旦这些符号传到接收端将引起译码错误.所以定长编码一般都存在译码差错,L越大差错越小。若信源输出概率不相等，如p(x)={0.4，0.18，0.1，0.1，0.07，0.06，0.05，0.04｝则

比特/符号等长编码定理第五十一页，共一百八十五页，2022年，8月28日例：如果有四个信源符号{s1，s2，s3，s4}，采用二元编码，KL=2，则可以编成s1=00，s2=01，s3=10，s4=11。如果我们要对信源的L次扩展信源进行编码，也必须满足，两边取对数得：表示平均每个信源符号所需的码符号个数。若对信源进行等长编码，则必须满足其中，KL是码长，m是码符号集中的码元数，q信源符号个数。5.2等长码第五十二页，共一百八十五页，2022年，8月28日例：对英文电报的32个符号进行二元编码，根据上述关系：

我们继续讨论上面得例子，我们已经知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。我们可以做到让平均码长缩短，提高信息传输率5.2等长码第五十三页，共一百八十五页，2022年，8月28日我们举例说明：

设信源而其依赖关系为：5.2等长码第五十四页，共一百八十五页，2022年，8月28日若不考虑符号间的依赖关系，对此信源作二次扩展若考虑符号间的依赖关系，则

可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长，但平均每个信源符号所需码符号为5.2等长码第五十五页，共一百八十五页，2022年，8月28日

我们仍以英文电报为例，在考虑了英文字母间的相关性之后，我们对信源作L次扩展，在扩展后形成的信源（也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，我们可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。等长信源编码定理给出了进行等长信源编码所需码长的极限值。5.2等长码第五十六页，共一百八十五页，2022年，8月28日定理5.3（等长信源编码定理）一个熵为H(X)的离散无记忆信源，若对其L次扩展信源进行等长m元编码，码长为KL，对于任意大于0，只要满足则可以实现几乎无失真编码，反之，若：则不可能实现无失真编码5.4等长信源编码定理第五十七页，共一百八十五页，2022年，8月28日定理5.3的条件式可写成：左边表示长为的码符号所能载荷的最大信息量，而右边代表长为L的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码。定理5.3的条件式也可写成：令：

称之为编码信息率。可见，编码信息率大于信源的熵，才能实现无失真编码。5.4等长信源编码定理第五十八页，共一百八十五页，2022年，8月28日最佳编码效率为：为了衡量编码效果，引进称为编码效率。5.4等长信源编码定理第五十九页，共一百八十五页，2022年，8月28日ε为一正数,当σ2(X)和ε2均为定值时,只要L足够大,pe

可以小于任一正数δ.

即信源序列长度满足

时,就能达到差错率的要求。即

差错概率为

在实际情况下,要实现几乎无失真的等长编码,L需要大到难以实现的程度。

为信源序列的自信息方差等长编码定理第六十页，共一百八十五页，2022年，8月28日5.2.4等长编码定理由L个符号（消息）组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1,X2,…,Xl,…XL，可用KL个符号Y1,Y2…,Yk,…YKL

（每个符号有m种可能值）进行定长编码。对任意

，只要则当L足够大时，必可使译码差错小于δ,反之，当

时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。等长编码定理第六十一页，共一百八十五页，2022年，8月28日

码字长度

，在定长编码中是定值，是符号个数，当编码器容许的输出信息率,即每个信源符号必须输出的码长是

时，只要

，且所取的符号数足够大，此时这种编码器一定可以做到几乎无失真，即收端的译码差错概率接近于零。等长编码定理第六十二页，共一百八十五页，2022年，8月28日

则(1)式可以写为

（无失真ε=0）

左侧为KL长码字所携带的最大信息量，右侧为L长信源序列携带的信息量.

当左侧﹥右侧，编码几乎不失真当左侧=右侧，临界状态。当左侧<右侧，不能实现无失真编码等长编码定理第六十三页，共一百八十五页，2022年，8月28日例:设离散无记忆信源=求信源符号序列长

解：自信息方差

=3/4(log3/4)2+1/4(log1/4)2-(0.811)2=0.4715等长编码定理第六十四页，共一百八十五页，2022年，8月28日则：

L≥=

=1.923×107允许错误概率pe≤10-5

若对信源X采取等长二元编码,要求编码效率η=0.96

信源序列长度需长达1923万以上，才能实现给定的要求，这在实际中很难实现。编码效率定义最佳编码效率等长编码定理第六十五页，共一百八十五页，2022年，8月28日

4.2.5变长编码定理

变长编码，编码后码长K是变化的。如果概率大的符号用短码，概率小的符号用较长的码，则大量信源符号编成码后，平均每个信源符号所需的输出符号数就可以降低，就可以提高编码效率。变长编码定理第六十六页，共一百八十五页，2022年，8月28日

单个符号变长编码定理:若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度

满足下列不等式码字的平均码长不能小于极限值H(X)/logm，否则唯一可译码不存在。平均码长小于上界值时，唯一可译码肯定存在，但并不是说大于这个上界不能够成为唯一可译码，而是因为希望平均码长尽可能短。定理给出了无失真信源编码的最短平均码长，并指出这个最短的平均码长与信源熵H(X)有关。变长编码定理第六十七页，共一百八十五页，2022年，8月28日

离散平稳无记忆序列变长编码定理（香农第一定理）:对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足下列不等式其中ε为任意小正数。变长编码定理第六十八页，共一百八十五页，2022年，8月28日要实现无失真的信源编码，采用m元码进行编码时，每个信源符号的平均码长的极限值就是原始信源的熵值。当编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码时必然带来失真或差错。同时还表明通过对扩展信源进行变长编码，当L→∞时，平均码长可以达到这个极限值。

变长编码定理第六十九页，共一百八十五页，2022年，8月28日已知平均输出信息率：

设用m进制码元作变长编码，序列长度为L个信源符号，则上个定理，可以得到平均码长

满足下列不等式两个定理关系：变长编码定理第七十页，共一百八十五页，2022年，8月28日化简有：则

变长编码定理当L足够大时,可使

,则上式可写为:第七十一页，共一百八十五页，2022年，8月28日

用变长编码来达到相当高的编码效率,一般所要求的符号长度可以比定长编码小得多,由前式得编码效率的下界：变长编码定理第七十二页，共一百八十五页，2022年，8月28日

如上次的例子:m=2,logm=1,H(x)=0.811比特/符号要求编码效率η=0.96定长编码符号序列长为：

L=1.923×107变长编码定理第七十三页，共一百八十五页，2022年，8月28日

编码效率总是小于1,用此衡量各种编码方法的优劣,为了衡量各种编码方法与最佳码的差距,定义码的剩余度为:变长编码定理第七十四页，共一百八十五页，2022年，8月28日

例

设离散无记忆信源的概率空间为

求:用二元码符号(0,1)来构成一个即时码时的信息传输率。变长编码定理第七十五页，共一百八十五页，2022年，8月28日

信源熵为H(X)=解：=0.81比特/符号用二进制符号(0,1)来构成一个即时码，

x10,x21平均码长：变长编码定理第七十六页，共一百八十五页，2022年，8月28日信息传输率为：

根据香农第一定理可对信源X的二次扩展信源X2进行编码,即L=2的信源进行变长编码,即时码表如表：编码效率为：1111/16X2X21103/16X2X1103/16X1X209/16X1X1即时码序列概率序列变长编码定理第七十七页，共一百八十五页，2022年，8月28日码的平均长度：信源中每一个单个符号的平均码长：信息传输率:编码效率：1111/16X2X21103/16X2X1103/16X1X209/16X1X1即时码序列概率序列变长编码定理第七十八页，共一百八十五页，2022年，8月28日

由此可见编码效率越复杂,传输率越高.

若用定长,当编码效率η=96%,编码错误概率δ≤105,则信源序列长度

L＞4.13×107用同样的方法进行三次，四次信源扩展即

L=3，L=4，得η3=0.985=R3η4=0.991=R4η1=0.81=R1η2=0.962变长编码定理第七十九页，共一百八十五页，2022年，8月28日

2.变长码,L不需太长,则可达到相当高的编码效率,且可以实现无失真编码,随着L增加,η

越接近1,编码后的信息传输率R也越来越接近无噪无损二元对称信道的容量,使信道得到充分的利用。1.定长码需要信源序列长,且总存在译码差错。结论：变长编码定理第八十页，共一百八十五页，2022年，8月28日4.3无失真信源编码方法4.3.1香农编码香农编码方法又称最佳变长编码方法。最佳变长编码:

能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合。对于某一信源和某一码元集来说，如果有一个唯一可译码的平均码长不大于其他的唯一可译码的平均码长，则称此码为最佳码或称为紧致码。香农编码第八十一页，共一百八十五页，2022年，8月28日

最佳码两个特点：1、概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；2、对于二元最佳码，所对应的缩减信源的两个最小概率的信源符号所对应的码字具有相同的码长，且总是最后一位不同，保证是即时码。

最佳变长编码的方法主要有：

香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。香农编码第八十二页，共一百八十五页，2022年，8月28日设离散无记忆信源：二进制香农编码步骤如下：香农编码第八十三页，共一百八十五页，2022年，8月28日1.将信源符号按概率从大到小的顺序排列

p(x1)≥p(x2)≥p(xn)2.确定下列不等式的整数码长Ki-logp(xi)≤Ki＜-logp(Xi)+13.令P(x0)=0,为编成唯一可译码,计算第i个信息的累加概率4.将累加概率pi变成二进制数;5.取pi二进制数的小数点后Ki位即为该消息的二进制码字。香农编码第八十四页，共一百八十五页，2022年，8月28日【例4.3-1】设信源共7个符号消息,其数学模型如下

香农编码第八十五页，共一百八十五页，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x42.480.18x32.410.19x22.340.2x1码字码字长度Ki-logp(xi)累加概率符号概率p(xi)信源消息符号xi香农编码过程如下：1.p(xi)排队，

-logp(xi)≤Ki

＜-logp(Xi)+12.确定下列不等式的整数码长KiiP3333347香农编码第八十六页，共一百八十五页，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1码字码字长度Ki-logp(xi)累加概率符号概率p(xi)信源消息符号xi33347

300.390.570.740.890.990.23.累加概率香农编码第八十七页，共一百八十五页，2022年，8月28日4,将pi

变成二进制数，以x3

为例∵K3取3,故码字为0110.39×2=0.78…00.78×2=1.56…10.56×2=1.12…10.12×2=0.24…001106.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1码字码字长度Ki-logp(xi)累加概率符号概率p(xi)信源消息符号xi33347

300.390.570.740.890.990.211111101110101000001011100共有5个三位代码组,各代码组之间至少有一个数不同是唯一可译码，可看出这七个代码组都不是延长码,均属于即时码。∵L=1，

m=2该编码的平均码长为：∑p(xi)Ki=(0.2+0.19+0.18+0.17+0.15)×3+0.1×4+0.01×7=0.89×3+0.4+0.07=3.14码元/符号香农编码第八十八页，共一百八十五页，2022年，8月28日平均信息速率：=-[0.2log0.2+0.19log0.19+0.18log0.18+0.17log0.17+0.15log0.15+0.1log0.1+0.01log0.01］/3.14=0.813比特/码元=2.61/3.14香农编码第八十九页，共一百八十五页，2022年，8月28日编码效率:

上述信源若采用定长编码，要做到无失真译码，每个符号至少要用三个比特来表示，比较起来香农编码无疑对信源进行了压缩，但编码效率并不是很高。香农编码第九十页，共一百八十五页，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1码字码字长度Ki-logp(xi)累加概率符号概率p(x)信源消息符号xi33347

300.390.570.740.890.990.2练习画树:11101010000010111001111110练习题第九十一页，共一百八十五页，2022年，8月28日上次课的内容4.2.3几个基本概念4.2.4等长编码定理4.2.5变长编码定理4.3无失真信源编码方法4.3.1香农编码方法第九十二页，共一百八十五页，2022年，8月28日2、在定长编码中，码长K是定值3、编码效率：表示编码后实际信息量和能载荷最大信息量的比值复习1、最佳变长编码:能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合。二元编码效率信息传输率第九十三页，共一百八十五页，2022年，8月28日4、码树:码树有一个树根A,树根有m个树枝，树枝的尽头称为节点,每个节点生出是树枝的数量等于码符号的数量m，从而形成m进制的码树。5、平均码长:

编码后的每个信源符号平均所需的码元（码符号）个数。第九十四页，共一百八十五页，2022年，8月28日(1)要求信源符号Xi,与码字Yi一一对应;(2)与码字组成的码符号序列的逆变换也是唯一的

(能被唯一的译成所对应的信源符号序列).6、要想实现无失真编码:

用定长编码若想实现无失真编码,L需足够长,不容易实现,现讨论变长码,寻求是小的K值。第九十五页，共一百八十五页，2022年，8月28日1.将信源符号按概率从大到小的顺序排列

p(x1)≥p(x2)≥p(xn)2.确定下列不等式的整数码长Ki-logp(xi)≤Ki＜-logp(Xi)+13.令P(x0)=0,为编成唯一可译码,计算第i个信息的累加概率4.将累加概率pi变成二进制数;5.取pi二进制数的小数点后Ki位即为该消息的二进制码字。7、香农编码步骤第九十六页，共一百八十五页，2022年，8月28日本次课内容4.3.2费诺编码方法4.3.3哈夫曼编码方法4.3.4游程(Run-length)编码第九十七页，共一百八十五页，2022年，8月28日编码步骤:

1.

将信源消息符号按其出现概率大小依次排列：

p(x1)≥p(x2)….p(xn)。

2.将依次排列的信源符号按概率值分两大组,并对各组赋予一个二进制元码0、1。4.3.2费诺编码

费诺（Fano）编码（简称费诺码）属于概率匹配编码.不是最佳编码。

3.将每一大组的信源符号进一步分组,使划分后的两组概率和近于相同并又赋两组0,1。

4.如此重复,至两组只剩下一个信源符号为止。

5.信源符号所对应的码字即为费诺码.4.3.2费诺编码第九十八页，共一百八十五页，2022年，8月28日4.3.2费诺编码41111

10.01x741110

0

10.1x63110

0

10.15x5210

0

10.17x43011

10.18x33010

0

10.19x2200

000.2x1码长Ki二元码第五次分组第四次分组第三次分组第二次分组第一次分组各消息概率信源符号xi平均码长：=(0.2+0.17)×2+(0.19+0.18+0.15)×3(0.1+0.01)×4=0.74+1.56+0.44=2.94码元/符号费诺码编码过程如下：第九十九页，共一百八十五页，2022年，8月28日信息传输率：编码效率：η

=95.3%费诺编码比香农码平均码长短,R大,效率高。4.3.2费诺编码第一百页，共一百八十五页，2022年，8月28日4.3.2费诺编码41111

10.01x741110

0

10.1x63110

0

10.15x5210

0

10.17x43011

10.18x33010

0

10.19x2200

000.2x1码长Ki二元码第五次分组第四次分组第三次分组第二次分组第一次分组各消息概率信源符号xi码树：A010101011100000100111101011101111第一百零一页，共一百八十五页，2022年，8月28日香农编码和费诺编码.在R、ŋ方面,费诺编码强于香农编码。香农编码：ŋ=0.813费诺编码：ŋ=0.953

4.3.2费诺编码第一百零二页，共一百八十五页，2022年，8月28日4.3.3哈夫曼编码一、编码方法1952年，哈夫曼提出了一种构造最佳码的方法。所得的码字是即时码，而且在所有唯一可译码中，它的平均码长最短，是一种最佳变长码。哈夫曼（Huffman）编码方法的编码步骤：哈夫曼编码第一百零三页，共一百八十五页，2022年，8月28日

(1)将n个信源消息符号按其出现的概率大小依次排列,p(x1)≥p(x2)≥…≥p(xn)

(2)取两个概率最小的字母分别配以0和1两码元,

并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。(3)重复步骤(2)的过程,直到最后两个符号配以0

和1为止;(4)从最后一级开始,向前返回得到各个信源符号所对应的码元序列。哈夫曼编码第一百零四页，共一百八十五页，2022年，8月28日【例4.3-3】设信源共7个符号消息,其数学模型如下

哈夫曼编码第一百零五页，共一百八十五页，2022年，8月28日0.110.200.190.180.170.15010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.39哈夫曼编码第一百零六页，共一百八十五页，2022年，8月28日101100000101001100111该哈夫曼码的平均码长为：信息传输速率：香农编码：ŋ=0.813费诺编码：ŋ=0.953

由此可见,哈夫曼码的平均码长最小,消息传输速率最大,编码效率最高。哈夫曼编码第一百零七页，共一百八十五页，2022年，8月28日

1、每次对信源缩减时,赋予信源最后两个概率最小的符号,用0和1是可以任意的,所以可以得到不同的哈夫曼码,但不会影响码长。

2、对信源进行缩减时,两个概率最小的符号合并后的概率与其它信源符号的概率相同时,这两者在缩减信源中进行概率排序,其位置放置次序是可以任意的,故会得到不同的哈夫曼码.注:此码并非是唯一的.

原因是：

2点,将影响码字的长度,一般将合并的概率放在上面,这样可获得较小的码方差。101100000101001100111第一百零八页，共一百八十五页，2022年，8月28日哈夫曼编码【例4.3-4】设有离散无记忆信源

用两种方法编写哈夫曼编码10

0.20.40.20.2010.40.40.20.60.41A1010110000011000100011哈夫曼树：第一百零九页，共一百八十五页，2022年，8月28日哈夫曼编码哈夫曼树：A01000010111100101011第一百一十页，共一百八十五页，2022年，8月28日哈夫曼树：哈夫曼编码第一百一十一页，共一百八十五页，2022年，8月28日由计算可得方法1、方法2的平均码长相等编码效率均为但两种码的质量不完全相同哈夫曼编码第一百一十二页，共一百八十五页，2022年，8月28日

第二种方差小些。即：将新合并的等概率消息排列到上支路，将有利于缩短码长的方差，即编出的码更接近于等长码。所以说第二种码的质量优于第一种码的质量。用码差表示:方法1:方法2:哈夫曼编码第一百一十三页，共一百八十五页，2022年，8月28日上面讨论了哈夫曼编码的方法和一些性质，在实际问题中真正应用哈夫曼编码方法时，还需进一步研究有关误差扩散，速率匹配和概率匹配等问题。二、工程上注意的三个问题哈夫曼编码第一百一十四页，共一百八十五页，2022年，8月28日

哈夫曼码是一类无失真信源最佳变长码,在研究这类无失真信源编码时认为信道传输是理想的,是不产生误差的,然而实际信道中总是存在噪声,噪声引入必将要破坏变长码的结构,同时变长码是不加同步的码,无法自动清洗所产生的影响,所以必然要产生误差的扩散,就是说噪声所影响的不仅是被干扰的码元,而是一直扩散下去,影响后面一系列码元,以至在低信噪比下无法正常工作。1、误差扩散哈夫曼编码第一百一十五页，共一百八十五页，2022年，8月28日

目前对这类误差扩散还没有特别有效的克服方法.在工程上,一般哈夫曼码能适合于高信噪比的优质信道,如误码率﹤10-6.同时工程上还常常采用定期清洗方法,比如在文件和报纸传真中采用按行清洗的方式,以牺牲编码效率来达到限制误差扩散的目的.另一种方法是加检错纠错码。哈夫曼编码第一百一十六页，共一百八十五页，2022年，8月28日

由于绝大多数信源其消息是不等概率的，因而编成的变长码长度也是不相等的,这必然导致信源输出速率的变化,而在实际信道中传送的信息率是固定不变的,就是说信源给出的是变速的,而信道传送则是恒速的,因而信源与信道之间必然存在一个速率匹配问题。2、速率匹配哈夫曼编码第一百一十七页，共一百八十五页，2022年，8月28日在工程上一般采用缓冲存储器方法，这个缓冲器起到类似水库的作用，变速输入，恒速输出，缓冲器容量的选择与信源统计特性，编码方法，输出速率相关，容量大浪费设备，小达不到效果。经概率运算得存储器容量

N表示在T秒内N个信源符号输出,σ为单符号方差。哈夫曼编码第一百一十八页，共一百八十五页，2022年，8月28日

变长码本身就是与信源统计特性相匹配的无失真信源编码,因此信源统计特性的变化对变长码影响很大,主要体现在：

3、信源统计特性匹配

(1)与信源消息种类多少的关系;一般变长码更适合于大的消息集,而不适合小且概率分布相差很大的集合。（2）变长码是在信源概率特性已知的情况下实现统计匹配的。哈夫曼编码第一百一十九页，共一百八十五页，2022年，8月28日

下面,进一步研究小消息集合如何实现统计匹配的变长码.

基本思想是扩张信源,以实现统计匹配。哈夫曼编码第一百二十页，共一百八十五页，2022年，8月28日从简单的例子入手：平均码长：信源消息概率编码s1P(s1)=2/30s2P(s2)=1/31【例4.3-5】信源消息熵：哈夫曼编码第一百二十一页，共一百八十五页，2022年，8月28日编码效率：

对上述信源进行二次扩展,即每次取两个消息,可组成新的联合信源。哈夫曼编码第一百二十二页，共一百八十五页，2022年，8月28日信源概率编码码字码长

s1s1

11

s1s2012

s2s10003

s2s200130110013/92/94/95/94/91对上述信源进行二次扩展,即每次取两个消息,组成联合信源哈夫曼编码第一百二十三页，共一百八十五页，2022年，8月28日

码字码长

11

01200030013哈夫曼编码第一百二十四页，共一百八十五页，2022年，8月28日进行三次扩展：信源消息概率编码Kis1s1s1012s1s1s20003s1s2s10013s1s2s21003s2s1s11103s2s1s21113s2s2s110104s2s2s210114哈夫曼编码第一百二十五页，共一百八十五页，2022年，8月28日哈夫曼编码第一百二十六页，共一百八十五页，2022年，8月28日

还可以一直扩展下去,以不断扩大信源消息集,以达到逐步实现完全统计匹配的目的,但扩展阶数越高,设备越复杂,所以在工程上只能在效率和复杂性方面作一折中。哈夫曼编码第一百二十七页，共一百八十五页，2022年，8月28日

前面介绍的均为二进制哈夫曼码,很容易推广到m进制的情况,只是编码过程中过程缩减信源时,每次都是将m个概率最小的符号合并,并分别用０、１、…m-1码符号表示,为了充分利用短码,使哈夫曼的平均码长最短,必须使最后一个缩减源有m个信源符号.三、m进制哈夫曼码哈夫曼编码第一百二十八页，共一百八十五页，2022年，8月28日故对m元哈夫曼编码信源Ｓ符号个数q必须满足q=(m-1)θ+m,θ表示信源缩减的次数,如m＝２的二元码,信源Ｓ的符号个数q必须满足

q=θ+2若不满足,用虚设方法,增补一些概率为信源符号满足上式,这样得到的m元哈夫曼码一定是紧致码。哈夫曼编码第一百二十九页，共一百八十五页，2022年，8月28日设离散无记忆信源码符号集X=(0、1、2)【例4.3-6】设无记忆信源试构造一种三进制哈夫曼码信源,哈夫曼编码第一百三十页，共一百八十五页，2022年，8月28日0S930110.05S830100.05S72220.05S62210.05S52200.1S42020.1S32000.2S2110.4S1KiWi编码过程P(si)信源符号0.20.10.10.10.050.050

120

120.40.20.20.10.10.40.40.20120121.0S9是增补,令其概率为0,0.4q=(m-1)θ+m平均码长：哈夫曼编码第一百三十一页，共一百八十五页，2022年，8月28日0S930110.05S830100.05S72220.05S62210.05S52200.1S42020.1S32000.2S2110.4S1KiWi编码过程P(si)信源符号0.20.10.10.10.050.050

120

120.40.20.20.10.10.40.40.20120121.00.4q=(m-1)θ+mA01201201200010011120022122码树:哈夫曼编码第一百三十二页，共一百八十五页，2022年，8月28日注:编码效率、编码信息率、编码后信息传输率之间关系编码信息率(信源符号的平均码长)：编码效率：编码后信息传输率：码字平均长二进制单个符号时L信源符号长度三进制单个符号时第一百三十三页，共一百八十五页，2022年，8月28日4.4常用信源编码方法简介指数学序列中连续出现相同符号的一段．游程编码游程码：

在二元序列中,只有两种符号,即“0”和“1”,这些符号可连续出现,连“0”这一段称为“0”游程,连“1”这一段称为“1”游程.它们的长度分别称为游程长度L(0)和L(1).“0”游程和“1”游程是总是交替出现的,如规定某二元序列是从“０”开始,第一个游程是“0”第二个是“1”第三个是“0”等等,对于随机二元序列,各游程长度是随机变量.取值为……无限,将二元序列换成游程长度序列.这种编码是一一对应的,是可逆的．游程编码第一百三十四页，共一百八十五页，2022年，8月28日例:０００１０００１１１０１１１１１００００３若二元序列是从“０”起始,上面的游程序列很容易恢复成原来的二元序列.游程编码仍是变长码,游程长度越长,概率越小．

缺点：需大量的缓冲和优质的信道，只适用于二元序列，对于多元信源,一般不能直接利用游程编码133154游程编码第一百三十五页，共一百八十五页，2022年，8月28日4-1以下以码字集合的形式给出5种不同的编码，第一个码的符号集合为{a,b,c},其他4个码都是二进制码。{aa,ac,b,cc,abc}{000,10,00,11}{100,101,0,11}{01,100,011,00,111,1010,1011,1101}{01,111,011,00,010,110}对于上面列出的5种编码，分别回答下述问题：⑴此码的平均码长是多少？⑵画出此码的树图，并判断此码是否是即时码？⑶此码的码长分布是否满足克劳夫特不等式，并判断此码是否是唯一可译码？练习题第一百三十六页，共一百八十五页，2022年，8月28日4-5某信源有8个符号，概率分别为1/2,1/4,1/8,1/16,1/32,1/64,1/128,1/128，编成这样的码：000，001，010，011，100，101，110，111.计算：⑴信源的符号熵H（S）；⑵出现一个“1”或“0”的概率；⑶这种码的编码效率；⑷相应的香农码和费诺码；⑸相应的香农码和费诺码的编码效率。练习题第一百三十七页，共一百八十五页，2022年，8月28日上次课内容4.3.2费诺编码方法4.3.3哈夫曼编码方法4.3.4游程(Run-length)编码第一百三十八页，共一百八十五页，2022年，8月28日编码步骤:

1.

将信源消息符号按其出现概率大小依次排列：

p(x1)≥p(x2)….p(xn)。

2.将依次排列的信源符号按概率植分两大组,并对各组赋予一个二进制元码0、1。一、费诺（Fano）编码（简称费诺码）属于概率匹配编码.不是最佳编码

3.将每一大组的信源符号进一步分组,使划分后的两组概率和近于相同并又赋两组0,1。

4.如此重复,至两组只剩下一个信源符号为止。

5.信源符号所对应的码字即为费诺码.复习第一百三十九页，共一百八十五页，2022年，8月28日

(1)将n个信源消息符号按其出现的概率大小依次排列,p(x1)≥p(x2)≥…≥p(xn)

(2)取两个概率最小的字母分别配以0和1两码元,

并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。(3)重复步骤(2)的过程,直到最后两个符号配以0

和1为止;(4)从最后一级开始,向前返回得到各个信源符号所对应的码元序列。二、哈夫曼编码步骤复习第一百四十页，共一百八十五页，2022年，8月28日三、工程上注意的三个问题1、误差扩散2、速率匹配3、信源统计特性匹配四、游程码：指数学序列中连续出现相同符号的一段。复习第一百四十一页，共一百八十五页，2022年，8月28日

本次课内容4.3.5算术编码4.4*限失真信源编码定理4.5*限失真信源编码方法第一百四十二页，共一百八十五页，2022年，8月28日4.3.5算术编码

算术编码不同于哈夫曼码,是非分组码,是运用复杂模型来使得优良的压缩性成为可能的一种压缩技术,在某种意义上讲算术编码是最优编码,但算术编码掌握有些困难,但目前发展很快,工程应用较多.4.3.5算术编码第一百四十三页，共一百八十五页，2022年，8月28日

既，从全序列出发,将各信源序列的概率映射到[0,1]区间上,使每个序列对应这区间内的一点,也就是一