跳到正文
视频

二维码是怎么工作的:为什么撕破的码还能扫

二维码存的不只是信息本身,还有根据它算出来的备用字节,所以被撕破、弄脏或被 logo 盖住的字节,扫码器都能重建。四个纠错等级,约 7% 到 30% 的码字,还有三个不能盖住的角方块。一支 48 秒的科普短片,每个数字都有出处。

发布于
阅读
约 7 分钟
标签
  • qr-codes
  • how-it-works
  • explainer
目录
  1. 撕破了、弄脏了,照样能扫
  2. 备用字节,由信息算出
  3. 每修一个字节,要两个备用字节
  4. 四个等级:7% 到 30%
  5. logo 是它能修的损坏
  6. 别盖住角
  7. 结论
  8. 来源

一句话总结: 二维码存的不只是信息本身。它还会加上根据信息算出来的备用字节,也就是里德-所罗门(Reed–Solomon)纠错,和音乐 CD 用的是同一套数学,所以扫码器能重建缺失或出错的字节。备用字节多少由你决定:L、M、Q、H 四个等级,分别能恢复约 7%、15%、25% 和 30% 的码字,备用字节越多,码就越大。这就是为什么中间放个 logo 也能扫:对扫码器来说,那只是损坏。三个角上的方块则不一样:它们不是数据,而是让扫码器找到并摆正这个码,所以大多数扫码器都离不开它们。

撕破了、弄脏了,照样能扫

二维码的开发者 DENSO WAVE(电装波动):"QR Code has error correction capability to restore data if the code is dirty or damaged."(二维码具有纠错能力,码被弄脏或损坏时也能恢复数据。)它在特点列表里还写道:"Data can be restored even if the symbol is partially dirty or damaged."(即使符号部分弄脏或损坏,数据也能恢复。)

视频里的码是真的:内容是 oliverz.dev。一角撕破、边上有污渍、中间盖着 logo,它的 44 个码字里有 13 个是错的,但照样能解出来(我们用 jsQR 和 ZXing 两个解码器测试过)。

备用字节,由信息算出

DENSO WAVE:"The QR Code error correction feature is implemented by adding a Reed-Solomon Code… to the original data."(二维码的纠错功能,是通过在原始数据上加上里德-所罗门码来实现的。)坎特伯雷大学的《Computer Science Field Guide》说得更简单:"it adds extra bits to the data so that errors can be corrected."(它在数据上加了额外的比特,这样错误就能被纠正。)

单位是码字。DENSO WAVE:"codeword is a unit that constructs the data area. One codeword of QR Code is equal to 8 bits."(码字是构成数据区的单位。二维码的一个码字等于 8 比特。)CS Field Guide:"Each black or white square (“dot” or “module”) corresponds to one bit of data."(每个黑色或白色的小方块("点"或"模块")对应一比特数据。)所以八个模块就是一个字节。

这套数学并不新。DENSO WAVE:"Reed-Solomon Code is a mathematical error correction method used for music CDs etc. The technology was originally developed as a measure against communication noise for artificial satellites and planetary probes."(里德-所罗门码是一种数学纠错方法,用于音乐 CD 等。这项技术最初是为了对付人造卫星和行星探测器的通信噪声而开发的。)

每修一个字节,要两个备用字节

DENSO WAVE:"Reed-Solomon Code requires twice the amount of codewords to be corrected."(里德-所罗门码需要两倍于待纠正数量的码字。)CS Field Guide:"The maximum number of errors that a Reed-Solomon code can correct is one half of the amount of extra error correcting data added to it."(里德-所罗门码最多能纠正的错误数,是加进去的额外纠错数据量的一半。)

我们的码用最高等级时,有 16 个信息码字和 28 个备用码字,共 44 个。28 的一半是 14,所以它最多能修 14 个错误码字:44 个里的 14 个约为 32%(我们自己算的),对应 DENSO 的 "Approx. 30%"(约 30%)。在我们的测试里,极限恰好就在这里:错 14 个码字还能读出,错 15 个就没有结果。

是没有结果,而不是错误的结果。CS Field Guide:"they won’t read the data incorrectly, instead they just refuse to give any data at all, rather than giving you incorrect data."(它们不会把数据读错,而是干脆拒绝给出任何数据,而不是给你错误的数据。)

四个等级:7% 到 30%

