二维码（QR Code）的生成原理及解析

转载自：琦小虾
https://blog.csdn.net/ajianyingxiaoqinghan/article/details/78837864#comments
二维码生成原理及解析代码

自从大街小巷的小商小贩都开始布满了腾讯爸爸和阿里爸爸的二维码之后，我才感觉到我大天朝共享支付的优越性。最近毕业论文写的差不多了，在入职之前多学一些东西也是好的。这里秉着好奇心，研究一下二维码的生成，并尝试性写一个二维码解析源码。

注：暂时只有二维码原理，笔者这段时间会持续研究解析代码，并随进度持续更新。

参考网址：
《二维码的生成细节和原理》
《QR Code Tutorial》
《Hello World!》—— 知乎专栏文章
《为程序员写的Reed-Solomon码解释》

一. 二维码基本知识

二维码另一个名称是QR Code(Quick Response Code)，近年来在移动设备上经常使用，与传统条形码相比，可以存储更多的信息。二维码本质上是个密码算法，基本知识总结如下。
首先，二维码存在 40 种尺寸，在官方文档中，尺寸又被命名为 Version。尺寸与 Version 存在线性关系：Version 1 是 21×21 的矩阵，Version 2 是 25×25 的矩阵，每增加一个 Version，尺寸都会增加 4，故尺寸 Size 与 Version 的线性关系为：

Version 的最大值是 40，故尺寸最大值是(40-1)*4+21 = 177，即 177 x 177 的矩阵。

二维码结构如下图 1.1 所示：

图1.1 二维码结构

二维码的各部分都有自己的作用，基本上可被分为定位、功能数据、数据内容三部分。

• 定位图案：
  
  • Position Detection Pattern, 定位图案：用于标记二维码矩形的大小；用三个定位图案即可标识并确定一个二维码矩形的位置和方向了；
  • Separators for Position Detection Patterns, 定位图案分割器：用白边框将定位图案与其他区域区分；
  • Timing Patterns, 时序图案：用于定位，二维码如果尺寸过大，扫描时容易畸变，时序图案的作用就是防止扫描时畸变的产生；
  • Alignment Patterns, 对齐图案：只有在 Version 2 及其以上才会需要；
• 功能数据：
  
  • Format Information, 格式信息：存在于所有尺寸中，存放格式化数据；
  • Version Information, 版本信息：用于 Version 7 以上，需要预留两块 3×6 的区域存放部分版本信息；
• 数据内容：剩余部分存储数据内容
  
  • Data Code, 数据码；
  • Error Correction Code, 纠错码；

二. 数据编码

2.1 数据编码信息

二维码的数据编码信息如下图 2.1, 2.2 中的列表所示：

图2.1 模式编号指示器

图2.2 字符计数指示器中的位数

上图 2.1 中，展示的是二维码支持的数据编码模式。
注：其中中文编码模式为 1101；

上图 2.2 中展示了不同版本（即不同尺寸）的二维码，单个编码对应二进制的位数。
注：二维码规格说明书中，存在各式各样的编码规范表；

图2.1, 2.2 表格具体含义，在后面的例程中会具体讲解。

2.2 数据编码形式

2.2.1 数字编码(Numeric Mode)

数字编码的范围为 0~9。
对于数字编码，统计需要编码数字的个数是否为 3 的倍数：如果不是 3 的倍数，则剩下的 1 位或 2 位会被转为 4bits 或 8bits（十进制转二进制），每三位数字都会被编成 10bits, 12bits, 14bits，具体编码长度仍然需要二维码尺寸决定。

2.2.2 字符编码(Alphanumeric Mode)

字符编码的范围有：

• 数字 0~9；
• 大写 A~Z（无小写）；
• 几个符号$ % * + - . / 和空格。

上述字符映射为一个索引表，如下图 2.3 所示：

图2.3 字符映射索引表

图中 Char 表示字符，Value 表示字符对应的索引值。
索引表中共 45 种对应关系，字符编码的过程，就是将每两个字符分为一组，然后转成上图 2.3 的 45 进制，再转为 11bits 的二进制结果。对于落单的一个字符，则转为 6bits 的二进制结果。
此外，根据上图 2.2 的设定，对不同 Version 的二维码使用 9/11/13 个二进制表示。

