揭秘二维码—原理与实践

什么是二维码

二维码，英文：Quick Response Code，简称 QR 码。二维码最初由日本一家公司发明，后由国际标准化组织ISO批准进行标准化。现在二维码在我们生活中广泛使用，它具有比条形码更强的数据表示能力和更强的纠错能力。

我认为，二维码就是一种编码，把我们要传递的数据进行编码并转换成另外一种形式呈现出来。

技术原理

注：文中所指的QR Code Spec : ISO/IEC 18004:2000(E) - QR code specification 。

整体结构

二维码的整体结构如下图所示：

整体分为两大部分：功能区（Function Patterns）和编码区（Encoding region）。

功能区里又分为：

Finder Pattern：用于让解码器定位二维码的位置，分别位于三个角
Separator：起分隔作用
Timing Patterns：相当于坐标轴
Alignment Patterns：帮助解码器重新同步坐标映射，在二维码有一定污损的情况下

编码区里分为：

Format Information：用来存储纠错等级和掩码（mask）类型
Version Information：二维码一共有40个尺寸，Version 1是21 x 21的矩阵，Version 2是 25 x 25的矩阵，Version 3是29的尺寸，每增加一个version，就会增加4的尺寸。在 >= Version 7以上，需要预留两块3 x 6的区域存放一些版本信息
剩下的区域用来存放数据和纠错码

编码方式

二维码有多种编码模式，这里介绍四种：

Numeric Mode：支持数字0～9
Alphanumeric Mode：包括数字0～9，大写字母A～Z，和一些符号空格 $ % * + - . / : 。这些字符会映射成一个字符索引表。如下所示：

编码的过程是把字符两两分组，然后转成上表的45进制，然后转成11bits的二进制，如果最后有一个落单的，那就转成6bits的二进制。
Byte Mode：这个模式可以编码的字符就比上一个多一些，每把个bit构成一个字符，总共可以表示256个不同字符，具体映射表见QR Code Spec的Table 6
Kanji Mode：双字节编码，这个模式可以编码日文，也可以用于中文编码，下图是一个示例：

每种编码模式都有对应的标识符，如表1所示。模式表示要放在数据的前面。

Mode	indicator
Numeric	0001
Alphanumeric	0010
Byte	0100
Kanji	1000

表1 Mode Indicator

下面我们来看一个具体示例。

我们用Alphanumeric模式编码 AC-42 这5个字符，假设为Version1：

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

(10, 12) = 10 * 45 + 12 = 462 = 00111001110

(41, 4) = 41 * 25 + 4 = 1849 = 11100111001
1. = 000010
把这些二进制连接起来：00111001110 11100111001 000010
把字符的个数转成二进制，不同的Version对应的bit个数如Table3所示。Version1对应的是9bits，总共5个字符，转换成9-bit二进制数就是：000000101
在数据前面加上模式标识符0010和上一步得到的字符数编码：0010 000000101 00111001110 11100111001 000010

结束和补齐

假如我们有个HELLO WORLD的字符串要编码，根据上述示例，我们得到一下编码：

模式	字符数	Hello world编码
0010	000001011	01100001011 01111000110 10001011100 10110111000 10011010100 001101

我们还要加上结束符：

模式	字符数	Hello world编码	结束符
0010	000001011	01100001011 01111000110 10001011100 10110111000 10011010100 001101	0000

按8bits重排

如果所有的编码加起来不是8个倍数我们还要在后面加上足够的0，比如上面一共有78个bits，所以，我们还要加上2个0，然后按8个bits分好组：

00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000

补齐码（Padding Bytes）

最后，如果如果还没有达到我们最大的bits数的限制，我们还要加一些补齐码，Padding Bytes就是重复下面的两个bytes：11101100 00010001 。关于每一个Version的每一种纠错级别的最大Bits限制，可以参看QR Code Spec的第33页的Table-7一表，下面是这个表的一部分，里面也包含可表示的最大字符数：

假设我们需要编码的是Version 1的Q纠错级，那么，其最大需要104个bits，而我们上面只有80个bits，所以，还需要补24个bits，也就是需要3个Padding Bytes，我们就添加三个，于是得到下面的编码：

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

上面的编码就是数据码了，叫Data Codewords，每一个8bits叫一个codeword，我们还要对这些数据码加上纠错信息。

纠错码

正是因为有了纠错码的存在，二维码才可以在有一定污损的情况下被正确识别，这也是好多二维码中间有图标或头像依然可以被扫出来的理论基础。

二维码有四个纠错级别，分别如下：

