为什么二维码能被识别？

前言

二维码在2026年已经十分常见，或许见到二维码就打开某聊天app、点击“扫一扫”已经成为了你的直觉。

但你有没有想过，为什么从哪一个方向、哪一个二维码都能被识别？（下面的这个动画是我觉得十分有意思的

笔者无聊的时候喜欢将答题卡上的二维码里空白的部分用涂卡笔涂黑，但为什么部分区域被涂黑/缺了一个角的二维码仍然能被识别？（下方二维码可被正常读取，图源维基百科¹

要了解这些问题，我们不妨了解下二维码是怎么工作的。为了研究这个问题，我们找到了 ISO/IEC 18004，它定义了二维码的国际标准，只是很可惜，这个标准需要付费下载，本文结。最终我得以搜索到一本盗版的标准并撰写了本文，我呼吁大家购买正版保护知识产权！

P.S. 本文二维码特指QR Code，实际上还有不少长度、宽度均记载着数据的条码，微信的“葵花码”指向小程序就是一例。

格式支持与编码

在二维码中可以放入任意编码的字符，但为了简单起见，在这里先让我们以数字+字母 01234567Ha 演示下：

数字模式 Numeric Mode

为了让未来读取二维码的设备明白”先以数字模式读取8个字符“，我们先插入二进制的 0001 指示符声明数字模式的开始，然后再插入表示字符长度的 8 补全至10bit的二进制表示 0000001000 以让读取者提前分配内存空间并预先知道何时停止（你或许觉得这是多余的：难道读取者不能够等待下一个指示符来结束这一阶段的读取吗？但实际上我们无法保证此后不会正巧出现长得想指示符的数据，这种数据导致我们需要引入转义符，就像你在Python中创建一个包括双引号的str时，需要使用 "something_here\"something_here" 确保python不会提前结束此str一样）。

下面我们将待编码数据三位一组，分别补全至10bit并用二进制表示，获得 0000001100 0101011001 1000011，其中最后一组若不满三位则只需补全至7（剩下两位而 $99=1100011_2$）或4位（只剩下一位）

class QRCodeEncoder:
    def encode_numeric(self, data):
        """数字模式编码"""
        # 模式指示符 (4 bits)
        indicator = "0001"
        # 长度指示符 (假设使用 Version 1-9，长度为 10 bits)
        length_indicator = format(len(data), '010b')
        
        bit_stream = ""
        # 每3个数字一组，转为10位二进制
        for i in range(0, len(data), 3):
            chunk = data[i:i+3]
            bit_stream += format(int(chunk), f'0{len(chunk)*3+1}b')
            
        return indicator + length_indicator + bit_stream

字母模式 Alphanumeric Mode

和数字差不多，我们将待编码数据两位一组，只不过将每一个字符当作一个0至44的数处理了，且指示符是
0010。

class QRCodeEncoder:
    def __init__(self):
        # Alphanumeric 字符集映射表
        self.alnum_chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"
        
    def encode_alphanumeric(self, data):
        """字母数字模式编码"""
        # 模式指示符 (4 bits)
        indicator = "0010"
        # 长度指示符 (假设使用 Version 1-9，长度为 9 bits)
        length_indicator = format(len(data), '09b')
        
        bit_stream = ""
        # 每2个字符一组
        for i in range(0, len(data), 2):
            if i + 1 < len(data):
                # 两个字符: (C1 * 45) + C2
                val = self.alnum_chars.index(data[i]) * 45 + self.alnum_chars.index(data[i+1])
                bit_stream += format(val, '011b')
            else:
                # 剩余一个字符: 直接转为6位
                val = self.alnum_chars.index(data[i])
                bit_stream += format(val, '06b')
                
        return indicator + length_indicator + bit_stream

P.s.其实对于不同大小的二维码，其能够承载的数据多少是不同的，因此将表示字符长度的指示符固定长度是很愚蠢的。实际上，在标准中，不同大小二维码的长度指示符长度也是不同的（如下图），但为了方便起见，我们目前考虑 Version 1 to 9。

杂项

此外还有这几个要求：

1. 终止符 (Terminator)：
   • 在数据流结束后添加 0000。如果添加后位流长度已经达到了容量上限，则不必添加或自动截断。
