第五章 习题课.ppt

第五章第五章 信源编码信源编码 当你为错过太阳而当你为错过太阳而流泪时，你也将错过流泪时，你也将错过群星了。群星了。泰戈尔泰戈尔 12/12/20221第五章第五章 信源编码信源编码n n信源编码信源编码：以以提高通信有效性提高通信有效性为目的的编码。通常通过为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。有效性。n信道编码：信道编码：是以是以提高信息传输的可靠性提高信息传输的可靠性为目的的编码。为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码通常通过增加信源的冗余度来实现。采用的一般方法是增大码率率/带宽。与信源编码正好相反。带宽。与信源编码正好相反。n密码：密码：是以是以提高通信系统的安全性提高通信系统的安全性为目的的编码。通常通为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，过加密和解密来实现。从信息论的观点出发，“加密加密”可视为可视为增熵的过程，增熵的过程，“解密解密”可视为减熵的过程。可视为减熵的过程。第五章第五章 总结总结12/12/20222第五章第五章 信源编码信源编码香农编码香农编码n设离散无记忆信源设离散无记忆信源n二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：q将信源符号按概率从大到小的顺序排列，为方便起见，将信源符号按概率从大到小的顺序排列，为方便起见，令令 p(x1)p(x2)p(xn)q令令p(x0)=0，用，用pa(xj)，j=i+1表示第表示第i个码字的累加概率，个码字的累加概率，则则12/12/20223第五章第五章 信源编码信源编码香农编码香农编码确定满足下列不等式的整数确定满足下列不等式的整数ki，并令并令ki为第为第i个码字的个码字的长度长度log2 p(xi)ki1 log2 p(xi)q将将pa(xj)用二进制表示，并取小数点后用二进制表示，并取小数点后ki 位作为符号位作为符号xi的编码。的编码。12/12/20224第五章第五章 信源编码信源编码费诺编码费诺编码 费诺编码也是一种常见的信源编码方法。编码步骤如下：费诺编码也是一种常见的信源编码方法。编码步骤如下：n将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令p(x1)p(x2)p(xn)n按编码进制数将概率分组，使每组概率尽可能接近按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编或相等。如编二进制码就分成两组，编m进制码就分进制码就分成成m组。组。n给每一组分配一位码元。给每一组分配一位码元。n将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2和和3，直，直至概率不再可分为止至概率不再可分为止。12/12/20225第五章第五章 信源编码信源编码n将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令p(x1)p(x2)p(xn)n给两个概率最小的信源符号给两个概率最小的信源符号p(xn-1)和和p(xn)各分配一个码位各分配一个码位“0”和和“1”，将这两个信源符号合并成一个新符号，并用这两个最小，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含的概率之和作为新符号的概率，结果得到一个只包含(n1)个信个信源符号的新信源。称为源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用，用S1表示。表示。n将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤2，得，得到只含到只含(n2)个符号的缩减信源个符号的缩减信源S2。n重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为符号的概率之和必为1。然后从最后一级缩减信源开始，依编码。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。路径向前返回，就得到各信源符号所对应的码字。二元哈夫曼编码二元哈夫曼编码12/12/20226第五章第五章 信源编码信源编码n在编在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有缩减信源有m个信源符号。非全树时，有个信源符号。非全树时，有s个码字不用：个码字不用：q第一次对最小概率符号分配码元时就只取第一次对最小概率符号分配码元时就只取(ms)个，分别配以个，分别配以0,1,ms1，把这些符号的概率相加作为一个新符号的概率，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。与其它符号一起重新排列。q以后每次就可以取以后每次就可以取m个符号，分别配以个符号，分别配以0,1,m1；如此如此下去，直至所有概率相加得下去，直至所有概率相加得1为止，即得到各符号的为止，即得到各符号的m进制码字。进制码字。M元哈夫曼编码元哈夫曼编码12/12/20227第五章第五章 信源编码信源编码n n香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；现了对信源的压缩；现了对信源的压缩；现了对信源的压缩；n n香农码有系统的、惟一的编码方法，但在很多情况下编码效率不香农码有系统的、惟一的编码方法，但在很多情况下编码效率不香农码有系统的、惟一的编码方法，但在很多情况下编码效率不香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；是很高；是很高；是很高；n n费诺码和哈夫曼码的编码方法都不惟一；费诺码和哈夫曼码的编码方法都不惟一；费诺码和哈夫曼码的编码方法都不惟一；费诺码和哈夫曼码的编码方法都不惟一；n n费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编可以编可以编可以编mm进制码，但进制码，但进制码，但进制码，但mm越大，信源的符号数越多，可能的编码方越大，信源的符号数越多，可能的编码方越大，信源的符号数越多，可能的编码方越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；案就越多，编码过程就越复杂，有时短码未必能得到充分利用；案就越多，编码过程就越复杂，有时短码未必能得到充分利用；案就越多，编码过程就越复杂，有时短码未必能得到充分利用；n n哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码编码设备的要求也比较简单，因此综合性能优于香农码和费诺码编码设备的要求也比较简单，因此综合性能优于香农码和费诺码编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。12/12/20228第五章第五章 信源编码信源编码n游程变换减弱了原序列符号间的相关性。游程变换减弱了原序列符号间的相关性。n游程变换游程变换将二元序列变换成了多元序列将二元序列变换成了多元序列；这样就适合于用其他方法，；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。如哈夫曼编码，进一步压缩信源，提高通信效率。n编码方法：编码方法：q首先测定首先测定“0”游程长度和游程长度和“1”游程长度的概率分布，即游程长度的概率分布，即以游以游程长度为元素，构造一个新的信源程长度为元素，构造一个新的信源；q对新的信源（游程序列）进行哈夫曼编码。对新的信源（游程序列）进行哈夫曼编码。n多元序列也可以变换成游程序列，如多元序列也可以变换成游程序列，如m元序列可有元序列可有m种游程。但是变种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的换成游程序列时，需要增加标志位才能区分游程序列中的“长度长度”是是m种游程中的哪一个的长度，否则，变换就不可逆。这样，增加种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行对多元序列进行游程变换的意义不大游程变换的意义不大。二元游程编码二元游程编码12/12/20229第五章第五章 信源编码信源编码nLD编码方法是一种分帧传送的方式；编码方法是一种分帧传送的方式；n编码方法编码方法q在冗余位序列中取在冗余位序列中取N个符号作为一帧，编成一个码字，码个符号作为一帧，编成一个码字，码字中含有信息位的数量和位置信息，在接收端依据这些信字中含有信息位的数量和位置信息，在接收端依据这些信息进行译码；息进行译码；q每个码字传送两个数：每个码字传送两个数：Q和和T，由下式计算，由下式计算L-D编码编码12/12/202210第五章第五章 信源编码信源编码qQ的位数：的位数：qT的位数：的位数：q总位数：总位数：L-D编码编码12/12/202211第五章第五章 信源编码信源编码q寻找某一值寻找某一值Kq若若q再找某一值再找某一值LL-D译码译码12/12/202212第五章第五章 信源编码信源编码n我们学习了我们学习了6种信源编码：种信源编码：香农编码香农编码、费诺编码费诺编码、哈哈夫曼编码夫曼编码、冗余编码冗余编码、游程编码游程编码。q游程编码是非分组编码；游程编码是非分组编码；q本章介绍的都是离散信源变长编码。本章介绍的都是离散信源变长编码。q优点优点：提高编码效率；：提高编码效率；q缺点缺点：需要大量缓冲设备来存储这些变长码，然后再：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。误码，容易引起错误扩散，所以要求有优质的信道。编码总结编码总结12/12/202213第五章第五章 信源编码信源编码 1.已知某信源的符号集合已知某信源的符号集合 x1,x2,x3,为无限离散消息集合，为无限离散消息集合，它们的出现概率分别为它们的出现概率分别为P(x1)=1/2，P(x2)=1/4，P(x3)=1/8，P(xi)=1/2i，。（。（1）用香农编码方法给出各个符号消息的代用香农编码方法给出各个符号消息的代码组；（码组；（2）计算该信源编码的效率。）计算该信源编码的效率。解解（1）信源消息的概率分布呈等比级数，按香农编码方法，其码）信源消息的概率分布呈等比级数，按香农编码方法，其码长集合为自然数数列长集合为自然数数列1,2,3,i,；对应的编码分别为：对应的编码分别为：0,10,110,111110(i 1个个1),。习题习题112/12/202214第五章第五章 信源编码信源编码 与本题有关的数据和编码结果列于下表。习题习题112/12/202215第五章第五章 信源编码信源编码习题习题1（2）先求熵和平均码长）先求熵和平均码长 12/12/202216第五章第五章 信源编码信源编码2.某信源具有某信源具有7个消息符号，其概率分别为：个消息符号，其概率分别为：0.20,0.19,0.18,0.17,0.15,0.10,0.01。欲对其进行香农方法的二进制编码，求其。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。二进制代码组及其编码效率。解解 先计算每一个码字的码长，分别为：先计算每一个码字的码长，分别为：3,3,3,3,3,4,7；再计；再计算累加概率。算累加概率。例如：例如：P4=p1+p2+p3=0.20+0.19=0.18=0.57，变换成二进变换成二进制数为：制数为：0.1001，因为，因为b4=3，故对于概率为故对于概率为0.17的消息符号的消息符号x4，其编码为其编码为100。依此类推，与本题有关的数据和编码结果列于下表。依此类推，与本题有关的数据和编码结果列于下表。习题习题212/12/202217第五章第五章 信源编码信源编码习题习题212/12/202218第五章第五章 信源编码信源编码可以求出其平均码长和信源熵分别为可以求出其平均码长和信源熵分别为3.14码元码元/符号和符号和2.16 比特比特/符号，故编码效率为符号，故编码效率为上述两个例子可见，香农编码方法对有的信源能够达到最佳编码上述两个例子可见，香农编码方法对有的信源能够达到最佳编码而有的则不能，因此还不能说它是最佳编码。而有的则不能，因此还不能说它是最佳编码。习题习题212/12/202219第五章第五章 信源编码信源编码香农编码方法特点香农编码方法特点：由于由于由于由于b bi i总是进一取整，香农编码方法不一定是最佳的；总是进一取整，香农编码方法不一定是最佳的；总是进一取整，香农编码方法不一定是最佳的；总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为由于第一个消息符号的累加概率总是为由于第一个消息符号的累加概率总是为由于第一个消息符号的累加概率总是为0 0，故它对应，故它对应，故它对应，故它对应的码字总是的码字总是的码字总是的码字总是0 0、0000、000000、0000的式样；的式样；的式样；的式样；码字集合是唯一的，且为即时码；码字集合是唯一的，且为即时码；码字集合是唯一的，且为即时码；码字集合是唯一的，且为即时码；先有码长再有码字；先有码长再有码字；先有码长再有码字；先有码长再有码字；对于一些信源，编码效率不高，冗余度稍大，因此其对于一些信源，编码效率不高，冗余度稍大，因此其对于一些信源，编码效率不高，冗余度稍大，因此其对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。实用性受到较大限制。实用性受到较大限制。实用性受到较大限制。评述评述12/12/202220第五章第五章 信源编码信源编码 3.试对概率分别为：试对概率分别为：0.20,0.19,0.18,0.17,0.15,0.10,0.01的信源用费诺编码方法，求其二的信源用费诺编码方法，求其二进制代码组及其编码效率。进制代码组及其编码效率。解先将消息符号按概率大小排列，再按步骤进解先将消息符号按概率大小排列，再按步骤进行子集分解，本题经过行子集分解，本题经过4次分解完成编码，整个次分解完成编码，整个过程列于下表过程列于下表习题习题312/12/202221第五章第五章 信源编码信源编码由上表的数据可得，代码组集合的平均长度为由上表的数据可得，代码组集合的平均长度为 =2.74 码元码元/符号符号编码效率为编码效率为可见，费诺方法的编码效率比香农编码方法要高。可见，费诺方法的编码效率比香农编码方法要高。习题习题312/12/202222第五章第五章 信源编码信源编码费诺编码特点费诺编码特点：概率大，则分解的次数小；概率小概率大，则分解的次数小；概率小,则分解的则分解的次数多。这符合最佳编码原则。次数多。这符合最佳编码原则。码字集合是唯一的。码字集合是唯一的。分解完了，码字出来了，码长也有了。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。因此，费诺编码方法又称为子集分解法。费诺编码方法比较适合于每次分组概率都很接费诺编码方法比较适合于每次分组概率都很接近的信源，特别是对每次分组概率都相等的信近的信源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。源进行编码时，可达到理想的编码效率。评述评述12/12/202223第五章第五章 信源编码信源编码 4.一个信源包含一个信源包含6个符号消息，它们的出现概率分别个符号消息，它们的出现概率分别为为0.3,0.2,0.15,0.15,0.1,0.1，信道基本符号为二进，信道基本符号为二进制码元，试用哈夫曼编码方法对该信源的制码元，试用哈夫曼编码方法对该信源的6个符号进个符号进行信源编码，并求出代码组的平均长度和信息传输速行信源编码，并求出代码组的平均长度和信息传输速率。率。解解 根据哈夫曼编码的步骤，可得其编码过程和编码根据哈夫曼编码的步骤，可得其编码过程和编码结果，如下图所示。结果，如下图所示。习题习题412/12/202224第五章第五章 信源编码信源编码习题习题412/12/202225第五章第五章 信源编码信源编码由编码结果，求得平均码长为由编码结果，求得平均码长为 =2.5码元码元/符号符号 信源熵为信源熵为 编码效率为编码效率为由此可得其编码效率为由此可得其编码效率为98.8%，接近于最佳编码。，接近于最佳编码。习题习题412/12/202226第五章第五章 信源编码信源编码5.已知一个信源的概率空间为已知一个信源的概率空间为试用三进制码元试用三进制码元0,1,2对该信源的各个消息进行哈夫曼编码。对该信源的各个消息进行哈夫曼编码。解解 这是多进制哈夫曼编码问题，其编码方法和二进制时基本相同，这是多进制哈夫曼编码问题，其编码方法和二进制时基本相同，即不断地将较小的概率相加并排队，只不过这里的基本分组应考即不断地将较小的概率相加并排队，只不过这里的基本分组应考虑虑M进制。进制。但在第一次组合时，可将概率最小和较小的但在第一次组合时，可将概率最小和较小的M或或(M 1,2)个个先组合，通过小概率参与组合次数的增加来减少大概率参与组合先组合，通过小概率参与组合次数的增加来减少大概率参与组合的次数。的次数。习题习题512/12/202227第五章第五章 信源编码信源编码设第一次组合的概率数取设第一次组合的概率数取 m0，考虑到第二次组合就应该使用考虑到第二次组合就应该使用M进进制，则制，则m0通常应满足通常应满足 =正整数的要求。正整数的要求。如果将如果将2个相加的概率按其大小分别赋予编码值个相加的概率按其大小分别赋予编码值“1”和和“0”（概（概率较大者赋率较大者赋“1”，小者赋，小者赋“0”，相等时则任意），相等时则任意），3个相加的概个相加的概率按其大小分别赋予编码值率按其大小分别赋予编码值“2”、“1”和和“0”，依此类推，就，依此类推，就可以得到类似于二进制时的哈夫曼编码结果。可以得到类似于二进制时的哈夫曼编码结果。习题习题512/12/202228第五章第五章 信源编码信源编码本例本例N=6、M=3。由于由于x5、x6的概率最小（均为的概率最小（均为0.1），），当取当取m0=2时，时，=，符合上述要求，故第一，符合上述要求，故第一 次组合取次组合取x5、x6；第二次组合将第二次组合将x3，x4和和x2的概率相加，其值为的概率相加，其值为0.5；第三次组合是这两组和第三次组合是这两组和x1概率之和已经为概率之和已经为1，完成编码，完成编码整个过程如下图所示，整个过程如下图所示，x1x6的编码结果分别为：的编码结果分别为：1,22,21,20,01,00。可以验证该结果也接近于最佳编码。可以验证该结果也接近于最佳编码。习题习题512/12/202229第五章第五章 信源编码信源编码习题习题512/12/202230第五章第五章 信源编码信源编码哈夫曼编码特点哈夫曼编码特点：由于哈夫曼编码总是以最小概率相加的方法来由于哈夫曼编码总是以最小概率相加的方法来“缩减缩减”参与排队参与排队的概率个数，因此概率越小，对缩减的贡献越大，其对于消息的的概率个数，因此概率越小，对缩减的贡献越大，其对于消息的码字也越长；码字也越长；最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，亦即具个消息符号有着相同概率的情况，将会有多种路径选择，亦即具有多种可能的代码组集合；有多种可能的代码组集合；尽管对同一信源存在着多种结果的哈夫曼编码，但它们的平均码尽管对同一信源存在着多种结果的哈夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此哈夫曼编码是最的方法，其实质都是遵循最佳编码的原则，因此哈夫曼编码是最佳编码。佳编码。哈夫曼编码是一种最佳编码，实现也不困难，因此到目前为止它哈夫曼编码是一种最佳编码，实现也不困难，因此到目前为止它仍是应用最为广泛的无失真信源编码之一。仍是应用最为广泛的无失真信源编码之一。评述评述12/12/202231第五章第五章 信源编码信源编码习题习题66.信源符号信源符号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)用哈夫曼编码编成三进变长码，计算其编码效率。用哈夫曼编码编成三进变长码，计算其编码效率。12/12/202232第五章第五章 信源编码信源编码习题习题6解:(1)H(X)=1.984412/12/202233第五章第五章 信源编码信源编码习题习题6xiP(xi)S1 S2S3S4S5S6S7 码字x11/20 0 x21/410 10 x31/810 110 x41/1610 1110 x51/3210 11110 x61/6410 111110 x71/12810 1111110 x81/1281 111111112/12/202234第五章第五章 信源编码信源编码习题习题6xiP(xi)S1S2S3S4码字x11/200 x21/41010 x31/8111x41/1620120 x51/321121x61/64201220 x71/12811221x81/128212/12/202235第五章第五章 信源编码信源编码习题习题612/12/202236第五章第五章 信源编码信源编码习题习题612/12/202237