二维码的纠错方式也是通过增加冗余位来实现纠错，这一点在本质上和（分组）奇偶校验，CRC循环校验等纠错方式是相同的，纠正 $t$ 个错误就需要 $2t$ 个纠错码。

具体来说，首先，我们需要对数据码进行分组，也就是分成不同的Block，然后对各个Block进行纠错编码，对于如何分组，我们可以查看QR Code Spec的第38页的Table-9的定义表，下面是该表的一部分：

倒数第二列表示了需要分多少个纠错块，最后一列表示每个纠错块的具体情况，(c, k, r) 分别代表：

c：该块中总共的Codeword个数
k：数据Codeword的个数
r：可以纠正的错误个数，所以纠错码的位(Codeword)数等于 2r

举个例子，上述的Version 5 + Q纠错级：需要4个Blocks（2个Blocks为一组，共两组），头一组的两个Blocks中各15个Codewords数据 + 各 18个Codewords的纠错码。下图给一个5-Q的示例（因为二进制写起来会让表格太大，所以都用了十进制）：

组	块	数据	纠错码
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 Code

关于每一块的纠错码是怎么来的，它是通过Reed-Solomon error correction（里德-所罗门纠错算法）实现的，这个地方应该是二维码最难的地方了。RS码是基于有限域的编码，这点和CRC循环冗余校验是一样的。

在这个有限域(GF(2))中，四则运算都是按比特模2的四则运算，即两个数的加减法就是按位异或（没有进位和借位），乘法和除法的相加过程也是模2加法。

每一个二进制数，都可以表示成一个多项式，每一位代表该项的系数，第几位代表指数，如100011101 可以表示为$x^8 + x^4 + x^3 + x^2 + 1$。

纠错码就是用数据多项式除以某一个本原多项式$g(x)$得到的余数。其中，本原多项式是什么就不多再解释，有兴趣的自行了解，在QR Code Spec中的附录A中有列出；这里面的除法是模2除法。

关于具体纠错方法和实现就不在这里展开，首先我的理解得也不是很清楚，其次这里面涉及的东西太多，尤其是数学知识，都说清楚可能需要专门写一篇文章。

最终编码

在画图前，还需要一步穿插放置的过程。

对于数据码：把每个块的第一个Codewords先拿出来按顺度排列好，然后再取第一块的第二个，如此类推。如，上述示例中的一部分Data Codewords如下：

块1	67	85	70	134	87	38
块 2	246	246	66	7	118	134
块 3	182	230	247	119	50	7
块4	70	247	118	86	194	6

我们先取第一列的：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

对于纠错码，也是一样的过程，然后，再把这两组放在一起（纠错码放在数据码之后）得到：

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

这就是我们的数据区。

Remainder Bits

对于某些Version的二维码，上面的还不够长度，还要加上Remainder Bits。比如：上述的5Q版的二维码，还要加上7个bits，Remainder Bits加零就好了。关于哪些Version需要多少个Remainder bit，可以参看QR Code Spec的Table-1的定义表。

画二维码图

Finder Pattern

终于到了激动人心的画图环节。首先，先把Position Detection图案画在三个角上，无论Version如何，这个图案的尺寸就是这么大：

接着用 HELLO WORLD 的例子，画完之后如下图所示：

Alignment Pattern

然后，再把Alignment图案画上，无论Version如何，这个图案的尺寸就是这么大：

关于Alignment的位置，可以查看QR Code Spec的第83页的Table-E.1的定义表，下面是该表的一部分：

举个例子，Version 2 的值是6和18。因此 Alignment Pattern 的位置应以(行，列)的 (18, 18) 为中心，因为 (6, 6), (6, 18), (18, 6) 和 Finder Patterns 的位置冲突，所以只剩一个。

画完如下：

Timing Pattern

接下来是Timing Pattern的黑白相间的线：

画完如下：

Format Information

再接下来是Formation Information，下图中的蓝色部分:

Format Information是一个15个bits的信息，每一个bit的位置如下图所示：

注1：图中的Dark Module，那是永远出现的注2：图中的第14位是最高位（The Most Significant Bit），第0位是最低位（The Least significant bit），即如果你得到的结果是100100001101000，那么第14位应该是1，第0位应该是0.

这15个bits中包括：

5个数据bits：其中，2个bits用于表示使用什么样的Error Correction Level， 3个bits表示使用什么样的Mask，每个纠错级别的标识符如Table25所示:
10个纠错bits，通过BCH码来计算。BCH码也是一种比较麻烦的编码，RS码是BCH码的一种特殊情况，有兴趣的读者自己了解一下。