离散无记忆(简单)信源的不等长编码 不等长编码的优越性总体上减少码字的长度。 不等长编码的特殊问题 ①唯一可译性,或者叫做可识别性。对于一个码,如果 存在一种译码方法,使任意若干个码字所组成的字母串 只能唯一地被翻译成这几个码字所对应的事件序列。这 个码就被称为是唯一可译的 解决方案:适当地编码,使得每个码字都具有识别标记。 (注解:一个唯一可译的、码字长度不超过N的D元码,其 码字个数小于D(D-1)(D1)个。这是因为两个码字c1)和 c2)连接成的字母串c)c2)不能是码字)
离散无记忆（简单）信源的不等长编码 ◼ 不等长编码的优越性 总体上减少码字的长度。 ◼ 不等长编码的特殊问题 ①唯一可译性，或者叫做可识别性。对于一个码，如果 存在一种译码方法，使任意若干个码字所组成的字母串 只能唯一地被翻译成这几个码字所对应的事件序列。这 个码就被称为是唯一可译的。 解决方案：适当地编码，使得每个码字都具有识别标记。 （注解：一个唯一可译的、码字长度不超过N的D元码，其 码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c (1)和 c (2) 连接成的字母串c (1)c (2) 不能是码字）
离散无记忆(简单)信源的不等长编码 ②平均码字长度。设信源随机变量U的概率分布为{a2p(a) k=1~K},事件a对应的码字长度为n,则平均码字长度为 n=∑mkP(ak) k=1 希望n小 解决方案:概率大的事件用短码字。 ③实时译码和容量限制
离散无记忆（简单）信源的不等长编码 ②平均码字长度。设信源随机变量U的概率分布为{ak , p(ak ), k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为 希望 小。 解决方案：概率大的事件用短码字。 ③实时译码和容量限制。 = = K k n nk p ak 1 ( ) n
离散无记忆(简单)信源的不等长编码 唯一可译性的两种解决方法 逗点码 ①事件与码字一一对应; ②每个码字的开头部分都是一个相同的字母串; ③这个字母串仅仅出现在码字的开头,不出现在码字的其 它部位,也不出现在两个码字的结合部。 则称这个字母串为逗号,称此码为逗点码。 异字头码 ①若事件与码字一一对应; ②每个码字都不是另一个码字的开头部分(字头)。 则称此码为异字头码。 2005-7-18 4
2005-7-18 4 离散无记忆（简单）信源的不等长编码 唯一可译性的两种解决方法 ◼ 逗点码 ①事件与码字一一对应； ②每个码字的开头部分都是一个相同的字母串； ③这个字母串仅仅出现在码字的开头，不出现在码字的其 它部位，也不出现在两个码字的结合部。 则称这个字母串为逗号，称此码为逗点码。 ◼ 异字头码 ①若事件与码字一一对应； ②每个码字都不是另一个码字的开头部分（字头）。 则称此码为异字头码
离散无记忆(简单)信源的不等长编码 注解 逗点码显然是唯一可译的,识别码字的方法为: 见到逗号就识别为一个码字的开始 异字头码也是唯一可译的,识别码字的方法为: 见到一个码字就识别为一个码字
离散无记忆（简单）信源的不等长编码 注解 逗点码显然是唯一可译的，识别码字的方法为： 见到逗号就识别为一个码字的开始。 异字头码也是唯一可译的，识别码字的方法为： 见到一个码字就识别为一个码字
离散无记忆(简单)信源的不等长编码 任一唯一可译的D元不等长存在唯一可译的D元不等长 码总满足 码满足 H(U) > 今_H(U) +1 log D log D
离散无记忆（简单）信源的不等长编码 D H U n log ( ) 1 log ( ) + D H U n 任一唯一可译的D元不等长 码总满足 存在唯一可译的D元不等长 码满足