第11讲信源编码三个基本编码课件.ppt

1、第第5章：信源编码章：信源编码通信系统的性能指标主要是通信系统的性能指标主要是有效性有效性、可可靠性靠性、安全性安全性和和经济性经济性，除了经济性外，除了经济性外，这些指标正是信息论研究的对象。这些指标正是信息论研究的对象。编码的目的是为了编码的目的是为了优化通信系统优化通信系统，使这，使这些指标达到最佳；些指标达到最佳；按不同的编码目的，编码分为三类：按不同的编码目的，编码分为三类：信信源编码源编码、信道编码信道编码和和安全编码安全编码/密码。密码。信源编码的基本途径有两个：信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，使序列中的各个符号尽可能地互相独立，即解除相关性；即解除

2、相关性；使编码中各个符号出现的概率尽可能地使编码中各个符号出现的概率尽可能地相等，即概率均匀化相等，即概率均匀化。信源编码的分类：离散信源编码、连续信信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。源编码和相关信源编码三类。l离散信源编码离散信源编码：独立信源编码，可做到无失真：独立信源编码，可做到无失真编码；编码；l连续信源编码连续信源编码：独立信源编码，只能做到限失：独立信源编码，只能做到限失真信源编码；真信源编码；l相关信源编码相关信源编码：非独立信源编码。：非独立信源编码。信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理：无失真编码定理无失真

3、编码定理只适用于离散信源只适用于离散信源 限失真编码定理限失真编码定理 对于连续信源，只能在失真受限制的情况下进对于连续信源，只能在失真受限制的情况下进行行限失真编码限失真编码5.1.1 码字唯一可译的条件码字唯一可译的条件5.1 离散信源编码离散信源编码充要条件。是异前置码的满足克劳夫特不等式11nikim即时码：如果一个码的任何一个码字都不是其他码字的前缀，则称该码为前缀码、异前置码也称为即时码。ki 称为码字长度或简称码长称为码字长度或简称码长m为码符号数为码符号数1110110100 0111011010 110010 10100 125.0125.025.05.04321DCBAaa

