第五章 习题课.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第五章 信源编码,当你为错过太阳而流泪时，你也将错过群星了。,泰戈尔,1/12/2026,1,信源编码,：,以,提高通信有效性,为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。,信道编码：,是以,提高信息传输的可靠性,为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率,/,带宽。与信源编码正好相反。,密码：,是以,提高通信系统的安全性,为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,第五章 总结,1/12/2026,2,香农编码,设离散无记忆信源,二进制香农码的编码步骤如下：,将信源符号按概率从大到小的顺序排列，为方便起见，令,p,(,x,1,),p,(,x,2,),p,(,x,n,),令,p,(,x,0,)=0,，用,p,a,(,x,j,),，,j,=,i,+1,表示第,i,个码字的累加概率，则,1/12/2026,3,香农编码,确定满足下列不等式的整数,k,i,，,并令,k,i,为第,i,个码字的长度,log,2,p,(,x,i,),k,i,1,log,2,p,(,x,i,),将,p,a,(,x,j,),用二进制表示，并取小数点后,k,i,位作为符号,x,i,的编码。,1/12/2026,4,费诺编码,费诺编码也是一种常见的信源编码方法。编码步骤如下：,将概率按从大到小的顺序排列，令,p,(,x,1,),p,(,x,2,),p,(,x,n,),按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编,m,进制码就分成,m,组。,给每一组分配一位码元。,将每一分组再按同样原则划分，重复步骤,2,和,3,，直至概率不再可分为止,。,1/12/2026,5,将信源符号按概率从大到小的顺序排列，令,p,(,x,1,),p,(,x,2,),p,(,x,n,),给两个概率最小的信源符号,p,(,x,n,-1,),和,p,(,x,n,),各分配一个码位“,0”,和“,1”,，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含,(,n,1),个信源符号的新信源。称为,信源的第一次缩减信源,，用,S,1,表示。,将缩减信源,S,1,的符号仍按概率从大到小顺序排列，重复步骤,2,，得到只含,(,n,2),个符号的缩减信源,S,2,。,重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为,1,。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,二元哈夫曼编码,1/12/2026,6,在编,m,进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有,m,个信源符号。非全树时，有,s,个码字不用：,第一次对最小概率符号分配码元时就只取,(,m,s,),个，分别配以,0,1,m,s,1,，,把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。,以后每次就可以取,m,个符号，分别配以,0,1,m,1,；,；,如此下去，直至所有概率相加得,1,为止，即得到各符号的,m,进制码字。,M,元哈夫曼编码,1/12/2026,7,香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；,香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；,费诺码和哈夫曼码的编码方法都不惟一；,费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编,m,进制码，但,m,越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；,哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码,。,1/12/2026,8,游程变换减弱了原序列符号间的相关性。,游程变换,将二元序列变换成了多元序列,；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。,编码方法：,首先测定“,0”,游程长度和“,1”,游程长度的概率分布，即,以游程长度为元素，构造一个新的信源,；,对新的信源（游程序列）进行哈夫曼编码。,多元序列也可以变换成游程序列，如,m,元序列可有,m,种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是,m,种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，,对多元序列进行游程变换的意义不大,。,二元游程编码,1/12/2026,9,L,D,编码方法是一种分帧传送的方式；,编码方法,在冗余位序列中取,N,个符号作为一帧，编成一个码字，码字中含有信息位的数量和位置信息，在接收端依据这些信息进行译码；,每个码字传送两个数：,Q,和,T,，由下式计算,L-D,编码,1/12/2026,10,Q,的位数：,T,的位数：,总位数：,L-D,编码,1/12/2026,11,寻找某一值,K,若,再找某一值,L,L-D,译码,1/12/2026,12,我们学习了,6,种信源编码：,香农编码,、,费诺编码,、,哈夫曼编码,、,冗余编码,、,游程编码,。,游程编码是非分组编码；,本章介绍的都是离散信源变长编码。,优点,：提高编码效率；,缺点,：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。,编码总结,1/12/2026,13,1.,已知某信源的符号集合,x,1,x,2,x,3,为无限离散消息集合，它们的出现概率分别为,P,(,x,1,)=1/2,，,P,(,x,2,)=1/4,，,P,(,x,3,)=1/8,，,，,P,(,x,i,)=1/2,i,，,。（,1,）,用香农编码方法给出各个符号消息的代码组；（,2,）计算该信源编码的效率。,解,（,1,）信源消息的概率分布呈等比级数，按香农编码方法，其码长集合为自然数数列,1,2,3,i,；,对应的编码分别为：,0,10,110,111110(,i,1,个,1),。,习题,1,1/12/2026,14,与本题有关的数据和编码结果列于下表。,习题,1,1/12/2026,15,习题,1,（,2,）先求熵和平均码长,1/12/2026,16,2.,某信源具有,7,个消息符号，其概率分别为：,0.20,0.19,0.18,0.17,0.15,0.10,0.01,。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。,解 先计算每一个码字的码长，分别为：,3,3,3,3,3,4,7,；再计算累加概率。,例如：,P,4,=,p,1,+,p,2,+,p,3,=0.20+0.19=0.18=0.57,，,变换成二进制数为：,0.1001,，因为,b,4,=3,，,故对于概率为,0.17,的消息符号,x,4,，,其编码为,100,。,依此类推，与本题有关的数据和编码结果列于下表。,习题,2,1/12/2026,17,习题,2,1/12/2026,18,可以求出其平均码长和信源熵分别为,3.14,码元,/,符号和,2.16,比特,/,符号，故编码效率为,上述两个例子可见，香农编码方法对有的信源能够达到最佳编码而有的则不能，因此还不能说它是最佳编码。,习题,2,1/12/2026,19,香农编码方法特点,：,由于,b,i,总是进一取整，香农编码方法不一定是最佳的；,由于第一个消息符号的累加概率总是为,0,，故它对应的码字总是,0,、,00,、,000,、,00,的式样；,码字集合是唯一的，且为即时码；,先有码长再有码字；,对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。,评述,1/12/2026,20,3.,试对概率分别为：,0.20,0.19,0.18,0.17,0.15,0.10,0.01,的信源用费诺编码方法，求其二进制代码组及其编码效率。,解先将消息符号按概率大小排列，再按步骤进行子集分解，本题经过,4,次分解完成编码，整个过程列于下表,习题,3,1/12/2026,21,由上表的数据可得，代码组集合的平均长度为,=2.74,码元,/,符号,编码效率为,可见，费诺方法的编码效率比香农编码方法要高。,习题,3,1/12/2026,22,费诺编码特点,：,概率大，则分解的次数小；概率小,则分解的次数多。这符合最佳编码原则。,码字集合是唯一的。,分解完了，码字出来了，码长也有了。,因此，费诺编码方法又称为子集分解法。,费诺编码方法比较适合于每次分组概率都很接近的信源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,评述,1/12/2026,23,4.,一个信源包含,6,个符号消息，它们的出现概率分别为,0.3,0.2,0.15,0.15,0.1,0.1,，信道基本符号为二进制码元，试用哈夫曼编码方法对该信源的,6,个符号进行信源编码，并求出代码组的平均长度和信息传输速率。,解 根据哈夫曼编码的步骤，可得其编码过程和编码结果，如下图所示。,习题,4,1/12/2026,24,习题,4,1/12/2026,25,由编码结果，求得平均码长为,=2.5,码元,/,符号,信源熵为,编码效率为,由此可得其编码效率为,98.8%,，接近于最佳编码。,习题,4,1/12/2026,26,5.,已知一个信源的概率空间为,试用三进制码元,0,1,2,对该信源的各个消息进行哈夫曼编码。,解,这是多进制哈夫曼编码问题，其编码方法和二进制时基本相同，即不断地将较小的概率相加并排队，只不过这里的基本分组应考虑,M,进制。,但在第一次组合时，可将概率最小和较小的,M,或,(,M,1,2),个先组合，通过小概率参与组合次数的增加来减少大概率参与组合的次数。,习题,5,1/12/2026,27,设第一次组合的概率数取,m,0,，,考虑到第二次组合就应该使用,M,进制，则,m,0,通常应满足,=,正整数的要求。,如果将,2,个相加的概率按其大小分别赋予编码值“,1”,和“,0”,（概率较大者赋,“,1”,，小者赋“,0”,，相等时则任意），,3,个相加的概率按其大小分别赋予编码值“,2”,、,“,1”,和“,0”,，依此类推，就可以得到类似于二进制时的哈夫曼编码结果。,习题,5,1/12/2026,28,本例,N,=6,、,M,=3,。,由于,x,5,、,x,6,的概率最小（均为,0.1,），当取,m,0,=2,时，,=,，符合上述要求，故第一,次组合取,x,5,、,x,6,；,第二次组合将,x,3,，,x,4,和,x,2,的概率相加，其值为,0.5,；,第三次组合是这两组和,x,1,概率之和已经为,1,，完成编码,整个过程如下图所示，,x,1,x,6,的编码结果分别为：,1,22,21,20,01,00,。,可以验证该结果也接近于最佳编码。,习题,5,1/12/2026,29,习题,5,1/12/2026,30,哈夫曼编码特点,：,由于哈夫曼编码总是以最小概率相加的方法来“缩减”参与排队的概率个数，因此概率越小，对缩减的贡献越大，其对于消息的码字也越长；,最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，亦即具有多种可能的代码组集合；,尽管对同一信源存在着多种结果的哈夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此哈夫曼编码是最佳编码。,哈夫曼编码是一种最佳编码，实现也不困难，因此到目前为止它仍是应用最为广泛的无失真信源编码之一。,评述,1/12/2026,31,习题,6,6.,信源符号,X,有,8,种消息，概率为,(1/2,1/4,1/8,1/16,1/32,1/64,1/128,1/128),(1),求符号熵,H,(,X,),(2),用香农编码编成二进变长码，计算其编码效率。,(3),用费诺编码编成二进变长码，计算其编码效率。,(4),用费诺编码编成三进变长码，计算其编码效率。,(5),用哈夫曼编码编成二进变长码，计算其编码效率。,(6),用哈夫曼编码编成三进变长码，计算其编码效率。,1/12/2026,32,习题,6,解,:(1)H(X)=1.9844,1/12/2026,33,习题,6,x,i,P(x,i,),S1,S2,S3,S4,S5,S6,S7,码字,x,1,1/2,0,0,x,2,1/4,1,0,10,x,3,1/8,1,0,110,x,4,1/16,1,0,1110,x,5,1/32,1,0,11110,x,6,1/64,1,0,111110,x,7,1/128,1,0 1111110,x,8,1/128,1 1111111,1/12/2026,34,习题,6,x,i,P(x,i,),S1,S2,S3,S4,码字,x,1,1/2,0,0,x,2,1/4,1,0,10,x,3,1/8,1,11,x,4,1/16,2,0,120,x,5,1/32,1,121,x,6,1/64,2,0,1220,x,7,1/128,1,1221,x,8,1/128,2,1/12/2026,35,习题,6,1/12/2026,36,习题,6,1/12/2026,37,