第三章：信源编码（一） 离散信源无失真编码3.1 信源及其分类 3.2 离散无记忆（简单）信源的等长编 码 3.3 离散无记忆（简单）信源的不等长 编码 3.4 最佳不等长编码 3.5 算术编码和LZ编码2018/7/1213.3 离散无记忆（简单）信源 的不等长编码（顺序地叙述以下的概念） （1）不等长编码的优越性 总体上减少码字的长度。 （2）不等长编码的特殊问题 唯一可译性，或者叫做可识别性。对于一个码，如果存在 一种译码方法，使任意若干个码字所组成的字母串只能唯 一地被翻译成这几个码字所对应的事件序列。这个码就被 称为是唯一可译的。 解决方案：适当地编码，使得每个码字都具有识别标记。 （注解：一个唯一可译的、码字长度不超过N的D元码，其码 字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2) 连接成的字母串c(1)c(2) 不能是码字）Date23.3 离散无记忆（简单）信源 的不等长编码平均码字长度。设信源随机变量U的概率分布为ak, p(ak), k=1K，事件ak对应的码字长度为nk，则平均码字长度为希望 小。 解决方案：概率大的事件用短码字。 实时译码和容量限制。Date33.3 离散无记忆（简单）信源 的不等长编码唯一可译性的两种解决方法 定义3.3.2(p51) 若 事件与码字一一对应； 每个码字的开头部分都是一个相同的字母串； 这个字母串仅仅出现在码字的开头，不出现在码字的其 它部位，也不出现在两个码字的结合部。 则称这个字母串为逗号，称此码为逗点码。 定义3.3.4(p51) 若事件与码字一一对应； 每个码字都不是另一个码字的开头部分（字头）。 则称此码为异字头码。Date43.3 离散无记忆（简单）信源 的不等长编码注解 逗点码显然是唯一可译的，识别码字的方法为： 见到逗号就识别为一个码字的开始。 异字头码也是唯一可译的，识别码字的方法为： 见到一个码字就识别为一个码字。Date53.3 离散无记忆（简单）信源 的不等长编码例 观察表3.3.1(p51)。 码A不是唯一可译的。码B不是唯一可译的。 码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一 个码字的结束。实际上，码C是异字头码。 码D是唯一可译的，识别码字的方法为：见“0”就是一个码字 的开始。实际上，码D是逗点码，其中“0”是逗号。 码C不是逗点码。码D不是异字头码。 码C的平均码长比码D的平均码长小： 码C的平均码长为10.5+20.25+30.125+30.125=1.75； 码D的平均码长为10.5+20.25+30.125+40.125=1.875。Date63.3 离散无记忆（简单）信源 的不等长编码异字头码的第一种构造方法：Shannon-Fano编码法 （D元编码，字母表为0, 1, , D-1） （1）将源随机变量的事件按概率从大到小排成一行。 （2）将此行切分为D段，分别赋予标号“0”到“D-1”，称为1 级标号。 （3）将每个非空段再切分为D段，分别赋予标号“0”到“D- 1”，称为2级标号。 （4）将每个非空段再切分为D段，分别赋予标号“0”到“D- 1”，称为3级标号。 。Date73.3 离散无记忆（简单）信源 的不等长编码如此一直到每个段均含有至多一个事件为止。 此时，一个事件的码字就是这个事件所在的段的标号序列 ，从1级标号到末级标号。为了使平均码长小，每次切分段时应使D段的概率尽可能相 近。 （注解：当然可以把“切分段”操作换为“任意分组”操作，使 D组的概率尽可能相近。这样可以使平均码长更小。但是 ，这不是一种有效的操作。 ）Date83.3 离散无记忆（简单）信源 的不等长编码异字头码的第二种构造方法：Huffman编码法 （D元编码，字母表为0, 1, , D-1） （0）如果源随机变量的事件的个数K不是(D-1)的倍数加1， 则添加若干0概率事件使得事件的个数是(D-1)的倍数加1 。 （1）将概率最小的D个事件分别赋予标号“0”到“D-1”。 （2）将这D个事件合并为一个事件，其概率为这D个事件概 率之和。 重复（1）-（2），直到事件的个数等于D。 将这D个事件分别赋予标号“0”到“D-1”。 编码完毕。此时，一个事件的码字是这个事件从最后标号开 始到最先标号为止的标号序列。 （当然要去掉那些0概率事件和它们的标号序列） Date93.3 离散无记忆（简单）信源 的不等长编码（为什么Shannon-Fano码和Huffman码都是异字头码？请看 p58图3.4.1，p58图3.4.2。这些图都是树，称为码树，码树 上的每个码字都在树梢。如果不是异字头码，则有的码字 就不在树梢，而在中间节点。）定理3.3.1(Kraft不等式，p53) 设信源随机变量共有K个事件 。则：各码字长度分别为n1、n2、nK的D元异字头码 存在的充分必要条件是Date103.3 离散无记忆（简单）信源 的不等长编码证明 不妨设n1n2nK。则 各码字长度分别为n1、n2、nK的D元异字头码存在； 当且仅当：存在这样一个D叉树，树上有n1级、n2级、nK 级树梢； 当且仅当：nK级D叉满树有不存在上下关系的n1级、n2级、 、nK级节点； 当且仅当： nK级D叉满树的树梢数量不小于Date113.3 离散无记忆（简单）信源 的不等长编码定理3.3.2(p53) （设信源随机变量共有K个事件）。则 ：一个唯一可译的、各码字长度分别为n1、n2、 、nK的D元不等长码存在的充分必要条件是Date123.3 离散无记忆（简单）信源 的不等长编码定理3.3.3(p54)任一唯一可译的D元不等 长码总满足存在唯一可译的D元不等长 码满足Date133.3 离散无记忆（简单）信源 的不等长编码证明 设信源随机变量U的概率分布为如果唯一可译的D元不等长码的码字长度为则Date143.3 离散无记忆（简单）信源 的不等长编码因此 。另一方面，取n1、n2、nK，则：由于 ，存在码字长度为的唯一可译的D元不等长码。Date153.3 离散无记忆（简单）信源 的不等长编码但此时Date163.3 离散无记忆（简单）信源 的不等长编码定理3.3.3的结论的推广(p55) 现在对信源随机向量 UL=(U1U2UL)做唯一可译的D元不等长码。此时UL的事件 的个数为KL。则任一唯一可译的D元不等 长码总满足存在唯一可译的D元不等长 码满足Date173.3 离散无记忆（简单）信源 的不等长编码重新定义平均码长：任一唯一可译的D元不等 长码总满足存在唯一可译的D元不等长 码满足Date183.3 离散无记忆（简单）信源 的不等长编码定义编码速率R和编码效率分别为 任一唯一可译的D元不等 长码总满足存在唯一可译的D元不等长 码满足注解 不等长编码与等长编码具有相似的性质：当L增大时，对UL的 编码可以使用更短的平均码长，因而更加节省编码速率。但节省 编码速率的下限是H(U)。Date193.3 离散无记忆（简单）信源 的不等长编码例3.3.1（见p56）做2元编码。设 ；H(U)=0.811。U概率码字平均码长编码 速率编码 效率a13/40(13/4+ 11/4)/1=110.811a21/41U2概率码字平均码长编码 速率编码 效率a1a19/160(19/16+ 23/16+ 33/16+ 31/16)/2 =27/3227/320.961a1a23/1610a2a13/16110a2a21/16111Date20