QR二维码编解码原理

QR码的编码

QR码的解码

纲要第一页，共23页。第一页，共23页。数据信息及数据信息的纠错码包含版本信息，只有版本7~40的符号有版本信息，其余版本全为0每个QR码符号由名义上的正方形模块构成，组成一个正方形阵列，它由编码区域和包括寻象图形、分隔符、定位图形和校正图形在内的功能图形组成。功能图形不能用于数据编码。符号的四周由空白区包围。下图为QR码版本7符号的结构图。迅速地识别可能的QR码符号，明确地确定视场中符号的位置和方向作用是确定符号的密度和版本，提供决定模块坐标的基准位置。补正QR码的歪斜。包含符号所使用的纠错等级和掩模图形信息。编码编码：QR码符号的结构第二页，共23页。第二页，共23页。1.数据分析2.数据编码3.纠错编码4.构造最终信息5.在矩阵中布置模块6.掩模7.格式和版本信息确定要进行编码的字符类型，选择所需的版本信息和纠错等级。采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字。生成纠错码字加到数据码字后。按规则将每一块中置入数据和纠错码字，必要时加剩余位。将寻像图形、分隔符、矫正图形与码字，按规则排列，放入二维码矩阵。用八种掩模图形依次对符号的编码区域的位图进行掩模处理，评价所得到的8种结果，选择最优的一种。生成版本信息（如果需要）和格式信息，构成符号。编码编码：QR码的编码流程第三页，共23页。第三页，共23页。1.数据分析：确定要进行编码的字符类型，选择所需的版本信息和纠错等级编码例：对数字12345（16个数字字符）进行编码，生成QR码。1.扩充解释（ECI）模式，数字模式，字母数字模式，8位字节模式，中国汉字模式，日本汉字模式，混合模式，结构链接模式，FNCI模式2.第四页，共23页。第四页，共23页。2.数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字编码例：对数字12345（16个数字字符）进行编码，生成QR码。分为3位一组：01234567890123452)将每组转换为二进制：012→0000001100 345→0101011001 678→1010100110 901→1110000101 234→0011101010 5→01013)将二进制数连接为一个序列：00000011000101011101110000101001110101001014)将字符计数指示符转换为二进制（查表知版本1-H为10位）：字符数为：16→00000100005)加入模式指示符0001（查表）以及字符计数指示符的二进制数据：000101011101110000101001110101001016）数字模式中位流的长度计算公式：B=4+C+10（DDIV3）+R=4+10+50+4=68第五页，共23页。第五页，共23页。2.数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字编码例：对数字12345（16个数字字符）进行编码，生成QR码。7）添加终止符：查表可知版本1-H的数据位数应为72，故需添加终止符序列0000，此时数据位流为72位，满足版本要求。8）填充位和填充码字：本例中，数据位流长度为72位，满足数据容量要求，无需添加填充位和填充码字。9）位流到码字的转换：所得的数据位流将被分为一个个码字，所有的码字长度都是8位。综上，所得到的数据码字序列为：0001010110011010001010011101（共9个码字）第六页，共23页。第六页，共23页。3.纠错编码：生成纠错码字加到数据码字后编码例：对数字12345（16个数字字符）进行编码，生成QR码。编码码字矩阵校验矩阵编码码字多项式：前9位为数据码字后17位为纠错码字第七页，共23页。第七页，共23页。3.纠错编码：生成纠错码字加到数据码字后编码例：对数字12345（16个数字字符）进行编码，生成QR码。定义：在任何q阶伽罗华域GF（q）中都能找到一个α，能用它的幂次表示q-1个非零元素。

QR码的纠错码生成是通过GF（28）来进行的，GF（28）中的元素组成一个循环群：（1，α1

，……，α254)，

其中α255=α0=1，则称α是GF（28）的本原域元素。α0α254可用0000000111111111来表示同时，α为P（X）=0的根。其中，P（X）是以GF（28）上8次首一既约多项式，以P(X)为模的多项式剩余类环构成28阶伽罗华域。本例中，本原多项式为P(X)=X8+X4+X3+X2+1。用αi模P（α）可以得到域元素和二进制比特串的对照表（如图）。第八页，共23页。第八页，共23页。3.纠错编码：生成纠错码字加到数据码字后编码例：对数字12345（16个数字字符）进行编码，生成QR码。第九页，共23页。第九页，共23页。3.纠错编码：生成纠错码字加到数据码字后编码例：对数字12345（16个数字字符）进行编码，生成QR码。(c,k,r):c=码字总数

k=数据码字数

r=纠错容量†纠错容量小于纠错码字数的一半，以减少错误译码的可能性生成多项式：g(x)=(x-α0)(x-α1)……(x-αn-1)=(x-α0)(x-α1)……(x-α16)其中n为生成多项式的次数，也就是纠错码字数。本例中，纠错码字数为17，生成多项式如图所示。第十页，共23页。第十页，共23页。（i=0,1,2,…，16）3.纠错编码：生成纠错码字加到数据码字后编码例：对数字12345（16个数字字符）进行编码，生成QR码。数据码字的多项式形式为：d(x)=d0+d1x+d2x2+……+d8x8（有9个数据码字）

