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

1、10/23/20211第三章：第三章：信源编码（一）离散信源无失真编码3.1 信源及其分类信源及其分类3.2 离散无记忆（简单）信源的等长编离散无记忆（简单）信源的等长编码码3.3 离散无记忆（简单）信源的不等长离散无记忆（简单）信源的不等长编码编码3.4 最佳不等长编码最佳不等长编码3.5 算术编码和算术编码和lz编码编码10/23/202123.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码（顺序地叙述以下的概念）（1）不等长编码的优越性不等长编码的优越性 总体上减少码字的长度。（2）不等长编码的特殊问题不等长编码的特殊问题 唯一可译性，或者叫做可识别性。对于一个

2、码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过n的d元码，其码字个数小于d(dn-1)/(d-1)个。这是因为两个码字c(1)和c(2) 连接成的字母串c(1)c(2) 不能是码字）10/23/202133.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码平均码字长度。设信源随机变量u的概率分布为ak, p(ak), k=1k，事件ak对应的码字长度为nk，则平均码字长度为希望 小。解决方案：概率大的

3、事件用短码字。实时译码和容量限制。kkkkapnn1)(n10/23/202143.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码唯一可译性的两种解决方法唯一可译性的两种解决方法定义定义3.3.2(p51) 若事件与码字一一对应；每个码字的开头部分都是一个相同的字母串；这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码逗点码。定义定义3.3.4(p51) 若事件与码字一一对应；每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码异字头码。10/23/202153.3 离散无记忆（简单）信离

4、散无记忆（简单）信源的不等长编码源的不等长编码注解注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。见到一个码字就识别为一个码字。10/23/202163.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码例例 观察表3.3.1(p51)。码a不是唯一可译的。码b不是唯一可译的。码c是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码c是异字头码。码d是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实

5、际上，码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。10/23/202173.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码异字头码的第一种构造方法：异字头码的第一种构造方法：shannon-fano编码法编码法（d元编码，字母表为元编码，字母表为0, 1, , d-1） （1）将源随机变量的事件按概率从大到小排成一行。（2）将此行切分为d段，分别赋予标号“0”到

6、“d-1”，称为1级标号。（3）将每个非空段再切分为d段，分别赋予标号“0”到“d-1”，称为2级标号。（4）将每个非空段再切分为d段，分别赋予标号“0”到“d-1”，称为3级标号。10/23/202183.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码如此一直到每个段均含有至多一个事件为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。为了使平均码长小，每次切分段时应使d段的概率尽可能相近。（注解：当然可以把“切分段”操作换为“任意分组”操作，使d组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。 ）10/23/20

7、2193.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”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始

8、到最先标号为止的标号序列。（当然要去掉那些0概率事件和它们的标号序列） 10/23/2021103.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码（为什么shannon-fano码和huffman码都是异字头码？请看p58图3.4.1，p58图3.4.2。这些图都是树，称为码树，码树上的每个码字都在树梢。如果不是异字头码，则有的码字就不在树梢，而在中间节点。）定理定理3.3.1(kraft不等式，p53) 设信源随机变量共有k个事件。则：各码字长度分别为n1、n2、nk的d元异字头码存在的充分必要条件是11kknkd10/23/2021113.3 离散无记忆（简单）信

9、离散无记忆（简单）信源的不等长编码源的不等长编码证明 不妨设n1n2nk。则各码字长度分别为n1、n2、nk的d元异字头码存在；当且仅当：存在这样一个d叉树，树上有n1级、n2级、nk级树梢；当且仅当：nk级d叉满树满树有不存在上下关系不存在上下关系的n1级、n2级、nk级节点；当且仅当： nk级d叉满树满树的树梢数量不小于;21kkkknnnnnndddknnnddd211当且仅当：10/23/2021123.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码定理定理3.3.2(p53) （设信源随机变量共有k个事件）。则：一个唯一可译的、各码字长度分别为n1、n2、n

10、k的d元不等长码存在的充分必要条件是11kknkd10/23/2021133.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码定理定理3.3.3(p54)duhnlog)(1log)(duhn任一唯一可译的d元不等长码总满足存在唯一可译的d元不等长码满足10/23/2021143.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码证明 设信源随机变量u的概率分布为如果唯一可译的d元不等长码的码字长度为则kkqqqaaau212101log) 1(loglnlogloglog1loglog)(111111kknkkknkkkknkkkknkkkkkk

11、kkkkkkkdeqdqeqdqeqdqdnqqqdnuhkknnnaaa212110/23/2021153.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码因此 。另一方面，取n1、n2、nk，则：由于 ，存在码字长度为 的唯一可译的d元不等长码。duhnlog)()log)(1,(duhnkkdqknk，则若kkdqdkknkn1,) 1(111kkkkknqdkkknnnaaa212110/23/2021163.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码但此时dndnqdqqquhkkkkkknkkkkkkloglog) 1(log1

12、log)(11111log)(duhn因此10/23/2021173.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码定理3.3.3的结论的推广(p55) 现在对信源随机向量ul=(u1u2ul)做唯一可译的d元不等长码。此时ul的事件的个数为kl。则任一唯一可译的d元不等长码总满足存在唯一可译的d元不等长码满足dulhduhunlllog)(log)()(1log)(1log)()(dulhduhunll10/23/2021183.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码重新定义平均码长：任一唯一可译的d元不等长码总满足存在唯一可译的d

13、元不等长码满足duhnlog)(lduhn1log)(lunnl)(10/23/2021193.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长编码源的不等长编码定义编码速率r和编码效率分别为 任一唯一可译的d元不等长码总满足存在唯一可译的d元不等长码满足dnldunrlloglog)()(uhr lduhrlog)(注解注解 不等长编码与等长编码具有相似的性质：当不等长编码与等长编码具有相似的性质：当l增大时，对增大时，对ul的编的编码可以使用更短的平均码长，因而更加节省码可以使用更短的平均码长，因而更加节省编码速率。但编码速率。但节省节省编码编码速率的下限是速率的下限是h(u)。ruh)(10/23/2021203.3 离散无记忆（简单）信离散无记忆（简单）信源的不等长