文章来源：https://blog.csdn.net/a22222259/article/details/98173091
二维码原理详解
Oct 10, 2020 1:24:15 AM
是一种编码方式，它比传统的 Bar Code 条形码能存更多的信息，也能表示更多的数据类型：比如：字符，数字，日文，中文等等。近几年随着我国移动支付等等发展迅猛,变得非常流行,但这个东西好像是日本人发明的...
从字面上看就是用两个维度（水平方向和垂直方向）来进行数据的编码，条形码只利用了一个维度（水平方向）表示信息，在另一个维度(垂直方向)没有意义，所以二维码比条形码有着更高的数据存储容量。
从形成方式上，二维码可以分为两类:堆叠式二维码：在一维条形码的基础上，将多个条形码堆积在一起进行编码，常见的编码标准有PDF417等。这个是美国人发明的,不常用.矩阵式二维码：在一个矩阵空间中通过黑色和白色的方块进行信息的表示，黑色的方块表示1，白色的方块表示0，相应的组合表示了一系列的信息，常见的编码标准有QR 码,在我国非常常用。
由于学习需要，所以看了一些相关知识,觉得这个玩意就是一个密码算法。
二、基本概念
首先，我们先说一下二维码一共有 40 个尺寸。官方叫版本 Version。Version 1 是 21 x 21 的矩阵，Version 2 是 25 x 25 的矩阵，Version 3 是 29 的尺寸，每增加一个 version，就会增加 4 的尺寸，公式是：(V-1)*4 + 21（V是版本号） 最高 Version 40，(40-1)*4+21 = 177，所以最高是 177 x 177 的正方形。
三、二维码组成及对应功能
A：功能图形区：起到定位的作用
a：定位图形
由两条黑白相间的直线组成，便于确定二维码的角度，纠正扭曲。
b：校正图形
仅在版本2以上存在，由三个黑白相间的小正方形嵌套组成，便于确定中心，纠正扭曲。
c：位置探测图形
由三个黑白相间的大正方形嵌套组成，分别位于二维码左上角、右上角、左下角，目的是为了确定二维码的大小和位置。
B：数据编码区:记录了具体的数据信息，纠错信息与版本信息。
d：数据码和纠错码
数据码(Data Code ):存储要存放的数据信息
纠错码(Error Correction Code ):纠错码的存在使得当二维码的数据出现允许范围内的错误时，也可以正确解码。这就是为什么二维码有残缺还能扫出来，也就是为什么有人在二维码的中心位置加入图标。二维码存在4个级别的纠错等级，每个纠错级别可修正的错误与标识见图4，纠错级别越高，可以修正的错误就越多，需要的纠错码的数量也变多，相应的可储存的数据就会减少，版本1的二维码在L级别下可储存25个字符，在H级别下只能储存10个字符。
e：版本信息
仅在版本7以上存在，记录具体的版本信息。
f：格式信息
记录使用的掩码和纠错等级。
g：数据编码
不在详述,见编码规则
C:此外二维码的外围还留有一圈空白区:主要是为了便于识别而存在。
四、编码规则
数据编码的方式有很多，如Numeric mode数字编码。Byte mode，字节编码。Alphanumeric mode 字符编码。Kanji mode 这是日文编码，也是双字节编码。Extended Channel Interpretation (ECI) mode 主要用于特殊的字符集。并不是所有的扫描器都支持这种编码。Structured Append mode 用于混合编码，也就是说，这个二维码中包含了多种编码格式。FNC1 mode 等。
每一个编码方式都有其独有的id进行标识，这些标识会记录在数据区的前端，使得解码器可以根据二维码使用的编码方式对数据进行解码。
1.字符编码示例
Alphanumeric mode 字符编码。包括 0-9，大写的A到Z（没有小写），以及符号$ % * + – . / : 包括空格。这些字符会映射成一个字符索引表。如图6所示：（其中的 SP 是空格，Char 是字符，Value 是其索引值） 编码的过程是把字符两两分组，然后转成下表的 45 进制，然后转成 11bits 的二进制，如果最后有一个落单的，那就转成 6bits 的二进制。而编码模式和字符的个数需要根据不同的 Version 尺寸编成9, 11 或 13 个二进制（如图7）
先简单举个例子让大家觉得很简单明了：
| A | B | C | D | E | F |
| 10 | 11 | 12 | 13 | 14 | 15 |
那么字符串AB=10*45+11。
为什么以长度为二的字符串举例,因为字符编码是两两分组
接下来进入正题：
在 Version 1 的尺寸下，纠错级别为H的情况下，编码: AC-42
第一步:先两两分组:(AC)(-4)(2),然后把每一组转成 11bits 的二进制：
(AC)=10*45+12 等于 462 转成 00111001110
(41,4)=41*45+4 等于 1849 转成 11100111001
(2) 转成 000010 落单就是6bits
第二步:把这些二进制连接起来：00111001110 11100111001 000010,把字符的个数转成二进制 (Version 1-H 为 9 bits ): 5 个字符，5 转成 000000101(9bits图7)
最后,在头上加上编码标识 0010(如图5) 和第 5二步的个数编码: 0010 000000101 00111001110 11100111001 000010
2.数字编码示例
Numeric mode 数字编码，从 0 到9。如果需要编码的数字的个数不是 3 的倍数，那么，最后剩下的 1 或 2 位数会被转成 4 或 7bits，则其它的每 3 位数字会被编成 10，12，14bits，编成多长还要看二维码的尺寸（图7说明了这点）
在 Version 1 的尺寸下，纠错级别为H的情况下，编码： 01234567(和前面的字符编码差不多)
1. 把上述数字分成三组: 012 345 67
2. 把他们转成二进制: 012 转成 0000001100； 345 转成 0101011001； 67 转成 1000011。
3. 把这三个二进制串起来: 0000001100 0101011001 1000011
4. 把数字的个数转成二进制 (version 1-H 是 10 bits ): 8 个数字的二进制是 0000001000
5. 把数字编码的标志 0001 和第 4 步的编码加到前面: 0001 0000001000 0000001100 0101011001 1000011
五、结束符和补齐码
1.结束符
假如我们有个HELLO WORLD的字符串要编码，根据上面的示例二，我们可以得到下面的编码：
| 编码 | 字符数 | 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 2.补齐码
最后，如果如果还没有达到我们最大的bits数的限制，我们还要加一些补齐码（Padding Bytes），Padding Bytes就是重复下面的两个bytes：11101100 00010001 （这两个二进制转成十进制是236和17，我也不知道为什么，只知道Spec上是这么写的）关于每一个Version的每一种纠错级别的最大Bits限制，可以参看QR Code Spec的第28页到32页的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，我们还要对这些数据码加上纠错信息。
六、纠错码
见图四及其上面简述(思路有点混乱,排版出了点问题)
那么，QR是怎么对数据码加上纠错码的？首先，我们需要对数据码进行分组，也就是分成不同的Block，然后对各个Block进行纠错编码，对于如何分组，我们可以查看QR Code Spec的第33页到44页的Table-13到Table-22的定义表。注意最后两列
| Number of Error Code Correction Blocks | 需要分多少个块 |
| Error Correction Code Per Blocks | 每一个块中的code个数，所谓的code的个数，也就是有多少个8bits的字节 |
举个例子：上述的Version 5 + Q纠错级：需要4个Blocks（2个Blocks为一组，共两组），头一组的两个Blocks中各15个bits数据 (k)+ 各 9个bits的纠错码(r)（注：表中的codewords就是一个8bits的byte）（再注：最后一例中的（c, k, r ）的公式为：c = k + 2 * r，因为后脚注解释了：纠错码的容量小于纠错码的一半）
下图给一个5-Q的示例（因为二进制写起来会让表格太大，所以，我都用了十进制，我们可以看到每一块的纠错码有18个codewords，也就是18个8bits的二进制数）
注意不要错误以为是上面的编码数据，上面的是Version 1的Q纠错级，而这个是Version 5 + Q纠错级,只是举个例子
注：二维码的纠错码主要是通过Reed-Solomon error correction（里德-所罗门纠错算法）来实现的。由于这个算法相当的复杂,所以...
七、最终编码
放置规则：穿插放置
如果你以为我们可以开始画图，你就错了。二维码的混乱技术还没有玩完，它还要把数据码和纠错码的各个codewords交替放在一起。如何交替呢，规则如下：
对于数据码：把每个块的第一个codewords先拿出来按顺度排列好，然后再取第一块的第二个，如此类推。如：上述示例中的Data Codewords如下：
| 块1 | 67 | 85 | 70 | 134 | 87 | 38 | 85 | 194 | 119 | 50 | 6 | 18 | 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 | 151 | 50 | 7 |
| 块4 | 70 | 247 | 118 | 86 | 194 | 6 | 151 | 50 | 16 | 236 | 17 | 236 | 17 | 236 | 17 | 236 |
我们先取第一列的：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
对于纠错码，也是一样：
| 块1 | 233 | 199 | 11 | 45 | 115 | 247 | 241 | 223 | 229 | 248 | 154 | 117 | 154 | 111 | 86 | 161 | 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 | 242 | 238 | 76 | 195 | 230 | 189 | 10 | 108 | 240 | 192 | 141 |
| 块4 | 235 | 159 | 5 | 173 | 24 | 147 | 59 | 33 | 106 | 40 | 255 | 172 | 82 | 2 | 131 | 32 | 178 | 236 |
和数据码取的一样，得到：213，87，148，235，199，204，116，159，…… …… 39，133，141，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
这就是我们的数据区。
最后再加上Reminder Bits，对于某些Version的QR，上面的还不够长度，还要加上Remainder Bits，比如：上述的5Q版的二维码，还要加上7个bits，Remainder Bits加零就好了。关于哪些Version需要多少个Remainder bit，可以参看QR Code Spec的第15页的Table-1的定义表。
八、画出二维码图
1.Position Detection Pattern
首先，先把Position Detection图案画在三个角上。（无论Version如何，这个图案的尺寸就是这么大）
2.Alignment Pattern
然后，再把Alignment图案画上（无论Version如何，这个图案的尺寸就是这么大）
关于Alignment的位置，可以查看QR Code Spec的第81页的Table-E.1的定义表（下表是不完全表格）
下图是根据上述表格中的Version8的一个例子（6，24，42）
3.Timing Pattern
4.Format Information(下图中的蓝色部分)
Format Information是一个15个bits的信息：
这15个bits中包括：
- 5个数据bits：其中，2个bits用于表示使用什么样的Error Correction Level， 3个bits表示使用什么样的Mask
- 10个纠错bits。主要通过BCH Code来计算
然后15个bits还要与101010000010010做XOR(异或)操作。这样就保证不会因为我们选用了00的纠错级别和000的Mask，从而造成全部为白色，这会增加我们的扫描器的图像识别的困难。
5.Version Information(版本7以后需要这个编码,下图中的蓝色部分)
Version Information一共是18个bits，其中包括6个bits的版本号以及12个bits的纠错码
6.数据和数据纠错码
然后是填接我们的最终编码，最终编码的填充方式如下：从左下角开始沿着红线填我们的各个bits，1是黑色，0是白色。如果遇到了上面的非数据区，则绕开或跳过。
7.掩码图案
这样下来，我们的图就填好了，但是，也许那些点并不均衡，如果出现大面积的空白或黑块，会告诉我们扫描识别的困难。所以，我们还要做Masking操作（掩膜操作）QR的Spec中说了，QR有8个Mask你可以使用，如下所示：其中，各个mask的公式在各个图下面。所谓mask，说白了，就是和上面生成的图做XOR操作。Mask只会和数据区进行XOR，不会影响功能区。
其Mask的标识码如下所示：（其中的i,j分别对应于上图的x,y）
下面是Mask后的一些样子，我们可以看到被某些Mask XOR了的数据变得比较零散了。
Mask过后的二维码就成最终的图了。
九、总而言之
二维码的原理可以简单总结为：
将我们想要存储的信息，通过不同的编码格式转换为二进制字符串,字符在变成0和1组成的序列之后,再进行一系列优化算法,就得到了最终的二进制编码.1对应黑色小方块,0对应白色小方块,然后将这些小方块八个一组填进大方块里.就变成了大家看到的二维码了.(说法过于简单,不要深究.当然里面除了要存储的信息还有类似上面所述的定位图案,功能性数据,纠错码,掩码等)
版权所属：NIMA二维码
原文地址：https://nima.vip/article/principle.html
转载时必须以链接形式注明原始出处及本声明。
本文标签：