（计算机应用技术专业论文）二维条码qr+code纠错算法的研究与实现.pdf

摘要 摘要 条码技术是以计算机技术、光电传感技术和通信技术为基础发展起来的一 项自动识别技术，现在已经成为信息数据自动输入、识别的重要方法和手段。 二维条码q rc o d e ( 快速响应矩阵码) 具有超高速识读、全方位识读、更有效地 表示汉字、信息存储量大、纠错能力强等特点。因此，q rc o d e 在国民经济的各 个领域应用特别广泛，在我国具有广阔的发展前景。 q rc o d e 编码和译码技术的核心之一是q rc o d e 的纠删纠错算法，从而保证 识别出的码字数据完整、正确。本文着重分析了q rc o d e 编译码技术的理论基 础，重点研究了q rc o d e 纠删纠错算法，完成了纠删纠错算法的程序设计的方 法和核心代码，具体介绍了本课题完成的q rc o d e 纠删纠错算法的纠错效果和 实验结果。经过测试，本课题完成的q rc o d e 纠删纠错译码器能成功地纠正q r c o d e 的4 0 个版本的全部纠错等级，最多能恢复3 3 3 3 的数据。 q rc o d e 译码产品多是用硬件实现的专用译码设备，在普通计算机上用 v i s u a lc + + 实现q rc o d e 纠删纠错功能，具有成本低廉和通用性强的优点。本 课题实现的q rc o d e 纠删纠错功能能将纠删纠错的中间结果和参数显示出来， 能清晰地反映出纠删纠错过程。通过修正纠错算法，纠错器不仅能纠正错误( 替 代错误) 还能纠正删除( 拒读错误) ，具有良好的纠删纠错特性和实用价值。 关键词：q rc o d e ；二维条码译码；纠删纠错 a b s t r a c t a b s t r a c t b a rc o d et e c h n o l o g yi san e w - s t y l et e c h n o l o g yb a s e do nc o m p u t e rt e c h n o l o g y ， i n f o r m a t i o nt e c h n o l o g ya n dp h o t o e l e c t r i cs e n s i n gt e c h n o l o g y i tn o wb e c o m e sv e r y i m p o r t a n tm e a no fd a t ai n p u t i n gr e c o g n i t i o n q rc o d eh a sm a n ya d v a n t a g e s ，f o r e x a m p l e ：l a r g ei n f o r m a t i o nc a p a c i t y , w i l de n c o d i n gr a n g e ，h i g hr e l i a b i l i t y , s e c u r i t y , a n ds t r o n ge r r o r - c o r r e c t i o na b i l i t y , a l t e r a b l eb a rc o d es y m b o l ，e a s yt om a k e ，l o wc o s t a n di n d e p e n d e n to fd a t a b a s ee t c q rc o d eh a sa m p l i t u d e f o r e g r o u n di ne v e r yf i e l do f n a t i o n a le c o n o m ya sw eh a v e9 魄 t h ec o r eo fe n c o d i n ga n dd e c o d i n go fq rc o d ei se r r o r sa n dd e l e t e s - c o r r e o t i n g f u n c t i o n t h ei n t e n t i o ni st om a k es u l et h ed a t aa f t e rr e c o g n i t i o na r ei n t e g r i t ya n d e x a c t n e s s t h i s p a p e rp u te m p h a s i s o n a n a l y s i s o ft h e o r i e so fe r l o r sa n d d e l e t e s - c o r r e c t i n gd e c o d i n ga n dr e s e a r c h i n go fe r r o r sa n dd e l e t e s - c o r r e c t i n gd e c o d i n g a r i t h m e t i c t oe x p l a i np r o g r a m so ft h i sa r i t h m e t i ci nd e t a i lb yu s i n gl o t so fc o d e s t h i s p a p e ra l s os h o w s r e s u l t so f t e s t i n ga n de f f e c t so fe x p e r i m e n tb yu s i n ge x a m p l e s t h i s i m p l e m e n to fe l l o r s a n dd e l e t e s - c o r r e c t i n gf u n c t i o nc a na c h i e v ea l l a 1 o r sa n d d e l e t e s c o r r e c t i n gg r a d e s ，a b o u t3 3 3 o f d a t ac a nb er e s t o r e da tb e s t t h ei m p l e m e n to fe r r o r sa n dd e l e t e s c o r r e c t i n gs e t , r a r eb yv i s u a lc + + h a s a d v a n t a g e s ：l o wc o s ta n dh i g hc o m p a t i b i l i t yc o m p a r e db ys p e c i a ld e c o d i n ge q u i p m e n l t h i ss o f t w a r ec a na l s os h o w so u t c o m e sa n dk e yp a r a m e t e r si ne l l o r s a n d d e l e t e s - c o r r e c t i n gp r o c e s s i nt h ef i n a l i t y , t h ep r o b l e m sr e q u i r i n gf u r t h e rs t u d i e sa r e d i s c u s s e d k e yw o r d s ：q rc o d e ；d e c o d i n g o ft w o d i m e n s i n o a lb a r c o d e ；e r r o r s a n d 学位论文版权使用授权书 本人完全了解北京机械工业学院关于收集、保存、使用学位论文 的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和 电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以 及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向 国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名： 家难 ( 舢宫年2 月2 君日 ( 注：非保密论文无需签字) 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 1 示锥 瑚年2 - 月羽e t 第1 章引言 1 1 条码技术概述 第1 章引言 自动识别技术是信息数据自动识读、自动输入计算机的重要方法和手段， 它是以计算机技术和通信技术为基础的综合性科学技术。自动识别技术近几十 年在全球范围内得到了迅猛发展，形成了一个包括条码技术、光学字符识别、 磁卡技术、智能卡、射频技术、声音识别及视觉识别等集计算机、声光、机电、 通信技术为一体的高新技术学科。条码技术是自动识别技术领域里应用得最为 广泛的一门技术隅1 。 条码技术是以计算机技术、光电传感技术和通信技术为基础发展起来的一 项自动识别技术，现在已经成为信息数据自动输入、识别的重要方法和手段。 条码技术是在计算机的应用实践中产生和发展起来的。由于其优点众多，因而 发展迅速，应用广泛。条码技术在商品、工业、物流业、邮电业、医疗卫生、 物资管理、安全检查、服务业、证卡管理、军事工程、办公室自动化等领域中 得到广泛应用。条码技术的应用极大地提高了数据采集和信息处理的速度，改 善了人们的工作和生活环境，提高了工作效率，并为管理的科学化和现代化做 出了重要贡献啪1 。 条码是由一组规则排列，宽窄不一的条、空组成的标记，用以表示一定的 信息，它是一种由光电扫描识读设备自动识读并实现信息自动输入计算机的图 形标示符。条是指条码中反射率较低的部分，也就是指黑色或深色的条形。空 是指条码中反射率较高的部分，也就是指白色或浅色的条形。条码是一个标记， 表示一定的信息，不同的条码标记不同的信息。条码中条与空的排列是有规律 的，不是任意排列、杂乱无章的，条与空的排列的形状反映了条码包含的信息 内容。一个完整的条码大体由以下几个部分构成：条码字符，起始符和终止符， 空白区。 相对于其他的识别技术，条码技术具有很多优点：输入速度快、可靠性高、 信息采集量大、灵活实用、自由度大、经济性好等优点，条码技术是目前最经 济、实用的一种自动识别技术，因而在国民经济的各个领域得到了广泛的应用。 第1 章引言 一维条码数据容量较小，只能包含3 0 个字符左右的字母和数字，无法表示汉字、 图像等信息，需要依赖数据库，应用范围有限。条码尺寸相对较大( 空间利用率 较低) ，条码遭到损坏后便不能阅读，鲁棒性差。因此人们迫切希望发明一种新 的条码，除具有普通条码的优点外，同时具有信息容量大、可靠性高、保密防 伪性强、易于制作、成本低廉等优点心引。 1 2 二维条码技术简介 1 2 1 二维条码简介 二维条码技术是在一维条码无法满足实际应用需求的前提下产生的。由于 受信息容量的限制，一维条码通常是对物品的标识，而不是对物品的描述。所 谓对物品的标识，就是给某物品分配一个代码，代码以条码的形式标识在物品 上，用来标识该物品以便自动扫描设备的识读，代码或一维条码本身不表示该 产品的描述性信息。 因此，在通用商品条码的应用系统中，对商品信息，如生产日期、价格等 的描述必须依赖数据库的支持。在没有预先建立商品数据库或不便联网的地方， 一维条码表示汉字和图像信息几乎是不可能的，即使可以表示，也显得十分不 便且效率很低。随着现代高新技术的发展，迫切需要用条码在有限的几何空间 内表示更多的信息，以满足千变万化的信息表示的需要。 国外对二维条码技术的研究始于2 0 世纪8 0 年代末。在二维条码符号表示 技术研究方面，已研制出多种码制，常见的有p d f 4 1 7 ，q rc o d e ，c o d e4 9 ， c o d e1 6 k ，c o d eo n e 等。这些二维条码的密度都比传统的一维条码有了较大的 提高，如p d f 4 1 7 的信息密度是一维条码c o d e 3 9 的2 0 多倍。在二维条码标准化 研究方面，国际自动识别制造商协会( a i m ) 、美国标准化协会( a n s i ) 已完成 了p d f 4 1 7 ，q rc o d e ，c o d e4 9 ，c o d e1 6 k ，c o d eo n e 等码制的符号标准。新 成立的国际标准化组织国际电工委员会第一联合委员会的第三十一分委员 会，即条码自动识别技术委员会( i s o i e c j t c l s c 3 1 ) ，已制定了q rc o d e 的 国际标准( i s 伽e c18 0 0 4 ：2 0 0 0 自动识别与数据采集技术条码符号技术 规范q r 码，起草了p d f 4 1 7 ，c o d e1 6 k ，d a t am a t r i x ，m a x ic o d e 等二维 条码的i s o i e c 标准草案。在二维条码设备开发研制、生产方面，美国、日本 2 第1 章引言 等国的设备制造商生产的识读设备、符号生成设备，已广泛应用于各类二维条 码应用系统。二维条码作为一种全新的信息存储、传递和识别技术，自诞生之 曰起就得到了世界上许多国家的关注。美国、德国、日本、墨蓖哥、埃及、哥 伦比亚、巴林、新加坡、菲律宾、南非、加拿大等圜，不仅已将二维条码技术 应用于公安、外交、军事等部门对各类证件的管理，而且也将二维条码应用于 海关、税务等部门对各类报表和票据的管理，商业、交通运输等部门对商品及 货物运输的管理，邮政部门对邮政包裹的管理，工业生产领域对工业生产线的 自动纯镑理。 我国对二维条码技术的研究开始于1 9 9 3 年。中国物品编码中心对几种常用 的二维条码p d f 4 1 7 ，q rc o d e ，d a t am a t r i x ，m a x ic o d e ，c o d e4 9 ，c o d e1 6 k ， c o d eo n e 的技术规范进行了翻译和跟踪研究。随着我国市场经济的不断完善和 信息技术的迅速发展，国内对二维条码这一新技术的研究和霈求与日俱增。中 国物品编码中心在原国家质量技术监督局和国家有关部门的大力支持下，对二 维条码技术的研究不断深入。在消化国外相关技术资料的基础上，制定了两个 二维条码的国家标准：g 8 t1 7 1 7 2 1 9 9 7 西一七条| 鹦，g b t1 8 2 8 4 - 2 0 0 0 快 速响应矩阵码嗍。 1 2 2 二维条码的技术特点 上世纪九十年代以来，二维条码逐渐发展超来并褥到越来越广泛的应用， 二维条码可以在横向和纵向两个方向携带信息，信息的容量更大。二维条码具 有以下许多特点： 1 信息高密度存储 二维条码通过剩用垂直方向的堆积来提高条码的信息密度。而且采用高密度 图形表示，通常情况下其密度是一维条码的几十到几百倍，这样我们就可以把 信息全部存储在一个二维条码中，要查看信息，只要用识读设备扫描二维条码 即可，因此不需要事先建立数据库，真正实现了用条码对信息的直接描述。t 2 具有一定的纠错功能 一维条码的应用建立在这样一个基础上，那就是识读时掇读( 即读不出) 要比 误读( 读错) 好。因此一维条码通常同其表示的信息一同印制池来。当条码受到 损坏( 如污染，脱墨等) 时，可以通过键盘录入代替扫描条码。鉴于以上原则， 3 第1 章引言 一维条码没有考虑到条码本身的纠错功能，尽管雩l 入了校验字符的概念，但仅 限于防止读错。二维条码可以表示数以千计字节的数据，通常情况下，所表示 的信息不可能与条码符号一同印刷出来。如果没有纠锩功能，当二维条码的某 部分损坏时，该条码便变得毫无意义，因此二维条码引入错误纠正机制。这种 纠错机制使得二维条码因穿孔、污损等引起局部损坏时，照样可以正确得到识 读。这种纠错机制使得二维条码成为一种安全可靠的信息存储和识别的方法， 这是一维条码无法相比的。 3 。可以表示多种语言文字 多数维条码所能表示的字符集不过是2 0 个数字，2 6 个英文字母及一些特 殊字符。条码字符集最大的c o d e1 2 8 条码，所能表示的字符个数也不过是1 2 8 个a s c i i 符。因此要用一维条码表示其它语言文字( 如汉字、日文等) 是不可能 的。二维条码具有字节表示模式，即提供了一种表示字节流的机制。我们知道， 不论何种语言文字，它们在计算机中存储时以机内码的形式表现，丽机内码都 是字节码。这样我们就可以设法将各种语言文字信息转换成字节流，然后再将 字节流焉二维条码表示，从而为多种语言文字的条码表示提供了一条翦所未有 的途径。 4 。可表示图像数据 既然二维条码可以表示字节数据，而图像多以字节形式存储，因此使图像 【如照片、指纹等) 的条码表示成为可能。 5 可弓l 入加密机制 加密机制的引入是二维条码的又优点。比如我们用二维条码表示照片时， 我们可以先用一定的加密算法将图像信息加密，然后再用二维条码表示。在识 别二维条码时，再加以一定的解密算法，就可以恢复所表示的照片。这样便可 以防止各种证件、卡片等的伪造。 1 2 。3 ：维条码的分类 诸多优点和低廉的成本使得条码技术被广泛地应用于物流信息自动化和工 业自动化生产过程的诸多锤业。二维条码是用某种特定的凡何图形按一定勰律 在平面( 二维方向) 上分布的条、空相间的图形来记录数据符号信息。它具有条 码技术的共性，即每种码制有其特定的字符集；每个字符占有一定的宽度；具有 4 第1 章引言 定的校验功能等。与一维条码一样，二维条码也有许多不同的编码方法，或 称码制。就这些码制的编码原理而言，通常可分为以下三种类型： 1 线性堆叠式二维码是在一维条码编码原理的基础上，将多个一维码在纵 向堆叠而产生的。典型的码制如：c o d e1 6 k ，c o d e4 9 ，p d f 4 1 7 等。 2 矩阵式二维码是在一个矩形空间通过黑、白像素在矩阵中的不同分布进 行编码。典型的码制如：a z t o c ，m a x ic o d e ，q rc o d e ，d a t am a t r i x 等。 3 邮政码 通过不同长度的条进行编码，主要用于邮件编码，如：p o s t n e t ，b p o4 - s t a t e 。 1 3 快速响应矩阵码0 rc o d e 概述 快速响应矩阵码cq u i c kr e s p o n s ec o d e ，简称q rc o d e ) 是由日本d e n s o 公司于1 9 9 4 年9 月研制的一种矩阵式二维条码符号，它是在一个矩形空间通过 黑、白像素在矩阵中的不同分布进行编码。1 9 9 7 年1 0 月被自动识别制造商协会 ( 姐) 制定为国际规格。1 9 9 9 年1 月被制定为j i s 规格。2 0 0 0 年6 月1 5 日被正 式接纳为i s o 国际规格。2 0 0 1 年我国颁布了快速响应矩阵码q rc o d e 国家标 准标志着q rc o d e 在我国的应用和发展进入了一个新的阶段啪1 。 1 3 1q r0 0 d e 的构成 每个q rc o d e 符号由正方形模块组成的一个正方形阵列构成，它由编码区 域和包括寻像图形、分隔符、定位图形和校正图形在内的功能图形组成，功能 图形不用于数据编码。符号的四周为空白区。q rc o d e 符号共有4 0 种规格，分 别为版本l 、版本2 版本4 0 。版本1 的规格为2 1 模块2 l 模块，版本2 为 2 5 模块x2 5 模块，以此类推，每一版本符号比前一版本每边增加4 个模块，直 到版本4 0 ，其规格为1 7 7 模块x1 7 7 模块。每个校正图形可看作是3 个重叠的 同心正方形，由5 5 个深色模块，3 3 个浅色模块以及位于中心的一个深色模 块组成编码区域包括表示数据码字、纠错码字、版本信息和格式信息的符号字 符。空白区域环绕在符号四周的4 个模块宽的区域，其反射率应与浅色模块相 同。如图1 所示。q rc o d e 包括：扩充解释模式、数字模式、字母数字模式、 8 b i t 字节模式、中国汉字模式和混合模式，各种模式对应不同字符集，使用不同 5 第1 章引言 模式进行编码时，可以在模式之间进行转换，高效地将数据转换为二进制位流。 图1 1q rc o d e 符号结构 位置探测图形 校正图形 数据和纠错码字 空白区 q rc o d e 条码表面包括两个部分：功能图形和数据图形。数据图形包括数 据码词信息和纠错码词信息。功能图形主要用来定位图形和探测图形以及检测 条码版本信息和纠错等级。q rc o d e 各部分图形的空间分布如下： 1 校正图形 校正图形的数目因版本不同而不同，版本l 没有校正图形，版本2 6 有1 个校正图形，版本7 - 1 3 有6 个校正图形，以次类推，每七个版本校正图形的数 量就增加一次。每个位置探测图形都可以看作是三个重叠的同心正方形组成， 由5 5 个深色模块，3 3 个浅色模块以及位于中心的一个深色模块组成，校正 图形的数量视符号的版本号而定。校正图形都相对于从左上角到右下角的对角 线对称，每个校正图形的坐标参考文献2 3 。 2 位置探测图形 位置探测图形又叫寻像图形，3 个位置探测图形分别在q rc o d e 的左上角、 右上角和左下角。每个位置探测图形都可以看作由三个重叠的同心的正方形组 成，它们分别7 x 7 个深色模块、5 5 个浅色模块和3 x 3 个深色模块。符号中 其他地方遇到类似图形的可能性极少，因此可以在视场中迅速地识别可能的q r c o d e 符号。识别组成寻像图形的三个位置探测图形，可以明确地确定视场中符 号的位置和方向。 3 定位图形 在q rc o d e 符号中，有两条定位图形：一是垂直定位图形；另一是水平定 位图形，二者相对于从左上角到右下角的对角线对称，由单行( 列) 黑白交错的 6 第1 章引言 单位模块组成。无论版本多少，水平的定位图形开始于左上角的位置探测图形 右侧而终止于位置探测图形左侧，距离q r c o d e 符号上端6 个单位模块的边长。 垂直定位图形开始于左上角的位置探测图形终止于左下角的位置探测图形符号 上端，距离q rc o d e 符号左边6 个单位模块边长。 4 格式信息与版本信息 版本信息记录当前q rc o d e 的版本号以及版本纠错码号。版本信息一共有 两个，分别分布在左下角位置探测图形的上部和右上角位置探测图形的左侧。 5 码字信息 在q rc o d e 符号的编码区域中，符号字符以2 个模块宽的纵列从符号的右 下角开始布置，并且自右向左，交替地从上到下或从下到上安排。当符号地数 据量不能恰好分为8 位符号字符时，要用相应的剩余位填满符号的容量。码字 信息既包括数据码字信息也包括纠错码字信息两部分。 q rc o d e 有8 种掩模图形，q rc o d e 的掩模是为了均衡地安排深色与浅色 模块，更加便于识读条码码词。尽可能地避免位置探测图形的位图1 0 1 11 0 1 出现 在其他区域，从而提高q rc o d e 可识读性。为了满足上述要求，需按照下列步 骤进行掩模“： 1 掩模作用于功能图形。 2 用多个矩阵图形连续地对已知的编码区域的模块图形r 格式信息和版本信 息除外) 进行x o r 操作。x o r 操作将模块图形依次放在每个掩模图形上，并将 对应于深色的掩模图形取反。 3 对每个结果图形的不合要求部分记分以评估这些结果。 4 用8 种掩模图形依次对符号的编码区域的位图进行掩模处理，评价所得 的8 种结果，选择得分最低的图形。 1 3 2 肌c o d e 的技术特点 q rc o d e 除了具有一维条码及其它二维条码所具有的信息容量大、可靠性 高、可表示汉字图像等多种信息、保密防伪性强等优点外，还具有以下主要特 点： 1 超高速识读 q rc o d e 码的英文名称是叫c kr e s p o n s ec o d e ，超高速识读特点是其区别 7 第1 章引言 于p d f 4 1 7 、d a t a m a t r i x 等其他二维条码的主要特性。用c c d 二维条码识读设 备每秒可识读3 0 个含有1 0 0 个字符的q rc o d e 符号，对于含有同样数据信息的 p d f 4 1 7 则只可识读3 个符号。 2 全方位识读 全方位( 3 6 0 度) 识读特点是优于行排式二维条码的主要特点，如p d f 4 1 7 的识读方位角仅为正负1 0 度。 3 能有效地表示中国汉字、日本汉字 由于q rc o d e 码采用独特的数据压缩模式表示中国汉字和日本汉字，仅用 1 3 b i t 就可以表示一个汉字，而p d f 4 1 7 、d a t am a t r i x 等二维条码没有特定的汉 字表示模式，只能用字节模式表示汉字，需用1 6 b i t 表示一个汉字，因此相对于 其他二维条码，q rc o d e 码表示汉字的效率提高了2 0 ，这也是q rc o d e 码在 我国具有良好应用前景的主要因素之一。 1 3 30 r0 0 d o 的纠错能力 q rc o d e 采用纠错算法生成一系列纠错码字，添加在数据码字序列后，使 得符号可以在遇到损坏时不致丢失数据。纠错共有四个等级，对应四种纠错容 量，如表1 1 所示。 表1 1q rc o d e 纠错等级与纠错容量 纠错等级 lmqh 纠错容量 7 1 5 2 5 3 0 9 6 纠错码字可以纠正两种类型的错误：拒读错误和替代错误。一个拒读错误 ( 错误码字的位置已知) 是一个没扫描到或无法译码的符号字符，一个替代错 误( 错误码字的位置未知) 是错误译码的符号字符。如果一个缺陷使得深色模 块变成浅色模块或将浅色模块变成深色模块，则错误地将符号码字译码为另一 个不同的码字，造成替代错误。这种数据错误需要两个纠错码字来纠正。可纠 正的替代错误和拒读错误的数量由下式给出： p + 2 f d - p ( 1 1 ) 其中：e = 拒读错误数t = - 替代错误数；d _ 纠错码字数；p = 错误检测码字数。 8 第1 章引言 1 3 4o rc o d e 技术在我国的研究现状 虽然，我国早在1 9 9 4 年就开始关注q rc o d e 技术，并且在2 0 0 1 年发布了 q rc o d e 国家标准，并取得了一些成绩，但我国在整体上与国外研究水平和商 品化程度还有相当大的差距。在我所调查的3 0 家厂商与经销商中，有2 0 家是 做国外相关产品与服务的代理商，另外1 0 家中具有独立研发能力的厂家寥寥无 几。国内的研发力量薄弱，研发投入不够，目前还没有我国自主知识产权的q r c o d e 译码设备。尽管早在“九五一期间国家就提及要全力研制、积极试点、快 速推广二维条码技术，但与之配套的一系列政策法规并没有出台，国家对产业 的扶持的力度还远远不够。一些国内厂商急功近利，仅仅满足于做国外厂商的 代理商和服务商。此外，二维条码技术引入我国不久，全社会对二维条码在国 民经济中的广泛应用和对于提高产业信息化的认识不足。国内的译码设备处于 研发阶段距离产品市场化还相去甚远，进口的译码设备价格昂贵，这些都严重 制约了q rc o d e 在我国的应用和发展。 1 3 5o rc o d e 的应用前景 二维条码q rc o d e 作为一种新的信息存储和传递技术，从诞生之始就受到 了国际社会的广泛关注。在流通领域，q rc o d e 广泛应用于货物出入库管理， 零售店的订货贩卖管理系统，f a 领域的工程管理等。在日本q rc o d e 还被印 在名片、户外广告牌、优惠券和产品包装等任何介质之上。日本本田公司使用 q rc o d e 应用管理解决方案使本田汽车在生产过程控制管理系统中成功应用了 q rc o d e 数据采集技术完成了生产的各个工序作业的管理。本田公司发货单和 收货单都是用q rc o d e 来编码，q rc o d e 包含了客户资料、发运商、货物编码、 数量和其他相关信息，这些数据可以用于订单处理和产品跟踪。在日本，q rc o d e 识别设备已经逐渐呈现微型化趋势，人们将手机镜头对准商场门口的标牌，就 能下载店内当天的所有打折信息和优惠券。这种条码还可以提供定位服务，在 十字路口路标上的q rc o d e 将告诉你附近的餐馆和其它消费场所的分布信息。 q rc o d e 在日本应用很广泛，很多产品都有q rc o d e ，用来描述产品名称、产 地、生产日期、价格等信息。如今，条码手机二维条码业务已经被中国移动确 定为重点发展领域，译码设备的微型化称为研究的新热点领域，手机二维条码 技术是以二维码标准为核心，将手机作为载体，而展开的码制编码、译码、识 9 第1 章引言 别和被识别相结合的综合技术。q rc o d e 的高密度信息存储和全方位识读特性， 特别适合存储高信息密度的图像信息。q rc o d e 用特定的数据压缩模式表示中 国汉字和日本汉字，表示汉字的效率比其他的二维条码提高了2 0 。这特点是 q rc o d e 在我国具有良好的应用前景的主要因素之一。 1 4 研究内容和课题意义 q rc o d e 是一种应用极其广泛的，在我国有广阔的应用前景的一种重要的 二维条码。如前所述，作为矩阵式二维条码q rc o d e 有着其他二维条码无法相 比的优势：1 超高速识读；2 全方位识读；3 高密度信息存储；4 较强纠错能力； 5 引入了数据加密机制；6 适合表示汉字等等。作为一种便携式数据文件，q r c o d e 在我国的研究还处于刚刚起步阶段，如今国内对这一技术的需求与日俱增。 尤其是近两年，二维条码已在国民经济的许多领域得到了快速的发展和应用， 巨大的市场需求推动着二维条码技术不断向前发展。 q rc o d e 识读设备的关键是纠错译码识别。保证条码携带的信息完整、正 确、无误必须要有高效的纠错译码设备。q rc o d e 具有较强的纠错功能，其纠 错算法与人造卫星，高清晰彩色电视，移动通讯等所使用的纠错算法类似，这 种纠错机制安全可靠，实现的难度也偏大。目前，国外的q rc o d e 纠错译码软 件都是在硬件环境中实现的专用纠错译码设备。本课题研究的目标是在掌握译 码原理基础上，跟踪国内外的研究前沿找到一个高效的纠删纠错算法，并在普 通计算机上用软件实现q r c o d e 的纠删纠错功能。能够使得q r c o d e 在损坏3 3 3 的数据后还能恢复出原始信息，能够达到国家纠错标准h 等级，具有一定的 实用价值。 论文第一章主要介绍自动识别技术、条码技术、二维条码技术概况和q r c o d e 的技术构成和技术特点，着重分析了q rc o d e 在我国的应用前景和推广应 用的可行性以及在我国应用中存在的主要问题。论文第二章主要讨论了纠删纠 错的理论基础差错控制理论，着重讨论了线性分组码、循环码、b c h 码的 生成矩阵、校验矩阵和伴随算子以及多项式的环、域、理想、有限域元素的运 算，重点分析了b c h 码的一般译码方法。论文第三章分析了r e e d s o l o m o n 代 数译码算法理论基础，着重研究了r s 码时域、频域编码理论，r s 迭代纠错算 法，纠删纠错译码算法。第三章和第四章是纠删纠错算法的理论基础。第四章 1 0 第1 章引言 是二维条码q rc o d e 的纠删纠错原理和流程，分析了各种纠错算法的优缺点， 重点讲解了纠错过程的几个部分：伴随算子和修正伴随算子的计算算法，错误 位置多项式系数的计算算法，删错位置多项式的构成，错误位置的计算算法， 错误幅值的计算算法。从算法原理上，阐述了q rc o d e 纠删纠错译码过程。第 五章是第四章译码算法理论的软件实现过程，详细分析了译码过程的核心代码： 伽罗华域元素的构造代码、纠错码词生成多项式构造代码，编码程序设计，伴 随算子和修正伴随算子的计算程序，删错位置多项式的程序设计，错误位置和 错误幅值的计算程序。第四章和第五章是q rc o d e 纠删纠错算法的理论设计和 软件实现的综述。第六章则是纠删纠错算法的实现，纠删纠错算法的运行结果 的重要参数。第七章包括三个部分：对课题结果分析、课题的难点总结和创新 点总结，最后包括对课题的展望。这七个部分从理论到实践再到总结和展望， 展现了q rc o d e 纠删纠错算法实现的整个过程。 第2 章纠删纠错理论基础 第2 章纠删纠错理论基础 2 1 差错控制编译码技术 2 1 1 差错控制技术原理 通信的目的是要把对方不知道的消息及时可靠地传送给对方，因此，要求 一个通信系统传输消息必须可靠与快速。所有的数字通信系统如通信、雷达、 遥控遥测、数字计算机的存贮系统和内部运算以及数字计算机之间的数据传输 等，都可以归结为图2 1 所示的模型。 图2 1 数字通讯编码译码模型 q rc o d e 的编译码过程也与上述原理相同。图中，信源编码器是把信源发 出的消息如图像、文字等转换为编码形式的信息序列，并且为了使传输有效， 还去掉了一些与传输信息无关的多余度。为了抗击传输过程中的各种干扰，往 往要人为地增加一些多余度，使其具有自动检错或纠错能力，这种功能由纠错 编码器完成。 1 2 第2 章纠删纠错理论基础 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通信的数学理论”中，首次阐明 了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定 了信息理论的基础。他指出了任意给定的信源都有一个称为熵的量，其表征了 信源的不确定性，这正好是信源的下限( 信源编码定理) 。同时他还提出了著名 的信道编码定理：任意给定的信道都有一个固定的量，称为信道容量。只要信 息的传输速率低于信道容量，总可以找到一种编码方法，使得差错概率任意的 小；反之，如果信息的传输率超过了信道容量，则不存在这样的编码方法。编 码定理表明，信道容量正好等与信息传输率的上确界。 这使人们认识到可以通过信道编码来提高通信的可靠性，而编码是通过在 发送符号之间引入冗余和记忆来实现的。加入冗余位后，可以纠正一些错误， 最终提高解调数据的可靠性，合理选择调制时的冗余，可以提高输入系统的误 码性能，我们是以编码增益来衡量的。编码增益定义为编码前后信噪比之差： cc c g = 1 0 l 甙善) 删一1 0 1 甙善) 删( 删 ( 2 1 ) yy 一般情况下，标准的差错控制系统可以得到6 - 9 d b 的编码增益。在加性高 斯白噪声( a w g n ) 信道中，设每符号平均能量为e s ，信号周期为t ，带宽为w ， 在理想情况下( 按n y q u i s t 准则) ，w = i t ，信号平均功率p = e s t ，则信道的平均 信噪比： d口 d d s n r = 二= 二r l = 如r - , b( 2 2 ) n q w 2 0 。 n q 其中的e b 是每比特的平均能量，是码率，表示每编码符号运载的平均信 息比特数( 信息量) ， 1 2 = n o 2 是高斯噪声的方差。则信道容量： c = w l 0 9 2 ( 1 + s n r ) = w l 0 9 2 ( 1 + 也乜0 ) ( 2 3 ) 原始的数据信息经过条码纠错编码器编制成条码信息，条码信息在传输过 程中，会受到噪声源干扰出现错误，纠错译码器纠正条码出现的错误。 一一一一一一一一一一1广一一一一一一一一一一i 1 3 第2 章纠删纠错理论基础 2 1 2 差错控制系统分类 图2 2 条码编译码通信模型 1 检错重发( a r q ) ： 在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道 要求发送端重新发送，直到接收端检查无误为止。a r q 系统具有各种不同的重 发机制：如可以停发等候重发、x 2 5 协议的滑动窗日选择重发等。a r q 系统需 要反馈信道，效率较低，但是能达到很好的性能。 2 前向纠错( f e c ) ： 发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能 自动纠正传输中的错误。这种错误控制方式不需要反馈信道，实时性好，但是 随着纠错能力的提高，编译码设备复杂。q rc o d e 译码设备属于前向纠错译码 设备，能自动检测错误并纠正产生的错误。 3 混合方式： 结合前向纠错和a r q 的系统，在纠错能力范围内能自动纠正错误，超出纠 错范围则要求发送端重新发送。它是一种折中的方案。 2 1 3 纠错码的分类 译码器能自动发现错误的是检错码，不仅能发现错误而且能自动纠正错误 的是纠错码，还能纠正删除错误的是纠删码。 1 按信息元处理方法的不同，分为分组码和卷积码两大类 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码器把 这段k 个信息元按一定规则产生r 个校验元，输出长为n = k + r 的一个码组。因此 每个码组的校验元与本组的信息元有关，而与别组无关。分组码用( 玛k ) 表示，1 3 表示码长，k 表示信息位。卷积码是把信源输出的信息序列，以k 个码元分为一 段，通过编码器输出长为n 的码段。在任何一段规定时间内产生的n 个码元不 仅取决于这段时间中的k 个信息元，而且还取决于前n 1 段规定时间内的信息 元。这时，监督码元监督着这n 段时间内的信息。这n 段时间内的码元数目n n 称为卷积码的约束长度。一般情况下，一个仳l ( ，m ) 卷积码编码器有1 1 1 个移位寄 存器，每输入一组k 个信息元，则输出n 个码元。此时n = m + l ，约束长度为n n 。 1 4 第2 章纠删纠错理论基础 2 根据校验元与信息元之间的关系分为线性码与非线性码。 若校验元与信息元之间的关系是线性关系，则称为线性码；否则，称为非 线性码。此外，按照纠正错误的类型可以分为纠正随机错误的码、纠正突发错 误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码。 按照每个码元取值来分，可分为二进制码与q 进制码。按照对每个信息元保护 能力是否相等可分为等保护纠错码与不等保护纠错码，按照码字的结构特点又 可分为循环码与非循环码。线性分组码理论和循环码理论是q rc o d e 纠错译码 的理论基础。 2 1 4 信道错误和错误图样 1 随机错误：错误的出现是随机的，一般而言错误出现的位置是随机分布 的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机 信道。 2 突发错误：错误的出现是一连串出现的。这种情况如移动通信中信号在 某一段时间内发生衰落道称之为突发信道，造成一串错误，光盘上的一条划痕 等等。发生突发错误的信道称之为突发信道。 3 混合错误：既有突发错误又有随机错误的情况，发生混合错误的信道称 之为混合信道。 由于各种干扰所造成的错误，往往不是单个地而是成群成串地出现的，也 就是一个错误的出现，往往引起其前后码元的错误，表现为错误的相关性，产 生这种错误的信道称有记忆的信道或突发信道。但由于实际信道干扰的复杂性， 所引起的错误往往不是单纯的一种，而是两种错误并存的信道，称为组合信道 或复合信道。 设n 个码元长的序列c ：( o n - l ，t - , n - 2 ，c l ，c o ) ，通过信道传输到达接受端( 纠错 码译码器输入端) 的序列为r ：( r e - l ，r n - 2 ，r l ，t o ) ，由于信道中存在干扰，r 序列 中的某些码元可能与c 序列中对应的值不同，也就是产生了错误。设错误图样 e ( x ) 含有v 个错误，分别位于x 1 , x 2 x v ，则： e ( z ) = e l x l + e 2 x , 2 + + e v x ( 2 4 ) e t - - e ，表示各个位置上错误值与正确值的差值，即错误幅值，e a = c m + r n 。 1 5 第2 章纠删纠错理论基础 2 2 线性分组码 线性分组码是分组码中最重要的一类码，它是讨论各类码的基础，也是条 码纠错的理论基础。特别是有关码的生成矩阵g 和校验矩阵h 的表示，以及它 们之间的关系，而h 与纠错能力之间的关系更为重要。一个【n ，k 】线性分组码， 是把信息划分成k 个码元为一段( 称为信息组) ，通过编码器变成长为n 个码元 的一组，作为【n 闽线性分组码的一个码字。若每位码元的取值有q 种( q 为素数 幂) ，则共有q k 个码字，n 长的数组共有q n 组。【n 闷线性分组码是g f ( q ) 上的n 维线性空间v n 中的一个k 维子空间。由于该线性子空间在加法运算下构成 阿贝尔群，所以线性分组码又称为群码。 2 2 1 码的校验矩阵和生成矩阵 n 维线性空间v n 中，如何找出满足一定要求的，有2 k 个矢量组成的k 维线 性子空间v i 吐。这相当于建立一组线性方程组，已知k 个系数，要求n - k 个未知 数，使得到的码恰好有所要求的最小距离d 。一般情况下，任何一个 n l ( ，d 】码的 h 矩阵可表示为： h = 啊扩j l l 扩： ，hj j l 2 ，柚 吨一吃吨。- 2 ( 2 5 ) 它是一个( n k ) x n 阶矩阵。由此h 矩阵可以很快地建立码的线性方程组： j l i ，。 | 1 1 2 ，。 吃一b l 巳一i 巳一2 ： c o ：0 r( 2 6 ) 由于【n ，k ，d 】码的每一码字必须满足式( 2 6 ) ，即它的每一码字必然在由h 矩 阵的行所张成的v 毗空间中的零空间中，那么v 呲的零空间必然是一个k 维 子空间v n k ，而这正是【n ，k ，d 】码的码字集合全体。所以，h 矩阵的每一行与它的 码的每一码字的内积均为0 ，即 n ，k ，d 】的每一码字与v i u a 正交。【玛l ( ，d