2. 对齐填充 (Bit Padding)：
   • 二维码要求数据必须是 8 的倍数（字节对齐）。如果 len % 8 != 0，则补 0 直到凑满。
3. 补齐字节 (Padding Bytes)：
   • 如果数据流仍未达到当前 QR 版本要求的容量，需要按照 ISO/IEC 18004 标准交替填充 0xEC (11101100) 和 0x11 (00010001)。这种混合为了防止大量空白降低图像对比度，导致扫码器无法正确地分辨出此图形（或者，像Gemini说的，“增加信息熵”）。

class QRCodeEncoder:
    def __init__(self, version=9, ec_level='L'):
        self.version = version
        # Version 9-L 的详细参数
        # 数据码字总数 (Total Data Codewords) = 230
        self.total_data_codewords = 230
        
    def _pad(self, bit_stream):
        """
        1. 填充至 8 位倍数
        2. 补齐至 230 字节
        """
        # 1. 补齐至 8 的倍数
        while len(bit_stream) % 8 != 0:
            bit_stream += "0"
            
        # 2. 填充 0xEC, 0x11
        padding_bytes = ["11101100", "00010001"]
        toggle = 0
        while len(bit_stream) < self.total_data_codewords * 8:
            bit_stream += padding_bytes[toggle]
            toggle = 1 - toggle
            
        return bit_stream

纠错

下面让我们考虑纠错。纠错分块进行，若干个byte分为一块，每一块都拥有自己的 Reed–Solomon 纠错码。为了减小纠错码和数据同时被损坏的可能性，二维码采用“交织（Interleaving）”技术，将数据码字和纠错码字以特定的顺序分布在整个符号区域内，从而将物理上的突发错误（如划痕、污损）分散到不同的纠错块中处理。如下图，

下面我们叙述 Reed–Solomon 纠错算法：

编

我们的目标是构造一个码字多项式 $C(x)$，使得它能被生成多项式 $G(x)$ 整除。
我们手头只有原始数据多项式 $D(x)$。显然 $D(x)$ 通常不能被 $G(x)$ 整除。

编码的过程就是：

1. 左移：先将 $D(x)$ 乘以 $x^{2t}$（其中 $2t$ 是纠错码字的数量）。这相当于在数据后面腾出了 $2t$ 个空位，留给纠错码。
2. 求余（即除法）：计算 $(D(x) \cdot x^{2t})$ 除以 $G(x)$ 的余数
   $R(x)$。（这一步可以模拟因式分解的大除法，也可以参考 CRC 纠错码生成的方式进行优化）
3. 相减（补齐）：用 $(D(x) \cdot x^{2t}) – R(x)$。
   • 为什么要减去余数？因为 $(D(x) \cdot x^{2t})$ 减去它的余数后，剩下的部分就一定能被 $G(x)$
     整除了！

这个最终结果 $C(x) = D(x) \cdot x^{2t} – R(x)$ 就是我们要发送的“带纠错的数据块”。

在实际的芯片或二维码生成软件中，你根本不会真的去运行“多项式长除法”，那是低效的。

工程师使用的是 LFSR (Linear Feedback Shift Register，线性反馈移位寄存器)。

解

二维码编码时，原始数据 $D$ 会被生成一个多项式 $C(x)=\sum_{i=0}^n{D_i x^i}$。在传输（或打印扫描）过程中，可能会引入错误 $E(x)$。接收端得到的是：
$$R(x) = C(x) + E(x)$$
如果存在 $e$ 个错误，那么 $E(x)$ 可以表示为：
$$E(x) = Y_1 x^{j_1} + Y_2 x^{j_2} + \dots + Y_e x^{j_e}$$
其中 $Y_i$ 是错误的大小（Magnitude），$j_i$ 是错误的位置（Position）。

你需要先知道的数学知识

在二维码的世界里，$GF(2^8)$ 是所有纠错数学的“运行平台”。GF指Galois Field，或 infinite field，即有限域（不过这个名字对理解帮助不大）。

• 元素的表达

在 $GF(2^8)$ 中，每个元素（取值范围为 0 到 255）对应一个次数小于 8 的多项式，其系数由该元素二进制表示的各位决定。
例如：0x05 (二进制 00000101) $\rightarrow x^2 + 1$。

