信息论与编码-信源编码-习题课件.ppt

当你为错过太阳而流泪时，你也将错过群星了。 －泰戈尔 ;信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。;香农编码;香农编码;费诺编码;将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。;在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有m个信源符号。非全树时，有s个码字不用： 第一次对最小概率符号分配码元时就只取(m－s)个，分别配以0,1,…,m－s－1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。 以后每次就可以取m个符号，分别配以0,1,…,m－1；…；如此下去，直至所有概率相加得1为止，即得到各符号的m进制码字。;香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高； 费诺码和哈夫曼码的编码方法都不惟一； 费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编m进制码，但m越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用； 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。;游程变换减弱了原序列符号间的相关性。 游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。 编码方法： 首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源； 对新的信源（游程序列）进行哈夫曼编码。 多元序列也可以变换成游程序列，如m元序列可有m种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是m种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。;L－D编码方法是一种分帧传送的方式； 编码方法 在冗余位序列中取N个符号作为一帧，编成一个码字，码字中含有信息位的数量和位置信息，在接收端依据这些信息进行译码； 每个码字传送两个数：Q和T，由下式计算;Q的位数： T的位数： 总位数：;寻找某一值K 若 再找某一值L;我们学习了6种信源编码：香农编码、费诺编码、哈夫曼编码、冗余编码、游程编码。 游程编码是非分组编码； 本章介绍的都是离散信源变长编码。 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。; 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, ···, 111…110 ( i – 1个1), ···。;;习题1;2. 某信源具有7个消息符号，其概率分别为：0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。 　解 先计算每一个码字的码长，分别为：3