「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)$ 了

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

https://blog.tonycrane.cc/p/12ee036b.html

作者

TonyCrane

发布于

2021-12-01

更新于

2021-12-01

许可协议

评论