「QRCode 标准阅读」#2 纠错码编码与图像生成
纠错码编码（7.5）
纠错容量（7.5.1）
纠错字（error correction codewords）可以纠正两种错误，一种是比如无法扫描或无法解码的已知位置的错误字（erasures），一种是未知位置的错误字（errors），一个 erasures 可以由一个纠错字纠错，而一个 errors 需要两个纠错字来纠错
可以纠错的 erasures 和 errors 的数量满足：
$$e+2t\leq d-p$$
其中 $e$ 是 erasures 的数量，$t$ 是 errors 的数量，$d$ 是纠错字的数量，$p$ 是被错误解析的保护字数量
其中 $p$ 由版本决定：
- $p=3$：版本 1-L
- $p=2$：版本 1-M、2-L
- $p=1$：版本 1-Q、1-H、3-L
- $p=0$：其他所有版本
分块编码纠错码
根据版本号及纠错等级，数据序列需要被分成 1 个或多个块，每块内需要单独编码纠错码
如果需要补充的话一律全部补充 0 比特到需要的长度
具体不同版本的分块块数和每块中数量安排以及纠错容量都在文档中 P38-44（pdf 中 P46-52）的大表格 Table 9 中
生成纠错码（7.5.2）
伽罗瓦域
生成纠错码之前要先将所有数据字转换成一个多项式，使其限制于伽罗瓦域 $GF(2^3)\bmod 100011101$ 中，而且后续的四则运算也都是该伽罗瓦域中的运算
具体伽罗瓦域的生成原理可以看：https://www.codenong.com/cs105738710/
简单来说就是多项式的加减法都是异或，乘除法要每一个比特模 2，每一个字节模 100011101（即该伽罗瓦域中的本原多项式 $x^8+x^4+x^3+x^2+1$）
具体多项式 mod 运算的方法可以看：https://blog.csdn.net/yaongtime/article/details/17200401
简单来说就是多项式的长除法取模，而且注意这里的加减都是伽罗瓦域中的加减，即异或
生成多项式（Annex A）
纠错码生成多项式的一般表达形式是：
$$g(x)=(x-\alpha^0)(x-\alpha^1)\cdots(x-\alpha^{n-1})$$
其中 $n$ 为纠错码字的个数，其中 $\alpha=2$， $\alpha^k$ 的是在伽罗瓦域下的运算，即：
$\alpha^0 = 1;\ \alpha^1=2;\ \alpha^2=4;\ \cdots;\ \alpha^7=128$
$\alpha^8=256\bmod 285=256\oplus 285=29;\ \alpha^9=29\times2=58;\ \cdots$
具体计算 $\alpha^k$ 的代码：
1 | def alpha(k): |
文档附录 A 中已经展开了所有可能 $n$ 值下的36个生成多项式
生成纠错码
文档里给了一个感觉比较晦涩难懂的图来展示生成纠错码的过程：
不是很容易理解，于是找了另一篇文章：https://blog.csdn.net/ljm1995/article/details/88819664
举个例子，比如要编码 12345678 这八个数字
版本 1-L，查 Table 9 得到分为 1 块，且该块内总字数为 26，数据字数为 19，纠错字数为 26-19=7
根据前面所说，比特流应该是： 0001 0000001000 0001111011 0111001000 1001110 0000
补成 8 的倍数长度： 00010000 00100000 01111011 01110010 00100111 00000000
添加 padding bits（补到 19 个字节）： 00010000 00100000 01111011 01110010 00100111 00000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100
写成多项式形式，次数是 19 次，整体乘 $x^7$：
$$16x^{25}+32x^{24}+123x^{23}+114x^{22}+39x^{21}+236x^{19}+\\17x^{18}+236x^{17}+17x^{16}+236x^{15}+17x^{14}+236x^{13}+\\17x^{12}+236x^{11}+17x^{10}+236x^{9}+17x^{8}+236x^{7}$$
再查附录 A 得到次数为 7 的生成多项式，并整体乘 $x^{18}$：
$$x^{25}+\alpha^{87}x^{24}+\alpha^{229}x^{23}+\alpha^{146}x^{22}+\alpha^{149}x^{21}+\\\alpha^{238}x^{20}+\alpha^{102}x^{19}+\alpha^{21}x^{18}$$
然后把第一个多项式除第二个多项式取余数
可以这样计算，把第二个多项式整体乘 16 即 $\alpha^4$：
$$\alpha^4x^{25}+\alpha^{91}x^{24}+\alpha^{233}x^{23}+\alpha^{150}x^{22}+\alpha^{153}x^{21}+\\\alpha^{242}x^{20}+\alpha^{106}x^{19}+\alpha^{25}x^{18}$$
计算出系数的值：
$$16x^{25}+163x^{24}+243x^{23}+85x^{22}+146x^{21}+\\176x^{20}+52x^{19}+3x^{18}$$
之后与第一个多项式异或得到：
$$131x^{24}+136x^{23}+197x^{22}+181x^{21}+216x^{19}+18x^{18}+\\236x^{17}+17x^{16}+236x^{15}+17x^{14}+236x^{13}+\\17x^{12}+236x^{11}+17x^{10}+236x^{9}+17x^{8}+236x^{7}$$
这之后最高次就变成了 24 次，重复整个过程直到结果只剩下 7 项（即最高次为 6 次）时即可得到：
$$188x^6+247x^5+62x^4+248x^3+53x^2+170x+224$$
所以纠错码就是：188 247 62 248 53 170 224
转为二进制： 10111100 11110111 00111110 11111000 00110101 10101010 11100000
所以整个二维码的编码区域（除格式信息外）全部内容就是：
00010000 00100000 01111011 01110010 00100111 00000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 10111100 11110111 00111110 11111000 00110101 10101010 11100000
纠错码可以直接用 python 的 reedsolo 包来求解：
1 | from reedsolo import RSCodec, ReedSolomonError |
剩余步骤（7.6~7.10）
合成序列（7.6）
首先按照 2 中所述给完整信息编码成数据序列，其中也包含 padding bits，且长度为 8 的倍数
然后根据 3.1.1 中所说对数据序列进行分块，然后对每块分别生成纠错码
最后把数据序列的所有块按照字节依次交错合成新的数据序列，然后把纠错码的所有块按照字节交错合成纠错码序列。把新的数据序列和纠错码序列连接在一起，如果总长度不够二维码的容量，则在后面补充 3/4/7 个 0 比特（需要补多少在 Table 1 中有定义）
而且这样也要保证最短的数据块在最前面（已经由 Table 9 定义）
比如 5-H 版本的序列，需要分为 4 块，前两块是 11 个数据字、22 个纠错字，后两块是 12 个数据字、22 个纠错字：
最后的序列就是 $D_1,D_{12},D_{23},D_{35},\cdots,D_{45},D_{34},D_{46},E_1,E_{23},\cdots,E_{88}$
填充数据（7.7）
把前面合成的完整消息序列填到二维码中，首先要先填充功能图案，然后预留出格式信息、版本信息的位置
填充时以两列为单位，即每次交替填充两列。从最右下角开始是最高位的比特，然后从右向左从下向上交替填充，到了上界时左转向下继续填充，遇到对齐图案直接穿过，遇到对齐图案边界则变为一行
也可以按照字节来依次填充，如果是向上填充，则最高位在下端，反之在上段。每个字节块内的最高位尽量取最右侧的，但如果最下(上)端只有一个比特的位置，则选它作为最高比特的位置
反正按顺序正常填就行了，遇到东西就绕
掩码遮盖（7.8）
填充后的数据还要遮盖一层掩码（异或）来平衡黑白块的数量，以及减少容易产生扫描错误的大块和形似功能图案的部分出现
QR 码一共有 8 种掩码，每个掩码有一个 3 bits 的编号，和一个生成公式。这个公式用来生成掩码图样，以左上为原点，向右、下为正方向，坐标满足这个公式的点在图样中是黑色（1），不满足的是白色（0）。在版本 1 中的掩码图像表现为：
进行掩码操作就是把除去功能图案和版本信息、格式信息之外的数据部分每一块的值与掩码图样异或
整个操作需要生成分别使用不同掩码的 8 个图样，然后计算出损失分数（penalty points score），然后采用损失分数最小的掩码模式作为最终的掩码模式
计算损失分数（7.8.3）
虽然进行掩码操作时仅对非功能图案、非版本信息格式信息的数据区域进行掩码，但是计算损失分数时按照整个二维码计算
计算损失分有四个规则：
- 相邻一行或一列内出现连续五个相同颜色块时损失分 +3，之后连续块数每加一，损失分 +1
- 寻找内部颜色相同的 2*2 的块，每出现一个损失分 +3
- 在每行和每列中寻找
10111010000和00001011101，每出现一个损失分 +40 - 评估黑色块占全部块数的比例，如果在 45%~55% 间则不增加损失分，在 40%~45%、55%~60% 间则损失分 +10，在 35%~40%、60%~65% 间则损失分 +10*2，以此类推
更详细的例子可以看：https://www.thonky.com/qr-code-tutorial/data-masking
然后对所有掩码结果计算损失分数后选择分数最低的一个作为最终结果
格式信息（7.9）
QRCode 的格式信息是 15 bits 的序列，其中前 5 位是数据，后 10 位是针对格式信息的纠错码（由 (15, 5) BCH 码生成）
5 bits 的数据前 2 位是纠错等级标识符，分别是 L -> 01 、M -> 00 、Q -> 11 、H -> 10
后 3 位是上面说到的掩码编号
然后后接 10 bits 纠错码，最后整体异或 101010000010010 防止产生全零数据序列
生成纠错码（Annex C）
先得到前 5 bits 的数据，然后化为多项式，整体乘 $x^{10}$，再除以生成多项式 $G(x)=x^{10}+x^8+x^5+x^4+x^2+x+1$ 得到余数转换为后 10 bits 的纠错码
- 例子
- 纠错等级 M，掩码编号 101
- 5 bits 数据：
00101 - 写为多项式： $x^2+1$
- 整体乘 $x^{10}$： $x^{12}+x^{10}$
- 除以 $G(x)$： 商 $x^2$，余数 $x^7+x^6+x^4+x^3+x^2$
- 余数转为 10 bits 纠错码：
0011011100 - 加上原数据：
001010011011100 - 异或
101010000010010：100000011001110
因为 5 bits 的数据一共只有 32 种情况，所以附录 C 中直接给出了完整的表格：
纠错：最多可以纠正 3 bits 的错误，先把格式信息异或 101010000010010 得到原始序列，然后与 Table C.1 中的有效格式信息进行对比，如果找不到说明有错误。此时仅选择 Table C.1 中与错误格式信息相差比特最少的一个作为纠正后的格式信息即可，如果相差少于等于 3 个比特，则视为纠正成功
填入二维码
左上角的格式信息区域填充一份完整的格式信息（最高位在左），左下角和右上角合起来是一份完整的格式信息（最高位在左下角的最下，最低位在右上角的最右）。并且左下角的格式信息上方（位置(4V+9,8)）有一块始终是黑色：
版本信息（7.10）
在版本 7 及以上的二维码中需要填入版本信息来确保准确度
版本信息只储存了该二维码的版本号（7～40），一共 18 bits，前 6 bits 为版本号的二进制（从 000111 到 101000），后 12 bits 为由 (18, 6) Golay code 生成的纠错码
不同于格式信息，因为版本号不会出现全零，所以不需要进行掩码操作
生成纠错码（Annex D）
和格式信息的纠错码类似，先把前 6 bits 转为多项式，然后整体乘 $x^{12}$，得到的结果除以生成多项式 $G(x)=x^{12}+x^{11}+x^{10}+x^9+x^8+x^5+x^2+x^1$ ，把余数转为 12 bits 二进制就是纠错码了
因为只有 34 个版本有版本信息，所以也就只有 34 种有效的版本信息序列，附录 D 的 Table D.1 中给出了完整的 34 个版本信息序列
和格式信息一样，纠错时对照表格选择相差比特数最小的即可。并且版本信息也只能纠正小于等于 3 个错误
填入二维码
在版本 7 以上的二维码中已经预留出了两个 6*3 大小的区域，一个位于左下分割线的上方时序图案左侧，一个位于右上分割线左侧时序图案的上方
按照下图顺序填入即可：
未完待续……「QRCode 标准阅读」#3 解码纠错过程
「QRCode 标准阅读」#2 纠错码编码与图像生成