（通信与信息系统专业论文）二维条码qr的纠错改进研究.pdf

摘要 二维条码与一维条码相比，它不需要依赖数据库，存储信息量大，可以表 达多种多媒体及文字信息，同时它还可以嵌入加密机制，具有纠错能力。快速 响应矩阵码( q r 码) 是一种矩阵二维条码，它能够全方位的识别和有效的表达 汉字，目前在我国有着广泛的应用。针对传统的q r 码的纠错能力有限，本文提 出了一种将纠错码l d p c 码替换r s 码运用到q r 图像中的方案，并利用图形预 处理技术对摄取到的有噪声和倾斜的图形进行处理，最后通过分割处理以及译 码流程对q r 码进行识别，从而得到我们想要的信息。目的是在采用纠错码l d p c 的编译码的基础上，提高q r 码的纠错能力，改进了q r 码的识别效果。在使用 方面由于纠错能力提高了，那么它的使用范围也就可以扩展了。 本文通过分析国内外的二维条码技术的发展现状，然后对q r 码的符号特征 以及编译码原理进行了研究，提出了一种新的q r 生成方案。通过对纠错码l d p c 码的编译码思想以及性能仿真进行研究，然后把它与r s 码进行仿真对比。同时 对生成的新的q r 码的图像预处理过程进行了详细的研究，包括图像的灰度化处 理、中值滤波、二值化处理、图形的分割等。对于新的q r 码，在生成的过程中 需要注意里面纠错码的构成，它的结构直接影响了最后q r 码的纠错能力。 通过理论研究之后，本文设计了q r 码的编译码处理的流程，并且进行了相 关的实验检测和分析。实验结果表明，新的q r 码的译码能力提高了，在污损程 度很大的时候也能够提取出正确的信息，相对于原来的q r 来讲，纠错能力提高 了，同时算法复杂度降低了。该技术不仅能够解决现有的二维条码q r 码所遇到 的问题，它还可以运用到其他的二维条码的系统中。 经过对本文的工作的总结，文中的创新工作有： 1 ) 提出了一种新的q r 码生成方案，把l d p c 码代替r s 码运用到q r 码中。 2 ) 针对采集到的q r 图像，采用了图像中值滤波和二值化处理，用新的纠 错码算法译码，把纠错能力从3 0 提高到5 0 。 3 ) 在不改变原来的q r 码的编解码机制的基础上，扩展了q r 码的应用， 降低算法复杂度。 关键字：q r 码，r s 码，l d p c 码，滤波，二值化 a b s t r a c t c o m p a r e dt w od i m e n s i o n a lb a r c o d ew i t ho n ed i m e n s i o n a lb a r c o d et h ef o r m e r d o e sn o tn e e dt or e l yo nd a t a b a s e ，a n di tc a l ls t o r el a r g ea m o u n to fi n f o r m a t i o na n d e x p r e s sav a r i e t yo fm u l t i m e d i aa n dt e x ti n f o r m a t i o n ，a tt h es a m et i m ei ta l s oc a i lb e e m b e d d e de n c r y p t i o ns y s t e m ，h a v i n ge r r o rc o r r e c t i o na b i l i t y q u i c kr e s p o n s em a t r i x c o d e s ( q rc o d e ) i sak i n do f m a t r i xt w od i m e n s i o n a lb a r c o d e ，i tc a t lb eaf u l lr a n g eo f r e c o g n i t i o na n de f f e c t i v e l ye x p r e s sc h i n e s ec h a r a c t e r s ，a tp r e s e n ti th a sb e e nw i d e l y a p p l i e di no u rc o u n t r y f o rt r a d i t i o n a lq rc o d et h ee r r o rc o r r e c t i o na b i l i t yi sl i m i t e d ， t h i sp a p e rp r o p o s e sas o l u t i o nt h a te r r o rc o r r e c t i n gc o d e sl d p cc o d e sw i l lr e p l a c er s c o d et ot h eq ri m a g e ，a n dg r a p h i c sp r e t r e a t m e n ti su s e dt od e a l 、航t l lo b t a i n e dn o i s e a n dt i l t e dg r a p h i c s ，f i n a l l yt h r o u g ht h es e g m e n t a t i o np r o c e s s i n ga n dd e c o d ep r o c e s s q r c o d ei si d e n t i f i e d ，s ot h ei n f o r m a t i o nw h a tw ew a n ti sg o t t e n t h ep u r p o s ei st h a t o nt h eb a s i so fe r r o r - c o r r e c t i n gc o d e sl d p ce n c o d i n ga n dd e c o d i n gq rc o d ee r r o r c o r r e c t i o na b i l i t yi si m p r o v e da n dt h eq rc o d er e c o g n i t i o ne f f e c ti sa l s ob e t t e r d u e t ot h ei m p r o v e de r r o rc o r r e c t i o na b i l i t y , t h eu s es c o p eo fq rc o d ei sa l s oc a l lb e e x t e n d e d t h r o u g ht h ea n a l y s i so ft h et w o - d i m e n s i o n a lb a r c o d et e c h n o l o g y sd e v e l o p m e n t s t a t u sa th o m ea n da b r o a d ，a n dt h e nt h eq rc o d es y m b o l sc h a r a c t e r i s t i c sa n d e n c o d i n ga n dd e c o d i n gp r i n c i p l e sa r es t u d i e d ，t h ep a p e rp u t sf o r w a r dak i n do fn e w q rg e n e r m i o ns c h e m e f i r s ti tg i v e sas t u d yo ft h ee r r o rc o r r e c t i o nc o d el d p cc o d e s e n c o d i n ga n dd e c o d i n gt h i n k i n ga n dp e r f o r m a n c es i m u l a t i o n , a n dt h e np u t si tw i t ht h e r sc o d es i m u l a t i o nc o n t r a s t a tt h es a m et i m ead e t a i l e ds t u d yi sc a r r i e df o rt h e g e n e r a t e dq rc o d ei m a g ep r e p r o c e s s i n g ，i n c l u d i n gi m a g eg r a y i n g ，m 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 , i m a g es e g m e n t a t i o na n ds oo n f o rn e wq rc o d ei nt h ep r o c e s so f g e n e r a t i o ne r r o r - c o r r e c t i n gc o d e sc o m p o s i t i o nn e e da t t e n t i o n , b e c a u s ei t ss t r u c t u r e d i r e c t l ya f f e c tt h ef i n a lq rc o d eo fe r r o rc o r r e c t i o na b i l i t y a f t e rt h e o r e t i c a ls t u d y , t h i sp a p e ri n t r o d u c e st h ed e s i g np r o c e s s i n go fq r e n c o d i n g a n dd e c o d i n g ，a n ds o m ee x p e r i m e n t a ld e t e c t i o na n da n a l y s i s 1 1 l e e x p e r i m e n t a lr e s u l t ss h o w t h a tt h en e wq rc o d ed e c o d i n ga b i l i t yh a sb e e ni m p r o v e d ， a n di tc a l le x t r a c tt h ec o r r e c ti n f o r m a t i o ni nt h el a r g ed e g r e ef o u l i n g ，w h e nc o m p a r e d i i t ot h eo r i g i n a lq rt h ee r r o rc o r r e c t i o na b i l i t yi si m p r o v e d ，a n dt h ec o m p l e x i t yo ft h e a l g o r i t h m i sr e d u c e d t h i st e c h n o l o g yc a l ln o t o n l ys o l v et h ee x i s t i n gt w o d i m e n s i o n a lb a r c o d eq rc o d ew i t hp r o b l e m ，i ta l s oc a nb ea p p l i e dt oo t h e rt w o d i m e n s i o n a lb a rc o d es y s t e m p a s sb yas u m m a r yo ft h ep r e s e n tw o r k , t h ei n n o v a t i o n si nt h et e x ta r ea s f o l l o w s ： 11an e wq rc o d eg e n e r a t i o ns c h e m ei sp r o p o s e dt h a tt h el d p cc o d e sa r e a p p l i e dt ot h eq r c o d ei n s t e a do ft h er sc o d e 2 ) f o rt h ec o l l e c t e dq ri m a g e ，t h ei m a g e sm e d i a nf i l t e ra n db i n a r yp r o c e s s i n g a r eu s e d ，a n d 谢mn e we r r o rd e c o d i n ga l g o r i t h mt h ee r r o rc o r r e c t i o na b i l i t yi s i n c r e a s e df r o m3 0 t o5 0 3 ) o nt h eb a s i so fn o tc h a n g i n gt h ec o d i n gs c h e m eo ft h eq rc o d e ，t h eq rc o d e a p p l i c a t i o ni se x t e n d e d a n dt h ec o m p l e x i t yo ft h ea l g o r i t h mi sr e d u c e d k e y w o r d s ：q rc o d e ，r sc o d e ，l d p cc o d e ，f i l t e r , b i n a r y i 武汉理工大学硕士学位论文 第1 章绪论 1 1 二维条码技术简介 在2 1 世纪，信息流在物流系统中占有很重要的地位，信息采集和处理过程 中需要用到a d c ( a u t o m a t i cd a t ac a p t u r e 自动化数据采集) 技术，而条码技术在 自动化数据采集中也占有很重要的地位。它是一门综合性技术，包括编码、印 刷、识别、数据采集和处理【l 】。一维条码只能在单一方向上装载信息，信息存储 容量小，而且还要与数据库连接才可以使用。继一维条码之后二维条码发展起 来，它有着较高的信息密度和较大的信息容量，同时可以不使用数据库。二维 条码可以编码数字、字符等信息，同时它还可以在条码里面嵌入图像信息，因 此二维条码在很多方面都有着广泛的应用，比如证件识别、人事管理、运输包 装、p o s 系统、电子数据交换【2 j 。更为重要的是二维条码可以引入加密机制，自 身还携带纠错码，所以它可以检测和纠正错误。二维条码的识别技术是其应用 的关键技术。 为了弥补一维条码的不足，产生了二维条码。二维条码技术的特点有信息 密度高、纠错能力强、可引入加密机制、能够表示多种信息和成本低，它非常 适用于自动识别与数据采集。与传统的一维条码相比，二维条码能够在二维的 方向上装载信息，它有两种分类，即矩阵式二维条码和行排式二维条码。所以 它的存储容量相对一维条码有了跳跃性的提高，一个邮戳大小的条码符号可以 存储几千个字符。二维条码可直接表示数字、字母、符号、图像、汉字等信息 内容，一个二维条码图形可以容纳较多的信息内容，真正意义上实现了对物品 的“描述 功能1 3 j 。在识别过程中，二维条码是根据对应的译码程序来实现，不 需要外接数据库，在应用上更加简便高效。 二维条码有如下特点： 1 ) 可以容纳大量信息。由于二维条码在水平方向和垂直方向都可以表达信 息，所以它比一维条码要多容纳很多的信息。一般，一维条码符号差不多可以 存储2 0 个字符，但是二维条码就可以存储上千字符。 2 ) 二维条码具有纠错能力。二维条码自身携带了纠错码，比如q r 码带有 纠错码r s ，而r s 码一共有四个等级纠错，最高纠错率达3 0 ，这使得条码受 武汉理工大学硕士学位论文 到某些污损后仍可以正确识读，安全性提高很多。 3 ) 编码范围很广。它可以编码图片、文字、声音、指纹、签字等信息，同 时还能够表示多种图像数据和语言文字。 4 ) 可以嵌入加密机制。加密机制的嵌入是二维条码的一大优点。比如：我 们在利用二维条码表达照片时，首先选择恰当的加密算法加密图像信息，然后 利用二维条码表示。在识别的过程中，通过相应的解密算法，照片就可以恢复 出来。这样就降低了各种证件、卡片等的造假率。 5 ) 二维条码译码识别可靠性高。一般条码的译码错误率大约为百分之二， 而二维条码的误码率不超过千分之一，译码可靠性极高。 除了以上特点外，二维条码还有其他的特点。比较常见的二维条码有q r c o d e 、p d f 4 1 7 、d a t am a t r i x 、c o d e l 6 k 、汉信码、龙贝码、网格码等。一些典型 的二维条码及其功能表如表1 1 所示。 表1 1 二维条码功能对比表 q r 码 p d f 4 1 7 码d a t am a t r i xm a x ic o d e 回崔回 砸鬻蓬霆幕圈 邕 榭嚣； 符号形状 回辩墩张鹳蛾 类型矩阵堆积条码 矩阵矩阵 数字 7 0 8 92 7 1 0 3 1 1 61 3 8 数 据 字母数字 4 2 9 61 8 5 02 3 5 5 9 3 容 8 位字节2 9 5 31 0 1 81 5 5 6| 量 汉字1 8 1 75 5 47 7 8| 大容量、小尺 主要特点 寸输出、高速 大容量小规模打印高速扫描 扫描 主要用途所有类别办公自动化小零件标识物流 二维条码作为现代条码的新兴技术，其适用范围广泛、推广应用价值极高， 其中q r 码在最近几年来被人们广泛的应用。日本的移动电话公司在具有拍摄功 2 武汉理工大学硕士学位论文 能的移动电话中加入q r 码识别软件，方便消费者获取商品信息；台湾的高铁车 票、电影票上都印有q r 码，并且推出了q r 码的专属商品、购物商城及其相关 应用；我国的新版火车票采用q r 码作为防伪措施，还有些城市在站台和车上使 用q r 码为市民提供公交路线信息。 1 2 国内外发展现状 在8 0 年代末，国外就开始了对二维条码的研究，现在已经研究出很多种码 制，比如c o d e 4 9 ，c o d e1 6 k ，p d f 4 1 7 ，c o d eo n e 、q rc o d e 等。同时针对二维 条码的一系列标准化工作很早就已经研究，国际自动识别设备制造商协会( a i m i ) 与美国标准化协会( a n s i ) 把p d f 4 1 7 、c o d eo n e 、c o d e1 6 k 、c o d e4 9 、d a t am a t r i x 与m a x ic o d e 等制定为符号标准。新成立的国际标准化组织与国际电工委员会的 第一联合委员会的第三十一分委员会在1 9 9 7 年6 月完成了四种二维条码的i s o 标准，即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 4 。q r 码标准化于2 0 0 0 年6 月被批准为i s o 国际标准( i s o i e c l 8 0 0 4 ) ，在2 0 0 4 年1 1 月微型q r 码被批 准为j i s ( 日本工业标准) 标准( j i sx0 5 1 0 ) 。 国外对二维条码技术的研究较早，目前主要研究领域有彩色条码和手机应 用条码。微软提出的彩色条码( h c c b ) 可以在较少的空间里存储更多的信息，并 且用三角形代替长方形。针对这种条码，国外学者研究了一种高容量的彩色二 维码，它的密度接近微软的h c c b ，鲁棒性接近q r 码，但是它的计算复杂度增 加了。针对手机应用条码，国外研究了一种预处理系统，恢复低质量的q r 图， 采取了直方图均衡化，利用卷积去模糊化，利用不同算法迭代。同时对于q r 码 的识别，利用超分辨率技术产生高质量的低分辨率q r 码。还有的学者利用点图 多路复用来识别q r 码。这种预处理系统只能对设备造成的污损进行消除，其他 的污损就靠自身携带的纠错码的进行纠正。o r 码的纠错能力最高只有3 0 ，相 比p d f 4 1 7 的5 0 ，q r 的纠错能力是远远不够的。因此这些都是现有黑白条码 所面临的新问题。 二维条码是一种新起的自动识别技术，和其它的自动识别技术相比，它的 成本低、信息能够移动、不需要数据库、保密防伪性强，二维条码一出现便受 到我国相关部门的重视。中国物品编码中心编著的( - - 维条码技术在1 9 9 7 年 初出版了，这是我国第一部二维条码专著。为了对二维条码技术有进一步的研 究，中国物品编码中心承担了国家科委“九五”重点项目“二维条码技术研究 武汉理工大学硕士学位论文 与应用试点 ，并且发布了国家标准四一七条码。在2 0 0 3 年，上海龙贝信息 科技公司发明了适合中国国情的二维条码一龙贝码。在2 0 0 5 年，第一个我国 自主知识产权二维条码标准汉信码研制成功。另外，许多的公司、研究所、 高等院校都在进行二维条码技术的研究【5 j 。 我国对于q r 码的研究主要在q r 码的识别技术，例如嵌入式环境下的q r 码识别研究，应用手机系统的q r 码识别研究等。在q r 码的编译码方面，大致 的流程都是一样的。主要的是特别的针对图像预处理这一块，重点是如何有效 的减少噪声对条码图像的影响，例如对条码图像做二值化处理【甜】和分割定位条 码。二值化阈值的选取一般有全局阈值法和局部阈值法，而最大类间方差法 ( o t s o ) 对二维条码图进行二值化能够得到很好的效果。图像的边缘检测是为了 突出我们所需要的特征，常见的边缘检测算子有r o b e r t 算子、s o b e l 算子、p r e w i t t 算子、l o g 算子等。在译码过程中，主要是一些快速定位寻像图像和建立取样网 格的一些优化算法。 二维条码的纠错能力、信息容量等特征决定了它的应用场所。而q r 具有大 容量、低成本、可以支持多类信息等优点，因此它在我国的应用前景很好。众 所周知，q r 码自身带有纠错能力，但是在实际获取q r 图像时，会因为各种不 同的原因而导致图像有不同程度的污损。假设污损程度加大，超过本身能够识 别的能力，那么q r 就不能译码成功，获得我们想要的信息。因此除了进行图像 预处理这一块外，还有必要设计一个方案来提高q r 码的抗污损能力，也就是提 高它的纠错能力。如果能够达到p d f 4 17 的纠错能力，那么就能大幅的提高q r 码的识别效果。 1 3 研究目的和内容 早期的二维条码由于条高的截短使得二维条码经常不可识别，为了改善这 种情况，后期研制的二维条码运用了纠错码技术。纠错码技术实质上是利用信 息冗余来对原有信息进行纠错。二维条码在制作的过程中可以根据用户的不同 需求来生成对应的二维条码，比如版本、纠错等级。最后得到的二维条码的信 息是由数据码字和纠错算法生成的纠错码字组成的。在实际生活中，提取到的 二维条码往往会有不同程度的污损，比如噪声、污点。噪声是可以利用图像处 理技术来消除的，而污点则需要通过纠错码技术来进行正确译码。q rc o d e 有四 个纠错等级，最高级别可以纠错3 0 。但是在实际应用过程中，为了能够得到 4 武汉理工大学硕士学位论文 准确的信息，条码的纠错能力肯定是越高越好。因此考虑到采用一种性能较好 的纠错码来代替q r 码里面的r s 码，同时运用图像预处理技术消除设备带来的 噪声。从这两个方面考虑，共同提高q r 码的识别效果。 本课题的主要研究是基于q rc o d e 这种二维条码的识别技术，提出一种新 的q r 码生成方案。针对现有的q r 中的纠错能力有限，研究了一种新的纠错码 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码。通过分析l d p c 码的编译码思想以及性能仿 真实验，并且与r s 码进行对比分析，从而可以得出l d p c 码的性能优于r s 码。 那么就可以利用l d p c 码来替换r s 码生成新的q r 码。一般的，设备采集到的 图像会因为环境的影响以及设备本身具有的缺陷而造成不同程度的污损，有的 污损可以利用图像处理技术进行消除，比如采用较好的滤波技术降低噪声对图 像的影响，运用灰度补偿、直方图判断和o t s u 法进行二值化处理以及利用边 缘检测进行阈值分割等。这些都是在图像预处理这一块来完成的。而有的污损 则需要q r 本身的纠错能力来进行纠正，即在q r 码的译码过程中，运用l d p c 码来进行纠错。最后通过理论分析和实验仿真来比较新旧q r 码，从而可以得出 新的q r 哪些方面改进了。 q rc o d e 二维条码不仅可靠性高，信息容量大，存储信息类别广泛，保密 防伪性强，而且具有超高速识读，全方位识读，纠错能力强等自身特点。因此 它的应用前景很好，但是在实际使用过程中会有不同程度的污损，所以就有了 纠错码。l d p c 码纠错能力强、译码复杂度底，灵活性好，便于实现。这样就能 够对所获得的信息进行处理，消除条码在使用过程中所造成的错误。对于新的 q r 码，它的纠错能力提高了，那么应用的范围可以扩展，同时也降低了算法复 杂度。 1 4 论文结构 本文各章内容安排如下： 本章，介绍了二维条码技术与国内外研究现状，同时也介绍了q r 码现阶段 所存在的问题以及本文的研究目的。 第2 章，介绍了二维条码q r 码的符号特征以及q r 码的编码原理，然后详 细的介绍了q r 码中纠错码r s 码的编译码思想及仿真实验。 第3 章，介绍了新的q r 码中涉及到的技术，例如纠错码l d p c 码和图像预 处理技术。简述了l d p c 码的编译码思想并且对其进行了仿真实验，然后把l d p c 5 武汉理工大学硕士学位论文 码与r s 码进行性能对比。在图像预处理过程中包括了图像灰度化、中值滤波、 二值化、几何调整最后介绍了q r 图像的定位与分割。 第4 章，介绍了新的q r 码的编译码的理论分析和实验过程，结果分析。 第5 章，对本文进行了工作总结，展望以后的研究方向。 6 武汉理工大学硕士学位论文 第2 章q rc o d e 二维条码 二维条码的获得包括信息编码、符号的制作、符号的印制、符号的拍摄等 过程【8 捌。文中针对二维条码q r 码进行研究，首先需要对q r 码的符号特征进 行分析，然后就是q r 码的生成流程。由于q r 码本身就具有纠错码r s 码，所 以为了分析q r 码的纠错性能，详细的介绍了r s 码的性能。 2 1q r 码的符号结构 q r 码是日本d e n s o 公司于1 9 9 2 年9 月研究出来的一种二维条码，比起一 维条码来说它有一些显著的特点，它可以表示汉字及图像等多种文字信息，信 息容量大，不依赖数据库，并且自身带有纠错能力，表2 一l 介绍了q r 码容量及 纠错能力。 表2 - 1q r 的一些特点 项目 特性 数字字符7 0 8 9 个 数据类型与容量( 4 0 l )字母数字4 2 9 6 个 8 位字节数据2 9 5 3 个 汉字1 8 1 7 个 l 级：约可纠错7 的错误 ( r s 码) 纠错等级m 级：约可纠错1 5 的错误 q 级：约可纠错2 5 的错误 h 级：约可纠错3 0 的错误 q rc o d e 是一种矩阵式二维条码，它是一个正方形图形，里面也是由正方形 模块排列而成，其中还包括位于符号的左上角、右上角、左下角的三个位置探 测图形，通过这三个图形可以确定符号的位置，倾斜度和尺寸，q rc o d e 的大 小范围较长，而且有四个纠错等级。用户根据自己的需求确定q r 码模块的宽度。 q r 码符号由编码区和功能图形组成，其中功能图形包括寻像图形、分隔符、定 位图和校正图形【1 0 。1 。数据编码在编码区，符号的四周是空白区。 1 ) 符号的版本和规格 q r 码符号总共有4 0 种规格1 1 2 以3 1 ，即版本l 、版本2 版本4 0 。版本l 的 7 武汉理工大学硕士学位论文 规格是2 1 x 2 1 模块，版本2 的规格是2 5 x 2 5 模块。以此类推，后一个版本符号 都比前一版本符号每边多4 个模块，那么版本4 0 的规格是1 7 7 x 1 7 7 模块。 2 ) 寻像图形 寻像图形是由3 个相同的位置探测图组成。每个位置探测图是由3 个不同 的同心正方形重叠而成，即7 x 7 个模块、5 x 5 个模块和3 x 3 个模块，分别为深色、 浅色、深色。位置探测图形的间隔宽度比例是1 ：1 ：3 ：1 ：1 。符号中基本上没有类似 的图形，因此可以快速的识别出可能的q r 符号。通过识别三个位置探测图形， 符号的位置和方向就可以确定。 3 ) 分隔符 分隔符位于位置探测图形和编码区域之间，占有1 个宽度的模块，它是由 浅色模块组成。 4 ) 定位图形 定位图形分为水平和垂直，大小为一个模块的宽度，以深色模块开始和结 束，中间的就是交替变换浅深色模块。水平定位图形在上方的两个位置探测图 形之间，垂直定位图在左侧的两个位置探测图形之间，它们的位置即是符号的 第6 行与第6 列。 5 ) 校正图形 校正图形是由3 个大小不同的同心正方形重叠而成，分别是5 x 5 个深色模 块，3 x 3 个浅色模块以及l x l 个深色模块。不同的版本号校正图形的数量也不同， 大于版本1 符号都有校正图形。 6 ) 编码区域 编码区域有不同信息的符号字符，即数据码字、纠错码字、格式信息和版 本信息。 7 1 空白区 空白区是围绕在符号四周的区域，它占有4 个模块的宽度，其反射率和浅 色模块的比例为1 。 2 2q r 码的编码 q r 码的编码方法流程如图2 - l 所示，每个模块的内容如下： 1 ) 数据分析 首先对输入的数据流进行分析，然后确定需要编码的字符类型。q r 码能够 8 武汉理工大学硕士学位论文 表达几种不同的数据模式，而不同的模式可以相互转换，因此数据可以高效转 换为二进制位流。纠错等级和错误检测由用户指定，如果没有指定符号版本， 则选择相适应数据量的最小版本。q r 码的版本符号不同数据容量也不一样，有 一个固定的计算公式，假设每边的模块数是a ，功能图形的模块数是b ，格式及 版本信息模块数是c ，那么除了c 以外的数据模块为d = a 2 一b c ，数据容量码 字为d 8 ，剩余位为d 8 。 数据数据纠错构成最 生成版本和格 分析 ， 掩膜 式信息，构成 编码编码终信息 符号 图2 1q r 码编码流程图 2 ) 数据编码 数据编码就是依据互相匹配的数据模式和变换方法将数据字符转换为位 流。如果需要模式转换时，将模式指示符和终止符分别加入到新的模式段首和 数据序列后。对于生成的位流按照8 位一个码字分组，遇见不足8 位的时，用0 填充以补足8 位，必要时加入填充码字1 1 1 0 1 1 0 0 和0 0 0 1 0 0 0 1 ，利用它们交替使 用以满足数据码字数。 3 1 纠错编码 纠错编码是利用纠错编码算法对码字进行编码。首先把码字序列进行分块， 然后为每一块生成相应的纠错码字，最后把生成的纠错码字加入到对应数据码 字的后面，实现纠错编码。 4 ) 构造最终信息 最终序列的构造是首先排完所有的数据块，然后再排纠错块。通常q r 码符 号的码字容量正好由所包含的数据块和纠错块填满，所以在有些版本中，可能 会需要几个剩余位添加在最终的信息位流中以填满编码区域的模块数。 5 ) 在矩阵中布置模块 在矩阵中布置各模块，即寻像图形、分隔符、定位图形、校正图形与码字 模块。 曲符号字符表示 q r 码符号有规则的和不规则的。其中大多数码字是规则的，表示为2 * 4 个 模块的排列，可以水平或者垂直布置，当方向改变或者紧靠功能图形时，就需 要使用不规则符号字符。 m 功能图形的布置 9 武汉理工大学硕士学位论文 按照使用版本相对应的模块数构造正方形矩阵，把寻像图形、校正图形等 放入相应位置，并填入合适的深浅颜色。暂时不安排格式信息和版本信息的位 置。 c ) 符号字符的布置 在符号的编码区域，以2 个模块宽的纵列从符号右下角开始，从右到左， 从下往上，再从上往下的交替布置。 6 ) 掩模 为了提高识读的可靠性，就必须合理地安排深色和浅色模块，阻止位置探 测图形的位图1 0 1l1 0 1 出现在符号其他区域。功能图形不需要掩膜，利用多个矩 阵图形对编码区域进行异或( x o r ) 操作，评价结果，选择掩模结果中得分最低的 掩模图形用于符号掩模。掩膜图形的参考从0 0 0 到1 1 1 ，一共8 个。 7 ) 格式和版本信息 有必要时生成格式和版本信息，形成符号。格式信息是1 5 位，其中有5 个 数据位，1 0 个是用b c h ( 1 5 ，5 ) 编码计算得到的纠错位。版本信息是1 8 位，其 中有6 个数据位，通过b c h ( 1 8 ，6 ) 编码计算出1 2 个纠错位【1 4 - 15 1 。版本大于6 的q r 里面才包含版本信息，而格式信息一直都有。最后的格式信息和版本信息 都要映射到对应的预留位置。格式和版本信息在符号中都出现两次并且提供冗 余，它们影响着整个符号的译码。同时它们是位于位置探测图形旁边，没有和 码字混合在一起。 2 3q r 码中的r e e ds o l o m o n 纠错算法 r s 码( r e e d s o l o m o n ，里德一所罗蒙码) 1 1 6 j 是一类非二进制的b c h 码，具有 极强的纠错能力，近几年来在通信中有着广泛的应用，它也是一种典型的代数 几何码。首先它是被里德( r e e d ) 和所罗蒙( s o l o m o n ) 应用于m s 多项式于1 9 6 0 年 构造出来的。 r s 码是纠错码中很重要的线性分组码之一，它是一种多进制码，也是一种 最大距离可分码，即在给定码字冗余量大小的情况下，码字具有最小的距离。 r s 码善于检测突发性的错误，它可以在不使用很多的符号数目下检查出错误。 与此同时，码字和译码过程中所使用的符号是一样的，所以译码过程中进行的 运算就是码字符号的运算。r s 码的码元符号来自有限域g f ( q ) ，它的生成多项 式的根也是g f ( q ) 中的本原元，即r s 码的符号域和根域是相同的。 1 0 武汉理工大学硕士学位论文 2 3 1r s 码的编码思想 令r e ( x ) = c 2 f x 矗- i - c 2 f + l x 2 h 1 + 厶一1 x ”1 和，( x ) = c o + q x + c 2 f _ 1 x 2 h 分别表示信 息多项式和校验多项式，则一个r s 码的多项式表示为： c ( x ) = 聊( x ) + 厂( x ) ( 2 一1 ) 如果c ( x ) 为一个码字，则它必须为生成多项式g ( x ) 的倍数，即： c ( x ) = g ( x ) g ( x )( 2 2 ) 编码的过程就是从m ( x ) 和g ( x ) 中寻找p ( x ) ，它可以通过除法算法来完成， 即用m ( x ) 除以g ( x ) 得到： m ( x ) = g ( x ) g ( x ) + p ( x )( 2 - 3 ) 同时令r ( x ) = - p ( x ) ，则有q ( x ) g ( x ) = ，z ( x ) + ，( x ) = c ( x ) 。 从上可得r s 码的编码步骤【1 7 】： 1 ) 首先把x 2 与信息多项式m ( x ) 相乘，得到x 2 t m ( x ) ； 2 ) 再用生成多项式g ( x ) 除x 2 m ( x ) 得到余式r ( x ) ，再利用加法逆元简化各项 系数，从而得出校验位； 3 ) 相加m ( x ) x ”和r ( x ) 就得到编码后的码字多项式m ( x ) x ”七+ 厂( x ) 。 2 3 2r s 码译码思想 n - i 设接收码字多项式是r ( x ) - - e 一，x ”， ，= l n - i 差错样图多项式是e ( x ) = e n 一，x ”7 ， j = l n - i 纠错码字多项式是c ( x ) = c n 一声”，伴随式多项式是s ( x ) ，差错定位多项式为 i 害l a ( x ) 。通过译码器从r ( x ) 中得到准确的估计错误图样e ( x ) = e ( x ) ，然后根据错 误样图得到c ( x ) ，最后得到信息m ( x ) t 1 引。 由于r s 码是非二进制的，所以在纠错时除了要确定错误位置外，还要求出 相应的错误值。设发送的码字为 c ( x ) = c o + q x + 巳x 2 + + 气一l x ”1( 2 - 4 ) 且传输中发生t 个错误。错误位置在 如 l 一州刀。 构造维数为m * n 的校验矩阵鼠利用高斯消元法将其转化如公式( 3 2 ) 所示。 rr矿 j 72 l1”一。”一。1”-k。七l(3-2)0 0ii 如果是满秩的，变换后则不会出现全0 的行。通过以上转化可以求出生 成矩阵g = 【最。( 柑) 厶。】，信息序列甜= l ，甜2 ，“足】则通过c = 甜g 生成码字c 。h 矩阵是稀疏的，但是矩阵尸不是稀疏的，因此在编码过程中矩阵尸需要占有大 量的空间。 团回曰团曰 曰 曰曰围困曰曰团园团圈圈圈 图3 1 校验矩阵的二分图 除了校验矩阵外，l d p c 码可以由图模型表示，其中t a n n e r 图是比较直观 的一种，l d p c 码的编译码特性可以通过它形象的刻画出来。将编码后的比特流 用顶点集来表示，顶点的个数为码长n ，也就是校验矩阵的列数n 。每一个比特 1 7 0 o 0 0 o 0 = = = = = 办砌白印印 + + + + + 岛缘靠白 + + + + + 以硌么靠所 + + + + + 岛磊晚白以 武汉理工大学硕士学位论文 对应其中的一个顶点，称之为信息节点或变量节点。还需要另一个顶点集来表 示校验约束，顶点个数为校验方程的个数，也就是校验矩阵的行数m ，每一个 校验约束对应其中一个顶点，称之为校验节点。如果第j 个码元参加了第i 个校 验约束，那么校验矩阵的第i 行第i 列的元素是l ；在对应的校验节点和信息节 点之间连一条边，从而得出与校验矩阵对应的二分副2 卜2 翻。方程( 3 。3 ) 表示为 h ( 1 2 ，3 ，6 ) 的校验矩阵，图3 1 表示的是其对应的二分图。 l d p c 码的校验矩阵与t a n n e r 图所表达的意思其实是一样的，对应的都是 同一个l d p c 码。同时码生成函数和度数分布都可以表示l d p c 码的集合。设 最大校验节点的度为以，最大变量节点的度为z ，凡( d ) 是指与度数为f 2 的 校验( 变量) 节点相连的边数在总边数中所占的比例，得出方程( 3 - 4 ) 和( 3 5 ) 。 h = 11l0 0110oo10 1l1l10 oo0o0l 00000l 1lo1l1 l0ol0o o11101 olol l0lllooo ool0110o11l0 屯 a ( x ) = z , x 扣1 ( 3 3 ) ( 3 - 4 ) p ( x ) = p , x 卜1 ( 3 5 ) i = 2 其中a ( 1 ) = p ( 1 ) = l ，a ( x ) 、p ( x ) 称为度数分布或者码生成函数。规则的 l d p c 码是指校验矩阵中各行、各列的非零元素的个数分别相同，此时所有的变 量节点都有一样的度或，所有的校验节点都有一样的度吃，它们的分布如方程 ( 3 6 ) 和( 3 - 7 ) 。 a ( x ) = x 西。1( 3 - 6 ) p ( x ) = 。1( 3 - 7 ) 总边数为e = ，矾= m a r c ，码率为，= ( n - m ) n = l 一矾吃。 3 1 1l d p c 码编码思想 利用生成矩阵直接编码方法是最基础的，它适用于任何类型的l d p c 码。 1 8 武汉理工大学硕士学位论文 它是通过对所构造的校验矩阵进行变换从而得到所需的生成矩阵，然后利用信 息序列与生成矩阵相乘，得到的结果就是编码后的码字。具体步骤如下： 1 ) 低密度校验矩阵的构造 l d p c 码是完全由其校验矩阵确定，所以要对l d p c 码进行编码，首先需要 构造一个校验矩阵。前面已经介绍了如何构造，这里假设已经构造出一个校验 矩阵风便可以从码字空间( 满足关系式日c r = 0 ) 中选出一组可用码字作为 所需构造的l d p c 码。 2 ) 为了方便在译码时明确信息比特的位置，需要利用高斯消元法将校验矩阵 h 转化为系统形式：日= ，】，其中i 是单位矩阵。 3 ) 变换校验矩阵得到生成矩阵g = 户，i 】。 4 ) 把信息序列u 与生成矩阵g 相乘，得出编码后的码字，如方程( 3 8 ) 所示。 c = “g = “尸，, 】( 3 8 ) 编码算法如下： f u n c t i o n 【u ，p ，r e a r r a n g e d _ c o l s - l d p c _ e n c o d e ( s ，h ) d i m = s i z e ( h ) ； r o w s = d i m ( 1 ) ； c o l s = d i m ( 2 ) ； 【p , r e a r r a n g e d c o l s = h 2 p ( h ) ； c = m u l _ g f 2 ( p ，s ) ； u l = c ，s 】； u = r e o r d e rb i t s ( u l ，r e a r r a n g e d c o l s ) ； 目前在编码方面影响l d p c 码的应用的重要因素有编码的复杂度以及编码 的时延。上面的利用生成矩阵直接编码方法的编码复杂度是o ( n 2 ) ，在码长很长 的情况下编码复杂度将成为一个严重的制约因素。为此需要引用一种新的编码 方案，针对在构造生成矩阵时，由于高斯消元处理会破坏了校验矩阵特有的稀 疏特性，使得生成矩阵中含有大量的“1 元素，因此提出了运用近似下三角矩 阵