二维码生成的细节和原理

时间：2021-09-08 来源：互联网编辑：宝哥软件园浏览：次

二维码，又称二维码，QR全称Quick Response，是近年来移动设备上超流行的一种编码方式。与传统的条形码相比，它可以存储更多的信息，代表更多的数据类型，如字符、数字、日文、中文等。这两天研究了二维码图像生成的细节，觉得这个东西是一个密码算法。我想在这里写一篇文章揭露一下。供好学的人一起学习。

关于二维码规范，请参考此pdf:http://raidenii.net/files/datasheets/misc/qr_code.pdf

基础知识

首先说二维码，有40种尺寸。官方名称是版本。版本1是21 x 21的矩阵，版本2是25 x 25的矩阵，版本3是29的大小。每次添加版本，都会增加4的大小。公式为：(V-1)*4 21(V为版本号)，最高版本40，(40-1)*4 21=177，所以最高是177177的平方。

让我们看一个二维码的例子：

定位模式

位置检测图案是用于标记二维码矩形尺寸的定位图案。这三种定位模式有白色边缘，称为定位检测模式的分隔符。为什么三而不是四意味着三可以识别一个矩形。

定时模式也用于定位。原因是二维码有40种尺寸。如果尺寸太大，需要一条标准线，否则扫描时可能会弯曲。

校准模式仅在版本2(包括版本2)以上的二维码中需要此项目，也用于定位。

功能数据

格式信息有各种大小，用于存储一些格式化的数据。

版本信息在上面=版本7，所以需要预留两个36的区域来存储一些版本信息。

数据码和纠错码

除上述位置外，其余位置存储数据码和纠错码。

数据编码

先说数据编码。二维码支持以下编码：

数字模式数字代码，从0到9。如果要编码的位数不是3的倍数，那么最后剩余的1或2位将被转换为4或7位，每隔3位将被编译为10、12、14位。编译的长度取决于二维码的大小(下面有一个表表3来说明这一点)

字母数字模式字符编码。包括0-9，大写的A到Z(不含小写)，符号$ % *。/:包括空格。这些字符被映射到字符索引表中。如下图：(其中SP为空格，Char为字符，Value为其索引值)编码过程是将字符成对分组，然后转换为下表中的45位二进制，再转换为11位二进制。如果最后只有一个，它将被转换成11位二进制。编码方式和字符数需要根据不同的版本大小编译成9、11或13个二进制文件(下表中的表3)

字节模式，字节码，可以是0-255个ISO-8859-1字符。一些二维码扫描仪可以自动检测是否是UTF-8编码。

汉字模式这是一个日语代码，也是双字节代码。同样，它也可以用于中文编码。从日本和中国字符的编码中减去一个值。比如将0X8140到0X9FFC中的字符减去8140，将0XE040到0XEBBF中的字符减去0XC140，然后将结果的前两个十六进制位乘以0XC0，再将最后两个十六进制位相加，最后转换为13位编码。

下图示例：

扩展通道解释(ECI)模式主要用于特殊字符集。并非所有扫描仪都支持这种编码。

结构化追加模式用于混合编码，即二维码包含多种编码格式。

FNC1模式主要用于一些特殊行业或行业。比如GS1条形码。

为简单起见，本文将不讨论最后三个。

在以下两个表格中，

表2是每种编码格式的“编号”，应写入格式信息。注：中文为1101

表3显示了不同版本(大小)二维码的数字、字符、字节和汉字模式下单个代码的二进制位数。(二维码的规范中有各种编码规范表，后面会提到)

我们来看几个例子。

示例1:数字编码

代码：01234567在版本1的大小下纠错级别为H时

1.将上述数字分成三组： 012 345 67

2.将其转换为二进制： 012和000001100；345到0101011001；67比1000011。

3.字符串这三个二进制： 0000001100 01011001 1000011。

4.将数字转换为二进制数(版本1-H为10位): 8个数字的二进制数为000001000。

5.将数字编码符号0001和步骤4的代码添加到前面： 0001 000001000 000001100 010101010101011000011。

示例2:字符编码

代码： AC-42在版本1的大小下纠错级别为h时

1.从字符索引表中找到AC-42的索引(10，12，41，4，2)

2.成对分组： (10，12) (41，4) (2)

3.将每组转换为11位二进制：

(10，12) 10*45 12等于462到00111001110(41，4) 41*45 4等于1849到1110011001 (2)等于2到000010

4.连接这些二进制文件：00111001110 1110011001 000010

5.将字符数转换为二进制(版本1-H为9位)，5个字符，5个转换为00000101

6.在头部第五步添加代码标记0010和数字代码： 0010 00000101 001110 111001110011001 00010

终止符和补码

如果我们有一个HELLO WORLD字符串要编码，根据上面的示例2，我们可以得到以下编码。

代码字符HELLO WORLD代码0010 00001011 0110001011 0111100110 10001101100 1011011000 100110101010101010100000010001101，我们还添加了结尾字符：

编码字符HELLO WORLD编码8位0010 000001011 0110001011 011100110 100011001100 1011000 10011000 100110101010101010101010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000

如果所有代码加起来都不是8的倍数，我们需要在它们后面加足够多的零，比如上面有78位，那么我们需要加2个零，然后按照8位分组：

00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000

填充字节(填充字节)

最后，如果我们还没有达到最大位数的限制，我们需要添加一些Padding Bytes，这意味着重复以下两个字节：11101100 00010001(这两个二进制数在转换成十进制数时是236和17，不知道为什么。我只知道规范是这么说的。)关于每个版本的每个纠错级别的最大位数限制，请参考二维码规范第28至32页的表-7。

