QR code，Quick Response，一种矩阵条形码，二维条形码，在1994年由供职于日本电装公司Denso Wave(丰田子公司)一名职员腾弘原（Masahiro Hara）发明，灵感来源于围棋，用于追踪流水线上的汽车，二维码之所以能快速在汽车制造领域外流行是因为自身的快速读取性，高存储性，更低的容错率，不需要特殊的设备读取。

二维码里可包含地理信息，身份标识，网页地址，是对这些信息进行了编码

可编码的原始信息可分为四种：

编码模式	内容
Numeric	1234567890
Alphanumeric	ABCDE…..Z 1234567890
Byte	0000111100001111
Kanji	漢字の部首・画数・読み方・筆順・意味などを調べることができる漢字辞典サイトで

每一种模式使用不同的方法把text转换为比特，尽可能使用效率高的方法，编码后的结果是一串比特，8bit为一个单位，称为data codeword。

二维码拆分

1 .Quiet zone: 二维码存放的区域，白色底板，用来和其他的图案隔离开来，比如被玷污的信封上，报纸上或者有过摩擦的纸箱表面

2.Finder patterns：左上，右上，左下的三个黑白正方形，用来确认是否为二维码，以及二维码的旋转方向

3.Alignment pattern: 在非正常情况下用来确保可以正常解码，比如印在凸面上，扫描角度不正等

4.Timing pattern:紫色连线部分，小黑白方块组成，用来辅助确认二维码里具体的信息（data cell），尤其是二维码污损的情况下

5.Version infomation:绿色部分，用来确认版本信息

6.Data Cells:剩余的黑白点部分，全为具体数据

容错率

Error Correction Level	Error Correction Capability
L (low)	Recovers 7% of data
M (medium)	Recovers 15% of data
Q (quarter)	Recovers 25% of data
H (high)	Recovers 30% of data

容错率的特点是在原始数据后面加上Reed-Solomon Code。打个比方，一段原始数据里包括100个codeword，需要修复50个，那么需要在数据尾部挂上100个Reed-Solomon code（两倍），这样下来总数为200codeword，容错率为25%，容错等级为Q。也可以认为刚才的例子容错率为50%，鉴于在通常情况下数据部分会污损，所以还是按25%来。容错率越高，数据越大

PS：Reed-Solomon Code 是一种在制作音乐CD领域较为常用的数学方法，一开始发明用来卫星或者星际通讯降噪，可以在比特级纠错

确定数据使用的最小版本

最小的二维码为21 * 21像素，最大是177 * 177像素，不同的尺寸代表不同版本，21 * 21为version 1，25 * 25为version 2，4个像素为一个步进，以此类推，177 * 177为version 40。

每一个版本都有数据容量上限，数据容量取决于编码的信息长度和纠错级别，字符容量表展示了每个版本不同纠错级别的容量

打个比方，HELLO WORLD包含11个字符，使用Q级别纠错，版本1 Alphanumeric最大容量是16字符，那么版本一就是HELLO WORLD最低版本，依次类推

下表是二维码数据容量的上限

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

添加模式标识

每一种编码模式机器需要通过在数据前添加标识来确定，HELLO WORLD的编码代码为表格第二行，0010

Mode Name	Mode Indicator
Numeric Mode	0001
Alphanumeric Mode	0010
Byte Mode	0100
Kanji Mode	1000
ECI Mode	0111

添加个数标识

个数标识表示字符串长度，HELLO WORLD长度为11，二进制1011，版本1的比特位长度为9，在左边补齐0，结果为 00000 1011，添加在模式标识后为 0010，00000 1011

下面是各版本规定的比特位长度

Versions 1 - 9

Mode	Bits
Numeric	10
Alphanumeric	9
Byte	8
Japanese	8

Versions 10 - 26

Mode	Bits
Numeric	12
Alphanumeric	11
Byte	16
Japanese	10

Versions 27 - 40

Mode	Bits
Numeric	14
Alphanumeric	13
Byte	16
Japanese	12

真实数据编码

以HELLO WORLD Alphanumeric模式为例，参考编码表为

把字符串拆分为如下形式,O和空格在一起

1	HE,LL,O ,WO,RL,D

找到对应的数字

H → 17
E → 14

第一个乘以45，加第二个

(45 * 17) + 14 = 779

转换为11bit长的字符串，左边补0

779 → 01100001011

以此类推得到所有的数据，最后一位D -> 13 转换长度为6比特 001101

Mode Indicator	Character Count Indicator	Encoded Data
0010	000001011	01100001011 01111000110 10001011100 10110111000 10011010100 001101

转换为8-bit CodeWord

二维码要求数据必须填满，参考纠错表，此处，我们采用的是版本一，Q级别，可以有13个CW，每个CW为8-bit，总容量为13*8=104bit，到了这一步，我们的数据总长度为74，离满格还差34，需要在尾部添加四个0，最多四个，如果数据长度为102，则补齐两个0，以此类推，到现在我们的数据为