DENSO WAVE 对标准(ISO/IEC 18004)的概述:"Level L Level M Level Q Level H Approx. 7% of codewords can be restored. Approx. 15% of codewords can be restored. Approx. 25% of codewords can be restored. Approx. 30% of codewords can be restored."(L 级、M 级、Q 级、H 级:约 7% 的码字可恢复;约 15% 的码字可恢复;约 25% 的码字可恢复;约 30% 的码字可恢复。)

这个百分比算的是码字,不是你看到的面积:"*Data restoration rate for total codewords" … "QR Code therefore represents its error correction rate as a ratio of the total codewords."(*数据恢复率以全部码字计……因此二维码用占全部码字的比例来表示纠错率。)

备用字节越多,占的地方越大。DENSO WAVE:"Raising this level improves error correction capability but also increases the amount of data QR Code size."(提高等级能增强纠错能力,但也会增加数据量和二维码的尺寸。)还有:"as the amount of data increases, more modules are required to comprise QR Code, resulting in larger QR Code symbols."(数据量增加时,组成二维码需要更多模块,二维码符号也就更大。)我们为 oliverz.dev 生成的四个码,信息码字 + 备用码字:

  • L:19 + 7,21 × 21 个模块
  • M:16 + 10,21 × 21 个模块
  • Q:13 + 13,21 × 21 个模块
  • H:16 + 28,25 × 25 个模块(在 H 级,"oliverz.dev" 的 11 个字节放不进 21 × 21 了)

logo 是它能修的损坏

所以中间放个 logo 也能扫:扫码器把它当作损坏,把它挡住的内容重建出来。在我们的 H 级码上,一个 7 × 7 模块的 logo 让 44 个码字里的 9 个出错,在 14 个的上限之内。

不过这不是白来的:它用掉了备用字节。DENSO WAVE 的常见问题,谈到带颜色或插图的码时说:"If it is deformed, the QR Code's error correction function is invoked where even a tiny missing or smeared part renders the reading operation impossible, or the response of the operation may become slow."(如果码变形了,就会动用二维码的纠错功能,这时哪怕再缺一小块或糊了一点,也可能读不出来,或者读取变慢。)

别盖住角

三个大方块不是数据。DENSO WAVE:"QR Code accomplishes this task through position detection patterns located at the three corners of the symbol."(二维码通过位于符号三个角上的位置探测图形来完成这项任务。)它讲二维码历史时写道,有了它们,"the orientation of their code could be determined regardless of the angle of scanning, which could be any angle out of 360°"(无论以什么角度扫描,360° 中的任何角度,都能确定码的方向)。

CS Field Guide:"Don’t colour in near the three large squares in the corners, as most QR scanners need these to align the image."(不要在角上三个大方块附近涂色,因为大多数二维码扫描器需要靠它们来对齐图像。)

在我们的测试里,在一个角方块中心贴一张 3 × 3 模块的小贴纸,两个解码器就都读不出了,而一个数据字节都没碰到。logo 盖住 49 个模块照样能扫;贴纸只盖 9 个,却扫不出来。

结论

  1. 二维码存的是信息加上由它算出的备用字节(里德-所罗门),所以扫码器能重建被撕破、弄脏或盖住的字节。
  2. 备用字节多少由你选:L、M、Q、H,约 7% 到 30% 的码字;备用字节越多,码越大。中间的 logo 就是备用字节能弥补的损坏。
  3. 三个角方块不是数据:它们让扫码器找到并摆正这个码,所以大多数扫码器都离不开它们。

来源

视频用代码制作动画,脚本在 AI 辅助下撰写;上面每条引文都对照出处核实过,标注"我们自己算的"的数字是我们自己的计算。码是真的(先生成,再用 jsQR 和 ZXing 解码),它们的字节和码字数也是真的。示意部分:撕口、污渍和 logo(一个通用图形,正好画在我们测试过的那些模块上)、相机取景框,以及倾斜的码(同一个码按透视画出)。真实的磨损不会像沿着模块画的损坏这么整齐。"QR Code" 是 DENSO WAVE INCORPORATED 的注册商标。视频为英文旁白。视频用 Shotloop 制作:我做的免费 Mac 应用,用代码做科普短视频,一个镜头一个镜头地改。

How It Works 更多

YouTube 播放列表 ↗
关注我

我会持续分享正在做的项目、实验和经验。

YouTube 上发视频,X 上发短笔记。这里的每篇文章都会链接到两边。

YouTube