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

第三章：信源编码（一）

离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码§3.5算术编码和LZ编码2026/6/41§3.3离散无记忆（简单）信源的不等长编码（顺序地叙述以下的概念）（1）不等长编码的优越性总体上减少码字的长度。（2）不等长编码的特殊问题

①唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字）2026/6/42§3.3离散无记忆（简单）信源的不等长编码②平均码字长度。设信源随机变量U的概率分布为{ak,p(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：概率大的事件用短码字。③实时译码和容量限制。2026/6/43§3.3离散无记忆（简单）信源的不等长编码唯一可译性的两种解决方法定义3.3.2(p51)若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。定义3.3.4(p51)①若事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。2026/6/44§3.3离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。2026/6/45§3.3离散无记忆（简单）信源的不等长编码如此一直到每个段均含有至多一个事件为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。为了使平均码长小，每次切分段时应使D段的概率尽可能相近。（注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。）2026/6/48§3.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概率事件和它们的标号序列）2026/6/49§3.3离散无记忆（简单）信源的不等长编码（为什么Shannon-Fano码和Huffman码都是异字头码？请看p58图3.4.1，p58图3.4.2。这些图都是树，称为码树，码树上的每个码字都在树梢。如果不是异字头码，则有的码字就不在树梢，而在中间节点。）定理3.3.1(Kraft不等式，p53)设信源随机变量共有K个事件。则：各码字长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是2026/6/410§3.3离散无记忆（简单）信源的不等长编码证明不妨设n1≤n2≤…≤nK。则各码字长度分别为n1、n2、…、nK的D元异字头码存在；当且仅当：存在这样一个D叉树，树上有n1级、n2级、…、nK级树梢；当且仅当：nK级D叉满树有不存在上下关系的n1级、n2级、…、nK级节点；当且仅当：nK级D叉满树的树梢数量不小于2026/6/411§3.3离散无记忆（简单）信源的不等长编码定理3.3.2(p53)（设信源随机变量共有K个事件）。则：一个唯一可译的、各码字长度分别为n1、n2、…、nK的D元不等长码存在的充分必要条件是2026/6/412§3.3离散无记忆（简单）信源的不等长编码定理3.3.3(p54)任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2026/6/413§3.3离散无记忆（简单）信源的不等长编码证明设信源随机变量U的概率分布为如果唯一可译的D元不等长码的码字长度为则2026/6/414§3.3离散无记忆（简单）信源的不等长编码因此。另一方面，取n1、n2、…、nK，则：由于，存在码字长度为的唯一可译的D元不等长码。2026/6/415§3.3离散无记忆（简单）信源的不等长编码但此时2026/6/416§3.3离散无记忆（简单）信源的不等长编码定理3.3.3的结论的推广(p55)现在对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2026/6/417§3.3离散无记忆（简单）信源的不等长编码重新定义平均码长：任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2026/6/418§3.3离散无记忆（简单）信源的不等长编码定义编码速率R和编码效率η分别为

任一唯一可译的D元不等