QR 二维码布局（五）

上一篇构建最终编码流程中，我们获取到最终包含数据码、纠错码和剩余字符的最终编码数据。接下来就是要最终的数据编码和其它必需的功能模块统一分配到 QR 二维码矩阵中。功能模块指的是不含数据，同时 QR 二维码规范中必需的元素，例如 QR 二维码三个角上的定位模块。本篇将介绍如何分配功能模块和数据编码位。

术语：Pixel 和 Module

本篇中，我们用 Module（姑且译为码元吧）而不是像素 Pixel 来指代 QR 二维码黑色或白色最小的单元区域。屏幕上的像素其实和二维码中黑白序的码元不是一回事。例如，版本 1 的 QR 二维码总是 21 x 21 码元，即使它会占据屏幕上 42 x 42 像素，或者 105 x 105 像素等。

功能模块概览

QR 二维码一定会包含功能模块。这些功能模块会被分配在 QR 二维码中特定位置以确保读码器可以正确识别它们以准备解码。下图展示了功能模块及其位置：

• 定位模块（ Finder Patterns）位于二维码的左上、左下和右上三个角；
• 隔离模块（Separators）紧靠定位模块的边；
• 校准模块（Alignment Pattern）类似于定位模块，但是更小些，分布于整个二维码区域中，它们只会出现在版本 2 及更高的版本中，位置取决于版本。
• 时间模块（Timing Patterns）是连接定位模块黑白相间的点线；
• 黑点码元（Dark Module）是一个始终位于左下角定位模块右上方的独立黑色码元。

接下来我们详细介绍如何分配不同功能模块。

第一步：添加定位模块

首先，将定位模块置于矩阵中。定位模块包含一个最外层的 7x7 码元的黑色正方外边，紧接着内部一个 5x5 码元的白色正方轮廓，最里层一个 3x3 码元的黑色正方区域。

定位模块本身设计完全不同于二维码中其它模式。该模块由外到内再到外有 1:1:3:1:1 的比例分布，QR 读码器会寻找这种比例的黑白码元来检测定位模块，并正确地适应 QR 二维码以准备解码。

无论哪种二维码版本，定位模块总会置于左上、左下和右上角。

如图显示了版本 1 和版本 18 QR 二维码中的定位模块，它们大小相同都是 7*7 码元，位置随着版本尺寸变化而坐标不同但还是位于相应角落。

由于 QR 二维码尺寸可以根据版本号来通过 (((V-1)*4)+21) 计算，相应地，定位模块的坐标也可以计算得出：

• 左上角定位模块的左上顶点坐标（0，0）
• 左下角定位模块的左上顶点坐标（0，[(((V-1)*4)+21) - 7]）
• 右上角定位模块的左上顶点坐标（[(((V-1)*4)+21) - 7]，0）

第二步：添加隔离模块

之前提到，隔离模块紧贴定位模块的边界，如图中包裹定位模块的白色区域：

第三步：添加校准模块

版本 2 及之后版本都会需要校准模块。一个校准模块如下图所示，包含一个 5x5 的黑色外轮廓，其内一个 3x3 的白色框，最内一个黑色码元。

校准模块位置被定义在校准模块位置表中。表中数字同时指代行列坐标（坐标从 0 开始计）

校准模块位置表：
https://www.thonky.com/qr-code-tutorial/alignment-pattern-locations

例如上方局部图中，版本 2 对应的坐标是 6 和 18，那么校准模块中心点应该位于 （6，6）（6，18）（18，6）和（18，18）位置。但是由于校准模块是在分配完定位模块和隔离模块之后进行分配，所以它不可以覆盖定位模块区域。最终只有不位于定位模块区域的校准模块才会添加到二维码内。

上图左边标红的三处校准模块错误，最终应为右边所示。

为了描述校准模块位置，下午展示了版本 8 QR 二维码中校准模块的坐标位置。所有 6，24 和 42 的组合坐标都会被用来分配校准模块（除了定位模块区域）。

第四步：添加时间模块

