聊聊二维码生成原理

guozhiwei · 发表于 2023-9-17 09:38:10

　　假期在家做了一个二维码生成器，不过现在还不完善。在这里记录一下二维码的生成原理。草料二维码生成器https://www.erweicaihong.cn/二维彩虹提供专业的二维码在线生成和美化。在线生成器可把文本、电子邮件、名片、网址、微信收款等信息一键制作自定义动态二维码图片，不仅能够随时让用户更改二维码背后的信息而无需更改二维码，而且能够让用户追踪最有价值的市场数据！

　　二维码一共有四十个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。

　　二维码共有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。

　　如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 100001112

　　如 CZH

　　先根据下表查到CZH对应(12, 35, 17)两个为一组分开 (12, 35), (17)将有两个数字的组的第一个数字乘45，然后加上第二个数字，最后转为11-bit的二进制数;将余下的一个数字转为6-bit的二进制数 (如12 * 45 + 35 -> 575 -> 01000111111, 17 -> 010001)计算Character Count Indicator，000000011Mode Indicator 0010最后按照1.1的顺序连接得到0010 000000011 01000111111 010001基本操作同上，查JIS 8表在我的生成器中，直接将std::string的每个char转为8位二进制数这部分我也不太明白，下面是一些普遍的教程对于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。

　　在数据后添加0000如果数据已满足最大容量，可省略或缩写如果数据不是8的倍数需要添加0凑齐如果数据仍不满足最大容量，依次在数据后添加11101100和00010001关于最大容量有一张表，但太大了，你可以在qr_code.pdf的第28页8.4.9找到

　　这部分对我来说十分难理解，里面牵扯了一些我不知道的数学知识。不过我还是照着大部分教程做出了一个简单生成器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

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

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

　　c=每块的codewords总数，即33，34k=每块的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

　　对于某些Version，还需添加一定量的Remainder Bits，填0即可这个也有一张表，在qr_code.pdf的15页

　　在二维码的左下角、左上角、右上角添加三个Position Detection Patterns,如下图

　　在Finder Pattern和编码区之间留一段空白，如下图

　　在第六行和第六列的Position Detection Patterns之间

　　Version 2及以上存在Alignment Patterns，如Version 8其中心方块的坐标如下，全表在qr_code.pdf的82页。

　　则其坐标为(6,6)(6,24)(6,42)(24,24)(24,6)(24,42)(42,42)(42,6)(42,24)，去掉其中与Position Detection Patterns冲突的块得(6,24)(24,24)(24,6)(24,42)(42,42)(42,24),如下图

　　以上述坐标为中心，画一个如下图的3×3的块

　　从二维码的右下角开始，沿下图顺序填充，跳过Function Patterns, Function Pattern包括

　　Finder PatternSeparatorsTiming PatternsAlignment PatternsFormat InfomationVersion Infomation（Version 7及以上）

　　关于Format Infomation和Version Infomation下文会说明其位置

　　Version 3

　　为避免出现不利于识别的图案，我们还需要对二维码进行Mask处理，Mask一共有8种。

　　以二维码的左上角为(0,0), i代表横坐标，j代表纵坐标，遍历二维码遇到符合条件的(i,j)将该坐标的颜色反转，如下表注意，Mask 不应用于 Function Pattern(见前文)最后一个110应是111

　　实际上，这部分算法并没有多么重要，选择一个不是最佳的Mask也可以识别。具体评估规则如下:

　　1.对于每一行和列，如果出现连续(i + 5)个颜色相同的模块, 分数加(i + 3)，如下图第一行分数为10

　　2.寻找m×n(m,n>=2)个颜色相同的区域，每个区域加3×（m-1）×（n-1）分，如下图一个2×2区域加3分

　　3.对于每一行和列，出现黑:白:黑:白:黑=1:1:3:1:1，加40分，如下图

　　4. 对于整个二维码，计算黑色块与总数的比率，找到两个与该比率相近的5%的倍数，记作k%。计算r=|k- 50|/5,取较小的r,乘10即为加分。

　　如比率为46，则k=45或k=50，r=0或r=1, 取0*10=0，即为加0分。

　　5.对每一种Mask评分，取分值最小的Mask

　　每个Version都有Format Information，但仅Version 7及以上有Version Information

　　如 Error Correction Level M，Mask Pattern 5，

　　1. Error Correction Level

　　查表得00

　　2.Mask Pattern ,由6.1表1得101

　　3.连接起来，求BCH码，得0011011100

　　这部分我也不太懂，可以看下面的文章

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

　　也可以看qrcode/qr.c at master · rsky/qrcode · GitHub

　　4.连接上述数据和BCH码，与101010000010010异或得100000011001110，避免全为0

　　Dark Module 应始终为黑

　　如 Version 7

　　1.将Version number转为6位二进制数，得000111

　　2.求其BCH码，得110010010100

　　3.连接上述数据和BCH码，得000111110010010100

　　当然，Version Information也可查表,可以看qrcode/qr_private.h at master · rsky/qrcode · GitHub

　　这就是二维码的制作原理，十分繁琐，在实现上会遇到更多困难。在这里提供一些相关资料：

　　库（第二个是我做的,header only）：

　　GitHub - rsky/qrcode: C library and its language bindings to make a QR Code.

　　caozhanhao/opqr

　　RS码：

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

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

　　How to create QRcode page3

　　二维码：

　　qr_code.pdf

　　QR码设计（1）之引言 - 简书 (jianshu.com)

　　二维码的生成细节和原理 | 酷壳 - CoolShell

　　How to create QRcode (swetake.com)

　　QR Code Tutorial - Thonky.com

　　转载请注明出处