《信息论-基础理论与应用：第八章 无失真的信源编码》由会员分享，可在线阅读，更多相关《信息论-基础理论与应用：第八章 无失真的信源编码（48页珍藏版）》请在金锄头文库上搜索。
1、1第二节第二节 霍夫曼编码霍夫曼编码第第一一节节 费诺编码费诺编码第三节第三节 游程编码游程编码第八章第八章 无失真的信源编码无失真的信源编码2信源编码概述信源编码概述o信源编码理论是信息论的一个重要分支，其理信源编码理论是信息论的一个重要分支，其理 论基础是信源编码的两个定理。论基础是信源编码的两个定理。n无失真信源编码无失真信源编码：针对离散信源或数字信号：针对离散信源或数字信号n限失真信源编码限失真信源编码：适用于波形信源或波形信号（模：适用于波形信源或波形信号（模拟信号）。拟信号）。信源编码的分类：离散信源编码、连续信源编码和相信源编码的分类：离散信源编码、连续信源编码和相关信源编码三
2、类。关信源编码三类。n离散信源编码离散信源编码：独立信源编码，可做到无失真编：独立信源编码，可做到无失真编码；码；n连续信源编码连续信源编码：独立信源编码，只能做到限失真：独立信源编码，只能做到限失真信源编码；信源编码；n相关信源编码相关信源编码：非独立信源编码。：非独立信源编码。3o有些编码原理和技术在通信原理和信号处理等相有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：关课程中已经介绍过。例如：n连续信源编码：脉冲编码调制连续信源编码：脉冲编码调制(PCM)(PCM)、矢量量化、矢量量化技术；技术；n相关信源编码：相关信源编码：o预测编码预测编码：增量编码、差分脉冲调制
3、：增量编码、差分脉冲调制(DPCM)(DPCM)、自适应差分脉冲调制自适应差分脉冲调制(ADPCM)(ADPCM)、线性预测声码、线性预测声码器；器；o变换编码变换编码：K KL L变换、离散变换、子带编码、变换、离散变换、子带编码、小波变换。小波变换。4定理定理5.8 5.8 无失真变长信源编码定理（香农第一定理）无失真变长信源编码定理（香农第一定理）离散无记忆信源离散无记忆信源S的的N次扩展信源次扩展信源 ，其熵为，其熵为 ，并且编，并且编码器的码元符号集为码器的码元符号集为A： 对信源对信源 进行编码，总进行编码，总可以找到一种编码方法，构成唯一可译码，使信源可以找到一种编码方法，构成唯
4、一可译码，使信源S中每个符中每个符号所需要的平均码长满足号所需要的平均码长满足 当 则得：回顾香农第一定理回顾香农第一定理5 这个定理是香农信息论中非常重要的一个定理，这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，个值，则唯一可译码不存在，可见，熵是无失真信熵是无失真信源编码的极限值源编码的极限值。定理还指出，通过对扩展信源进。定理还指出，通过对扩展信源进行编码，当行编码，当N N趋向于无穷时
5、，平均码长可以趋近该趋向于无穷时，平均码长可以趋近该极限值。极限值。 6第一节第一节 费诺编码费诺编码 费诺编码也是一种常见的信源编码方法。编码步骤费诺编码也是一种常见的信源编码方法。编码步骤如下：如下：o将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令p p( (x x1 1) ) p p( (x x2 2) p p( (x xq q) )o按编码进制数将概率分组，使每组概率和尽可能按编码进制数将概率分组，使每组概率和尽可能接近或相等。如编二进制码就分成两组，编接近或相等。如编二进制码就分成两组，编r r进进制码就分成制码就分成r r组。组。o给每一组分配一位码元。给每一组分配一
6、位码元。o将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2 2和和3 3，直至概率不再可分为止。直至概率不再可分为止。7 例例 设有一单符号离散信源设有一单符号离散信源o对该信源编二进制费诺码。编码过程如下表。对该信源编二进制费诺码。编码过程如下表。表5.3.1 二进制费诺编码信源符号信源符号概率概率编码编码码字码字码长码长x10.2500002x20.251012x30.2010102x40.15101103x50.101011104x60.051111148o上述码字还可用码树来表示，如图下所示。9o该信源的熵为该信源的熵为o平均码长为平均码长为o编码效率为编码效
7、率为o本例中费诺编码有较高的编码效率。费诺码比较适合本例中费诺编码有较高的编码效率。费诺码比较适合于于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组分组概率都相等概率都相等的信源进行编码时，可达到理想的编码效的信源进行编码时，可达到理想的编码效率。率。10 例例 有一单符号离散无记忆信源有一单符号离散无记忆信源o对该信源编二进制费诺码，编码过程如表。对该信源编二进制费诺码，编码过程如表。11o码树图如图。码树图如图。o信源熵为信源熵为 H H( (X X)=2.75()=2.75(比特比特/ /符号符号) )o平均码长为平均码长为o编码效率为编码效率为=1
8、=1。之所以如此，因为每次所分两组的概率恰好。之所以如此，因为每次所分两组的概率恰好相等。相等。12第二节第二节 霍夫曼编码霍夫曼编码 霍夫曼霍夫曼(Huffman)编码是一种效率比较高的变长编码是一种效率比较高的变长无失真信源编码方法。无失真信源编码方法。o编码步骤编码步骤o二进制霍夫曼编码二进制霍夫曼编码or进制霍夫曼编码进制霍夫曼编码13o将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xq)o给两个概率最小的信源符号给两个概率最小的信源符号p(xn-1)和和p(xn)各分配一个码位各分配一个码位“0”和和“1”，将这两个信源符号合
9、并成一个新符号，并用，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只这两个最小的概率之和作为新符号的概率，结果得到一个只包含包含(q1)个信源符号的新信源。称为个信源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用用S1表示。表示。o将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤2，得到只含，得到只含(q2)个符号的缩减信源个符号的缩减信源S2。o重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为两个符号
10、的概率之和必为1。然后从最后一级缩减信源开始，。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。依编码路径向前返回，就得到各信源符号所对应的码字。14例例 设单符号离散无记忆信源如下，要求对信源编二进制设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。霍夫曼码。编码过程如下图（后页）。n在图中读取码字的时候，一定要从后向前读，此时编出在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。则码字不可分离。1516o将上图左右颠
11、倒过来重画一下，即可得到二进制哈夫将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。曼码的码树。17o信源熵为：信源熵为：o平均码长为平均码长为o编码效率为编码效率为o若采用定长编码，码长若采用定长编码，码长L=3，则编码效率，则编码效率o可见哈夫曼的编码效率提高了可见哈夫曼的编码效率提高了12.7%。18注意：注意：哈夫曼的编法并不惟一哈夫曼的编法并不惟一。o每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0 0”和和“1 1”码元是任意的，所以可得到不同的码字。只码元是任意的，所以可得到不同的码字。只要要在各次缩减信源中保持码元分配的一致性在各次缩减信源中
12、保持码元分配的一致性，即即能得到可分离码字。能得到可分离码字。o不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长L Li i不变，平均码长也不变，所以没有本质区别；不变，平均码长也不变，所以没有本质区别；o缩减信源时，若合并后的新符号概率与其他符号缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，概率相等，从编码方法上来说，这几个符号的次这几个符号的次序可任意排列，编出的码都是正确的，但得到的序可任意排列，编出的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到的不同的编法得到的码字长度码字长度L Li i也不也不尽相同尽相同。1
13、9例例 设有离散无记忆信源设有离散无记忆信源用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanhuffman码码20方法一方法一方法二方法二21 22信源符号信源符号xi概率概率p(xi) 码字码字Wi1码长码长Li1码字码字Wi2码长码长Li2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比23两种编码的平均码长是一样的，都是两种编码的平均码长是一样的，都是2.2，那一种更好呢，那一种更好呢，我们可以计算一下平均码长的方
14、差。我们可以计算一下平均码长的方差。定义码字长度的方差定义码字长度的方差2：24n可见：第二种编码方法的码长方差要小许多。意味着第可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。二种编码方法的码长变化较小，比较接近于平均码长。l第一种方法编出的第一种方法编出的5 5个码字有个码字有4 4种不同的码长；种不同的码长；l第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长；l显然，显然，第二种编码方法更简单、更容易实现，所以第二种编码方法更简单、更容易实现，所以更好更好。结论：结论：在哈夫曼编码过程中，对缩减信源符号按概率由
15、大在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应到小的顺序重新排列时，应使合并后的新符号尽可能排使合并后的新符号尽可能排在靠前的位置在靠前的位置，这样可使合并后的新符号重复编码次数，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。减少，使短码得到充分利用。25“全树全树”概念概念o定义：码树图中每个中间节点后续的枝数为定义：码树图中每个中间节点后续的枝数为r时称为时称为全树全树；若有些节点的后续枝数不足若有些节点的后续枝数不足r，就称为，就称为非全树非全树。o二进制码不存在非全树的情况，因为后续枝数是二进制码不存在非全树的情况，因为后续枝数是1时，这个时，这个
16、枝就可以去掉使码字长度缩短。枝就可以去掉使码字长度缩短。o对对r进制编码：若所有码字构成全树，可分离的码字数（信进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为源个数）必为 r+k(r1)。k为信源缩减次数。为信源缩减次数。o若信源所含的符号数若信源所含的符号数q不能构成不能构成r进制全树，必须增加进制全树，必须增加s个不个不用的码字形成全树。用的码字形成全树。26o在编在编r进制哈夫曼码时为了使平均码长最短，必须使最进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有后一步缩减信源有r个信源符号。非全树时，有个信源符号。非全树时，有s个码字个码字不用不用.n第一次对最小概率
17、符号分配码元时就只取第一次对最小概率符号分配码元时就只取(rs)个，个，分别配以分别配以0,1,rs1，把这些符号的概率相加作为，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。一个新符号的概率，与其它符号一起重新排列。n以后每次就可以取以后每次就可以取r个符号，分别配以个符号，分别配以0,1,r1；如此下去，直至所有概率相加得；如此下去，直至所有概率相加得1为止，即得到各为止，即得到各符号的符号的r进制码字。进制码字。27例：对如下单符号离散无记忆信源编三进制哈夫曼码。例：对如下单符号离散无记忆信源编三进制哈夫曼码。这里：这里：r=3，q=8o令令k=3，r+k(r1)=9
18、，则，则 s=9q=98=1o所以第一次取所以第一次取rs=2个符号进行编码。个符号进行编码。282930o平均码长为平均码长为o信息率为信息率为o编码效率为编码效率为o可见：哈夫曼的编码效率相当高，对编码器的要求可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。也简单得多。31(3) (3) 结论结论o费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；而实现了对信源的压缩；o费诺码和哈夫曼码的编码方法都不惟一；费诺码
19、和哈夫曼码的编码方法都不惟一；o费诺码比较适合于对分组概率相等或接近的信源编码，费费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编诺码也可以编r r进制码，但进制码，但r r越大，信源的符号数越多，可越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；能得到充分利用；o哈夫曼码对信源的统计特性没有特殊要求，编码效率比较哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于费高，对编码设备的要求也比较简单，因此综合性能优于费诺码诺码。32实际使用中注
20、意的问题实际使用中注意的问题o误差扩散问题：误差扩散问题： 实际信道中有噪声存在，必然要破坏变长码的实际信道中有噪声存在，必然要破坏变长码的结构。同时由于变长码是不加同步的码，无法自结构。同时由于变长码是不加同步的码，无法自动清洗产生的错误使得产生的错误扩散。动清洗产生的错误使得产生的错误扩散。 在工程上哈夫曼码只能适合于高信噪比的优在工程上哈夫曼码只能适合于高信噪比的优质信道，如：误码率低于质信道，如：误码率低于1010-6-6以下。以下。 工程上还常常采用定期清洗的方法，如在文件工程上还常常采用定期清洗的方法，如在文件或报纸中采用按行清洗的方式，以牺牲编码效率或报纸中采用按行清洗的方式，以
21、牺牲编码效率达到限制误差扩散的目的。达到限制误差扩散的目的。33o速率匹配问题速率匹配问题 由于信源消息是不等概率的，因而编成的变长由于信源消息是不等概率的，因而编成的变长码长度也是不相同的，这必然导致信源输出速率是码长度也是不相同的，这必然导致信源输出速率是变化的，然而在实际信道中传送的信息率是变化的，然而在实际信道中传送的信息率是固定不固定不变化变化的。的。 一般在工程中采用缓冲存储器的方法，变速输一般在工程中采用缓冲存储器的方法，变速输入恒速输出，存储器容量的选取与信源统计特性和入恒速输出，存储器容量的选取与信源统计特性和编码方法，以及输出速率密切相关。容量选大了浪编码方法，以及输出速率
22、密切相关。容量选大了浪费设备，容量小了会产生溢出或取空现象。费设备，容量小了会产生溢出或取空现象。实际使用中注意的问题34o与信源统计特性相匹配的问题与信源统计特性相匹配的问题 一般变长码更适合于大的消息集，而不大一般变长码更适合于大的消息集，而不大适合消息集小且概率分布相差很大的集合。小适合消息集小且概率分布相差很大的集合。小集合只有在很特殊情况下才能实现统计匹配。集合只有在很特殊情况下才能实现统计匹配。 如果信源的统计特性不完全知道，则无如果信源的统计特性不完全知道，则无法实现变长编码。法实现变长编码。实际使用中注意的问题35第三节第三节 游程编码游程编码一一. .游程编码对象和性质游程编
23、码对象和性质二二. . 游程编码的定义游程编码的定义三三. . 二元独立序列二元独立序列四四. . 游程编码的效率游程编码的效率五五. . 长码的截断处理方法长码的截断处理方法36一一. . 游程编码对象和性质游程编码对象和性质o费诺编码、哈夫曼编码主要是针对无记忆信源。当信费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；源有记忆时上述编码效率不高；o游程编码对游程编码对相关信源相关信源编码更有效；编码更有效；o费诺编码、哈夫曼编码属于费诺编码、哈夫曼编码属于无失真信源编码无失真信源编码；o游程编码属于游程编码属于限失真信源编码限失真信源编码。37二二. . 游程编码
24、的定义游程编码的定义o游程游程：数字序列中连续出现相同符号的一段。：数字序列中连续出现相同符号的一段。o二元序列的游程：只有二元序列的游程：只有“0 0”和和“1 1”两种符号。两种符号。n连连“0 0”这一段称为这一段称为“0 0”游程，它的长度称为游程，它的长度称为游游程长度程长度L L(0)(0)；n连连“1 1”这一段称为这一段称为“1 1”游程，它的游程长度用游程，它的游程长度用L L(1)(1)表示。表示。38三三. . 二元独立序列二元独立序列 二元独立序列游程长度概率二元独立序列游程长度概率o若规定二元序列总是从若规定二元序列总是从“0 0”开始，第一个游程是开始，第一个游程是
25、“0 0”游程，则第二个游程必为游程，则第二个游程必为“1 1”游程，第三个游程，第三个又是又是“0 0”游程游程。o对于随机序列，游程长度是随机的其取值可为对于随机序列，游程长度是随机的其取值可为1,2,3,1,2,3,，直至无穷。，直至无穷。39o游程长度序列游程长度序列/ /游程序列：用交替出现的游程序列：用交替出现的“0 0”游程游程和和“1 1”游程长度表示任意二元序列。游程长度表示任意二元序列。o游程变换游程变换：是一种一一对应的变换，也是可逆变换。：是一种一一对应的变换，也是可逆变换。 例如：二元序列例如：二元序列 000101110010001000101110010001 可
26、变换成如下游程序列可变换成如下游程序列 3113213131132131o游程变换减弱了原序列符号间的相关性。游程变换减弱了原序列符号间的相关性。o游程变换游程变换将二元序列变换成了多元序列将二元序列变换成了多元序列；这样就适；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。提高通信效率。40编码方法编码方法n首先测定首先测定“0 0”游程长度和游程长度和“1 1”游程长度的概率分游程长度的概率分布，即布，即以游程长度为元素，构造一个新的信源以游程长度为元素，构造一个新的信源；n对新的信源（游程序列）进行哈夫曼编码。对新的信源（
27、游程序列）进行哈夫曼编码。 多元序列也可以变换成游程序列，如多元序列也可以变换成游程序列，如r r元序列可元序列可有有r r种游程。但是变换成游程序列时，需要增加标志位种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的才能区分游程序列中的“长度长度”是是r r种游程中的哪一个种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，可能会抵消压缩编码得到的好处。所以，对多元序列对多元序列进行游程变换的意义不大进行游程变换的意义不大。41 二元独立序列游程长度的熵二元独立序列游程长度的熵o若二元序
28、列的概率特性已知，由于二元序列与游程若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率变换序列的一一对应性，可计算出游程序列的概率特性。特性。o令令“0 0”和和“1 1”的概率分别为的概率分别为p p0 0和和p p1 1，则，则“0 0”游程游程长度长度L L(0)(0)的概率为的概率为 p p L L(0)=(0)=p p0 0L L(0)(0)1 1p p1 1 式中式中L L(0)=1,2,(0)=1,2, ,o在计算在计算p p L L(0)(0)时必然已有时必然已有“0 0”出现，否则就不是出现，否则就不是“0 0”游程，若下一个符号是游程，
29、若下一个符号是“1 1”，则游程长度为，则游程长度为1 1，其概率是，其概率是p p1 1 =1 =1p p0 0；若下一个符号为；若下一个符号为“0 0”、再下、再下一个符号为一个符号为“1 1”，则游程长度为，则游程长度为2 2，其概率将为，其概率将为p p0 0p p1 1 ；依此类推。；依此类推。42o游程长度至少是游程长度至少是1 1，理论上，游程长度可以是无穷，理论上，游程长度可以是无穷，但很长的游程实际出现的概率非常小。但很长的游程实际出现的概率非常小。o同理可得同理可得“1 1”游程长度游程长度L L(1)(1)的概率为的概率为P P L L(1)=(1)=p p1 1L L(
30、1)-1(1)-1p p0 043o“0”游程长度的熵游程长度的熵44 二元独立序列的平均游程长度二元独立序列的平均游程长度o“0 0”游程序列的平均游程长度游程序列的平均游程长度o同理可得同理可得“1 1”游程长度的熵和平均游程长度游程长度的熵和平均游程长度45 二元独立序列的熵二元独立序列的熵o“0 0”游程序列的熵与游程序列的熵与“1 1”游程长度的熵之和除游程长度的熵之和除以它们的平均游程长度之和，即为对应原二元序以它们的平均游程长度之和，即为对应原二元序列的熵列的熵H H( (X X) )o游程变换后符号熵没有变。游程变换后符号熵没有变。因为游程变因为游程变换是一一对应的可逆变换，所
31、以变换后换是一一对应的可逆变换，所以变换后熵值不变，这也说明变换后的游程序列熵值不变，这也说明变换后的游程序列是独立序列。是独立序列。46o对于有相关性的二元序列，也可以证明变换后的游对于有相关性的二元序列，也可以证明变换后的游程序列是独立序列，并且也有程序列是独立序列，并且也有 的结论，只是此时的结论，只是此时H H L L(0)(0)，H H L L(1)(1)，l l0 0和和l l1 1的的具体表达形式不同，它们是相关符号的联合概率和具体表达形式不同，它们是相关符号的联合概率和条件概率的函数。条件概率的函数。47五. 长码的截断处理方法o理论上，游程长度可从理论上，游程长度可从1 1到无穷，要建立游程长度和到无穷，要建立游程长度和码字之间的一一对应的码表是困难的。码字之间的一一对应的码表是困难的。o一般情况下，游程越长，出现的概率越小；当游程长一般情况下，游程越长，出现的概率越小；当游程长度趋向于无穷时，出现的概率也趋于度趋向于无穷时，出现的概率也趋于0 0。o按照哈夫曼编码规则，概率越小，码字越长。但小概按照哈夫曼编码规则，概率越小，码字越长。但小概率的码字对平均码长影响较小。所以在实际应用时，率的码字对平均码长影响较小。所以在实际应用时，常对长码采用截断处理的方法。常对长码采用截断处理的方法。48(1) 8.5； 8.9 ；8.11（1、3）作 业