注：
上图 2.3 中的 SP 代表空格。

2.2.3 字节编码(Byte Mode)

可以是 0-255 的 ISO-8859-1 字符。有些二维码的扫描器可以自动检测是否是 UTF-8 的编码。

2.2.4 日文编码(Kanji Mode)

日文编码同时也是双字节编码，同样也可以用于中文编码。
日文与中文编码流程基本相似：

1. 首先减去一个值；
2. 挑出差值结果的前两个 16 进制，乘以 0xC0；
3. 加上后两个 16 进制位；
4. 转为 13bits 编码；

按照日文编码集 SHIFT_JIS为参照，可查询日文字符的对应编码。以“雅”与“芒”为例，转换过程如下图 2.4 所示：

图2.4 日文编码流程展示

2.2.5 其他编码

其他类型的编码本文中不详细说明。其中包括：

• 特殊字符集(Extended Channel Interpretation Mode)：主要用于特殊的字符集，并不是所有的扫描器都支持这种编码；
• 混合编码(Structured Append Mode)：说明该二维码中包含了多种编码格式；
• 特殊行业编码(FNC1 Mode)：主要是给一些特殊的工业或行业用的，如GS1条形码等；

2.3 数据编码示例说明

分别用一个数字编码与字符编码的示例，说明数据编码的过程：

2.3.1 例程1：数字编码

问题：对于 Version 1 尺寸的二维码，纠错级别为 H，编码为：01234567
解析步骤：

1. 将上述数字分为三组：012, 345, 67；
2. 查询图 2.2 表格内容，Version 1 二维码的数字编码应转换为 10bits 的二进制数字，故将上面三组数字转为二进制分别为：012→0000001100, 345→0101011001, 67→1000011；
3. 将三个二进制串连接起来：0000001100 0101011001 1000011；
4. 将数字的个数转成二进制：对于数字编码，数字长度依旧用图 2.2 表格中查到的 10bits 二进制数字来表示，数字共有 8 个，故数字个数的二进制形式为：8→0000001000；
5. 查询图 2.1 表格内容，数字编码的标志为 0001，将编码标志与步骤 4 编码结果加到步骤 3 结果之前，故最终结果为：0001 0000001000 0000001100 0101011001 1000011

2.3.2 例程2：字符编码

问题：对于 Version 1 尺寸的二维码，纠错级别为 H，编码为：AE-86
解析步骤：

1. 在图 2.3 的字符索引表中分别找到 AE-86 五个字符的索引分别为：(10, 14, 41, 8, 6)；
2. 将五个字符两两分组：(10, 14) (41, 8) (6)；
3. 字符编码应将字符组转换为 11bits 的二进制，故上述三组字符首先转为 45 进制后再转为二进制：
   
   • (10, 14)：转为 45 进制：10×45+14=464；再转为 11bits 的二进制：00111010000；
   • (41, 8)：转为 45 进制：41×45+8=1853；再转为 11bits 的二进制：11100111101；
   • (6)：转为 45 进制：6；再转为 6bits 的二进制：000110；
4. 将步骤 3 中得到的三个二进制结果连接起来：00111010000 11100111101 000110；
5. 查询图 2.2 表格内容，Version 1 二维码的字符个数应转换为 9bits 的二进制数字，对于 5 个字符，二维码字符个数转为 9bits 二进制为：000000101；
6. 查询图 2.1 表格内容，字符编码的标志为 0010，将编码标志与步骤 5 编码结果加到步骤 4 结果之前，故最终编码结果为：0010 000000101 00111010000 11100111101 000110；

三. 结束符与补齐符

对于结束符和补齐符，我们直接举例进行说明。
问题：对于 Version 1 尺寸的二维码，纠错级别为 H，以笔者的英文名作为编码：CHANDLERGENG
按照 2.3.2 字符编码例程进行分析，得到编码如下：

3.1 结束符

在需要在对于上述字符的编码，需要在最后加上结束符。结束符为连续 4 个 0 值。加上结束符后，得到的编码如下：

如果所有的编码加起来不是 8 的倍数，则还需要在后面加上足够的 0。如上面一共有 83bits，所以与 8 的倍数还相差两位，故在最后加上 5 个 0，上表最终的数据变为：
00100000 01101010 00101101 00111011 00101001 01111001 01001000 10101101 11101000 00110110 00000000

