第5章：信源编码

1、信息论与编码信息论与编码西安工业大学电子信息工程学院 赵 黎第五章 信源编码通信系统的优化模型n信源信源编码加密信道编码信源译码信道译码信道解密信宿密 钥 源噪声密 钥 源ULVLULSmCmXnYnCmSmVLK1K2本章内容n离散信源编码离散信源编码n连续信源编码连续信源编码5.1 离散信源编码n编码的基本概念编码的基本概念n码的分类码的分类n香农编码香农编码n费诺编码费诺编码n赫夫曼编码赫夫曼编码n无失真信源编码定理无失真信源编码定理-香农第一定理香农第一定理 a1, a2, , aK 为信源符号集，序列中每一个符号为信源符号集，序列中每一个符号uml都取自信源符都取自信源符号集。号集。

2、 b1 ，b2 ，bD 是适合信道传输的是适合信道传输的D个符号，用作信源编码器的个符号，用作信源编码器的编码符号。编码输出码字编码符号。编码输出码字cm = cm1 cm2 cmn， c mk b1 ，b2 ，bD k = 1, 2 , , n ，n表示码字长度，简称表示码字长度，简称码长码长 信源符号信源符号 a1,a2, , aK 信道符号（码符号）信道符号（码符号） b1, b2, , bD 信源编码器信源编码器 ui = ui1 ui2 uiL 码字码字ci = ci1 ci2 cin 1、编码的基本概念信源符号集信源符号集=我我, 是是, 一名一名，学生，老师，编码，理论，学生，老

3、师，编码，理论, 信道符号集信道符号集=I=I ，am，is, are, a, student, coding, theory, apple, 如果某次该编码器的输入是如果某次该编码器的输入是“我是一名学生我是一名学生”，即输入序列，即输入序列ui = (ui1=“我我”，ui2=“是是” ，ui3=“一名一名” ，ui4=“学生学生”)，编码器，编码器的输出的输出“I am a student”，即输出序列，即输出序列ci = (ci1=“I”, ci2 =“am”, ci3 =“a”, ci4 =“student”) 信源编码可看成是从信源符号集到码符号集的一种映射信源编码可看成是从信源符

4、号集到码符号集的一种映射，即将，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为射成一个长度为n的码字。对于同一个信源，编码方法是多种的。的码字。对于同一个信源，编码方法是多种的。【例【例5.1】 用用 u1 ，u2 ，u3，u4， 表示信源的四个消息，码符号集为表示信源的四个消息，码符号集为0,1，表，表1列出了该信源的几种不同编码。列出了该信源的几种不同编码。表1 同一信源的几种不同编码2、编码的分类信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )0000

5、01u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000码码5 51010010001 3.变长码变长码若码字集合若码字集合C中的所有码字中的所有码字cm (m = 1,2, ,M)，其码长不都相同，称其码长不都相同，称码码C为变长码，表为变长码，表1中列出的码中列出的码3、码、码4 和码和码5就是变长码。就是变长码。 2.等长码等长码在一组码字集合在一组码字集合C中的所有码字中的所有码字cm (m = 1,2, ,M)，其码长都相同，其码长都相同，则称这组码则称这组码C为等长码，表为等长码，表1中列出的码中列出的码1、码、码2

6、 就码长就码长n = 2等长码等长码一般，可以将码简单的分成如下几类：一般，可以将码简单的分成如下几类： 1.二元码二元码若码符号集为若码符号集为0，1，则码字就是二元序列，称为二元码，则码字就是二元序列，称为二元码, ,二元码二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表码，表1列出的列出的5种码都是二元码。种码都是二元码。 5.非奇异码非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表息都用不同的码字对其编码，例表

7、1 1中的码中的码2、码、码3、码、码4和码和码5都都是非奇异码。是非奇异码。 4.奇异码奇异码对奇异码来说，从信源消息到码对奇异码来说，从信源消息到码字的影射不是一一对应的。例表字的影射不是一一对应的。例表1中中的码的码1 1，信源消息，信源消息u2和和u4都用码字都用码字11对其编码，因此这种码就是奇异码对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。，奇异码不具备惟一可译性。6 6）唯一可译码：）唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一的信源符号序

8、列，则此码称为唯一可译码，否则就称为非唯一可译码。可译码。111001004321ssss等长码等长码非奇异码非奇异码0 0 0 1 1 0 1 14321ssss唯一可译唯一可译 如果接收端收到一个完整的码字后，不能立即译码，还要如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。做非即时码。7 7 非即时码：非即时码：10001001014321ssss非奇异码非奇异码1 1 0 1 0 0 1 0 0 01 0?2s01不即时不即时任何一个码字是其它码字的延长或前缀任何一

