Reed-Solomon算法在PDF417译码中的实现

摘要

条码技术是在计算机技术与信息技术基础上发展起来的一门容编码、印刷、识别、数据采集和处理于一身的新兴技术。由于二维条码具有信息容量大、编码范围广、可靠性高、保密防伪性强、纠错能力强、条码符号的形状可变、容易制作、成本很低且不依赖数据库等优点，最近几年得以迅速发展。PDF417条码即是其中的典型代表。
　　 二维条形码具有一维条码不具备的纠错功能,RS码是一类功能很强，应用广泛的纠错码，尤其是在纠突发错误方面性能优越。目前RS码已经广泛应用于通信系统、计算机系统、存储介质、网络和数字电视中，以提高数据的可靠性。
　　 本文简要介绍了二维条形码PDF417的特点，编码、译码规则，Reed-Solomon纠错码(RS码)原理，数字传输系统和差错控制编码的发展历史，RS码的应用领域和其现有的实现方法。重点分析研究它在PDF417二维条形码中的应用方法，并详尽地推导了在伽罗华域GF(929)域内RS码的编码、译码方法，详细阐述用计算机实现其译码的原理和方法，采用具体实例介绍设计步骤，并给出c语言实现译码的程序设计方法。

目录

文摘

英文文摘

声明

第1章二维条码PDF417概述

1.1条码技术概述

1.1.1条码的特征

1.1.2条码的优点

1.2二维条码技术简介

1.2.1二维条码的产生背景

1.2.2二维条码的特征

1.2.3二维条码的分类

1.3二维条码PDF417的应用及发展前景

1.3.1 PDF417概述

1.3.2 PDF417的纠错功能

1.3.3 PDF417的应用前景

第二章差错控制编码简介

2.1信道编码基本理论

2.1.1信道发生错误的几种模式

2.1.2错误控制的三种方式

2.1.3纠错码的分类

2.2数字传输系统与差错控制编码

2.3差错控制编码的发展历史

第三章RS码代数译码算法

3.1 RS码的定义及性质

3.1.1数学预备知识

3.1.2 RS码预备知识

3.2 RS编码算法

3.3 RS译码算法

3.3.1计算伴随式Sk

3.3.2 Peterson算法

3.3.3 Berlekamp-Massey算法

3.3.4 Euclid算法

3.3.5钱搜索

3.3.6 Forney算法

3.3.7小结

第四章RS码在二维条码PDF417中的应用

4.1二维条码PDF417编码概述

4.1.1二维条码PDF417的符号结构

4.1.2符号字符的簇

4.1.3三种压缩模式

4.1.4 PDF417条码的数据编码

4.1.5纠错等级

4.2二维条码PDF417译码

4.2.1二维条码PDF417译码流程

4.2.2二维条码PDF417译码原理

4.3课题中译码算法的选择

4.3.1计算伴随式算法的选择

4.3.2计算错误位置多项式算法的选择

4.3.3求解差错值多项式算法的选择

4.4 RS译码算法在PDF417中的应用

4.4.1计算伴随式

4.4.2通过BM迭代计算错误位置多项式

4.4.3得到错误位置

4.4.4.计算错误值

第五章PDF417译码的实现

5.1 Galois域的构造

5.2 PDF417的编码实现

5.2.1数据编码

5.2.2错误纠错码词的求取

5.2.3 PDF417的符号组配

5.2.4转换为条空形式

5.2.5绘制条码

5.3 PDF417的译码流程

5.4 RS纠错算法的实现

5.4.1总体流程图

5.4.2计算伴随式

5.4.3求解错误位置多项式系数

5.4.4通过chien搜索求λ(χ)的根

5.4.5求出错误位置的错误值

5.4.6纠正错误码字，输出信息码元

5.5运行测试

第六章总结与展望

致谢

参考文献

学位期间在公开期刊上发表的学术论文