二维码学习笔记——编码

2020-05-11 本文已影响0人 skogt

数据编码

源数据编码

编码模式（模式指示符）

我们先来说说数据编码。QR码支持如下的编码：

数字编码(Numeric Mode)：从0到9。如果需要编码的数字的个数不是3的倍数，那么，最后剩下的1或2位数会被转成4或7bits，则其它的每3位数字会被编成 10，12，14bits，编成多长还要看二维码的尺寸（下面有一个表Table 3说明了这点）

字符编码(Alphanumeric Mode)：包括 0-9，大写的A到Z（没有小写），以及符号$ % * + – . / : 包括空格。这些字符会映射成一个字符索引表。如下所示：（其中的SP是空格，Char是字符，Value是其索引值）编码的过程是把字符两两分组，然后转成下表的45进制，然后转成11bits的二进制，如果最后有一个落单的，那就转成6bits的二进制。而编码模式和字符的个数需要根据不同的Version尺寸编成9, 11或13个二进制（如下表中Table 3）

image

字节编码(Byte Mode)：支持0x00~0xFF内所有的字符
日文编码(Kanji Mode)：也是双字节编码。只能支持0x8140 - 0x9FFC, 0xE040 - 0xEBBF的字符，可以在这里找到

Extended Channel Interpretation (ECI) mode 主要用于特殊的字符集。并不是所有的扫描器都支持这种编码。

Structured Append mode 用于混合编码，也就是说，这个二维码中包含了多种编码格式。

FNC1 mode 这种编码方式主要是给一些特殊的工业或行业用的。比如GS1条形码之类的。

例如字符串123，就可以使用Numeric Mode；而HELLO WORLD需要用Alphanumeric Mode；Hello world需要使用Byte Mode.

简单起见，后面三种不会在本文中讨论。

下面两张表中，

Table 2 是各个编码格式的“编号”，这个东西要写在Format Information中。注：中文是1101
Table 3 表示了，不同版本（尺寸）的二维码，对于，数字，字符，字节和Kanji模式下，对于单个编码的2进制的位数。（在二维码的规格说明书中，有各种各样的编码规范表，后面还会提到）

image

下面我们看几个示例，

示例一：数字编码

在Version 1的尺寸下，纠错级别为H的情况下，编码： 01234567

1. 把上述数字分成三组: 012 345 67

2. 把他们转成二进制: 012 转成 0000001100； 345 转成 0101011001； 67 转成 1000011。

3. 把这三个二进制串起来: 0000001100 0101011001 1000011

4. 把数字的个数转成二进制 (version 1-H是10 bits ): 8个数字的二进制是 0000001000

5. 把数字编码的标志0001和第4步的编码加到前面: 0001 0000001000 0000001100 0101011001 1000011

示例二：字符编码

在Version 1的尺寸下，纠错级别为H的情况下，编码: AC-42

从字符索引表中找到 AC-42 这五个字条的索引 (10,12,41,4,2)
两两分组: (10,12) (41,4) (2)
把每一组转成11bits的二进制:

(10,12)  10*45+12 等于 462 转成 00111001110
(41,4) 41*45+4 等于 1849 转成 11100111001
(2) 等于 2 转成 000010

把这些二进制连接起来：00111001110 11100111001 000010
把字符的个数转成二进制 (Version 1-H为9 bits ): 5个字符，5转成 000000101
在头上加上编码标识 0010 和第5步的个数编码: 0010 000000101 00111001110 11100111001 000010

版本、纠错级别确定

首先依据源字符串可以知道应该采用哪种编码方式，然后需要先确定纠错级别，最后不同版本在此纠错级别+编码方式下的数据容量是不同的。我们只需找到最小的能容纳所有数据的那个版本即可。

举例来说：字符串 HELLO WORLD包含 11 个字符，通过上面的介绍得知，它应该使用字符编码Alphanumeric Mode，如果设定纠错级别是Q,通过查表得知1-Q可以容纳 16 个字符，那么最低就可以使用版本 1：

character-capacities-table

如果是字符串HELLO THERE WORLD(17 个字符)，那么最低版本就只能选 2 了。

另外，可以推断，二维码是存在数据容量上限的，它应该是40-L的容量：

Encoding Mode	Maximum number of characters a 40-L code can contain in that mode
Numeric	7089 characters
Alphanumeric	4296 characters
Byte	2953 characters
Kanji	1817 characters

也就是说，单纯存储数字的话，可以存 7089 个；只存大写字母的话，可以存大约 4k 个。

字符计数指示符

