二维码生成原理

假期在家做了一个二维码生成器，不过现在还不完善。在这里记录一下二维码的生成原理。

1、概览

二维码一共有四十个Version，其实就是尺寸、可容纳的数据不同。如Version 1是21×21，Version 2是25×25。

每一个二维码都有左下，左上，右上，三个Position Detection Patterns，统称为Finder pattern，用来定位
在左下和右上有两个重复的Format Information。
在二维码的四周还有Timing Patterns, 可以用来确定Version和校准。
在Version 2及以上还存在Alignment Patterns。在Version 7及以上还有Version Infomation。

2、数据编码

二维码共有8种Mode

Numeric Mode，数字
Alphanumeric Mode，大写英文字母(A-Z)、数字和9个符号。注意这个模式不包括小写字母
8-bit Byte Mode， JIS X 0201，这个模式可以编码中文
Kanji Mode 双字节编码，中文和日文
Mixing modes 混合
Structured Append Mode 混合
FNC1 Mode 一些工业使用
Extended Channel Interpretation (ECI) Mode 特殊字符集
本文只介绍前四种模式。下面的示例都是Version 1-H。

2.1.1 Numeric Mode

如01234567

先将其以三个为一组分开 012 345 67
将每一组的数字转化成二进制，其中有三位数字的组转为10 bits,两位7 bits,一位4 bits
如012 ->0000001100 345 -> 0101011001 67 -> 1000011
再将上述数字连接得到0000001100 0101011001 1000011
将数字的个数转化为一定bits的二进制，其中Version 1-H为10 bits,详见下表1
上一步的数据叫做Character Count Indicator，在本例中8 -> 0000001000
还有Mode Indicator, 本例为0001，详见下表2
最后我们以Mode Indicator - Character Count Indicator - Data为顺序连接上述数据，得到0001 0000001000 0000001100 0101011001 1000011

2.1.2 Alphanumeric Mode

如 CZH

先根据下表查到CZH对应(12, 35, 17)
两个为一组分开 (12, 35), (17)
将有两个数字的组的第一个数字乘45，然后加上第二个数字，最后转为11-bit的二进制数;将余下的一个数字转为6-bit的二进制数 (如12 * 45 + 35 -> 575 -> 01000111111, 17 -> 010001)
计算Character Count Indicator，000000011
Mode Indicator 0010
最后按照1.1的顺序连接得到0010 000000011 01000111111 010001

2.1.3 8-bit Byte Mode

基本操作同上，查JIS 8表
在我的生成器中，直接将std::string的每个char转为8位二进制数

2.1.4 Kanji Mode

这部分我也不太明白，下面是一些普遍的教程
对于JIS值在8140(HEX)t到9FFC(HEX)的字符,将高位减去8140(HEX)
对于JIS值在E040(HEX)t到EBBF(HEX)的字符,将高位减去C140(HEX)
将高位与C0(HEX)相乘，然后与低位相加
上一步得到的结果转化为13-bit的二进制数
其他操作同上
关于中文汉字可参考下面的文章

QR码编码原理三（日本汉字和中文编码）_dekko的博客-CSDN博客_qr码中文

实际上，大部分时候可以使用 8-bit Byte Mode代替其他Kanji Mode，但它需要3或4个字节存储kanji，而kanji仅需要2个字节，所以如果想要更大的容量还是需要Kanji Mode。

2.2.1 结束符

在数据后添加0000
如果数据已满足最大容量，可省略或缩写

2.2.2 8bit重组

如果数据不是8的倍数需要添加0凑齐

2.2.3 补齐符

如果数据仍不满足最大容量，依次在数据后添加11101100和00010001
关于最大容量有一张表，但太大了，你可以在qr_code.pdf的第28页8.4.9找到

3、纠错码生成

这部分对我来说十分难理解，里面牵扯了一些我不知道的数学知识。不过我还是照着大部分教程做出了一个简单生成器generate_ECBlock()，参考qrComputeECWord()。

纠错一共有四个等级L,M,Q,H，每个等级纠错能力不同，如下表

下面是基本流程,其中以十进制数代替二进制。

查下表得Version 1-H下共需要1个Error Correction block，全表在qr_code.pdf的35页
有些Version，可能需要两组Error Correction block，每组的codewords也不同，具体看表
对于每一个Block计算出相应的纠错码
如在Version 1-H下，数据{32 ,65 ,205 ,69 ,41 ,220 ,46 ,128 ,236}计算后，应得到{42,159,74, 221, 244 ,169, 239 ,150, 138, 70, 237, 85, 224, 96, 74, 219, 61}

其具体计算过程目前我也解释不清，可以看看下面几篇文章

有人能解释一下伽罗瓦域和GF(2^8)吗？

[译] 为程序员写的Reed-Solomon码解释

How to create QRcode page3

4、数据分配

4.1 排列

以Version 5-H为例,查qr_code.pdf的35页得如下

观察最右侧的(c,k,r)

c = 每块的codewords总数，即33，34
k = 每块的Data codewords数,即11，12
则每块的Error Correction共有c-k个，即22。所以共有211+212共46个codewords的数据,4*22共88个的纠错码

我们将每一个块的数据和纠错码排成一个表，如下

最后从第一列开始一列一列地排列，最终得到D1, D12, D23, D35, D2, D13, D24, D36, ... D11, D22, D33, D45, D34, D46, E1, E23, E45, E67, E2, E24, E46, E68, ... E22, E44, E66, E88