二维码纠错码的里德所罗门编码原理

从二维码损坏到数据恢复的基本链路

二维码能在部分污损、遮挡后继续被读取，靠的不是图像处理“猜回”黑白模块，而是编码阶段加入了冗余数据。核心机制是 Reed–Solomon（里德–所罗门，简称 RS）编码：它把原始数据码字转换成包含校验信息的码字序列，使解码器有机会恢复被改动的符号。

QR Code 由数据码字、纠错码字和功能图形组成。功能图形包括定位图形、校正图形和时序图形等，它们帮助扫描器确定二维码的位置、方向和模块网格；污渍或遮挡可能让部分模块无法正确采样。

一次典型的解码流程大致如下：

1. 扫描器在图像中寻找定位图形，估计二维码的边界、旋转角度和透视变形。
2. 根据网格进行采样，把图像中的黑白区域转换成模块值，并读取格式信息、版本信息。
3. 按照格式信息选定掩模，撤销掩模对数据区域的扰动，再把模块组合成码字。
4. 对交错排列、按块组织的码字执行 RS 纠错，修正错误符号并恢复数据。
5. 解析模式指示符、字符数和内容，输出文本或其他载荷。

“看见图案”和“恢复数据”是两件事。定位图形受损、模块边界模糊时，解码器可能还没有获得可靠码字，就已经在定位阶段失败；RS 编码只能处理编码层面的符号错误，不能替代图像定位。

QR Code 的相关符号、编码和解码要求由 ISO/IEC 18004 规定，具体条款应以采用的标准版本为准。标准提供 L、M、Q、H 四档纠错等级，但实际可恢复程度还取决于版本、内容编码、印刷质量和损坏位置。

有限域运算如何生成冗余校验码

RS 编码使用 GF(256)，也就是包含 256 个元素的有限域。一个二维码码字可看作 0～255 之间的一个符号，但加法、乘法和除法不是普通整数运算；运算结果仍会被约束在这 256 个值内。

编码器把数据码字写成消息多项式，再选定一个生成多项式。将消息多项式乘以相应的幂后，用生成多项式做多项式除法，所得余数就是纠错码字。最终结构可以简化表示为：

数据码字 + 纠错码字 = RS 码字

例如，一个简化的 RS(10,6) 码包含 6 个数据码字和 4 个纠错码字。真实 QR Code 的参数会随纠错等级、版本和码块结构变化，不能把所有二维码都当成同一个 RS(10,6) 码。

RS 参数通常写作 RS(n,k)：k 是数据码字数，n-k 是纠错码字数。QR Code 往往把完整码字拆成多个块分别编码，某些版本还会使用长度不同的块组，因此“纠错等级”并不等于一个固定的 RS 参数。

解码器怎样定位并纠正错误码字

扫描图像后，某个码字可能因为模块污染而变成错误数值，这称为错误码字；如果解码器知道某个位置不可靠但不知道其内容，可把它视为擦除位置。二维码实际处理中，污渍通常先表现为未知错误，只有在图像分析能标记具体位置时，才可能按擦除错误处理。

RS 解码通常围绕以下步骤展开：

1. 计算一组综合症，它们相当于对接收码字做校验，先判断是否存在错误。
2. 利用综合症求出错误定位多项式。实现中可能使用 Berlekamp–Massey 算法，也可能使用扩展欧几里得算法。
3. 通过 Chien 搜索遍历有限域中的候选位置，找出定位多项式的根，从而确定错误码字的位置。
4. 计算错误值并修正相应码字，随后检查校验是否通过。

如果一个 RS 码包含 t 个纠错码字，通常最多能纠正约 t/2 个未知错误。已知位置的擦除错误消耗的校验能力不同，理论上可恢复的擦除数量可达到约 t；混合存在错误和擦除时，还要满足对应的综合约束。具体边界取决于码块参数和解码器实现。

四档纠错等级与实际生成操作

QR Code 的纠错等级及规范中的约略恢复能力如下：

• L：约 7%，适合图案简单、印刷和读取环境稳定的场景。
• M：约 15%，是常见的通用选择。
• Q：约 25%，适合可能出现一定污损的场景。
• H：约 30%，适合需要放置较小标志或面临较高损坏风险的场景。

这些比例描述的是码字层面的近似恢复能力，不是“可以遮住同样比例的二维码面积”。连续遮挡、定位图形受损、污渍分布、打印缩放和解码器实现都会改变结果；H 级也不保证任意 30% 的图像面积被遮挡后仍能读取。

QR Code 版本范围是 1 到 40。版本 1 的符号矩阵为 21×21 模块，版本每增加 1，边长增加 4 个模块，因此版本 40 为 177×177 模块。版本、字符编码、内容长度和纠错等级会共同决定最终码字布局；同样一段文字，在 UTF-8、数字模式或不同纠错等级下，所需版本可能不同。

使用二维码生成工具时，可以按下面的顺序操作：

1. 输入内容，并确认是否包含中文、网址参数或换行符。
2. 选择 L、M、Q 或 H；若需要放置标志，先从 Q 或 H 开始，但不要只依赖纠错等级弥补糟糕设计。
3. 让工具自动选择版本，或在需要固定尺寸时手动指定版本。ZXing、Python 的 qrcode 库和 Nayuki QR Code generator 对版本、掩模和纠错参数的接口可能不同。
4. 保留四周至少 4 个模块宽度的静区，也就是二维码与其他图形之间的空白边界。
5. 以最终使用尺寸缩放并打印，再用实际手机、不同距离和不同光照条件扫描测试。

Logo、文字和低对比度颜色不要放在定位图形、格式信息等高风险区域。二维码生成工具只能生成编码和图案，不能弥补静区不足、模块边界模糊、对比度过低或二维码被裁切造成的定位失败；实际容错还取决于扫描器、打印分辨率和表面材质。

读者最容易误解的地方

• 误解：H 级等于能遮住 30% 的二维码面积。
  事实：约 30% 描述的是码字纠错能力，不是任意图像区域的面积比例。
  实际影响：一小块连续遮挡若破坏定位图形，可能比更大范围的零散噪声更难解码。
• 误解：纠错码能把模糊图像自动变清晰。
  事实：RS 只能恢复符号值，不能修复失焦、低对比度或模块边界。
  实际影响：应优先保证足够尺寸、清晰缩放和黑白反差，再提高纠错等级。
• 误解：生成器提高纠错等级就能解决所有读取问题。
  事实：纠错发生在码字层，静区、定位、打印和材质属于图像与物理层问题。
  实际影响：生成后必须在实际打印尺寸下测试，而不是只检查屏幕上的预览图。