是一串二进制数字，表示源字符串的字符个数。字符计数指示符必须放在模式指示符之后。此外，字符计数指示符有特定的位长，具体取决于二维码的版本和编码模式：

单位 bits	Versions 1 ~ 9	Versions 10 ~ 26	Versions 27 ~ 40
Numeric mode	10	12	14
Alphanumeric mode	9	11	13
Byte mode	8	16	16
Kanji mode	8	10	12

具体步骤是：计算原始输入文本的字符数，将其转为二进制数字。根据版本和编码模式找到对应的位长，不够位长的在前面加 0 补齐。

例如 HELLO WORLD, 版本号为 1，则字符计数指示符需要 9 bits.
HELLO WORLD的字符数为 11，转为二进制1011，不够 9 位，需要补上 5 个 0，最终结果是000001011

那么针对HELLO WORLD，我们目前获得的二进制串是0010 000001011，0010是模式指示符Alphanumeric Mode。

字符串编码

这一步就是利用编码模式对源字符串进行编码，我们仍以HELLO WORLD为例，使用Alphanumeric Mode。

将字符两两分组，得到(H,E)、 (L,L)、(O, )、(W,O)、(R,L)、(D)
在字母索引表中找到对应的value，得到(17,14)、 (21,21)、(24,36)、(32,24)、(27,21)、(13)
对于每组数字，将第一个数字乘以 45 加上第二个数字（最大结果 2024），得到的结果再转为长度为 11 的二进制串，长度不足的前面补 0。例如(17,14) => 17*45+14=779 => 1100001011 => 01100001011。如果最后一组是单个字符，则用 6 位表示就行。最终得到结果：
01100001011 01111000110 10001011100 10110111000 10011010100 001101
追加到模式指示符和字符计数指示符之后，得到结果：
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101

后续的补齐

在给定版本和纠错级别后，源数据的编码结果是一个固定长度的二进制串，如果在上一步的结果没有达到这个长度，需要进行一些补齐操作。

例如1-Q下，源数据编码结果需要是13个字节，也就是104位:

total-number-of-data-codewords

而HELLO WORLD在上一步之后的二进制串是 74 位，所以需要补齐。

末尾追加至多4个0的终止符0000
末尾补更多的0直到8的倍数,例如上面74+4=78，就需要再补 2 个 0： 00
如果长度还没有达到目标，末尾重复添加固定的补齐码11101100 00010001直到满足长度。例如上面就需要添加11101100 00010001 11101100

以上就是源数据编码了，HELLO WORLD的编码结果由以下各部分组成：

模式指示符	字符计数指示符	字符串自身编码	终止符	补齐到 8 的倍数	补齐码
0010	000001011	01100001011 01111000110 10001011100 10110111000 10011010100 001101	0000	00	11101100 00010001 11101100

纠错码生成

根据源数据编码结果可以计算得到纠错码，使用的是Reed-Solomon纠错算法。二维码中有四种级别的纠错，这就是为什么二维码有残缺还能扫出来，也就是为什么有人在二维码的中心位置加入图标。

纠错码也和版本和纠错级别有关系,参考这个纠错表。

纠错表中包含group 1和group 2，每个group又包含至多 2 个block。源数据编码结果必须被分割成多达两个group，并且在每个group内也需要进一步分成block，在这个过程中源数据编码被顺序地分解。

以5-Q为例：

error-correction-code-words-and-block-information

可以知道的信息是：

源数据编码结果的总长度是 62 个字节
纠错码被分为group 1与group 2，两个group内都含有 2 个block
每个block包含 18 个字节的纠错码，所以纠错码的总长度是18*4 = 72个字节
group 1内的每个block，包含 15 个字节的源数据，以及 18 个字节的纠错码。也就是说源数据编码的前 15 个字节会放到group 1-> block 1中，第 16~30 这 15 个字节会放到group 1-> block 2中
group 2内的每个block，包含 16 个字节的源数据，以及 18 个字节的纠错码

另外细心点可以看的出来：给定版本后，源数据编码总长度+纠错码总长度是固定的，例如版本 5 就是 134 个字节。

至于每个block内部如何根据源数据编码计算得到纠错码（未去深究，后面有时间了再去研究下。下方是网上找的一个具体例子）由于二进制串太长，统一转成了 10 进制：