3.2 补齐符

如果最后还没有达到我们最大的 Bits 数限制，则需要在编码最后加上补齐符(Padding Bytes)。
补齐符内容是不停重复两个字节：11101100 和 00010001。这两个二进制转成十进制，分别为 236 与17，具体不知道为什么选这两个值……关于每一个Version的每一种纠错级别的最大Bits限制，可以参看 QR Code Spec 的第35页到44页的 Table-7 一表（笔者参考的是《ISO/IEC 18004》2000版），大致如下图 3.1 所示：

图3.1 二维码纠错级别的最大Bits限制（部分）

上图 3.1 中提到的 codewords，可译为码字，一个码字是一个字节。对于 Version 1 的 H 纠错级别，共需要 26 个码字，即 104bits。现在加上用 0 补全的结束符，已经有了 88bits，故还需要补上 16 bits。补齐后的编码为：

00100000 01101010 00101101 00111011 00101001 01111001 01001000 10101101 11101000 00110110 00000000 11101100 00010001

以上数据即为数据码(Data Codewords)。

四. 纠错码

前文提到了不同的纠错级别(Error Correction Code Level)。有了纠错机制，才可以使得有些二维码有了残缺也可以扫码解析出来，才可以使得二维码中心位置可以供某些商家加上对解析不必要的图标。
二维码一共有四种纠错级别：

二维码对数据码加上纠错码的过程，首先要对数据码进行分组，即分成不同的块(Block)。参看如上图 3.1 所示 QR Code Spec 的第35页到44页的 Table-7 中的最下方说明了分组的定义表：

图4.1 二维码纠错级别说明（部分）

对于表中的最后两列的内容：

• 纠错块个数(Number of error correction blocks)：需要划分纠错快的个数；
• 纠错块码字数(Error Correction Code Per Blocks)：每个块中的码字个数，即有多少个字节Bytes；

表中最下面关于 (c,k,r) 的解释：

• c：码字总个数；
• k：数据码个数；
• r：纠错码容量

注：

• c,k,r的关系公式：。
• 纠错码容量小于纠错码个数的一般

以上图 4.1 中的 Version 5 + H 纠错机为例：图中红色方框说明共需要 4 个块（上下行各一组，每组 2 个块）。

第一组的属性：

• 纠错块个数 = 2：该组中有两个块；
• (c, k, r) = (33, 11, 11)：该组中每个块共有 33 个码字，其中 11 个数据码， 11×2=22 个纠错码；

第二组的属性：

• 纠错块个数 = 2：该组中有两个块；
• (c, k, r) = (34, 12, 11)：该组中每个块共有 34 个码字，其中 12 个数据码， 11×2=22 个纠错码；

具体示例如下表所示，且由于使用二进制会使得表格过大，故转为范围在 0~255 的十进制。其中组 1 的每个块，都有 11 个数据码， 22 个纠错码；组 2 的每个块，都有 12 个数据码，22 个纠错码。

二维码的纠错码主要是通过里德-所罗门纠错算法(Reed-Solomon Error Correction)实现的。

（关于 Reed-Solomon 算法，现在此处占坑，回头研究了再写上去）

五. 最终编码

此时得到了数据，但还不能开始画图，因为二维码还需要将数据码与纠错码的各个字节交替放置。

5.1 穿插放置

继续以第四章中给出的示例为例，给出其穿插放置的过程。

5.1.1 数据码穿插放置

第四章示例中的数据码如下表所示：

提取每一列数据：

• 第一列：67, 66, 247, 194；
• 第二列：85, 7, 119, 6；
• ……
• 第十一列：6, 199, 134, 17；
• 第十二列：151, 236；

将上述十二列的数据拼在一起：67, 66, 247, 194, 85, 7, 119, 6,…, 6, 199, 134, 17, 151, 236。

纠错码如下表所示：

同样的方法，将 22 列数据放在一起：199, 177, 96, 173, 11, 212, 60, 24, …, 148, 117, 118, 76, 235, 129, 134, 40。

上述部分即为二维码的数据区。

5.2 剩余位 (Remainder Bits)

