（通信与信息系统专业论文）基于存储函数变换的pdf417码译码的研究与实现.pdf

摘要 摘要 二维条码技术是在一维条码基础上发展起来的应用领域非常广泛的一种新 兴自动识别技术，在许多国家被推广应用。在众多二维条码中，p d f 4 1 7 的应用 最为广泛。 国外的二维条码技术已经处于应用阶段，已经有了性能较好的二维条码识 别系统，而我国与国外水平还有很大差距。其主要原因是识读系统的高成本， 所以我们研究的重点是侧重于p d f 4 1 7 的自动识别部分，即译码部分的研究。 本课题的主要任务是p d f 4 1 7 二维条码图象的读取和识别。二维条码图象的读 取是由图象读取装置完成的，采用基于a v r 高速单片机的译码系统。这种系统 可实现便携式译码以及保证条码的安全性。 关键字：p d f 4 1 7 ，存储器函数变换，译码，嵌入式系统，信息安全 a b s t r a c t a b s t r a c t 2 db a r c o d ei sal a t e s ta u t o m a t e d b a r c o d e w h i c hi s w i d e l yu t i l i z e di n b a r c o d ei sm o s tw i d e l yu s e d r e c o g n i t i o nt e c h n o l o g yd e v e l o p e df r o m 1d m a n yc o u n t r i e s ，a m o n gw h i c ht h ep d f 4 17 i nf o r e i g nc o u n t r i e s ，2 db a r c o d et e c h n o l o g yh a v ea l r e a d yb e e na p p l i e di nm a n y f i e l d s ，a n dt h e yh a v ep r o d u c e d2 db a r c o d ei d e n t i f ys y s t e mi ng o o dp r o p e r t y w eh a v e d r o p p e db e h i n dt h ef o r e i g nc o u n t r i e sg r e a t l y t h em a i nf a c t o r i st h a t2 db a r c o d e i d e n t i f ys y s t e m s a r es o l dt o o e x p e n s i v e l y , t h e r e f o r e o u rr e s e a r c hf o c u so n a u t o i d e n t i f yo fp d f 4 17 ，n a m e l y , t h er e s e a r c ho fd e c o d ea r i t h m e t i c t h i sp a p e rd i s c u s s e sa c q u i r i n gi m a g eo fp d f 4172 da n dr e c o g n i t i o no fi t i m a g ei s a c q u i r e db yi m a g es e n s o r t h er e c o g n i t i o ns y s t e mi sb a s e do na v r k e yw o r d ：p d f 417 ，s t o r a g ef u n c t i o n ，d e c o d i n g ，e m b e d d e ds y s t e m ，d a t a s e c u r i t y i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：桶回良 五觏步年岁月2 多日 经指导教师同意，本学位论文属于保密，在三年解密后适用 本授权书。 指导教师签名： 拆磊范 学位论文作者签名： 杨国良 i 解密时 间： 2 0 哆年5 月3 d 日 各密级的最长保密年限及书写格式规定如下： f i ；i ；赢三；? ；孬j 甭_ 。 | 秘密1 0 年( 最长l o 年，可少于1 0 年) ， l 机密2 0 年( 最长2 0 年，可少于2 0 年) l 。，一。：。：二。、： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：万杨国良 工o d 步年2 , - 5 月2 日 第一章绪论 第一章绪论 第一节二维条形码简介 条码技术自本世纪7 0 年代初期问世以来，很快得到了普及并广泛应用到工 业、商业、国防、交通运输、金融、医疗卫生、邮电及办公室自动化等领域。 但是由于一维条码的信息容量很小，如商品上的条码仅能容纳1 3 位的阿拉 伯数字，更多的描述商品的信息只能依赖数据库的支持，离开了预先建立的数 据库，条码本身就没有意义了，因而条码的应用范围受到了一定的限制。基于 这个原因，人们迫切希望发明一种新的条码，除具有普通条码的优点外，同时 具有信息容量大、可靠性高、保密防伪性强、易于制作、成本低等优点。二维 条码的诞生满足了人们的这种需求，它能够在横向和纵向两个方向上同时表达 信息，不仅能够在很小的面积内表达大量的信息，而且能够表达汉字和存储图 象，扩展了条码的应用领域。在二维条码中，性能突出，应用最为广泛的是1 9 9 1 年正式推出的名为p d f 4 1 7 的二维条码，简称为p d f 4 1 7 条码，即“便携式数据文 件 。 1 1 1p d f 4 1 7 条码的特点 p d f 4 1 7 条码是一种高密度、高信息含量的便携式数据文件，是实现证件及 卡片等大容量、高可靠性信息自动存储、携带并可用机器自动识读的理想手段。 p d f 4 1 7 条码具有如下特点： ( i ) 信息容量大 根据不同的条空比例每平方英寸可以容纳2 5 0 n i i 0 0 个字符。在国际标准的 证卡有效面积上( 相当于信用卡面积的2 3 ，约为7 6 m m * 2 5 m m ) ，p d f 4 1 7 条码可以 容纳1 8 4 8 个字母字符或2 7 2 9 个数字字符，约5 0 0 个汉字信息。这种二维条码比普 通条码信息容量高几十倍。 第一章绪论 ( 2 ) 编码范围广 p d f 4 1 7 条码可以将照片、指纹、掌纹、签字、声音、文字等凡可数字化的 信息进行编码。 ( 3 ) 保密、防伪性能好 “ p d f 4 1 7 条码具有多重防伪特性，它可以采用密码防伪、软件加密及利用所 包含的信息如指纹、照片等进行防伪，因此具有极强的保密防伪性能。 ( 4 ) 译码可靠性高 普通条码的译码错误率约为百万分之二左右，而p d f 4 1 7 条码的误码率不超 过千万分之一，译码可靠性极高。 ( 5 ) 修正错误能力强 p d f 4 1 7 条码采用了世界上最先进的数学纠错理论，如果破损面积不超过5 0 ，条码由于沾污、破损等所丢失的信息，可以照常破译出丢失的信息。 ( 6 ) 容易制作且成本很低 利用现有的点阵、激光、喷墨、热敏热转印、制卡机等打印技术，即可在 纸张、卡片、p v c 、甚至金属表面上印出p d f 4 1 7 - - 维条码。由此所增加的费用仅 是油墨的成本，因此人们又称p d f 4 1 7 是“零成本 技术。 ( 7 ) 条码符号的形状可变 同样的信息量，p d f 4 1 7 条码的形状可以根据载体面积及美工设计等进行自 我调整。 1 1 2p d f 4 1 7 与i c 卡及磁卡技术的比较 在证卡技术的应用上，p d f 4 1 7 条码卡及i c 卡、磁卡技术比较如下： 磁卡 优点：可读可写，成本略高于p d f 4 1 7 - - 维条码卡； 缺点：1 信息容量小，常依赖于外界的数据库； 2 保密防伪性差； 3 可靠性低，易受电磁场干扰而损毁信息； 4 寿命短( 1 年) 。 2 第一章绪论 工c 卡 优点：信息容量大，可读可写； 缺点：1 成本高，i c 卡的成本通常是p d f 4 1 7 条码卡的3 - 5 倍； 2 寿命短( 2 - 3 年) ，易于折毁： 3 可靠性差，易受外界强磁场干扰而损毁信息； 4 保密防伪性相对较差，信息可改写既是i c 卡的优点，同时亦成为i c 卡 的缺点，为伪造信息留下契机。 p d f 4 1 7 - - 维条码卡 优点：1 信息容量大、保密防伪性强、可靠性高； 2 成本低，按照材料的不同选用载体，一张p d f 4 1 7 条码卡，价格最多几 元钱人民币，甚至几角几分即可实现； 3 寿命长，p d f 4 1 7 - - 维条码卡的寿命可达8 、9 年( p v c 卡) 。 缺点：信息不可改写。这点恰恰增强了二维条码卡的防伪能力。 通过上述分析，可以看出，二维条码卡几乎包容了磁卡和i c 卡的所有优点。 唯一的缺点是不可改写，而如果为了增强证卡的保密防伪性，对于证照等不需 经常改写的应用场合，信息不可改写恰恰增强了证卡的保密防伪性能。 第二节二维条码p d f 4 17 的应用 二维条码p d f 4 1 7 做为一种新的信息存储和传递技术，从诞生之始就受到了 国际社会的广泛关注。经过几年的努力，现已广泛地应用在国防、公共安全、 交通运输、医疗保健、工业、商业、金融、海关及政府管理等领域。 美国亚利桑那州等十多个州的驾驶证、美国军人证、军人医疗证等几年前 就已采用了p d f 4 1 7 技术。将证件上的个人信息及照片编在二维条码中，不但可 以实现身份证件的自动识读，而且可以有效地防止伪冒证件事件的发生。菲律 宾、埃及、巴林等许多国家也已在身份证或驾驶证上采用二维条码，据不完全 统计，准备在身份证或驾驶证上采用二维条码p d f 4 1 7 的国家已达4 0 多个，我国 对香港地区恢复行使主权后，香港居民新发放的特区护照上采用的就是二维条 码p d f 4 1 7 技术。 第一章绪论 除了证件上，在工业生产、国防、金融、医药卫生、商业、交通运输等领 域，二维条码同样得到了广泛的应用。 第三节本课题的意义 由于二维条码具有成本低，信息可随载体移动，不依赖于数据库和计算机网络、 保密防伪性能强等优点，结合我国人口多、底子薄、计算机网络投资资金难度 较大，对证件的防伪措施要求较高等特点，可以预见，p d f 4 1 7 条码在我国极有 推广价值。但是目前由于大部分技术及设备都需从国外引进，使用成本非常高， 因此目前实际应用范围还很小，只有开发出拥有自主知识产权的编译码设备， 才能够降低使用成本，促进二位维条码的普及应用。我国于9 7 年1 2 月正式颁 布了p d f 4 1 7 条码国家标准四一七条码。已经开始了相关的研究和推广应用。 4 第二章p d f 4 1 7 码的识读算法 第二章p d f 4 17 码的识读算法 第一节p d f 4 17 条码的结构概述 p d f 4 1 7 条码符号是一种多层、可变长度、具有高容量和错误纠错能力 的连续性二维条码。相当于一维条形码在纵向上的叠加。符号的最小成份 叫模块，模块是一种代表规定长度的物理量，其宽度为0 3 3 mm 。组成条 码符号的基本单元是条和空，简称码元，码元由模块构成。p d f 4 1 7 条码 的可编码字符集包括全a s c i i 字符及扩展a s c i i 字符或8 位二进制数据， 多达8 1 1 8 0 0 种；含有2 - 5 1 2 个错误纠正码词，具有字符自校验功能；条 码符号是连续多行类型，符号尺寸可变，其最小行数为3 ，最大行数为9 0 。 宽度为9 0 - - 5 8 3 个模块，双向可读。p d f 4 1 7 条码符号顶部和底部为空白区， 上下空白区之间是多行( 3 - 9 0 行) 结构，各行符号字符数相同。行与行左右 对齐直接衔接。每行由左空白区，起始符，左行指示符，1 3 0 个数据符号字 符，右行指示符、终止符，右空白区组成。以下为一个7 行的p d f 4 1 7 条码， 每行自左向右结构如图1 一l ： 起始符号 左行指示符 数据码词 右行指示符 终止符 陆哦暾啭 图2 一lp d f 4 1 7 条码结构示意图 每个字符由4 个条和4 个空( 码元) 构成，自左向右从条开始，每个码元含1 6 第二章p d f 4 1 7 码的识读算法 个模块，在一个符号字符中，4 个条和4 个空的总模块数为1 7 。 条码由取值0 q 2 8 的9 2 9 个码词组成码词集，其中：0 8 9 9 码词根据当前的压 缩模式和全球标记标识符( g l i ) 解释，用于表示数据；9 0 0 ，9 0 1 ，9 0 2 ，9 1 3 ，9 2 4 码词用模式识别；9 2 5 ，9 2 6 ，9 2 7 用于g l i ；9 2 2 ，9 2 3 ，9 2 8 用于宏“四一七 条码；9 2 1 用于阅读器初始化；其余码词保留待用。 p d f 4 1 7 条码的符号字符集可分为三个独立的子集即三个簇，每一簇均以 不同的条、空形式表示所有9 2 9 个p d f 4 1 7 的码词。在每一簇中，每一符号字符 对应唯一的码词，其范围为0 - - - 9 2 8 。四一七条码使用簇号0 、3 、6 。条码的每 行只使用一个簇中的符号字符。同一簇每三行重复一次。第一行使用第0 簇的 符号字符，第2 行使用第3 簇的符号字符，第3 行使用第6 簇的符号字符，第4 行再使用第0 簇的符号字符，依此类推。行号由上向下递增，最上一行的行号 为1 。对于一个特定的符号字符，其簇号由下式确定： 簇号= ( b l - - b 2 + b 3 - - b 4 - i - 9 ) m o d 9 式中：b 1 ，b 2 ，b 3 ，b 4 凡分别表示自左向右四个条的 模块。 b 2b 3b 4 图2 - 2p d f 4 1 7 的条空结构 对于每一特定的层，使用的符号字符的簇号由下式计算： 簇号= ( 层号) m o d 3 3 由此可见，p d f 4 1 7 条码采用三种不同的符号字符集，且任何相邻两行使用不同 模式的符号字符集，这样的编码模式使得扫描器可以在高信息密度的情况下仍 能快速准确地识读代码。 图( 2 3 ) 表示普通p d f 4 1 7 符号的层结构，每层中的字符数和行数都可调整以 适应不同需要每行都有左层、右层的指示符，中间是数据区，数据区的第一个 码词表示数据区的总字符个数( 错误校验码除外) ，对应一组给定的数据码词和 错误纠正级别，根据r e e d - - s o l o m o n 错误控制码算法计算出错误纠正码词，错 6 第二章p d f 4 1 7 码的识读算法 误纠正码词跟在数据码词之后，若条码数据区未满，则应在数据码词和校验码 词之间加入若干个填充码词。 一 l o d 。一1d 。- 2r o l lr 1 起 终 始 止 符符 l ，2d 0 c k l c k 一2 r 毗 l i _ lc lc or ，l 图2 - 3 数据、层标识符及错误纠正码词位置示意图 图中l i ，r i 为左右层指示符，d i 为数据码词，c i 为纠错码词。左、右行指示符的 值有下式确定， 3 0 x i + y 当b i = 0 时 l i = 一3 0 x i + z 当b i = 3 时 i 3 0 x i + v 当b i = 6 时 、 r 3 0 x i + v当c i = 0 时 r i = 一3 0 x i + y 当c i = 3 时 i3 0 x i + z 当e l = 6 时 x i = i n t ( 层号3 ) i = o ，1 ，2 ，3 8 9 ： y = i n t ( 层号一1 ) 3 ： z = 错误纠正等级3 + ( 层数- 1 ) m o d 3 ： v = 每层列数- 1 ： b i = 第i 层的簇号 错误纠正码词根据r e e d - - s o l o m o n 错误纠正码算法计算生成，它可以将由 于条码符号破损、沾污等丢失的信息恢复，最高时，可将符号受损面积达5 0 的条码符号所含信息复现出来。在美国国防部举办的管理数据库测试中，阅读 2 0 0 0 万个p d f 4 1 7 条码，没出现一例译码错误，证明该算法具有极高的可靠性。 每一个p d f 4 1 7 条码至少包含两个错误纠正码词，用于对符号字符的错误检 测与纠正。 7 第二章p d f 4 1 7 码的识读算法 p d f 4 1 7 条码共有9 种错误纠正等级，用户可自行选择。 i 错误纠正等级 0 l 12345678 i 错误纠正码词数目 2 i 481 63 26 41 2 82 5 65 1 2 图2 - 4p d p 4 1 7 条码的错误纠正等级表 条码识读错误主要包括拒读错误和替代错误两种。对于一个给定的错误纠错等 级，其纠错纠正容量由下式所示： e 十2 t d 一2 = 2 s + 1 2 其中，e 为拒读错误的数目，t 为替代错误的数目，s 为错误纠正等级，d 为错 误纠正的码词数量。不同数量的编码数据所对应的错误纠正等级推荐值如下表 所示。在条码易损坏的场所，应选用较高的错误纠正等级。在封闭式系统中， 可选用低于推荐错误纠正等级的错误纠正等级。 数据码词数 1 4 04 0 1 6 01 6 1 3 2 03 2 1 8 6 3 p d f 错误纠正等级2 345 图2 - 5p d f 4 1 7 条码的推荐错误纠正等级表 p d p 4 1 7 四一七条码的起始符和终止符是唯一的。自左向右由条开始，起始 符的条、空组合序列为8 1 1 1 1 1 1 3 ，终止符的条、空序列为7 1 1 3 1 1 1 2 1 。 p d f 4 1 7 条码符号可以印刷成多种密度，以适应不同的印刷及扫描条件的要 求，但符号的模块宽度( x ) 不得小于0 1 9 1 m m 。条码的左、右、顶部、底部的 空白区不得小于2 个模块宽度。对于己达到推荐的最低错误纠正等级的p d f 4 1 7 条码符号，其推荐的最小行高为3 x ；对未达到推荐的最低错误纠正等级的p d f 4 1 7 条码符号，其最小行高应为4 x 。 8 第二章p d f 4 1 7 码的识读算法 p d p 4 1 7 还有另外几种条码形式。在相对“干净”的环境中，条码损坏的可能性 很小，右行指示符可以省略，终止符可以减为1 个模块宽度的条，这种条码称为 截短p d f 4 1 7 条码。当文件内容太长，无法用一个p d f 4 1 7 条码符号表示时，可以 利用用宏p d f 4 1 7 ，将大文件分成几个块来表示。宏p d f 4 1 7 条码与普通d f 4 1 7 条码 不同之处是多了一个控制块( m p c b ) ，包含块索引、文件标识等信息。在解码时， 多个宏p d f 4 1 7 条码可根据控制块信息将各分块的扫描解码结果按顺序重新正确 的连接起来，而不需要考虑扫描器阅读的顺序。通过宏p d f 4 1 7 条码，一个文件 可以用1 - - 9 9 9 9 9 个条码符号分块表示出来。 第二节p d f 4 17 的译码算法 p d f 4 1 7 的译码算法是以测量条码符号的边缘到相似边缘的距离为基础的，具体 步骤为： ( 1 ) 测量七个宽度值t 1 ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ，t 7 如下图 iiii t 2t 4t 6 ( 2 ) 将测量值t 1 ，t 2 t 7 转换为常数值t 1 ，t 2 ，t 7 ，t 序列代表 这些测量值的整数模块宽，以下方法用于t 序列值的求取： 若1 5 p 1 7 、 t i 2 5 p 1 7 那么t i = 2 若2 5 p 1 7 弋 t i 3 5 p 1 7 那么t i = 3 若3 5 p 1 7 t i 4 5 p 1 7 那么t i = 4 9 第二章p d f 4 1 7 码的识读算法 若4 5 p 1 7 4 t i4 5 5 p 1 7 那么t i = 5 若5 5 p 1 7 t i4 6 5 p 1 7 那么t i = 6 若6 5 p 1 7 4 t i 4 7 5 p 1 7 那么t i = 7 若7 5 p 1 7 4 t i4 8 5 p 1 7 那么t i = 8 若8 5 p 1 7 t i 9 5 p 1 7 那么t i = 9 否则表明出现错误。 计算过程如下 t = o ： f o r ( i = o ：i 8 ：i + + ) w h i l e ( p i x e l i m a g a r r a y l i n r n u m b e r m 1 i = = t ) i = i + l ： c o u n t 0 i = c o u n t 0 i + 1 ： t t ： f o r ( i = o ：i 7 ：i + + ) t i = 0 ； t i = c o u n t o i + c o u n t 0 i 十1 ：) w = t 0 + t 2 + t 4 + t 6 ： p = w 1 7 ； f o r ( i = o ：i 7 ：i + + ) t i = c e i l ( t i p ) ： p r i n t f ( “t d = d ，i ，t i ) ： ) ( 3 ) 计算码词簇号 簇号= ( t 1 - t 2 + t 5 - t 6 ) m o d 9 簇号取值为0 ，3 或6 ，否则错误 ( 4 ) 用以下7 个值( 簇号，t 1 ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ，t 7 ) 在译码表中查出码词所对 应的符号字符。 再应用p d f 4 1 7 条码的解码和显示程序，将条码所代表的信息显示出来。 解码过程 i o 第二章p d f 4 1 7 码的识读算法 圈 r i 数据库查询 条碉 码词 1 的 接收数据，放入数组a 9 2 6 ，码词个数为m 土 分析a 【i 】 上 1 r1r1r1 r1 r1r i f a i ：i f a i =i f a i = i f a i 】=i f 正在i f 转移 9 0 0 9 0 1 ，9 2 4 9 0 29 1 3 转移，备 完成，恢 上j上上 份当前复当前 文本解 字节解数字解发生转 压缩模模式 压缩压缩压缩移 式 上j上上 上上 上 码词分析县否完了 n ”7 。y 。7 。7 h u 。 i 解码结果 r 显示程序 图2 - 6 解码过程 第二章p d f 4 1 7 码的识读算法 2 2 1 文本压缩模式解码算法 文本压缩模式是每一符号起始的默认有效的压缩格式，3 有分为四个子模 式，其解码算法的基本步骤为： 第一步；输入编码码词序列的转换 建立三个队n l l ，l 2 ，l 3 ，队y i j l l 用来存放输入的编码码词序列，l 2 用来存放转 换后的解码信息序列，l 3 存放解码信息序列数据的a s c i i 值。 每个编码码词数据m 通过到基3 0 的转换生成两个解码信息数据d h 和d l ， d h = m 3 0 ，d l = mm o d3 0 把d h 和d l 依次存放至t j l 2 中。 第二步：将队歹i j l 2 中的解码信息序列中数据转换成a s c i i 码值。 队歹l j l 2 中的信息数据的范围为0 2 9 ，通过查表得到他们对应的a s c i i 值，并存 放到队歹l j l 3 中。 第三步：通过显示程序将l 3 中a s c i i 码显示出来。 2 2 2 字节压缩模式解码算法 字节压缩模式是通过基2 5 6 至基9 0 0 的转换，将字节序列转换为码词序列， 在对应用字节压缩模式的码词序列进行解码时，过程与此相反，通过基9 0 0 虱j 2 5 6 的转换，将编码码词序列转换为字节序列。基本步骤为： 第一步：输入编码码词序列分组 建立一个队歹i j l , 1 用来存放输入的编码码词序列。如果是模式锁定9 2 4 ，则编码码 词序列的长度正好是5 的倍数，把这些编码码词序列按先后顺序每5 个为单元分 成组；如果是模式锁定9 0 1 ，则把这些编码码词序列按先后顺序每5 个为单元分 成组，最后一组可以少于5 个。 第二步：编码码词序列的转换 建立一个队列l 2 ，l 2 用来存放转换后的解码信息序列。如果是模式锁定9 2 4 ，则 通过基9 0 0 至i j 2 5 6 的转换，将每组5 个编码码词转换成6 个字节。如果是模式锁定 9 0 1 ，则前面的码词组的转换同模式锁定9 2 4 卡h 同，最后一组原样输出。 第三步：通过显示程序将l 2 中字节信息显示出来。 1 2 第二章p d f 4 1 7 码的识读算法 图2 7 字节压缩模式解码流程图 2 2 3 数字压缩模式解码算法 数字压缩模式是从基1 0 到基9 0 0 的转换将数字信息转换成条码码词，在对数 字压缩模式解码时，就是完成从基9 0 0 至u 基1 0 的反向转换。 第一步：将每1 5 个码词从左向右分为一组，最后一组码词可以少于1 5 个。 第二步：对于每一组码词：先执行基9 0 0 銎j 1 0 的转换，然后去掉前导1 。 第三步：将解码后的各组信息数据输出。 第二章p d f 4 1 7 码的识读算法 图2 - 8 数字压缩解码流程图 1 4 第二章p d f 4 1 7 码的识读算法 2 2 4 错误纠正码的译码算法 r s 译码的步骤大致可以分为三步： 1 、由接收到的信息计算出伴随式s ； 2 、由伴随式找出错误图样，也就是码词的错误位置和错误幅值； 3 、由已确定的错误位置和错误幅值修正接收到的信息，得到最有可能发送 的原始信息，完成译码。 伴随式s 。的定义及计算 n - 1 假设原始传输码词表达式为v ( x ) = u “g f ( 2 m ) ) n - i 传输过程中发生错误，接收到的码词表达式为“x ) = r , x ( r i g f ( 2 m ) ) 。 i = o n - 1 则令e ( x ) 为错误图样，表达式为e ( x ) = q x g f ( 2 m ) ) i - - q ) r ( x ) = v ( x ) + e ( x )( 2 2 一1 ) 对于可能包含错误的接收到的码词表达式r ( x ) n - i r ( x ) = r t x r ( x ) 2 乙 i = o ( 2 2 2 ) r ；为接收码词，其中包含错误。由于v ( x ) 是不包含错误的原始表达式，所以令 e ( x ) 为错误图样，用纠错码生成多项式g ( x ) 的各个零点a ，( j = l ，2 ，2 t ) 对r ( x ) 求值，其结果定义为伴随式s ，。由于v ( 酽) = 0 ，可得： s j = r ( a 3 ) = v ( a ) + e ( a 3 ) = e( 2 2 - 3 ) 如果s j _ o ，认为接收无误。若s j o ，则由s ，找出错误图样。假设r ( x ) 包含r 个错 误( o r t ) ，它们发生在未知位置i 。i ，上，于是差错多项式e ( x ) 又可以写成 e ( x ) = e i l x i l + e i 2 x i 2 + e l 。x l r( 2 2 4 ) 其中e u - e 垤为各个错误位置上错误值与正确值之差，也就是错误幅值。用a 对接收多项式求值可以得到伴随式s 。：s t = e ( a ) = e 。a “+ e ，：a 坦+ e 。，a h 。为简化记 号，我们令错误幅值y 。= e n ，错误位置x 。= a n ，i ，是第1 个差错的实际位置，而 x ，是对应这些位置的域元素( 1 = 1 ，2 ，r ) 。于是有s 。= y ，x 。+ y ：x ：+ y ，x ，。同理，用 a 的各次幂，也就是r s 码生成多项式的零点，对差错多项式s 。求值，可得到下 1 5 第二章p d f 4 1 7 码的识读算法 面2 t 个方程的方程组。 s l = y l x l + y 2 x 2 + y , x ， s ：= y ，( x 。) 2 + y 。( x ：) 2 + y ，( x r ) 2 ( 2 2 5 ) s 2 t - - y 1 1 ) 2 t + y 2 ( x 2 ) 2 t + y r ( x r ) 2 x 、y 、r 都是未知的，必须通过计算来获得，从而纠正差错。 求错误位置x i 以及错误幅值y i 的算法 。( x ) = 兀( 1 一城) ( o r t ) ( 2 2 - 6 ) 差错位置。我们试图从伴随式s 计算o ( x ) 各项系数。将o ( x ) 展开，令系数分别 匪姚： = - 引 固 1 6 第二章p d f 4 1 7 码的识读算法 图2 - 9r s 纠错译码的流程图 1 7 第三章码识读模块的意义 第三章码识读模块的意义 由于p d f 4 1 7 条码的优越性能，使得它在各行各业中有广泛的应用前景，作 为一种便携式数据文件，甚至可以做为电子数据交换( e d i ) 的载体。目前在美国 等发达国家，二维条码已经在一些实际应用领域中崭露头角。 现在使用的p d f 4 1 7 的解码方式是首先按照p d f 4 1 7 解码算法，编写好实现 不同解码功能的各个模块，把它们做成d l l 动态链接库，它包括若干个不同的 功能的模块，如数据读取，数据解码，纠错、左右行指示符解码，条码符号的物 理特性( 长，宽等) 确定，条码符号输出的格式( d i b ，c o d e b a r ，p a t t e r n s ) 等 功能。然后编写一应用程序，在应用程序中调用这些动态链接库，来实现二维 条码的解码以及显示、打印功能。这种方法实际上是通过软件进行解码，有很 大一个缺陷就是它不能脱离计算机的存在。另外二维条码作为一项自动识别技 术虽然具有高速识读和高可靠性的特点，但是二维条码并不是专用信息安全技 术，本身所具有的安全能力有限，解码程序一旦被非法复制使用，信息安全就 得不到保证。这样严重制约了二维条码在一些对信息安全要求较高的领域中的 应用。 所以本次论文将按照p d f 4 1 7 解码算法，利用s o c 阻3 进行解码，将编写好的程序 输入到s o c 芯片中。形成二维条码解码芯片，同时把防伪加密技术应用在p d f 4 1 7 二维条码上，运用密码学的原理，把密钥的私钥和公钥体制与二维条码技术结 合起来，克服二维条码所载信息传输时，容易被破译和复制的缺点。由于智能 卡是具有体积小、便于携带、安全性高等特点，并有一定的数据存储和数据处 理能力同时包含很多安全特性，能够保护卡片内部的敏感信息在密码算法 中私钥的保护是最关键的，而智能卡能够保证私钥在卡内生成并永远不会泄 漏到卡外同时由干受智能卡的存储容量和计算速度的限制，在智能卡内很难 实现密码算法所以本文采用智能卡结合嵌入式单片机( a t 8 9 c 5 1 ) 实现信息安 全算法。最后在应用中添加必要的输入输出设备( 如c c d 、l c d 、打印机) ，就可 以实现对p d f 4 1 7 符号的解码。 1 8 第四章面向行业信息安全的算法 第四章面向行业信息安全的算法 第一节密码学基本概念阳1 密码学包括两个方面：密码编码学和密码分析学，密码编码学就是研究对 数据进行变换的原理、手段和方法的技术和科学，其目的是隐藏数据的真实内 容。密码分析学是为了取得密码的消息，而对密码系统及其数据进行分析、攻 击的技术和科学。 密码学的理论基础是数学。它的基本思想就是隐藏伪装信息，使未经授权者不 能得到消息的真正含义，伪装信息的方法就是进行一组可逆的数学变换，伪装 之前的原始信息，称为明文。伪装之后的信息，看起来是一串无意义的乱码， 称为密文。把明文伪装成密文的过程称为加密，该过程使用的数学变换就是加 密算法。把密文还原成明文的过程称为解密，该过程使用的数学变换，通常是 加密时数学变换的逆变换，就是解密算法。加密与解密通常需要参数控制，该 参数称为密钥，有时也称为密码，加密时使用的叫加密密钥，解密时使用的叫 解密密钥，加密与解密密钥可能相同，也可能不同，相同时就称为对称型或单 钥型，对称密码体制中，影响系统安全的关键是密钥的管理。典型的加密算法 是d e s 算法。不同时就称为非对称型或双钥型。它的典型算法是r s a 算法。 一个密码体制是由明文空间、密文空间、密钥空间、加密算法和解密算法五个 部分组成。明文、密文、密钥空间分别表示全体明文、全体密文、全体密钥的 集合，加解密算法是一些公式法则或程序，规定了明文与密文之间的数学变换 规则。 下面用字母分别表示这个概念：密钥k = ，k e 表示加密密钥，k d 表示解 密密钥，设明文m ，密文c ，加密算法e ，解密算法d 。 把明文变为密文：c = e ( m ，k e ) 把密文解密为明文：m = d ( c ，k d ) = d ( e ( m ，k e ) k d ) 1 9 第四章面向行业信息安全的算法 第二节d e s 算法 d e s 算法是分组长度为6 4 比特的分组密码算法，它以6 4 位分组对数据加密。 6 4 位一组的明文从算法的一端输入，6 4 为的密文从另一端输出。d e s 加密解密 用的是同一算法。密钥的长度也是6 4 位，其中8 位为奇偶校验位。整个算法的 流程如图4 1 。d e s 对6 4 位明文分组进行操作，通过一个初始置换，将明文分 成左半部分和右半部分，各3 2 位。然后进行1 6 轮完全相同的运算，在运算过 程中数据与密钥结合，经过1 6 轮后，左右半部分合在一起经过一个末置换( 初 始置换的逆置换) ，密文生成。 输入6 4 比特明问数据 上 初始置换i p j 在密钥控制下1 6 轮迭代 上 交换左、右3 2 比特 j 初始逆置换i p 1 上 输出6 4 比特明文数据 图4 - 1d e s 算法框图 第四章面向行业信息安全的算法 第三节r s a 算法 4 3 1 公钥密码算法具有如下特性： 一是加密密钥与解密密钥是本质上不同的，也就是说如果仅仅知道密码算 法和加密密钥，而要确定解密密钥，在计算上是不可行的。 二是大多数公钥密码算法的加解密密钥具有互换的性质，如应用最广泛的 r s a 算法，密钥对中的一个用于加密，另外一个就用于解密。 公钥密码体制的数学解释： 从数学上讲，公钥密码体制是一族变换对 e i ，d i ) ，i i ，满足条件 a ：e i 是x 到y 的映射，d i 是y 到x 的映射，且对任意x x ，d i ( e i ( x ) ) = x b ：对任意x x ，y y ，计算e i ( x ) 和d i ( y ) 都是容易的。 c ：由e i 出发去寻找等价于d i 的变换在计算上是不可行的。 d ：对任何i i ，生成变换对e i 与d i 是多项式时间或概率多项式时间的。 在公钥密码体制中，任何一个用户i 都有自己的加密变换e i 和解密变换d i ，并 且e i 对其他用户公开，而d i 则对其他用户保密。在实际公钥密码系统中，公 开的就是公钥，而保密的就是私钥。 4 3 2 利用公钥密码体制信息的编码 下面举例介绍用户i 把消息x 编码，然后传递给拥护j 的过程。 当要进行保密通信时，用户j 首先获得用户i 的加密变换e i ，然后把明文x 变 换为密文y = e i ( x ) ；最后将密文y 发送给用户i ， 用户i 的处理过程：收到密文y ，用解密变换d i 恢复明文x = d i ( y ) ，由条件a 可以知道x 、= x 。 由于除了用户i 自己外，其他用户不知道d i ，那么由条件c 可知，其它用户要 想从密文中获取明文是不可行的。 2 l 第四章面向行业信息安全的算法 4 3 3 公钥密码体制r s a 算法的数学基础 r s a 算法非常简单，概述如下： 找两素数p 和q 取n = p * q 取t = ( p 一1 ) 木( q 一1 ) 取任何一个数e ，要求满足e t 并且e 与t 互素( 就是最大公因数为1 ) 取d , e = = i m o d t 这样最终得到三个数：nd e 设消息为数m ( m n ) 设c = m d m o d n 就得到了加密后的消息c 设m _ c 。m o d n 则i l l = = m ，从而完成对c 的解密。 在对称加密中： nd 两个数构成公钥，可以告诉别人； ne 两个数构成私钥，e 自己保留，不让任何人知道。 r s a 的安全性在于对于一个大数n ，没有有效的方法能够将其分解从而在已知nd 的情况下无法获得e ；同样在己知ne 的情况下无法求得d 。 r s a 简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用r s a 来对所有 的信息进行加密，最常见的情况是随机产生一个对称加密的密钥，然后使用对 称加密算法对信息加密，之后用r s a 对刚才的加密密钥进行加密。 第四节r s a 算法实例 找两个小素数来建立一个简单的r s a 算法： ( 1 ) 选择两个素数p = 7 和q = 1 7 ； ( 2 ) 计算n = p q = 7 , 1 7 = l1 9 ，计算t = ( p 1 ) 木( q 1 ) = 6 1 6 = 9 6 ； 第四章面向行业信息安全的算法 ( 3 ) 选择一个随机整数e = 5 ，它小于9 6 并且与之互素； ( 4 ) 求出d ，使得d e = 1 m o d 9 6 ，此处d = 7 7 ，因为7 7 5 = 3 8 5 = 4 , 9 6 + 1 ； ( 5 ) 输入明文m = 1 9 ，计算1 9 模1 1 9 的5 次幂m e = 1 9 5 = 6 6 m o d l l 9z 得密文c = 6 6 ； ( 6 ) 接收密文6 6 ，计算6 6 模1 1 9 的7 7 次幂；c 6 6 7 7 = 1 9 m o d l l 9 ，得明文1 9 ； r s a 简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用r s a 来对所有 的信息进行加密，最常见的情况是随机产生一个对称加密的密钥，然后使用对 称加密算法对信息加密，之后用r s a 对刚才的加密密钥进行加密。 第五节二维条码防伪加密方案 在二维条码防伪加密中，通常将对称密码和非对称密码结合在一起使用，利用对 称密码加密信息，采用非对称密码加密对称密码的密钥，使之具有对称密码加密速度 快，非对称密码密钥管理简单的优点。 对于二维条码的加密和解密，我们采用基于d e s 算法对称密码体制和基于r s a 算 法的非对称密码体制，根据信息的安全程度要求选择不同的加密方案，具体方案 如下 图4 2 条码加密方案 第四章面向行业信息安全的算法 对信息进行防伪，不论采用哪种密码体制，最重要的是对密钥的管理。智能 卡由于它的自身特点，常用来存储密钥和进行系统身份验证。本文采用a v r 高 速嵌入式单片机作为编、译码模块平台。 l 、身份认证 编、译码模块和智能卡内各自都拥有一对公钥体制中的密钥。当插入智能卡时， a v r 向智能卡发一产生随机数的命令，卡产生一随机数c r ( e l l e n tr a n d o m ) ， 做为请求号。然后用智能卡的公钥对此请求号和智能卡身份信息进行加密，将 密文发送给a v r ，a v r 接到信息后用自己的私钥进行解密运算，获取随机的请求 号和智能卡信息明文，a v r 根据已存储在系统r o m 内智能卡的公钥，将随机的请 求号和自己产生的一个随机数s r ( s e r v e rr a n d o m ) 一起用其加密后传回智能卡， 智能卡用自己的私钥解密，获得随机请求号和随机数明文，将随机数再用a v r 的公钥加密发送给a v r ，由a v r 解密获得随机数的明文。到此，完成了智能卡和 a v r 双方身份的相互认证如图 k 1 r - - f ( k ! 、 均x 随村 i k _ r 图4 - 3 智能卡和a v r 的相互认证 2 、数据加密和解密 智能卡内存储的数据，用来作为用对称密码算法对信息加密和解密时的密钥， 首先，利用单向散列函数( s e c u r e h a s h f u n c t i o n ) 计算所要加密信息的校验 和，将结果用自己的私钥进行加密，即签名，再利用主密钥( 智能卡内的数据) 和对称密码算法加密信息和签名印刷成p d f 4 1 7 标签。识读器识读标签得到密文 数据后，利用译码模块内自己掌握的主密钥解密获得信息的明文和对方的签名， 把编码模块的签名用对方的公钥解密，与所获得的明文进行校验和比较，从而 确定所获的明文信息的有效性。 第五章二维码的存储器函数变换分析与讨论 第五章二维码的存储器函数变换分析与讨论 存储器作为计算机系统中的重要部件为大家所熟悉，它可即将程序和数据存 放起来，使计算机脱离人的干预自动工作，按照其导体材料和用途的不同，可分 成e p r r o m