9、个码字是其它码字的延长或前缀如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异异前缀码。前缀码。8 8、即时码、即时码00010010114321ssss非奇异码非奇异码1 0 1 0 0 1 0 0 0 1任何一个码字不是其它码字的延长或前缀任何一个码字不是其它码字的延长或前缀即 时 码0 12s即时n即时码的判决准则即时码的判决准则n克拉夫特不等式：克拉夫特不等式：设信源为设信源为 ，对其进行，对其进行r元信源编码，

10、相应码字长度为元信源编码，相应码字长度为 ，则即时码存在，则即时码存在的充要条件是：的充要条件是：nuuuU,21nlll,2111nilirn唯一可译码的判决准则唯一可译码的判决准则n麦克米伦不等式：麦克米伦不等式：设信源为设信源为 ，对其进行，对其进行r元信源编码，相应码字长度为元信源编码，相应码字长度为 ，则唯一可译码，则唯一可译码存在的充要条件是：存在的充要条件是：nuuuU,21nlll,2111nilirn不同编码方式的衡量标准不同编码方式的衡量标准n平均码长：平均码长：对离散无记忆信源进行信源编码，设编码后各个对离散无记忆信源进行信源编码，设编码后各个码字的码长分别为码字的码长分

11、别为 ，则定义该码的平均码长为：，则定义该码的平均码长为：n如果某种编码方式的平均码长小于所有其他编码方式，则该如果某种编码方式的平均码长小于所有其他编码方式，则该码称为紧致码或最佳码。码称为紧致码或最佳码。 niiilupL1nlll,21n编码信息率编码信息率(编码速率编码速率)：n码长码长 表示长为表示长为N的信源序列用多少个的信源序列用多少个r进制码符号表示，因进制码符号表示，因此此 表示平均一个信源符号用多少个表示平均一个信源符号用多少个r进制符号表示，再进制符号表示，再乘以乘以 表示将表示将r进制转换成二进制进制转换成二进制signbitrNlR/logNl /rlogln编码效率

