（计算机软件与理论专业论文）erasurecode在网络存储系统中的研究与实现.pdf

哈尔滨工程大学硕士学位论文 摘要 随着电子商务时代的到来，存储信息成爆炸性增长。企业信息数据的安 全、可靠存储问题是存储系统稳定运行的关键所在，也是数字化信息存储发 展所要解决的首要问题。网络存储因为其具有结构灵活、性能较好、可扩展 性强等优势，在存储舞台上所发挥的作用日益增大。但是人为的错误操作、 数据服务器受病毒的侵害，物理存储介质的意外损坏等原因，经常使存储的 信息丢失，造成巨大的经济损失，所以存储信息的安全性、完整性成为网络 存储领域的研究重点。 e r a s u r e c o d e 是数字通信领域用于纠正数据传输过程中所发生错误的代 数编码理论。本文首先阐述了e r a s u r e c o d e 的基本理论，并重点介绍了一种 具有纠错能力的e r a s u r e c o d e r e e d s o l o m o n 码。在详细分析了其编码算 法与译码算法的基础上，将r e e d s o l o m o n 码的纠错能力与局域网络存储技术 相结合，设计出允许多个存储数据服务器失效的局域网络存储系统。并针对 译码算法运行时间较长的缺陷提出了改进方案。由于在此局域网络存储系统 中，r e e d s o l o m o n 码算法使用频率较高，并且始终保持不变，所以本文采用 f p g a 技术设计了r e e d s o l o m o n 编译码器，使之硬件化，从而提高了运行速 度。 关键词：网络存储；e r a s u r e c o d e ；r e e d s o l o m o n 码；f p g a 设计 哈尔滨工程大学硕士学位论文 i i ；鲁i i i 暑每i i i ；宣；葺暑i i 暑i ；i i ；i ；i i i ；i | i ii 墨 a b s t r a c t 、矾t ht h ea r r i v a lo ft h ee r ao fe - c o m m e r c e ，t h es t o r a g ei n f o r m a t i o nh a s i n c r e a s e de x p l o a i v e l y t h es e c u r i t ya n dr e l i a b i l i t yo fe n t e r p r i s ei n f o r m a t i o n s t o r a g en o to n l yi st h ek e yt os t a b i l i t yo fs t o r a g es y s t e m ，b u ti ti sa l s oa l li s s u eo f p a r a m o u n ti m p o r t a n c et ot h ed e v e l o p m e n to fd i g i t a li n f o r m a t i o ns t o r a g e b e c a u s e o ft h ef l e x i b l es t r u c t u r e ，s u p e r i o rp e r f o r m a n c ea n dg o o de x p a n d a b i l i t y , n e t w o r k s t o r a g e i s p l a y i n ga l li n c r e a s i n g l yi m p o r t a n tr o l e i nt h ef i e l do fi n f o r m a t i o n s t o r a g e h o w e v e r ，t h em a i l m a d em i s o p e r a t i o n ，t h ev i r u s i n v a d e dd a t as e r v e ra n d t h ea c c i d e n t a l l yd a m a g e dp h y s i c a l s t o r a g em e d i u mo f t e nm a k et h es t o r a g e i n f o r m a t i o nl o s ea n dc a u s eh u g ee c o n o m i cl o s s e s t h e r e f o r e ，t h es e c u r i t ya n dt h e i n t e g r i t yo fs t o r a g ei n f o r m a t i o nh a sb e c o m ea r e s e a r c hh o t s p o ti nt h ef i e l do f n e t w o r ks t o r a g e 。 e r a s u r e c o d ei sak i n do fa l g e b r a i cc o d i n gt h e o r yi nt h ef i e l do fd i g i t a l c o m m u n i c a t i o n , w h i c hi su s e dt oc o r r e c tt h ee r r o r si np r o c e s so f d a t at r a n s m i s s i o n t h et h e s i si se l a b o r a t e dt h ef u n d a m e n t a lt h e o r yo fe r a s u r e c o d e ，e s p e c i a l l ys t a t e d r e e d s o l o m o nc o d ew h i c hi sak i n d o fe r a s u r e c o d e 、i t l le r r o rc o r r e c t i n g c a p a b i l i t i e s b a s e d o nt h e a n a l y z e o fr e e d s o l o m o nc o d i n ga n dd e c o d i n g a l g o r i t h m ，t h et h e s i si sd e s i g n e da l o c a la r e an e t w o r ks y s t e mu s i n gr e e d s o l o m o n c o d ea n dl a ns t o r a g et e c h n o l o g i e s t h es y s t e mc a nr u ns m o o t h l yw h e nm u l t i d a t as t o r a g es e r v e rf a i l u r ea to n et i m e i na d d i t i o n ，i no r d e rt oo v e r c o m et h el o n g r u n n i n gt i m eo fd e c o d i n ga l g o r i t h m ，a i li m p r o v e dp r o g r a mi sp r o p o s e d i nr e s p e c t t h a tt h er e e d s o l o m o nc o d ea l g o r i t h mi su s e df r e q u e n t l ya n dr e m a i n su n c h a n g e d i nt h el o c a la r e an e t w o r ks y s t e m ，r e e d s o l o m o nc o d i n ga l g o r i t h mi si m p l e m e n t e d u s i n gf p g at e c h n o l o g ya n ds o l i d i f i e di nh a r d w a r e ，w h i c hi m p r o v e st h er u n n i n g s p e e do ft h ea l g o r i t h mg r e a t l y k e y w o r d s ：n e t w o r ks t o r a g e ；e r a s u r e - c o d e ；r e e d - s o l o m o nc o d e ；f p g a 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：圭氩 一，：7 日期：) p 口绰弓月i 多e t 哈尔滨工程大学硕士学位论文 1 1 研究背景和意义 第1 章绪论 随着计算机和网络技术的发展，社会信息化程度不断提高，按照m o o r e s l a w ，计算机的性能每1 8 个月增长一倍，各种数据信息，包含各种空间数据、 报表统计数据、文字、声音、图像、超文本等，以难以置信的速度急剧增加。 一方面，在网上流动的数据量以前所未有的速度增加，包括来自分布式数据 库、文件服务器、w e b 服务器等网上数据源，尤以i n t e r n e t 文件的数据量最 大，基于数据安全和使用方便的目的，人们通常对这些数据一再进行备份， 因而耗费的存储空间也非常之多。另一方面，科学计算和仿真，飞行动力学、 核爆炸仿真、虚拟现实以及医疗影像数据等，所需的存储容量更是大到惊人 的程度。人们对存储产品及服务的迫切需求无疑对服务质量和存储系统性能 提出了更高的要求，这也就推动了各种存储技术和存储结构的飞速发展。 信息的存储技术和计算机网络技术的结合越来越紧密，使互联网中出现 了网络存储技术。有了这种网络存储技术以后，可以把用户的文件保存在互 联网上，并且存储容量不受限制，文件访问方便、快捷，文件共享高效、智 能，文件存储可靠、安全。它的这些优越的性能使其自发布之日起便受到市 场的关注与青睐。人们对存储产品及服务的迫切需求，无疑对服务质量和存 储系统性能提出了更高的要求。美国9 1 1 事件警示了世界的同时，也警示了 信息存储界，从中汲取了不少重要的教训和经验。数据信息能安全可靠的使 用和迅速的恢复，是亟待解决的关键技术，成为当下存储界研究的热点问题。 目前，在数据的容错恢复方面，网络存储系统，为了取得较高的数据持 续性和可靠性，通常使用两种冗余容错方法，它们是完全的数据复制和磁盘 冗余阵列( r e d u n d a n ta r r a yo fi n d e p e n d e n td i s k s ，r a i d ) 技术。 完全复制就是通过将文件的多个副本分别存储在系统中的不同节点，实 现冗余容错，只要这些节点中有一个可以被访问，就可以取得文件数据。文 件副本越多，数据的可用性越好，可靠性越高。完全复制的方法不涉及编码 运算，文件的创建和读取不需要编译码操作。但是完全复制方法数据冗余度 哈尔滨工程大学硕士学位论文 较大，要想提高文件的容错性能，只能通过增加文件副本的数据来实现。完 全复制也会带来相当高的带宽和存储空间，很难满足网络存储系统的容错性 能的要求。 r a i d 技术其原理是通过资源冗余来提供服务质量，它将多个独立的磁 盘组织成一个逻辑盘，提供更大的存储容量，通过保存冗余的数据、校验信 息来提高存储系统的可靠性。应用最广泛的是r a i d 5 技术，但r a i d 5 技术 使用简单的奇偶检验码技术来保障数据的可靠性，至多只能容许一个磁盘出 现故障，并需要知道是哪个盘才能恢复，若两块及两块以上盘出错就会面临 存储系统瘫痪的局面。当系统规模较大时，同时发生多个磁盘失效的概率比 较高，存储系统的可靠性迅速降低。在容错恢复机制中，只能恢复一个已知 错，不能满足存储信息高安全性、高可靠性系统的需要。近年来，许多研究 者开始探讨将e r a s u r e c o d e 编码技术作为网络存储系统中的一种冗余机制来 提高数据的可靠性。将e r a s u r e c o d e 原理应用于网络存储系统，利用其强大 的纠错能力，可实现多盘容错并恢复，有效增加容错能力。因此，如何运用 e r a s u r e c o d e 在网络存储系统中，以及其设计构架和策略的分析是很值得研 究的。 1 2 网络存储备份技术概况 随着信息化建设的不断深入，尤其是因特网和电子商务的发展使计算机 用户的信息容量迅猛增长，需要保存的重要数据总量和增量非常大，制定有 效的存储备份策略是各种计算机行业面临的重大问题，也是网络存储技术所 要解决的一个重大课题。 现今，主要的网络储存有三种形式：直接网络存储( d i r e c ta t t a c h e d s t o r a g e ，d a s ) 、网络附加存储( n e ta t t a c h e ds t o r a g e ，n a s ) 以及存储区 域网络口1 ( s t o r a g ea r e an e t w o r k ，s a n ) 。 在网络存储备份h 1 方面，按技术分类，主要分为各份软件技术和备份硬 件技术。备份软件技术可分为通用备份软件技术( 由操作系统所提供的各份 功能) 和专用的备份软件技术。为了提高存储备份效率，大型企业通常选择 那些专业的备份软件，如e m c 公司的s y m m e t r i x 技术和h p 公司的o m n i b a c k 技术。 2 哈尔滨工程大学硕士学位论文 备份硬件技术主要是指磁盘阵列、磁带机与磁带库等硬件备份。企业通 常考虑到存储设备的容量和成本造价来进行选择硬件存储备份设备。其中的 r a i d 是一种高效、快速的被广泛应用在网络系统中海量数据即时存取的网 络存储备份设备。这些数据备份技术，多是针对于大型企业，成本费用比较 昂贵，小型企业很难支付得起这种巨大投资，所以研发低附加成本的、面向 小型企业的局域网络存储备份系统是很有应用价值的。 1 3 国内外研究现状和发展趋势 在国内，网络存储的备份方面，已经有几家研究机构取得了一定的进展。 清华大学高性能计算技术研究所网络存储实验室是国内较早开展海量信 息存储技术研究的课题组。该研究所的研究内容主要包括：海量信息的多层 存储体系结构、海量信息的快速i o 技术、存储容灾技术、存储智能管理技术、 存储高可用技术、存储安全技术、分布式信息服务技术、面向互联网服务的 海量信息存储技术等。 华中科技大学正在进行网络存储系统中虚拟化存储技术的研究。通过虚 拟化网络磁盘阵列，将分布在网络中的空闲资源收集起来构建公共存储池， 实现基本的j b o d 4 5 以及0 级和l 级磁盘阵列。同时还在研究如何构建和管理公 共存储池以及如何定制底层通信协议。j b o d 技术支持热插拔磁盘驱动器，即 可以在不影响数据存储和服务器操作的同时增加或者替换磁盘，拥有一定的 容错能力。 目前国际上i b m 、惠普及i n t e l 等公司都是采用r a i d 技术实现数据的容 错恢复的。r a i d 技术是为了防止存储系统因为磁盘故障而丢失数据而研发出 来的。r a i d 是一种把多个独立的硬盘( 物理硬盘) 按不同方式组合起来形成一 个硬盘组( 逻辑硬盘) 从而提供了比一个硬盘更高的存储性能并提供数据的冗 余技术。r a i d 是利用冗余信息解决恢复损坏的数据。r a i d 中的磁盘阵列可 以保证其中的任何一个磁盘出现了故障都不会导致用户数据的丢失和中断。 快照是当今流行的另一种数据恢复技术。s n i a ( 存储网络行业协会) 对 快照( s n a p s h o t ) 的定义是：关于指定数据集合的一个完全可用拷贝，该拷 贝包括相应数据在某个时间点( 拷贝开始的时间点) 的映像。快照可以是其 哈尔滨工程大学硕士学位论文 昌-i ii ii 一一 t 葺葺宣葺i 肓 所表示的数据的一个复制品。与r a i d 技术相比，快照具有备份和恢复窗口短、 性能损失小、容量利用率高等优点，更适合保护因人为失误等软故障造成的 数据损失。它可以高效地管理一个数据源的多个存储快照，并提供快照的读 写、，创建、回收等功能。另外针对快照技术物理容错性差的缺点，通常把快 照技术与镜像技术相结合起来，这样较好地解决了存储网络软、硬故障时数 据的保护。 e r a s u r e c o d e 编码技术呻1 主要应用在数字通信系统中，应用于传输信道 或其他噪声的存在引起的数据传输及交换过程产生的错误，尤其是远程、高 速传输，它可以有效地避免随机错和突发错。研究分析表明，这种纠错能力 也适用于存储系统中，美国加州b e r k e l e y 大学研发的o c e a n s t o r e 系统口1 ，是 正在研发的面向整个互联网的网络存储系统，在该系统中就是采用 e r a s u r e c o d e 编码技术实现存储数据的容错与恢复。 1 4 主要内容和章节安排 本文根据相关网络存储中数据容错恢复的发展趋势，详细设计了一种简 单且无附加成本的局域网存储数据恢复系统。本文所选取的r e e d s o l o m o n 编译码是e r a s u r e c o d e 中的一种b c h 循环码，其编译码算法较易于实现，并 且已经在数据通讯领域的数据传输纠错中得到了广泛的应用，体现了其巨大 的使用价值。本文在数据存储系统中利用r e e d s o l o m o n 编译码简单易行的纠 错能力，来实现存储信息的容错恢复能力，通过对r e e d s o l o m o n 编译码机制 的数学原理研究，重点分析了它在网络存储中的应用，设计出一个基于该编 译码算法局域网络存储容错恢复系统，并利用f p g a 技术实现了该编译码算 法的硬件设计。 论文共分五章，组织结构如下： 第l 章绪论。简单介绍了本论文的背景、意义以及与网络存储技术和网 络存储备份相关的国内外研究现状和发展趋势。 第2 章e r a s u r e - c o d e 基本理论。介绍了e r a s u r e - c o d e 基本原理。首先介 绍了e r a s u r e c o d e 的相关知识，然后着重介绍了r e e d s o l o m o n 编译码理论。 4 哈尔滨工程大学硕士学位论文 第3 章局域网络存储系统中r s 码软件实现。运用r e e d s o l o m o n 编译码 原理进行设计局域网络存储系统，并对译码算法进行了改进。 第4 章r s 编译码的f p g a 设计与实现。介绍了r e e d s o l o m o n 编译码算 法的硬件设计与实现。 第5 章基于r s 编译码的局域网络存储系统性能分析。首先对基于 r e e d s o l o m o n 编译码的局域网络存储系统可靠性与r a i d 5 系统的可靠性进行 了对比分析，然后验证了改进的译码算法的优越性，最后进行了r s 码算法软 件与硬件的对比分析。 结论部分作为全文的总结，概括了论文的设计思想和主要贡献，并给出 了后续工作的展望。 5 哈尔滨工程大学硕士学位论文 第2 章e r a s u r e c o d e 基本理论 e r a s u r e c o d e 是本文设计和实现高可靠网络存储系统的基础，因此，本 章主要对于e r a s u r e c o d e 的基础理论加以介绍。 2 1e r a s u r e - c o d e 概述 e r a s u r e c o d e 原来是无线通信中有噪信道编码的一种，也叫纠删码。后 来由k a m i n 提出的密钥共享n 町以及m 0 r a b i n 提出i d a 主要( i n f o r m a t i o n d i s p e r s a la l g o r i t h m ) 算法，将其引入到计算机应用中，发展到现在，已有数 十种编码，主要包括r e e d s o l o m o n 码和t o r n a d o 码，最常用的是 r e e d s o l o m o n 码，这两种编译码的主要区别是r e e d s o l o m o n 码适合于编码 参数较小的情况下编译码性能较好。本文主要针对的是局域网络存储，考虑 其编码参数较小，故主要研究r e e d s o l o m o n 码。 2 2 有限域基本概念 有限域n l 垤1 是1 8 3 2 年g a l o i s 弓i 进的，g a l o i s 为了探讨一元高次方程能否用 四则运算和开方求解，创造了著名的g a l o i s 理论，在这一理论中他引进了群 和域这两个概念，人们也因此把有限域称为g a l o i s 域。由于有限域运算的无 进位、固定字长等特性，因而在信息学领域得到了广泛的应用，在现代编码 理论中占有重要的地位。 域是编码理论中一个重要的概念，它是具有两种运算的代数系统。 定义2 1 对于非空元素集合f ，若在f 中定义了在其上的二元代数运算 加和乘，若满足下述公理： 1 ) f 关于加法构成阿贝尔群，其加法的恒等元记为0 ( 又叫零元) ； 2 ) f 非o 元素的全体在乘法运算下构成阿贝尔群，其恒等元( 单位元) 记为l ； 3 ) 加法运算和乘法运算之间满足如下分配率： a ( b + c ) = a b + a c 6 哈尔滨工程大学硕士学位论文 和 ( b + c ) 口= b a + 则称f 为一个域( f i e l d ) 。 其中，包含有限个元素的域就是有限域或叫作( g a l o i s ) 域，元素的个 数称为域的阶。元素个数为q 阶有限域用g f ( q ) 表示。如果q 为一个素数， 则集合 o ，1 ，2 ，q 一1 ) 在模加法和乘法下，构成一个q 阶有限域g f ( q ) 。有 限域在编码理论中具有重要的地位，下面给出g a l o i s 域的几个基本概念和重 要结论n 3 。 定义2 2 以q 为特征的域是g f ( q ) ，m = 1 ，2 ，称g f ( q ) 是g f ( q ”) 的 基域，g f ( q ”) 为g f ( q ) 的扩域。 域中一切非零元素的特征都等于域的特征，且域的特征一定为素数。非 零元素构成的乘法群的阶定义为域中该元素的级。若a 为域g f ( q ) 中的1 1 级 元素，则称口为n 次单位原根。若某一元素口的级为q 1 ，则称口为本原域 元素。域的特征表明了域中加法运算的循环性，而域的级则表明了域中乘法 运算的循环性。 有限域g f ( q ) 中的q 一1 个非零元素构成一个循环群，它其中至少有一个 本原元，它的其它元素分别为这个本原元的j 次幂构成，j = 0 ，1 一，q - 2 。 每一个非0 元素都满足等式：x p l 一l = 0 。在特征为q 的域中，恒有 o 一口) = 妒一口一，式中，口是域中的任一元素。任一元素的级均不是q 的倍 数。特别地，本原域元素的级是q ”一1 ，而其它所有元素的级必为口“一1 的因 子。 对g f ( q “) 上任何元素，恒有c o q “= c o 。它就是著名的费尔马( f e r m a t ) 定理。因此，在q 特征域中，元素为域整数的充要条件是，该元素是方程 x q x = 0 的根。 定义2 3 有限域g f ( q ) 上的n 次多项式为： 厂( x ) = f n x ”+ z l z ”- 1 + + z 工+ f o ， ( 2 1 ) z g f ( p )涪o ，1 ，2 ，l 妫一未知元 对于有限域来说，研究最多的是g f ( 2 ) = o ，1 ) 以及它的扩展域g f ( 2 “) 。 因为g f ( 2 ”) 上每个元素都可表示为多项式的形式，并且多项式的系数在 g f ( 2 ) = 0 ，l 上。 哈尔溟工程大学硕士学位论文 给定任意两个多项式厂( 石) ，g ( x ) 为g f ( q ) 上魄多项式，一定存在有唯一 的多项式q ( x ) 和r ( x ) 使： 厂( x ) = 口( 工) g ( x ) + ，( x ) 0 o o ，( 石) o ) 次首一多项式( 工) 在域g f ( q ) 既约，则由模f ( x ) 所组成的多项 式剩余类环是一个有矿个元素的有限域g f ( q ”) 。若q 特征域的的元素是 方程厂( x ) = 0 的根，则对于一切自然数n 、c o 一也必是厂( 功的根。 若国g f ( q “) ，且为g f ( q ) 上多项式f ( x ) 的根，则“= 国，故 旗矿，矿2 ，矿“必为厂( 工) 的m 个互不相同的根，这m 个互不相同的根称 为的共扼根系。 在q 特征有限域中的每一个元素国，皆存在有唯一的最小多项式，记为 朋( x ) ，则它具有如下性质： ( 1 ) 脚( x ) 在g f ( q ) 域上既约； ( 2 ) 若f ( x ) 也是c o ，c o p ，0 9 ，矿”1 上的多项式，且f ( c o ) = 0 ，则 聊( z ) 厂( 工) 。 若c o 为q 特征有限域g f ( q ”) 中的1 1 级元素，而m 是q 关于模n 的方次 m - i 数，则0 9 的最小多项式m ( x ) 是m 次多项式，且m ( x ) = 丌( 石一) = i 定义2 4 系数取自g f ( q ) 上的以g f ( q 1 ) 中本原域元素为根的最小多项 式，称为本原多项式。若缈是q 特征有限域f 上的m 次域元素，则g f ( q ) 上 的次数小于m 的、缈的多项式的全体构成域f 上的q ”阶子域。 因为有限域的阶一定是其特征的幂，而有限域的特征必是素数q 的幂 q “。因此，若有一素数q ，则一定可以从g f ( q ) 的多项式中选出一个m 次既 约多项式p ( x ) ，以它构造出一个q 4 阶有限域g f ( q “) 。并且该域包含了g f ( q ) 哈尔溟工程大学硕士学位论文 上所有m 次既约多项式的全部根。 如果把p ( x ) 的一个根称为口，则可把q “阶有限域中的每一个元素，表示 成系数在g f ( g ) 上且次数低于1 1 1 的口多项式。而g ，( g ) 上次数小于m 的多项 式与g f ( q ) 的m 重同构。因此，m 重、多项式剩余类环以及口多项式之间均 同构，都可以用来表示g ”阶有限域。 在扩展域g f ( q 胛) 中的g ”一1 个非零元素，都能用本原多项式的根口的多 项式表示，此时 1 ，口，口”1 ) 就是域的一组自然基底或本原基底也称多项式 基底( 也称多项式基) 。若口为g f ( q “) 中的本原域元素，则 缸，口p ，口p 2 ，口，“) 为g f ( q ”) 域的正规基底。正规基底其实就是以口为根的 本原多项式厂( x ) 的共扼根系。 在域的运算和研究中，迹是非常有用的分析工具。 定义2 5 、若口g f ( q “) ，则它在g f ( q ) 上的迹为： z ( 倪) = 口+ 口g + + 口9 4 一( 2 4 ) 其中q 为素数或素数幂。 对于所有口，g f ( q ”) ，迹具有如下性质： z 幢) g f ( q ) z ( a + ) = i ( a ) + i ( ) r r ( 旯a ) = a z ( 口) ，a g f ( q ) z ( a 9 ) = 乃 ) 因此迹是可以把g f ( q ”) 中元素映射到g f ( q ) 中。当且仅当有一个元素 夕g f ( q ”) ，使口= 一9 ，则z ( 口) = 0 。 与g f ( q “) 的基底b = ( , a o ，层，成一。) 相对应，若 z ( 层乃) = ：二i 二 ( 2 5 ) 成立，则称g f ( q “) 的基底b = ( ，乃，一。) 是b 的对偶基，如果 b = b ，则称b 为自对偶基。 9 哈尔滨工程大学硕士学位论文 2 3 循环码与b c h 码 循环码是一类重要的线性码。由于具有以下性质： ( 1 ) 循环码具有严格的代数结构，其性能易于分析； ( 2 ) 并且循环码具有循环特性，其编译码电路，特别是编码电路易于实现。 基于这些特征，循环码特别引入注目，对它的研究和应用也比较深入和系统。 定义2 6 设有一个n 重的k 维子空间圪。k ，若对其中任意一个 y = ( 以纠，口川，a o ) 圪i ，恒有巧= ( a n - l - i ，口柚小，a o ，a 剃) 圪，t ，则称k i 为 循环子空间或循环码。 域g f ( q ) 上的多项式和它上的n 重之间是一一对应的，在( n ，k ) 循环码中， 码字( a n - 1a 川，a 。) 的多项式表示为： 盘( 对= a n _ i x “- 1 + a n _ 2 x ”2 + + q x + ，a f g f ( q ) ( 2 6 ) 它的循环移位一次后所得的码字多项式为： a i ( x ) = a n _ 2 x ”1 + 口 一3 x 4 2 + + 口。工+ - l 相当于乘以x 后，用，一1 取模： x a ( x ) = a n _ i x ”+ a n 一2 x “一14 - + a l x 24 - a o x = a n 一2 x “4 - + x + 以。一i ( n l o d 石4 1 ) 即循环码可以用模x ”一1 的多项式表示。 在域g f ( q ) ( q 为素数或素数的幂) 上的( n ，k ) 循环码中，存在有唯一的n - k 次首一多项式： g ( x ) = x “一+ g - k _ l x “一一4 - + g l 工+ g o ( 2 7 ) ， 使得域中的每一个码多项式都是g ( x ) 的倍式，且每一个次数小于等于 ( n 1 ) 次的g ( x ) 的倍式一定是码多项式。 因此g ( x ) 称为码的生成多项式，它是( n ，k ) 循环码中唯一的n k 次多项式， g ( 石) 一定是x “一1 的因式。因此一个k 维循环码，其最重要的是一个能除尽 ，一1 的n k 次首一多项式g ( x ) ，并由此多项式生成该循环码。 因为每一个码多项式都是的g ( x ) 倍式，因此g ( x ) 的根必是所有码字多项 式的根。 ， g ( x ) 在扩域g f ( q “) 上完全分解： g ( 工) = ( 石一o f l ) ( x 一口2 ) ( x o f r ) q 口，f ，= 1 ，2 ， ( 2 8 ) 1 0 哈尔滨工程大学硕士学位论文 其中g f ( q ”) ，= 一k 。因此每一个码多项式c ( x ) 也必以 q ，a 2 ，q 为根。 1 9 5 9 年h o c q u e n g h e m 以及1 9 6 0 年的b o s e 和c h a u d h u r i 发明了b c h 码， b c h 码纠错能力强，构造方便，编译码简单，有快速的译码算法。这类码具 有严格的代数结构，在编码的理论和实际中都起着重要的作用，也是迄今为 止研究得最为详尽、分析得最为透彻和成果最为丰富的码类n 钔。 b c h 码n 1 1 是能纠正多个随机错误的循环码。这种码是目前所发现的一类 很好的线性纠错码类，它的纠错能力很强，特别是在短和中等码长下，其性 能接近理论值，并且构造方便，编码简单。特别是它具有严格的代数结构， 因此它在编码理论中起着重要的作用。 1 9 6 0 年彼得逊伊( p e t e r s o n ) 从理论上解决了二进制b c h 码的译码算法， 奠定了b c h 码译码的理论基础。稍后，格林斯坦( g o r e n s t e n ) 和齐勒尔 ( z i e r l e r ) 把它推广到多进制。伯利坎谱( b e r l e k a m p ) 利用迭代法译码b c h 码，从而大大地提高了译码速度，从实际上解决了b c h 码的译码问题。 定义2 7 给定任一有限域g f ( q ) 及其扩域g f ( q ”) ，其中q 为素数或素 数的幂，m 为某一正整数。若码元取自g f ( q ) 上的一循环码，它的生成多项 式g ( x ) 的根集合r 中含有以下万一1 个连续根： r2 口j ，l o ，口+ i ，口w - 2 时，则由g ( x ) 生成的循环码称为q 进制b c h 码。 其中口g f ( q ”) 是域中的n 级元素a 帕“g f ( q “) ( 0 f 艿一2 ) m o 是 任意正整数。如果生成多项式g ( x ) 的根中，有一个g f ( q “) 域中的本原域元 素，则刀= g “一1 ，称这种码长玎= q 用一1 的b c h 码为本原b c h 码；否则， 称为非本原b c h 码。g f ( q ”) 中元素的级一定是q “一l 的因子。 2 4r s 码 2 4 1r s 码的简介 r e e d - s o l o m o n 码5 川1 是一类有很强的纠错能力的码n ，是二进制b c h 码 “ 哈尔滨工程大学硕十学位论文 的多进制推广，也是一种典型的代数几何码，它首先由里得( r e e d ) 和索洛 蒙( s o l o m o n ) 应用m s 多项式于1 9 6 0 年构造出来的，所以称为r e e d ，s o l o m o n 码，简称r s 码。 定义2 8g f ( q ) ( q 2 ) 上，码长n = g 一1 的本愿b c h 码称为r s 码。 r s 码是符号域和根域相一致的b c h 码。 长为n = q 一1 ，设计距离为万的r s 码，生成多项式： g ( x ) = ( x - - 口) ( x - - a + 1 ) ( x - - t z + 2 ) ( 2 9 ) 其中是任意正整数，口为g f ( q ) 上的本原域元素。由此生成了一个q 进制的【g 一1 ，g 一翻r s 码，有最小距离万。码最小距离等于校验元的个数加， 所以也称r s 码为极大最小距离可分码，简称m d s 码。在给定每个码字所具 有多少冗余量的情况下，r s 码能够产生极大的最小距离。换句话说，r s 码 的最小距离d 、信息长度k 以及码字长度n 满足s i n g l e t o n 极限，即d = n k + 1 。 除此以外，i 峪码是一种具有纠正多个错误能力的非二元码，任何一个g f ( q ) 上的( n , k ) r s 码，对任何k 个符号位置，将只有一个与这个位置内g 种符号 组合之一相对应的码字。r s 码的另外一个性质是，码字所使用的符号和译码 过程中所使用的符号是一致的，从而使得在译码过程中所进行的运算就是码 符号之间的运算n 。 2 4 2r s 码的编码 因为r s 码是循环码的一种，每个码字都是生成多项式的倍数，在实际 中，常用到的是系统码n 引，信息码元以不变的形式在码字的任意k 位( 通常 是在最前面的k 位) 中出现的码称为系统码n 3 。 设g f ( 2 ”) 上，系统码的矢量为： c = ( g 一。g 一：c o ) 用多项式可表示为： c ( x ) = c k l x - 1 + c 七一2 石- 2 + + c ：j + c o ) ( 2 1 0 ) 能纠正t 个码元错误的r s 码的生成多项式为： g ( x ) = ( x + 口) ( x + 口2 ) ( x + 口2 ) 2 t = 兀( 工+ 口) 哈尔滨工程大学硕士学位论文 所以编码可用除法运算，即将k 1 次的多项式e ( x ) 左移r = 2 t 位( 校验 位) 并用g ( x ) 来除，再将除得的余式与x 2 c ( x ) 相加，即 d ( x ) = x 2 t c ( x ) + c ( x ) m o d g ( x ) 】。 ( 2 1 1 ) 采用系统码编码，所以 d = ( c ，r ) = ( g 一，g 一：c o ，砖一。r 一：r ) ( 2 1 2 ) 其中r 表示校验码组。 每组码字都是定义在它的特定域上的，并且它的符号取自有限域 g f ( 2 ”) ，不同的域都有其相应的域生成多项式，用于计算生成域中的各元素。 多项式的乘除法运算与普通的代数多项式乘除法是相同，多项式的加减法运 算则以2 为模的运算，与逻辑异或相一致。 编码具体方法为用待存储的信息码，( z ) 除以生成多项式，将最后的余数 作为r s 校验码。步骤如下： ( 1 ) 设待存储的数据信息为k 码元，需纠t 个错，则在k 码元后添加2 t ( 最p 蚧码元，发送的数据信息为k + 2 t 码元，对应的多项式为x r f ( x ) 。 ( 2 ) 用生成多项式g ( x ) 去除，i ( x ) ，求得的余数为r - l 阶的多项式，此多 项式即为经过生成多项式编码的r s 码的校验码。 ( 3 ) 用，( x ) 以2 为模的方式加上余式多项式，得到的多项式即为存储的 码字。 2 4 3r s 码的译码 r s 译码又称解码，主要分成3 步： 第一步由读取的存储码组计算出伴随式； 第二步由伴随式求解出错误图样； 最后由错误图样和接收码组计算出可能存储的码字n 劓。 译码算法主要有时域译码算法和频域译码算法，因为该译码算法和其它 算法比较有很多优点：首先，时域译码算法实现比较简单，易于用计算机完 成译码。其次，利用时域译码算法不需要进行傅立叶变换和逆傅立叶变换n 9 l ， 比起频域译码算法要简洁得多，减少了很多运算。所以本文采用基于时域的 译码算法。 r s 码的译码算法的复杂性主要归结为关键方程的求解，即错误位置多项 哈尔滨工程大学硕七学位论文 式的求法。时域译码算法应用较为普遍是b m 迭代算法，极大地加快了求错 误位置多项式仃( x ) 的速度，使译码速度能满足多数应用的需要n 引。 假设所要存储的码字为： c = ( c n l ，巳一2 ，c 1 ，c o ) 1 用多项式可以表示为： c ( x ) = q l x ”1 + c n 一2 x ”1 + + q x + c o ) ( 2 1 3 ) 由于存储过程中出现故障，使读取的码字为： r = ( 一l ，一2 ，r l , t o ) 其多项式表示为： r ( x ) = ，：i l 石4 1 + ，：i 一2 x 卜1 + 、+ f i x + t o ) ( 2 1 4 ) 所以错误图样e = ( 巳中乞彩，e l ，e o ) 与存储码字和读取码字具有下面的 对应关系： r=c+e(2-15) r s 译码算法比起编码算法要复杂得多。译码算法是对读取到的码字进行 运算来确定信息码域校验码是否符合编码规则，从而利用所观察到的情况进 行判断并尽可能的对出现的错误加以纠正。 r s 译码第一步是接收序列r ( x ) 计算伴随式，伴随式又称校正子，一个 纠t 重错的r s 码，伴随式是2 t 重，即s = ( s ，是，是，) ，其中s = r ( a ) 。 伴随式完全由错误样图e 决定，它能够反映出读取到的码字的差错情况。 然后是求解出错误位置c r ( x ) ，为了能纠正出错误的码字，必须要确定错 误码字的位置。 在求得出错误位置后，再求出相应错误位置的错误取值，最后将得到的 错误值修改并加到相应的错误位置上。r s 码译码具体步骤如图2 1 所示。 1 4 哈尔滨工程大学硕士学位论文 2 5 本章小结 ( 开始 ) 读取存储数据码元 根据存储数据码元来计算伴随式 + 确定错误位置多项式 解出错误位置多项式的根 计算错误值 对求出的错误位置与错误值进行纠正 对纠正过的码再进行伴随式计算 结果为0 ，纠正 结果不为0 ，表明 成功 超出t 个错 ( 结束 ) 图2 1r s 译码过程 本章介绍了e r a s u r e c o d e 的基本概念与原理，阐述了有限域的概念和在 有限域里的一些重要定义、性质以及运算规则，并着重介绍一类纠错能力很 强的多进制b c h 码r e e d s o l o m o n 码。本章为论文后续具有数据容错恢 复的局域网络存储系统的设计打下了理论基础。 哈尔滨丁程大学硕士学位论文 第3 章局域网络存储系统中r s 码软件实现 当前，企业信息化程度的提高，自动化办公能里的提升，计算机几乎已 经遍及到了技术人员的办公桌上，使得企业所要存储的数据信息也相对猛烈 迅速的增长。小型公司往往承担不起巨额的数据信息存储备份系统的硬件购 买费用，所以设计出针对局域网络存储的容错备份软件系统是很有价值的。 3 1r s 码选取 r s 码对于多重的错误具有相当高的检测和纠正能力，其主要参数t ，表 示能纠正到的错误数据个数，同时也能检测到2 t 个未知错误数据。为了能够 达到纠正t 个错误数据的能力，需要增加2 t 个冗余数据汹1 。 通常在诸如学校的实验室，公司的办公室以及小型的企业网络都采用简 单的局域网络连接其内部计算机，计算机的数量大体在几台到十几台之间。 由于r s 码是( n = q ，k , d = n - k + 1 ) 的线性码，对于每一组q 与k ，都能实现一组 r s 码的实现。每个r s 码的码字是一组有限域的符号，其中每一个符号都是 伽罗华域的元素，r s ( n ，k ，d ) 码参数具体介绍如下： m ：每个符号比特数； 1 1 ：码长挖= 2 ”一l ： t ：纠错符号个数； d ：码距d = 2 t + 1 ： k ：信息符号个数； 也因为在1 5 = 2 4 1 ，容易在g f ( 2 ”) m = 4 上实现，该码的编译码过程所 以本文的系