二维条码中RS纠错译码算法
ComputerEngineeringandApplications计算机工程与应用
二维条码中RS纠错译码算法的优化实现
尚振宏,袁梅宇,刘辉
SHANGZhen—hong,YUANMei-yu,LIUHui昆明理工大学信息工程与自动化学院,昆明650051
Facultyof
InformationEngineering
andAutomation,KunmingUniversity“ScienceandTechnology,Kunming650051,China
E--mail:&hangzhenhong@126.e0立l
SHANGZhen-hong.YUANMei-yu.LIUHal.RSdecodingalgorithmin2Dbarcodes—improvementandimplementation.Computer
E埘neering
and
Applications.2007.43(25):175—177.
Abstract:UsingBerlekamp
Massey,Chienand
Code
Fomey
and
algorithms,thispaperpresents
a
way
to
implement
Reed-Solomonalgo--
rithmin2D
barcodes--DataMatrix,QR
n¥e
standards.Beyondthis.bymaking
way
to
MaxiCode.ThisimplementationhaslesstimecomplexitythanthoseinISO
ofthecharacteristicofsystematicformofRScodein2Dbarcodes,Wehavepresented8
improvethedecodirrg
speed.
Keywords:Iked—Solomon;2Dbarcodes;errorcorrecting
摘要:利用BerlekampMassey迭代算法、钱搜索算法以厦Fomey算法改进并实现了DataMan'ix、QRCode和MaxiCode二维备码ISO标准中的Reed—Solomon纠错译码算法(简祢RS算法),降低了三种二雏条码码制中RS纠错译码算法的计算复杂度。在此基础上,利用RS缩短系统码的特点对译码过程作进一步简化。实验结果表明,通过简化译码过程再次提高了Rs纠错译码的速度。
关键词:Reed—Solomon;=维条码;纠错文章编号:1002—8331(2007)25-0175-03
文献标识码:A
中图分类号:TP391
1引言
由于二维条形码与一维条形码相比具有更高的信息携带
能力、安全性和纠错能力,二维条码在国际上和国内得到了广泛的运用I”。Rs码是一类有很强纠错能力。能纠正多个随机错误的多进制BCH码,它同时也是极大最小距离可分码(MDS码)。其纠错能力在短和中等码长’情况下接近理论值Ⅲ。因此,在国际上广泛采用的DataMatrixt目、QRCodeIm,和MaxiCodeIsl等二维条码码制中(目前我国已翻译和颁布QRCode国标161,
Data
计算量。由于二维条码的整个译码过程—般是在资源相对有限的嵌八式计算环境中完成,并且Rs纠错译码花费的时间在整个二维条码译码过程中占有相当比例。因此,提高Rs纠错译码的速度将对改善_二维条码识读器的译码效率起到重要作用。
2二维条码标准巾的RS纠错译码算法
在DataMatrix、QRCode和MaxiCode二维条码的ISO标准中,分别给出了各自的Rs纠错译码算法㈣,它们在实现上具体细节有所不同,如表1所示,但均是基于有限域GF(24)的
Rs纠错泽码算法。基本算法如下:
表1不同二维条码中Rs码的差剐
Matrix和MaxiCode国标即将颁布).均运用RS纠错算法上述二维条码的ISO标准”以及我国QRCode国标[61中
实现纠错功能。
给出的Rs译码算法均基于求解线性方程组,其计算复杂度较高。本文利用BerlekampMassey迭代算法(简称BM算法)、钱搜索算法和Fomey算法分别求解错误位置多项式、错误位置和错误值,从而避免了求解线性方程组,降低了整个Rs纠错译的计算复杂度。另外,由于上述二维条码使用的是Rs系统
码,即在码词多项式中,纠错码词和数据码词可区分开口。而在
二维条码的实际应用中。只需关心数据码词是否正确,无需对
第—步:计算伴随式值。
首先,利用从二维条码符号图像中还原出的数据构建码词多项式:
ProvinceofChinaunderGrant
错误的纠错码词进行纠错,从而可进一步减少Ils纠错译码的
基盘砸目:云南省自然科学基金(山eNatural瓤en凹Foundationof
Yunnan
N02005F0016Q);云南省教育厅资助
No.5Y0674D);昆明理工大学基金
科研课题(the
Research
Project
ofDeparUIlentofEducationofYunnan
Frovince.ChinaunderGrant
项目(No.枝引2005-6)。
作者简介:尚振宏(1975一),男,博士,讲师,研究方向:二维条码技术、信息处理;衷梅宇(1967一).男.博士.副教授,研究方向:分布式处理及并行计
算;刘辉(1969一),男,博士,教授,研究方向:图像处理、分析。
万方数据
二维条码中RS纠错译码算法的优化实现 利用Berlekamp Massey迭代算法、钱搜索算法以及Fomey算法改进并实现了DataMatrix、QRCode和MaxiCode二维条码ISO标准中的Reed—...
实验结果表明,迭代译码算法不仅速度快、而且实现简单,译码准确,更 易于完成计算机...2 基于 RS 一般译码方法的 PDF417 条码纠错译码算法 RS码的译码算法 比编码...
实验结果表明,迭代译码算法不仅速度快、而且实现简单,译码准确,更 易于完成计算机...2 基于 RS 一般译码方法的 PDF417 条码纠错译码算法 RS码的译码算法 比编码...
2006年第 3期 福 建 电 脑 109 RS 编译码算法的实现武 炜, 董志学010051...【关键词】 RS码 编码 译码 纠错 一、 引言 个符号中错了多少位,在RS解码...
RS 码编译码原理的基础上, 通过对二维条码 PDF417 码和四一七国家条码规范的分 析和研究,将RS码技术应用 译码算法过程中, 完成了 PDF417 纠错 的实现,同时给出...
RS码编译码算法的实现_计算机软件及应用_IT/计算机_专业资料。RS码编译码算法...它的译码比较 复杂 ,且专门介绍译码过程的资料很少 ,所以不少人情愿使用纠错...
Solo mo n 提出 RS 码 [ 1 ] 。由于其优 越的纠错能力 ,RS 码被广泛...( x) 的迭代译码算法 ,极大地加快了求 σ( x) 的速度 , 实现比较简单 ,...
二维条码的纠错编码算法研究及实现 Research Error-correcting Coding Algorithm of QR Code 摘要 : QR 二维条码的编码算法应用了有限域中 RS 码编码算法增加冗余...
t 3 RS 码在 QR 码中的译码过程 条码在传输的过程中可能受到污染, 接收的... 讲座--Turbo 纠错码的原... 19页 免费 QR算法原理及计算机实现... 8页 ...
,2004 文章编号 :1005 - 2992 (2004) 02 - 0014 - 04 RS 码译码算法与译码器的 DSP 实现方法戴伏生1 ,朱 2 ,王春虎3 亮 (1. 哈尔滨工业大学 [ 威海...
热门文档