1、二维码基础二维码基础-QR（Quick Response）码2I.QR码的编码码的编码II.QR码的解码码的解码 纲 要要3数据信息及数据信息的数据信息及数据信息的纠错码包含版本信息，只有版本包含版本信息，只有版本740的符号有版本信息，的符号有版本信息，其余版本全其余版本全为0每个QR码符号由名义上的正方形模块构成，组成一个正方形阵列，它由编码区域和包括寻象图形、分隔符、定位图形和校正图形在内的功能图形组成。功能图形不能用于数据编码。符号的四周由空白区包围。下图为QR码版本7符号的结构图。迅速地迅速地识别可能的可能的QR码符号，明确地确定符号，明确地确定视场中符号的位置和方向中符号的位置和方
2、向作用是确定符号的密度和作用是确定符号的密度和版本，提供决定模版本，提供决定模块坐坐标的基准位置。的基准位置。补正正QR码的歪斜。的歪斜。包含符号所使用的包含符号所使用的纠错等等级和掩模和掩模图形信息。形信息。编码编码：QR码符号的符号的结构构41.数据分析2.数据编码3.纠错编码4.构造最终信息5.在矩阵中布置模块 6.掩模7.格式和版本信息确定要确定要进行行编码的字符的字符类型，型，选择所需的版本信息和所需的版本信息和纠错等等级。采用既定采用既定规则，数据字符，数据字符转换为位流，加必要符号，后将位流位流，加必要符号，后将位流转换为码字。字。生成生成纠错码字加到数据字加到数据码字后。字后。
3、按按规则将每一将每一块中置入数据和中置入数据和纠错码字，必要字，必要时加剩余位。加剩余位。将将寻像像图形、分隔符、形、分隔符、矫正正图形与形与码字，按字，按规则排列，放入二排列，放入二维码矩矩阵。用八种掩模用八种掩模图形依次形依次对符号的符号的编码区域的位区域的位图进行掩模行掩模处理，理，评价所得到价所得到的的8种种结果，果，选择最最优的一种。的一种。生成版本信息（如果需要）和格式信息，构成符号。生成版本信息（如果需要）和格式信息，构成符号。编码编码：QR码的的编码流程流程51.数据分析数据分析：确定要确定要进行行编码的字符的字符类型，型，选择所需的版本信息和所需的版本信息和纠错等等级编码例：
4、例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。1.扩充解释（ECI）模式，数字模式，字母数字模式，8位字节模式，中国汉字模式，日本汉字模式，混合模式，结构链接模式，FNCI模式2.62.数据数据编码：采用既定采用既定规则，数据字符，数据字符转换为位流，加必要符号，后将位流位流，加必要符号，后将位流转换为码字字编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。1)1)分为分为3 3位一组：位一组：012 345 678 901 234 52)2)将每组转换为二进制：将每组转
5、换为二进制：0120000001100 3450101011001 6781010100110 9011110000101 2340011101010 501013)3)将二进制数连接为一个序列：将二进制数连接为一个序列：0000001100 0101011001 1010100110 1110000101 0011101010 01014)4)将字符计数指示符转换为二进制（查表知版本将字符计数指示符转换为二进制（查表知版本1-H1-H为为10 10位）：位）：字符数为：1600000100005)5)加入模式指示符加入模式指示符00010001（查表）以及字符计数指示符的二进制数据：（查表）
6、以及字符计数指示符的二进制数据：0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 01016 6）数字模式中位流的长度计算公式：）数字模式中位流的长度计算公式：B=4+C+10（D DIV 3）+R=4+10+50+4=6872.数据数据编码：采用既定采用既定规则，数据字符，数据字符转换为位流，加必要符号，后将位流位流，加必要符号，后将位流转换为码字字编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。7）添加）添加终止符：止符：查表可知版本
7、1-H的数据位数应为72，故需添加终止符序列0000，此时数据位流为72位，满足版本要求。8）填充位和填充）填充位和填充码字：字：本例中，数据位流长度为72位，满足数据容量要求，无需添加填充位和填充码字。9）位流到）位流到码字的字的转换：所得的数据位流将被分为一个个码字，所有的码字长度都是8位。综上，所得到的数据上，所得到的数据码字序列字序列为：00010000 01000000 00001100 01010110 01101010 01101110 00010100 11101010 01010000（共9个码字）83.纠错编码：生成生成纠错码字加到数据字加到数据码字后字后编码例：例：对数字
8、数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。编码码字矩阵编码码字矩阵校验矩阵校验矩阵编码码字多项式：编码码字多项式：前前9位为数据码字位为数据码字后后17位为纠错码字位为纠错码字93.纠错编码：生成生成纠错码字加到数据字加到数据码字后字后编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。定定义：在任何：在任何q阶伽伽罗华域域GF（q）中都能找到一个）中都能找到一个，能用它的，能用它的幂次表示次表示q-1个非零元个非零元素。素。QR码的的纠错码生成是通生成是通过GF（28）来来进行
9、的，行的，GF（28）中的元素中的元素组成一个循成一个循环群：群：（1，1，254)，其中其中255=0=1，则称称是是GF（28）的本原域元素。的本原域元素。0 254 可用可用0000 0001 1111 1111 来表示来表示同同时，为P（X）=0的根。其中，的根。其中，P（X）是以）是以GF（28）上上8次首一既次首一既约多多项式，以式，以P(X)为模的多模的多项式剩余式剩余类环构成构成28阶伽伽罗华域。域。本例中，本原多本例中，本原多项式式为P(X)=X8+X4+X3+X2+1。用用i模模P（）可以得到域元素和二）可以得到域元素和二进制比特串的制比特串的对照表（如照表（如图）。）。1
10、03.纠错编码：生成生成纠错码字加到数据字加到数据码字后字后编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。113.纠错编码：生成生成纠错码字加到数据字加到数据码字后字后编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。(c,k,r):c=码字字总数数k=数据数据码字数字数r=纠错容量容量 纠错容量小于容量小于纠错码字数的字数的一半，以减少一半，以减少错误译码的可能的可能性性生成多生成多项式：式：g(x)=(x-0)(x-1)(x-n-1)=(x-0)(x-1)(x
11、16)其中其中n为生成多生成多项式的次数，式的次数，也就是也就是纠错码字数。本例中，字数。本例中，纠错码字数字数为17，生成多，生成多项式式如如图所示。所示。12（i=0,1,2,，16）3.纠错编码：生成生成纠错码字加到数据字加到数据码字后字后编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。数据数据码字的多字的多项式形式式形式为：d(x)=d0+d1x+d2x2+d8x8（有9个数据码字）生成多生成多项式式为：g(x)=编码后的表达式后的表达式为：纠错码字多项式其中，其中，纠错码字是数据字是数据码字被字被纠错码多多项式式g(
12、x)除得的余数。除得的余数。纠错码多多项式求出后，将系数式求出后，将系数i按按对照表照表转换为位流，加到数据位流后面，即可求出整个位流，加到数据位流后面，即可求出整个编码数据位流。数据位流。C（X）C(i)=0=g(x)q(x)（数据码字多项式）（纠错码字多项式）134.构造最构造最终信息信息：按按规则将每一将每一块中置入数据和中置入数据和纠错码字，必要字，必要时加剩余位加剩余位编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。按如下步骤构造最终的码字序列（数据码字加上纠错码字，必要时加上剩余码字）。1）根据版本和纠错等级将数据码
13、字序列分为n块。2）对每一块，计算相应块的纠错码字。3）依次将每一块的数据和纠错码字装配成最终的序列：数据块1的码字1；数据块2的码字1；数据块3的码字1；以此类推至数据块n-1的最后的码字；数据块n的最后的码字；随后，纠错块1的码字1，纠错块2的码字1，以此类推至纠错块n-1的最后的码字；纠错块n的最后的码字。查表可知，本例中表可知，本例中1-H版本的数据版本的数据码字序列字序列为1块，不需要分开，故无需构造最，不需要分开，故无需构造最终信息。信息。145.在矩在矩阵中布置模中布置模块：将将寻像像图形、分隔符、校正形、分隔符、校正图形与形与码字，按字，按规则排列，放入二排列，放入二维码矩矩阵
14、编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。图形表示：形表示：00010000排列排列规则数据数据码字字9个，个，纠错码字字17个，共个，共26个个码字，就是字，就是26块码字区。字区。将将码字，字，寻像像图形，分隔符，校正形，分隔符，校正图形按形按规则排列，放入二排列，放入二维码中即可中即可15掩模图形参考条件000(i+j)mod 2=0001i mod 2=0010j mod 3=0011(i+j)mod 3=0100(i div 2)+(j div 3)mod 2=0101(i j)mod 2+(i j)mod 3=
15、0110(i j)mod 2+(i j)mod 3)mod 2=0111(i j)mod 3+(i+j)mod 2)mod 2=06.掩模掩模：依次依次对符号的符号的编码区域的位区域的位图进行掩模行掩模处理，理，评价所得价所得结果，果，选择最最优一种。一种。编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。为了QR码阅读的可靠性，最好均衡地安排深色与浅色模块。应尽可能避免位置探测图形的位图1011101出现在符号的其他区域。为了满足上述条件，应按以下步骤进行掩模。1)掩模不用于功能图形2)用多个矩阵图形连续地对已知的编码区域的模块
16、图形（格式信息和版本信息除外）进行XOR操作。XOR操作将模块图形依次放在每个掩模图形上，并将对应于掩模图形的深色模块的模块取反（浅色变成深色，或相反）。3)对每个结果图形的不合要求的部分记分，以评估这些结果。4)选择得分最低的图形。版本版本1符号的所有的掩模符号的所有的掩模图形，用掩模形，用掩模图形形参考参考000到到111的掩模的掩模结果。果。167.格式和版本信息格式和版本信息：生成版本信息（如果需要）和格式信息，构成符号生成版本信息（如果需要）和格式信息，构成符号编码例：例：对数字数字0123456789012345（16个数字字符）个数字字符）进行行编码，生成，生成QR码。格式信息格
17、式信息为15位，其中有位，其中有5个数据位，个数据位，10个是用个是用BCH（15，5）编码计算得到的算得到的纠错位。其中，数据位的第位。其中，数据位的第1,2位是符号的位是符号的纠错等等级，第，第3到第到第5位是掩模位是掩模图形参考。形参考。格式信息掩模是与格式信息掩模是与101010000010010进行行XOR异或运算。异或运算。本例中本例中纠错等等级为H，查表知，二表知，二进制指示符制指示符为10。掩模。掩模图形参考根据上形参考根据上页结果确定。果确定。版本信息版本信息为18位，其中，位，其中，6位数据位，位数据位，12位通位通过BCH（18,6）编码计算出的算出的纠错位。只有版本位。
18、只有版本7到版本到版本40的符号包含版本信息，没有任何版本信息的的符号包含版本信息，没有任何版本信息的结果全果全为0。纠错等级二进制指示符L01M00Q11H1017解解码1.计算伴随多算伴随多项式的式的值。2.求求错误位置多位置多项式。式。3.求求错误位置多位置多项式的根。式的根。4.求求错误值并并对码字字进行行错误纠正。正。图像像处理方法理方法解解码：QR码的解的解码流程流程18解解码编码后的表达式为：=C25X25+C24X24+C1X1+C0=q(x)g(x)C（X）例：例：以版本以版本1-M为例，例，GF（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正正4个
19、个码字。字。1.计算伴随多算伴随多项式的式的值=ea1a1+ea2a2+ea3a3+ea4a4=ea1+ea2+ea3+ea4=ea1（7）a1+ea2（7）a2+ea3（7）a3+ea4（7）a4 若若Si0(i=0,1,2,3,4,5,6,7),则接受到的接受到的码字无字无错误。若若Si0(i=0,1,2,3,4,5,6,7)，则接收到的接收到的码字有字有误，需先，需先找出找出错误码字位置字位置，再，再算出算出错误值，最后，最后进行行纠错，得到正确，得到正确码字。字。19解解码例：例：以版本以版本1-M为例，例，GF（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正
20、正4个个码字。字。令ai为错位码字的位置（ai=0-25）。找到错误码字位置ai 即可算出错误码字eai。故需先求出1,2,3,4。得到多项式(z)。将-ai依次带入(z)，使(z)=0的项即为所求。2.找出找出错误码字位置字位置是一个相对于是一个相对于的值，不是一个绝对值。有的值，不是一个绝对值。有4个错误和有个错误和有5个错误的个错误的值是不一样的。值是不一样的。20解解码例：例：以版本以版本1-M为例，例，GF（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正正4个个码字。字。同理可得：2.找出找出错误码字位置字位置21解解码例：例：以版本以版本1-M为例，例，G
21、F（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正正4个个码字。字。2.找出找出错误码字位置字位置根据上式，确定根据上式，确定错误位置矩位置矩阵为：将将-ai依次依次带入入(z)，使，使(z)=0的的项即即为所求（只要是所求（只要是错误的的-ai带入后，入后，结果都果都为0）。）。ai即即为错误码字位置，接下来用字位置，接下来用错误码字位置找到字位置找到错误值进行行纠错。（注：若。（注：若ai 的的个数多余个数多余4个，个，则无法无法进行行纠错。）。）解此矩解此矩阵，即可求出，即可求出1,2,3,4。(z)即可求出：即可求出：22解解码例：例：以版本以版本1-M为例，
22、例，GF（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正正4个个码字。字。3.找出找出错误值上式中上式中a1,a2,a3,a4已知，求得已知，求得错误值ea1,ea2,ea3,ea4即可即可进行行纠错。23解解码例：例：以版本以版本1-M为例，例，GF（28）上有）上有码字字26个，其中个，其中纠错码字字10个，可个，可纠正正4个个码字。字。4.纠错将4个错误值与其错误位置对应的码字值进行异或运算，得到纠错后的码字值，完成错误纠正。假假设：从二从二维条条码符号符号图像中像中还原出的一个原出的一个错误码字字值 ri=1101 0001计算得出的算得出的错误值是是 ei=0000 0110用用，ci即即为正正确的数据确的数据码字字值。24谢谢大家谢谢大家!
