二维条码QR CODE译码的研究与实现.doc

北京机械工业学院 硕士学位论文 维条码QRDE译码的研究与实现 姓名：王琳 申请学位级别：硕士 专业：计算机应用技术 指导教师：佟俐鹃20071201n摘要条码技术是以计算机技术、光电传感技术和通信技术为基础而发展起来的 一项自动识别技术。现在已经成为信息数据自动输入、识别的重要方法和手段。 现代高新技术的发展，迫切要求条码在有限的几何空间内表示更多的信息，从 而满足千变万化的应用需求。二维条码正是为了解决一维条码无法解决的问题 而产生的.在国外，QR码技术已经广泛应用于各个部门，而在我国的应用才刚 刚起步的。因此，QR码的研究对在我国推广二维条码的使用具有深远的意义。QR码的数据译码是译码过程中关键的一步，只有通过数据译码这一过程才 能最终把条码符号转换为我们可以识别的数据形式。本文详细介绍了不同数据 模式下的QR码编码的理论和规则，根据QR码的编码理论和编码规则推导出对 应数据模式译码的设计思路和具体实现方法，同时阐述了译码器的设计原理。 通过该译码器可以将QR码符号转化为数字、字母数字、8位字节、以及中国汉 字等数据模式。本课题中的程序是在PC机上的Vc+6. 0环境下调试运行成功的，具有良好 的可移植性，经过已经实现的编码系统对译码系统进行测试，该译码器能够有 效，正确的对QR码进行译码，具有实际应用价值。关键词：QR码；二维条码编码；译码方法；二维条码译码AbstractABSTRACTBarcode technology is an automatic identification technology based on the development of computer technology, photoelectric sending technology and communications technology. Now, this technology is become a important method and means in the automatic input and recognition of the information data. The development of high-tech needs barcode could show more information in limited space, so 2-D barcode produced. In foreign countries, QR Code technology has already been applied in many fields, but in China, this technology is just in research phase. Therefore, the research on QR Code has far-reaching meaning.Data decoding is the most pivotal part in the whole process of decoding, through data decoding we can transform the barcode to the data which we can recognition. This text introduces the encoding theory and method under several kinds data mode, deduces decoding method and implementation along with the theory of encoder. The decoder can decode QR code to number, alphanumeric, octet and Chinese characters.The program of this text run well under VcrH-6.0,is well transplantable. The test on encoder with output of decoder provide the decoder can efficiently, accurately decode QR Code，has actual application value.Key words： QR Code； 2-D barcode encode； decode method； 2-D barcode encode学位论文版权使用授权书本人完全了解北京机械工业学院关于收集、保存、使用学位论 文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷 本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用 影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目 录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按 有关规定向国家有关部门或者机构送交论文的复印件和电子版；在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。学位论文作者签名：M年 月曰经指导教师同意，本学位论文属于保密，在 年解密后适用 本授权书。指导教师签名：学位论文作者签名-年月日年月曰硕士学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中己经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均己在文中以明确方式标明本学位论文原创性声明的 法律责任由本人承担。签名：I M年 V月对日第1章条码简介第1章条码简介1.1条码技术条码技术是在计算机技术与信息技术基础发展上发展起来的一门容编码、 印刷、识别、数据采集和处理于一体的新兴技术。我们通常看到的印刷在商品 包装上的条码是一维条码，它是由一组规则排列的条，空及其对应字符组成， 表示一定信息的标识2。自20世纪70年代初问世以来，条码由于其快速、准 确、成本低、可靠性高等优点很快得到广泛应用。仅仅20多年的时间，一维条 码在商场、金融、海关、生产、邮政等社会的各个领域已经得到了广泛的应用， 大大提高了资料收集与资料处理的速度，但是由于受到信息容量的限制，一维 条码仅仅能标识商品，而不能够描述商品，因此相当依赖于电脑网络和后台数 据库。在网络资源受到限制或者不便于建立后台数据库的应用环境，一维条码 很难派上用场。另一方面，要用一维条码表示汉字和图像等信息几乎是不大可 能的，即使可以表示，也显得十分不便且效率很低随着现代高新技术的发 展，迫切要求条码技术做到在有限的几何空间内表示更多的信息，从而满足千 变万化的信息要求，二维条码正是为了解决一维条码无法解决的问题而诞生的， 它具有高密度、大容量、纠错能力强等特点，拓宽了条码的应用领域。由于大多数的二维条码是矩阵式的二维条码，对于一维条码的识别和译码 的方法不能应用在对二维条码的识别和译码的过程中。并且根据详细的市场调 查，绝大多数的二维条码是由国外进行研制的，虽然很多的二维条码已经成为 国际的或者国内的标准，但是对各种二维条码识别和译码的关键技术仍然掌握 在国外公司，这样条码的编码设备及译码设备的制造就长期被国外公司所垄断 w。尽管国内也有少数几家公司或者研究机构也研发类似的二维条码的识读设 备，但是识读设备的诸如识读率、识读速度等性能尚与国外的同类产品有很大 的差距，真正可用的成熟技术和产品至今没有研究成功，使得我国大部分技术 及设备目前仍需要从国外引进，导致实际应用起来成本较高。而在我国，二维条 码的推广应用工作得到了国家有关部门的大力支持和社会各界的极大关注6。 目前，已经在汽车自动化生产线，军队仓储，武警车辆管理，珠宝玉石饰品管行汇票及医疗急救服务卡上得到了应用，99年全国人大第九届三次全体会议期 间，成功的将二维条码应用于对人员证件、记者证、旁听证的管理。我国香港 特别行政区已经将二维条码应用在特别行政区的护照上。二维条码技术在我国 的推广应用己经展露出诱人的前景。因此，随着二维条码的应用越来越广泛， 二维条码编解码技术的研究有着深远的意义。1.1.1条码的概述条码是一种可印制的机器语言，它采用二进制的概念，以“0”和“1”表 示编码的特定组合单元，以规则排列的图形符号来表示数据.早期的条码只在一 个方向上携带信息，称为一维条码。然而，一维条码仅仅只是一种商品的标识， 它不含有对商品的任何描述，人们只有通过后台的数据库，提取相应的信息才 能明白这个商品标识的具体含义。在没有数据库或联网不便的地方，这一商品 标识变得毫无意义。此外，一维条码无法表示汉字和图像信息，在有些应用汉 字和图像的场合，显得十分不便。同时，即使我们建立了数据库来存储产品信 息，而这些大量的信息需要一个很长的条码标识。如应用储运单元条码，应用 EAN/UPC128条码，都需要占有很大的印刷面积。现代高新技术的发展，迫切 要求条码在有限的几何空间内表示更多的信息,从而满足千变万化的应用需求 二维条码正是为了解决一维条码无法解决的问题而诞生的为在有限的几何空 间内印刷大量的信息，可用两种方法：一是在一维条码的基础上向二维条码方 向发展；二是利用图像识别原理，采用新的几何图像和结构设计出二维条码码 制。目前，根据二维条码实现原理、结构形状的差异，可分为堆积式或层叠式 二维条码(Stacked Bar Code)和棋盘式或矩阵式二维条码(Dot Matrix Bar Code) 两大类型。1.1. 2条码的特点条码技术是电子与信息科学领域的髙新技术，所涉及的技术领域较多，是 多项技术相结合的产物。在自动识别技术中，条码技术具有如下特点：1、简单条码符号制作容易，扫描操作简单易行。2、可靠性高键盘录入数据，误码率为三百分之一，利用光学字符识别技术，误码率约 为万分之一，而采用条码扫描录入方式，误码率仅有百万分之一。人工输入方 法的可靠性受人为因素影响很大，特别对于信息位长的字符串，是很容易出错 的，有资料可查，键盘输入平均每300个字符出现一个错误。字符识别技术， 由于字符图形的不规则性和复杂性，以及易受噪声干扰等影响，识别率有限， 而且实施成本高。语音识别技术人为的因素较大。因此，这些识别技术在可靠 性上很难与条码匹敌。3、成本低廉条码自动识别系统所涉及到的识别符号成本以及设备成本都非常低。特别 是条码符号，即使是一次性使用，也不会带来多少附加成本，尤其是在大批量 印刷的情况下。这一特点使得条码技术在某些应用领域有着无可比拟的优势， 适用于众多的领域和工作场合。与其它自动识别技术相比较，推广应用条码技 术，所需费用较低。条码标签易于制作而且成本低，对印刷技术设备和材料无 特殊要求。对于量大的条码图形，可以通过印刷大量产生，对于量小的条码图 形，则可以通过计算机自动生成，由打印机输出。条码符号的识读设备普遍采 用光电技术，价格便宜，而且操作设备简单易学，无需专门训练。4、信息采集速度快普通计算机的键盘录入速度是每分钟200字符，而利用条码扫描录入信息 的速度是用键盘录入的20倍。这是因为条码的条空容易识读，用光电扫描装置 识读条码并将信息输入的方法比人工键盘输入的方法要快的多。键盘输入，对 于操作员来说，输入速度慢而且繁琐。使用条码可以大大提高输入速度，实现 “即时数据输入”。字符识别技术、声音识别及视觉识别所涉及到的处理算法复 杂，因此识别速度远远慢于条码识别。5、自由度大识别装置与条码标签相对位置的自由度要比OCR大得多。一维条码通常 只在一维方向上表达信息，而同一条码条高方向上所表示的信息完全相同，这 即使是标签有部分缺欠，仍可以从正常部分输入正确的信息。与磁条信息相比, 条码信息不会受到电磁场的影响和干扰。6、灵活实用条码符号作为一种识别手段可以单独使用，也可以和有关设备组成识别系 统实现自动化识别，还可和其他控制设备联系起来实现整个系统的自动化管理。 同时，在没有自动识别设备时，也可实现手工键盘输入。3第丨章条码简介1.2 二维条码1.2.1 二维条码的产生早期的条码只在一个方向上携带信息，称为一维条码。然而，一维条码仅 仅只是一种商品的标识，它不含有对商品的任何描述，人们只有通过后台的数 据库，提取相应的信息才能明白这个商品标识的具体含义。在没有数据库或联 网不便的地方，这一商品标识变得毫无意义。此外，一维条码无法表示汉字和 图像信息，在有些应用汉字和图像的场合，显得十分不便。同时，即使我们建 立了数据库来存储产品信息，而这些大量的信息需要一个很长的条码标识。如 应用储运单元条码，应用EAN/UPC128条码，都需要占有很大的印刷面积。现 代高新技术的发展，迫切要求条码在有限的几何空间内表示更多的信息，从而 满足千变万化的应用需求。二维条码正是为了解决一维条码无法解决的问题而 诞生的.为在有限的几何空间内印刷大量的信息，可用两种方法：一是在一维条 码的基础上向二维条码方向发展；二是利用图像识别原理，采用新的几何图像 和结构设计出二维条码码制。目前，根据二维条码实现原理、结构形状的差异， 可分为堆积式或层叠式二维条码(Stacked Bar Code)和棋盘式或矩阵式二维条码 (Dot Matrix Bar Code)两大类型。1、堆积式或层叠式二维条码堆积式二维条码的编码原理建立在一维条码基础之上，按需要堆积成二行 或多行。它在编码设计、校验原理、识读方式等方面继承了一维条码的特点， 识读、设备与条码印刷与一维条码技术兼容。但由于行数的增加，行的鉴定、 译码算法与软件不完全相同于一维条码。有代表性的堆积式二维条码有 CODE49, PDF417, CODE 16K 等。2、棋盘式或矩阵式二维条码第1章条码简介矩阵式二维条码是在矩阵相应元素位置上，用点(方点、圆点或其他形状） 的出现表示二进制“1”，点的不出现表示二进制的“0”，点的排列组合确定了 矩阵码所代表的意义。矩阵码是建立在计算机图像处理技术、组合编码原理等 基础上的一种新型图形符号自动识读处理码制。具有代表性的矩阵码如QR Code, CODE ONE, DATA MATRIX 等。 1.2.2 二维条码的特性二维条码的主要特征是二维条码符号在水平和垂直方向均表示数据信息。 二维条码除具备一维条码的优点外，同时还具有信息容量大、可靠性高、可表 示汉字及图像等多种文字信息、保密防伪性强等优点。其主要特征如下：1、高密度目前，应用比较成熟的一维条码如EAN/UPC条码，因密度较低，故仅作 为一种标识数据，不能对产品进行描述。我们要知道产品的有关信息，必须通 过识读条码而进入数据库。这就要求我们必须事先建立以条码所表示的代码为 索引字段的数据库。二维条码通过利用垂直方向的尺寸来提高条码的信息密度。 通常情况下，其密度是一维条码的几十到几百倍。这样，我们就可以把产品信 息全部存储在一个二维条码中。要查看产品信息，只要用识读设备扫描二维条 码即可，因此，不需要事先建立数据库，真正实现了用条码对“物品”的描述。2、具有纠错功能二维条码可以表示数以千计字节的数据。通常情况下，其所表示的信息不 可能与条码符号一同印刷出来。如果没有纠错功能，当二维条码的某部分损坏 时，该密码无法识读而变得毫无意义。二维条码引入的纠错机制，使得二维条 码在因穿孔、污损等引起局部损坏时，照样可以得到正确识读。3、可表示图像及多种文字信息多数一维条码所能表示的字符集不过是10个数字，26个英文字母及一些 特殊字符。条码字符集最大的Codel28条码，所能表示的字符个数也不过是128 个ASCII字符。因此，要用一维条码表示其他语言文字（如汉字、日文等)是不 可能的。大多数二维条码都具有字节表示模式，可将语言文字或图像信息转换 成字节流，然后再将字节流用二维条码表示，从而实现二维条码的图像及多种 语言文字信息的表示。4、可引入加密机制加密机制的引入是二维条码的又一优点。比如：我们用二维条码表示照片 时，我们可以先用一定的加密算法将图像信息加密，然后再用二维条码表示。 在识别二维条码时，再加一定的解密算法，就可以恢复所表示的照片。这样便 可以防止各种证件、卡片等的伪造。7第丨章条码简介寻像图形包括三个相同的位置探测图形，分别位于符号的左上角、右上角、 左下角，如图1.2所示每个位置探测图形可以看作是由3个重叠的同心的正 方形组成，它们分别为7X7个深色模块，5X5个浅色模块，3X3个深色模块。 探测图形的模块宽度比为1: 1： 3： 1： 1： 1。符号中其他地方遇到类似的图形 的可能性很小，因此可以在视窗中迅速的识别可能的QR码符号。识别组成寻 像图形的三个位置探测图形，可以明确的确定视窗中符号的位置和方向。3、分隔符在每个位置探测图形和编码区域之间有一个宽度为1个模块的分隔符。4、定位图形水平和垂直定位图形分别为一个模块宽的一行和一列，由浅色和深色模块 组成。rrr ttI图1.2位置探测图形的结构5、校正图形每个校正图形都可以看作是3个重叠的同心正方形，由5X5个深色模块, 3X3个浅色模块以及位于中心的一个深色模块组成。校正图形的位置视符号的 版本号而定，版本2以上的符号均有校正图形。6、编码区域编码区域包括表示数据码字、纠错码字、版本信息和格式信息的符号字符。7、空白区空白区为环绕在符号周围的四个模块宽的区域，其反色率应与浅色模块相第1章条码简介1.3.2 OR码特点QR码除了具有一维条码及其它二维条码所具有的信息容量大、可靠性高、 可表示汉字及图像等多种信息、保密防伪性强等优点外，还具有如下主要特点：1、超高速识读从QR码的英文名称Quick Response Code可以看出，超高速识读是QR码 区别于四一七条码、Data Matrix等二维码的主要特性。由于在用CCD识读QR 码时，整个QR码符号中信息的读取是通过QR码符号的位置探测图形，用硬 件来实现，因此，信息识读过程所需时间很短，它具有超高速识读特点用CCD 二维条码识读设备，每秒可识读30个含有100个字符的QR码符号；对于含有 相同数据信息的四一七条码符号，每秒仅能识读3个符号；对于DataMatrix矩 阵码，每秒仅能识读23个符号,QR码的超高速识读特性使它能够广泛应用于 工业自动化生产线管理等领域。2、全方位识读QR码具有全方位360度识读的特点，这是QR码优于层叠式二维条码如 四一七条码的另一主要特点，由于四一七条码是将一维条码符号在行排高度上 的截短来实现的，因此，它很难实现全方位识读，其识读方位角仅为土 10度。3、能够有效地表示汉字由于QR码用特定的数据压缩模式表示中国汉字和日本汉字，它仅用13 位可表示一个汉字，而四一七条码、DataMatrix等二维条码没有特定的汉字表 示模式，因此仅用字节表示模式来表示汉字，在用字节模式表示汉字时，需用 16bit(两个字节)表示一个汉字，因此QR Code码比其它的二维条码表示汉字的 效率提高了 20%。1.4 QR Code 二维条码的应用现状1.4.1 QR Code 的应用1第丨章条码简介在国外，二维条码技术己经广泛应用于政府部门(如：档案管理)、公共安 全(如：枪械证、身份证)、交通运输(如：驾驶证)、邮政(如：包裹单)、医疗保 健(如：医疗卡)、工商行政管理(如：代码证、营业执照)、金融业(如：银行的 汇票、支票)、海关(如：海关报关单)等需要信息携带、信息传递、信息防伪的 汇票、支票)、海关(如：海关报关单)等需要信息携带、信息传递、信息防伪的 行业。例如美国在身份证、驾驶证、军人证等证件中，除了将人的姓名、单位、 地址、电话、个人简历等信息进行编码外，还将人体的特征、如指纹、视网膜 扫描以及照片等个人信息存储在可识别的条码中M。二维条码己在美国、加拿 大、新西兰等国家的交通部门的执照年审、车辆违章登记及年检上全面应用。 许多发展中国家如菲律宾、埃及、巴林等国及我国的香港特区、台湾省也在各 种个人证卡中采用二维条码，并迅速推广。下面介绍一下QR Code的应用1、物流业中的应用QR码信息容量大，可以储存包裹、货物的详细信息，并且它容易打印， 可以采用原来的标签打印机打印，同时可以根据需要进行加密，防止数据的非 法篡改。此外，由于QR码具有很强的自动纠错能力，因此在实际的包裹运输 中，即使条码标签受到一定的污损，QR码依然可以正确地识读。QR码这些突 出的特点，使得它被广泛应用在各个国家的邮局、铁路、机场、码头等的包裹 和货物运输上，实现了货物运输的全过程跟踪，消除了数据的重复录入，加快 了货物运输的数据处理速度，降低了对计算机网络的依赖程度，从而实现了物 流管理和信息流管理的完美结合。比如美国陆路运输部、新西兰陆路运输部、 法国邮局、南非航空货运公司、英国、巴西的快运公司等世界各地的物流机构 纷纷采用。2、零售业中的应用QR码应用的另一方面就是在零售业上。比如超市零售，最常见的是各种 商品上的QR码，如同一维条码一样，含有商品的各种信息，包括产地，制造 商，生产日期，保质期，价格等等。通过条码扫描器，可以把这些信息识读出o3、手机QR码的应用QR码是一种摄像头可以扫描识别的二维码，手机或电脑只要装有QR译 码软件，用摄像头扫描QR码即可看到条码里面的信息，提供了让用户在手机 上交换信息以及享受多种在线服务的全新方式。手机扫描QR码技术简单的说是通过手机拍照功能对QR码进行扫描，快 速获取到QR条码中存储的信息，进行上网、发送短信、拨号、资料交换、自 动文字输入等，手机QR码目前已经被各大手机厂商使用开发3】。手机QR码第1章条码简介过手机扫描QR码，或输入QR码下面的号码即可实现快速手机上网功能，并 随时随地下载图文、了解企业产品信息等。现在，手机QR码已经广泛应用在 日本的各个行业，比如票务、餐饮、旅游等等。据日本最大移动运营商NTT DoCoMo2005年12月发布的财年调查，日本对手机条码的总体认识度达到 96.5%,对手机条码的实际使用率是73.3%;而在韩国，目前市面上有660万部 手机支持条码大厂Iconlab的条码业务。1.4.2国内二维条码的硏究和应用近年来，国内在大力进行条码推广应用的同时也积极跟踪国外技术发展， 进行条码理论基础和关键技术的研究。中国物品编码中心条码髙新技术研究立 项进行二维条码研究工作。在二维条码码制设计、编码原理等方面进行了探索， 提出了一种自动识别方位进行校正的结构方案与中心符号相结合的二维码制初 步编码方案。对二维条码图像处理译码解码算法等关键技术进行了研究，并取 得一些初步成果。在QR码方面，国际自动识别制造商协会（AIMI)、美国标 准化协会（ANSI)已经完成了对QR码制的符号标准。条码自动识别技术委员 会已经制定了 QR码的国际标准。我国的物品编码中心在消化国外相关资料的基础上，编著出版了QRCode 二维码种新型的矩阵符号，制定了GBAT18284-2000快速响应矩阵码的国家标准。近年来QR码在我国的应用范围也逐步扩大，手机二维码业务引起人们越 来越多的关注。QR码是目前移动正式推广的二维条码，目前移动推出的五款 支持“中国移动二维码”的手机都是支持的QR码。QR码作为移动官方推荐的条 码标准，早在2004年就纳入中国移动数据部的业务计划，在2005年底制定中 国移动企业标准，在2006纳入中国移动终端预置规划。在上海，手机QR码己 应用到移动订票、电子VIP卡、电子折扣券、企业广告应用等，成为数字时代 的宠儿。在北京，手机条码业务在易初莲花超市、北京地铁站、中关村电脑节 等项目上进行开展，2007年9月的张学友北京演唱会售票过程中应用了手机 QR码。本次演唱会通过短信或彩信将QR Code门票发送到观众手机上，观众 可以在一个专用的识读设备上进行识读，即可完成电子票的“验票”。据悉， QRCode门票方案还将在最近的多场文艺演出中进行尝试使用。而随着北京 2008奥运会的日益迫近，QRCode的应用空间将更为广阔。1.5本课题的内容 1.5.1课题目的根据详细的市场调查，绝大多数的二维条码是由国外进行研制的，虽然很 多的二维条码己经成为国际的或者国内的标准，但是对各种二维条码译码的核 心技术仍然掌握在国外公司，条码的编译码技术长期被国外公司所垄断。尽管 国内也有少数几家公司或者研究机构也研发类似的二维条码的识读设备，但是 识读设备的诸如识读率、识读速度等性能尚与国外的同类产品有很大的差距。 而且由于各个公司并没有将自己的核心技术公开，限制了条码技术的应用和推 广，因此进行QR码的译码研究是很有必要的。近年来随着二维条码的应用越 来越广泛，二维条码译码技术的研究有着深远的意义。1.5.2课题内容通过对QR码国标的掌握，在研究己有QR码的编码过程的基础上，本课 题对QR码译码过程以及涉及到的各种关键技术进行研究,具体研究内容如下：1、研究QR码的基础理论和应用领域，比较国内外研究现状。2、研究QR码的编码过程尤其是编码规则，为译码做准备。3、深入研究QR码译码的具体过程，了解图像处理和纠错码的基本原理和 思路。4、对译码中可能出现的问题和难点进行分析，制定相应的解决方法。5、对纠错后的位流进行译码，得到编码信息。论文的具体内容安排如下：第一章：简要介绍了条码技术的产生背景、条码技术的特点以及前人在该 领域所取得的研究成果，重点介绍一下QR码的相关情况，最后讨论了一下本 课题的意义。第二章：因为我们研究的QR码的译码是编码的逆过程，所以必须在深刻 理解编码的原理和过程的基础上才能对译码过程做出正确的规划和设计。因此, 在第二章里面会详细介绍一下整个编码的流程，以及各种数据模式的编码方法, 为译码研究做理论准备。第三章：介绍了译码的流程，以及译码要达到的目标，使译码工作能沿着 正确的方向进行，提高了工作效率。第四章：这章是本文的重点，详细介绍了各种数据模式的译码方法。根据 已知的编码规则和方法，推导出相应的译码方法，并在程序上得到实现。通过 译码程序，可以将二进制的位流转换为数字模式、字母数字模式、八位字节模 式、中国汉字模式等我们可以识别的数据模式，实现了第三章的关于译码预定 目标。另外还有关于译码系统的正确性验证的方法，来验证译码系统是否能正 确，有效的对QR码进行译码操作。11第2章QR码编码理论第2章QR码编码理论2.1 QR码编码原理2.1.1 QR码编码流程QR码编码器将用户输入的信息数据进行编码，将编码结果以矩阵符号的 形式输出。根据国标GB/T2842000快速响应矩阵码，编码流程说明如下 第一步数据分析分析所输入的数据流，确定要进行编码的字符的类型。QR码包括几种不 同的模式，即数字模式、字母数字模式、8位字节模式、中国汉字模式，以便 高效地将不同的数据字符转换为符号字符，必要时可以进行模式之间的转换， 以便更高效地将数据转换为二进制位流。选择所需的纠错等级。如果没有预先规定所采用的符号版本，则选择与数 据相适应的最小版本。 第二步数据编码对于采用的模式按照每一种模式编码的规则，将数据字符转换为位流。当 需要进行模式转换时，在新的模式段幵始前加入模式指示符进行模式转换，在 数据序列后面加入终止符，将产生的位流分为每8位一个码字，必要时加入填 充字符以填满按照版本要求的数据码字数。经过上面一步，已经初步将编码数据转换成了数据码字，其流程图如图2.1 所示：子串转换为位流淸空子串己读完更新当前模式子串转换为位流子位流加入位流串图2.1数据编码流程图第三步纠错编码加入模式子串设置初始模式判断所属模式身当前模式相I按需要将码字序列分块，以便按块生成相应的纠错码字，并将其加入到相13第2章QR码编码理论应的数据码字序列的后面。第四步构造最终信息在每一块中置入数据和纠错码字，必要时加剩余位。第五步在矩阵中布置模块将寻像图形、分隔符、定位图形、校正图形与码字模块一起放入矩阵。第六步 掩模为了提高QRCode码的阅读可靠性，最好均衡的安排深色和浅色模块，尽 可能的避免位置探测图形的位图出现在其他区域。具体方法是依次将掩模图形 用于符号的编码区域，按照评价结果选择，使深色浅色模块比率最优。第七步格式和版本信息生成版本信息（如果需要)和格式信息，构成最终的符号矩阵。 2.1.2 QR码编码中的几个要点一、数据分析分析输入数据，根据内容选择采用缺省的或者其他适当的ECI (扩充解释） 与模式。从数字模式到中国汉字模式，每种模式的字符所需的位数依次增加。 在符号中可以通过模式的转换使数据的位流长度最短。数据的某些部分用一种 模式编码比用多种模式编码效率更高。例如：数字序列后跟随字母数字序列。 理论上说，用每个数据字符所需的位数最少的模式进行编码是最高效的，但每 次模式转换时都需要有相关模式指示符和字符计数指示符等形式的附加开销， 因此，对于较少的字符数，模式的转换并不总是能使位流总量最少。同时，由 于各个版本的容量的增加不是连续的，所以不一定在任何情况下都要达到最高 的转换效率。编码时进行模式转换应遵循下面的规则：1、选择初始模式时，(1) 如果初始输入数据在中国汉字字符集中，不包括其他字符，选择中国 汉字模式；(2) 如果初始输入数据在8位字节的专有子集中，选择8位字节模式；(3) 如果初始输入数据在字母数字的专有子集中，选择字母数字模式；(4) 否则，选择数字模式。2、转换模式时，(1) 在8位字节模式中，如果出现中国汉字专有子集，则转换到中国汉字 模式；(2) 在字母数字模式中，如果出现中国汉字专有子集，则转换到中国汉字 模式，如果出现8位字节专有子集，则转换到8位字节模式；(3) 在数字模式中，如果出现中国汉字专有子集，则转换到中国汉字模式， 如果出现8位字节专有子集，则转换到8位字节模式，如果出现字母数字专有 子集则转换到字母数字模式。二、模式1、数字模式数字模式对十进制数字09 (ASCII值30hex至39hex)进行编码，通常的密 度为每10位表示3个字符。2、字母数字模式字母数字模式对45个字符的字符集进行编码，即：10个数字。09(ASCII 值30hex至39hex)，26个字母字符AZ (ASCII值41hex至5Ahex)以及9个符号 SP、$、*、+、一、/、： (ASCn 值分别为 20hex，24hex, 25hex, 2Ahexhex, 2Bhex, 2Dhexhex, 2Ehex、2Fhex 3Ahex)。通常情况下，两个输入字符用11位表示。3、8位字节模式8位字节模式用于表示ASCn字符集(字符值为OOhex至FFhex)，其编码密 度每个字符8位。4、中国汉字模式中国汉字模式用于表示GE3 2312规定的双字节表示的中国汉字和非汉字 字符，其字符值为GB 2312规定字符对应的内码值。每个双字节字符由13位 二进制数表示。5、混合模式QR码符号可以包含在上面描述的多种模式所表示的混合数据序列。三、数据编码数据编码的任务是将输入的数据转换为一个位流，位流的每一段由以下内 容组成，它们包含：一模式指示符（4位）一字符计数指示符一数据位流21每个模式段以模式指示符的最高位开始，以数据位流的最低位结束。由于 段的长度己经由采用模式的规则以及数据字符数明确地确定，因此，段与段之 间没有特定的分隔。表2.1定义了每个模式的模式指示符。表2.2定义了采用不 同模式和符号版本的字符计数指示符的长度。表2.1模式指示符表摸式指示符模式指示符ECI0111中国汉字1101数宇0001结构链接0011宇母数字0010FNCI0】0丨(第一位置） iooi(第二位 s)8位字节0100终止符(信息结)0000每个符号的结束由4位终止符0000表示，当符号数据位流后所余的容量不 足4位时，终止符将被截短。终止符本身不是模式指示符表2.2字符计数指示符的位数版本数字棋式字母数字填式8位字节模式中囡汉字横式191098810-261211161027 40141316122.2 QR码数据编码2.2.1不同数据模式编码规则一、数字模式将输入的数据每三位分为1组，将每组数据转换为10位二进制数。如果所 输入的数据的位数不是3的整数倍，所余的1位或2位数字应分别转换为4位 或7位二进制数。将二进制数据连接起来并在前面加上模式指示符和字符计数 指示符。数字模式中字符计数指示符如表2-2中定义的有10,12或14位。输入 的数据字符的数量转换为10,12或14位二进制数后，放置在模式指示符之后J 二进制数据序列之前。 二、字母数字模式按照表2.3，每个输入的字符赋予一个数值V,它的值为0到44。 表2.3字符数字模式的编码/译码表字佑宇偟字值宇值字值字ft宇值字值符符符符符符符符0066c 12118024U30SP36421177D13J19P25Y31t37/43Z2881420Q26V32%38443399P15L21R2?133*3944A10G1622S28T34*40SB11II17N23T291m-41将输入的数据分为两个字符一组，用11位二进制表示。将前面字符的值乘 以45与第二个字符的值相加，将所得的结果转换为11位二进制数。如果输入 的数据的字符数不是2的整数倍，将最后一个字符编码为6位二进制数。将所 得的二进制数据连接起来并在前面加上模式指示符个字符计数指示符，在字母 数字模式中，字符计数指示符的长度为9,11或13位，其定义见表2-2。将输 入的字符数编码为A 11或13位二进制数，放在模式指示符之后，二进制数据 序列之前。三、8位字节模式在本模式中，一个8位码字直接表示一个输入数据字符的ASCII字符值， 即密度为每个字符8位。将二进制数据连接起来并在前面加上模式指示符和字符计数指示符。按表2-2的规定，8位字节模式的字符计数指示符为8位或16位，将输入字符数转 换为8位或16位二进制数据放在模式指示符之后，二进制数据序列之前。8位字节模式的位流的长度计算公式如下： B=4+C+8D其中:B=位流的位数；C=字符计数指示符的位数(见表2-2)； D=输入数据的字符数。四、中国汉字模式GB 2312中规定的中国汉字和非汉字字符共7445个，其中汉字字符6768 个。GB 2312规定的字符由两个字节表示。字符值为GB 2312中图形字符的内 码值。将输入数据字符按下面定义转换为13位二进制数。随后将二进制数据连 接起来并在前面加上模式指示符、中国汉字子集指示符和字符计数指示符。中 国汉字模式的中国汉字子集指示符为4位二进制数，字符计数指示符的位数按 表2-2规定为8,10或12位，将字符计数指示符转换为相应的8，10或12位二 进制数，放在模式指示符之后，二进制数据序列之前。对于第一字节值在Al hex到AAhex范围,第二字节值在A lhex到FE hex 范围的字符：(1) 第一字节值减去Alhex；(2) 将(1)的结果乘以60hex;(3) 第二字节值减去Alhex;(4) 将(2)的结果加上(3)的结果；(5) 将结果转换为13位二进制串。对于第一字节值在bo hex到FAhex范围，第二字节值在Al hex到FE hex 范围的字符：第一字节值减去A6 hex;(2) 将的结果乘以60hex;(3) 第二字节值减去Alhex；(4) 将(的结果加上(3)的结果；(5) 将结果转换为13位二进制串。对于所有的中国汉字字符：在输入的数据字符的二进制队列前加上模式指示符(1101)，中国汉字子集指示符(4位，对应GB2312的子集指示符为0001)和字符计数指示符的二进制 表示（8，10或12位)：中国汉字模式的位流长度计算方式如下-B=4+4+C+13D 其中：B=位流的位数；C=字符计数指示符的位数(见表2-2)； D=输入的数据字符数。 五、混合模式根据数据内容的要求或者为了增加编码密度，可以从一种模式转换为另一 种模式来表示数据。每一段数据按照前面给出的相应模式进行编码。基本结构 为模式指示符+字符计数指示符+数据，后面紧跟下一个模式指示符用来开始 下一段。表2.4为有n段数据的结构。表2.4混合模式数据格式段1段2段n数据指字符计数数数据指字符计数数数据指字符计数指数示符1指示符据示符2指示符据示符n示符据2.2.1位流的形成和到码字的转换符号的数据结尾由紧跟在最后一个模式段后面的终止符序列0000表示，当 数据位流数量正好填满符号的容量时，它可以省略，或者当符号所余的容量不 足组位时它可以截短。将各个数据模式译码的位流与终止符连接起来形成最终 的二进制位流。每个模式段的位流需要按顺序连接在一起，最后添加终止符，除非数据位 流正好填满符号容量。所得的数据位流将被分为一个个码字；所有的码字的长 度都是8位，如果位流长度最后一个码字不足8位，则用二进制值为4的填充 位填充至8位，填充位应加在数据位流最后1位(最低位)的后面。然后按国家 标准中的表7所定义的版本和纠错等级交替添加填充码字11101100和 00010001,将数据位流扩展，以填满符号的数据容量，所得结果的数据码字序 列进行处理加入纠错码字。为了正好填满符号容量，有些版本也许需要在信息 的最后添加3，4或7个剩余位(全为0)。第2章QR码编码理论2. 3纠错及码字的最终形成2.3.1纠错QR码采用纠错算法生成一系列纠错码字，添加在数据码字序列后，使得 符号可以在遇到损坏时不致丢失数据。纠错共有4个纠错等级，对应4种纠错 容量，如表2.5所示表2. 5纠错等级纠铕等级LNQH纠错容量，近似值）7152530纠错码字可以纠正两种类型的错误，拒读错误（错误码字的位置己知）和 替代错误（错误码字位置未知）。一个拒读错误是一个没有扫描到或者无法译码 的符号字符，一个替代错误是错误译码的符号字符。如果一个缺陷使得深色模 块变成浅色模块或者将浅色模块变成深色模块，将符号字符错误的译码为是另 外一个不同的码字，造成替代错误，这种数据替代错误需要两个纠错码字来纠可纠正的替代和拒读错误的数量由下式给出： e+2td-p其中：e=读错误数； t=替代错误数； d=纠错码字数； p=错误检测码字数。根据版本和纠错等级，将数据码字序列分为1个或多个块，对每一个块分 别进行纠错运算。国家标准的表9中列出了每一个版本、每一个纠错等级的码 字总数、纠错码字总数以及纠错块的结构和数量。如果某一符号版本需要剩余位填充符号容量中的剩余的模块，剩余位均为0。按照GB/T 18284-2000的规定，将数据码字(必要时包括填充码字在内)分 为相应数量的块，每一块分别计算出纠错码字并添加到数据码字后。第2章QR码编码理论QR码的多项式算法用位的模2算法和字节的模100011101算法。这是伽 罗华域2的00011101表示主模块多项式：x4+ x+ xM据码字为多项式各项的系数，第一个数据码字为最高次项的系数，第一个 纠错码字前的最后一个数据码字是最低次项的系数。纠错码字是数据码字被纠错码多项式g(x)除得的余数。的最高次项系数为 第一个纠错码字，最低次项系数为最后一个纠错码字，也是整个块的最后一个 码字。2.3.2构造信息的最终码字序列最终码字序列中的码字数应与国家标准中的表7和表9所列的符号能够表 示的码字总数相同。按如下步骤构造最终的码字序列(数据码字加上纠错码字，必要时加上剩余 码字)。(a) 国家标准中的表9，根据版本和纠错等级将数据码字序列分为n块。(b) 每一块，按照纠错码字的生成规则和国家标准的附录A计算相应块的 纠错码字。(c) 每一块的数据和纠错码字装配成最终的序列：数据块1的码字1，数据 块2的码字1,数据块3的码字1，以此类推至数据块n-1的最后一个码字，数 据块n的最后一个码字：随后，纠错块1的码字1,纠错块2的码字1,以 此类推至纠错块n-1的最后一个码字，纠错块XI的最后一个码字。QR码符号所 包含的数据和纠错块通常正好填满符号的码字容量，而在某些版本中，需要3，4 个剩余位，添加在最终的信息位流中以正好填满编码区域的模块数。在块序列中，最短的数据块应在序列的最前面，所有的数据码字应放在第 一个纠错码字的前面。2.3.3码字在矩阵中的布置在QR码符号中有规则的和不规则的两种类型的符号字符。它们的使用取 决于它们在符号中的位置，以及与其他符号字符和功能图形的关系。多数码字在符号中表示为规则的2X4个模块的排列。其排列有两种方式: 垂直排列(2个模块宽，4个模块高)和水平位置(4模块宽，2个模块高)。当改 变方向或紧靠校正图形以及其他功能图形时，需要不规则符号字符。关于功能 图形的布置按照与使用的版本相对应的模块数构成空白的正方形矩阵。在寻像 图形、分隔符、定位图形以及校正图形相应的位置，填入适当的深色或浅色模 块。格式信息和版本信息的模块位置暂时空置。最后在QR码符号的编码区域 中，符号字符以2个模块宽的纵列从符号的右下角开始布置，并自右向左，且 交替地从下