二维码笔记系列：

唠唠闲话

解码是编码的逆过程，与笔记 1-5 的内容正好相反。我们先略过一遍解码流程，再展开介绍一个关键步骤：数据纠错。

跳转链接：

解码流程

下设二维码已识别，并按一定格式要求输出为矩阵。二维码矩阵为 0-1 方阵，0代表暗模块，1代表亮模块，索引从 (0, 0) 开始，以左上角为原点。

二维码检查

  1. 根据矩阵大小计算二维码版本：版本 k 的二维码尺寸为 17+4k x 17+4k，其中 k 的取值范围为 1-40，下图为版本 3 的二维码：
    20220602230150

  2. 检查位置探测图形 Finder Patterns

    • 三个图形分别位于左上，右上，右下
    • 图形大小为 7x7
    • 模块宽比为 1:1:3:1:1

  3. 检查包围探测图形的白色分隔符 Separators

  4. 检查对齐图案 Alignment Pattern

    • 仅当二维码版本 ≥2 时存在
    • 图案大小为 5 x 5，按 黑-白-黑 的方式包围
    • 根据对齐图案位置表确定位置

  5. 检查时序图案 Timing Pattern

    • 连接探测图形的虚线，一条水平，一条垂直
    • 水平时序图案位于上数第 7 行（索引6）
    • 垂直时序图案位于左数第 7 列（索引6）
    • 时序图案总是以暗模块开始和结束
    • 时序图案可能与对齐图案重叠，但不影响，比如下图
      20220603090203

  6. 检查暗模块 Dark Module，位于左下角探测图形的分隔符的右上边缘

以上为二维码最基础的要素，检查无误后，下一步读取格式信息和版本信息。

版本和格式信息

  1. 格式信息区域：分隔符旁边的一条模块，规则如下：

    • 左上角的探测图案附近，分隔符下方和右侧的单模块条
    • 右上角的探测图案附近，分隔符下方的单模块条
    • 左下角的探测图案附近，分隔符右侧的单模块条
      20220603091217

  2. 格式信息 = 纠错等级(2 bit) + 掩码模式(3 bits)

    • 格式信息总长度为 15 比特（信息位 5 + 纠错位 10），数据按以下方式排列
      20220603210934

  3. 版本信息保留区域

    • 二维码码版本 7 及更高版本必须包含两个放置版本信息位的区域
    • 位于左下角探测图案上方的 6x3 块和右上角探测图案左侧的 3x6 块
    • 如下图蓝色区域
      20220603091647

  4. 二维码规范要求版本信息串使用 (18, 6) Golay Code，因此，版本信息字符为 18 位字符串，由 6 位二进制字符串和 12 个纠错为组成

  5. 格式信息以及版本信息的解码代码(Julia)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    """编码距离"""
    hamming_distance(x::Integer, y::Integer) = hamming_weight(x ⊻ y)
    hamming_weight(x::Integer) = hamming_weight(digits(x; base=2))
    hamming_weight(x::AbstractVector) = count(!iszero, x)

    """版本信息解码"""
    function qrdecode_version(version_code::Int)
       ver_info, best_dist = -1, 18
       for test_info in 7:40
          test_code = qrversion(test_info)
          test_dist = hamming_distance(version_code, test_code)
          if test_dist < best_dist
                best_dist = test_dist
                ver_info = test_info
          elseif test_dist == best_dist
                ver_info = -1
          end
       end
       return ver_info
    end

    """格式信息解码"""
    function qrdecode_format(fmt_code::Int)::Int
       fmt_info, best_dist = -1, 15
       for test_info in 0:31
          test_code = qrformat(test_info)
          test_dist = hamming_distance(fmt_code, test_code)
          if test_dist < best_dist
                best_dist = test_dist
                fmt_info = test_info
          elseif test_dist == best_dist
                fmt_info = -1
          end
       end
       return fmt_info
    end

读取版本信息后，与二维码尺寸进行比较，如果不匹配，则报错或重新识别。

提取数据位

所有检查无误后，按笔记 5 的规则施加掩码，并按笔记 4 的方式提取数据区的比特。

数据还原

得到数据位（数据模块+纠错模块）后，根据二维码版本和纠错等级“去交织”，还原数据码块和纠错码块的原本顺序。

数据纠错

使用 Reed Solomon 编码数据码块，若纠错失败，则报错，否则返回编码数据，具体算法在后边单独讲解。

数据解码

笔记 1 的逆过程，此时得到的数据内容为

1
mode indicator + character count indicator + encoded data + pad bits

即：模式指示符 + 字符计数指示符 + 编码数据 + 填充位
主要步骤：

  1. 读取头部 4 个字节（模式指示符），获取编码模式
  2. 根据编码模式和版本，计算字符计数指示符的长度
  3. 读取字符计数指示符，得到字符数目
  4. 根据编码模式，截取编码数据（二进制）并检查填充位是否正确性
  5. 根据编码规则，还原原始数据

这几个步骤大都比较简单，难点在第 4 步处理字节模式和 UTF8 模式的情况，由于两种编码使用相同的模式指示符。通常策略是先用 UTF8 模式读取数据，读取失败时（比如遇到无效字符），再用字节模式读取。

数据解码

Syndrome 纠错

  1. 设 R(x)=C(x)+E(x)R(x)=C(x)+E(x) 为接收码字，C(x)C(x) 为信息编码，E(x)E(x) 为干扰码字且错误数 v≤e=⌊d−12⌋v\leq e=\lfloor\frac{d-1}2\rfloor，设

    E(x)=∑k=0v−1ekxik, ek≠0,∀kE(x) = \sum_{k=0}^{v-1}e_kx^{i_k},\ e_k\neq 0,\forall k

    解码目的是 R(x)R(x) 中计算 E(x)E(x)。

  2. 计算 Syndromes sjs_j 如下

    sj=R(αj)=C(αj)+E(αj)=E(αj),∀j=0,⋯ ,e−1s_j = R(\alpha^j) = C(\alpha^j)+E(\alpha^j) = E(\alpha^j),\forall j=0,\cdots,e-1