• 不可约多项式 (Irreducible)：QR Code 使用 x^8 + x^4 + x^3 +

  x^2 + 1 (十六进制 0x11D)。它是一个“素数多项式”（即不可再被因式分解），确保了运算空间没有“零因子”，从而保证了除法（逆元）的存在，这就像我们在操作整数时指出对 $1e9+7$ 取模一样。

• 本原多项式 (Primitive)：0x11D

  同时也是一个本原多项式，这意味着存在一个 $\alpha$（通常取 0x02），使得 $\alpha$ 的幂次 ${\alpha^0, \alpha^1, \dots, \alpha^{254}}$ 能覆盖 $GF(2^8)$ 中所有非零元素。

• 运算规则

  • 加法与减法：在 $GF(2^8)$ 中，加法等于减法，且等于异或(XOR)，这是因为 $1+1=0$（每一位都得对2取模）。
  • 乘法：多项式乘法取模 0x11D。即当结果超过 8 位时，通过异或 0x11D 来“降位”。
  • 对数/反对数表 (Log/Exp)：
    • Exp[i] 表存储 $\alpha^i$ 的值。
    • Log[val] 表存储 $val$ 是 $\alpha$ 的多少次方。
    • 这使得 $A \times B$ 变为 Exp[(Log[A] + Log[B]) % 255]，运算复杂度从 $O(n)$ 降为 $O(1)$

(i) 计算伴随式（Syndromes）

多写一个公式就会吓跑一半读者

霍金

那么让我们开始吧 lol

编码器在生成码字时，确保了 $C(x)$ 能够被生成多项式 $G(x)$ 整除。$G(x)$ 是由用户选择的纠错等级确定的。

假如 $C(\alpha^i) = 0$，则有 $S_i = R(\alpha^i) = C(\alpha^i) + E(\alpha^i) = E(\alpha^i)$。

伴随式完全由错误项决定。如果所有 $S_i = 0$，说明没有错误。否则，我们有 $R(x)=\sum_{i=0}^n({D_i+E_i) x^i}=\sum_{i=0}^nD_ix_i+\sum_{i=0}^nE_ix^i$,$S_k = R(\alpha^k) = \sum_{j=0}^{n-1} e_j (\alpha^k)^j = e_0 + e_1 \alpha^k + e_2 (\alpha^k)^2 + \dots + e_{n-1} (\alpha^k)^{n-1}$，这种形式被称作“（加权）幂和”，考虑到未知数同时在指数和系数出现，显然直接解这种非线性方程组十分困难。

(ii) 找到错误位置

为了方便表述，我们令 $X_i=\alpha^{-i}$ 。

我们定义一个“错误位置多项式” $\sigma(x)$，其根就是 $X_i$。在下方公式的最后一个等号，我们设此连乘式的系数为 $\sigma_x$ 。

$$\sigma(x) = \prod_{i=1}^e (1 – x \cdot \alpha^{j_i}) = \sigma_e x^e + \dots + \sigma_1 x + 1$$

我们要找到一个 $\sigma(x)$，使得它的根是 $X_1, X_2, \dots, X_e$。

下面让我们曲线救国，尝试先解出 $\sigma$

由根的定义知，对于每一个根 $X_i$，都有：

$$\sigma(X_i) = X_i^e + \sigma_1 X_i^{e-1} + \dots + \sigma_e = 0$$

现在，我们把等式两边同时乘以 $(Y_i \cdot X_i^k)$：

$$Y_i \cdot X_i^k \cdot (X_i^e + \sigma_1 X_i^{e-1} + \dots + \sigma_e) = 0$$

展开后得到：

$$Y_i X_i^{k+e} + \sigma_1 Y_i X_i^{k+e-1} + \dots + \sigma_e Y_i X_i^k = 0$$

接下来，对所有 $i = 1 \dots e$ 求和：

$$\sum_{i=1}^e (Y_i X_i^{k+e}) + \sigma_1 \sum_{i=1}^e (Y_i X_i^{k+e-1}) + \dots + \sigma_e \sum_{i=1}^e (Y_i X_i^k) = 0$$

每一项里的求和 $\sum Y_i X_i^{k+m}$ 正好就是我们的加权幂和（即伴随式 $S_{k+m}$）。

