西南交通大学：《信息论与编码》课程教学资源（PPT课件讲稿）第二章 信源编码（3/3）

离散无记忆(简单)信源的不等长编码 不等长编码的优越性总体上减少码字的长度。 不等长编码的特殊问题 ①唯一可译性,或者叫做可识别性。对于一个码,如果 存在一种译码方法,使任意若干个码字所组成的字母串 只能唯一地被翻译成这几个码字所对应的事件序列。这 个码就被称为是唯一可译的 解决方案:适当地编码,使得每个码字都具有识别标记。 (注解:一个唯一可译的、码字长度不超过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元不等长 码满足

离散无记忆(简单)信源的不等长编码 现在对信源随机向量U=(U1U2…U)做唯一可译的D元不等长码。 此时U的事件的个数为K。则 任一唯一可译的D元不等长存在唯一可译的D元不等长 码总满足 码满足 n(U)≥ H(U H(UL n(U)< +1 log D log D LH(O) LH(U log D 108D xI

离散无记忆（简单）信源的不等长编码 现在对信源随机向量UL=(U1U2…UL )做唯一可译的D元不等长码。 此时UL的事件的个数为KL。则 任一唯一可译的D元不等长 码总满足 存在唯一可译的D元不等长 码满足 D LH U D H U n U L L log ( ) log ( ) ( ) =  1 log ( ) 1 log ( ) ( ) = +  + D LH U D H U n U L L

离散无记忆(简单)信源的不等长编码 重新定义平均码长: n= n(UrL L 任一唯一可译的D元不等长存在唯一可译的D元不等长 码总满足 码满足 H(U) 分_H() log D log D L

离散无记忆（简单）信源的不等长编码 重新定义平均码长： 任一唯一可译的D元不等长 码总满足 存在唯一可译的D元不等长 码满足 D H U n log ( )  D L H U n 1 log ( )  + L n U n L ( ) =

离散无记忆(简单)信源的不等长编码 定义编码速率R和编码效率分别为 ≈(U4)logD H(U g D 7 L R 任一唯一可译的D元不等长存在唯一可译的D元不等长 码总满足 码满足 log D R≥H() R<H(U)+ 注解不等长编码与等长编码具有相似的性质:当L增大时,对U的编 码可以使用更短的平均码长,因而更加节省编码速率。但节省编码 速率的下限是H(U

离散无记忆（简单）信源的不等长编码 定义编码速率R和编码效率η分别为 任一唯一可译的D元不等长 码总满足 存在唯一可译的D元不等长 码满足 n D L n U D R L log ( )log = = R  H(U) L D R H U log  ( ) + 注解 不等长编码与等长编码具有相似的性质：当L增大时，对UL的编 码可以使用更短的平均码长，因而更加节省编码速率。但节省编码 速率的下限是H(U)。 R H (U )  =

离散无记忆(简单)信源的不等长编码 例做2元编码。设U={31414;H(U)=0.811 U概率码字平均码长编码速率编码效率 3/4 0 (1×3/4+ 0.811 1/4 1×1/4)/1=1 U2概率码字平均码长编码速率编码效率 9/16 0 (1×9/16+ 27/32 0.961 2×3/16+ 1a2 3/16 3×3/16+ aa306103×1/62 aDd 1/16 111 =27/32

离散无记忆（简单）信源的不等长编码 例 做2元编码。设 ；H(U)=0.811。 U 概率 码字 平均码长 编码速率 编码效率 a1 3/4 0 (1×3/4+ 1×1/4)/1=1 1 0.811 a2 1/4 1 U2 概率 码字 平均码长 编码速率 编码效率 a1a1 9/16 0 (1×9/16+ 2×3/16+ 3×3/16+ 3×1/16)/2 =27/32 27/32 0.961 a1a2 3/16 10 a2a1 3/16 110 a2a2 1/16 111 U={3/4,1/4}