第5章信源编码李伟.pptVIP

第五章 无失真信源编码 ;信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。;信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编??的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。;第二节 码的分类;1、二元码： 码符号集X={0,1}，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。 2、等长码： 若一组码中所有码字的长度都相同，称为等长码。 3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。 4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。 ;5、奇异码： 若一组码中有相同的码字，称为奇异码。 6、码的N次扩展： 若码 ， 码 则称码B为 码C的N次扩展码。 7、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为唯一可译码。 ;① 唯一可译变长码与即时码; 码1是一个奇异码，不是唯一可译码；码2也不是唯一可译码，因为收到一串序列时，无法唯一译出对应的原符号序列，如0100，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；码3和码4都是唯一可译的。 但码3和码4也不太一样，码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当受到一个或几个码是，必须参考后面的码才能作出判断。 定义，在唯一可译码中，有一类码，它在译码时无须参考后面的码字就可以作出判断，这种码称为即时码。;定义：如果一个码组中的任一个码字都不是另一个码字的续长，则称为即时码。 ;② 即时码的树图构造法; 在每个节点上都有r个分枝的树称为整树，否则称为非整树。 ;③ 克拉夫特（Kraft）不等式;定理5.6 若存在一个码长为 唯一可译码，则一定存在一个同样长度的即时码。 这说明，其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时，只需要讨论即时码就可以了。 ;例：如果有四个信源符号{s1，s2，s3，s4}，采用二元编码，l=2，则可以编成s1=00，s2=01，s3=10，s4=11。;; 我们举例说明： 设信源;若不考虑符号间的依赖关系，可得码长l＝2 若考虑符号间的依赖关系，则对此信源作二次扩展;;定理5.3（等长信源编码定理） 一个熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意 大于0，只要满足;定理5.3的条件式可写成：;最佳编码效率为：;例：设离散无记忆信源：;设信源;; 这个定理是香农信息论中非常重要得一个定理，它指出，在二元编码中，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。 ;由;无噪信道编码定理 若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错的以最大信息传输率C传输信息，若R大于C，则无差错传输是不可能的。;例：;第五节 香农编码;第五节 香农编码;第五节 香农编码;第六节 费诺编码;第六节 费诺编码;第六节 费诺编码;第六节 费诺编码;第七节 霍夫曼编码;第七节 霍夫曼编码——编码步骤;第七节 霍夫曼编码——二进制哈夫曼编码;第七节 霍夫曼编码——二进制哈夫曼编码;第七节 霍夫曼编码——二进制哈夫曼编码;信源熵为： 平均码长为 编码效率为 若采用定长编码，码长K=3，则编码效率 可见哈夫曼的编码效率提高了12.7%。;第七节 霍夫曼编码——