对于某些 Version 的二维码，得到上面的数据区结果长度依旧不足，需要加上最后的剩余位。比如对于 Version 5 + H 纠错等级的二维码，剩余位需要加 7bits，即加 7 个 0。参看 QR Code Spec 的 Table-1 一表即可查询不同 Version 的剩余位信息，如下图 5.1 所示：

图5.1 不同 Version 的剩余位

六. 二维码的绘制

终于讲到二维码绘制过程了，绘制的过程按照顺序对图 1.1 中各个重要部分依次讲解。

6.1 定位图案 (Position Detection Pattern)

首先在二维码的三个角上绘制定位图案。定位图案与尺寸大小无关，一定是一个 7×7 的矩阵。如下图 6.1 所示：

图6.1 定位图案 (Position Detection Pattern)

6.2 对齐图案 (Alignment Pattern)

然后绘制对齐图案。对齐图案与尺寸大小无关，一定是一个 5×5 的矩阵。如下图 6.2 所示：

图6.2 对齐图案 (Alignment Pattern)

对齐图案绘制的位置，可参看 QR Code Spec 的 Table-E.1 一表查询，部分内容如下图 6.3 所示：

图6.3 对齐图案位置索引表（部分）

下图 6.4 是上述表格中 Version 8 的一个例子，对于 Version 8 的二维码，行列值在 6, 24, 42 的几个点都会有对齐图案。

图6.4 对齐图案例程 1

下图 6.5 是最近我老妈怂恿我用支付宝抢红包时给我发来的二维码，该二维码中只有一个对齐图案， 故 Version 应在 V2——V6 之间。

图6.5 对齐图案例程 2

6.3 时序图案 (Timing Pattern)

时序图案是两条连接三个定位图案的线，如下图 6.6 所示：

图6.6 时序图案例程 1

依旧拿支付宝红包的二维码为例，其时序图案如图 6.7 所示：

图6.7 时序图案例程 2

6.4 格式信息

格式信息如下图 6.8 所示：

图6.8 格式信息

格式信息在定位图案周围分布，由于定位图案个数固定为 3 个，且大小固定，故格式信息也是一个固定 15bits 的信息。每个 bit 的位置如下图 6.9 所示：（注：图中的 Dark Module 是固定永远出现的）

图6.9 格式信息位置

15bits 中数据，按照 5bits 的数据位 + 10bits 纠错位的顺序排列：

• 数据位占 5bits：其中 2bits 用于表示使用的纠错等级 (Error Correction Level)，3bits 用于表示使用的蒙版 (Mask) 类别；
• 纠错位占 10bits：主要通过 BCH Code 计算；

为了减少扫描后图像识别的困难，最后还需要将 15bits 与 101010000010010 做异或 XOR 操作。因为我们在原格式信息中可能存在太多的 0 值（如纠错级别为 00，蒙版 Mask 为 000），使得格式信息全部为白色，这将增加分析图像的困难。

纠错等级的编码如下图 6.10 的表格所示：

图6.10 纠错等级编码

关于蒙版图案的生成，在后文 6.7 中具体说明。格式信息的示例如下：

假设存在纠错等级为 M（对应 00），蒙版图案对应 000，5bits 的数据位为 00101，10bits 的纠错位为 0011011100：
则生成了在异或操作之前的 bits 序列为：001010011011100
与 101010000010010 做异或 XOR 操作，即得到最终格式信息：100000011001110

6.5 版本信息 (Version Information)

对于 Version 7 及其以上的二维码，需要加入版本信息。如下图 6.11 蓝色部分所示：

图6.11 版本信息

版本信息依附在定位图案周围，故大小固定为 18bits。水平竖直方向的填充方式如下图 6.12 所示：

图6.12 版本信息填充方式

18bits 的版本信息中，前 6bits 为版本号 (Version Number)，后 12bits 为纠错码 (BCH Bits)。示例如下：

假设存在一个 Version 为 7 的二维码（对应 6bits 版本号为 000111），其纠错码为 110010010100；
则版本信息图案中的应填充的数据为：000111110010010100

6.6 数据码与纠错码

此后即可填充第五章得到的数据内容了。填充的思想如下图 6.13 的 Version 3 二维码所示，从二维码的右下角开始，沿着红线进行填充，遇到非数据区域，则绕开或跳过。

