ECC200 Data Matrix 中的 Reed Solomon 纠错码如何推导？

题目列出的七个纠错码字 20 246 205 226 4 231 123，对应的数据码字应为 66 67 68 142 52。原问题中的最后一个数据码字写成了 53，与这个结果不一致。

所有码字和多项式系数均以十进制表示，只有带 0x 前缀的数使用十六进制。

1. 先核对 ABC123 的数据码字

在 Data Matrix 的 ASCII 编码模式下，普通 ASCII 字符用其字符值加 1 表示；连续两个数字可以合并，用两位数的值加 130 表示。这两个规则可以在 ZXing 的 ASCIIEncoder 实现中核对。

按题目采用的编码方式：

因此，数据码字应当是：

66 67 68 142 52

在相同编码模式下，最后一个码字 53 表示字符 4，因此原问题中的那组数据对应的是 ABC124。

这里的 12×12 指包含定位边框、不含外围静区的符号尺寸。它可以容纳五个数据码字和七个纠错码字。本例的数据容量恰好用满，不需要额外填充码字。对应容量可见 ZXing 的 SymbolInfo 表及尺寸计算。

2. 理解 GF(256) 中的加法和乘法

ECC200 的 Reed Solomon 运算在有限域 GF(256) 中进行，每个域元素用一个字节表示。

它使用的域多项式是：

p(t) = t^8 + t^5 + t^3 + t^2 + 1

其二进制系数写成整数是 0x12D，本原元素取 α = 2。Data Matrix 的生成多项式从根 α^1 开始。这些参数可在 ZXing 的 GenericGF 定义中核对。

加法和减法都是 XOR

例如：

67 + 100 = 67 XOR 100 = 39

这里的加号表示有限域加法。减法也使用 XOR，因此一个数减去自身等于零。

乘法需要按域多项式约简

字节的二进制位表示多项式的系数。例如：

66 = 0b01000010  →  t^6 + t

两个元素相乘时，先做二进制多项式乘法，再对 p(t) 取余。

实现时可以不断左移一位；如果出现第九位，就与 0x12D 做 XOR。例如：

128 ⊗ 2 = 0x100 XOR 0x12D = 0x2D = 45

符号 ⊗ 表示有限域乘法，这种运算不同于普通整数乘法后取模 256。

3. 推导七个纠错码字对应的生成多项式

七个纠错码字需要一个七次生成多项式：

g(x) = (x + α^1)(x + α^2)…(x + α^7)

这里有两种多项式：p(t) 用来定义字节之间的乘法，g(x) 用来对整条消息生成纠错码。

本例中：

α^1 … α^7 = 2, 4, 8, 16, 32, 64, 128

从 g₀(x) = 1 开始，依次乘入每个因子：

gₖ(x) = gₖ₋₁(x) × (x + α^k)

前两步是：

g₁(x) = x + 2

g₂(x) = (x + 2)(x + 4)
      = x^2 + (2 XOR 4)x + (2 ⊗ 4)
      = x^2 + 6x + 8

继续运算，得到：

因此：

g(x) = x^7 + 254x^6 + 92x^5 + 240x^4
       + 134x^3 + 144x^2 + 68x + 23

这些是域元素的字节值，不是 α 的指数。ZXing 的专用 ECC200 实现把非首项系数按相反顺序存为 23 68 144 134 240 92 254，可参考其 ErrorCorrection 实现。使用时需要结合算法中的系数顺序来理解。

4. 对消息做多项式长除法

把更正后的五个数据码字按最高次在前写成消息多项式：

m(x) = 66x^4 + 67x^3 + 68x^2 + 142x + 52

为了留出七个纠错码字的位置，先乘以 x^7：

m(x)x^7 = 66x^11 + 67x^10 + 68x^9 + 142x^8 + 52x^7

这相当于在数据后面追加七个零：

66 67 68 142 52 0 0 0 0 0 0 0

接下来计算余式：

