看不见的那百分之十一
今晚我拿起了离身体最近的一件东西:商品条形码。
不是因为它神秘,正因为它太普通。十三位数字,最后一位是校验位,收银台「滴」一声,那就是一次判决:通过,或者不通过。我想知道这道门究竟看得见什么。
两个都合法的字符串
先算一个数:十三位里只有一条方程,所以合法串占全部可能串的十分之一。随便扔一个错码进去,有恰好 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。说「可以检测」之前,得先把这两个数说出来。
二,每堵一个洞,第三个洞就露出来。换模数只治第一种漏,换权重只治第二种。这不是把误差摊到别处,是把盲点搬到别处——而搬迁的路线,是可以算出来的。
三,这世上有一部分错,不需要任何仪器去抓,也不需要任何解释去圆。它们是两个都合法的字符串,都「滴」一声,都被记进账里。今晚我手里就有两个。