能容纳多少个码字?
最小距离要求使码字相互分离,但能选多少个并不显然。我们以构造证明下界,并以互不相交的球装箱证明上界;两界不一定相等。
定义 13.1.1
(汉明距离与球体积)
设 是有 个符号的字母表,、,三者都是整数。两个长度为 的字的汉明(Hamming)距离是不同坐标的数目。码是一组字;它不必线性, 也不必是素数幂。记
这是与固定字距离至多 的字的数目:选 个坐标,每个坐标有 个替代值。此数目与中心无关。
贪心存在性下界
定理 13.1.2
(贪心覆盖界)
存在码 ,任意两个不同码字距离至少为 ,且
这是有限情况下的贪心 Gilbert–Varshamov 界。
证明
(贪心选取直至覆盖整个空间)
开始时所有字都可选。任选一个可选字加入 ,然后移除与它距离至多 的所有字。重复至没有可选字为止。每次至少移除所选字,有限的可选集合因此令过程终止。每个后选的字都在先前所选字的半径 球外,所以所选字两两距离至少为 。
终止时,所选字周围半径 的球覆盖全部 个字。球可以重叠,所以并集大小至多是各球大小之和。因此 ,得到上述向上取整的界。因为 ,球小于整个空间,该界至少给出两个码字。
证明透视
覆盖不是装箱
有限性只用于终止:每一轮至少从有限集合中移除所选字。间距来自移除规则,因为与所选字距离至多 的字在下一次选取前都已删去。关键一步是倒过来读停止条件:既然没有可选字,所选字周围半径 的球便覆盖整个 。
论证以并集界收尾,而并集界允许重叠;正因如此,不等式的方向恰好给出 的下界。这里的半径是 ,不是纠错半径,各球也不必互不相交。下面的装箱界用的是相反的计数方式。
装箱上界
定理 13.1.3
(汉明装箱界)
令 。任意两个不同码字距离至少为 的每个码 都满足
证明
(半径 t 的不相交球)
码字周围半径 的球互不相交:若有共同字,由三角不等式可知两个不同码字的距离至多为 。所有球都位于 ,所以 。因为 是整数,可以取向下取整。
两个界分别使用半径 和 ,主张也不同:第一个构造某个具有最小数量保证的码;第二个限制所有具有指定间距的码。一般而言,这些界未必能确定可能的最大码;如果两界相等,则可以确定。
例题 13.1.4
(五个二元位置,距离三)
对 、、,贪心球体积为 ,定理保证至少 个字。装箱半径为 ,,因此所有这样的码至多有 个字。
四个字 构成最小距离为三的具体码:其非零字的重量是 ,后三个字两两之差的重量为 。此构造改进了本例的下界,但本身不能排除五字码的存在。
反例模式
极大不等于最大
贪心算法在包含关系意义下的极大码处停止:不能再加入任何字而保持距离要求。这性质本身不证明其码字数是所有码中最多的。在二元 的例子中,先选 再选 ,每个字已在其中一个字距离二以内:任何字的重量不是至多二,就是至少三。这个极大码有两个字,而上面的四字码更大。覆盖论证保证一个数量下界,没有声称最优。
例题 13.1.5
(两界相遇的三元码)
取 、、。贪心体积为 ,所以存在至少 个字的码。装箱半径为 ,,所以每个码至多有 个字。码 中两两距离都是三,因此达到上界:长度三、最小距离三的最大三元码恰有三个字。这里字母表 只作为符号集合使用,不需要域结构。
例题 13.1.6
(距离等于长度)
在极端情形 ,取 、、。半径 的球只漏掉中心的补字,所以 ,贪心界给出至少 个字。取 ,,装箱界给出至多 个字。重复码 同时达到两界,所以是最优的;事实上,两个距离为五的二元字互为补字,第三个字不可能同时是两者的补字。
常见错误
(把两个半径互换)
贪心界除以半径 的球,装箱界除以半径 的球。若在贪心界中用半径 ,对二元 、 便会声称存在至少 个字的码,与装箱上界 矛盾。不相交只在半径 成立;覆盖只在半径 得到保证。
定理没有提供什么
算法可能需要检查指数大小的 个字。此存在性证明没有给出高效的编码器或译码器、线性码,也没有给出特定信道的错误概率。装箱论证确实给出至多 个符号受损时的唯一性,但要高效地找出最近码字仍需额外工作。
习题
快速检查
(计算 和 的贪心下界。)
距离一以内只有中心及其 个邻字。
解答 · 答案
,故贪心码至少有 个字。
快速检查
(对二元 ,为什么装箱半径是一,而贪心覆盖半径是二?)
比较不相交所用的半径与算法移除的半径。
解答 · 答案
中心距离至少三时,半径一的球互不相交;贪心过程排除距离至多 的字,确保所选中心有要求的间距。
快速检查
(验证 的最小距离为三。)
计算全部六个两两距离。
解答 · 答案
非零字重量为 ,三个非零字两两距离为 ,故最小值为三。
快速检查
(极大的贪心码是否必然具有最多码字?证明实际上确立什么?)
比较包含关系意义下的极大与数量上的最大。
解答 · 答案
证明没有确立这点;它确立包含关系意义下的极大性、两两距离至少 和上述数量下界。
延伸阅读
卡内基梅隆大学编码理论课程材料 列出 Gilbert–Varshamov 界及基本码界的讲义。