r(x) = m(x)x^7 mod g(x)

第一步：消去 66x^11

因为 g(x) 的最高项是 x^7，所以先用 66x^4 乘以 g(x)，再从被除式中减去它。

所需的有限域乘积为：

66 ⊗ [1, 254, 92, 240, 134, 144, 68, 23]
   = [66, 100, 241, 143, 181, 128, 47, 119]

其中第一个非首项乘积 66 ⊗ 254 = 100 也可以手算。不断乘以 2，得到：

66, 132, 37, 74, 148, 5, 10, 20

由于 254 = 0b11111110，取对应位的结果做 XOR：

132 XOR 37 XOR 74 XOR 148 XOR 5 XOR 10 XOR 20 = 100

然后把乘积与原系数对齐做 XOR：

原系数：66  67  68 142  52   0   0   0 0 0 0 0
乘  积：66 100 241 143 181 128  47 119 0 0 0 0
结  果： 0  39 181   1 129 128  47 119 0 0 0 0

最高项被消去后，下一步用 39x^3 乘以 g(x)，消去 39x^10。

重复直到余式次数小于 7

每一轮都取当前最高项的系数，乘以适当移位的 g(x)，然后做 XOR。下表省略已经消去的前导零，其余系数一直列到常数项：

最后得到的余式是：

r(x) = 20x^6 + 246x^5 + 205x^4 + 226x^3
       + 4x^2 + 231x + 123

按最高次到常数项读取，正好是题目给出的七个纠错码字：

20 246 205 226 4 231 123

完整的十二个码字为：

66 67 68 142 52 20 246 205 226 4 231 123

从多项式角度看，完整码字对应 c(x) = m(x)x^7 + r(x)。由于有限域加法和减法相同，得到的 c(x) 能被 g(x) 整除。

5. 用 Python 复现计算

下面的代码实现上述有限域乘法、生成多项式展开和长除法，不依赖第三方库。系数数组统一采用最高次在前的顺序。

def gf_mul(a, b):
    result = 0
    while b:
        if b & 1:
            result ^= a
        b >>= 1
        a <<= 1
        if a & 0x100:
            a ^= 0x12D
    return result


def poly_mul(a, b):
    result = [0] * (len(a) + len(b) - 1)
    for i, av in enumerate(a):
        for j, bv in enumerate(b):
            result[i + j] ^= gf_mul(av, bv)
    return result


def generator(n):
    g = [1]
    root = 1
    for _ in range(n):
        root = gf_mul(root, 2)
        g = poly_mul(g, [1, root])
    return g


def encode_ecc(data, n):
    g = generator(n)
    work = list(data) + [0] * n

    for i in range(len(data)):
        factor = work[i]
        for j, coefficient in enumerate(g):
            work[i + j] ^= gf_mul(factor, coefficient)

    return work[-n:]


print(generator(7))
print(encode_ecc([66, 67, 68, 142, 52], 7))
print(encode_ecc([66, 67, 68, 142, 53], 7))

计算结果为：

[1, 254, 92, 240, 134, 144, 68, 23]
[20, 246, 205, 226, 4, 231, 123]
[234, 170, 61, 100, 148, 163, 108]

最后一行是使用原问题中的 53 算出的 ECC，结果与题目给出的值不同。

6. 实现时需要注意什么

• 纠错运算的输入是完成高层编码及必要填充后的数据码字。本例采用 ASCII 编码模式；如果编码模式不同，应先确认实际产生的数据码字。
• 0x12D 和生成多项式从 α^1 开始这两个条件必须匹配。直接套用 QR Code 的有限域参数会得到不同结果。
• 纠错码字算出后，才进入二维模块的放置过程。本例不需要借助码字位置图就能完成上述数学计算。
• 上面的代码针对单个 Reed Solomon 块。本例只有一个块；处理更大的 Data Matrix 符号时，还需要按相应规则分块和交织，不能直接把所有数据当成同一个块计算。

备注：内容仅供参考。