时间模块就是一条水平、一条垂直的黑白相间的线。水平方向的时间模块位于坐标第六行（从 0 开始算）连接上方两个定位模块的隔离模块；垂直方向的时间模块位于第六列（从 0 开始算）连接左侧两个定位模块的隔离模块。时间模块两端都是黑色码元。校准模块有可能会覆盖时间模块，因为它们的黑白间隔模式是统一的并不影响。下图展示了不同版本 QR 二维码的时间模块。

第五步：添加黑点码元和预留区域

接下来应该向二维码矩阵中添加数据编码了，但在那之前，一定要先添加黑色码元，同时还有矩阵中的用以记录该二维码格式和版本的保留区域。

黑色码元

之前提过，所有的 QR 二维码都有黑色码元，位于左下角定位模块的右上角。再具体些，黑色码元的位置位于坐标 ([(4 * V) + 9], 8) 其中 V 是 QR 二维码的版本号。

预留格式信息的区域

紧邻隔离模块一串码元需要被预留以存储二维码格式信息：

• 在左上角定位模块，隔离模块外围的水平和竖直方向的闲置码元
• 在右上角定位模块，下方隔离模块下边水平方向一串码元
• 在左下角定位模块，右侧隔离模块右边竖直方向一串码元

下图中蓝色区域即预留区域，无论什么版本，它们总是紧邻隔离模块：

预留版本信息的区域

QR 二维码版本 7 及之后的版本一定会含有两个储存版本信息的区域。每个区域都是 6x3 码元，其中一个位于左下角定位模块上方，另一个位于右上角定位模块左侧，下图蓝色区域标明其位置：

第六步：安置数据编码信息

接下来我们要将最初得到的编码数据填充到 QR 二维码的矩阵中，它是按照一定模式来排布的。

排布模式

编码数据会从二维码右下顶点开始，左右相邻的两码元宽度为开始向上按顺序填充数据。白色码元代表 0， 黑色码元代表 1。当该列向上抵达顶部，向左平移两码元位置，继续向下。当进行到二维码底部，继续向左移动两码元，重复向上，以此类推。如果期间遇到预留区域，不对该处码元进行填充，一直到下一个闲置码元才继续进行填充。

下图展示了放置数据编码的顺序。注意当数据填充到最左侧竖直方向的时间模块时，向下的宽度为 2 码元的这一列是紧贴时间模块的，并不占用时间模块的位置。

向上模式

下图展示了当 2 码元宽度向上填充时，数据编码的填充顺序，总是先右后左，保持向上方向：

向下模式

当宽度为 2 码元的数据向下填充时，也是先右后左，保持向下方向：

跳过功能模块

当填充数据编码遇到功能模块时，跳过已经被功能模块占用的码元，向下一处闲置码元填充信息。

总之，按列不断行进填充编码数据，跳过功能模块和保留区域占用的码元。唯一要注意的是之前提到的左侧时间模块。

例外：竖直时间模块

填充数据编码时，以上规则都是通用的，唯独左侧时间模块不同，当填充区域抵达竖直方向时间模块时，时间模块这一列不算在向下方向的填充区域内，紧贴时间模块左侧的 2 码元宽度的这一列是填充区域的位置。

如图所示，当时间模块右侧这一列填充完毕时，跳过时间模块这一列，左边另起一个 2 码元宽的新一列进行向下填充：

再进行简单归纳下，整个数据编码信息的填充路线如下图所示：

由右下角开始沿着红线行进填充，遇到已经被占用的码元，绕过或跳过。

预留格式信息区域

格式信息是对该二维码中的纠错级别和选用的掩码模式进行编码后的字符串。因为总共有 L，M，Q 和 H 四种纠错级别，以及 0 - 7 八种掩码模式，所以总共有 32 种可能的格式信息。所有的 32 种格式信息字符串可以在下列链接中找到：

格式版本信息表
https://www.thonky.com/qr-code-tutorial/format-version-tables

接下来我们来看下格式信息字符串如何生成。

格式信息字符串总共 15 位长度，首先 5 位用来编码纠错级别和用到的掩码模式。然后使用这 5 位来生成一个 10 位的纠错码。最终的 15 位二进制串会和 101010000010010 进行 XOR 运算得到的结果即 格式信息二维码。

纠错级别码

注意数字顺序是 1，0，3，2

掩码模式码

