（测试计量技术及仪器专业论文）二维条形码编译码原理与应用研究.pdf

摘要 本文简要介绍了二维条形码的特点和编码规则，详细阐述用计算机实现其编码的 原理和方法，采用具体实例介绍设计步骤，并给出可同时实现中英文编码的程序设计 方法。另外，二维条形码具有一维条码不具备的纠错功能。本文简要介绍了 r e e d - s o l o m o n 纠错码( r s 码) 原理，重点分析研究它在p d f 4 1 7 二维条形码中的应用 方法，并详尽地推导了在迦罗华域g f ( 9 2 9 ) 域内r s 码的编译码方法。同时提出一种 适用于p d f 4 1 7 纠错编码和译码的查表方法，可以简单确定任意码字在g f ( 9 2 9 ) 内所 对应的本原元的幂次。运用该方法可以快速而准确地计算出纠错码生成多项式的系数 列以及差错伴随式。显著提高纠错效率。在译码方面本文探讨了一种采用c c d 整图 读取条码图像的方法，用计算机进行图像分析，特征提取，完成译码的实现方法。还 给出了一种基于p d f 4 1 7 二维条码结构特性的算法，该方法设计滤波器滤除噪声部分， 再采用点搜索法进一步去除不符合条码边界特点的孤立的点和容易与边界混淆的竖 直划痕，最后对条码图像进行复原。实验证明可以有效去除滤波对有效条码边缘的影 响，同时保证图像可靠恢复。对于恢复后的条码图像采用改进的边缘检测投影方法译 码，降低了对条码纠错等级的要求，大大提高了译码的效率和准确率。 关键字：二维条码，p d f 4 1 7 ，滤波一还原，投影，r s 纠错码，b m 算法。 a bs t r a c t ih l sp a p e rc o v e r st h ec h a r a c t e r i s t i c sa n db a s i cp r i n c i p l e so ft h ed e s i g no ft w o d i m e n s i o n a l b a rc o d ea n dd e t a i l e de x a m p l e so fi t s a p p l i c a t i o n ，i n c l u d i n ga ne n c o d i n gm e t h o df o rb o t h e n g l i s ha n dc h i n e s ec h a r a c t e r s t w o d i m e n s i o n a lb a rc o d ep o s s e s s e st h ec a p a b i l i t yo f e r r o r c o r r e c t i n gw h i c ho n e - d i m e n s i o n a lb a rc o d ed o e s n t s o ，b e s i d e sab r i e fi n t r o d u c t i o n o fr e e d s o l o m o n e r r o r - c o r r e c t i n gc o d e ( r sc o d e ) t h i sp a p e r a l s o g i v e s at h o r o u g h a n a l y s i so fr sc o d e sa p p l i c a t i o ni nt w o d i m e n s i o n a lb a rc o d ep d f 4 1 7 ，g i v i n gd e t a i l e d e r r o r 。c o r r e c t i n gp r i n c i p l e si ng f ( 9 2 9 ) m e a n w h i l e ，al o o k i n g - u pd a t a b a s em e t h o du s e df o r y i e l d i n gp d f 4 7 e r r o r c o r r e c t i n gc o d e sh a sb e e nd e v e l o p e d ，w h i c hm a k e s i te a s i e ra n dm o r e a c c u r a t et oc o m p u t et h ec o e f f i c i e n t so ft h eg e n e r a t i n gp o l y n o m i a la n dr e s u l t so f s y n d r o m e p o l y n o m i a l s t h ee f f i c i e n c y o fp d f 4 1 7 e r r o r - c o r r e c t i n g f u n c t i o ni st h e r e f o r e h i g h l y i m p r o v e d a sf o rt h ed e c o d i n gp r o c e s s t h i sp a p e rd e s c r i b e sas o l u t i o nb a s e do nw h o l eb a r c o d ep i c k i n gu pb yc c dv i s i o ns y s t e m ，a n d c o m p u t e rp r o c e s s i n gt od e t e c tt h ee d g e so f t h e b a r c o d e s a na l g o r i t h mi sa l s od e s i g n e dh e r eb a s e do np d f 4 17t w o d i m e n s i o n a lb a r c o d e s s t r u c t u r e i tf i r s tp r o p o s e saf i l t e rt oe l i m i n a t en o i s e ，t h e nd e a l sw i t hv e r t i c a ls c r a t c h e sa n d t h o s e p o i n t s t h a td on o t c o m p l yw i t h t h eb a rc o d e s l b o u n d a r yc h a r a c t e r i s t i c sb y a p o i n t s e a r c hs t r a t e g y l a t e r ，d u r i n gp r o c e s so fr e s t o r i n g t h eb a rc o d e dp i c t u r e s ，t h e c o n t a m i n a t i o n sw i l ln o tb er e s t o r e dd u et ot h a tf a c tt h a tt h e i rs e e d sf o rr e s t o r a t i o nh a v e b e e nc l e a n e d b e f o r e h a n d e x p e r i m e n t sh a v ep r o v e dt h a tt h i sa l g o r i t h mc a ne f f e c t i v e l y e l i m i n a t et h en e g a t i v es m o o t ho ft h eb a rc o d ec a u s e db yf i l t e r i n g t h er e s t o r e dp i c t u r e s w i l lt h e nb ed e c o d e db ya ni m p r o v e de d g e d e t e c t i n gp r o j e c t i o nm e t h o dw h i c hc a nl e a dt o e f f i c i e n c ya n da c c u r a c yo f t h ed e c o d i n gp r o c e s sw h i l ed e m a n d i n gal o w e re r r o rc o r r e c t i n g 】e v e 】 k e y w o r d s ：t w o d i m e n s i o n a lb a r c o d e ，p d f 4 1 7 ，f i l t e r - r e s t o r e ，p r o j e c t i o n ，r s e r r o r c o r r e c t i n gc o d e ，b ma l g o r i t h m i i 南京航空航天大学硕士学位论文 i i 二维条形码简介 第一章绪论 条码技术自问世2 0 多年来发展讯速，受到人们的普遍关注。条码、e d i 、集装箱 三大技术已成为国际商贸3 大标准贸易方式而被广泛采用。目前一维条码技术在我国 已广泛应用于商业、金融业、交通运输业、医疗卫生、邮电、制造业、仓储业等领域， 极大地提高了工作效率，提高了数据采集和信息处理的速度，为管理科学化和现代化 做出了积极的贡献。但是，一维条码存在很多缺陷。首先，其表征的信息量有限，一 般每英寸只能存储十几个字符信息。例如：c o d e 3 9 码最大密度只有9 4 c p i ( c h a r a c t e r p e ri n c h e s ) 。c o d e l 2 8 码最大密度也只有1 2 2 c p i 【1 i 。所以一维条玛常依赖于一个有 效外部数据库的支持，而其本身只起一个指针作用，离开外部数据库，条码本身就没 有意义了。这一缺点严重限制了条码的使用范围和工作效率。目前几乎所有的使用一 维条形码的机构都依据这种模式，附带庞大数据库的方法显然无法适应某些服务对象 数量巨大酌行业的要求，比如户籍管理、医疗信息卡、物流信息卡等。最好的方法是 可以把产品或者服务对象的所有相关信息都记录在一份信息量大的条码标签上，彻底 脱离数据库的束缚。其二，一维条码只能表达字母和数字，而不能表达汉字和图像， 在一些需要应用汉字的场合，一维条码便不能很好的满足要求。其三，一维条码不具 备纠错功能，比较容易受外界污染的干扰。 二维条码的诞生解决了一维条码不能解决的问题，它能够在横向和纵向两个方位 同时表达信息，不仅能在很小的面积内表达大量的信息，使条码脱离数据库成为独立 的信息载体。而且能够表达汉字和存储图像。拓展了条码的应用领域。目前国际上使 用的二维条码有两种，一种是堆积码，如c o d e 4 9 、1 6 k 、p d f 4 1 7 等。另一类是矩阵码， 如c o d e l 、m a x i c o d e 等。二维条码属于高密度条码，可以将大量数据在小区域内编码， 它本身就是一个完整的数据文件。在国外有便携式数据文件( p o r t a b l ed a t af i l e ) 、 自备式数据库( s e l f - c o nr a i n e dd a t a b a s e 、纸上网络( p a p e rf l e ) 等美拣，p o f 4 1 7 是其中一种使用较广、较成熟的二维条码。关于几种条码的形式，如图卜l 。 j 荃ii - 一斑蓉妈扭? d f 4 7 二维条码以及o a t mk a t r i x 二维条码 二维条形码编译码原理与应用研究 1 2p d f 4 1 7 二维条码的特点和应用方法 在二维条形码中，p d f 4 1 7 性能尤为突出。它的优点包括：( 1 ) 信息容量大密度 高。例如，p d f 4 1 7 条码符号可以容纳1 8 4 8 个字母字符，或2 7 2 9 个数字字符，或字 母数字混合编码。当窄条模宽为6 6 密耳( 0 1 7 m m ) 时，p d f 4 1 7 条码表示标准i s o 卡， 大约只占面积7 6 m m x 2 5 r a m ( 包括周围空白区) 。表示相同信息时二维条码比一维条 码节省空间，例如表示1 7 个字母数字符号串，c o d e 3 9 码需要长度大约8 0 r a m 左右， c o d e l 2 8 码需要长度6 0 r a n 左右，而p d f 4 1 7 码只用2 5 m m 2 5 m m 的面积( 打印时采用 缺省长高比) 。( 2 ) 修正错误能力强，译码可靠性高。二维条码采用世界上先进的错 误修正技术，可以有效地防止译码错误。可将由于条码符号破损、玷污等丢失的信息 破译出来。同时还能提高译码速度。用户可根据需要选择错误修正等级。最高时，可 将符号受损面积达5 0 的条码符号所含信息复现出来。最近，在美国国防部举办的管 理数据库测试中，阅读2 0 0 0 万仑p d f 4 1 7 条码，没出现一例译码错误，说明其具有极 高的可靠| 生。( 3 ) 保密性高。信息按密码格式编码，可以防止伪造条码或非法使用有 关编码的信息。( 4 ) 易打印且耐用持久。条码可印在纸、卡片等各种条码载体上，可 使用激光、热敏热转印、喷墨等打印技术，读条码时不需要物理接触，所以不受读 卡次数限制，使用寿命长。( 5 ) 识读条码方法灵活。堆积型二维条码( 如? d f 4 1 7 ) 可以使用线性c c d 、2 d c c d 、激光扫描器识读。( 矩码码只能用2 d c c d 识读) 。( 6 ) 成 本低。可以将重要文档编为一系列二维条码，打印或印刷在普通纸介质上，使用二维 条码存储相同量的信息比使用磁带等存储介质成本低【3 】【4 】。因此p d f 4 1 7 的应用最为 广泛。 1 3p d f 4 1 7 二维条码应用方案举例 1 3 1p d f 4 1 7 条码在税务申报方面的应用方案 目前，我国的税务申报主要都是采用传统的手工申报，税务局每日都要处理非常 繁多的报表，所有报表需要手工重复录入到计算机中，因此税务人员的工作量很大， 申报过程缓慢而烦琐。使用p d f l 7 后，税务申报可采取如下方式步骤： 1 ) 纳税人索取申报软件：就近向税局申领或从i n t e m c t 网上下载申报软件。 2 ) 纳税人在计算机上填写申报表：税人依照软件提示逐项填写报表，计算机自动校 对后，选择二维条码生成按钮，生成p d f 4 1 7 。 3 ) 打印税务申报表：印出来的税务申报表中含原始报表数据、二维条码p d f 4 1 7 等。 4 ) 纳税人进行申报：税人依照原来的申报渠道( 真接到税局、邮寄等) 缴纳申报表。 5 1 税局扫描条码，完成申报过程：税务局开设二维条码扫描专用窗口，为申报人提 南京航空航天大学硕士学位论文 供方便快捷的服务。二维条码p d f 4 1 7 的编码格式可依据各税局自行定义 该方案的好处在于：1 ) 可以实现高效率作业；2 ) 提供精确无误的服务；3 ) 防伪 能力。由于税局可以在二维条码p d f 4 1 7 中加入密码和特殊信息，因此数据交换的可 靠性高，可以防止对报表数据进行假冒、篡改等非法行为。4 ) 文档管理，减少纠纷。 纳税户在缴纳p d f 4 1 7 条码的同时，也提供了报表原件，而原件上的公章或私人签名 等都具有法律效力，因此在发生错误和纠纷等特殊情况下，税局可以有单据进行核查， 这是使用电子数据交换( e l e c t r o n i c a l d a t a i n t e r c h a n g e e d i ) 所不能做到的。5 ) 可以 使税务处理系统免受病毒侵害，保证信息的安全性。这也e d 不能做到的。6 ) 可 以节约政府开支。税局每年需花费一定数量的钱用于印制税单发放给企业和个人，而 采用p d f 4 1 7 条码后，税局不再需要印制大量税单，从而合理地分配了资源，节约了 政府的开支。7 ) 弥补e d i 及网络建设的不足。税务系统涉及面比较广，必须与工商、 海关、银行、外汇管理、运输及其他相关部门多方面配合。但由于多方面的因素，这 些网络普遍缺乏开放性，因此给各个系统的互连带来了困难。甭p d f 4 1 7 二维条码对 网络没有要求，通过纸面传输可以方便地实现各个行业的业务联系，弥补了e d i 及 网络建设的不足。8 ) 可以改善服务质量。节约大量时间，纳税人不需要排着长队等 待。 1 3 2 其他p d f 4 1 7 应用案例 埃及生物和疫苗制品组织( v a c s e r a ) ，是埃及最大的疫苗制造商之一。近日宣 布在其所属的血站引进的二维扫描系统。大大加快了血制品的处理速度。“血制品的 质量和安全保证是挽救生命的关键所在，与此同时，运送速度也至关重要。”v a s e r a 的经理m a h is a d e k 先生说，“我们一直在寻找一种解决方案，能够在日处理量高达百 只血袋的情况下，确保准确与安全。每只血袋上必须标明序列号，捐赠人信息，捐 赠日以及到期日。p d f 4 1 7 技术的大信息，高效率，高可靠性解决了这些的问题。”如 图1 2 。 图1 2v a c s e r a 使用的含p d f 4 1 7 条码的血袋 二维条形码编译码原理与应用研究 1 ，4 本课题的意义 p d f 4 1 7 码1 9 9 2 年由美籍华人王寅君博士( y n j i u np w a n g ) 发明。p d f 是取英文 p o r t a b l ed a t af i l e 三个单词的首字母的缩写，意为“便携数据文件”。九十年代末 期，美国s y m b o l 公司将先进的自动识别技术应用在二维条码数据采集和识别领域， 极大地提高了译码的效率和准确性，把对高密度的二维条码的特征提取和分析的问题 推向了应用领域。迄今，他们的二维条码产品已经遍布世界各地，其中包括零售、仓 储、物流、生产制造、医药卫生、交通运输、邮政、教育、金融、军工及政府等众多 领域和部门。带来了丰厚的经济收益。1 9 9 8 年s y m b o l 公司在美国商业周刊杂志 上排名全世界i t 行业第五十一名，并在纽约股市的业绩排行前十名。由此可见，二 维条形码技术有着广阔的市场前景和价值，是能够产生巨大经济效益，促进国家发展 的高科技项目。 很多科研文献分析了二维条形码卓越的特性，预言其可以在某些行业担负重要的 职责，甚至成为电子数据交换( e d i ) 的载体e 5 1 州”。实际上，目前在美国等发达国家， 二维条码已经开始在一些实际应用领域中崭露头角。但在我国，由于大部分技术及几 乎所有设备都需从国外引进，使用成本非常高，因此目前实际应用范围很小。另一方 面，p d f 4 1 7 二维条形码信息密度大，数据采集及识别的难度很高，加之该技术具有 商业保密性，资料来源较少，相关研究受到很大限制。但是，只有开发出拥有自主知 识产权的编码软件和译码设备，我国才自够在条码市场上占据一席之地，降低使用成 本，促进二维条码的普及应用。当前，我国政府和科研机构也对二维条码技术设备的 开发给予了广泛的关注，已经把二维条形码技术的研究和推广应用逐步提到议事日 程。 1 5 本课题研究的主要内容 本系统按照功能结构可以划分为四个部分： 1 信息的采集、压缩编码和条码标签的生成 设计信息采集界面，根据四一七条码的编码原则和信息的特点，选择合适的压缩 模式或其组合，将原始信息压缩成四一七码字序列。建立与四一七条码对应的符号字 符数据库，以v i s u a lc + + 的o d b c 数据库模块来构建数据库关联，实现码字数据的 检索。并依据所得符号字符的个数确定其排列方式，以及相关标志符号的内容。然后 设计绘图程序，生成条码标签。 2p d f 4 1 7 纠错码的应用 p d f 4 1 7 条码的突出性能在于它具有纠错功能，它选用r e e d s o l o m o n 码( r s 码) 实现这一功能。r s 码是一种高效的纠错码，尤其是对那些突发性的成片干扰特 南京航空航天大学硕士学位论文 别有效 8 1 。但是，目前国内外的研究报告中都没有关于r s 码在四一七条码中的应用 原理的描述，这给如何实现纠错功能带来了困难。本文以通用r s 码的编译码原理为 参考，研究了四一七条码中r s 纠错码的生成算法和纠错算法，充分剖析了其纠错原 理和应用方法，并依据深入的理论探索，设计对应的实现程序。为了简化程序，减少 运算量以提高纠错速度，本文还设计了一种可以有效应用于循环码的码字值确定方 法，实验证明非常有效。 3 条码图像的处理和译码 准确译码的关键之一是准确分析条码图像，读取条码的条空分界信息，由此获得 条码的符号字符，检索对应码字数据库以获得原始码字信息。关于条码图像的定位和 扫描的方法，目前国内外都有一些理论上的研究和探索，如文献 9 】提出利用条码纹 理特征确定其在载体上的位置和方向的方法；文献 1 0 i n 对条码扫描仪将产生的低通 滤波器效果，提出了信号增强的方法，并就此设计一系列滤波器增强条码的条空边界 信号。 本文在把条码图像文件导入处理系统后，设计了对应的图像定位和扫描程序。使 用相应算法以有效剔除条码的污染确定每行条码的位置，最后通过逐行扫描程序， 获取符号字符信息。本系统中还包含分析程序段，根据四一七条码的特性，筛选出最 具可能性的一组。另外，一部分国外文献中研究了如何设计梯度滤波器和投影方法来 实现条码图像定位和扫描的功能，如文献 1 l 】、 1 2 ，将二维条形码问题转换一维来 解决。沿袭这种思路，本文从理论上探讨了一种基于滤波一还原的投影算法，从而提 高图像扫描的可靠性，并通过大量仿真实验验证了该方法的有效性。 4 应用方案的设计和实现 为增强本系统的应用性，更直观地显示二维条形码的优越性，本系统开发了两个 应用方案。包括居民身份证的条码编译和报税表格的条码编译界面。 二维条形码编译码原理与应用研究 第二章p d f 4 1 7 二维条形码的编码方法及实现 2 1p d f 4 1 7 编码原理 p d f 4 1 7 条码符号是一个多行可变长结构，相当于一维条形码在纵向上的叠加。 每行数据符号字符数相同，行与行左右对齐，直接衔接。其最小行数为3 ，最大行数 为9 0 。以下为一个7 行的p d f 4 1 7 条码，每行自左向右结构如图2 1 ： 2 1 1 符号表示 图2 - 1p d f 4 1 7 二维条形码结构示意图 2 1 1 1 符号字符的结构 每符号字符由4 个条( 图2 2 中黑色部分，b b 。) 和4 个空( 图2 2 中白色 部分，s 。s 。) 构成，自左向右从条开始。每一个条或者空包含1 6 个模块。在一个 符号字符中，4 个条和4 个空的总模块数为1 7 。 s 1s 2s 3 s 4 图2 - 2 符号字符 2 1 1 2 符号字符的簇 四一七条码的符号字符集由三个簇构成，每一簇包含以不同的条、空形式表示 的所有9 2 9 个四一七条码的码字。在每一簇中，每一符号字符对应唯一的码字，其范 围为0 9 2 8 。四一七条码使用簇号0 、3 、6 。簇号的定义适用所有的四一七条码符号 字符。条码的每行只使用一个簇中的符号字符。同一簇每三行重复一次。第一行使用 第0 簇的符号字符，第2 行使用第3 簇的符号字符，第3 行使用第6 簇的符号字符， 第4 行再使用第0 簇的符号字符，依此类推。行号由上向下递增，最上一行的行号为 1 。 一“攀 南京航空航天大学硕士学位论文 对于一个特定的符号字符，其簇号由下式确定： 簇号= ( 6 1 一b 2 + b 3 一b 4 + 9 ) r o o d 9( 2 1 - 1 ) 式中：b i ，b ，b 、，b 。分别表示自左向右四个条的模块。( 参见图2 2 ) 。 例：对于图2 2 中的符号字符，其簇号计算如下： 簇号= ( 5 1 + 1 2 + 9 3 m o d 9 = 3( 2 1 2 ) 对于每一特定的行，使用的符号字符的簇号由下式计算： 簇号= ( 行号一1 ) m o d 3 3( 2 1 3 ) 2 1 1 3 行指示符号字符 行指示符号字符包括左行指示符号字符( l ) 和右行指示符号字符( r ，) ，分别 与起始符和终止符相邻接。见图2 3 。行指示符号字符的值指示四七条码的行号( f ) 行数( 3 9 0 ) ，数据区中数据符号字符的列数( 1 3 0 ) ，错误纠正等级( o 8 ) 。 睦 k以一、4 一：r终 厶r止 特 符 ，t靠吒一oq 一2r 一： _ 引c 1吒r 一； 图2 。3 数据、行标识符及错误纠正码字位置示意图 其中l ，r 。为左、右行指示符，d i 为数据码字，c ，为纠错码字。 左、右行指示符号字符的值由下式确定，其位置亦可参见图2 i 。 f3 0 x ，+ y ，= 13 0 x ，+ z 【3 0 x ，+ v 当c = o 时 当c = 3 时 当c = 6 时 当c ，= o 时 当c = 3 时( 2 i - 4 ) 当c ，= 6 时 x = i n t 【( 行号一1 ) 3 i = 1 , 2 , 3 - 9 0 ；y = i m 【0 亍弓_ 1 ) 3 ， z = 错误纠正等岛酞3 + ( 行数1 ) r o o d 3 ，v = 数据区的列数一1 ，c ，= 第珩的簇号。 例如，如果一个四一七条码的符号为3 行，3 列，错误纠正等级为1 ，那么 ( 三，三：，) 为( 0 ，5 ，2 ) ，( r ，r 2 ，r 3 ) 为( 2 ，0 ，5 ) 。 2 1 2p d f 4 1 7 编码压缩模式 p d f 4 1 7 条形码有三种数据压缩模式：文本压缩模式( t c ) ；字节压缩模式( b c ) ； 数字压缩模式( n c ) 。【1 3 】【“1 2 1 2 1 文本压缩模式f r c ) 文本压缩模式将两个字符以3 0 为基组合成一个码字，该模式在表述文本时效率 较高。它包含四个子模式，分别为大写字母子模式、小写字母子模式、混合型子模式 和标点型子模式。字模式的设置是为了更有效地表示数据，每种子模式选择了文件中 出现频率较高的一组字符组成字符集。在子模式中，每个字符对应一个值( 0 2 9 ) ， 7 v y = 十 + + x x x 0 o o 3 1 j 3 。l i r 二维条形码编译码原理与应用研究 详见参考文献【4 的表三。两个字符对应值以3 0 为基组合成一个码字，这样可以用单 独的码字表示一个字符对，表示字符对的码字由下式计算：码字= 3 0 + l ，h 、l 依次表示字符对中的高位和低位字符值。 2 1 2 2 数字压缩模式( n c ) 数字压缩模式通过从基l o 到基9 0 0 的转换压缩数据。将约3 个数字位用一个码 字表示，在表示数字时效率最高。在数字压缩模式下，将根据下述算法对数字位进行 编码： 1 ) 将数字序列从左向右每4 4 位分为一组，最后一组包含的数字位可以少于4 4 个。 2 ) 对每一组数字： 首先在数字序列前加一位有效数字1 ( 即前导位) ，然后执行基1 0 至基9 0 0 的转 换。 例：数字序列0 0 0 2 1 3 2 9 8 1 7 4 0 0 0 压缩方法如下 首先，对其进行分组，因为它只有十五位，故只有一组： 其次，在其最左边加1 。将得到数字序列1 0 0 0 2 1 3 2 9 8 1 7 4 0 0 0 ； 最后，将其转换为基9 0 0 的码字序列，结果为l ，6 2 4 ，4 3 4 ，6 3 2 ，2 8 2 ，2 0 0 。 译码算法与编码算法相反： 1 ) 将每1 5 个码字从左向右分为一组，( 每1 5 个码字可以转换成4 4 个数字位) ，其中 最后组的码字可以少于1 5 个； 2 ) 对于每一组码字： 先执行基9 0 0 至基l o 的转换，然后去掉前导位1 。 2 1 。2 。3 字节压缩模式( b c ) 字节压缩模式通过基2 5 6 到基9 0 0 的转换，将6 个字节转换成5 个码字，从左到 右进行转换。它有两个模式锁定( 9 0 1 ，9 2 4 ) 。当要表示的字节总数不是6 的倍数时， 用模式锁定9 0 1 ：当所要表示的字节总数为6 的倍数时，用模式锁定9 2 4 。如6 个字 节a 1 、a 2 、a 3 、a 4 、a 5 、a 6 转换为5 个码字s 1 、s 2 、s 3 、s 4 、s 5 ，方法是： a i 2 5 6 5 + a 2 2 5 6 4 十a 3 2 5 6 3 + a 4 2 5 6 2 + a 5 x 2 5 6 + a 。= s 1 9 0 0 4 + s 2 9 0 0 3 + s 3 9 0 0 ：+ s 4 9 0 0 + s 5 注意，上式中a 1 至a 6 均以十进制数形式带入。 若所要表示的字节数不是6 的倍数，除模式锁定码字用9 0 1 外，对于被6 整除所 剩余的字节，每个字节对应一个码字，逐字节用码字表示。另外，以上三种预定义的 压缩模式可以结合使用，通过应用模式锁定转移( l a t c h s h i f t ) 码字，可在一个四一 七条码符号中应用多种模式表示数据。字节压缩模式的算法较为复杂，本文重在以方 法研究为目的，所以将采用字节压缩模式为例。 南京航空航天大学硕士学位论文 2 1 3 起始符和终止符 四一七条码的起始符和终止符是唯一的。自左向右由条开始，起始符的条、空组 合序列为8 1 1 1 1 1 1 3 ，终止符的条、空序列为7 1 1 3 1 1 1 2 1 。 2 1 4 错误纠正码字 四一七条码的错误纠正等级可由用户选择。每种错误纠正等级所对应的错误纠正 码字数目见表2 - 1 。对于一个给定的错误纠正等级，其错误纠正容量由下式确定 p + 2 t d - - 2 = 2 ”1 - - 2 ( 2 i 一5 j 式中，e 为拒读错误数目；t 为替代错误数目；s 为错误纠正等级；d 为错误纠正码字 数目。 错误纠正码字的总数为2 。其中两个用于错误检测；其余的错误纠正码字用 于错误纠正。用一个错误纠正码字恢复拒读错误，用两个错误纠正码字纠正一个替代 错误。 当被纠正的替代错误数目小于4 时( s = o 除外) ，错误纠正容量由下式确定： + 2 ts d 一3 ( 2 ，l 一6 ) 例如，一个错误纠正等级为3 的四一七条码符号能纠正1 3 个拒读错误或7 个替 代错误，或者为e 和t 的各种组合，但必须满足上述纠正容量条件。 表2 - 1 四一七条码的错误纠正等级 错误纠正等级错误纠正码字数目 02 14 28 31 6 43 2 56 4 61 2 8 72 5 6 b5 1 2 2 2p d f 4 1 7 条码图像的生成 在我们设计的条码编译系统中，计算机编码过程就是将可读信息转换成用于绘制 条码的码字，然后加上必要的附加信息。其流程为：运用编码算法将有用信息转换成 p d f 4 1 7 码字再通过数据库查询把码字转换成对应的条空相间的符号字符，最后在 二维条形码编译码原理与应用研究 计算机上将那些层层相叠的条空绘出。即得到二维条形码图像。其流程简图见图2 4 原始信息( 文符 字，字符，数 缩算法jp d f 4 1 7 码字串( 以l ! ! 窒+ d 百 字，图像，指 叫l 字 l9 2 9 为域的整数)i 坡)符 图2 - 4编码流程简图 以下为编码及绘图的实现步骤，所有源程序均由v i s u a lc + + 实现。 2 2 1 数据码字的生成 在对话框中输入待编码的原始信息，存入字符串变量m i n p u t s t r 。依据压缩算法， 将其转换成p d f 4 1 7 码字序列。我国国标规定汉字用内码表示，内码为两个字节。为 保证和西文兼容且不冲突，目前规定每个字节只用7 位，若两个字节的最高位均为l ， 则该字符为汉字。在编码过程中，对读入的字节进行最高位校验，若连续两个最高位 为1 ，则记录其位置，并将该位清0 。这部分包含较多烦琐的计算，所以在这里我们 用软件流程图说明，如图2 - 5 。 南京航空航天大学硕士学位论文 图2 - 5 码字生成流程图 维条形码编译码原理与应用研究 2 2 2 纠错码字的生成 根据已得的数据码字和选择的纠错等级计算纠错码字。纠错码字的计算包括以下 步骤： 第一步：建立符号数据多项式，表达式为( 2 2 1 ) 。式中多项式系数由数据码字 区的码字成，包括符号长度码字、数据码字和填充码字，排列位置如图2 3 。其中l ， r ，为左、右行指示符d ，为数据码字，c 为纠错码字。 d ( x ) = i x 舾1 + 一一z x 4 _ 2 + 十d , x + d o ( 2 2 1 ) 第二步：建立纠错码字的生成多项式，具有k 个错误纠正码字的生成多项式为 第三步：错误纠正码字的计算。对于一组给定的数据码字和一选定的错误纠正等 级，错误纠正码字为符号数据多项式d ( x ) 乘以 f ，然后除以生成多项式g ( x ) ，所得 余式的各项系数的补数。实现程序较长，请参见 1 5 。这部分数据码字只是原始信息 转换，还没有包括条码的标识符号。由于标识符号的多少是根据条码行数确定，因此 我们先绘制主信息部分，以后再使用同样的绘制流程绘制标识分。 2 2 3 左右行指示符的计算 得到纠错码字之后，根据码字数量选择条码的行数和列数，在码字数组中适当加 入少量空白码字，使图形成工整的长方行。此例中我们选用9 0 0 为空白码。同时，利 用式f 2 1 4 ) ，计算左右行指示符。 到此，我们已经完整地得到了数据码字、纠错码字和指示码字。由于在p d f 4 1 7 条码图像中，码字是由对应的符号字符表示的。所以我们需要检索码字数据库，通过 码字的数值和它的位置确定它所对应的符号字符。 2 2 4 符号字符查询的实现方法 现在要把数据码字转换成p d f 4 1 7 条码的符号字符。这一过程可以通过查询数据 库来实现。注意，这里所指的数据库与一维条形码使用时所附带的信息数据库不同， 所汜录不是产品或服务对象信息，而是码字与p d f 4 1 7 符号字符的对应关系。符号字 符数据库共包含9 2 9 3 = 2 7 8 7 条记录，是一个比较小的数据库。 在v i s u a lc + + 中使用o d b c ( 开放式数据库连接o p e n d a t a b a s ec o n n e c t i v i t y ) 进 行数据查询是比较方便的。建立与o d b c 数据源相连的数据库类c b a r s e t ，它派生自 m f cc r e c o r d s e t 类，属性为s n a p s h o t 。在进行数据检索时要依据两个检索值，分别 南京航空航天大学硕士学位论文 是每一个码字的数值和它所在的簇。其中，码字的数值在之前的编码流程中就已实现。 另一方面，由于我们在知道数据码字和纠错码字的数量之后已经确定了条码图形的行 数和列数，此时可计算出其簇号。利用q u e r y 语句查出与它相应的p d f 4 1 7 符号字符。 除了完成查询之外，为便于在以后的绘图过程中进行信息读取和处理，还需要转换所 得结果的形式，把以字符串为元素的数组转换为以单个字符为元素的数组。 在源程序中，我们将查询到的符号字符按顺序存入c s t r i n g a r r a y 类型( 字符串数 组) 变量r f ls t r i n g a r r a y 中。在以后绘制条码图形时我们会注意到，需要知道每个符 号字符的条和空所对应的模块宽度，以确定它们的相对位置，所以要把符号字符转换 单个字符。于是我们建立c s t r i n g 类型( 字符串) 变量w h o l e s t r 。将i ns t r i n g a r r a y 中 的符号字符首尾相连存入w h o l e s t r 中。选用s t r c a t 函数进行字符拷贝。它的原形为： c h a r + s t r c a t ( c h a r + s t r d e s t i n a t i o n ，c o n s t * s t r s o u r c e ) 。注意，执行s t r c a t 之前需要为 w h o l e s t r 开辟数据缓冲区，执行结束后需将缓冲区释放。 为增加程序的通用性，实现查询功能的程序参数选用指针类型变量p a r r a y ，它当 前为指向记录原始信息码字的数组的指针，以后它还可以根据需要指向记录左右层指 示符或者起始终止符的数组。 2 2 5 绘制条码图形 同数据库检索符号字符一样，绘制条码图形之前要确定图形的行数和每行的码字 数，进而确定每个符号字符在图形上的位置。在这里我们选用的方法为：将压缩后所 得的信息字符串w h o l e s t r 中的单个字符转化为整形数，选用字符数“1 ”所对应的条 的宽度( 即1 个模块宽度) 作为绘图的“笔宽”i ni n t w i d t h ，根据所需条码图形的高 度选定模块的长度mi n t h e i g h t 。再依据其黑白相间的特性确定各个条空的起始点和 终止点的坐标。( 注意考虑每个码字的位置) 。最后运用v i s u a lc + + g d i 绘图功能中 的c d c 函数在屏幕上实现条码的绘制。 假如w h o l e s t r 字符串中有一个符号字符5 1 1 2 1 3 2 2 ，对它的处理过程应是，将每个 条和空所包含的模块数转换成整数，即：5 个模块( 条) ，1 个模块( 空) ，1 个模块 ( 条) ，2 个模块( 空) 再按这个顺序绘图：画5 笔黑，跳过1 个模块宽度，再 画1 笔黑，跳过2 个模块宽度在这里，我们使用画笔的概念来描述是为了便于读 者理解，在编程时，鉴于条码图像的大小要具有可调节性，使用g d i 画笔( c p e n ) 可能会导致图像在被放得较大时边缘出现毛刺。所以我们使用黑色g d i 画刷( c b r u s h ) 来填充包含数个模块宽的“条”。可见，问题的关键是根据符号字符和它的位置确定 每一个“条”所对应的矩形框的四个顶点的坐标。 由p d f 4 1 7 每个符号字符包含8 个条空，且条空相间这一特性可知，如果某符号 字符在字符串中的顺序位置号能被2 整除，则它必为“条”。假设该字符串中某一“条” 符号字符为c ，则读取c 的位置并将符号字符转换为整数形式，i n t k = a t o i ( c ) 。 】1 二维条形码编泽码原理与应用研究 c p o i n t 类型变量m _ u p p o s 记录某一“条”( 黑色矩形) 的左上角顶点的坐标， m b o t t o m p o s 记录该“条”的左下角顶点的坐标，则可根据该起始点的位置和条空字 符的宽度，确定每个条块的四个顶点坐标。然后，我们需要将所有顶点的坐标都保存 入点数组中。 除此之外，还要注意不同行的各个码字之间相对位置的差别，以整个条码图像的 左上顶点m l e f t s t a r t p o s 为参照点，第j 行第一个“条”矩形的起点就是 n l u p p o s x = m _ l e f t s t a r t p o s x ； m _ u p p o s y = m l e f l s t a r t p o s y + j x m _ i m h e i g h t 。 在确定每点的坐标之后，就可以用m i c r o s o f tv c + + m f c 的画刷( c b r u s h ) 对象 为各个“条”矩形着色，连接各点，轻易绘制出二维条形码的图形了。 图2 - 6 就是该程序的编码结果，一个2 5 行的二维条码图像，图像的大小可根据 使用需要任意调节。 厦蛤信息n o n j l n gu n i v er s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s 南京航空航天大学自动化学院藏扬 圳隆羹睡睡陵_ i 图2 - 6 编码实验结果 南京航空航天大学硕士学位论文 第三章r e e d - s o l o m o n 纠错码在p d f 4 1 7 条码中的应用 3 1r s 码原理简介 p d f 4 1 7 二维条形码之所以具有纠错能力强、译码可靠性高等诸多的特点，是由 于它采用了目前世界上最先进的纠错码技术之一，r e e d - - s o l o m o n ( r s ) 错误控制码。 r s 码的纠错能力非常强大，尤其是对那些突发性的成片干扰特别有效 6 1 。显著地提 高了p d f 4 1 7 码的抗干扰能力和可靠性。r s 码具有卓越的性能，但是实现r s 纠错算 法的计算量很大，尤其当纠错级数较大时，对速度的影响非常大，目前使用的r s 码 纠错算法主要是b e r l e k a m p m a s s e y 算法( b m 算法) f 1 6 删【1 ”，为提高其运算速度， 国内外学者都开展了很多相关研究。方向大致分为两种，一种是在算法上对b m 算法 加以改进，比如文献 1 9 2 0 2 1 】 2 2 】，另外一种是结合四一七条码中纠错码的域结构 特点，设计一些技巧性的解决方案，比如文献【2 3 就利用g o o d t h o m a sf f t 算法， 将四一七条码在伽罗华域g f ( 9 2 9 ) 内分解成两个正交的子集，以达到减小计算量的目 的。在本文中，我们选用相对成熟的b m 算法确定错误位置，f o m e y 算法确定错误 幅值i ”，对其选用合适的参数，应用于p d f 4 1 7 条码纠错。 3 1 1 数学预备知识 定理l 欧几里德算法 给定任意正整数a 、b ，必存在有整数a 、b 使 ( a ，b ) = a a + b b 其中，f a b ) 为a ，b 的最大公约数。( 证明略) 。 定义1 若两个整