二维码笔记系列:

唠唠闲话

纠错码字允许 QR 码阅读器检测和纠正 QR 码中的错误,本篇介绍ReedSolomon 纠错码的编码过程,以及与数据编码的交织方式。

跳转链接:


基础知识

Galois 域上的运算

下设 F28\mathbb{F}_{2^8} 为 Galois 域(理论基础参阅番外篇)

F28\mathbb{F}_{2^8} 的计算性质:

  • g(x)g(x) 为 8 次 F2\mathbb{F}_2 上的本原多项式,则 F28F[x]/(g(x))\mathbb{F}_{2^8}\cong \mathbb{F}[x]/(g(x))
  • 特别地,二维码规范取 g(x)=x8+x4+x3+x+1g(x)=x^8+x^4+x^3+x+1
  • F28\mathbb{F}_{2^8} 的元素对应到多项式,即

ε7ε6ε5ε4ε3ε2ε1ε0ε7x7+ε6x6+ε5x5+ε4x4+ε3x3+ε2x2+ε1x+ε0\varepsilon_7\varepsilon_6\varepsilon_5\varepsilon_4\varepsilon_3\varepsilon_2\varepsilon_1\varepsilon_0 \Rightarrow \varepsilon_7x^7+\varepsilon_6x^6+\varepsilon_5x^5+\varepsilon_4x^4+\varepsilon_3x^3+\varepsilon_2x^2+\varepsilon_1x+\varepsilon_0

  • 在这一对应下生成元写为 100011011100011011
  • F28\mathbb{F}_{2^8} 上的加法对应为二进制的异或,乘法为多项式的模 g(x)g(x) 运算,即二进制的自然乘法,但当二进制长度(多项式次数)超过 8 时,需要模去 100011011100011011 来减少长度
  • 特别的, 2 = 00000010 对应多项式 x,其为 F28\mathbb{F}_{2^8} 的乘法群生成元,通常记为 α\alpha

基于以上性质,我们得到 Galois 域 F28\mathbb{F}_{2^8} 上乘法运算的指数表。用 Julia 代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 指数表
_powtable = ones(Int, 256)
v = 1 # 幂次 2^0
for i in 2:256
v = 2 * v
if v > 255 # 二进制长度超过 8,需模去 100011011
v = xor(v, 285) # 285 = 0b100011011
end
t[i] = v # 记录 2^i 的值
end
# 指数字典和对数字典
powtable = Dict(zip(0:255, _powtable))
logtable = Dict(zip(_powtable, 0:254))
# 指数运算和对数运算
gfpow2(n::Int) = logtable[mod(n, 255)]
gflog2(n::Int) = antilogtable[n]

借助指数表,我们可以在 F28\mathbb{F}_{2^8} 上实现乘法运算:

1
2
3
4
5
6
7
8
9
10
11
"""乘法运算"""
function mult(a::Integer, b::Integer)
(a == 0 || b == 0) && return 0
return gfpow2(gflog2(a) + gflog2(b))
end

"""除法运算"""
function divide(a::Integer, b::Integer)
a == 0 && return 0
return gfpow2(gflog2(a) - gflog2(b))
end

Reed Solomon 编码

设 Galois 域 F=F28\mathbb{F}=\mathbb{F}_{2^8},多项式环 F[x]\mathbb{F}[x]F28\mathbb{F}_{2^8} 的元素为系数。其每个系数能存储 1 个字节(8 位)的信息。

自然地,我们有嵌入映射

FnF[x](a0,a1,,an1)a0+a1x++an1xn1\begin{align*} \mathbb{F}^n &\hookrightarrow \mathbb{F}[x] \\ (a_0, a_1, \cdots, a_{n-1}) &\mapsto a_0 + a_1x + \cdots + a_{n-1}x^{n-1} \end{align*}

左侧为字节长度 n 的数据集,右侧为次数小于等于 n - 1 的多项式。简记 F[x]n\mathbb{F}[x]_{n} 为次数不超过 n - 1 的多项式集合,则有同构关系

FnF[x]n\mathbb{F}^n \cong \mathbb{F}[x]_{n}

在这一同构下,我们将一串字节自然看作一个多项式。

Reed Solomon 编码是一种可设计的编码:指定数据长度(nmess)和纠错长度(nerr),设计所需编码。由于定义限制,两部分的总长度还要求满足 nmess + nerr ≤ 255

从多项式角度,Reed Solomon 编码如下给出

  1. 设纠错码数为 e,则取生成元多项式

    g(x)=(xα0)(xα1)(xαe1)g(x) = (x-\alpha^0)(x-\alpha^1)\cdots(x-\alpha^{e-1})

  2. 设原始信息为 (c0,c1,,ck1)F28k(c_{0},c_1,\cdots, c_{k-1})\in\mathbb{F}_{2^8}^k,写成多项式形式为

    p(x)=c0+c1++ck1xkp(x) = c_0 + c_1 + \cdots + c_{k-1}x^k

  3. 将多项式 p(x)p(x) 乘以 xex^e,并对 g(x)g(x) 做带余除法

    p(x)xe=g(x)q(x)+r(x), deg(r(x))<deg(g(x))p(x)x^e=g(x)q(x) + r(x),\ \deg(r(x))<\deg(g(x))

    p(x)xer(x)p(x)x^e-r(x) 作为码字,写成向量形式为

    (r0,r1,,re1,c0,c1,,ck1)(r_0, r_1, \cdots, r_{e-1}, c_{0},c_1,\cdots, c_{k-1})

    其中 (re1,,r1,r0)(r_{e-1},\cdots, r_1,r_0) 为纠错码字

