G B 1 8 0 3 0汉字信息的二维条码拆分迭代编码算法

第27卷第9期 2007年 9月 计算机应用 Computer Applications Vo1．27 No．9 Sep．2007 文章编号：1001—9081(2007)09—2337—03 GB18030汉字信息的二维条码拆分迭代编码算法 夏春蕾，戴曙光，张仁杰 (上海理工大学 光学与电子信息工程学院，上海200093) (mayerx@163．tom) 摘 要：为了解决二维码在证件类应用中常常面临的冷僻字编码问题，以GB18030字符集为对 象分析汉字编码特点，提出基于该标准的汉字与 ASCII混合信息的PDF417编码方法。并针对当前 广泛应用的 l6位编程工具，结合实例给出了一种拆分迭代编码算法来实现字节压缩模式，它能够在 保证较高编码效率的基础上有效节省编码存储空间。 关键词：编码；二维条码；汉字；GB18030；Reed—Solomon码 中图分类号：TP391．1 文献标志码：A Split-iterated algorithm for 2D bar code encoding of the GB 1 8030．character-set．based Chinese ideograms XIA Chun—lei，DAI Shu—guang，ZHANG Ren-jie fCollege ofOptical&Electronic Information Engineering, University ofShanghaifor Science and Technology,Shanghai 200093，China) Abstract：It is very important for the wide use of 2D bar codes in certificates to encode the Chinese ideograms that are rarely seen and used in social life while more people would like to have them in the name to show its uniqueness． GB18030----2005 character set makes it possible to solve such a question with neady 27000 Characters included．The encoding regulations for Chinese ideograms in GB18030 were analyzed here and then the 2D bar code PDF417 encoding method of the mixed information of Chinese ideograms with ASCII characters was put forward．A special byte-compression method nam ed split·-iterated algorithm which could save memory without loss of encoding efficiency and could be realized on 16--bit programming tools was introduced here too．An example was given in this paper to illustrate the wh01e encoding process． Key words：encod ing；2D bar cod e；Chinese ideograms；GB18030；Reed·Solomon code 0 引言 1 GB18030字符集汉字编码特点 二维条码具有信息密度大、纠错能力强等特点，自推出后 迅速在国际上得到认可 ，被广泛应用于各类证件、邮政、物流 管理等行业I1 川 。我国1997年颁布了第一个二维条码标 准——《四一七条码》(GB／T17172)，为二维码在我国的应用 制定了相应。但目前我国多数二维条码产品的编码算法 针对的还是ASCII码信息，对汉字信息的编码不多且主要仍 是基于GB2312标准中定义的汉字，其中包含有高频字、常用 字及次常用字共计6 763个 ]。对于各类证件如身份证，其 中姓名一项人们为了独特性和个性化常常会使用冷僻字及罕 见字，而这些字在 GB2312中没有定义。因此现有的二维编 码方式在证件应用场合很难推广 川 。2000年我国结合 Unieode的发展趋势，推出了新的汉字编码标准 GB18030，并 在2005年颁布了第一次修订本 。该字符集中包含了彝、 藏、维吾尔等多种汉藏语系文字，其中汉字数量达到27 ooo多 个，它包含了大量 GB2312中没有的冷僻字及罕见字。显然 研究基于 GB18030的二维条码编码方法对于推广二维条码 技术在各类证件上的应用具有重要的实际价值。 GB18030中规定了单字节编码、双字节编码及四字节编 码三种方式。单字节部分收录的是基本等同于ASCII码字符 集中的128个字符。双字节部分为图形、符号和部分汉字，汉 字主要集中在第2、3和4区。这三个区中，第 2区主要对应 GB2312中的汉字，而第3区和第4区则是汉字内码扩展规范 GBK在 GB2312基础上扩展的汉字约 14 000多个，其中包括 台湾通用的繁体汉字在内的罕见字及冷僻字等。四字节部分 则包括少数民族文字及其他的扩展汉字，汉字所占区域地址 范围为 0x8139FE39～0x82358738(对应于 Unieode中 CJK统 一 汉字扩展 A)和0x95328236～0x9835F336(对应与 Unleode 中CJK统一汉字扩展 B)，后者为2005年修订版中添加的内 容。四字节部分是对二字节汉字集的进一步补充，如此， GB18030中囊括的汉字符号共计达到70000多个 J。即使 是对四库全书这样的古籍巨著，GB18030能达的汉字也达 到了99．99％以上 J。 GB18030中的汉字编码有两字节与四字节之分 ，两种编 码方式可通过第二字节来区分：第二字节范围在 0x30～0x39 的属于四字节编码汉字，在 0x40～0x7E或 0x80～0xFE范围 收稿日期：2007—03—06；修回日期：2007—05—21。 基金项目：上海市教委基金资助项目(05E241)。 作者简介：夏春蕾(1974一)，女，安徽肥西人，讲师，博士研究生，主要研究方向：光电检测、信息处理； 戴曙光(1957一)，男 ，上海人 ，教授， 博士生导师，主要研究方向：自动测量在线检测、机器视觉检测、信号与信息处理； 张仁杰(1956一)，男 ，山东青岛人 ，教授，博士生导师 ，主要研 究方向：在线检测技术与装置、测试信息获取与处理、测试技术及仪器。 维普资讯 http://www.cqvip.com Administrator Pencil Administrator Pencil Administrator Pencil 2338 计算机应用 2007卑 者属于二字节编码汉字。且四字节编码的各字节有效编码范 围均被加以限制，首字节和第三字节为0x81—0xFE，第二字 节和尾字节为0x30—0x39。所有的汉字编码第一字节均大于 0x80。上述字节范围25~,b的则可判定为不属于汉字。如大多 数ASCII码信息在 GBl803O中是单字节编码，地址范围在 0xO0—0x7F之间。 另外，值得注意的是 GB18030的二字节汉字要考虑与 GB2312等旧有国标向下兼容，它与目前很多通用平台采用的 Unicode编码之间不能直接用数学换算方式进行编码转换，而 要制作表格以备查表转换。四字节部分则基本保持与 unieode中的cJK统一汉字扩展A及 B一致，可以使用线性 数学换算的方式进行编码转换。例如对 CJK统一汉字扩展 B，其 unicode起始地址为0x20000，对应 GB18030编码起始地 址为 0x95328236，若某个汉字对应 的 unicode编码表示 为 置 它相对 CJK统一汉字扩展 B起始地址偏移量为 s= ； 一 0x20000。若定义r=smod(0x0A)是偏移量s相对第四 字节码位数目lO的求余运算，而两者除法运算的商表示为 g=l( 一0x20000)／0x0A l，则该汉字对应的GB18030编 码第四和第三字节可分别按照式(1)、(2)转换得到。式中Ox 是十六进制的标志。 洲 =(r+0x36)mod(0x40)+0x30 (1) 渊 ={[g+(r+0x36)rood(0x40)]mod(0x7E)+ 0x82}mod(0xFF)+0x81 (2) 前文提到第三字节有效编码范围为0x30—0x39，第四字 节为Ox81一OxFE。上述公式中0x36和0x82分别是GB18030 汉字的第四和第三字节的起始编码地址，Ox40和 OxFF是第 四和第三字节有效编码的进位控制数，而0x0A和0x7E分别 是第四与第三字节的有效编码数目对应的十六进制表示。类 似地，可得出第二和第一字节的转换公式。 对cJK统一汉字扩展A，有部分汉字对应在二字节部分， 转换时需特别对这些汉字加以考虑并适当修正数学转换计算 式。 2 汉字混合信息的二维条码表示 2．1 基于 GB18030的混合信息的统一编码可行性 对于多数证件来说，其主要文本信息是汉字与基本 ASCII符号混合而成。如地址信息：上海市军工路516弄28# 信箱，其中不仅包含有汉字，还有 ASCII符号。因此，用于证 件的二维条码编码需要考虑汉字与ASCII码的混合编码问 题。GB18030中把多数ASCII符号(除$)放入了单字节部分， 其地址范围在0x00一OxTF。它们与汉字编码的显著不同在 于最高位为0，而汉字不论是二字节还是四字节，最高位都是 1，因此可将它们与汉字放在一起编码而不会引起解码混淆。 同是汉字，如前文所述可借助第二字节的地址范围区分它属 于二字节部分还是 四字节部分。通过上述 分析，可知 GB18030字符集中的汉字与ASCII信息可放在一起统一进行 二维条码的压缩转换编码。 2．2 用拆分迭代编码算法生成二维码字 GB／T17172--1997中规定的二维条码 PDF417的压缩编 码一般有文本压缩(TC)、字节压缩(BC)及数字压缩(NC)三 种模式，其码位压缩比率分别为2：1、6：5和44：15。显然数 字压缩比率最高，但是不适用多种字节并存的汉字信息编码。 文本压缩要求被压缩的两个码位在0—29之间，因此也不适 用于汉字编码。故汉字的二维条码压缩转换一般采用字节压 缩模式。即将待压缩的数据字节按照每6个字节一组进行分 组，每组六个字节转换为5个基900数，即五个PDF417码字， 余下不足六个的逐个字节单独表示。若数据字节数目恰好是 六的倍数，模式锁定码字用 924，否则用901。每组字节压缩 的转换关系可用式(3)表示如下。 256 5+256 X4+256 3+25 6 X2+25 6xl+X0= 900 Y4+900 Y3+9002y2+900yl+y0 (3) 其中： ( =O，1，2，3，4，5)是待转换数据字节， (五=0，1， 2，3，4)是待求解的基900的PDF417码字。由式(3)可知，字 节压缩转换过程中产生的中间结果将会很大，需用到int64以 上的数据类型。对于一些能支持到int64的高级语言编程工 具如VC、VB等实现起来虽然并不困难，但仅仅为了支持中间 结果而采用int64数据类型显然非常浪费存储空间，且高数据 类型的使用也会降低编码算法的效率。而对于目前多数的编 程工具如DSP汇编等，它们甚至还不能支持 int64。因此，寻 找一种有效的基于intl6数据类型的转换算法有重要的实际 意义。我们将给出一种基于 intl6的拆分迭代算法来实现字 节压缩模式的编码。该算法的基本思想是将式(3)左边的各 项依次拆分，将每个256‘ 分别用基900数据表示。即： f256 ％ =900 +900 Y53’+9002y52+900y5l+Yso l256 X4=900 Y44+900 ‰+900 Y42+900y4l+Y4o { ； l 256xl=900yll+Ylo 【 ： Yoo (4) 将式(4)中不足的系数用0填充，则式(3)右边的5位基 900数据可按下式求出： (1 t j+ ，， )mod(900)； _『=1，2，3，4 (5) 显然J=0时，Yo=(∑‰)mod(900)。在求解拆分式 (4)右边系数Y 的过程中，为了保证中间变量在有效示数范 围之内，我们采用了迭代方法。以256 ,X2项为例，首先求解 256x2=9o 。+ ，然后求解256 X2=9OO +9o0y~,+ 。等式右边Y的上标表示迭代的次数，下标表示对应的 序 号及其在基900表示法中对应码位的权值幂次。如 表示对 应 的第 1次迭代产生的权为900 的码位。图1给出了单组 字节压缩编码的拆分迭代流程图。流程图中数学符号的含义 同前文。 迭代向量初始化即令： { }={0 0 0 0 0 } (6) 流程中第n次迭代运算见式(7)。6个字节对应的迭代向 量全部算完后，则可按照式(5)求解对应的5个基 900码字 ，， (．『=0—4)。 维普资讯 http://www.cqvip.com Administrator Pencil 第9期 夏春蕾等：GB18030汉字信息的二维条码拆分迭代编码算法 2339 y s6y m。d c +l s6y J ㈩ 引 区尺寸。 例如对信息：“9个冷僻字例子：慰，楝娘歆毡摧烘株铨”， 按照上述方法转换可得其 PDF417压缩编码为：{901 96 659 698 247 10 281 248 7o4 599 251 353 884 849 27 453 249 308 206 555 169 259 328 326 602 310 229 119}。 图1 拆分迭代流程 2．3 冗余纠错码的生成 将所有的数据字节都转换 为基 900的 PDF417码字后 ， 就可以计算冗余纠错码字。PDF417条码采用基于GF(929) 的Reed．Solomon纠错码[ ，并给出了不同信息容量下的推 荐纠错等级。据此对于上例选择纠错等级为2，即该条码具 有k=2 A(2+1)=8个纠错码位。以上文生成的28个基 9OO的 PDF417码字及其数 目(长度码字)为系数，得到数据 多项式如下： d( )= 一l I1+ 一2 一 +⋯ +dl + (8) 其中：d 是长度码字， d 一3⋯ 为前面得到的28个基 900码字。按照国标规定取生成多项式为： g( )=( 一3)( 一3 )⋯( 一3 )： +g —l 一。+⋯ +gl +g0 (9) 则纠错冗余码字按照式(10)产生： C( )=(d( ) )rood(g( )) (10) 本例中8个纠错码位分别为：{509 393 588 179 863 534 500 907}。最终包含纠错码字的 PDF417码字多项式可 表示为下式： d，( )=d( ) +C( ) (11) 式(11)表明我们最终得到的 PDF417码字是由长度码 字、数据码字和纠错码字共同构成。 3 二维码图的生成 对得到的长度码字、数据码字和纠错码字，我们还要合理 安排以构成一个完整的条码阵列以便生成条码图形。一般需 要考虑的有条码的应用场合、印刷条件和扫描条件。根据这些 条件选择条码长宽比及所需的印刷密度，确定符号的基本模 块宽度 ，并选择适当行数和数据列数。为了保证条码矩阵的 完整，可能还需要添加部分填充码字。对条码的行高和条码图 形的高度和宽度都需要根据实际情况加以适当控制。通常行 高 应为3X以上。若条码矩阵中行数为Ⅳj，数据列数为C ， 则最终生成条码图形的宽度 和高度 日可 由下列两式计 H =Nl×月 +Q (13) 确定了条码矩阵的行数和列数之后就能按照标准给定的 公式计算并添加左右指示 符及起始符 81111113与终止符 711311121。通过打印得到所需的条码图形。本例中采用激 光打印机，确定数据符号字符区行数为16，列数为6。最终得 到的二维码码图如图2所示。该二维码图中包含了除前文例 中信息外的作者相关信息。 鲢醚罐雕鹾隧麟隧 上海理工大学光电学院夏春蕾上海市军工路516弄208栉信箱邮编200093 9个冷僻字例子：融徕娘歆毡堵蜣抖；铨 图2 二维条码示例图 4 结语 GB18030标准字符集包含了70000多个汉字字符，其中 囊括了大量的冷僻字和罕见字。本文结合该字符集中汉字的 编码特点，提出了面向GB18030字符集中所有汉字及汉字与 ASCII混合信息的二维条码编码方法，解决了以往二维条码 在证件类应用场合中较为棘手的冷僻字和罕见字的编码问 题。本文提出的拆分迭代编码算法可避免编码过程中产生过 大的中间变量，在 int16数据格式下实现字节压缩模式的转 换，即不必为了支持大量中间变量的运算而采用高数据类型， 从而也能有效节省编码过程中的存储空间，提高编码效率。 参考文献： 【1】 PAVLIDIST．A new paper／computerinterface：two-dimensional symbologies【C】／／Proceedings of IEEE International Conference on Pattern Recognition．【S．1】：IEEE PI-I~s，2000：145—151． 【2】 薛红，薛军，邹彦卿．二维条码在车辆管理系统中的应用研究 【J】．计算机工程，2002，28(6)：211-213． 【3】 陈哲，张永林．基于二维条码技术的证件管理系统【J】．计算机 应用与软件，2005，22(4)：121—124． 【4】 GB18030--2005，信息技术 信息交换用汉字编码字符集 基本集 的扩充【S】． 【5】 Tom E．A look at China’s n GB 1 8 0 3 0 character set standard 【EB／OL】．【2006-09-25】．http：／／en．wikipedia．ors／wik GB— l8030． 【6】 JOSE S．Summary，explanations，and l~mal'ks：GB1 8030--2000 【EB／OL]．【2006—09-25】．hnp：／／en．wikipedia．org／wiki／GB— l8030． 【7】 王晓明．用信息化手段进行语言文字研究【EB／OL]．【2006一o6 — 19】．http：／／www．china-language．gov．ca． 【8】 GB17172--1997，四一七条码【S】． 【9】 戴扬，于盛林．二维条码编码与译码的计算机实现【J】．数据采 集与处理，2003，18(2)：356—360． 【10】SHAN S S，YAQUB S．Self-correcting codes conquer noise Part 2： Reed-Solomon Codes【EB／OL】．【2006一lO一03】．http：／／www． tmssales．com／Application _ Notes／Digital _ Test／reod solomon．p札 【11】王毅．二维条码技术应用及标准化状况介绍【J】．中国标准化， 2006，(5)：24—28． 维普资讯 http://www.cqvip.com