动机
信源产生某些符号的频率可能远高于其他符号。为常见符号使用较短描述可以降低平均长度,但接收者仍须知道每个描述在哪里结束。前缀码保证明确的边界。在这里讨论的有限情形中,熵与单个符号的最优平均长度之差小于一比特。
定义
定义 3.1.1
(二元熵)
设信源产生 个符号之一,概率为 且 。概率为零的符号可从有限列表中省略。其二元熵为
定义 3.1.2
(前缀码)
二元码给每个符号分配不同的有限二进制字。第 个字的长度为 ,平均长度为 。若任何码字都不是另一个不同码字的前缀,称码为前缀码。只在码中仅有一个字时允许空字。非空字的前缀码可从左到右译码:一旦识别出码字就停止,前缀条件保证它不会只是更长码字的开头。若唯一的码字为空字,接收者必须另行知道发送了多少个符号。
定理/命题
定理 3.1.3
(Kraft 不等式)
有限二元前缀码的长度满足 。反之,任何满足此不等式的有限个非负整数长度都能由某个二元前缀码实现。
定理 3.1.4
(熵与平均长度)
任何有限二元前缀码的平均长度 满足 。并且存在前缀码满足 。
证明思路
证明
(Kraft 不等式的二进区间证明)
长度为 的二元字对应 中长度为 的二进区间:它的比特确定 等分区间之一。若有限码是前缀码,这些区间两两不交,长度之和至多为一,得到必要不等式。
反过来,将给定长度按非递减次序排列。从零开始依次放置长度为 的区间。放置第 个区间之前,前面长度的总和是 的整数倍,因为此前的区间都对应更粗或相同的二进划分。因此新区间本身是要求深度的二进区间。Kraft 不等式保证所有区间都在 中。它们的二元标记构成前缀码:一个二进区间包含另一个,当且仅当其标记是后者标记的前缀。空字对应整个区间,所以只能是唯一的码字。
证明
(散度与向上取整的长度)
为证明熵下界,先使用 时的 。对 求导可知它在 取得最小值。若 是等长的正概率向量,则
证明:对 应用不等式,乘以 并求和,得到 。
对前缀码长度令 、。则 是正概率向量,且
为证明上界,取 。于是 ,Kraft 不等式保证存在这些长度的前缀码。又因 ,乘以 求和即得 。下界也适用于该码。这是单符号结论,不声称每个码都达到熵,也不声称某个具体信源模型已得到验证。
证明透视
前缀条件贡献了什么
下界只通过 Kraft 不等式 用到前缀条件;此后论证只涉及两个概率向量。不明显的一步是把二进权重归一化为 ,使散度不等式可以应用。归一化的代价恰为 ,由于 它非负;每个 都为正,则保证每个对数有限。
上界的方向相反。向上取整的长度 满足 ,所以其 Kraft 和至多为 ,而产生码的是 Kraft 定理的逆向部分;严格不等式来自 。若没有前缀条件, 可以超过一, 变为负数,这正是常见错误中的反例逃出该界的方式。
为什么均匀分布的熵最大
定理 3.1.5
(均匀分布使熵最大)
对 个正概率,。上界恰由均匀分布达到。
证明
(与均匀分布比较)
对 个正概率,将 与均匀分布 比较。散度不等式给出
因此 。下界是因为 ,每项 非负。上界恰在均匀分布时取等号: 只有在 时取等号,所以每个 都必须为一。若 ,唯一概率为一,熵为零。
分块编码与独立性的作用
定理 3.1.6
(分块编码趋近熵)
若 个信源符号独立同分布,分布为 ,则长度为 的块的熵为 ,并且存在块的前缀码,其平均长度 满足 。
证明
(块熵与每符号码率)
假设 个信源符号独立同分布,各符号概率为 。把每个长度为 的序列看成扩充字母表中的一个符号,它的概率是各坐标概率的乘积。块熵为
最后一个等式可将对数展开成 项;每一项对其他坐标的概率求和均为一,留下 。乘积公式依赖独立性。如果重复符号完全相关,块熵可以远小于 。
对有限块字母表应用前述构造,其平均码长 满足
因此每个原始符号的平均比特数随块长增长而趋近熵。这是对每个有限块长的码的存在性结论,不是计算成本、内存、延迟或模型错误时性能的界。所有概率均为正时,块字母表有 个可能序列,直接查表可能增长很快。
前缀码作为树
概念视角组合
用数叶子理解 Kraft 不等式
有限二元前缀码可画成有根二叉树:从根开始,0 走左边,1 走右边。码字标记选定节点,前缀性说明任何选定节点都不是另一个的祖先。删去未使用的后代后,可把码字视为叶。取深度 ,长度为 的码字有 个后代。这些后代集合互不相交,且均在深度 的 个节点中。两边除以 便再次得到 Kraft 不等式。
树的图像还说明 的情形:深度 的一些叶没有使用。并非每个内部节点都需要两个被使用的子节点。添加未使用的字以补全树会改变消息字母表,编码原有符号并不需要这样做。
等号与约定
定理 3.1.7
(熵界的等号情形)
单符号前缀码满足 ,当且仅当对每个符号都有 。
证明
(两项松弛都必须为零)
下界证明把可能的差距分成两部分:
右边两项都非负,所以取等号必须有 且 。由 的等号条件,后者意味着所有 。合起来得到每个符号的 。反过来,若每个概率都等于其码长对应的二进权重,直接代入即得 。因此逐个编码信源符号的前缀码达到下界,当且仅当概率与一个填满容量的前缀长度列表的二进权重一致。
只有一个符号时,本节允许长度零的空字,得到 、。某些通信情境要求至少一比特或另加终止标记;那是附加编码约束,可改变允许的码和最优平均长度。数学上的零长度不意味着真实协议无需帧定界,也不意味着接收者无需知道发送符号的数量。
对于非空码字的前缀码,从左到右读到一个码字就能确定其终点,再读下一个,因而可唯一译码。若唯一的码字为空字,则需要另行知道字数才能确定序列,因为没有比特标记其重复次数。这里的熵和 Kraft 结论不需要证明针对所有唯一可译码的更一般定理。非前缀码仍可能以更复杂方式唯一译码,所以仅凭它不是前缀码,不能证明每种拼接都有歧义。
本模型只计算码字的比特数,不计算传送不断变化的字典、同步分块或检测传输错误的成本。
例题详解
例题 3.1.8
(概率不相等)
概率为 时,前缀字 的长度为 ,平均长度为 。熵同样是 。这里每个字长都等于 ,因此达到下界。
例题 3.1.9
(信息量不是整数)
三个符号等概率时,。码 的平均长度为 。每个字的长度必须是整数,不能分别赋予 比特,尽管平均长度可以不是整数。这与上下两个界都一致:。
例题 3.1.10
(不可能的长度列表)
三个长度均为一的二元码字的 Kraft 和为 ,故不存在这样的前缀码;事实上长度一的二元字只有两个。定理的反方向说明,当 Kraft 和至多为一时,可以构造具有指定整数长度的前缀码。
例题 3.1.11
(有偏的二元信源)
两个符号的概率为 时,熵为
它小于公平二元信源的一比特。对两个单独符号的前缀码,每个码字仍至少需要一比特:码有两个字时任何一个都不能是空字。所以单符号码 的平均长度是 1,而非 。整数码长未必能达到熵下界。
例题 3.1.12
(独立与完全相关的比特对)
两个独立公平比特有四个等概率的两位块。分别使用 作为码字,平均块长度为 2,每个原始符号平均 1 比特,等于单符号熵。若两位完全相关,只可能出现各占一半的 ,其块熵为 1 而非 2。边缘概率不能单独决定联合熵。
常见错误
常见错误
(互不相同的码字不一定是前缀码)
平均长度小不保证即时译码。字 和 虽然不同,却不是前缀码:读到第一个零时不能立刻知道它是完整码字还是第二个码字的开头。前缀性是即时译码的充分条件;这里的熵定理针对前缀码,并未对任意不同字列表作断言。
去掉前缀条件不只是使译码变得复杂;它甚至可以破坏熵界本身。
反例模式
只要求码字互不相同并不保证熵界
断言:每个给符号分配互不相同的二元字的码都满足 。对 使用互不相同的字 。则
该码不是前缀码,因为 是 的前缀,其 Kraft 和为 。它也无法译码:字符串 可以是一个第三符号,也可以是两个第一符号。修正后的命题就是上面证明的定理:前缀码满足 。
常见错误
(界 只针对平均长度)
熵依赖概率,而不只依赖可能符号数。 是构造所得码的平均长度上界,不是每个码字长度的上界。概率必须构成分布;这里省略 的项以避免写 ,需要时也可使用通常的极限约定。
总结
Kraft 不等式把前缀条件转化为二叉树的容量限制,并刻画哪些有限长度列表可以实现。熵下界来自散度非负;把信息量向上取整,可构造平均长度比熵多不到一比特的码。
练习
快速检查
(二元前缀码能否有长度 ?)
计算 Kraft 和。
解答 · 答案
不能,Kraft 和为 。
快速检查
(两个等概率符号的熵是多少?给出最优前缀码。)
以 应用均匀分布使熵最大的定理。
解答 · 答案
熵为 1 比特。码字 长度均为 1,平均为 1,达到熵下界。
快速检查
(某前缀码长度为 。求 Kraft 和并构造一个这样的码。)
先放两个短字,再把一个未用的长度二的字拆分。
解答 · 答案
和为 。例如 ,其中没有一个字是另一个的前缀。未使用容量不会妨碍译码。
快速检查
(信源把同一个公平比特重复两次,因此两位块只可能是各占一半的 。求块熵,并与两个边缘熵之和比较。)
数一数实际会出现的结果。
解答
块有两个等概率结果,熵为 1 比特。每一位单独的熵都是 1,但两位相关,两个边缘熵之和为 2。独立符号的乘积分布证明不能应用。
快速检查
(长度为 的二元前缀码,按此顺序对应概率 时,能否恰好达到熵?)
计算 并与 比较。
解答
平均长度为 ,而信源熵为 ,因此没有达到下界。其 Kraft 和为 ,也显示树容量未填满。长度 的码对该分布可以达到熵。
快速检查
(信源只有一个概率为一的符号。按本节约定,它的熵和最优平均长度是多少?)
使用空字的约定。
解答 · 答案
熵为 。分配空字得到平均长度零,达到下界。实际系统的消息数量或定界要求可能在模型之外增加成本。