基于Reed-Solomon码的Data Matrix条码纠错研究

　　0　引　言

　　与一维条码相比,二维条码是用特定的几何图形按一定规律分布在平面(水平和垂直方向上)上的黑白相间的图形记录数据符号信息,它具有编码范围广、密度高、信息容量大、可引入加密机制等特点,使得在小面积上编码大数据成为可能,因此被广泛地应用于工业自动化、物流、身份识别等各个领域。

　　本研究介绍基于Reed-Solomon码的DataMatrix编码、解码及其软件实现过程。

　　1　DataM atrix码的纠错机制

　　DM码是由美国国际资料公司于1989年发明的一种最早的矩阵式二维条码,其发展构想是希望在较小的条码标签上存入更多的信息量。DM码的尺寸可任意调整,最小可到0. 000 2平方英寸,这个尺寸是目前所有条码中最小的,特别适用于小零件的标识,以及直接印刷在实体上[1]。

　　早期的DM码是使用卷积码来进行纠错的,虽然它能够用于纠正随机错误,但是只进行错误校验,且纠错和编码效率很低。直到1995年5月, Jason Le对DM码进行改进,他把Reed-Solomon纠错码(RS码)用于DM码中。RS码是性能优良的纠错码,它具有纠正突发错误和随机错误的能力,而纠正突发错误更为有效。在线性分组码中它的纠错能力和编码效率是最高的,是目前世界上最先进的纠错码技术之一[2]。

　　DM二维条形码的编码和解码流程图如图1所示。编码时首先对原始信息按照不同类别的字符进行编码以生成数据码字,接着将数据码字按标准分成相应数量的块,对每块按照RS算法分别计算出纠错码字并添加到数据码字的后面[3]。最后把码字模块放置到矩阵中生成DM图形。

　　在DM解码时,条码有可能因穿孔、污损等引起局部损坏,而DM码具有很强的纠错能力,有些条码只需读取资料的20%即可精确地识别,这种纠错能力的获得是借助RS纠错码来实现的。

　　2　RS码的基本概念

　　定义1[4]:有限整数集合F={0,1,…,q-1}(q是素数)在模q加、模q乘运算下构成一个q阶有限域,称为伽罗华(Galois)域,记做GF(q)。

　　定义2:在GF(q)中可以找到一个元素α,使得GF(q)中的q-1个非零元素都可以通过α的各次幂α0,α1…,αq-2生成,元素α称为本原元。

　　定义3:对于某数域上的多项式p(X),若除了常数c以及c·p(X)外,不能被该数域上的任何其他多项式整除,则称p(X)为该数域上的既约多项式。

　　定义4:对于GF(q)中的m次既约多项式p(X)若满足p(X)被整除的Xn+1的最小正整数n为qm-1,则称p(X)为本原多项式。

　　定义5:将信息流的每k个码元分为一组,通过线性变换,映射成由n个码元组成的码字,称为(n,k)线性分组码。

　　定义6:对于一个(n,k)线性分组码,若将其任意一个码字的码元向左或向右循环移动一位后仍然还是码字,则称该码为(n,k)循环码。