支撑二维码的数学 - 有限域与 Reed-Solomon 码的原理
为什么脏了的二维码还能读出来
二维码最突出的特长，是即使一部分被污损或破坏，依然能够正确地还原数据。在纠错等级 H 之下，整体约 30% 的面积丢失，原始数据也可以完整复原。支撑这项近乎「魔法」的能力的，是一种叫做 Reed-Solomon 码的纠错算法。
Reed-Solomon 码由 Irving S. Reed 与 Gustave Solomon 于 1960 年发表。它并不只用在二维码上，CD 与 DVD、数字广播、深空通信（NASA 的旅行者号探测器）、RAID 存储，凡是对数据可靠性有要求的场合都在使用。
一个 60 多年前构思出来的算法，如今每天在全世界的手机里运转。这件事本身就说明了优秀的数学具有怎样的普适性。
有限域（伽罗瓦域）- 二维码的数学地基
要理解 Reed-Solomon 码，先得知道「有限域」（伽罗瓦域，Galois Field）这种数学结构。在日常的算术里，数是无限延伸下去的（1、2、3……）；而在有限域中，只用规定好的有限个元素，四则运算就能自成体系。
二维码使用的有限域是 GF(28)，也就是拥有 256 个元素的域。从 0 到 255 这 256 个数，把加、减、乘、除全都封闭在同一个世界里。所谓「封闭」，指的是无论做哪种运算，结果一定仍然落在 0 到 255 的范围之内。
为什么偏偏是 256。计算机处理数据的基本单位是 1 个字节（8 位），1 个字节能表示的取值正好是 0 到 255 共 256 种。为了让二维码的数据以字节为单位来处理，恰好含 256 个元素的有限域就被选中了。数学上抽象的结构，与计算机物理上的约束，在 GF(28) 这一点上漂亮地交汇在一起。
Reed-Solomon 码的原理 - 用多项式守住数据
Reed-Solomon 码的核心，是把数据当作「多项式」来处理。比如有 3 个字节的数据 [65, 118, 42]，就把它看成多项式 65x2 + 118x + 42。
接着在 GF(28) 上，用一个「生成多项式」去做除法，所得的余数就是「纠错码字」。把这些纠错码字附在原始数据后面，一起存进二维码。
读取的时候，把收到的多项式再用生成多项式除一次：余数为 0 就判定「无错误」，不为 0 就判定「有错误」。存在错误时，从余数的形态反推出「哪个位置」「以何种方式」出了错，进而复原原始数据。这一步反推会用到 Berlekamp-Massey 算法、Forney 算法等相当进阶的数学手法。
换个直观的说法：Reed-Solomon 码相当于「画一条穿过数据各点的曲线，即使其中一部分点消失了，也能靠剩下的点把原来的曲线还原出来」。它利用的是「有 n 个点就能唯一确定一条 n-1 次多项式」这一数学性质——事先多放几个点（纠错码字），于是丢掉一部分点之后，原来的曲线（数据）依然可以重建。
纠错等级的两个数字 - 可恢复比例与冗余占比
围绕纠错等级 L、M、Q、H，有两个很容易被混为一谈的数字。一个是能够复原的损伤比例（可恢复比例）：等级 L 约 7%，M 约 15%，Q 约 25%，H 约 30%。另一个是纠错码所占的比例（冗余占比），也就是二维码里装的码字当中，有多少个被留给了纠错。常见的说法「等级 H 破损 30% 也能读」讲的是前者，并不是说纠错码占了整体的 30%。
这是信息论中一个根本性的取舍。正如 Claude Shannon 在 1948 年发表的《通信的数学理论》所指出的，要在有噪声的信道上提高可靠性，就必须加入冗余（多余的信息）。二维码的纠错等级，正是控制这份冗余多少的参数。
冗余占比的实际数值，可以从标准 ISO/IEC 18004 规定的码字构成中看到。最小的版本 1（21 × 21 模块）总共有 26 个码字：等级 L 的分配是数据 19 + 纠错 7，等级 H 是数据 9 + 纠错 17。纠错码所占的比例，等级 L 约 27%，等级 H 约 65%，都比人们常说的 7% 和 30% 大得多，也就是说有更多的空间实际上花在了纠错上。
两个数字之所以对不上，原因在于 Reed-Solomon 码改正错误的步骤。要改正一个错误，必须同时查出「哪个码字出了问题」和「它变成了什么值」，因此每改正一个错误就要消耗两个纠错码字。此外，为了避免把变形的值认错、把它复原成另一份数据，标准并没有把纠错能力用到极限。这两点叠加起来，能够复原的损伤比例就落在纠错码占比的一半以下。增加冗余确实能提高可恢复比例，但增加的量不会原样变成可恢复比例。
分配上的差别，会体现在存放同样数据时的尺寸上。以版本 1 来比较，能存放的数据在等级 L 是 19 个码字，等级 H 是 9 个码字。要装进同样多的数据，等级 H 大约需要两倍的码字，也就得选用更大的版本。举例来说，等级 L 用版本 3（29 × 29 模块）就能装下的数据，等级 H 需要版本 5（37 × 37 模块），边长便这样一步步变长。印刷空间紧张的场合选等级 L 或 M，室外或工厂这类容易蹭上污渍、发生磨损的场合选等级 H。同时看可恢复比例和冗余占比，才是实务上的判断方式。
藏在日常里的高等数学
每一次扫描二维码，手机内部都在高速执行有限域上的多项式运算。便利店支付、乘坐电车、活动入场、翻看餐厅菜单，在这些日常动作的背后，1960 年代问世的编码理论，以及 19 世纪埃瓦里斯特·伽罗瓦发现的有限域理论，每秒都在被计算数亿次。
伽罗瓦是一位 20 岁便因决斗丧命的天才数学家，他留下的理论在当时被认为「几乎没有人能看懂」。这套理论在 200 年后成了全世界的人每天都在使用的技术的地基，这在数学史上属于最富戏剧性的段落之一。