信息理论与编码4详解.ppt

信息理论与编码 第4章 离散无记忆信源无失真编码 第4章 离散无记忆信源无失真编码 信息传输系统编码和译码示意图 本章主要内容 4.1 信源编码概论 4.2 码的唯一可译性 4.3 定长编码定理和定长编码方法 4.4 变长编码定理 4.5 变长编码方法 4.6 几种实用的无失真信源编码 4.1 信源编码概论 信源编码器示意图 定长编码和变长编码 平均码长 编码效率 4.2 码的唯一可译性 4.2.1 常见码及其唯一可译性 4.2.2 码树和Kraft 不等式 4.2.1 常见码及其唯一可译性 唯一可译码和非唯一可译码 码W 是唯一可译码的充分必要条件 奇异码和非奇异码 非续长码和续长码 及时码或立即码 各种码的关系 4.2.2 码树和Kraft 不等式 码树 非续长码可用码树表示。 码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点。 经过 l 根树枝才能到达的节点称为 l 阶节点。 向上不长出树枝的节点称为终端节点或端点。 r 进制码树各节点（包括树根）向上长出的树枝数不会超过r ，若等于r 则称为整树。 4.3 定长编码定理和定长编码方法 定长编码惟一可译条件 定长无失真编码定理 4.4 变长编码定理 无失真变长编码定理（香农第一定理） 用r 元符号表对离散无记忆信源U 的N 长符号序列进行变长编码，记N 长符号序列对应的平均码长为 ，那么，要做到无失真编码，平均码长必须满足 4.5 变长编码方法 最佳码 对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码。 本节介绍三种变长编码方法：霍夫曼编码、费诺编码以及香农编码。其中只有霍夫曼编码是真正意义下的最佳编码。 本节主要内容 4.5.1 霍夫曼编码 4.5.2 费诺编码 4.5.3 香农编码 4.5.1 霍夫曼编码 二进制霍夫曼编码 编码效果分析 r进制霍夫曼编码 符号序列的霍夫曼编码 4.5.2 费诺编码 费诺编码的步骤 费诺编码的基本特点 4.5.3 香农编码 香农编码二进制编码步骤 （1）将信源符号按概率从大到小的排序； （2）按下式求i 个信源符号对应的码长 ，并取整； （3）按下式求i 个信源符号的累加概率 ； （4）将累加概率 转换成二进制数； （5）取 二进制数小数点后 个二进制数字作为第i 个信源符号的码字。 4.6 几种实用的无失真信源编码 4.6.1 游程编码 4.6.2 算术编码 4.6.3 基于字典的编码 4.6.1 游程编码 游程编码基本原理 MH 码 MH 码编码规则 MH 码与霍夫曼码存在的差异 4.6.2 算术编码 编码过程 将各信源符号序列依累积概率分布函数的大小映射到[0,1)区间，将[0,1)区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。 为达到与信源符号序列在概率上的匹配，选取编码的码长与信源序列的概率成反比，即取码长l 为 其中: 表示信源符号序列 的概率，符号 表示取大于或等于该值的最小整数。 4.6.3 基于字典的编码 LZ 编码的基本原理 LZW 码 可求出费诺编码的平均码长和编码效率 码元/符号 bit/符号 如对该信源进行霍夫曼编码， 码元/符号 费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。因此，费诺编码不是平均码长最短意义下的最佳编码，可将其看作准最佳编码。 费诺编码的基本特点 （1）费诺编码在构造码树时，是从树根开始到终端节点结束，这与霍夫曼编码相反； （2）由于赋码元时的任意性，因此费诺编码编出的码字也不唯一； （3）费诺编码虽属概率匹配范畴，但并未严格遵守匹配规则，因此平均码长一般不会最小。 例 设信源有7个符号，其二进制香农编码过程如下。 符号 概率 累加概率 自信息量 码长 码字 1111110 7 6.66 0.99 0.01 1110 4 3.34 0.89 0.10 101 3 2.74 0.74 0.15 100 3 2.