二维码的纠错码原理及如何纠错(1)

本文主要是介绍二维码的纠错码原理及如何纠错(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文将通过例子来说明两个方面的内容：
（1）如何构建纠错码？
（2）有了纠错码之后如何纠错？

1 如何构建纠错码？

直接上例子，“hello world” 利用二维码的编码原理，转换成十进制数字为“32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17”，因此这个语句的消息多项式为：
$$\begin{array}{rl}& 32x^{15}+91x^{14}+11x^{13}+120x^{12}+209x^{11}+114x^{10}+220x^9+77x^8+67x^7\\ & +64x^6+236x^5+17x^4+236x^3+17x^2+236x^1+17\end{array}\text{\hspace{1em}(1)}$$

1.1 生成多项式

从下面这个网址可以轻松得到$n\ge 7$的生成多项式：
https://www.thonky.com/qr-code-tutorial/generator-polynomial-tool?degree=7

1.2 多项式除法

“Hello world”完整的消息多项式见公式(1)，为了确保在除法期间引导项的指数不会变得太小，将消息多项式乘以$x^n$，$n$是所需的纠错码字的数量。如当纠错码字的数量是10时，式(1)应该变成：

$$\begin{array}{rl}& 32x^{25}+91x^{24}+11x^{23}+120x^{22}+209x^{21}+114x^{20}+220x^{19}+77x^{18}+67x^{17}\\ & +64x^{16}+236x^{15}+17x^{14}+236x^{13}+17x^{12}+236x^{11}+17x^{10}\end{array}\text{\hspace{1em}(2)}$$

生成多项式的前导项也应该具有相同的指数，因此生成多项式也乘$x^{15}$得到下式：

$$\begin{array}{rl}& {\alpha }^0{x}^{25}+{\alpha }^{251}{x}^{24}+{\alpha }^{67}{x}^{23}+{\alpha }^{46}{x}^{22}+{\alpha }^{61}{x}^{21}+{\alpha }^{118}{x}^{20}+\\ & {\alpha }^{70}{x}^{19}+{\alpha }^{64}{x}^{18}+{\alpha }^{94}{x}^{17}+{\alpha }^{32}{x}^{16}+{\alpha }^{45}{x}^{15}\end{array}\text{\hspace{1em}(3)}$$

具体除法步骤如下：
（1）将生成多项式乘以消息多项式的前导项。
消息多项式的前导项是32，也就是${\alpha }^5$，乘上生成多项式后，生成多项式变成：
$$\begin{array}{rl}& {\alpha }^5{x}^{25}+{\alpha }^{256\%255}{x}^{24}+{\alpha }^{72}{x}^{23}+{\alpha }^{51}{x}^{22}+{\alpha }^{66}{x}^{21}+{\alpha }^{123}{x}^{20}+\\ & {\alpha }^{75}{x}^{19}+{\alpha }^{69}{x}^{18}+{\alpha }^{99}{x}^{17}+{\alpha }^{37}{x}^{16}+{\alpha }^{50}{x}^{15}\\ & ={\alpha }^5{x}^{25}+{\alpha }^1{x}^{24}+{\alpha }^{72}{x}^{23}+{\alpha }^{51}{x}^{22}+{\alpha }^{66}{x}^{21}+{\alpha }^{123}{x}^{20}+\\ & {\alpha }^{75}{x}^{19}+{\alpha }^{69}{x}^{18}+{\alpha }^{99}{x}^{17}+{\alpha }^{37}{x}^{16}+{\alpha }^{50}{x}^{15}\\ & =32x^{25}+2x^{24}+101x^{23}+10x^{22}+97x^{21}+197x^{20}+\\ & 15x^{19}+47x^{18}+134x^{17}+74x^{16}+5x^{15}\end{array}\text{\hspace{1em}(4)}$$
(2) 使用消息多项式对结果进行异或。
从下面这个式子也可以看出来，就是消息多项式和生成多项式中相同次数的项的系数进行了异或操作，经过这个操作之后，消息多项式中最高次数的项已经没有了（因为生成多项式和消息多项式拥有完全相同的第一项，一异或就没了）。
$$\begin{array}{rl}& (32\oplus 32)x^{25}+(91\oplus 2)x^{24}+(11\oplus 101)x^{23}+(120\oplus 10)x^{22}+(209\oplus 97)x^{21}\\ & +(114\oplus 197)x^{20}+(220\oplus 15)x^{19}+(77\oplus 47)x^{18}+(67\oplus 134)x^{17}+(64\oplus 74)x^{16}\\ & +(236\oplus 5)x^{15}+(17\oplus 0)x^{14}+(236\oplus 0)x^{13}+(17\oplus 0)x^{12}+(236\oplus 0)x^{11}+(17\oplus 0)x^{10}\\ & =0x^{25}+89x^{24}+110x^{23}+114x^{22}+176x^{21}+183x^{20}+211x^{19}+98x^{18}+197x^{17}\\ & +10x^{16}+233x^{15}+17x^{14}+236x^{13}+17x^{12}+236x^{11}+17x^{10}\\ & =89x^{24}+110x^{23}+114x^{22}+176x^{21}+183x^{20}+211x^{19}+98x^{18}+197x^{17}\\ & +10x^{16}+233x^{15}+17x^{14}+236x^{13}+17x^{12}+236x^{11}+17x^{10}\end{array}\text{\hspace{1em}(5)}$$
(3) 将生成多项式乘上一步的XOR结果的前导项。注意，这里的生成多项式已经经过了和现在的信息多项式等指数的过程，所以最高次是24。
在这个例子中，前导项是$89x^{24}$，做乘法的时候，把数字用α表示比较简单，89又等于${\alpha }^{210}$(这个可以查表得)，所以：

$$\begin{array}{rl}& ({\alpha }^{210}\ast {\alpha }^0)x^{24}+({\alpha }^{210}\ast {\alpha }^{251})x^{23}+({\alpha }^{210}\ast {\alpha }^{67})x^{22}+({\alpha }^{210}\ast {\alpha }^{46})x^{21}\\ & +({\alpha }^{210}\ast {\alpha }^{61})x^{20}+({\alpha }^{210}\ast {\alpha }^{118})x^{19}+({\alpha }^{210}\ast {\alpha }^{70})x^{18}+({\alpha }^{210}\ast {\alpha }^{64})x^{17}\\ & +({\alpha }^{210}\ast {\alpha }^{94})x^{16}+({\alpha }^{210}\ast {\alpha }^{32})x^{15}+({\alpha }^{210}\ast {\alpha }^{45})x^{14}\\ & ={\alpha }^{210}{x}^{24}+{\alpha }^{206}{x}^{23}+{\alpha }^{22}{x}^{22}+{\alpha }^1{x}^{21}+{\alpha }^{16}{x}^{20}\\ & +{\alpha }^{73}{x}^{19}+{\alpha }^{25}{x}^{18}+{\alpha }^{19}{x}^{17}+{\alpha }^{49}{x}^{16}+{\alpha }^{242}{x}^{15}+{\alpha }^0{x}^{14}\\ & =89x^{24}+83x^{23}+234x^{22}+2x^{21}+76x^{20}+202x^{19}+3x^{18}+90x^{17}\\ & +140x^{16}+176x^{15}+1x^{14}\end{array}\text{\hspace{1em}(6)}$$
(4) 将上一步得到的式子继续重复类似步骤2的异或操作，这个操作之后，最前面那项（次数为24次的那项）又成功没有了。
那么重复到什么时候好呢？从上面可以看出来，循环一次，就有一个消息多项式中的一项被消除，所以消息多项式有多少项，就进行多少次循环（这就好像除法进行到了最后一位）。上述例子循环16次后，就得到了下面这个式子（从这个式子中我们就可以看出来，刚开始的时候乘x^10有多明智，为什么是10而不是9或者8也从这里可以看出，因为生成多项式的最高次数是纠错码字的数目，一项项异或之后，最后的余数的位数和生成多项式的位数是相关的）

$$\begin{array}{rl}& 196x^9+35x^8+39x^7\\ & +119x^6+235x^5+215x^4+231x^3+226x^2+93x^1+23\end{array}\text{\hspace{1em}(7)}$$

现在我们就得到纠错码字了：196 35 39 119 235 215 231 226 93 23
得到纠错码字之后就是按照规范给填到二维码的格子里面。

2 如何进行纠错？

二维码采用Reed-Solomon Codes（简称RS编码）进行纠错。

2.1 RS编码

RS编码以word为编码和解码单位，大的数据块拆分到字长为$w$（取值一般为8或者16位）的word，然后对word进行编解码。 数据块的编码原理与word编码原理相同，后文中以word为例说明，变量${\mathrm{D}}_{\mathrm{i}}$, ${\mathrm{C}}_{\mathrm{j}}$将分别代表第$i$个数据码和第$j$个纠错码（以word为单位）。
输入数据为向量$\mathrm{D}=({\mathrm{D}}_1，{\mathrm{D}}_2，\dots ,{\mathrm{D}}_{\mathrm{n}})$，编码后为向量$({\mathrm{D}}_1，{\mathrm{D}}_2，\dots ,{\mathrm{D}}_{\mathrm{n}},{\mathrm{C}}_1,{\mathrm{C}}_2,\dots ,{\mathrm{C}}_{\mathrm{m}})$，RS编码可表示为如下图所示矩阵运算：

图1 RS编码示意图

上图最左边是编码矩阵（或称为生成矩阵、分布矩阵，Distribution Matrix），编码矩阵需要满足任意$n\times n$子矩阵可逆。

为方便数据存储，编码矩阵上部是单位阵（$n$行$n$列），下部是$m$行$n$列矩阵。下部矩阵可以选择范德蒙德矩阵或柯西矩阵。后文说明。

2.2 RS编码数据恢复原理

RS最多能容忍$k$个数据块被删除。 数据恢复的过程如下：
（1）假设${\mathrm{D}}_1$、${\mathrm{D}}_4$、${\mathrm{C}}_2$丢失，从编码矩阵中删掉丢失的数据块/编码块对应的行。

图2 数据缺失情况

（2）根据图1所示RS编码运算等式，可以得到如下${\mathrm{B}}^{\prime }$以及等式。

图3 数据缺失后的编码矩阵

（3）由于${\mathrm{B}}^{\prime }$是可逆的，记${\mathrm{B}}^{\prime }$的逆矩阵为 ${{\mathrm{B}}^{\prime }}^{-1}$，则${\mathrm{B}}^{\prime }\times {{\mathrm{B}}^{\prime }}^{-1}=\mathrm{I}$ 单位矩阵。两边左乘${\mathrm{B}}^{\prime }$逆矩阵${{\mathrm{B}}^{\prime }}^{-1}$后如下图：

图4 左乘逆矩阵的结果

（4）得到如下原始数据$\mathrm{D}$的计算公式：

图5 计算机原始数据

恢复原始数据$\mathrm{D}$：

图6 计算机原始数据

（5）对$\mathrm{D}$重新编码，可得到丢失的编码。

3 下一步工作

下一步将讨论范德蒙德（Vandermonde）矩阵和柯西（ Cauchy）矩阵。

这篇关于二维码的纠错码原理及如何纠错(1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---