举个例子:

  • 设信息长为 2,纠错长为 3,初始数据为 (2, 5)
  • 初始多项式 f(x)=2+5xf(x) = 2 + 5x
  • 生成元多项式

    g(x)=(x1)(x2)(x4)=8+14x+7x2+x3g(x) = (x - 1)(x - 2)(x - 4) = 8 + 14x + 7x^2 + x^3

  • 余数多项式为 (200, 182, 121)

    r(x)f(x)x3modg(x)200+182x+121x2modg(x)\begin{align*} r(x) &\equiv f(x)\cdot x^3 \mod g(x)\\ &\equiv 200 + 182x + 121x^2 \mod g(x) \end{align*}

  • 编码数据为 (200, 182, 121, 2, 5)

    f(x)200+182x+121x2+2x3+5x4f(x) \mapsto 200 + 182x + 121x^2 + 2x^3 + 5x^4

从编码规则不难看出,f(x)f(x) 映射像的前 k 个字符仍为 f(x)f(x),这种编码称为系统编码(System Coding)。系统编码的好处在于,纠错完成后,取前 k 个字符即可得到原始数据。

纠错能力

设生成元多项式的次数为 n,则 Reed Solomon 能够:

  • 填补不超过 n 个的位置缺失
  • 检测不超过 n 的位置错误
  • 纠正不超过 n2\frac n2 个位置错误
  • 同时填补 ρ\rho 个位置缺失,并纠正 σ\sigma 个位置错误,且满足 ρ+2σn\rho + 2\cdot \sigma \leq n

这种纠错能力和 ReedSolomon 编码满足 Singelton 边界有关。

纠错的核心思想是将低维数据映射到高维数据,当映射后的数据出现少量错误时,我们仍能还原初始数据。RS 码将信息长为 k 的数据集映射到信息长为 k + e 的数据集,进而提升容错能力。

纠错与交织

纠错表

上节提到信息长和纠错长度需满足限制条件 nmess + nerr ≤ 255,当我们要传输更长信息时,就得将数据拆解为若干小块。

  1. 当数据量较大时,数据码先分成组(至多两组),组内分成若干个码块,每个码块内包含若干数据码字(字节)。

  2. 以版本 5 为例,下表为纠错表关于版本 5-Q 的数据,更多表格内容参看:纠错表

    版本-纠错等级 总数据码 纠错码数/块 组 1 块数 数据码数/块(组1) 组 2 块数 数据码数/块(组2)
    V-eclevel nb1*nc1 + nb2*nc2 ncodeword nb1 nc1 nb2 nc2
    5-Q 62 18 2 31 2 16
  3. 查表可知,5-Q 版本的二维码数据码字总数为 62,分成 2 组,第一组分成两块,码字总数为 15+15;第二组分成两块,码字总数为 16+16。此外,每个码块分配的纠错码数目为 16。

码字交织

  1. 第一步,将码字按顺序进行分解并分组,比如对于 5-Q 二维码 62 个码字分组后为:

    (w1,,w62)={B1:(w1,,w15),第一组第一块B2:(w16,,w30),第一组第二块B3:(w31,,w46),第二组第一块B4:(w47,,w62),第二组第二块\begin{align*} (w_1,\cdots, w_{62}) =\begin{cases} B_1:(w_1,\cdots, w_{15}), &\text{第一组第一块}\\ B_2:(w_{16},\cdots, w_{30}), &\text{第一组第二块}\\ B_3:(w_{31},\cdots, w_{46}), &\text{第二组第一块}\\ B_4:(w_{47},\cdots, w_{62}), &\text{第二组第二块} \end{cases} \end{align*}

  2. 第二步,计算每个码块的纠错码字,得到

    (c1i,c2i,,c16i),i=1,2,3,4(c_1^i, c_2^i,\cdots, c_{16}^i), i=1,2,3,4

  3. 第三步,按以下规则对数据码块进行交错:

    • 取第1个码块的第1个码字
    • 紧接着,取第2个码块的第1个码字
    • 依次下去,直到取完所有码块的第1个码字
    • 接着取第1个码块的第2个码字,同上依次进行
  4. 以 5-Q 二维码为例,对数据码块交错,得到

    (w11,w12,w13,w14,,w151,w152,w153,w154,w163,w164)\begin{align*} (w_1^1,w_1^2,w_1^3,w_1^4,\cdots, w_{15}^1,w_{15}^2,w_{15}^3,w_{15}^4,w_{16}^3,w_{16}^4) \end{align*}

  5. 第四步,数据码块处理完毕后,用同样方法处理纠错码块,纠错码跟在数据码之后

  6. 5-Q 二维码的纠错码块交错得到

    (c11,c12,c13,c14,,c161,c162,c163,c164)\begin{align*} (c_1^1,c_1^2,c_1^3,c_1^4,\cdots, c_{16}^1,c_{16}^2,c_{16}^3,c_{16}^4) \end{align*}

余数比特

对于某些二维码版本,最终构建信息的二进制数据长度不足,需要在最后添加一定数量的 0 比特,这些 0 比特称为余数比特。对于版本 5 二维码,需要在最后添加 7 个余数比特。一般地,通过查表可知每个版本需要添加的 0 的数目,即:

添加比特数目 二维码版本
0 1,7-13,35-40
3 14-20,28-34
4 21-27
7 2-6

注意添加余数比特的数目只与二维码版本有关,与纠错等级无关。

相关链接

纠错表
二维码的纠错编码
构建最终信息