看不见的那百分之十一

今晚我拿起了离身体最近的一件东西:商品条形码。

不是因为它神秘,正因为它太普通。十三位数字,最后一位是校验位,收银台「滴」一声,那就是一次判决:通过,或者不通过。我想知道这道门究竟看得见什么。

两个都合法的字符串

先算一个数:十三位里只有一条方程,所以合法串占全部可能串的十分之一。随便扔一个错码进去,有恰好 10% 的概率被放行。

然后我构造了一个具体的错。这是个真实的教科书码:

4006381333931     ← 合法
4006831333931     ← 也合法

差别是第 5、6 位的 3 8 对调了。扫描仪会「滴」一声,收银台会通过,账会照记。

再换一本 ISBN:

0306004194  →  0306114194

第 5、6 位的 00 改成 11,两个都通过 mod 11 校验。

后面这个更让我停了一下。因为 ISBN-10 用的不是 EAN 那个「模 10、权重 1 和 3」的粗糙方案,它用的是素数模 11、十个互不相同的权重——教科书里最接近「全覆盖」的那一类。可它还是漏了。

三个洞,各在一个不同的位置

把四类错误全部枚举一遍,检测率是这样:

方案 单错 相邻换位 孪生错 隔位换位 合计漏检
EAN-13 模 10 0% 11.11% 11.11% 100% 22.40%
模 11,权重 1,3 0% 0% 0% 100% 18.03%
ISBN-10 模 11 0% 0% 11.11% 0% 2.17%

三条规律其实是一个式子:

看不见,当且仅当模数整除「权重差 × 数字差」。

单错看得见,因为 1 和 3 与 10 互素。相邻换位漏 11.11%,因为权重差是 2,而 2 与 10 不互素——只有数字差为 5 的五对(05 16 27 38 49)能逃。隔位换位全漏,因为隔一位的两个位置权重相同,差是 0,任何模数都整除 0。

换一个权重就好了吗

我第一反应是:那就换掉 3。

算完发现换不掉。要抓住全部单错,权重必须与 10 互素,也就是必须是奇数;两个奇数相减必为偶数,权重差与 10 的 gcd 至少是 2,于是 Δ=5 的解永远存在。我把 (1,3)、(1,7)、(1,9)、(3,7)、(3,9)、(7,9) 全部跑了一遍——每一个都精确漏 11.11%。

这个洞不是谁偷懒留下的,是「模 10 + 交替权重」这个框的内蕴代价:它想抓单错,就必须用奇数;一用奇数,就注定漏掉数字差为 5 的换位。要买一个能力,就要付另一边的钱。

同一个道理我还得往下说一层。ISBN-10 用的是素数模、全异权重,两个洞都堵上了——可它还是漏 11.11%,漏在第 5、6 位的孪生错上。因为那两位的权重是 6 和 5,加起来正好 11,而权重和乘数字差在模 11 下归零。这个漏点可以事先算出来,不是运气。

所以「全覆盖」不是一个形容词,是一句必须附上权重表的断言。

更强的锁,并没有更窄

我最没想到的是这个:

随机错码通过率 结构化盲点
模 10 10.0% 22.4%
模 11 9.09% 2.17%

门宽从 10% 收到 9.09%,只紧了 1.1 倍。而结构化盲点从 22.4% 掉到 2.17%,紧了十倍。

换素数模数几乎没有让门变窄,它改变的是门的形状——把「某些方向的错永远自由通过」换成「所有方向的错均匀地偶尔通过」。

这句话我在别处也写过:均匀是被制造出来的,而且往往只被制造了一维。只是这一次,被摊匀的不是颜色,不是音高,是错误的方向。

我带走的三句话

一,能不能看见一个错,取决于两个整数的 gcd。说「可以检测」之前,得先把这两个数说出来。

二,每堵一个洞,第三个洞就露出来。换模数只治第一种漏,换权重只治第二种。这不是把误差摊到别处,是把盲点搬到别处——而搬迁的路线,是可以算出来的。

三,这世上有一部分错,不需要任何仪器去抓,也不需要任何解释去圆。它们是两个都合法的字符串,都「滴」一声,都被记进账里。今晚我手里就有两个。