根据掩码模式 0 到 7 的编号，将其转化为 3 位的二进制位。

例如纠错级别 L，掩码模式 4，得到 5 位码 01100

生成 10 位纠错码

采用 Reed-Solomon 纠错算法，但该过程会更容易些，因为其多项式没有超过 15 项，而且系数只有 1 和 0。

生成纠错码的过程中，QR 二维码规范指出生成多项式采用下列多项式：

我们也可以将其转化为二进制串 10100110111。

接下来用 01100 来除以 生成多项式。首先在其后加 10 个 0 组成 15 位二进制串 01100 00000 00000，移走左侧的 0 得到 1100 00000 00000。

接下来进行除法，步骤如下：

1. 在生成多项式后补全 0 位使其长度相等。
2. 补齐长度后的生成多项式二进制串与得到的二进制串进行 XOR 运算
3. 移走结果左侧的 0

我们必须一直对多项式进行除法直到生成的结果格式为 10 位或小于 10 位长度。因此，在除法步骤之前，先确保目前生成的二进制串长度要大于等于 11 位（11 位是生成多项式二进制位的长度）。目前我们的是 1100 00000 00000 总共 14 位。

第一次除法，在生成多项式后补齐 3 个 0 得到 10100110111000，XOR 运算完得到 01100110111000，移走左侧 0 得到 1100110111000 共 13 位。

对上方结果进行第二次除法，对生成多项式二进制后补齐 2 个 0 得到 13 位的 1010011011100，继续 XOR 运算。

一直到第四次除法运算后生成 1000111101 共 10 位的结果。如果结果是跳过 10 位直接小于 10 位，我们在其左侧补 0 补至 10 位长度。该 10 位结果即所求的 10 位纠错码。

与掩码串进行 XOR 运算

15 位目标串位 01100 1000111101，与 QR 二维码规范中指定的 101010000010010 进行 XOR 运算得到 110011000101111。此即最终要求的格式信息码。

将格式信息码按顺序填充到 QR 二维码矩阵的预留格式信息区域中：

0 到 14 即 15 位格式信息码从左到右的编码对应的位置编号。在 QR 版本 1 二维码中，110011000101111 格式信息码填充如下：

预留版本信息区域

在 QR 二维码版本 7 及之后版本，在左下角或右上角都有 18 位的预留版本信息区域。不同版本下其位置如下：

18 位版本信息中，首 6 位是版本号转化为 6 位二进制结果，剩余 12 位是 6 位版本号对应的 12 位纠错码。生成过程与格式信息中的纠错码过程类似，不过对应的是 12 位并且最终无需与掩码 XOR 运算。

当然也可以直接在格式版本信息表中直接查得版本对应的 18 位版本信息码：

格式版本信息表
https://www.thonky.com/qr-code-tutorial/format-version-tables

我们继续讲下其具体生成过程：

首先以版本 7 为例，将 7 转化为 6 位二进制：000111

接下来生成多项式二进制采用的是规范中指出的 1111100100101 共 13 位。

首先我们把版本号补至 18 位并移走左侧 0 得到 111 000000 000000 共 15 位，再将生成多项式后补 2 位得到 15 位后进行 XOR 运算，结果为 110010010100 恰好为 12 位，即我们所求的 12 位纠错码。

将版本号与纠错码结合到一起得到 18 位版本信息码：

000111110010010100

填充版本信息码

将 18 位信息码及其每位坐标对应如下表：

左下角的预留版本信息区域为横向矩形，其填充顺序对应信息码位置如下表：

右上角的预留版本信息区域为纵向矩形，其填充顺序对应信息码位置如下表：

最终填充结果如图：

输出最终二维码结果

再添加完格式版本信息后，选择最合适的掩码模式进行掩码操作，即可得到最终的二维码结果了。

注意，QR 二维码规范中指出 QR 二维码外围要有一个隔离区域，该区域要求是 4 码元宽度的白色区域。

回到我们 "HELLO WORLD" 的例子，我们采用 1-Q 版本，字符编码模式，得到结果如下：

本文翻译自
https://www.thonky.com/qr-code-tutorial/introduction

中文参考文章：《二维码的生成细节和原理》
http://blog.sae.sina.com.cn/archives/1139