QR二维码编解码原理PPT课件

二维码基础-QR（QuickResponse）码,.,QR码的编码QR码的解码,纲要,.,数据信息及数据信息的纠错码,包含版本信息，只有版本740的符号有版本信息，其余版本全为0,每个QR码符号由名义上的正方形模块构成，组成一个正方形阵列，它由编码区域和包括寻象图形、分隔符、定位图形和校正图形在内的功能图形组成。功能图形不能用于数据编码。符号的四周由空白区包围。下图为QR码版本7符号的结构图。,迅速地识别可能的QR码符号，明确地确定视场中符号的位置和方向,作用是确定符号的密度和版本，提供决定模块坐标的基准位置。,补正QR码的歪斜。,包含符号所使用的纠错等级和掩模图形信息。,编码,编码：QR码符号的结构,.,1.数据分析,2.数据编码,3.纠错编码,4.构造最终信息,5.在矩阵中布置模块,6.掩模,7.格式和版本信息,确定要进行编码的字符类型，选择所需的版本信息和纠错等级。,采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字。,生成纠错码字加到数据码字后。,按规则将每一块中置入数据和纠错码字，必要时加剩余位。,将寻像图形、分隔符、矫正图形与码字，按规则排列，放入二维码矩阵。,用八种掩模图形依次对符号的编码区域的位图进行掩模处理，评价所得到的8种结果，选择最优的一种。,生成版本信息（如果需要）和格式信息，构成符号。,编码,编码：QR码的编码流程,.,1.数据分析：确定要进行编码的字符类型，选择所需的版本信息和纠错等级,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,1.扩充解释（ECI）模式，数字模式，字母数字模式，8位字节模式，中国汉字模式，日本汉字模式，混合模式，结构链接模式，FNCI模式,2.,.,2.数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,分为3位一组：01234567890123452)将每组转换为二进制：01200000011003450101011001678101010011090111100001012340011101010501013)将二进制数连接为一个序列：0000001100010101100110101001101110000101001110101001014)将字符计数指示符转换为二进制（查表知版本1-H为10位）：字符数为：1600000100005)加入模式指示符0001（查表）以及字符计数指示符的二进制数据：000100000100000000001100010101100110101001101110000101001110101001016）数字模式中位流的长度计算公式：B=4+C+10（DDIV3）+R=4+10+50+4=68,.,2.数据编码：采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,7）添加终止符：查表可知版本1-H的数据位数应为72，故需添加终止符序列0000，此时数据位流为72位，满足版本要求。8）填充位和填充码字：本例中，数据位流长度为72位，满足数据容量要求，无需添加填充位和填充码字。9）位流到码字的转换：所得的数据位流将被分为一个个码字，所有的码字长度都是8位。综上，所得到的数据码字序列为：000100000100000000001100010101100110101001101110000101001110101001010000（共9个码字）,.,3.纠错编码：生成纠错码字加到数据码字后,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,编码码字矩阵,校验矩阵,编码码字多项式：,前9位为数据码字后17位为纠错码字,.,3.纠错编码：生成纠错码字加到数据码字后,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,定义：在任何q阶伽罗华域GF（q）中都能找到一个，能用它的幂次表示q-1个非零元素。QR码的纠错码生成是通过GF（28）来进行的，GF（28）中的元素组成一个循环群：（1，1，254)，其中255=0=1，则称是GF（28）的本原域元素。0254可用0000000111111111来表示同时，为P（X）=0的根。其中，P（X）是以GF（28）上8次首一既约多项式，以P(X)为模的多项式剩余类环构成28阶伽罗华域。本例中，本原多项式为P(X)=X8+X4+X3+X2+1。用i模P（）可以得到域元素和二进制比特串的对照表（如图）。,.,3.纠错编码：生成纠错码字加到数据码字后,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,.,3.纠错编码：生成纠错码字加到数据码字后,编码,例：对数字0123456789012345（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，生成多项式如图所示。,.,（i=0,1,2,，16）,3.纠错编码：生成纠错码字加到数据码字后,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,数据码字的多项式形式为：d(x)=d0+d1x+d2x2+d8x8（有9个数据码字）生成多项式为：g(x)=,编码后的表达式为：,纠错码字多项式,其中，纠错码字是数据码字被纠错码多项式g(x)除得的余数。纠错码多项式求出后，将系数i按对照表转换为位流，加到数据位流后面，即可求出整个编码数据位流。,C（X）,C(i)=0,=g(x)q(x),（数据码字多项式）,（纠错码字多项式）,.,4.构造最终信息：按规则将每一块中置入数据和纠错码字，必要时加剩余位,编码,例：对数字0123456789012345（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块，不需要分开，故无需构造最终信息。,.,5.在矩阵中布置模块：将寻像图形、分隔符、校正图形与码字，按规则排列，放入二维码矩阵,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,图形表示：00010000,排列规则,数据码字9个，纠错码字17个，共26个码字，就是26块码字区。将码字，寻像图形，分隔符，校正图形按规则排列，放入二维码中即可,.,6.掩模：依次对符号的编码区域的位图进行掩模处理，评价所得结果，选择最优一种。,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,为了QR码阅读的可靠性，最好均衡地安排深色与浅色模块。应尽可能避免位置探测图形的位图1011101出现在符号的其他区域。为了满足上述条件，应按以下步骤进行掩模。1)掩模不用于功能图形2)用多个矩阵图形连续地对已知的编码区域的模块图形（格式信息和版本信息除外）进行XOR操作。XOR操作将模块图形依次放在每个掩模图形上，并将对应于掩模图形的深色模块的模块取反（浅色变成深色，或相反）。3)对每个结果图形的不合要求的部分记分，以评估这些结果。4)选择得分最低的图形。,版本1符号的所有的掩模图形，用掩模图形参考000到111的掩模结果。,.,7.格式和版本信息：生成版本信息（如果需要）和格式信息，构成符号,编码,例：对数字0123456789012345（16个数字字符）进行编码，生成QR码。,格式信息为15位，其中有5个数据位，10个是用BCH（15，5）编码计算得到的纠错位。其中，数据位的第1,2位是符号的纠错等级，第3到第5位是掩模图形参考。格式信息掩模是与101010000010010进行XOR异或运算。本例中纠错等级为H，查表知，二进制指示符为10。掩模图形参考根据上页结果确定。,版本信息为18位，其中，6位数据位，12位通过BCH（18,6）编码计算出的纠错位。只有版本7到版本40的符号包含版本信息，没有任何版本信息的结果全为0。,.,解码,1.计算伴随多项式的值。2.求错误位置多项式。3.求错误位置多项式的根。4.求错误值并对码字进行错误纠正。,图像处理方法,解码：QR码的解码流程,.,解码,编码后的表达式为：,=C25X25+C24X24+C1X1+C0=q(x)g(x),C（X）,例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。,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)，则接收到的码字有误，需先找出错误码字位置，再算出错误值，最后进行纠错，得到正确码字。,.,解码,例：以版本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个错误的值是不一样的。,.,解码,例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。,同理可得：,2.找出错误码字位置,.,解码,例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个，可纠正4个码字。,2.找出错误码字位置,根据上式，确定错误位置矩阵为：,将-ai依次带入(z)，使(z)=0的项即为所求（只要是错误的-ai带入后，结果都为0）。ai即为错误码字位置，接下来用错误码字位置找到错误值进行纠错。（注：若ai的个数多余4个，则无法进行纠错。）,解此矩阵，即可求出1,2,3,4。(z)即可求出：,.,解码,例：以版本1-M为例，GF（28）上有码字26个，其中纠错码字10个