QR二维码编解码原理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二维码基础,-QR,（,Quick Response,）,码,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,位一组：,012 345 678 901 234 5,2),将每组转换为二进制：,0120000001100,3450101011001,6781010100110,9011110000101,2340011101010,50101,3),将二进制数连接为一个序列：,0000001100 0101011001 1010100110 1110000101 0011101010 0101,4),将字符计数指示符转换为二进制（查表知版本,1-H,为,10,位）：,字符数为：,160000010000,5),加入模式指示符,0001,（查表）以及字符计数指示符的二进制数据：,0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 0101,6,）数字模式中位流的长度计算公式：,B=4+C+10,（,D DIV 3,）,+R=4+10+50+4=68,2,.,数据编码,：,采用既定规则，数据字符转换为位流，加必要符号，后将位流转换为码字,编码,例：对数字,0123456789012345,（,16,个数字字符）进行编码，生成,QR,码。,7,）添加终止符：,查表可知版本,1-H,的数据位数应为,72,，故需添加终止符序列,0000,，,此时数据位流为,72,位，满足版本要求。,8,）填充位和填充码字：,本例中，数据位流长度为,72,位，满足数据容量要求，无需添加填充位和填充码字。,9,）位流到码字的转换：,所得的数据位流将被分为一个个码字，所有的码字长度都是,8,位。,综上，所得到的数据码字序列为：,00010000 01000000 00001100 01010110 01101010 01101110 00010100 11101010 01010000,（共,9,个码字）,3,.,纠错编码,：,生成纠错码字加到数据码字后,编码,例：对数字,0123456789012345,（,16,个数字字符）进行编码，生成,QR,码。,编码码字矩阵,校验矩阵,编码码字多项式：,前,9,位为数据码字 后,17,位为纠错码字,3,.,纠错编码,：,生成纠错码字加到数据码字后,编码,例：对数字,0123456789012345,（,16,个数字字符）进行编码，生成,QR,码。,定义：在任何,q,阶伽罗华域,GF,（,q,）中都能找到一个,，能用它的幂次表示,q-1,个非零元素。,QR,码的纠错码生成是通过,GF,（,2,8,）,来进行的，,GF,（,2,8,）,中的元素组成一个循环群：,（,1,，,1,，,，,254,),，,其中,255,=,0,=1,，则称,是,GF,（,2,8,）,的本原域元素。,0,254,可用,0000 0001 1111 1111,来表示,同时，,为,P,（,X,）,=0,的根。其中，,P,（,X,）是以,GF,（,2,8,）,上,8,次首一既约多项式，以,P(X),为模的多项式剩余类环构成,2,8,阶伽罗华域。,本例中，本原多项式为,P(X)=X,8,+X,4,+X,3,+X,2,+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)=d,0+,d,1,x+d,2,x,2,+d,8,x,8,（有,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,块码字区。,将码字，寻像图形，分隔符，校正图形按规则排列，放入二维码中即可,掩模图形参考,条件,000,(,i+j,)mod 2=0,001,i,mod 2=0,010,j,mod 3=0,011,(,i+j,)mod 3=0,100,(,i,div 2)+(,j,div 3)mod 2=0,101,(,i j,)mod 2+(,i j,)mod 3=0,110,(,i j,)mod 2+(,i j,)mod 3)mod 2=0,111,(,i j,)mod 3+(,i+j,)mod 2)mod 2=0,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,。,纠错等级,二进制指示符,L,01,M,00,Q,11,H,10,解码,1.,计算伴随多项式的值。,2.,求错误位置多项式。,3.,求错误位置多项式的根。,4.,求错误值并对码字进行错误纠正。,图像处理方法,解码：,QR,码的解码流程,解码,编码后的表达式为：,=C,25,X,25,+C,24,X,24,+C,1,X,1,+C,0,=q(x)g(x),C,（,X,）,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,1.,计算伴随多项式的值,=e,a1,a1,+e,a2,a2,+e,a3,a3,+e,a4,a4,=e,a1,+e,a2,+e,a3,+e,a4,=e,a1,（,7,）,a1,+e,a2,（,7,）,a2,+e,a3,（,7,）,a3,+e,a4,（,7,）,a4,若,S,i,0(i=0,1,2,3,4,5,6,7),则接受到的码字无错误。,若,S,i,0(i=0,1,2,3,4,5,6,7),，则接收到的码字有误，需先,找出错误码字位置,，再,算出错误值,，最后,进行纠错,，得到正确码字。,解码,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,令,ai,为错位码字的位置（,ai=0-25,）。,找到错误码字位置,ai,即可算出错误码字,e,ai,。,故需先求出,1,2,3,4,。,得到多项式,(z),。,将,-ai,依次带入,(z),，使,(z)=0,的项即为所求。,2.,找出错误码字位置,是一个相对于,的值，不是一个绝对值。有,4,个错误和有,5,个错误的 值是不一样的。,解码,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,同理可得：,2.,找出错误码字位置,解码,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,2.,找出错误码字位置,根据上式，确定错误位置矩阵为：,将,-ai,依次带入,(z),，使,(z)=0,的项即为所求（只要是错误的,-ai,带入后，结果都为,0,）。,ai,即为错误码字位置，接下来用错误码字位置找到错误值进行纠错。（注：若,ai,的个数多余,4,个，则无法进行纠错。）,解此矩阵，即可求出,1,2,3,4,。,(z),即可求出：,解码,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,3.,找出错误值,上式中,a1,a2,a3,a4,已知，求得错误值,e,a1,e,a2,e,a3,e,a4,即可进行纠错。,解码,例：,以版本,1-M,为例，,GF,（,2,8,）上有码字,26,个，其中纠错码字,10,个，可纠正,4,个码字。,4.,纠错,将,4,个错误值与其错误位置对应的码字值进行异或运算，得到纠错后的码字值，完成错误纠正。,假设：,从二维条码符号图像中还原出的一个错误码字值,r,i,=1101 0001,计算得出的错误值是,e,i,=0000 0110,用 ，,c,i,即为正确的数据码字值。,谢谢大家,!,