生成多项式为：g(x)=编码后的表达式为：纠错码字多项式其中，纠错码字是数据码字被纠错码多项式g(x)除得的余数。纠错码多项式求出后，将系数αi按对照表转换为位流，加到数据位流后面，即可求出整个编码数据位流。C（X）C(αi)=0=g(x)q(x)（数据码字多项式）（纠错码字多项式）第十一页，共23页。第十一页，共23页。4.构造最终信息：按规则将每一块中置入数据和纠错码字，必要时加剩余位编码例：对数字12345（16个数字字符）进行编码，生成QR码。按如下步骤构造最终的码字序列（数据码字加上纠错码字，必要时加上剩余码字）。1）根据版本和纠错等级将数据码字序列分为n块。2）对每一块，计算相应块的纠错码字。3）依次将每一块的数据和纠错码字装配成最终的序列：数据块1的码字1；数据块2的码字1；数据块3的码字1；以此类推至数据块n-1的最后的码字；数据块n的最后的码字；随后，纠错块1的码字1，纠错块2的码字1，…以此类推至纠错块n-1的最后的码字；纠错块n的最后的码字。查表可知，本例中1-H版本的数据码字序列为1块，不需要分开，故无需构造最终信息。第十二页，共23页。第十二页，共23页。5.在矩阵中布置模块：将寻像图形、分隔符、校正图形与码字，按规则排列，放入二维码矩阵编码例：对数字12345（16个数字字符）进行编码，生成QR码。图形表示：排列规则数据码字9个，纠错码字17个，共26个码字，就是26块码字区。将码字，寻像图形，分隔符，校正图形按规则排列，放入二维码中即可第十三页，共23页。第十三页，共23页。掩模图形参考条件000(i+j)mod2=0001imod2=0010jmod3=0011(i+j)mod3=0100((idiv2)+(jdiv3))mod2=0101(ij)mod2+(ij)mod3=0110((ij)mod2+(ij)mod3)mod2=0111((ij)mod3+(i+j)mod2)mod2=06.掩模：依次对符号的编码区域的位图进行掩模处理，评价所得结果，选择最优一种。编码例：对数字12345（16个数字字符）进行编码，生成QR码。

为了QR码阅读的可靠性，最好均衡地安排深色与浅色模块。应尽可能避免位置探测图形的位图出现在符号的其他区域。为了满足上述条件，应按以下步骤进行掩模。1)掩模不用于功能图形2)用多个矩阵图形连续地对已知的编码区域的模块图形（格式信息和版本信息除外）进行XOR操作。XOR操作将模块图形依次放在每个掩模图形上，并将对应于掩模图形的深色模块的模块取反（浅色变成深色，或相反）。3)对每个结果图形的不合要求的部分记分，以评估这些结果。4)选择得分最低的图形。版本1符号的所有的掩模图形，用掩模图形参考000到111的掩模结果。第十四页，共23页。第十四页，共23页。7.格式和版本信息：生成版本信息（如果需要）和格式信息，构成符号编码例：对数字12345（16个数字字符）进行编码，生成QR码。格式信息为15位，其中有5个数据位，10个是用BCH（15，5）编码计算得到的纠错位。其中，数据位的第1,2位是符号的纠错等级，第3到第5位是掩模图形参考。

格式信息掩模是与1010进行XOR异或运算。本例中纠错等级为H，查表知，二进制指示符为10。掩模图形参考根据上页结果确定。版本信息为18位，其中，6位数据位，12位通过BCH（18,6）编码计算出的纠错位。只有版本7到版本40的符号包含版本信息，没有任何版本信息的结果全为0。纠错等级二进制指示符L01M00Q11H10第十五页，共23页。第十五页，共23页。解码1.计算伴随多项式的值。2.求错误位置多项式。3.求错误位置多项式的根。4.求错误值并对码字进行错误纠正。图像处理方法解码：QR码的解码流程第十六页，共23页。第十六页，共23页。解码编码后的表达式为：

=C25X25+C24X24+……+C1X1+C0=q(x)g(x)C（X）例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。1.计算伴随多项式的值=ea1αa1+ea2αa2+ea3αa3+ea4αa4

=ea1+ea2+ea3+ea4=ea1（α7）a1

+ea2（α7）a2+ea3（α7）a3+ea4（α7）a4

若Si＝0(i=0,1,2,3,4,5,6,7),则接受到的码字无错误。若Si≠0(i=0,1,2,3,4,5,6,7)，则接收到的码字有误，需先找出错误码字位置，再算出错误值，最后进行纠错，得到正确码字。第十七页，共23页。第十七页，共23页。解码例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。令①αai为错位码字的位置（ai=0-25）。②找到错误码字位置αai

即可算出错误码字eai。

故需先求出σ1,σ2,σ3,σ4。得到多项式σ(z)。③将α-ai依次带入σ(z)，使σ(z)=0的项即为所求。2.找出错误码字位置是一个相对于α的值，不是一个绝对值。有4个错误和有5个错误的值是不一样的。第十八页，共23页。第十八页，共23页。解码例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。同理可得：2.找出错误码字位置第十九页，共23页。第十九页，共23页。解码例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。2.找出错误码字位置根据上式，确定错误位置矩阵为：将α-ai依次带入σ(z)，使σ(z)