（控制科学与工程专业论文）快速响应矩阵码识别研究及其在车站自动售票系统中的应用.pdf

硕l j 学位论文 摘要 随着社会信息化的进程，条码技术，尤其是二维条码技术得到了蓬勃的发展 和广泛的应用。针对中国的铁路客运中存在的购票的问题，提出采用二维条码识 别技术构建移动支付业务模式的车站自动售票系统，以降低出行旅客购票时间， 提高车站售票效率，降低铁路部门的运营成本。 本文首先从纠错控制编码理论着手，介绍了常用的几种纠错控制编码，深入 分析了r s 纠错编码理论和q r 码的编码方法，为q r 码的自动识别技术研究奠定 了基础，并给出了q r 码软件编码流程。 在q r 码的识别中，重点介绍了图像预处理算法和条码图像定位提取算法。 图像预处理算法包括中值滤波、二值化、二值图像去噪，在图像二值化部分提出 过模糊图像阈值选取方法，为每一个像素点选择一个合适的阈值，从而避免了光 照不均匀对图像二值化造成的影响，并采用形态学运算对二值图像进行去噪处理， 为图像的定位提取扫清了障碍。在图像的定位提取算法中分析了前人的识别算法， 针对他人算法对摄像头拍摄的模糊q r 码定位提取成功率低的缺点，提出了基于 轮廓特征查找的寻像图形定位算法，然后根据寻像图形的位置，采用直线扫描算 法寻找条码符号边界，找到边界后利用图像坐标变换算法将符号变换到水平方向， 得到标准条码符号，最后根据q r 码的编码方法进行逆运算，而得到符号中所蕴 含的信息。经过实验验证该方法对摄像头拍摄的模糊条码图像有很好的识别效果， 具有较高的识别率。 然后介绍了基于二维条码识别技术的车站自动售票系统的工作原理，并详细 的介绍了车票自助打印终端的硬件设计的全过程和关键软件设计方法，最后给出 采用该终端打印的车票票样。 最后，该算法在车站售票终端中得到了成功应用，此技术具有很大的应用前 景，值得进一步进行推广。 关键字：快速响应矩阵码；识别；差错控制编码：轮廓特征；嵌入式系统 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o np r o c e s s ，b a r c o d e ，e s p e c i a l l y2 - db a r c o d e t e c h n o l o g yh a sb e e nq u i c k l yd e v e l o p e da n dw i d e l ya p p l i e d c o n s i d e r i n gt h ep r o b l e m s e x i s ti nt h et i c k e t ss e l l i n ga tt h er a i l w a ys t a t i o n ，ar a i l w a ya u t o m a t i ct i c k e t ss e l l i n g s y s t e mb a s e do n2 - db a r c o d er e c o g n i t i o nt e c h n o l o g ya n dm o b i l ep a y m e n ts e r v i c ei s p r o p o s e d ，w h i c hc a nr e d u c et h et i m et h a tp a s s e n g e r ss p e n d0 nt i c k e t sb u y i n g ，p r o m o t e t h ee f f i c i e n c yo ft i c k e t ss e l l i n ga n dd e c r e a s et h er a i l w a yo p e r a t i n gc o s t s f i r s t l y , s t a r t i n gw i t ht h ee r r o rc o n t r o lc o d i n gt h e o r y ，s o m ek i n d so fc o m m o nu s e d e r r o rc o n t r o lc o d e sa r ei n t r o d u c e di nt h i sp a p e r d e e p l ya n a l y z i n gr sc o d ec o d i n ga n d d e c o d i n gt h e o r ya n dq r c o d ec o d i n gt h e o r y , as t r o n gb a s i sf o rq rc o d er e c o g n i t i o ni s e s t a b l i s h e d ，a n dt h e nas o f t w a r ef l o wo fq rc o d ec o d i n gi sg i v e n s e c o n d l y ，i nq rc o d er e c o g n i t i o n ，t h ei m a g ep r e p r o c e s s i n ga n db a r c o d es y m b o l l o c a t i n ga n de x t r a c t i n ga r em a i n l yp r e s e n t e d t h ei m a g ep r e p r o c e s s i n ga l g o r i t h m c o n s i s t so fm e d i a nf i l t e r i n g ，b i n a r i z a t i o n ，b i n a r yi m a g ed e n o i s i n g at h r e s h o l dv a l u e s e l e c tm e t h o db a s e do nt h ed e e pb l u r r e di m a g ei sp r o p o s e d ，a n das u i t a b l et h r e s h o l d f o re v e r yp i x e li sc h o s e nt oa v o i dt h ee f f e c tw h i c hc a u s e db yt h eu n e v e nl i g h tt ot h e i m a g eb i n a r i z a t i o n ，m o r p h o l o g i c a lo p e r a t i o ni sa p p l i e dt oe l i m i n a t en o i s ew h i c hc a n c l e a nt h eo b s t a c l ei nt h es y m b o ll o c a t i o n a c c o r d i n gt ot h ep r e v i o u sr e s e a r c hw h i c h h a sl o ws u c c e s sr a t i oo nt h eq rc o d es y m b o ll o c a t i o na n de x t r a c t i o nf r o mt h ef u z z y i m a g et a k e nb yc a m e r a ，t h ef i n d e rp a t t e r nl o c a t i o na l g o r i t h mb a s e do nt h ec o n t o u r s e a r c h i n gi sp r e s e n t e d ，t h e na c c o r d i n gt ot h ef i n d e rp a t t e r nl o c a t i o n ，l i n es c a n n i n g a l g o r i t h mi sa d o p t e dt of i n db o u n d a r yo ft h ec o d es y m b o l ，t h e nt h es y m b o li s t r a n s f o r m e dt o h o r i z o n ，a n dt h e nt h es t a n d a r dc o d es y m b o li so b t a i n e d t h e i n f o r m a t i o ni m p l i c a t e di nt h i ss y m b o li so b t a i n e db yi n v e r s eo p e r a t i o no fq rc o d e c o d i n g t h ee x p e r i m e n t si n d i c a t et h a t ：t h i sm e t h o dh a sb e t t e rr e c o g n i t i o np e r f o r m a n c e a n dh i g h e rr e c o g n i t i o nr a t i oo nf u z z yq rc o d ei m a g et a k e nb yc a m e r a t h i r d l y , t h eo p e r a t i o np r i n c i p l eo ft h er a i l w a ya u t o m a t i ct i c k e t ss e l l i n gs y s t e m b a s e do nt h e2 - db a r c o d er e c o g n i t i o nt e c h n o l o g yi se x p l a i n e d ，a n dh a r d w a r ed e s i g n p r o c e s sa n dk e ys o f t w a r ed e s i g nm e t h o do ft h et e r m i n a la r ed e s c r i b e di nd e t a i l a n d t h e nt h es a m p l et i c k e tp r i n t e db yt h et e r m i n a li ss h o w n a tl a s t ，t h ea l g o r i t h mh a sb e e ns u c c e s s f u l l ya p p l i e di nt h er a i l w a ya u t o m a t i c t i c k e t ss e l l i n gt e r m i n a l t h et e c h n i q u eh a sg o o d a p p l i c a t i o np r o s p e c t ，i sw o r t h t l p o p u l a r i z i n g 硕i j 学位论文 k e y w o r d ：q rc o d e ；r e c o g n i t i o n ；e r r o r c o n t r o l c o d i n g ；c o n t o u rf e a t u r e ； e m b e d d e ds y s t e m i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：幸唬伟 日期：砂严 月7 弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：秒鸯弗 聊签名：嚅玩 日期：唧年4 - 月谚日 日期：卿古月侈e l 硕f ：学位论文 第1 章绪论 1 1 课题研究背景及意义 自动识别技术是以计算机技术和通信技术的发展为基础的一种多学科综合性 的科学技术。自动识别技术自诞生以来在全球范围内得到了迅猛的发展，形成了 包括条码技术、射频技术、生物识别、磁卡及智能卡识别、光学字符识别、视觉 识别、语音识别、图像识别等集计算机、光、电、通信技术为一体的高新技术学 科e l3 。 条码技术是其中最为成熟、应用领域最广泛的一种自动识别技术。条码技术 产生于2 0 世纪4 0 年代，最初为一维条码，由于其可靠准确、数据输入速度快、 灵活实用等优点，被广泛应用在商场、海关、金融、邮政等领域。但是由于受到 信息容量的限制，一维条码仅仅能标识商品，而不能够描述商品，因此需要依赖 电脑网络和后台数据库而存在，大大制约了其应用领域。二维条码正是为了解决 一维条码无法解决的问题而诞生的，它具有高密度、大容量、纠错能力强的特点， 拓宽了条码的应用领域。目前二维条码已经被应用在移动支付、会员管理、汽 车配件跟踪、仓储管理、工业生产、交通运输、医疗卫生等领域【2 q j 。 在我国二维条码主要应用在大型连锁机构的会员管理、大型超市的仓储管理 和移动支付上。一些地区的景点和电影院采用移动支付业务来发售电子门票，其 业务模式为：用户登陆电子门票发售的网站，选择自己需要的门票，确认后，包 含门票信息的二维条码会被下载到用户的手机中，同时移动运营商从用户手机话 费中代扣购票费用；用户持手机到景点或电影院门口的电子检票终端上扫描二维 条码，识别出其中包含的门票信息，用户便可以顺利进入景点或电影院。这既可 以节省用户购票的时间，也可以减少商家售票和检票的人员浪费，是一种非常值 得推广的业务模式。 中国是一个人口大国，乘火车出行的旅客众多，在客流高峰期，日发送旅客 接近5 0 0 万人次。目前的售票模式不但在人力上是一种浪费，由于购票人员高度 聚集，也给社会治安埋下了严重的安全隐患。本文深入分析了快速响应矩阵码的 编码和识别方法，提出了建立移动支付业务模式的火车站自动售票系统。该系统 以二维条码为载体，通过数字图像处理技术、嵌入式技术和移动支付业务的结合， 将繁杂的购票流程简化为轻轻触动手机按键和条码扫描，既减少了旅客购票所需 的时间，又有效的杜绝了假票泛滥现象，不仅可以减少人力资源的浪费，消除安 全隐患，对国家的经济建设也具有非常积极的意义。 l 快速响j 帑矩阵码识别研究及其在车站自动售票系统中的应用 1 2 国内外二维条码研究现状 1 2 1 国外二维条码研究概况 国外对二维条码技术的研究始于2 0 世纪8 0 年代末。在二维条码符号表示技 术研究方面，已研制出多种码制，常见的有p d f 4 l7 ，d a t am a t r i x ，q rc o d e ，c o d e 4 9 ，c o d e16 k ，c o d eo n e 等。这些二维条码的密度都比传统的一维条码有了较大 的提高，如美国s y m b o l 公司研制的p d f 4 1 7 行排式二维条码，它的信息密度是一 维条码c o d e3 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 等码制的符号标准。新成立的国际标准化组织国际电 工委员会第l 联合委员会的第31 分委员会，即条码自动识别技术委员会 ( i s o i e c j t c i s c 3 1 ) 。已制定了q rc o d e 的国际标准( i s o i e c1 8 0 0 4 ：2 0 0 0 自动识别与数据采集技术条码符号技术规范q r 码) ，以及p d f 4 1 7 ， d a t am a t r i x ，m a x ic o d e 等二维条码的i s o i e c 标准。 在二维条码设备开发研制、生产方面，美国、日本等国的设备制造商生产的 识读设备、符号生成设备，已广泛应用于各类二维条码应用系统。美国s y m b o l ( 讯 宝) 公司是世界上最大的条码阅读设备制造商之一，其带光栅的激光阅读器和光电 扫描技术及译码技术一直领导着世界的潮流，最近它也着手开发具新概念的图像 阅读( i m a g er e a d e r ) 技术。美国韦林( w e l c h a l l y n ) 公司也是主要的二维条码阅读设 备制造商之一，其c c d 技术、图像式阅读器( i m a g er e a d e r ) 技术以及译码技术处 于世界领先地位，最近它又提出了线性图像( l i n e a ri m a g i n g ) 技术的新概念，其主 要产品包括i t 3 8 0 0 和i t 4 4 0 0 两大系列b3 。 在二维条码应用方面，美国、德国、日本、墨西哥、埃及、哥伦比亚、巴西、 新加坡、菲律宾、南非、加拿大等国，不仅已将二维条码技术应用于公安、外交、 军事等部门对各类证件的管理，而且也将二维条码应用于海关、税务等部门对各 类报表和票据的管理，商业、交通运输等部门对商品及货物运输的管理，邮政部 门对邮政包裹的管理，工业生产领域对工业生产线的自动化管理。 1 2 2 国内二维条码研究概况 我国对二维条码技术的研究开始于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 e o n e 的技术规范进行了翻译和跟踪研究。中国物品编码中心在原国家质量技术监 督局和国家有关部门的大力支持下，对二维要码技术的研究不断深入。在消化国 外相关技术资料的基础上，制定了两个二维条码的国家标准：g b t1 7 1 7 2 1 9 9 7 2 硕十学位论文 四一七条码，g b t1 8 2 8 4 2 0 0 0 快速响应矩阵码。同时国内的一些企业也相 继提出了自主研发的二维条码，如深圳矽感科技的c m 紧密矩阵码( c o m p a c t m a t r i xc o d e ) 、g m 网格矩阵码( g r i dm a t r i xc o d e ) ，上海龙贝科技的“龙贝码”， 由中国物品编码中心和北京网路畅想科技发展有限公司合作开发的汉信码。它们 的多项指标技术超过了国际上现有的码制，整体上达到了国际先进水平。 在二维条码设备的研发方面，国内越来越多的公司开始自助研发生产，目前 福建新大陆自动识别技术有限公司研发了针对多种二维码制的识别设备，其识别 速度和识别率均已达到世界先进水平，产品已经远销韩国、日本、美国和欧洲各 国。 二维条码技术已在我国的汽车行业自动化生产线、医疗急救服务卡、涉外专 利案件收费、珠宝玉石饰品管理及银行汇票上得到了应用；1 9 9 9 年3 月在北京举 行的全国人大第九届三次全体会议和全国政协第九届三次会议期间，在随行人员 证件、记者证、旁听证上成功地应用了二维条码技术，引起了与会代表和新闻界 的极大关注；我国香港特别行政区已经将二维条码应用在了特别行政区的护照上 1 。二维条码在我国有着广阔的应用前景，二维条码技术在我国的推广应用必将 推动我国信息产业的快速发展，带动国民经济建设。 随着我国市场经济的不断完善和信息技术的迅速发展，国内对二维条码这一 新技术的需求也会与日俱增。 1 3 快速响应矩阵码简介 快速响应矩阵码( q u i c kr e s p o n s ec o d e ) ，又叫做q r 码，是由日本d e n s o 公 司于1 9 9 4 年9 月研制的一种矩阵式二维条码。q r 码除了具有其它二维条码的信 息容量大、可靠性高、可表示汉字及图像多种文字信息、保密防伪性好等优点外 还具有如下的特点 ： ( 1 ) 超高速识读，当表示相同信息时，其识读速度是d a t am a t r i x 码的1 0 1 5 倍， 是p d f 4 17 码的1 0 倍左右。 ( 2 ) 全方位识读，q r 码具有全方位( 3 6 0 。) 识读的特点，这是它优于行排式二 维条码的另一主要特点。 ( 3 ) 能够有效表示中国汉字和日本汉字，q r 码以特定的数据压缩模式表示中国汉 字和日本汉字，它以1 3 b i t 压缩方式表示汉字，比其他二维条码表示汉字的效 率提高了2 0 ，该特点是q r 码在中国具有良好的应用前景的主要因素之一。 q r 码符号是有深浅正方形模块堆叠而成的正方形矩阵码。它由编码区域和 由包括寻像图形、定位图形、分隔符和校正图形在内的功能图形组成，其四周为 空白区所包围。其中功能图形和空白区中不包含编码数据信息。图1 1 为q r 码 版本7 的符号结构。 3 快速响应矩阵码识别研究及j 在车站自动售票系统中的应用 q r 码符号共有4 0 种规格，分别为版本1 、版本2 、版本4 0 。版本1 的规格为2 1 模块2 1 模块，版本2 为2 5 模块x2 5 模块，以后每一版本符号比前 一版本每边增加4 个模块，以此类推，直到版本4 0 ，规格为1 7 7 模块1 7 7 模块。 版本l 没有校正图形，版本1 - 6 没有版本信息。 q r 码符号有很强的纠错能力，它具有四个纠错等级，最多可以纠正3 0 的 数据码字错误。同时q r 码可以对多种字符进行编码，如数字型数据、字母数据、 八位字节数据( 八位a s c i i 码表) 、中国汉字字符、日本汉字字符以及缺省字符 集以外的其他字符集( 如阿拉伯字符集、古斯拉夫字符集、希腊字母等) 。 同r 黝= 瞿嗣i 伯 鏊三导弋一 、 、 萋自古、，剥 煎 符 号 图1 1q r 码符号结构 与其它二维条码相比，q r 码具有突出的优点，它比其他二维条码具有更高的编 码效率和更快的识读速度。图1 1 是q r 码与p d f 4 1 7 码、d a t am a t r i x 码的编码 比较，其编码信息均为“这是一个编码效率测试”，模块像素为4 4 。很明显 p d f 4 17 码占用的空间面积远远大于q r 码和d a t am a t r i x 码。虽然d a t am a t r i x 码 的占用空间面积小于q r 码，但q r 码对中文信息的采用压缩编码方式，随着编 码信息的增多，q r 码的编码效率要远远高于d a t am a t r i x 码。而且由于q r 码具 有超高的识读速度，因此其在移动支付业务中具有比p d f 4 1 7 码和d a t am a t r i x 更 大的应用价值。 目前q r 码已经在韩国和日本得到了广泛的应用，在我国，由于2 0 0 5 年中国 移动与北京意锐新创在q r 码研发与应用上达成的战略合作伙伴关系后也将有较 大的发展。 4 硕十学位论文 ( b ) d a t am a t r i x ( a ) p d f 4 1 7 图1 2 几种二维条码的符号示例 ( c ) q rc o d e 1 4q r 码识别算法及应用研究现状 长期以来q r 码的识别设备都只有国内外少数几家公司可以生产，而且设备 价格昂贵，其识别算法也被这些公司所垄断。目前昂贵的识别设备成为q r 码被 进一步应用的商业壁垒，因此q r 码的识别成为近年来研究的一个热点。其中研 究的内容主要包括图像预处理算法和符号定位提取算法两个研究方向。 在图像预处理方面，文献 2 和 6 分别针对不同对比度的图像提出基于 灰度直方图的多级阈值化方法，对图像灰度直方图不成双峰状的图像进行了比较 好的二值化。文献 7 提出采用形态学腐蚀膨胀的运算对二值q r 码图像进行去 噪的方法，对有噪声的二值图像有较好的去噪效果。 在条码符号定位提取方面，文献 8 提出一维特征模板匹配的寻像图形定位 方法，并采用h o u g h 变换得到图像的边界，一维特征模板匹配法对于拍摄比较清 晰的图像有较好的定位效果。文献 9 提出采用轮廓查找算法定位符号四个顶点， 利用二次反透视变换结合双切线逼近的方法复原图像，对于散焦模糊图像产生比 较好的复原效果。文献 1 0 提出采用多直线扫描法取得符号顶点，利用多阶线 段逼近法取得弯曲条码的边界，对于边界变形的条码符号有很好的提取效果。文 献 1 1 提出用c a n n y 边缘检测算法结合轮廓查找算法进行寻像图形定位的算法， 并采用反透视变换取得符号四个顶点，对于边界未变形的条码图像有较好的提取 5 快速响应矩阵码识别研究及j - i t i 车站自动售票系统中的应用 效果。 以上算法均是针对印制在纸张上的q r 码图像进行的，而实际的应用中很多 时候需要识别设备直接识别手机屏幕上的q r 码图像，由于手机屏幕一般分辨率 不高，而且其具有自发光的特点会使深浅模块的比例严重失调，而使得以上大部 分算法不能够达到理想效果，甚至不能够提取到条码图像。而对于文献e 9 3 和 1 1 提出的轮廓查找具有比较强的鲁棒性，本文汲取以上算法的优点，提出了改进的 图像预处理算法和图像定位提取算法，能够很好的识别利用普通摄像头从手机屏 幕获取的q r 码图像，大大提高了该算法的实用价值。 在q r 码的应用方面，文献 4 设计了基于b l a c k f i n 5 3 3 的便携式q r 码识 别设备，该设备将自动识别技术与z i g b e e 无线传感器网络技术结合，可以应用在 分布式数据采集系统中，具有很强的实用性；文献 1 2 设计了基于摄像手机的 q r 码识别系统，由于摄像手机的大量普及，具有很强的通用性。目前的研究基 本都是针对印制q r 码和短距离通信技术，其应用具有一定的局限性。本文汲取 以上设计的优点，提出基于q r 码识别的车站自动售票系统，将q r 码识别技术 与嵌入式技术和远距离无线通信技术相结合，大大提高了系统的地域适应性，并 且具有较强的专业性和应用价值。 1 5 本文研究的主要内容 本文主要是针对目前已具有国家标准的q r 码的研究，重点研究了其编码技 术与符号定位识别技术，最后将识别算法应用于嵌入式设备中。在q r 码编码分 析中，深入的分析了q r 码的编码算法和r s 纠错编码算法的编码译码原理。在 研究他人识别算法的基础上，提出了基于轮廓查找和直线扫描的q r 码定位与提 取算法，在符号版本的判断上采用模块数计算与版本信息校验两者结合的方法进 行版本的确认，避免了高版本图像因版本的错误判断，而导致图像无法识别；然 后根据q r 码的译码算法进行译码，得到编码数据信息。设计了基于条码识别的 车票自助打印系统，并在嵌入式处理器中实现了条码识别算法。最后对该方法的 进一步应用进行了展望。文章共有五个部分： 第一章，对国内外二维条码技术的发展应用进行了简要介绍，对条码识别中 涉及的图像处理技术和嵌入式技术进行了概述，提出了文章研究的目的和意义， 最后介绍了文章的总体结构和章节安排。 第二章，主要介绍了q r 码的编码方法和纠错编码理论，以及q r 码编码的 软件实现。纠错码中对q r 码编码中用到的r s 码进行了详细的阐述，分析了其 编解码原理，最后给出了q r 码编码的系统流程图。 第三章，在分析摄像头拍摄的q r 码的特点的基础上，结合前人的识别算法， 提出了基于轮廓特征的q r 码定位提取算法，然后介绍了各部分详细的算法，以 6 硕上学位论文 及图像识别流程，最后对算法进行实验验证，并对实验结果进行了分析。 第四章，针对目前我国铁路售票中存在的问题，提出了基于二维条码识别的 列车自动售票系统，叙述了系统的运行原理和自助车票打印终端的硬件和软件设 计的全过程。 第五章，对文章所做的工作进行了总结，并就这一技术的发展应用前景进行 了进一步的展望。 7 快速响心矩阵码识别研究及其行：车站自动售票系统中的心用 第2 章q r 码编码理论 2 1 差错控制编码理论 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编 码是为了提高数字信号的有效性，使模拟信号数字化而采取的编码。信道编码是 为了降低误码率，提高数字通信的可靠性而采取的编码e 1 3 。 数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系 统的抗干扰性能，可以采用信道编码技术，即差错控制编码技术。 2 1 1 差错控制编码基本原理 差错控制编码的原理是：发送方对准备传输的数据进行抗干扰编码，即按照 某种算法附加上一定的冗余位，构成一个码字后再发送。接收方收到数据后进行 校验，即检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错 发生。差错控制编码分为检错码和纠错码两种1 如，检错码是能自动发现差错的编 码，纠错码是不仅能发现差错而且能自动纠正差错的编码。 2 1 2 几种常用的差错控制编码 r s 差错控制编码是多进制b c h 码，而b c h 码是循环码的一种，循环码又是 分组码的一种特殊形式，所以在此分别对分组码、循环码、b c h 码和r s 码逐个 作一介绍。 2 1 2 1 分组码 分组码编码器是把信源输出的信息序列，按k 个相继码元分为一组( 信息组) ， 并按一定规则对每一信息末增加，= 以一k 个校验元，组成长为，2 的行重码字。在二 进制情况下，长为k 的信息组共有2 种组合，通过编码器后，相应的码字也有2 个， 称这2 码字集合为( 力，七) 分组码。 线性分组码中的一个重要参数是码率r = k n ，它说明在一个码字中信息位所 占的比重。r 越大，说明信息位占的比重越大，码的传输信息的有效性越高。 2 1 2 2 循环码 循环码是线性分组码中最重要的一个子类，它的结构完全建立在有限域的基 础上，具有以下两个特点：一是码的编码电路及伴随式计算电路简单，易于实现； 二是循环码的代数结构具有很多有用的性质，易于找到有效的译码方法。循环码 r 硕十学位论文 中最重要的二类码是b c h 码和r s 码。 2 1 2 3b c h 码 b c h 码是一类重要而有效的纠正多个随机错误的差错控制编码。它是1 9 5 9 年由霍昆格姆( h o c q u e n g h e m ) ，1 9 6 0 年由博斯( b o s e ) 和查德胡里( c h a n d h a r i ) 各自提出的纠正多个随机错误的循环码，它具有很好的纠错性能，构造容易，在 实际中得到广泛应用。b c h 码译码算法的研究一直是编码理论的重要课题之一， 迄今为止已有许多学者提出了不同的算法。1 9 6 0 年彼得逊( p e t e r s o n ) 奠定了二 进制b c h 码译码的理论基础。1 9 6 5 年福尼( f o r n e y ) 解决了b c h 码的纠错纠删 码。 1 9 6 6 年伯利坎普( b e r l e k a m p ) 提出了迭代译码算法，节省了计算量，加快 了译码速度，因而从实际上解决了b c h 码的译码问题，1 9 6 9 年m a s s e y 发现了该 方法与最短线性移位寄存器之间的关系，从而进一步简化了算法 14 。自此以后， 很多学者又不断提出了新的译码方法。 2 1 2 4r e e d s o l o m o n 码 r s 码是一种特殊形式的循环码，它由i r v i n gr e e d 和g u s t a v es o l o m o n 于1 9 6 0 年构造的，是多元b c h 码的一种，简称为r s 码( r e e d s o l o m o n 码) 。r s 码基于 有限域理论，特别是形如g f ( q ”) 的有限域( q 为质数，聊为正整数) 。在发送端发 送信息之前，纠错编码器根据要发送的数据信息计算相应的纠错信息，并把纠错 信息作为冗余校验和数据信息一起组成纠错码。接收端收到这些码后，通过纠错 编码器不仅能自动地发现错误，而且能自动地纠正码字在传输过程中的错误，这 种差错控制的系统属于前向纠错系统。待编码的数据以k 个信息码元作为一段， 编码器把这七个信息位按照r e e d s o l o m o n 算法产生厂个校验元，输出长为刀= 七+ ， 的码字。r s 码不但可以纠正随机错误、突发错误以及二者的组合，而且可以 用来构造其它码类。r s 码以其纠错能力强、编码效率高、构造方便、算法相对简 单，以及在数字系统中易于实现等优点，逐步成为当前最有效、应用最为广泛的 差错控制编码之一，也是二维条码普遍采用的一种纠错码。 2 1 3 r s 纠错码与q r 码 q r 码的码字序列由数据码字和纠错码字组成，数据码字在前，纠错码字在 后。纠错码字是数据码字多项式被纠错码多项式【1 5 j 6 1 9 ( x ) 除得的余数。余数的最 高次项系数为第一个纠错码字，最低次项系数为最后一个纠错码字，也是整个块 的最后一个码字。 数据码字为数据码字多项式各项的系数，第一个数据码字为最高次项的系数， 第一个纠错码字前的最后一个数据码字是最低次项的系数。 9 快速响心矩阵码识别研究及其以：车站自动售票系统中的应用 c ( x ) = x n - k m ( x ) + ，( x )( 2 1 ) 式中c ( x ) 是所要求的码字序列多项式，即编码的最终序列。m ( x ) 是数据码字多项 式。，( x ) 是川( x ) 除以g ( x ) 所得的余式，也就是纠错码字多项式3 。 2 1 3 1r s 码编码原理 设a 为g f ( q ) 中的一个本原元，则能纠正f 个错误的本原r s 码的生成多项式 为： g ( x ) = ( x a ) ( x - a 2 ) ( x a 2 ) = g o + g l x + + 9 2 卜l x 2 卜1 + x 2 ( 2 2 ) 式( 2 2 ) 中蜀o = o ，1 ，2 2 t - 1 ) 是g f ( q ) 域中的元素，a 为g f ( q ) 域中的本原元。若原 始信息多项式为： d ( x ) = d o + d l x + 畋x 2 + + 吃一l x ”1 ( 2 3 ) 则进行r s 编码后的多项式为： v ( x ) = x 2 d ( x ) + x 2 d ( x ) m o dg ( x ) ( 2 4 ) 其中x 2 t d ( x ) 的各次系数是原始数据码字部分，x 2 t d ( x ) m o d g ( x ) 的各次系数是纠错 码码字部分，编码时纠错码字跟在数据码字的后面。实际上，( 刀，k ，r ) r s 码是将k 位数据码元d ( x ) 转换成可以被g ( x ) 除尽的k + r 个码元多项式v o ) 川。 2 1 3 2r s 码译码原理 r s 码译码的实质就是对接收到的码字进行运算，确定原始数据码和纠错码是 否符合编码规则，并对传输中出现的据读错误或替代错误进行纠正。r s 码的译码 原理如下f i g ：先由接收到的信息计算出伴随式s ；然后采用b m 迭代算法求错误 位置多项式；再用钱氏搜索算法求取错误位置多项式的根；最后计算错误位置， 修正接收到的信息，完成译码。r s 码的译码步骤如下： 第一步、伴随式s 的定义及计算 假设原始传输码字表达式为d ( x ) ，表示为 d ( x ) = d o + 4 x + 畋z 2 + + 以一l x ”- 1 ( 2 5 ) 接收到的码字表表达式为，( x ) ，表示为 r ( x ) = r o + x + r 2 x 2 + + 一i x ” ( 2 6 ) 令p ( x ) 为错误多项式，表示为 e ( x ) = + 岛x + e 2 x 2 + + e n l x 护1 ( 2 7 ) 则有 ，( x ) = d ( x ) + e ( x )( 2 8 ) 对于可能包含错误的接收到的码字表达式，( x ) ，为接收码字，它可能还有错误。 由于d ( x ) 是不包含错误的原始传输码字表达式，用纠错码生成多项式g ( x ) 的各个 根口，( ，= l ，2 ，2 t ) 对，( x ) 求值，把其结果定义为校正子s ，。由于d ( 口，) = 0 ，可得： 1 0 硕l ：学位论文 q = ，( 哆) = d ( 吩) + p ( q ) = p ( 哆) ( 2 9 ) 若巴= o ，则接收码字无误，否则出错。假设，( 工) 中包含m 个错误( o sm f ) ，错 误发生在未知位置，之，上。于是差错多项式p ( 功可以写成： e ( x ) - e t t x _ f t + 气k + + 气屯 ( 2 1 0 ) 由式( 2 9 ) 和( 2 1 0 ) 可以导出以下方程组： 气( 口) 2 + p f _ ( 口) 2 ( 2 1 1 ) 对于1 m ，令，全口。和万，会e ，即两个分别表示错误位置和错误数值。则利 用上述屏和艿，的定义，式( 2 1 1 ) 可以简化为 ls = 磊届+ 岛压+ + 瓯尾 j 2 磊屏+ 磊历+ + 瓯历( 2 1 2 ) f ： 【岛，= 磊屏+ 岛屏+ + 瓯尾 第二步、采用b m 迭代算法3 计算错误位置多项式盯( 工) 错误位置多项式盯( x ) 定义为 o ( x ) = ( 1 - f l l x ) ( 1 一履x ) ( 1 一尾x ) = o - o + q x + + x 魔 ( 2 1 3 ) 其中o - 0 = l 。错误位置数就是仃( x ) 的根的倒数，即( 1 f 朋) 。由式( 2 12 ) 和( 2 1 3 ) p i 可以得到如下方程组： i & + l + q 瓯+ c r s l = 0 s r a + 2 + q 氏+ l + 最( 2 1 4 ) i ： 【蔓，+ q 是f - l + 是卜。= 0 找到满足上式( 2 1 4 ) 的最低次数的仃( x ) ，就可以得到错误位置和错误数值。 决定译码复杂性和速度的主要因素在于求错误位置多项式仃( z ) ，如何简化和加快 这一步骤是译码的关键。1 9 6 6 年伯利坎普( b e r l e k a m p ) 提出了可以有伴随式计 算错误位置多项式的迭代译码算法，这极大地加快了求解错误位置多项式的速度， 该方法简单易于实现，从工程上解决了r s 译码问题；1 9 6 9 年梅西( m a s s e y ) 指 出了该算法与序列的最短线性移位寄存器综合之间的关系，并进行了简化，因此， 此译码算法就称为b m 迭代译码算法。 令c o ( x ) = l + c o _ i x + c o z x 2 + 表示s ( x ) 与仃( 工) 的乘积，经过简单推导，可得到校 口 一 卜 叩 一 岛 z 驴 他 矿 心 托 气： 产 屺咿 孵 幽 和 印纠 刮 一 一一 r-_-_-_j-_-。-_-_-_-_l，s 是；逆 快速响心矩阵码识别研究及j e 柏! 下站自动售票系统中的应用 正子s ( x ) 、错误位置多项式c r ( x ) 和o j ( x ) 之间的关系，由于次数大于一的项的系数 均为0 ，则有 s ( x ) a ( x ) 暑w ( x ) m o d ( x 可+ 1 ) ( 2 15 ) b m 迭代的原理如下：先人为选定一个初值c r o ( x ) 和c o o ( x ) ，然后开始第一次 迭代得到a l ( x ) 和c o 。( x ) ，并用a o ( x ) 和( x ) 表示它们。这样依次进行，由q ( x ) 和 o - r ( x ) 求得啡+ ，( x ) 和缉+ 。( x ) ，也就是先计算满足式( 2 1 5 ) 的仃( 功和缈( x ) 的低次项， 然后通过迭代得到高次项，最后解出满足式( 2 1 5 ) 的a ( x ) 和缈( 功。 第三步、采用钱搜索算法，计算错误位置 如何求取错误位置多项式o - ( x ) 的根是一个比较复杂的问题，1 9 6 4 年钱闻天提 出了搜索错误位置的方法，从而无需直接求解错误位置多项式仃( x ) ，此方法被称 为钱氏搜索算法。该方法就是将有限域的所有元素2 0 ，2 1 ，2 ”1 从高位开 始依次代入仃( x ) ，进行校验，判断是否是根，这样校验、输出，总共校验以个根。 算法从判断最高位2 ”1 是否有错开始，将2 卜1 的倒数2 ( 卜i ) = 2 2 = 2 代入错误位置多 项式仃( x ) ，如果它使得仃( x ) = 0 ，则说明2 巾_ 1 是a ( x ) 的根，即接收码字多项式 r ( x ) - - r 一l x 剃+ 一2 矿一2 + + r l x + r o 中，：l l 有错，否则说明一l 无错2 1 2 2 1 。这样只需 要检测出刀个错误位置即可。 第四步、错误幅值的计算 假设错误位置个数为m ，差错位置分别为屈，屈，”，尾，差错幅值为e i ， e 2 ，气，由错误位置多项式可知： j l a ( x ) = ( 1 一p , x ) o 一屈砷( 1 一成力= q 一 ( 2 1 6 ) i = o 其中，= l ，定义如下函数： 啪) = 嚣 仃，( z ) 是去除了第j 个根后盯( x ) 的剩余式。根据式( 2 1 6 ) 和( 2 1 7 ) 可得： q ( x ) = 兀( 1 - f l , x ) = x 。 从而推导得到： t t n l m - i 盯( x ) = q ( x ) ( 1 一层x ) = q ，x 一q ，局x ”1 i = oi = o ( 2 1 7