二维码学习笔记(三) | 纠错编码

二维码笔记系列：

唠唠闲话

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

跳转链接：

RS编码基础
纠错与交织

基础知识

Galois 域上的运算

下设 $\mathbb{F}_{2^8}$ 为 Galois 域（理论基础参阅番外篇）

域 $\mathbb{F}_{2^8}$ 的计算性质：

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

$\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$

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

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

# 指数表
_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]

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

"""乘法运算"""
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 域 $\mathbb{F}=\mathbb{F}_{2^8}$ ，多项式环 $\mathbb{F}[x]$ 以 $\mathbb{F}_{2^8}$ 的元素为系数。其每个系数能存储 1 个字节（8 位）的信息。

自然地，我们有嵌入映射

$\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 的多项式。简记 $\mathbb{F}[x]_{n}$ 为次数不超过 n - 1 的多项式集合，则有同构关系

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

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

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

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

设纠错码数为 e，则取生成元多项式

$g(x) = (x-\alpha^0)(x-\alpha^1)\cdots(x-\alpha^{e-1})$
设原始信息为 $(c_{0},c_1,\cdots, c_{k-1})\in\mathbb{F}_{2^8}^k$ ，写成多项式形式为

$p(x) = c_0 + c_1 + \cdots + c_{k-1}x^k$
将多项式 $p(x)$ 乘以 $x^e$ ，并对 $g(x)$ 做带余除法

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

将 $p(x)x^e-r(x)$ 作为码字，写成向量形式为

$(r_0, r_1, \cdots, r_{e-1}, c_{0},c_1,\cdots, c_{k-1})$

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

举个例子：

设信息长为 2，纠错长为 3，初始数据为 (2, 5)
初始多项式 $f(x) = 2 + 5x$
生成元多项式
$g(x) = (x - 1)(x - 2)(x - 4) = 8 + 14x + 7x^2 + x^3$
余数多项式为 (200, 182, 121)
$\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) \mapsto 200 + 182x + 121x^2 + 2x^3 + 5x^4$

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

纠错能力

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

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

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

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

纠错与交织

纠错表

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

当数据量较大时，数据码先分成组（至多两组），组内分成若干个码块，每个码块内包含若干数据码字（字节）。

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

版本-纠错等级	总数据码	纠错码数/块	组 1 块数	数据码数/块(组1)	组 2 块数	数据码数/块(组2)
`V-eclevel`	`nb1nc1 + nb2nc2`	`ncodeword`	`nb1`	`nc1`	`nb2`	`nc2`
5-Q	62	18	2	31	2	16

查表可知，5-Q 版本的二维码数据码字总数为 62，分成 2 组，第一组分成两块，码字总数为 15+15；第二组分成两块，码字总数为 16+16。此外，每个码块分配的纠错码数目为 16。

码字交织

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

$\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*}$
第二步，计算每个码块的纠错码字，得到

$(c_1^i, c_2^i,\cdots, c_{16}^i), i=1,2,3,4$
第三步，按以下规则对数据码块进行交错：
- 取第1个码块的第1个码字
- 紧接着，取第2个码块的第1个码字
- 依次下去，直到取完所有码块的第1个码字
- 接着取第1个码块的第2个码字，同上依次进行
以 5-Q 二维码为例，对数据码块交错，得到

$\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-Q 二维码的纠错码块交错得到

$\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`

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