资源描述
Abstract
The world in the future will be a world built upon full of various information. When people began an age called information age in the 20th century, it would never stop and develop faster and faster. As the information increase exponentially nowadays , we’re sure this world will be always together with the information everywhere in the 21st century and the future: whether personal life , work , study ,or industry production , finance system , national defense , etc , all social activities of people will be informationed all-around. In this case, there is no doubt in the information society; the key resource is the data which are stored in billions of devices and terminals.
However, just because every society unit is concerned with data, the security of data self has become the most serious problem that people have to be in the face of. Compared with the regret of personal commemorable data’s damage, the bank and finance system, corporation group, the government, the army and national defense, the spaceflight, once the stored data of these units of society is destroyed, it will cause enormous economy damnify and even worse. Economy and finance system’s sudden paralysis, wining victory without battle will be the truth, and the key reason of that is whether the data is secure or not. The data is secure? No, damage of computer virus, fire, earthquake, terrorism attack, man-made wrong operation, bugs of logic system, especially the inevitability of physical damage, all these have said that whether the storage device is good or not, the data will not be secure absolutely.
In the face of above cases, this paper attempts to break through the bottleneck of data security with another way. Through study of Error Correction Code and Finite Field theoretics, this paper tries to apply the Reed-Solomom arithmetic based on Finite Field Galois Field to Redundant Array of Independent Disk, and tries to realize a simple RAID6 level programme, thereby could offer an idea for securer storage device.
Keywords: Reed-Solomon theoretics 、Error Correction Code 、RAID6 、 Redundant Array of Independent Disk 、 Finite Field 、 Galois Field
第一章 绪 论
1.1信息时代数据存储安全的极端重要性
未来的世界将是一个用0和1来进行描述的世界，随着二十世纪末人类开启了信息时代的大门，世界信息化的脚步就越走越快，爆炸式的信息增长趋势已注定人类的二十一世纪及未来将会和无处不在的信息形影不离：无论是人们的个人生活、工作、学习，还是工业生产、金融、国防，人类所有的社会活动将全面进入被信息化的时代。显而易见，对于这样的一个信息社会来说，其核心的社会资源无疑将是存储在数以亿计各式终端中的各类数据。根据IDC(国际数据资讯)的调查显示，截止到2003年，全球计算机数据存储量已达2000000TB，并且能够保持以每年80%的速度在增长，而预计到了2008年，仅中国就将达到139415TB（IDC数据）的外部磁盘存储容量，可以预见，在不远的将来，一个真正数字化的信息社会将在人类的面前实现。
然而，正是因为社会的每一个单元都开始变得和数据息息相关，数据存储本身的安全就已然成为人们首要也是必须关心的核心问题。珍藏的数码照片，个人的影像资料，各种私人文档、统计表格，甚至是个人的科研成果等等，这些对于个人用户来说极为重要的存储数据一旦遭到破坏，将会是莫大的遗憾和惋惜；而对比以上这些个人数据，银行金融系统，大型企业集团，国家政府机构，军队国防系统，航空航天等等，这些社会单元的数据资料一旦遭到破坏，将会造成巨大的经济损失，甚至会更为严重。在不远的将来，可以想象一个国家甚至世界范围内的金融经济在一瞬间瘫痪，可以想象在战场上兵不血刃就可以摧毁敌方的防御能力，可以想象一个大型的企业集团因为核心资料被破坏而无法运作，而在人类探索太空的道路上，资料数据的存储安全更是极为重要。
结论是很明显的，在未来这个被全面信息化的世界里，绝大部分的社会单元，社会活动都是以存储在介质上的数据资料作为核心的，其安全的极端重要性，正是人们必须迫不及待关心的重大问题。
1.2当今数据存储及数据安全的现状
1.2.1数据存储概况
数据的存储是指根据不同的应用环境通过采取合理有效的方式将数据保存到某些介质上并能保证有效的访问，当今对数据的存储可以从四个方面进行分类：
一是按照使用的方式，可以分为移动存储设备和非移动存储设备；
二是按照存储的介质进行分类，可以分为光介质存储、电介质存储和磁介质存储；
三是按照传输速度的快慢或访问频度进行分类，可以分为在线存储、近线存储和离线存储；
还有一种就是按照存储设备与服务器的连接方式分类，目前可以有存储设备与服务器直接相连的DAS(Direct Attached Storage,直连方式存储)，和存储设备需连接到TCP/IP网络中的NAS(Network Attached Storage网络连接存储)方式。
而在这几种不同角度的分类中，我们可以看出，最基本的存储要素还是采用何种存储介质进行存储，就当前的发展而言，磁存储仍然是世界主流的存储介质，那么，目前数据存储的安全性如何呢？
1.2.2数据存储的安全性现状
虽然计算机存储的安全技术在不断的快速发展，但是，显然还跟不上世界信息化过程中数据爆炸式增长、数据重要性日益升高对数据存储安全的需要，就目前而言，以下几个方面的影响仍然是数据存储安全保障的大敌：
I．计算机病毒的破坏：
充斥在计算机世界的各种病毒程序随时随地都会对数据、重要数据产生重大的威胁，它们要么使数据表现失效，不能够被正常访问，要么干脆就毁掉数据，使数据不能够再生，以1999年在全球爆发的CIH病毒为例，仅一波攻击就导致全球超过六千万台计算机数据遭到破坏，造成超过10亿美元的直接或间接经济损失。
II．逻辑系统的设计缺陷：
数据在存储过程中是必须需要软件来对数据进行组织和管理的，例如，文件系统就是用来管理存储在磁盘上的数据的管理系统，然而，这些软件产品却很难做到十全十美，万无一失，在实际的应用中，由于设计上的难于发现的bug或一些莫名奇妙的原因，导致数据失效的情况不足为奇。
III. 人为误操作：
人们在对计算机数据进行管理和操作时，偶尔会出现人为的失误，这种失误有时将会导致严重的数据被破坏的后果，例如，对数据进行误删除，误格式化，对存储设备进行误插拔等等，这些不可百分百避免的人为事故都是数据安全的大敌。
IV. 恐怖袭击
人为的恶意破坏，要求数据的存储系统能够提供尽可能多的对于数据的保护及尽可能强的灾难恢复功能。
V. 地震，火灾等
同样，大自然不可抗力的破坏，也对数据存储的安全构成重大威胁，也同样要求存储系统能够提供尽可能多的对于数据的保护及尽可能强的灾难恢复功能。
VI. 物理介质损坏的必然性
物理介质存在出现故障的可能的必然性，是威胁数据存储安全的又一重要原因，不管有多么优秀的设计技术，多么优秀的质量，作为一种机械设备，单个的磁盘存储器都必然会有发生故障的可能，而恰恰是这种不可预见的对于数据的破坏，形成了当今数据存储安全的一个瓶颈。
因此，就目前而言，数据存储的安全现状并不容乐观，人们仍需找出一种能够尽可能保证数据安全的方法，这也正是本文努力的方向。
1.3 本课题的研究内容及实现目标
正是针对目前数据存储的现状，本文试图换一个角度，采用多个磁盘存储设备协同配合，对数据进行冗余存储的方法，即磁盘阵列技术，尝试突破数据存储安全的瓶颈，从而为实现更加安全的数据存储技术提供一种思路。
其中，本课题的具体研究内容包括以下几个方面：
◆RAID6磁盘阵列模型的构想及功能实现原理
◆有限域代数及二元域运算的研究
◆基于Galois域GF（）的Reed-Solomon算法
◆基于Galois域GF（）的Reed-Solomon算法的程序实现及在RAID6阵列中的应用
◆P校验、Q校验的程序实现
◆基于Galois域GF（）Reed-Solomon算法的RAID6磁盘阵列的模拟实现
◆基于Galois域GF（）Reed-Solomon算法的RAID6磁盘阵列数据恢复功能的模拟实现
最终，本课题将模拟一个基于Reed-Solomon算法的RAID6级别的磁盘阵列(以4块磁盘驱动器为例)，并成功完成在两块磁盘驱动器(模拟)失效的情况下，对存储于其中的数据进行百分之百的恢复。
1.4 本课题在领域内研究的现状
作为一项刚刚开始进入实际应用的新技术，RAID6模型的设计，算法的实现及产品的开发还未形成统一的规范和标准，正如美国企业管理协会(Enterprise Management Associates)资深分析师Mike Karp所说：RAID6磁盘阵列提供了重要的资料保障升级，让存储数组以合理的成本获得更完善的保护。对于那些读取频繁的应用系统，如任选视讯与其它固定内容应用等，RAID 6将是最理想的选择，也将是最获得市场青睐的磁盘阵列技术。
因而，作为行业先驱者的各大厂商均按照RAID6所构想的基本目标要求纷纷推出了自己的RAID产品并形成自己的RAID6规范和标准，2005年末，Promise公司及Intel存储事业部等就推出了自己的RAID6双重校验码硬盘存储架构产品。
因此，本文也将按照RAID6所构想的基本目标要求，通过对有限域代数、基于Galois域的Reed-Solomon算法的研究，将该算法应用于RAID6磁盘阵列及RAID6数据恢复的算法研究，最终完成基于Galois域GF（）Reed-Solomon算法、拥有创建和数据恢复功能的RAID6磁盘阵列(以4块磁盘驱动器为例)的模拟实现。
第二章 RAID(Redundant Array of Independent Disk)独立冗余磁盘阵列理论基础与RAID6模型的建立
2.1 什么是独立冗余磁盘阵列
正如前所述，单个磁盘存储介质的安全性是难以保障的，最根本的原因在于其作为一种机械设备，必然会有物理上的损坏，从而造成不可预期的数据破坏。正是在这种情况下，采用多个磁盘驱动器协同工作，利用数据的冗余存储而避免数据被彻底破坏的方法应运而生，这种方法就是RAID(Redundant Array of Independent Disk)独立冗余磁盘阵列。
RAID技术最早是由加州大学伯克利分校于1987年提出的，但它最初的目的却并不是为了专门应用于数据的安全领域，而是为了组合小的廉价的磁盘来代替大的昂贵的磁盘，因为当这种方法提出时，几个小容量磁盘驱动器的价格总和要比同等容量的一个大容量磁盘驱动器的价格便宜得多，因此，RAID一词最初的含义为Redundant Array of Inexpensive Disks，即廉价磁盘冗余阵列。到了后来，当不存在以上所说的价格问题的时候，我们发现采用这种磁盘驱动器阵列的方法，把数据进行冗余后再进行存储，可以大大的提高数据存储的安全性，这时，RAID才正式更名为Redundant Array of Independent Disk，也就是独立冗余磁盘阵列。
独立冗余磁盘阵列实际上是指一种由多块磁盘驱动器按照一定的要求构成的冗余阵列，在操作系统中，这多块磁盘驱动器将作为一个独立的大型存储设备而出现。RAID按照不同的需求和设计要求分为不同的级别(level)，需要说明的是，各个级别的差异是根据用户对于其需求的不同而设定的，之间没有性能上的比较，也不存在高级别是低级别的性能升级的情况。当有数据需要存储时，待存储数据首先需要按照不同级别的RAID系统的规定进行相关的处理，主要是加上冗余位信息，然后再和冗余位信息一起作为新的数据存入磁盘阵列当中。
RAID，作为一种由多个存储设备组成的、能够协同工作的存储设备，可以充分发挥出其多个存储设备的优势：它既可以提升存储的速度，更可以增大容量 , 利用冗余信息位的作用，它很好地提供了对于数据的容错与数据灾难的恢复功能，不会因为单个存储设备的损坏而造成对数据的破坏，有的级别的RAID系统还能够保证在若干存储个体出现故障时整个系统仍可以继续正常工作。
2.2 已成功研发的各级别(level)RAID系统原理、性能比较与原因分析
RAID技术从发明到现在，得到了迅速的发展，目前，已成功研发出的各级别磁盘阵列系统在各个领域得到了使用，其中，我们就最主要的RAID系统的工作原理、性能比较和原因分析如下：
RAID 0 ：
RAID 0，我们又称之为Stripe或Striping，即条带型存储，它代表了所有RAID级别当中最高的存储性能。RAID 0提高存储性能的原理在于把连续的数据分散地存储到了多个磁盘驱动器上，这样，当系统有数据请求时，就可以由多个磁盘并行的同时执行，每个磁盘驱动器执行属于它自己的那部分数据请求。这种数据上的并行操作可以充分利用总线的带宽，从而可以显著提高磁盘整体的存取性能。
图2.1
RAID0的具体原理模型如图2.1所示：当操作系统向三个磁盘组成的逻辑硬盘（RAID 0 磁盘组，在操作系统中表现为一个存储器）发出I/O数据请求时，该请求被转化为了3项操作，其中的每一项操作都对应于一块单一的物理硬盘。我们从图中可以清楚的看到，通过建立RAID 0磁盘阵列，原先顺序的数据请求被分散到所有的三块磁盘驱动器中同时并行执行。从理论上讲，三块磁盘驱动器的并行操作可以使同一时间内磁盘读写速度提升3倍(当然，由于总线带宽等多种因素的影响，实际的提升速率肯定会低于理论值)，与单一的串行传输相比较，当大量的数据进行并行传输时速度的提升效果是十分显著的。
但是，RAID 0有一个明显的缺点，即它并没有提供数据的冗余处理，因此谈不上对数据拥有安全性能上的保护，一旦数据遭到破坏，则损坏的数据将无法得到恢复。
综合来看，RAID 0磁盘阵列所具有的特点，使其特别适用于对存储性能尤其是存储速度要求比较高，但对数据安全不太在乎的领域，如图形工作站等。当然，对于个人用户，RAID 0也是提高硬盘存储性能的绝佳选择。
RAID 1：
RAID 1，我们又称之为Mirror或Mirroring，即镜像磁盘阵列，RAID1的宗旨是最大限度的保证用户数据的安全性和可恢复性。 RAID 1的操作方式是把用户写入磁盘驱动器的数据百分之百地自动复制到另外一个磁盘驱动器上。如图2.2所示：
图2.2
当操作系统读取数据时，系统先从Disk 0上开始读取数据，如果读取数据成功，则系统不再去管备份磁盘驱动器上的数据；而如果读取数据失败，则系统自动转向读取备份磁盘驱动器上的数据，从而不会造成用户工作任务的中断。当然，这也需要及时地更换损坏的磁盘驱动器并利用备份数据重新建立Mirror，避免备份磁盘驱动器同时发生损坏时，造成不可挽回的数据损失。
在RAID1中，由于对存储的数据进行了百分之百的备份，因此，RAID 1提供比较高的数据安全保障。但与此同时，同样由于数据的百分之百备份，备份数据占据了总存储空间的一半，因而，RAID1的磁盘空间利用率低，存储成本较高。
总的来看，RAID1虽不能提高存储性能，但由于其具有较高的数据安全性，使其尤其适用于存放重要数据，如服务器和数据库存储等领域。
RAID 0+1：
正如这种RAID的名字一样RAID 0+1是RAID 0和RAID 1的组合形式，也称为RAID 10。
我们可以以四个磁盘组成的RAID 0+1为例来分析它的原理，其数据存储方式如图2.3所示。
RAID 0+1是兼顾存储性能和数据安全性的方案。它在提供与RAID 1一样的数据安全保障的同时，也提供了与RAID 0近似的存储性能。
但由于RAID 0+1同样通过数据的100%备份的方式来提供数据安全的保障，因此RAID 0+1的磁盘空间利用率与RAID 1是相同的，它的存储成本也比较高。
RAID 0+1的特点使其特别适用于既要求有大量数据需要存取，同时又对数据安全性要求特别严格的领域，如银行、金融、商业超市、仓储库房、各种档案管理等。
图2.3
RAID 5：
RAID5磁盘阵列在目前为止是一种集存储性能、数据安全和存储成本可以兼顾的存储解决方案。
我们可以以四块硬盘组成的RAID 5为例来分析它的工作原理，RAID5的数据存储方式如图2.4所示：
图2.4
在这样的模型当中，P0为数据D0，D1和D2的奇偶校验信息位，P1、P2等其它条带均以此类推。
由图中可以看出，RAID 5并没有像RAID1那样对存储的数据进行百分百的备份，而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上，并且奇偶校验信息和相对应的数据分别存储于不同的磁盘驱动器上。这样，当RAID5的一个磁盘数据发生损坏后，利用剩下的数据和相应的奇偶校验信息就可以恢复被损坏的数据，也正是因为如此，所以应用RAID5磁盘阵列的存储系统在一块磁盘驱动器失灵的情况下能够保证整个系统仍然正常工作。
在性能上，RAID 5可以理解为是RAID 0和RAID 1的折衷方案。RAID 5可以为系统提供数据的安全保障，但保障程度要比RAID1低而磁盘空间利用率要比RAID1高很多。RAID 5具有和RAID 0相近似的数据读取速度，而在写入方面，由于只多了一个奇偶校验信息，写入数据的速度对比单个磁盘进行写入操作稍慢。同时由于RAID 5的磁盘空间利用率要比RAID 1高很多，所以存储成本相对较低。
2.3 继承与发展，RAID6独立冗余磁盘阵列的设想与模型的建立
分析了到目前为止已成功开发的RAID磁盘阵列的原理及性能，我们发现，RAID5是唯一能够兼顾数据存储性能、数据安全性以及应用成本的RAID阵列系统，但是，在实际的应用中，我们发现，在对数据安全性要求更高的情况下，RAID5仅允许一块磁盘驱动器出错的性能经常不能满足要求，在一些领域仍旧会造成巨大的经济损失。因此，我们能不能进一步发展，使得在磁盘阵列中即使有两块磁盘驱动器失灵的情况下，仍能保证系统的正常工作，并且能够保证数据的安全恢复，RAID6磁盘阵列的设想应运而生，这也正是本文尝试研究的方向。
2.3.1如何实现更高的数据安全性
如何才能做到使阵列在两块驱动器不工作的情况下，仍能够进行工作并保证数据的安全呢？我们分析，最关键也是最直接的要点在于，如何能够重新利用起这两块失效硬盘中的数据。
如何才能重新利用起两个失效的驱动器中的数据呢？我们借鉴一下RAID5磁盘阵列的原理，在RAID5磁盘阵列中，巧妙的利用了一个奇偶校验位P，令P=D1⊕D2⊕D3...⊕,这样，当其中一块磁盘驱动器失效时，可以由剩下的N-1个数据块重新计算出失效数据块(驱动器)的内容，进而保证了在一块磁盘驱动器失效情况下的数据安全性。
我们再联想一下初等代数中最简单的二元方程组，是不是可以将失效的两块磁盘驱动器上的数据块内容看作是方程组中的两个未知数，这样，通过解这个方程组就可以重新生成已经不复存在的数据了。那么，如何才能得到这个方程组的两个方程呢？
延伸RAID5的想法，我们显然可以把P=D1⊕D2⊕D3...⊕看作是这个方程组中的一个方程，显然，要想得到另一个方程，就需要再重新定义一个冗余数据块，作为第二个数据校验位，我们把它称为Q。采用什么算法生成Q将在后文当中论述，我们首先来看一下根据以上的设想和想法，如何确定出RAID6磁盘阵列的阵列模型。
2.3.2 RAID6模型的设想与建立
RAID5磁盘阵列之所以能够兼顾数据存储性能、数据安全性以及应用成本，一是因为它引入了校验位，而不是像RAID1那样进行百分之百的备份，这在保证安全性的同时也降低了成本，二是因为RAID5将校验位与各数据位混合，进而均匀的分布在磁盘驱动器上，使得在数据的读写过程中各存储器的负载保持平衡。不难看出，既然我们设想RAID6是需要在RAID5的基础上再引入一个校验位，那么，RAID5阵列的模型将会对RAID6磁盘阵列的模型设计具有重要的可借鉴性。
经过比较和研究，现在给出一种本文认为理想的RAID6磁盘阵列的模型(以总共4块磁盘驱动器为例，每一个条带两个真实数据)，绘图如下：
图2.5
在这个RAID6模型中，为数据块，P仍为各条带(stripe)真实数据的奇偶校验位，且P=D1⊕D2⊕D3...⊕，⊕为抑或运算，Q为新定义的一种校验位，这样，便实现了引入两个校验位对待存储数据进行冗余运算并均匀的分布在了阵列的各个磁盘驱动器上，使各存储器读写操作时达到负载平衡。
那么，Q校验位应该如何得出呢？Q校验的作用在于，和P校验一起构成用于恢复数据计算的二元方程组，因此，我们仍就可以从简单的实数方程组中得到灵感，我们知道，对于一个拥有两个未知数的问题来说，只要由他们组成的方程组中两个方程不重复，那么就一定可以得到有效解，例如：如下方程组 ，一定可以得出x= -4，而y=9，那么我们就可以在
P这个奇偶校验方程的基础上，仍旧采用异或运算，得到一个添加了系数的方程
……..
从而，P、Q方程联立便可以组成能够计算出D1与D2的方程组。
但是，我们很快就会发现一个明显的问题，我们知道，在计算机中，所有的数据都将转化成二进制的0和1来表示，这样的话，Q方程中的系数、、等等就必须保证它们在作用之后，不会改变D1、D2等这些数据的所属范围，否则的话，这些数据将不能够被计算机所识别，那么，、…该取怎样的值呢？这也正是本文接下来要探讨的另一个重要问题。
第三章 Reed-Solomon算法理论探究
正如上文所述，如何取得Q方程中各系数的值是成功开发RAID6技术的关键，经过研究和比较，我们发现可以利用基于一个伽罗华域的Reed-Solomon算法来解决这个问题，本章将尝试给出这个问题的答案。
3.1 群、环、域的基本概念和性质
3.1.1 群的基本概念和性质
在代数系统中，群是这样定义的：
设G是非空集合，并在G内定义了一种代数运算，若满足如下4个条件，则称G为一个群：
1) 封闭性。对任意a∈G,b∈G,恒有ab∈G。
2) 结合律成立。对任意a∈G,b∈G，c∈G,恒有(ab)c = a(bc)。
3) 若G中有一元素e，对任意的a∈G,满足ae = ea = a ,则e称为单位元或恒元。
4) 若对于任意a∈G,G中存在有另一个元素，使a=a = e,则称为a的逆元。
在一个群中，若它的二元运算满足交换律，即若a∈G,b∈G,有ab = ba ,则称这个群G为一个交换群，或者称为Abel群。
设(G，·)为群．对于任意a∈G，使＝e成立的最小自然数m称为a的阶或a的周期。
设(G,)为一个乘法群，如果存在a∈G,a的阶为n，使得
G = {e,a,,…,}
则称G为n阶循环群，此时a称为生成员或本原元。
在一个群中，具有以下两条性质：
① 群G中恒元是唯一的。
② 任一个群元素的逆元是唯一的。(证明略)
由群的定义和性质，进而我们可以得到在代数系统中，环这种结构的定义和性质。
3.1.2 环的基本概念和性质
在代数系统中，环是这样定义的：
在非空集合R中，若定义了两种代数运算加和乘，且满足：
1) 集合R在加法运算下构成Abel群。
2) 乘法有封闭性，即对任何a∈R,b∈R，有ab∈R。
3) 乘法分配律与结合律成立，即对任何a∈R，b∈R和c∈R，有
a (b+c) =ab + ac
(b+c)a = ba + ca
(ab)c = a(bc)
我们则称R是一个环。一个环同样有几个最基本的性质：
对于任何的a∈R和b∈R,有
① a0 = 0a = 0。
② a(-b) = (-a)b = -ab。(证明略)
下面，我们再进一步由群和环的定义引出“域”这个重要的概念
3.1.3 域的基本概念
对一个非空元素集合F，若在F中定义了加和乘两种运算，且满足
1) F关于加法构成Abel群，其加法恒元记为0。
2) F中非零元全体对乘法构成Abel群，其乘法恒元记为1。
3) 加法和乘法间有如下分配律：a(b+c) = ab + ac，(b+c)a = ba + ca
我们则称F是一个域。
我们不难看出，域实际上是一个可交换的、有单位元并且非零元素拥有逆元的环。在本
文中，域是一个非常重要的代数结构，但是，我们还不能直接利用域的性质来解决第二章中提出的关键性问题，而是还要进一步的对域进行要求，得出有限域的概念和性质。
3.2 有限域的定义及有限域的性质
简单的说，有限域就是元素可以有q个不同的值的域，有限域又可以称作伽罗华域，名称来源于法国数学家皮尔伽罗华(Pierre Galois)，一个含有q个不同元素的伽罗华域记为GF(q)。
通常，有三种典型的有限域：
1)二元域GF(2)。集合{0，1}在模2加法和模2乘法下，是两个元素的域GF(2)。
2)P元域GF(p)。令p为素数，集合{0,1,…，p-1}在模p加法和模p乘法下是阶为p的域，称为素域GF(p)。
3)扩域GF()。将素数GF(p)扩展成由个元素的域，即得GF(p)的m次扩域GF(q)。扩域GF()可以用一个多项式p(x)来进行描述(见后文)。
在本文中，我们最终的目的是利用这三个典型有限域的特点和性质，构造出基于二进制域(二元域)的扩域GF()。下面，我们首先来定义在二进制域中最重要的一种运算：模2运算。
3.2.1 模2运算与有限域中元素的逆元
模2运算，即定义：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1
仔细观察这种运算的定义我们会发现，在这种运算的“+”部分，实际上是等同于布尔运算当中的异或运算⊕的。
这样，在一个二元域中，由域的定义，我们构造它的两个运算，加法为模2加法，乘法为模2乘法：
1)对所有元素：
0 + 1 = 1 + 0 = 1
0 + 0 = 0
1 + 1 = 0
可得，在加法运算中，恒元为0，并且每一个元素(0和1)的逆元都是它本身，这样，在模2运算中，加法和减法实际上是等效的。
2)对所有非零元素：
1 × 1 = 1，即恒元为1，逆元仍为其本身。
综上，我们得出结论，在采用模2运算的二元域中，每个元素的逆元就是它本身。
3.2.2 域元素的阶与本原元素
定义一个q元有限域GF(q)，设a∈GF(q),根据GF(q)在乘法下的封闭性，有
∈GF(q),i=1,2,3…
由于域中仅包含有限个元素，所以中必然有重复，故一定存在k<m,使
=
也即 = 1
因此，必然存在一个最小正整数n ，使
= 1
我们称n为域元素a的阶。
利用域元素阶的概念，可以得出以下几个重要结论
1) 设，∈GF(q)，若i+j<=n,则
=
若i+j>n,且i+j = n+r(0<r<=n),则
=
故元素=1和，，…，在GF(q)的乘法下形成了一个循环群。
2) 若a∈GF(q),a0,则有
= 1
3) 若a∈GF(q)，a0,n为a的阶，如果n = q-1，则称a是GF(q)的本原元，根据本原元的定义，a的各次幂将生成GF(q)的所有非零元素。
3.3 二元域的运算
了解了典型有限域的一些基本运算法则，我们进一步探讨一下关于二元域的相关算法，从而为最终我们构造出扩域GF()做好铺垫。
3.3.1 系数取自GF(2)的多项式
对于(n+1)比特的二进制数字序列，可以用多项式来进行描述：
上式称为GF(2)上的n次多项式。其中系数0或1是二元域GF(2)的元素，0<=i<=n,与二进制数字序列的对应值相同， 代表着对应系数所在的位置。例如，数字序列1001001100111001，其对应的多项式为
3.3.2 既约多项式
在这里，我们给出既约多项式的定义：
若GF(2)上的m次多项式不能被GF(2)上的任何次数小于m但大于零的多项式除尽，就称它是GF(2)上的既约多项式。例如：
是2次既约多项式
是4次既约多项式
对于GF(2)上的任意m次既约多项式，都能够除尽，例如2次既约多项式能够除尽，3次既约多项式能够除尽等等
3.3.3 本原多项式
知道了既约多项式的概念，我们进一步给出本原多项式的定义：
若m次既约多项式p(x)能除尽的的最小正整数n满足，则称p(x)为本原多项式。
例如，既约多项式的m = 3，它能够除尽，但是却除不尽、、，所以是一个本原多项式。
在数学参考文献中，已经给出了m<=24的部分本原多项式的表格，在这里，我们给出后文能够用到的三次本原多项式：
(m = 3)
和8次本原多项式：
(m=8)
3.4 基于Galois域GF()的Reed-Solomon算法
3.4.1 Galois域GF()的构造
1）由GF(2)构造出个元素(m>1)
我们设p(x)是GF(2)上的m次本原多项式，为p(x)的根，即有p() = 0,由本原多项式的定义，可以得到以下表达式：
= q(x)p(x) (q(x)为一多项式)
带入根，可得：
= q()p() 即
= 0 由于做的是模2运算，所以可以得到
= 1
根据前文的内容，我们发现，对于一个拥有个元素的Galois域，正是其本原元素，因此，我们可以用来生成GF()中的其他元素(非零)：、、、…、，由此，我们定义 = {0,1, ,,…，}，则为一个有限域。下面，本文给出证明。
2) 证明中全体非零元素在乘法下构成一个可交换群
设 0<= i,j<
若 i + j < ,则 = 是中的一个非零元素
若 i + j>= ,且i + j = () + r ,0<= r < ,则 = = = ， 也是中的一个非零元素。
所以，我们得出结论，中的全体非零元素在乘法下是封闭的，并且，中的非零元素在乘法下满足交换律和结合律，有恒元1，有逆元(与互为逆元)。即，中的非零元素在乘法下构成了一个可交换群。
3） 证明在加法下构成一个可交换群
对于0 <= i< ,用p(x)去除多项式，得
=p(x) +
式中为商式，为余式。因为p(x)是m次多项式，所以的次数小于或等于m-1,将其记为：
设为p(x)的根，即p() = 0,则
=
在模2加法下，对0 <= i,j < ,有
0 + = + 0 =
且 + = ()+
=
若i = j,则上式为0，若i j ,则上式必为中某个的多项式，即在定义的加法下拥有恒原0，逆元为每个元素本身，
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