Mode Indicator	Character Count Indicator	Encoded Data	Terminator
0010	000001011	01100001011 01111000110 10001011100 10110111000 10011010100 001101	0000

拆分补齐数据，使之长度为8的倍数

74 + 4 = 78bit，在末尾添加00成为80bit

前：

00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 010000

后：

00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000

距离104还差24bit，使用Pad bytes继续填充

236	17
11101100	00010001

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

236 - 17 - 236 - 17 如此循环下去，直到填满为止，对应的十进制为

32,91,11,120,209,114,220,77,67,64,236,17,236

数据纠错编码

数据分组
Reed-Solomon算法，包含多项式、伽罗瓦群论、对数、XOR计算等组合方法生成

根据算法产生的纠错码为

168 72 22 82 217 54 156 0 46 15 180 122 16

合起来为

	Col 1	Col 2	Col 3	Col 4	Col 5	Col 6	Col 7	Col 8	Col 9	Col 10	Col 11	Col 12	Col 13
Block 1	32	91	11	120	209	114	220	77	67	64	236	17	236
Block 2
ECC1	168	72	22	82	217	54	156	0	46	15	180	122	16
ECC2

内容连起来，转换为二进制，类似于

1	01000011111101101011011001000110

尾部添加0

不同的版本在末尾添加0补全

QR Version	Required Remainder Bits
1	0
2	7
3	7
4	7
5	7
6	7
7	0
8	0
9	0
10	0
11	0
12	0
13	0
14	3
15	3
16	3
17	3
18	3
19	3
20	3
21	4
22	4
23	4
24	4
25	4
26	4
27	4
28	3
29	3
30	3
31	3
32	3
33	3
34	3
35	0
36	0
37	0
38	0
39	0
40	0

在这里我们用第一版，不加零

生成矩阵

添加分隔线

添加对齐图案

version 2及其以上需要这个图案，经过查表可以得知，以左上角为原点，可以摆放四个位置，(6, 6), (6, 18), (18, 6) and (18, 18)，不能遮挡，故右下角合格

INCORRECT

CORRECT

添加Timing Patterns

开始和结束均为黑色

黑色模块和数据保留区

左下角黑点 Dark Module和蓝色区域部分Reserved Areas

版本数据区域

version 7及其以上必须包含版本信息，两个蓝色区域

添加文本数据

如果遇到了阻挡，绕过去

如果遇到了垂直的Timing Pattern,跳过去到下一列

Data Masking

为什么需要masking，因为要减少复杂度，提升机器的识别率

什么是masking

黑白切换

Mask方法

只mask数据区域

Mask种类

Mask Number	If the formula below is true for a given row/column coordinate, switch the bit at that coordinate

0	(row + column) mod 2 == 0
1	(row) mod 2 == 0
2	(column) mod 3 == 0
3	(row + column) mod 3 == 0
4	( floor(row / 2) + floor(column / 3) ) mod 2 == 0
5	((row * column) mod 2) + ((row * column) mod 3) == 0
6	( ((row * column) mod 2) + ((row * column) mod 3) ) mod 2 == 0
7	( ((row + column) mod 2) + ((row * column) mod 3) ) mod 2 == 0

寻找最佳Mask

每一种mask加上去后进行四种惩罚算法验证，得分最低者为最合适的mask

The first rule gives the QR code a penalty for each group of five or more same-colored modules in a row (or column).
The second rule gives the QR code a penalty for each 2x2 area of same-colored modules in the matrix.
The third rule gives the QR code a large penalty if there are patterns that look similar to the finder patterns.
The fourth rule gives the QR code a penalty if more than half of the modules are dark or light, with a larger penalty for a larger difference.

这里举第一种惩罚算法为例

350得分最低，选择第一种mask

添加格式信息

纠错级别有四个 L M Q H，Maks有八种，一共32种组合

格式信息是一个15-bit长的字符串

前5个bit包含纠错版本（2-bit）和mask版本（3-bit）

Error Correction Level	Bits	Integer Equivalent
L	01	1
M	00	0
Q	11	3
H	10	2

Mask Number	If the formula below is true for a given row/column coordinate, switch the bit at that coordinate

0	(row + column) mod 2 == 0
1	(row) mod 2 == 0
2	(column) mod 3 == 0
3	(row + column) mod 3 == 0
4	( floor(row / 2) + floor(column / 3) ) mod 2 == 0
5	((row * column) mod 2) + ((row * column) mod 3) == 0
6	( ((row * column) mod 2) + ((row * column) mod 3) ) mod 2 == 0
7	( ((row + column) mod 2) + ((row * column) mod 3) ) mod 2 == 0