「QRCode 标准阅读」#3 解码纠错过程

< #2

解码（11、Annex B）

简要的解码过程：

1. 定位并获取图像中的二维码，并把图像中的黑白块提取为 1 和 0
2. 读取格式信息
   • 释放掩码 101010000010010
   • 进行纠错
   • 如果纠错失败则将二维码镜面对称再尝试
3. 读取版本信息（如果有的话）
4. 读取格式信息中的掩码编号，并释放掩码
5. 读取并恢复数据字和纠错字
6. 纠错，如果检测到了错误就纠正
7. 把数据字解码得到结果

纠错（Annex B）

Annex B 讲的纠错过程很简略，而且符号说明不全，很难看懂

去学了学 PGZ 解码：Reed–Solomon_error_correction#Peterson–Gorenstein–Zierler_decoder

设当前版本下每块中有 $n$ 个字，$k$ 个数据字，$n-k$ 个纠错字，纠错容量为 $\nu$

首先定义原来的完整数据（即数据字和纠错字）从高位到低位为 $c_{n-1},c_{n-2},\cdots,c_0$ ，对应多项式为：

$$s(x)=\sum_{i=0}^{n-1}c_ix^i=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots+c_0$$

而且根据纠错码生成原理，$s(x)$ 可以被生成多项式 $g(x)$ 整除，其中

$$g(x)=\prod_{i=0}^{n-k-1}(x-\alpha^i)$$

所以 $s(x)$ 也有根 $s(\alpha^i)=0, i=0,1,\dots n-k-1$

再设接收到的消息多项式（可能有错）为 $r(x)$ ，误差多项式为 $e(x)$ ，满足：

$$r(x)=s(x)+e(x),\quad e(x)=\sum_{i=0}^{n-1}e_ix^i$$

先设一共有 $\nu$ 个错误，且每个错误的位置为 $i_k,k=0,1,\dots \nu-1$，所以有：

$$e(x)=\sum_{k=0}^{\nu-1}e_{i_k}x^{i_k}$$

最终的目标就是找到错误个数 $\nu$，错误位置 $i_k$，以及错误大小 $e_{i_k}$

计算典型值

首先定义典型值（syndromes）为把 $\alpha^j$ 传入 $r(x)$ 得到的值 $S_j$，有：

$$S_j=r(\alpha^j)=s(\alpha^j)+e(\alpha^j)=e(\alpha^j)=\sum_{k=0}^{\nu-1}e_{i_k}(\alpha^j)^{i_k},j=0,1,\dots,n-k-1$$

此时如果得到的典型值都为 0，那说明没有错误

为了方便，再令 $X_k=\alpha^{i_k},Y_k=e_{i_k}$，这样 $X_k$ 也能用来定位错误，同时也有：

$$S_j=\sum_{k=0}^{\nu-1}Y_kX_k^j$$

写成矩阵形式就是：

$$
\begin{bmatrix}
X_0^0 &X_2^0 &\cdots &X_{\nu-1}^0\\
X_0^1 &X_1^1 &\cdots &X_{\nu-1}^1\\
\vdots &\vdots & &\vdots\\
X_0^{n-k-1} &X_1^{n-k-1} &\cdots &X_{\nu-1}^{n-k-1}
\end{bmatrix}
\begin{bmatrix}
Y_0\\Y_1\\\vdots\\Y_{\nu-1}
\end{bmatrix}=
\begin{bmatrix}
S_0\\S_1\\\vdots\\S_{n-k-1}
\end{bmatrix}
$$

所以只要求得位置 $X_k$ 就能得到错误大小，但是此时并不是线性的

错误定位多项式

定义一个错误定位多项式（error locator polynomial）$\Lambda(x)$：

$$\Lambda(x)=\prod_{k=0}^{\nu-1}(1-xX_k)=1+\Lambda_1x+\Lambda_2x^2+\cdots+\Lambda_\nu x^\nu$$

可以看出 $\Lambda(X_k^{-1})=0$，所以对于 $0\leq j\leq\nu-1$ 有：

$$
Y_kX_k^{j+\nu}\Lambda(X_k^{-1}) =0
$$

$$
Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0
$$

$$
Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0
$$

$$
Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0
$$

所以把 $k$ 从 $0$ 到 $\nu-1$ 累加起来也为 0：

$$\sum_{k=0}^{\nu-1}\left(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0$$

然后转换为每项累加并提取出 $\Lambda_i$：

$$\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0$$

根据典型值的定义有：

$$S_{j+\nu}+\Lambda_1S_{j+\nu-1}+\cdots+\Lambda_\nu S_k=0$$

把 $S_{j+\nu}$ 移到右边，并展开所有 $j$ 可以得到矩阵形式：

$$
\begin{bmatrix}
S_{0}&S_{1}&\cdots &S_{\nu-1}\\S_{1}&S_{2}&\cdots &S_{\nu}\\\vdots &\vdots &&\vdots \\S_{\nu-1}&S_{\nu}&\cdots &S_{2\nu -2}
\end{bmatrix}
\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}
\end{bmatrix}
=
\begin{bmatrix}
-S_{\nu}\\-S_{\nu +1}\\\vdots \\-S_{2\nu-1 }
\end{bmatrix}
$$

此时是一个线性方程组，而且 $S_i$ 全部已知，可以解得 $\Lambda_i$

得到错误位置和大小

此时多项式 $\Lambda(x)$ 已经完全已知，所以可以求得其根（用 Chien search 算法在伽罗瓦域上求根）

再算其倒数即可得到 $X_k$ ，然后可以寻找到错误位置 $i_k$

这时也就可以带入第一个方程组求得错误大小 $Y_k$（或者利用 Forney algorithm）

得到了 $e(x)$ 后就可以根据 $r(x)$ 算出原始信息 $s(x)$ 了