Group	Block	源数据编码	此 block 的纠错码
1	1	67 85 70 134 87 38 85 194 119 50 6 18 6 103 38	213 199 11 45 115 247 241 223 229 248 154 117 154 111 86 161 111 39
1	2	246 246 66 7 118 134 242 7 38 86 22 198 199 146 6	87 204 96 60 202 182 124 157 200 134 27 129 209 17 163 163 120 133
2	1	182 230 247 119 50 7 118 134 87 38 82 6 134 151 50 7	148 116 177 212 76 133 75 242 238 76 195 230 189 10 108 240 192 141
2	2	70 247 118 86 194 6 151 50 16 236 17 236 17 236 17 236	235 159 5 173 24 147 59 33 106 40 255 172 82 2 131 32 178 236

注：二维码的纠错码主要是通过Reed-Solomon error correction（里德-所罗门纠错算法）来实现的。
到这一步还没有结束，最终的编码结果并不是这些串顺序相连，而是交替连接。如何交替呢，规则如下：

不论数据码还是纠错码，把每个块的第一个字节先拿出来按顺度排列好，然后再取每个块的第二个字节，如此类推。

具体操作如下，首先对于源数据编码，先摆放好：

-	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
block 1-1	67	85	70	134	87	38	85	194	119	50	6	18	6	103	38	-
block 1-2	246	246	66	7	118	134	242	7	38	86	22	198	199	146	6	-
block 2-1	182	230	247	119	50	7	118	134	87	38	82	6	134	151	50	7
block 2-2	70	247	118	86	194	6	151	50	16	236	17	236	17	236	17	236

先取第一列的67， 246， 182， 70,再取第二列的67， 246， 182， 70， 85，246，230 ，247,依次类推最终结果是67， 246， 182， 70， 85，246，230 ，247 ……… ……… ，38，6，50，17，7，236。

对于纠错码也是一样的操作：

-	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
block 1-1	213	199	11	45	115	247	241	223	229	248	154	117	154	111	86	161	111	39
block 1-2	87	204	96	60	202	182	124	157	200	134	27	129	209	17	163	163	120	133
block 2-1	148	116	177	212	76	133	75	242	238	76	195	230	189	10	108	240	192	141
block 2-2	235	159	5	173	24	147	59	33	106	40	255	172	82	2	131	32	178	236

交替拿到的结果是：213，87，148，235，199，204，116，159，…… …… 39，133，141，236

把这两组交替结果放到一起，源数据的在前面：

67， 246， 182， 70， 85，246，230 ，247 ……… ……… ，38，6，50，17，7，236, 213，87，148，235，199，204，116，159，…… …… 39，133，141，236

最终的数据

对于某些版本的二维码，上面的结果不足填充满整个数据区+纠错码区，需要再在末尾补上一些 0，具体补多少个可以参照这个表：

https://image.3001.net/images/20190525/1558787612_5ce9361cb3205.png!small

版本 5 的二维码图案里，数据区+纠错码区一共有1079位，而我们上面的结果只有 134 个字节也就是1072位，所以需要再补上 7 个 0。

绘制二维码

3 个位置探测方块

先把三个大“回”字画整起来！分别放在左上、右上和左下角，回字的大小是固定的（无论Version如何，这个图案的尺寸就是这么大）

然后他们外围的一圈白色位置探测分隔符也可以直接画上。

https://www.thonky.com/qr-code-tutorial/separators2.png

N 个校正方块

校正方块是比较小的回字，它的大小也是固定的，只不过不同的版本都不同数量的校正方块：

alignment-patterns-count

举例version 8的(6,24,42)是如何画校正图形的：

alignment-patterns-example

2 个定位条（Timing Patterns）

在确定位置探测方块后，这两根条就很好画了。

https://www.thonky.com/qr-code-tutorial/function-patterns2.png

https://www.thonky.com/qr-code-tutorial/timing-m.png

头尾固定是黑色，中间黑白相间。

格式信息

https://www.thonky.com/qr-code-tutorial/format-reserved2.png

格式信息画在上面的蓝色部分，是固定 15 位的二进制串，具体组成部分为：

2 位表示纠错级别，一共有 4 种纠错级别。

http://officialblog-wordpress.stor.sinaapp.com/uploads/2013/10/13.png
3 位表示使用何种掩码图案，一共有 8 种掩码图案，具体要使用哪一个掩码在后面会具体介绍

https://image.3001.net/images/20190525/1558787639_5ce9363709673.png!small
10 位纠错信息，使用 BCH 编码计算得出
上面的 15 位再和固定的101010000010010做异或操作，这样就保证不会因为选用了 00 的纠错级别和 000 的掩码图案，从而造成全部为白色，这会增加扫描器的图像识别的困难。