循环码(BCH)编译码的并行化研究

摘要

随着信息技术飞速发展,全球的信息总量正以前所未有的速度迅猛增长,如何存储和处理如此巨量的数据,新的技术不断被提出,云存储和并行计算框架MapReduce是这些技术中具有代表性的一种。云存储是基于分布式文件系统构建的存储系统,具有大容量、多样性、时效性、准确性的特点。分布式文件系统由分布式部署的多个节点组合而成,传统的单机存储系统校验方法(如:奇偶校验、汉明校验等)均无法满足分布式文件系统的校验和纠错的要求,如何更有效地对分布式文件系统的数据进行校验和纠错显得更加迫切。本课题主要讨论大数据环境下,分布式文件所存储数据的BCH码编、译码并行化的问题,以解决大数据编、译码方面的瓶颈,从而有效地提高大数据编译码的性能。
　　本课题主要从线性分组码并行化的角度,利用分组码的特点进行编译码的并行化研究,主要包括两个方面的研究内容:(1)分组码编码的并行化;(2)分组码译码的并行化。本课题对当前分布式文件系统的存储方案存在的问题进行了深入的分析,针对校验和纠错能力不足的方面,提出了一种基于BCH循环纠错码的容错机制,以解决目前主流分布式文件系统缺乏校验和纠错机制、采用多副本存储所存在的空间浪费等问题。本课题在分析大数据环境和分组码的特点的基础上提出了一种基于查找表的并行编译码算法,设计了基于MapReduce并行框架的编译码方案并结合MapReduce分片的原理,设计了分片、编码查表的编译码方案并给出了该方案的实现。
　　本课题最后给出了所实现的BCH码的编译码并行化方案的性能分析。从性能分析的情况来看,采用本课题的BCH编译码的并行化处理方法时间复杂度得到了极大地提升,有效地解决了大数据环境下的数据校验和纠错问题。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

插图清单

表格清单

第一章 绪论

1.1研究的背景及意义

1.2循环码并行编译码的国内外研究现状及进展

1.3论文的内容安排

第二章 循环纠错码的原理与分布式文件系统

2.1编码理论代数基础

2.2线性分组码与循环码

2.3云存储与分布式文件系统(DFS)

第三章 循环码（BCH）编译码的并行化

3.1分布式与并行化

3.2 BCH码编码算法

3.3 BCH码译码算法

3.4基于分布式框架的循环码(BCH)并行编译码算法

第四章 循环码并行编译码的软件设计与实现

4.1并行编译码器的设计

4.2并行编译码器的实现

4.3性能分析

第五章 总结与展望

5.1工作总结

5.2不足之处

参考文献

攻读硕士学位期间发表的论文