4、aa码码码码概率消息判断以下码字是否可分离？异前置码即时码可分离有延时可分离分离不可分离不可例mXLHKmXLHlog)(log)(1对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行m元变长编码，一定存在无失真的信源编码方法，满足：满足：其码字平均长度其码字平均长度满足：满足：其码字平均信息率其码字平均信息率R)()(XHRXH5.1.1 码字唯一可译的条件码字唯一可译的条件5.1.2 香农编码香农编码例例05.01.015.02.025.025.0)(654321xxxxxxXPX设一单符号离散无记忆信源设一单符号离散无记忆信源试对该信源编二进制香农码。试对该信源编二进制香农码。

5、5.1.2 香农编码香农编码二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：（1）将信源符号按概率）将信源符号按概率从大到小从大到小的顺序排列的顺序排列 p(x1)p(x2)p(xn)xi p(xi)pa(xj)ki 码字码字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 111110(0.11110)2 njxpxpjii

6、ja,2,1,)()(10（2）令）令 p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 个码字的个码字的累加概率累加概率，则，则 （3）确定满足下列不等式的整数）确定满足下列不等式的整数 ki，并令，并令 ki 为第为第 i 个码字的个码字的长度长度log2 p(xi)ki 1 log2 p(xi)xi p(xi)pa(xj)ki 码字码字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10

7、0.850 4 1101(0.1101)2 x6 0.05 0.950 5 111110(0.11110)2 （4）将）将 pa(xj)用二进制表示，并取小数点后用二进制表示，并取小数点后 ki 位作为符号位作为符号 xi 的的编码。编码。计算出给定信源香农码的计算出给定信源香农码的平均码长平均码长)/(7.2505.0410.03)15.02.0(2225.0符号码元K)/(42.2)(log)()(612符号比特iiixpxpXH由离散无记忆信源熵定义，可计算出由离散无记忆信源熵定义，可计算出信源熵信源熵为：为：信息率信息率为为编码效率编码效率为信源熵和信息率之比为信源熵和信息率之比量符号

8、能载荷的最大信息是编码后平均每个信源mLKR2log2,1/(7.22log17.2log22mLmLKR这里符号）比特%63.897.242.2)(RXH5.1.3 5.1.3 费诺编码费诺编码5.1.1 5.1.1 码字唯一可译的条件码字唯一可译的条件例例:设有一单符号离散信源设有一单符号离散信源对该信源编二进制费诺码。对该信源编二进制费诺码。04.008.016.018.022.032.0,)(654321xxxxxxXPX（2）按编码进制数将概率分组，使每组概率尽可能接近）按编码进制数将概率分组，使每组概率尽可能接近或相等。如或相等。如编二进制码就分成两组编二进制码就分成两组，编，编

9、m 进制码就分进制码就分成成 m 组。组。信源符号信源符号 概率概率 编码编码 码字码字 码长码长 x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 （1）将概率按从大到小的顺序排列）将概率按从大到小的顺序排列 p(x1)p(x2)p(xn)（3）给每一组分配一位码元。）给每一组分配一位码元。（4）将每一分组再按同样原则划分，重复步骤）将每一分组再按同样原则划分，重复步骤 2 和和 3，直至概率不再可分为止。直至概率不再可分为止。信源符号信

10、源符号 概率概率 编码编码 码字码字 码长码长 x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 该信源的该信源的熵熵为为平均码长平均码长为为对上述信源采用费诺编码的对上述信源采用费诺编码的信息率信息率为为编码效率编码效率为为)/(35.2)(log)()(612符号比特iiixpxpXH)/(4.2)(61符号码元iiikxpK2,1/(4.22log14.2log22mLmLKR这里符号）比特%92.974.235.2)(RXH5.1.

11、4 赫夫曼编码赫夫曼编码5.1.1 码字唯一可译的条件码字唯一可译的条件 赫夫曼赫夫曼(Huffman)编码是一种效率比较高的变长无失编码是一种效率比较高的变长无失真信源编码方法。真信源编码方法。5.3.1 二进制哈夫曼编码二进制哈夫曼编码 5.3.2 m 进制哈夫曼编码进制哈夫曼编码(自学）自学）例：设单符号离散无记忆信源如下，要求对信源例：设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。编二进制哈夫曼码。(1)将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令p(x1)p(x2)p(xn)5.3.1 二进制哈夫曼编码二进制哈夫曼编码04.005.006.0

12、07.01.01.018.04.0,)(87654321xxxxxxxxXPX(2)信源的第一次缩减信源信源的第一次缩减信源：给两个概率最小的信源符号给两个概率最小的信源符号 p(xn1)和和 p(xn)各分配一个码位各分配一个码位“0”和和“1”，将这两个信源符号合并成一，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含得到一个只包含(n1)个信源符号的新信源，用个信源符号的新信源，用 S1 表示。表示。(3)将缩减信源将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率

13、从大到小顺序排列，重复步骤(2)，得到只含得到只含(n2)个符号的缩减信源个符号的缩减信源 S2。(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为剩两个符号的概率之和必为 1。然后从最后一级缩减信源开。然后从最后一级缩减信源开始，依编码路径始，依编码路径向前返回向前返回，就得到各信源符号所对应的码字。，就得到各信源符号所对应的码字。l信源熵信源熵为为l平均码长平均码长为为l编码效率编码效率为为l若采用定长编码，码长若采用定长编码，码长 K=3，则编码效率则编码效率l编码效率提高了编码效率提高了 12.7%。)/(

14、55.2)(log)()(812符号比特iiixpxpXH)/(61.25)04.005.0(4)06.007.010.0(3)1.018.0(14.0)(81符号码元iiikxpK%7.9761.255.2)()(KXHRXH%85355.2l缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到的码字长码字长度度 ki 也不尽相同也不尽相同。例例：单符号离散无记忆信源：单符号离散无记忆信源 ，用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。l方法一：方法一

15、：合并后的新符号排在其它相同概率符号的后面。合并后的新符号排在其它相同概率符号的后面。1.01.02.02.04.0,)(54321xxxxxXPXl方法二：方法二：合并后的新符号排在其它相同概率符号合并后的新符号排在其它相同概率符号的前面。的前面。l编法一的平均码长为编法一的平均码长为l编法二的平均码长为编法二的平均码长为l可见可见 ，本例两种编法的平均码长相，本例两种编法的平均码长相同，所以编码效率相同。同，所以编码效率相同。)/(2.23)1.01.0(2)2.02.04.0()(512符号码元iiikxpK21KK)/(2.24)1.01.0(32.022.014.0)(511符号码元

16、iiikxpK讨论讨论：l码字长度的方差码字长度的方差2：长度长度 ki 与平均码长与平均码长 之差的之差的平方的数学期望，即平方的数学期望，即l编法一码字长度方差：编法一码字长度方差：l编法二码字长度方差：编法二码字长度方差：KniiiiKkxpKkE1222)()(36.1)2.24)(1.01.0()2.23(2.0)2.22(2.0)2.21(4.022222116.0)2.23)(1.01.0()2.22)(2.02.04.0(2222比比 较较 相同点：相同点：香农编码、费诺编码、哈夫曼编码属于香农编码、费诺编码、哈夫曼编码属于无失真信源编码无失真信源编码。香农编码、费诺编码、哈夫

17、曼编码主要针对香农编码、费诺编码、哈夫曼编码主要针对无记忆无记忆信源。信源。香农码、费诺码、哈夫曼码都考虑了信源的统计特性，香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；码长缩短，从而实现了对信源的压缩；不同点不同点：香农码有系统的、惟一的编码方法，但在很多情况下编码香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码，费费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编诺码也可以编 m 进制码，但进制码，但 m 越大，信源的符号数越多，越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；必能得到充分利用；结论结论：哈夫曼码对信源的统计特性没有特殊要求，编码效哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。优于香农码和费诺码。作业：5.1 5.2