本文来自微信民众号：回形针PaperClip（ID：papercliptv），作者：吴松磊，题图来自：IC photo

来，看着这个二维码。

加人、购物、填表、付钱，你可能扫过无数次二维码，但却从来没有认真看过它。

这个二维码结构看起来很简朴，左下、左上和右上有三个方块用来定位。剩下的位置就是一堆玄色和白色小方块组成一个 29×29 的大方块，白色方块示意 0，玄色方块示意 1。由这些 0 和 1 组成的二进制字符串就可以转换成种种数字、字母和符号了。

但你仔细看，就会发现没这么简朴。

条码系统降生之初，就是希望缔造一套简朴清晰可被印刷能被机械识别的图形编码，让机械轻松获取商品编号。

这样你在超市买东西的时刻，收银员就不需要手动纪录，只需要扫一下就能知道若干钱了。

这就是二维码的前身——一维码，今天我们都叫条形码。以 UPC（Universal Product Code）码为例，本质上就是 30 条粗细纷歧的黑线。

而玄色竖线和白色距离的宽度，就是隐藏在条形码里的二进制信息。

竖线和距离都有 4 种宽度。最细的竖线代表一个 1，之后是两个 1，三个 1，最粗的竖线就是 4 个 1。对应的，4 种距离宽度就是 0、00、000、0000。

好比这里，就是 0110001，凭据编码表，代表 5。每 2 条竖线加 2 条距离就能示意一个数字，这 48 条竖线和距离就可以示意 12 位数字编号了。

而左右最外侧的双排线则是所有条码的牢固开头，代表 101，这么做的意义在于让扫码器知道这个条码最细宽度，进而识别出这个宽度的 2、3、4 倍。

这样，无论条码根据什么尺寸印刷，扫码器都可以完成识别，需要的信息也只有一条线这么多，其他地方都污损了也没关系。

然则若是扫反了怎么办？

只要让扫码器区分左右就好了。我们把分隔符左侧的编码内外的 0 酿成 1、1 酿成 0 ，就获得了分隔符右侧的编码表。巧妙的地方在于，左侧所有组合里 1 的个数都是奇数 ，而右侧都是偶数。

这样，扫码器从左往右读取数据时只要发现一组数据里的 1 是偶数，那么就可以确认扫反了。用逆码表解读数字，再重新组合，就能获得准确编号。

最后，编号第 12 位数是凭据前 11 位数盘算出来的校验码，以防止窜改。

这三重设计保证了条形码可以顺应种种庞大的现实情形，异常可靠。

但条形码上能承载的信息照样太少了，以是，以矩阵形式承载更多信息的二维码泛起了。在这些奇新鲜怪的二维码中， QR 码脱颖而出，泛起在了你的微信支付宝和火车票上。

QR 的全称是 Quick Response，快速响应矩阵。最有代表性的就是这三个回字型方块，这样的排布方案可以让你无论从哪个偏向扫描二维码都市自动校正为准确偏向，只要右下角没方块就是对的，很简朴。

但 QR 码是怎么实现校验、纠错同时保证准确度的呢？我们找到了这份 126 页的 QR 码国际通用尺度。

今天的通俗 QR 码有 40 个版本，版本越大，尺寸越大。最小的版本 1 是一个 21×21 的正方形，版本号每加 1，正方形的边长就多 4 格。最大的版本 40 就是一个这样 177×177 的密恐正方形。

以这个版本 3 的 QR 码为例，也许由 5 个部门组成。

1 是 3 个7×7 的回字形方块和宽度为 1 的白色的分隔符。

2 是这两条是非相间的定位图案，告诉扫码器横竖的尺度偏向。

3 是右下角的校正图形，一个 5×5 的小方块，尺寸越大，校正图形越多。这样，纵然你用新鲜的角度扫描，算法依然可以凭据这三组图案提取轮廓，修正透视，获得正面图案。

4 是由相同的两组方块组成的花样信息，每组 15 个，放置在定位方块的旁边。