假设我们需要对版本1的Q纠错级别进行编码，它最大需要104位，但是我们上面只有80位，所以我们需要补充24位，也就是我们需要3个Padding Bytes，所以我们加3，得到如下编码：

00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100

上述代码是数据代码，称为数据码字，每8位称为一个码字。我们还需要向这些数据代码添加纠错信息。

纠错码

上面我们讲了一些纠错等级，纠错码等级，二维码有四个纠错等级，这就是为什么二维码即使不完整也可以扫描的原因，这也是为什么有人在二维码中间加图标的原因。

纠错能力：可纠正7%的l级代码；可以纠正15%的m级代码；25%的q级代码可以纠正；并且可以校正30%的h级代码。首先，我们需要对数据编码进行分组，即将它们划分为不同的区块，然后对每个区块进行纠错编码。关于如何分组，我们可以查看二维码规范第33至44页的表-13至表-22中的定义表。请注意最后两列：

纠错码块的数量：需要多少块。每块纠错码：每个块中的码数，即所谓的码数，即8位，有多少个八位字节。

例如：上面的版本5 Q纠错级别需要4个blocks(两个Blocks为一组，共两组)，第一组的两个Blocks各有15个8位的纠错码(注：表中的码字只是一个8位字节)(注：最后一个例子中(c，k，r)的公式为：c=k)

下图给出了一个5-Q的例子(因为二进制写入会使表太大，所以我用十进制，我们可以看到每个纠错码有18个码字，也就是18个8-8位二进制数)

每个数据块1 1的数据块纠错码67857013487388519411950618610338213199114511524724。

1171541118616111139

2 24624666711813424273886221981991466 87204966020218212415720013427

12920917163163120133

2 1 1822302471195071181348738826134151507 148116177212761337524223876195

23018910108240192141

2 702471188619461515016236172361723617236 235159517324147593310640255

17282213132178236

注：二维码的纠错码主要通过里德-所罗门纠错算法实现。对我来说，这个算法相当复杂。里面有很多数学计算，比如多项式除法，把1到255的数映射成2的n次方(0=n=255)的伽罗瓦域，以及基于这些基础的纠错数学公式。因为我的数据库比较差，对我来说太复杂了，所以还是有一段时间没做了。请原谅我。(当然，如果朋友理解得好，可以找我咨询。)

最终编码

分散放置

如果你认为我们可以开始画画，那你就错了。二维码的混沌技术还没有结束，还需要把数据码和纠错码的所有码字交替放在一起。如何交替，规则如下：

对于数据码：取出每个块的第一个码字并按顺序排列，然后取出第一个块的第二个码字，以此类推。例如，上述示例中的数据码字如下：

第1 67 85 70 134 87 38 85 194 119 50 618 6 103 38第2 246 246 66 7 118 134 242 7 38 86 22 198 199 146 6第3 182 230 247 119 50 7 118 134 87 38 82 6 134 1 51 50 7第4 70 247 118 86 194 6

然后取第二列：67，246，182，70，85，246，230，247

等等：67，246，182，70，85，246，230，247 ……… …，38，6，50，17，7，236

纠错码也是如此：

第1 213 199 11 45 115 247 241 223 229 248 154 117 154 111 86 168 111 39第2 87 204 96 60 202 182 124 157 200 134 27 129 209 17 163 163 120 133第3 148 116 177 212 76 133 75 244

然后，将这两组放在一起(纠错码放在数据码之后)，得到：

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

这是我们的数据区。

剩余位

最后，添加提醒位。对于一些版本的二维码，上面不够长，还要加上剩余的比特，比如上面提到的5Q版本的二维码，再加上7个比特。只需在剩余的位上加零。参见二维码规范第15页表-1的定义表，该版本需要多少余数位。

绘制二维码地图

位置检测模式

首先，在三个角上绘制位置检测图案。(不管什么版本，这个图案的尺寸都这么大。)

对齐模式

然后，画出对齐图案(不考虑版本，这个图案的尺寸好大)

关于校准的位置，可以查看二维码规范第81页表E.1的定义表(下表为不完整的表)

下图是上表中版本8的示例(6、24、42)

时序模式

接下来是时序模式(不用说)

格式信息

然后是编队信息，下图中的蓝色部分。

格式信息是一条15位的消息，每一位的位置如下图所示：(注意图中的暗模块，它会一直出现)

这15位包括：

5个数据位：2位用于指示使用何种纠错级别，3位用于指示使用何种掩码10纠错位。主要用BCH码计算，然后15位与101010000010010异或。这样就保证了不会全部都是白色的，因为我们选择了00的纠错级别和000的Mask，这样会增加我们扫描仪的图像识别难度。

以下是一个例子：

下表显示了纠错级别：

掩模图案如下表23所示。

版本信息

然后是版本信息(版本7之后需要这个代码)，下图中的蓝色部分。

版本信息由18位组成，包括6位版本号和12位纠错码。以下是一个例子：

其填充位置如下：

数据和数据纠错码

然后按照以下方式填写我们的最终代码：从左下角开始，沿着红线填写我们的位，其中1是黑色，0是白色。如果遇到上述非数据区域，请绕过或跳过它。

掩模图案

这样，我们的地图就被填满了，但可能那些点是不平衡的。如果有大的空白或黑块，它会告诉我们扫描和识别的难度。所以我们要做Masking操作(该死的，不太复杂)。二维码的规格说明二维码有8个掩码可以使用，如下图：每个掩码的公式在每个数字下面。所谓掩码，说白了就是和上面生成的图进行异或运算。掩码只会与数据区异或，不会影响功能区。(注意：选择合适的掩码也是算法)