第三章离散无失真信源编码.ppt

第三章 离散信源无失真编码 ;用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、费诺编码法和霍夫曼编码法。 ;§3.1 概 述 ;信源编码的概念：对信源的原始符号序列按一定的数学规则映射成由码符号组成的码序列的过程 。;信源编码模型：;【例3.1.1】中文电报编码： ;二．码的分类;;;2．原码C的N次扩展码;3．惟一可译码（Uniquely decodable code） ;d ;定理：D进制码集合C ={c1，c2， …， cM }，码集中每一ci（i = 1, 2, …, M）都是一个D进制符号串，设c1，c2，…，cM 对应的码长分别是n1，n2，…，nM，则存在惟一可译码的充要条件是 ;码1，码长组合为{1，1，1，2}，2-1×3+2-2=1.751，不满足Kraft不等式，故不是单义可译码； 码2的码长组合为{1，1，2，2}，不满足Kraft不等式，故也不是单义可译码； 码3的码长组合为{2，2，2，2，}，2-2×4=1，满足Kraft不等式，但还不能确定其是否为单义可译码。又因为码3是异前缀码，故是单义可译码； 再如，码{0，11，100，110}，码长组合满足Kraft不等式，但不是单义可译码，‘110’可译为‘d’，也可译为‘ba’；如果将该码的编码方法稍加改变为{0，10，110，111}，即为单义可译码，又还是异前缀码，故还是即时码。;4．即时码;码的树图构造;码的分类结构图;三．平均码长的计算;【例3.1.5】计算下表各码的平均码长： ;四．信息传输率;【例3.1.6】给定信源;§3.2 等长码及等长编码定理 ;下面的定理将说明，当满足一定的条件时，在L →∞时，失真pe →0 。;二．编码速率（码率）;三．编码效率;根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故取n1=n2=2。并做如下编码： ，得到唯一可译码。 ;编码效率为： ;编码效率： ;§3.3 变长码及变长编码定理 ;二．变长编码定理 ;【例3.3.1】;其L次扩展信源 的熵记为 ;编码效率： ;【例3.3.2】已知离散无记忆信源; 对X2进行二进制变长编码;③ 对X3进行二进制变长编码 ;常用变长编码;记离散信源 ;编码步骤：;【例3.4.1】对给定信源进行D =2进制香农编码并求编码效率。;（2）求编码效率;费诺编码法的具体步骤如下： ;【例3.4.2】对给定信源进行D =2进制费诺编码并求编码效率。;1. 霍夫曼编码法的具体步骤如下：（先考虑D =2的情况）;【例3.4.3】对给定信源进行D =2进制霍夫曼编码并求编码效率。 ;信源熵： ;D进制霍夫曼编码法的具体步骤：（D 2的情况）;本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。;二．变长编码定理(Shannon第一定理)