图6.13 二维码数据填充（原始版）

然而这样难以理解，我们可以将其分为许多小模块，然后将许多小模块串连在一起，如下图 6.14 所示（截取自 QR Code Spec 的图 15）：

图6.14 二维码数据填充

小模块可以分为常规模块和非常规模块，每个模块的容量都为 8。常规情况下，小模块都为宽度为 2 的竖直小矩阵，按照方向将 8bits 的码字填充在内。非常规情况下，模块会产生变形。
填充方式上图 6.14，图中深色区域（如 D1 区域）填充数据码，白色区域（如 E15 区域）填充纠错码。遍历顺序依旧从最右下角的 D1 区域开始，按照蛇形方向（D1→D2→…→D28→E1→E2→…→E16→剩余码）进行小模块的填充，并从右向左交替着上下移动。下面给出若干填充原则：

原则 1：无论数据的填充方向是向上还是向下，常规模块（即 8bits 数据全在两列内）的排列顺序应是从右向左，如下图 6.15所示；

图6.15 常规模块内的填充方向

原则 2：每个码字的最高有效位（即第7个bit）应置于第一个可用位。对于向上填充的方向，最高有效位应该占据模块的右下角；向下填充的方向，最高有效位占据模块的右上方。
注：对于某些模块（以下图 6.17 为例），如果前一个模块在右边模块的列内部结束，则该模块成为不规则模块，且与常规模块相比，原本填充方向向上时，最高位应该在右上角，此时则变为左下角；
原则 3：当一个模块的两列同时遇到对齐图案或时序图案的水平边界时，它将继续在图案的上方或下方延续；
原则 4：当模块到达区域的上下边界（包括二维码的上下边界、格式信息、版本信息或分隔符）时，码字中任何剩余 bits 将填充在左边的下一列中，且填充方向反转；如下图 6.16 中的两个模块遇到了二维码的上边界，则方向发生变化；

图6.16 非常规模块填充方向的改变（举例于 QR Code Spec 图 13）

原则 5：当模块的右一列遇到对齐图案，或遇到被版本信息占据的区域时，数据位会沿着对齐图案或版本信息旁边的一列继续填充，并形成一个不规则模块。如果当前模块填充结束之前，下一个的两列都可用，则下一个码字的最高有效位应该放在单列中，如下图 6.17 所示：

图6.17 模块单列填充

6.7 蒙版图案

按照上述思路即可将二维码填充完毕。但是那些点并不均衡，如果出现了大面积的空白或黑块，扫描识别会十分困难，所以按照在前文 6.4 中格式信息的处理思路，对整个图像与蒙版进行蒙版操作(Masking)，蒙版操作即为异或 XOR 操作。
二维码又 8 种蒙版可以使用，如下图 6.18 所示，公式也在图中说明。蒙版只会和数据区进行异或操作，不会影响与格式信息相关的功能区。
注：选择一个合适的蒙版也是有一定算法的。

蒙版图案如下图 6.18 所示，对应的产生公式与蒙版 ID 如下图 6.19 的表格所示：

图6.18 蒙版图案

图6.19 蒙版图案产生公式

蒙版操作的过程与对比图如下图 6.20 所示，图中最上层是没有经过蒙版操作的原始二维码，其中存在大量黑色区域，难以后续的分析识别。经过两种不同蒙版的处理，可以看到最后生成的二维码变的更加混乱，容易识别。

图6.20 蒙版操作示例

蒙版操作之后，得到的二维码即为最终我们平常看到的结果。

七. 源码

笔者原本准备用 C++ 与 OpenCV 写一个二维码解析程序，现在学了二维码的原理后，发现好难。另外网上关于二维码解析与生成的程序基本都是用 Python 写的，笔者又想找个合适机会学习一下 Python，所以这段时间就准备从二维码入手，学习一下 Python 的基础～

源码及解析笔者会随学习的进度持续更新～

八. 后记

笔者学习完毕二维码内容后不禁感叹，二维码规则的制定当真是凝聚了多少研究者的心血。学无止境，在知识的海洋中，当真是需要抱着敬畏之心和谦卑的态度，才能体会到这片海洋的浩瀚。
研究二维码的过程十分有趣，学到了不少东西，后续过程中笔者会持续更新对二维码的学习心得体会～