5 作为剩下的区域，会被分成 8 个一组的模块，存储数据和纠错码。

而在大于即是版本 7 的 QR 码里，还需要在这两处纪录 18 位的版本信息，提高扫码器的效率。

1、2、3 的设计只是让 QR 码可以被扫码器认出来，但 QR 码真正厉害的地方在于，纵然你这样、这样、或者这样、它都能被准确识别。

为什么？

现在，我们终于进入到了 QR 码的焦点， Reed-Solomon 编码。

注重，接下来的内容会有一点点难，但也只需要中学数学知识就够了，若是你理解了会异常有意思，让我们最先吧。

我们知道，二维码是用是非方格对应的二进制数据来示意信息，好比 1234 就可以编码为 00011110110100，对应成二维码里的方格就是这样。而 Reed-Solomon 编码可以让你随便修改一定数目的格子，机械都能自动还原成准确的数据。

为了更好的注释这一历程，我们简化成 4 个格子，有 4 个数字，划分是 1、2、3、4。

我们的目的是，任选 2 格修改成其他数字，算法都可以自动发现错的是哪一个，而且还原成修改前的数据。

为了做到这件事，我们需要获得 4 个变量，错误的两个格子的位置，e1 和 e2，这两个格子错误的巨细 y1 和 y2。假设我们知道 e1=3，e2=1，y1=-5，y2=1，那么机械就可以自动调整成准确数据了。

而在盘算这 4 个未知数之前，还得先让机械知道，这串数字错了。

最简朴的方式，就是算 0。算出了 0 就是对的，不是 0 就是错的。

好比我们所有人的装备都可以保留一个牢固数值 g=1234，用输入数值 m 1234 减牢固值 g 1234 就正好即是 0。但 g 是不会变的，若是我们想输入 5678，效果就不是 0 了。这时我们就需要凭据输入值和牢固值反推出一个 p，无论我们想输入什么，都能算出 0，这个 p 就是纠错码。

好比牢固数值 g= 100，输入值是 5678，那 p 就可以是 -5578，若是我们输入酿成 1234，p 就会随着酿成 -1134。这样，若是输入值被窜改了，好比被改成了 6234，效果就不是 0，而是 5000，机械就知道输入错了。

纠错码 p 和输入值 m 都市泛起在二维码上，但这样就带了一个新问题，纠错码被修改了怎么办？

若是 m p-100 不即是 0，我们永远不可能知道是 m 错了照样 p 错了，然则若是我们可以把 m 和 p 组合成一个数字好比说 1234XXXX 呢？听起来不错，但这样减法就不行了，这 4 位数不管是若干都不可能获得 0，那怎么办？

谜底是：用除法。

好比我们让 12340000 除以 3，余数即是 1，我们用 12340000 减去 1，就获得了 12339999，此时除以 3 的余数即是 0。但这样带来了两个新问题， 3 的倍数有许多，许多错误情形下一样可以获得 0，而纵然我们获得了一个余数，我们又怎么能通过余数知道哪一位数错了若干呢？

这时，我们就需要改变盘算规则了。盛大先容——伽罗瓦域（Galois Field，GF）。

伽罗瓦域厉害的地方在于，这是一个封锁的天下，内里的有限个数字不管怎么算都不会获得它们之外的效果。

以 GF(2^3) 域为例，一共有 8 个数，0、1、2、3、4、5、6、7，他们对应的二进制是这样。

伽罗瓦域的加法和减法运算一样，都是异或算法。好比 1-2 就是 001 异或 010，效果是 011，凭据这个表 011 是 3，1 2 效果也一样。6 7 就是 1，不管怎么加减，都只能获得这个域里的数字。

而乘除法的规则庞大一些，效果大于 7，好比 6*7 就需要对 110 和 111 做模二乘法，再用模二除法除以提前预设的数值 1011，获得余数 100，就是 4。

这就是伽罗瓦域 GF(2^3) 的完整乘法表，不管你怎么算，永远只能获得 0、1、2、3、4、5、6、7。除法也类似。

