文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 二维条码中RS纠错译码算法的优化实现
侵权投诉

二维条码中RS纠错译码算法的优化实现

二维条码中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一),男,博士,教授,研究方向:图像处理、分析。

万方数据 

第1页

你可能喜欢

热门文档

相关文档

  • 二维条码中RS纠错译码算法的优化实现

    二维条码中RS纠错译码算法的优化实现 利用Berlekamp Massey迭代算法、钱搜索算法以及Fomey算法改进并实现了DataMatrix、QRCode和MaxiCode二维条码ISO标准中的Reed—...

  • 基于Reed-Solomon迭代译码的PDF417二维条码纠错译码算法

    实验结果表明,迭代译码算法不仅速度快、而且实现简单,译码准确,更 易于完成计算机...2 基于 RS 一般译码方法的 PDF417 条码纠错译码算法 RS码的译码算法 比编码...

  • 基于Reed-Solomon迭代译码的PDF417二维条码纠错译码算法

    实验结果表明,迭代译码算法不仅速度快、而且实现简单,译码准确,更 易于完成计算机...2 基于 RS 一般译码方法的 PDF417 条码纠错译码算法 RS码的译码算法 比编码...

  • RS编译码算法的实现

    2006年第 3期 福 建 电 脑 109 RS 编译码算法的实现武 炜, 董志学010051...【关键词】 RS码 编码 译码 纠错 一、 引言 个符号中错了多少位,在RS解码...

  • RS码技术在PDF417码纠错码编译码中的应用研究

    RS 码编译码原理的基础上, 通过对二维条码 PDF417 码和四一七国家条码规范的分 析和研究,将RS码技术应用 译码算法过程中, 完成了 PDF417 纠错 的实现,同时给出...

  • RS码编译码算法的实现

    RS码编译码算法的实现_计算机软件及应用_IT/计算机_专业资料。RS码编译码算法...它的译码比较 复杂 ,且专门介绍译码过程的资料很少 ,所以不少人情愿使用纠错...

  • RS码译码算法对比研究

    Solo mo n 提出 RS 码 [ 1 ] 。由于其优 越的纠错能力 ,RS 码被广泛...( x) 的迭代译码算法 ,极大地加快了求 σ( x) 的速度 , 实现比较简单 ,...

  • QR二维条码的纠错编码算法研究及实现

    二维条码的纠错编码算法研究及实现 Research Error-correcting Coding Algorithm of QR Code 摘要 : QR 二维条码的编码算法应用了有限域中 RS 码编码算法增加冗余...

  • QR码纠错码原理及实现

    t 3 RS 码在 QR 码中的译码过程 条码在传输的过程中可能受到污染, 接收的... 讲座--Turbo 纠错码的原... 19页 免费 QR算法原理及计算机实现... 8页 ...

  • RS码译码算法与译码器的DSP实现方法

    ,2004 文章编号 :1005 - 2992 (2004) 02 - 0014 - 04 RS 码译码算法与译码器的 DSP 实现方法戴伏生1 ,朱 2 ,王春虎3 亮 (1. 哈尔滨工业大学 [ 威海...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email