于是，整个式子变成了：

$$S_{k+e} + \sigma_1 S_{k+e-1} + \dots + \sigma_e S_k = 0$$

这表明，无论权重 $Y_i$ 是多少，只要它不是 0（即确实发生了错误），它都会作为常数因子被保留在每一项中。由于方程右边是 0，这个常数因子根本不影响方程的解。这样一来，我们得以剥离错误大小对计算造成的影响，而只需考虑解出 $Y_i$ 。这个式子其实也可从牛顿恒等式²推导。

这是一个代数问题。给定 $2e$ 个伴随式，我们总能解出 $e$ 个错误的位置变量 $\sigma_i$。一旦 $\sigma(x)$ 被求出，取倒数即有 $X_i$，利用 钱氏搜索 (Chien Search)（即把 $GF(2^8)$ 的元素逐一代入测试），就能迅速找到哪些位置使得 $\sigma(x) = 0$，它们的倒数即为 $X_i$， 再取 $\log$ 即为错误位置。

(iii) 找到错误大小（Error Magnitude）

一旦知道了位置 $j_i$，我们就拥有了 $e$ 个线性方程，变量是 $Y_i$。
$$S_0 = Y_1 \alpha^{j_1} + Y_2 \alpha^{j_2} + \dots$$
$$S_1 = Y_1 \alpha^{2j_1} + Y_2 \alpha^{2j_2} + \dots$$

求解该方程组，即可精确算出每个错误位置的错误大小 $Y_i$。

(iv) 纠正错误：GF(2⁸) 的特性

在 $GF(2^8)$ 中，加法即为异或（XOR）运算。

因为 $R = C + E$，所以 $C = R – E$。在二进制域中，减法等同于加法，即 $C = R + E$。

只要把算出来的错误大小 $Y_i$ 与原始接收数据 $R$ 在对应位置进行异或运算，错误就被消除了。

排列至矩阵

微烦，从右下蛇形排列即可。

运用掩码&加入基本信息

你一定注意到二维码右上、左下、左上方的 Finder Pattern 了，它们引导解码器在杂乱的环境中寻找到二维码，因此十分重要，损坏了则无法扫描。顺便一提，画一条过其中心的水平/竖直线，则黑:白:黑:白:黑=1:1:3:1:1，这是研发团队调查出的印刷品中“最不常用的比率”³。

如图，为了防止数据混淆二维码边缘的 Finder Pattern 影响到解码器对二维码的寻找，我们需要对数据运用掩码（mask），将数据与上图右侧的7种掩码分别xor，我们选择其中最好的（标准是一个公式）。

此外我们还需将二维码版本、纠错等级写在 Finder Pattern 旁边。

后记

山木自寇也，膏火自煎也。桂可食，故伐之；漆可用，故割之。人皆知有用之用，而莫知无用之用也。

孔子

通过本文的撰写，我了解到了以数学为代表的理论学科的重要性：诞生于百年前的群论为 Reed–Solomon 纠错算法提供了有限域运算的基础，而看似仅用于因式分解的”长除法“——常配合因式定理试根以求余因式——竟然也能在纠错领域大显身手。它们的发明者并不以”直接产生经济利益“为目标进行研究，而是专注于解决自己对真理的好奇。这种对”科学纯粹性“的保持，正是人类文明的宝贵经验。

相反，如果将资源全部投入到“立刻能产生利润”的应用科学中，它会获得一段时期的快速增长，但由于缺乏底层逻辑的突破，它很快会陷入“内卷”和“技术瓶颈”。

无用之用，方为大用。

感谢 Gemini 3.1 Flash Lite 回答了笔者几十个问题，并不断激励笔者：

• 你的理解非常准确，几乎完全触及了 Reed-Solomon 编码的工程实质。
• 这是一个极其关键的问题！你直接击中了…
• 你的直觉非常敏锐！你之所以觉得它不像“牛顿恒等式”，是因为…

感谢春假让我领略了美丽的数学风光。

参考资料

1. QR code – Wikipedia ↩︎
2. 牛顿恒等式 – 维基百科，自由的百科全书 ↩︎
3. QR码的成功之路 | QRcode.com | DENSO WAVE ↩︎