还记得刚刚的除法吗？现在若是我们用伽罗瓦域的规则，就不能再用 12340000 了，这个天下里只能有这 8 个数字，那我们还能怎么显示 12340000 呢？

谜底是：多项式。

在多项式中，我们可以把每个格子里的数字作为 x 的系数，把格子的位数作为 x 的次方数。好比 1、2、3、4 就是 1*x^3 2*x^2 3*x^1 4*x^0，那么 12340000 的多项式 m(x) 就是这样

既然输入数据酿成了多项式，我们要除以的牢固值 g 也应该是一个有 x 的多项式。我们要获得的 4 位纠错码， g(x) 就有 4 个因子，划分是x减2的零次方，x减2的一次方，x减2的二次方，x减2的三次方，

g(x) 就即是这 4 个因子相乘。

这样做的意义在于，由于这个 g(x) 睁开后的多项式最高位就是 x 的 4 次方，以是我们用 m(x) 除以 g(x) 能正好就获得 4 位数的余数P(x)= 1*x^3 6*x^2 7*x 4，把多项式的系数换成数字就是 1674。

这个历程用公式形貌就是这样：

我们双方都乘 g(x) ，再把余数 P(x) 移到左边，别忘了伽罗瓦域里加和减是一样的。以是我们可以神奇地发现，把原来的 M(x) 和余数 P(x) 相加，获得的新多项式正好可以被整除，而这 4 位余数就是我们要找的 4 位纠错码。

这样我们获得了最终的输入数据 12341674，用多项式示意就是这样：

好，我们的准备工作已经所有完成了。现在，你可以随便修改这 8 个格子里的 2 个数，机械都可以完成自动修正。

首先，系统会把收到的输入数据酿成多项式，除以提前设定好的 g(x) ，获得余数 1645，不即是 0，说明输入数据有误。

现在，只需要找到错误位置 e1、e2 以及他们对应的错误巨细 y1、y2 就行了。

而这一切的要害，就在于四个隐藏着的方程组。

我们知道准确的输入数据 M(x) 除以 g(x) 的余数是 0，那么 M(x) 就即是 g(x) 乘一个牢固值 h。

若是 g(x)=0， 准确的 M(x) 也会即是 0。

而凭据 g(x) 的公式，正好有 4 种情形会即是 0。划分是 x 即是 2 的 0 次方 1 次方 2 次方和 3 次方，用公式写出来就是这样：

虽然我们不知道准确情形下 m1、m2、m3、m4、p1、p2、p3、p4 是若干，然则我们知道错误情形下的，把我们收到的输入数据 62241674 带入这 4 个方程盘算，能获得 4 个不即是 0 的效果。

而这 4 个方程之以是不即是 0，是由于有 2 个地方的数字失足了，失足的巨细 y 乘 2 的 n 次方后相加就是方程的效果。而这 2 的这个 n 次方又和失足数字的位置有关，若是 x=2^1 ，那么 n 就即是 1 乘失足的位置 e，若是 x=2^2 ，那么 n 就即是 2 乘失足的位置 e。用公式写出来就是这样：

现在，我们有四个方程组，四个未知数，机械就能算出来。

现在，我们可以把收到数据的第 5 和第 7 位的数字 2 和 6，划分和 y1 和 y2 做异或运算，获得 3 和 1，填回去，我们就获得准确的输入数据了。

需要说明的是，这是一个简化后的盘算历程，实际情形还要更庞大。

这就是二维码的隐秘，把信息编码为二进制，按顺序填上原始数据，再填上盘算后的纠错码，和其他信息，再和掩码做一次异或运算，最终成为你看到的样子，一个可靠的码。

1960 年，工程师 Irving S. Reed 和 Gustave Solomon 可能也不会想到，他们公布的这篇不到的 5 页论文会在 60 年后成为现代生涯不可或缺的一部门，和无数精彩绝伦的论文一样，成为这个天下底层看不见的一块砖。

本文来自微信民众号：回形针PaperClip（ID：papercliptv），作者：吴松磊