12、：编码效率：n含义：理论上平均每个信源符号用多少个二进制符号的个数含义：理论上平均每个信源符号用多少个二进制符号的个数除以实际上用的二进制码符号的个数，即表示一种编码的效除以实际上用的二进制码符号的个数，即表示一种编码的效率。率。 RuHn设离散无记忆信源：设离散无记忆信源： niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(3、香农编码n 二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：n将信源符号按概率从大到小的顺序排列，为方便起见，令：将信源符号按概率从大到小的顺序排列，为方便起见，令： p(x1) p(x2) p(xn)n 令令

13、p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 个码字的个码字的累加概累加概率率，则：，则：n确定满足下列不等式的整数确定满足下列不等式的整数 ki ，并令，并令 ki 为第为第 i 个码字的长个码字的长度度log2 p(xi) ki 1 log2 p(xi)n 将将 pa(xj) 用二进制表示，并取小数点后用二进制表示，并取小数点后 ki 位作为符号位作为符号 xi 的的编码。编码。njxpxpjiija, 2 , 1, )()(10 例例6.1.1 ：有一单符号离散无记忆信源：有一单符号离散无记忆信源：n对该信源编二进制香农码。对该信源编二进制香农码。 05. 010.

14、 015. 020. 025. 025. 0,)(654321xxxxxxXPXn计算出给定信源香农码的平均码长：计算出给定信源香农码的平均码长：n若对上述信源采用等长编码，要做到无失真译码，每个符若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用号至少要用 3 个比特表示。相比较，香农编码对信源进个比特表示。相比较，香农编码对信源进行了压缩。行了压缩。)/(7 .2505.0410.03)15.02 .0(2225.0符符号号比比特特 Kn由离散无记忆信源熵定义，可计算出信源上熵为：由离散无记忆信源熵定义，可计算出信源上熵为：n对上述信源采用香农编码的信息率为：对上述信源采用香农编

15、码的信息率为：n编码效率为信源熵和信息率之比。则：编码效率为信源熵和信息率之比。则：可以看出，编码效率并不是很高。可以看出，编码效率并不是很高。)/(42. 2)(log)()(612符符号号比比特特 iiixpxpXH2, 17 . 22log17 . 2log22 mLmLKR这这里里%63.897 . 242. 2)( RXH n将概率按从大到小的顺序排列，令：将概率按从大到小的顺序排列，令：p(x1) p(x2) p(xn)n按编码进制数将概率分组，使每组概率尽可能接近或相按编码进制数将概率分组，使每组概率尽可能接近或相等。如等。如编二进制码就分成两组，编二进制码就分成两组，编编 m

16、进制码就分成进制码就分成 m 组。组。n给每一组分配一位码元。给每一组分配一位码元。n将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤 2 和和 3，直，直至概率不再可分为止。至概率不再可分为止。4、费诺编码例例6.3.1：设有一单符号离散信源：设有一单符号离散信源n对该信源编二进制费诺码。对该信源编二进制费诺码。05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX表表二进制费诺编码二进制费诺编码 信源符号信源符号 概率概率 编码编码 码字码字 码长码长 x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0

17、.20 0 10 2 x4 0.15 0 110 3 x5 0.10 0 1110 4 x6 0.05 1 1 1 1 1111 4 n该信源的熵为：该信源的熵为：n平均码长为：平均码长为：n对上述信源采用费诺编码的信息率为：对上述信源采用费诺编码的信息率为：n编码效率为：编码效率为：n本例中费诺编码有较高的编码效率。费诺码比较适合于本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组概率分组概率都相等都相等的信源进行编码时，可达到理想的编码效率。的信源进行编码时，可达到理想的编码效率。)/(42325. 2)(l

18、og)()(612符号比特iiixpxpXH)/( 54 . 2)(61符号比特iiikxpK2, 145. 22log145. 2log22mLmLKR这里%91.9845. 242325. 2)(RXH例例6.3.2：有一单符号离散无记忆信源：有一单符号离散无记忆信源n对该信源编二进制费诺码，编码过程如下表。对该信源编二进制费诺码，编码过程如下表。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPXn信源熵为：信源熵为：H(X)=2.75(比特比特/符号符号)n平均码长为：平均码长为：n编码效率为编码效率为=1。之所以如此，因为每次所分两组

19、的。之所以如此，因为每次所分两组的概率恰好相等。概率恰好相等。（比比特特符符号号）75. 2440625. 03212. 02)25. 025. 0( K 哈夫曼哈夫曼( (HuffmanHuffman) ) 编码是一种效率比较高的变长无失编码是一种效率比较高的变长无失真信源编码方法。真信源编码方法。5、哈弗曼编码编码步骤(1) 将信源符号按概率从大到小的顺序排列，令：将信源符号按概率从大到小的顺序排列，令：p(x1) p(x2) p(xn)(2) 信源的第一次缩减信源：信源的第一次缩减信源：给两个概率最小的信源符号给两个概率最小的信源符号 p(xn1) 和和 p(xn) 各分配一个码位各分配

20、一个码位“0”和和“1”，将这，将这两个信源符号合并成一个新符号，并用这两个最小的概两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含率之和作为新符号的概率，结果得到一个只包含 (n1) 个信源符号的新信源，用个信源符号的新信源，用 S1 表示。表示。(3) 将缩减信源将缩减信源 S1 的符号仍按概率从大到小顺序排列，的符号仍按概率从大到小顺序排列，重复步骤重复步骤 (2)，得到只含，得到只含 (n2) 个符号的缩减信源个符号的缩减信源 S2。(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符

21、号的概率之和必为时所剩两个符号的概率之和必为 1。然后从最后一级缩。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。所对应的码字。例例 设单符号离散无记忆信源如下，要求对信源编二进制设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。哈夫曼码。 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPXn在图中读取码字的时候，一定要从后向前读，此时编出在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，

22、来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。则码字不可分离。n信源熵为：信源熵为：n平均码长为：平均码长为：n编码效率为：编码效率为：n若采用定长编码，码长若采用定长编码，码长 K=3，则编码效率：，则编码效率：n哈夫曼的编码效率提高了哈夫曼的编码效率提高了 12.7%。)/(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. 2

23、 n 注意：注意：哈夫曼的编法并不唯一。哈夫曼的编法并不唯一。n 每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”和和“1”码元是任意的，所以可得到不同的码字。只要码元是任意的，所以可得到不同的码字。只要在各次缩在各次缩减信源中保持码元分配的一致性，减信源中保持码元分配的一致性，即能得到可分离码字。即能得到可分离码字。n 不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长 ki 不不变，平均码长变，平均码长 也不变，所以没有本质区别；也不变，所以没有本质区别；n 缩减信源时，若合并后的新符号概率与其他符号概率缩减信源时，若合并后的

24、新符号概率与其他符号概率相等，从编码方法上来说，相等，从编码方法上来说，这几个符号的次序可任意排这几个符号的次序可任意排列，编出的码都是正确的，但得到的列，编出的码都是正确的，但得到的码字不相同码字不相同。不同。不同的编法得到的码字长度的编法得到的码字长度 ki 也不尽相同。也不尽相同。 例例 ：单符号离散无记忆信源：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。n方法一：方法一：合并后的新符号排在其它相同概率符号的后面。合并后的新符号排在其它相同概率符号的后面。 1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxX

25、PX n方法二：方法二：合并后的新符号排在其它相同概率符号的前面。合并后的新符号排在其它相同概率符号的前面。n单符号信源编二进制哈夫曼码，编码效率主要决定于信单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。码长越短，编码效率就越高。n编法一的平均码长为：编法一的平均码长为：n编法二的平均码长为：编法二的平均码长为：n可见可见 ，本例两种编法的平均码长相同，所，本例两种编法的平均码

26、长相同，所以编码效率相同。以编码效率相同。（比比特特符符号号） 5122 . 23) 1 . 01 . 0(2)2 . 02 . 04 . 0()(iiikxpK21KK （比特符号）（比特符号） 5112 . 24)1 . 01 . 0(32 . 022 . 014 . 0)(iiikxpKn讨论：n码字长度的方差码字长度的方差2：长度长度 ki 与平均码长与平均码长 之差的之差的平方的数学期望，即：平方的数学期望，即：n编法一码字长度方差：编法一码字长度方差：n编法二码字长度方差：编法二码字长度方差： niiiiKkxpKkE1222)()( 36. 1)2 . 24)(1 . 01 .

27、0()2 . 23(2 . 0)2 . 22(2 . 0)2 . 21(4 . 0222221 16. 0)2 . 23)(1 . 01 . 0()2 . 22)(2 . 02 . 04 . 0(2222 哪种方哪种方法更好？法更好？Kn比较：比较：第二种编码方法的码长方差要小许多。第二种编第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。码方法的码长变化较小，比较接近于平均码长。n第一种方法编出的第一种方法编出的 5 个码字有个码字有 4 种不同的码长；种不同的码长；n第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长；n第二种编

28、码方法更简单、更容易实现，所以更好。第二种编码方法更简单、更容易实现，所以更好。n结论结论：m 进制哈夫曼编码n对如下单符号离散无记忆信源编三进制哈夫曼码对如下单符号离散无记忆信源编三进制哈夫曼码. 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPXm 进制哈夫曼编码n对对m进制编码，可分离的码字数必为进制编码，可分离的码字数必为n即信源所含有的符号数为上值，如果不等于，则必须增加即信源所含有的符号数为上值，如果不等于，则必须增加s个不用个不用的码字，此时的码字，此时sm-1n当有当有s个码字不用时，第一次对最小概率符号

29、分配码元时就只取个码字不用时，第一次对最小概率符号分配码元时就只取(m-s)个，分别配以个，分别配以0,1，m-s-1，把这些符号的概率相加作，把这些符号的概率相加作为一个新符号的概率，与其他符号一起重新排列。以后每次就可为一个新符号的概率，与其他符号一起重新排列。以后每次就可以取以取m个符号，分别配以个符号，分别配以0,1，m-11 mkm例例 设单符号离散无记忆信源如下，要求对信源编三进制设单符号离散无记忆信源如下，要求对信源编三进制哈夫曼码。哈夫曼码。 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPXn平均码长为

30、：平均码长为：n信息率为：信息率为：n编码效率为：编码效率为：n可见：哈夫曼的编码效率相当高，对编码器的要求也简可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。单得多。（比比特特符符号号）69. 13)04. 005. 0(2)06. 007. 01 . 018. 0(14 . 0)(51 iiikxpK（比特符号）（比特符号）68. 23log169. 13log22 LKR%2 .9568. 255. 2)( RXH 结论n香农码香农码、费诺码费诺码、哈夫曼码哈夫曼码都考虑了信源的统计特性，使经常出现的都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；源的压缩；n香农码有系统的、唯一的编码方法，但在很多情况下编码效率不是很香农码有系统的、唯一的编码方法，但在很多情况下编码效率不是很高高;n费诺码和