用于存储数据信号的编码方式

1.一种对用于存储的数据信号进行编码以对一种存储介质中的一 个存储单元进行容错的方法，包括：
对于N+2个存储单元，N是一个正整数，又将每个存储单元分成 N个存储块，由(N)(N)个数据信号块产生出2N个奇偶校验信号块；以 及
将N(N+2)个奇偶校验和数据信号块分配在存储介质的N+2个 存储单元中，以使2N个奇偶校验信号块不是仅仅存储在N+2个存储 单元中的其中两个单元上。
2.如权利要求1所述的方法，其特征在于所述的2N个奇偶校验 信号块中包含水平奇偶校验信号和对角奇偶校验信号。
3.如权利要求2所述的方法，其特征在于产生的对角奇偶校验信 号实质上是按照下述等式：
D(i，N-1-i)＝D(i，j)，其中j＝0至N，j≠N-1-i，0≤i≤N-1。
4.如权利要求2所述的方法，其特征在于产生的水平奇偶校验信 号实质上是按照下述等式：
D(i，N+1)＝D(N-1-j，(N-i+j)mod(N+1))，其中j＝0至N-1，0≤i ≤N-1。
5.如权利要求2所述的方法，其特征在于对角奇偶校验信号只存 储在N+2个存储单元的其中一个单元中。
6.如权利要求5所述的方法，其特征在于水平奇偶校验信号被分 配存储在N+2个存储单元的仅N个单元中。
7.如权利要求6所述的方法，其特征在于N+2个存储单元的其 中1个单元中只存储数据信号。
8.一种对用于储存的已编码的数据信号进行重建以对一种包含有 N+2个存储单元的存储介质中的一个存储单元进行容错的方法，N是 一个正整数，又将每个存储单元分成N个存储块，由(N)(N)个数据信 号块产生出2N个奇偶校验信号块，所述方法包含：将N(N+2)个奇 偶校验和数据信号块分配在存储介质的N+2个存储单元中，以使2N 个奇偶校验信号块不是仅仅存储在N+2个存储单元中的其中两个单元 上；以及
在至少其中一个存储单元受损后，利用选择的数据和奇偶校验信 号来重建由于存储单元受损而丢失的数据信号。
9.如权利要求8所述的方法，其特征在于所述的至少其中一个存 储单元包括两个存储单元。
10.一种对用于储存的已编码的数据信号进行更新以对一种包含 有N+2个存储单元的存储介质中的一个存储单元进行容错的方法，N 是一个正整数，又将每个存储单元分成N个存储块，由(N)(N)个数据 信号块产生出2N个奇偶校验信号块，所述方法包含：将N(N+2)个 奇偶校验和数据信号块分配在存储介质的N+2个存储单元中，以使2N 个奇偶校验信号块不是仅仅存储在N+2个存储单元中的其中两个单元 上，
读取要被更新的数据信号以及任何与之相关的奇偶校验信号；
处理要被更新的数据信号，任何与之相关的奇偶校验信号，以及 正在更新要被更新以产生已更新的奇偶校验信号的数据信号；以及
写入更新要被更新的数据信号和已经更新的奇偶校验数据信号， 以取代要被更新的数据信号和任何与之相关的奇偶校验信号。
11.如权利要求10所述的方法，其特征在于所述的任何相关的奇 偶校验信号包含一个水平奇偶校验信号和一个相应更新的数据信号的 对角奇偶校验信号；以及
该更新的奇偶校验信号包括更新的水平奇偶校验信号和更新的对 角奇偶校验信号。

技术领域\n本发明涉及数据信号的编码，更具体地说涉及用于存储的数据信 号的编码。\n背景技术\n数据信号在诸如硬盘、磁盘或磁盘阵列等辅助存储介质中的存储 与个人计算机(PC)或其他计算机的运算是相关的，这一点是普遍公 知的。可以用冗余磁盘阵列来建立高可用性、高稳定性的磁盘子系统。 数据信号一般是由一些磁盘经异或运算而得且将其保存在冗余磁盘 上，这样当某个磁盘受损时，就可利用在现存磁盘和写到备份磁盘上 的数据将受损磁盘上的数据信号重建出来。但是，如果在重建完成之 前又有一个磁盘受损，就可能造成数据信号的丢失。令人感到遗憾的 是：在一个以上的磁盘受损的情况下，利用传统的磁盘阵列就无法防 止数据丢失了。因此，人们就希望获得一种即使在多个磁盘损坏的情 况下仍不会丢失数据的技术，同时，这项技术应具有优良的性能。\n发明内容\n根据本发明的一个方面，一种对用于存储的数据信号进行编码以 对一种存储介质中的一个存储单元进行容错的方法包括：\n对于N+2个存储单元，N是一个正整数，又将每个存储单元分成 N个存储块，由(N)(N)个数据信号块产生出2N个奇偶校验信号块；以 及\n将N(N+2)个奇偶校验和数据信号块分配在存储介质的N+2个 存储单元中，以使2N个奇偶校验信号块不是仅仅存储在N+2个存储 单元中的其中两个单元上。\n根据本发明的另一个方面，一种对用于储存的已编码的数据信号 进行重建以对一种包含有N+2个存储单元的存储介质中的一个存储单 元进行容错的方法，N是一个正整数，又将每个存储单元分成N个存储 块，由(N)(N)个数据信号块产生出2N个奇偶校验信号块，所述方法包 含：将N(N+2)个奇偶校验和数据信号块分配在存储介质的N+2个 存储单元中，以使2N个奇偶校验信号块不是仅仅存储在N+2个存储 单元中的其中两个单元上；以及\n在至少其中一个存储单元受损后，利用选择的数据和奇偶校验信 号来重建由于存储单元受损而丢失的数据信号。\n根据本发明的再一个方面，一种对用于储存的已编码的数据信号 进行更新以对一种包含有N+2个存储单元的存储介质中的一个存储单 元进行容错的方法，N是一个正整数，又将每个存储单元分成N个存储 块，由(N)(N)个数据信号块产生出2N个奇偶校验信号块，所述方法包 含：将N(N+2)个奇偶校验和数据信号块分配在存储介质的N+2个 存储单元中，以使2N个奇偶校验信号块不是仅仅存储在N+2个存储 单元中的其中两个单元上，\n读取要被更新的数据信号以及任何与之相关的奇偶校验信号；\n处理要被更新的数据信号，任何与之相关的奇偶校验信号，以及 正在更新要被更新以产生已更新的奇偶校验信号的数据信号；以及\n写入更新要被更新的数据信号和已经更新的奇偶校验数据信号， 以取代要被更新的数据信号和任何与之相关的奇偶校验信号。\n简单地说，按照本发明中的一个实施例，用于编码存储的数据信 号以对存储介质中的存储单元进行容错的方法包含以下内容：有N+2 个存储单元，N是一个正整数，又将每个存储单元分成N个存储块，则 由(N)(N)块数据信号会产生出2N个奇偶校验信号块。将N(N+2)个 奇偶校验信号块和数据信号块分配在存储介质的N+2个存储单元中， 这样就可使2N个奇偶校验信号块不是仅仅存储在N+2个存储单元中 的其中两个单元中。\n简单地说，按照本发明中的另一个实施例，一存储介质包含：N+ 2个存储二进制数字信号的存储单元，N是一个正整数，又将每个存储 单元分成N个存储块，在N+2个存储单元上存储了2N个奇偶校验信 号块和(N)(N)个数据信号块，其中2N个奇偶校验信号块是以(N)(N) 个数据信号为基础的。将2N个奇偶校验信号块分配存储在N+2个存 储单元中，这样就可使2N个奇偶校验信号块不是仅仅存储在N+2个 存储单元中的其中两个单元中。\n附图说明\n尽管在说明书的结论部分，指出了本发明的发明主题和清晰的权 利要求，仍旧相信当结合下述附图阅读时参照其详细说明将帮助大家 更好的理解本发明所述主题内容的操作方法和结构，目的，特征，和 优点。\n图1说明了按照本发明中所述的一种用于存储的数据信号的编码 方法的应用；\n图2说明了现有技术中用于存储的数据信号的编码方法的应用；\n图3是一个用于说明按照本发明的一种对已经编码的用于存储的 数据信号进行重建的方法的一个实施例中的一部分内容的流程图；\n图4说明了按照图1所示应用更新用于存储的已经编码的数据信 号的处理的一个实施例。\n具体实施方式\n为了全面的理解本发明，在以下的内容中阐述了许多个实施例。 但是不具备实施例中所述的各个具体细节也可以实施本发明，这对于 本领域技术人员来说是可以理解的。为了不使本发明变得模糊，在他 处对公知的方法、步骤、组成和线路进行了详细地描述。\n图2是用于说明采用现有技术来对要存储的数据信号进行编码的 方法的应用的一个简略示图。这个方案称为“EVENODD”方法，是在载 于1995年2月出版的第44卷第2期的IEEE计算机报上的第192-202 页的题为“EVENODD：An efficient scheme for tolerating double disk failures in Raid architectures”文章中提出的，在图2所示 的这一具体实施例中，使用了很多的冗余磁盘来存储以二进制数字信 号形式存在的奇偶校验或冗余信息。也可参见于1996年11月授予 Blaum，Brady，Bruck，Menon的题为“Methods and means for encoding and rebuilding data contents up to two unavailable DASDSs in a DASD array using simple non-recursive diagonal and row parity”的第5,579,475号美国专利。还可参见下述书籍：Paul Massiglia，The RAID book，RAID Advisory Board，1997(在这本书的 第6章描述了RAID Level 6)。方便地话，用于存储数据信号的磁盘 数N应设定为一个质数。但是，这并不会对上述方案造成任何限制， 这是由于通过假定在某些磁盘上没有容纳任何信息，即在某些磁盘上 所存储的所有二进制数字信号或字节都是零，这样就可以处理存储数 据信号的任意磁盘数。因此，当数据磁盘数不是质数时，例如就可以 对N值进行选择以使其为大于数据磁盘数的最近质数。\n如图2所示，以5个数据磁盘为例来说明上述方案的实施过程。 在标有“冗余磁盘”的磁盘中存储了奇偶校验数据信息，上述磁盘标 志成下数据块：\nD(0，5)，D(1，5)，D(2，5)，D(3，5)，D(0，6)，D(1，6)，D(2，6)，和 D(3，6)。在这一实施例中，如图2所示磁盘被分成了数据信号块或奇 偶校验信号块。奇偶校验信号信息可按照下述等式进行计算：\nD(0，5)＝D(0，0)D(0，1)D(0，2)D(0，3)D(0，4)\nD(1，5)＝D(1，0)D(1，1)D(1，2)D(1，3)D(1，4)\nD(2，5)＝D(2，0)D(2，1)D(2，2)D(2，3)D(2，4)\nD(3，5)＝D(3，0)D(3，1)D(3，2)D(3，3)D(3，4)\nD(0，6)＝SD(0，0)D(3，2)D(2，3)D(1，4)\nD(1，6)＝SD(1，0)D(0，1)D(3，3)D(2，4)\nD(2，6)＝SD(2，0)D(1，1)D(0，2)D(3，4)\nD(3，6)＝SD(3，0)D(2，1)D(1，2)D(0，3)\nS＝D(3，1)D(2，2)D(1，3)D(0，4)\n采用这种方法，对于一个带有五个磁盘数据容量的磁盘阵列上的 奇偶校验信号信息进行编码的话，就需要执行35次的异或运算 (“XOR”)。在这个例子中，如果假定在数据存储块 D(0，4)，D(1，4)，D(2，4)，D(3，4)中存储的均为零，则如果仅有四个数 据磁盘的话，要对数据信号进行编码就需要执行27次的异或运算 (XOR)。\n应用已编码的冗余信号信息的一个方面是在更新数据块时执行写 操作方法的效率。例如采用这种技术时，只要写的数据块不是图2中 所示的主对角线上的部分时，每次写该技术应用都需要执行附加的两 个写操作(“写”)。如果要写的数据块是主对角线上的部分，则需 要使用附加的5个写操作。总之，需要使用N次另外的写操作。因此， 如果都要以相同的概率访问数据块，则对于一个含有5个数据磁盘的 阵列来说，进行更新所需的附加写操作的预期值为2.6。如果有四个 数据磁盘，则每次更新所要进行的附加写操作的预期值为2.56。总 之，每次更新所进行的附加写操作的预期值为3-(1/N)，因此 对大值N越接近3。\n如果两个冗余磁盘都受到损坏，则采用上述的编码步骤可以由数 据磁盘或数据存储单元中的存储信息计算出所丢失的奇偶校验信号信 息。因此，重建的复杂性与编码的复杂性是相等的。然而如果两个数 据磁盘受到损坏，则需要执行44次异或(XOR)运算来重建所丢 失的数据。例如，假设存储单元或磁盘0和2受到了损坏，则所丢失 的数据存储块D(0，0)，D(1，0)，D(2，0)，D(3，0)，D(0，2)， D(1，2)，D(2，2)，和D(3，2)可采用下述的运算顺序获得：\nS＝D(0，5)D(1，5)D(2，5)D(3，5)D(0，6)D(1，6) D(2，6)D(3，6)\nS(0)0＝D(0，1)D(0，3)D(0，4)\nS(0)1＝D(1，1)D(1，3)D(1，4)\nS(0)2＝D(2，1)D(2，3)D(2，4)\nS(0)3＝D(3，1)D(3，3)D(3，4)\nS(0)4＝D(4，1)D(4，3)D(4，4)\nS(1)0＝SD(0，6)D(4，1)D(2，3)D(1，4)\nS(1)1＝SD(1，6)D(0，1)D(3，3)D(2，4)\nS(1)2＝SD(2，6)D(1，1)D(4，3)D(3，4)\nS(1)3＝SD(3，3)D(2，1)D(0，3)D(4，4)\nS(1)4＝SD(4，6)D(3，1)D(1，3)D(0，4)\nD(2，2)＝S(1)4\nD(2，0)＝S(0)2D(2，2)\nD(0，2)＝S(1)2D(2，0)\nD(0，0)＝S(0)0D(0，2)\nD(3，2)＝S(1)0D(0，0)\nD(3，0)＝S(0)3D(3，2)\nD(1，2)＝S(1)3D(3，0)\nD(1，0)＝S(0)1D(1，2)\n因此，执行44次的XOR运算就可重建出包含在两个受损坏的 存储单元中的数据信号。同样，指示如果存储单元的个数是4，则执 行34次XOR运算就可重建出所丢失的数据存储块。假设阵列中的 所有数据存储单元受到损坏的概率相同，则在四个存储单元阵列中有 两个单元受到损坏的情况下重建数据所要执行的XOR运算的预期次 数为大约29.8。\n图1是说明了按照本发明中所述存储数据编码方法的一个实施例 的应用情况示意图。在这个例子中，存储阵列包含6个存储单元，其 中既有数据信号单元也有奇偶校验信号存储单元。因此，该存储阵列 具有匹配等效储存能力的数据存储单元数为N。在这个例子中，N＝4。 当然，本发明并不局限于这一数据存储容量也不局限于这一特定实施 例。存储总数据量是N个存储单元的容量，在这一实施例中N为4， N个存储单元中的每一个单元又被分成N个数据存储块。另外，从 (N)(N)数据信号块中产生了2N个奇偶校验信号块，在下面的 内容中将对此进行更为详细的描述。而且，在这一特定实施例中，N(N+2) 个奇偶校验和数据信号被分配在存储介质的N+2个存储单元中，这 样便可使2N个奇偶校验信号块不是仅仅存储在N+2个存储单元中 的其中两个单元中，在这一点上与EVENODD方案是不相同的。\n在这一实施例中，奇偶校验信号既有水平奇偶校验信号也有对角 奇偶校验信号。如图1所示，在这一实施例中，对角奇偶校验信号只 存储在N+2个存储单元中的一个单元中。同样，在这一实施例中， 不同于EVENODD方案，水平奇偶校验信号被分配存储在N+2 个存储单元中的N个单元中。而且，如图1所示在这一实施例中，N +2个存储单元中的一个单元只存储数据信号。\n在这一实施例中，假设N+1是一个质数。与EVENODD方 案那样，只要通过假设存储单元中没有存储数据信号，因此在那些单 元中的所有数据均为零，该技术就可处理任意的存储单元数。为了简 单化，如图1所示假定每个存储单元有N个数据块，在这一实施例中， N即为4。当然，在这方面本发明并不局限于这一范围。例如，通过 分开进行处理每个N个数据块组就可以处理任意存储单元容量。在这 一方案中，一个数据块也可以包含有任意位数。在这一例子中，奇偶 校验信号信息D(0，3)，D(1，2)，D(2，1)，D(3，0)，D(0，5)， D(1，5)，D(2，5)，和D(3，5)可按照下列等式计算出：\n水平奇偶校验：\nD(0，3)＝D(0，0)D(0，1)D(0，2)D(0，4)\nD(1，2)＝D(1，0)D(1，1)D(1，3)D(1，4)\nD(2，1)＝D(2，0)D(2，2)D(2，3)D(2，4)\nD(3，0)＝D(3，1)D(3，2)D(3，3)D(3，4)\n对角奇偶校验：\nD(0，5)＝D(3，4)D(2，0)D(1，1)D(0，2)\nD(1，5)＝D(3，3)D(2，4)D(1，0)D(0，1)\nD(2，5)＝D(3，2)D(2，3)D(1，4)D(0，0)\nD(3，5)＝D(3，1)D(2，2)D(1，3)D(0，4)\n如这个例子所示，对于一个存储容量相当于由四个存储单元所组 成的存储阵列中的奇偶校验信号信息进编码要执行24次XOR运 算。而在前所述的EVENODD方案中，要对相等数据容量进行编 码则需要执行27次XOR运算。因此，由这一实施例便可看出：按 照本发明中所述的编码方法进行编码储存的数据信号的复杂性小于E VENODD方案中的编码复杂性。总之，需执行2N(N-1)次 XOR运算。\n在数据块更新方面，所建议的技术仅采用执行两次额外的写操 作，与数据块的位置无关，这一点将在下面的内容作详细的描述。因 此，本方案的更新性能也优于EVENODD方案中的更新性能。\n按照本发明中所述的编码存储数据信号方法的这一实施例在双盘 或受损存储单元的恢复方面也提供更好的性能。设F1和F2为受到 损坏的存储单元。如果F1大于或等于零且小于或等于N，F2等于 N+1，则使用水平奇偶校验便可重建F1。在F1重建之后，由于 可以获得这些受损的所有数据块，则使用编码步骤便可直接重建出存 储在F2中的对角奇偶信号信息了。因此，在这种情况下，这一实施 例执行24次XOR运算就可重建存储在两个受损的存储单元中的信 号信息了。但是，如果F1小于F2且F1大于或等于零，F2小于 或等于N，则两个存储单元含有数据信号信息或既有数据也有奇偶校 验信号信息。在这一例子中，即使在上述情况下，按照本发明所述的 方法也仅需执行24次XOR运算便可恢复丢失的数据和/或奇偶校 验信号信息。\n通过下面的几个例子可以说明本发明中所提出的编码技术只需执 行24次XOR运算便可重建所丢失的数据，而按照EVENODD 方案则需执行34次运算。在有两个相独立的受损存储单元的实施例 中，本发明中的所述方案总是正好执行24次XOR运算以从保持完 好的存储单元中重建数据信号。而在EVENODD方案中则需执行 29.8次XOR运算才能恢复受损的两个存储单元。因此，本发明中 编码存储的数据信号方法的这一实施例中的重建复杂性小于EVEN ODD方案中的重建复杂性。\n例如，假设存储单元1和4受到损坏，则在这一实施例中所对应 的丢失块为D(0，1)，D(1，1)，D(2，1)，D(3，1)，D(0，4)，D(1，4)，D(2，4) 和D(3，4)。采用这一本发明中编码存储的数据信号方法的具体实施 例，一个对角奇偶校验组不包含存储单元1中的任何数据块，另一对 角校验组不包含存储单元4中的任何数据块。因此，在这一实施中， 两者都可以作为起始点。在这一实施例中，我们先从不包含任何存储 单元1中的数据块的那个对角奇偶校验组开始，即D(3，2)，D(2，3)， D(1，4)，D(0，0)。那么，可按以下等式来建立D(1，4)：\nD(1，4)＝D(3，2)D(2，3)D(0，0)D(2，5)\n在这一例子中，使用水平奇偶校验组D(1，0)，D(1，2)，D(1，3)， D(1，4)，按如下等式来建立D(1，1)：\nD(1，1)＝D(1，0)D(1，2)D(1，3)D(1，4)\n使用含有D(1，1)的对角奇偶校验组按如下等式来获得D(3，4)：\nD(3，4)＝D(2，0)D(1，1)D(0，2)D(0，5)\n使用水平奇偶校验组D(3，1)，D(3，2)，D(3，3)，D(3，4)，按如 下等式来建立D(3，1)：\nD(3，1)＝D(3，0)D(3，2)D(3，3)D(3，4)\n然后，使用合有D(3，1)的对角奇偶校验组按如下等式来获得 D(0，4)：\nD(0，4)＝D(3，1)D(2，2)D(1，3)D(3，5)\n然后，使用下述的水平组来建立D(0，1)：\nD(0，1)＝D(0，0)D(0，2)D(0，3)D(0，4)\n然后，使用含有D(0，1)的对角奇偶校验组来获得D(2，4)：\nD(2，4)＝D(3，3)D(1，0)D(0，1)D(1，5)\n然后，使用下述的水平组来建立D(2，1)：\nD(2，1)＝D(2，0)D(2，2)D(2，3)D(2，4)\n在这一例子中，一个受损存储单元4中只有数据块。而用下一个 例子来说明两个受损的存储单元只包含数据和奇偶校验信号。\n代之以，假设存储单元0和2受到了损坏。在这个例子中，也就 是意味着块D(0，0)，D(1，0)，D(2，0)，D(3，0)，D(0，2)，D(1，2)，D(2，2) 和D(3，2)丢失了。在这一例子中，对角奇偶校验组D(3，1)， D(2，2)，D(1，3)和D(0，4)没有包含存储单元0的数据块。因此，按如 下等式来建立D(2，2)：\nD(2，2)＝D(3，1)D(3，5)D(1，3)D(0，4)\n利用如下的水平奇偶校验组来建立D(2，0)：\nD(2，0)＝D(2，1)D(2，2)D(2，3)D(2，4)\n利用含有D(2，0)的对角奇偶校验组来获得D(0，2)：\nD(0，2)＝D(3，4)D(2，0)D(1，1)D(0，5)\n利用如下的水平奇偶校验组来建立D(0，0)：\nD(0，0)＝D(0，3)D(0，1)D(0，2)D(0，4)\n利用含有D(0，0)的对角奇偶校验组来获得D(3，2)：\nD(3，2)＝D(2，5)D(2，3)D(1，4)D(0，0)\n利用如下的水平奇偶校验组来建立D(3，0)：\nD(3，0)＝D(3，1)D(3，2)D(3，3)D(3，4)\n在这个例子中，D(3，0)是一个水平奇偶校块。因此，为了从一个 对角奇偶校验组中获得另一个块，利用了不含存储单元2的数据块 D(3，3)，D(4，4)，D(1，0)，D(0，1)按下式来建立D(1，0)：\nD(1，0)＝D(3，3)D(2，4)D(1，5)D(0，1)\n在这一例子中，通过利用如下的水平奇偶校验组来获得D(1，2)的 重建工作就完成了：D(1，2)＝D(1，0)D(1，1)D(1，3)D(1，4)\n总之，对于这一具体实施例，当两个存储单元同时受损时，则重 建过程需要执行2N(N-1)次XOR运算，这与在这一实施例中对数据 信号进行编码所需执行的XOR运算次数是相等的。因此，由前述内容 可以看出：当两个存储单元受损时，本发明中编码存储的数据信号方 法的具体实施例在编码、更新以及在重建数据信号方面都具有比EV ENODD方案更好的性能。\n图1阐明了一个具有四个数据存储单元的具体实施例，下面将描 述另一个实施例，其中数据存储单元的个数可以是不确定的。考虑一 个具有N+2个存储单元的存储阵列。在这个具体实施例中，与EVENODD 方案相同使用两个有存储容量价值的存储单元来存储奇偶校验信号信 息。为了使这个实施例简化，如果N-1是一个质数，则假设N+2个 存储单元每个单元都有N个存储块；在其他情况下，则假设有M个存 储块，其中M+1为大于N-1的最小质数。当然，在另外的实施例中， 通过考虑每个与一个存储单元单独相关的N个(如果N+1不是质数则 为M个)存储块，可以处理具有不同容量的存储单元。如果一个存储 单元中的一个存储块含有奇偶校验信号信息，则在这里将其称为奇偶 校验块。同样，如果一个存储单元中的一个存储块含有数据信号信息， 则将其称为数据块。\n考虑一个N(N+2)个数据块阵列以使D(i，j)(其中i大于或 等于零且小于或等于N-1，j大于或等于零且小于或等于N+1)为第j 个存储单元中的第i个数据块。数据阵列中有(N)(N)个数据信号块和 2N个奇偶校验信号块。问题是如何获得奇偶校验信号并将其放在存储 阵列中的2N个奇偶校验块中，以使得任意两个存储单元都可以由阵列 中的其他N个存储单元的内容建立起来。在这一实施例中，按照以下 等式只需使用XOR运算便可生成奇偶校验信号信息且可将其放在存储 阵列中：\nD(i，N-1-i)＝D(i，j)，其中j＝0至N，j≠N-1-i，0≤i≤N-1(1)\nD(i，N+1)＝D(N-1-j，(N-i+j)mod(N+1))，其中j＝0至N-1，0≤i ≤N-1(2)\n等式(1)定义出了水平校验信号的产生和放置。存储单元块D(0， N-1)，D(1，N-2)，...D(N-1，0)中包含了水平奇偶校验信号 信息。等式(2)定义出了奇偶校验块中产生的对角奇偶校验信号。按 照等式(2)，奇偶校验块D(0，N+1)，D(1，N+1)，...D(N-1， N+1)中包含了对角奇偶校验信号信息。所前所示，在这一实施例中， 对角奇偶校验信号信息只存储在第N+1个存储单元中。\n如前所述，这一优选实施例的一次更新操作中每次写需执行两次 附加的写运算，这与要写的块无关。假设要写对块D(i，j)进行写操 作，为了完成这一写操作，就要对奇偶校验块D(i，N-1-i)(水平奇 偶校验)和D((2N-1-i-j)mod(N+1)，N+1)(对角奇偶校验)执行附 加的写运算。利用上述的等式(1)和(2)就可获得要写的信号值。\n图4是一说明这个优选实施例所执行的一次更新过程的方框图。 如图所示，由存储单元发出了一个写请求510。在这一实施例中，该请 求继发到存储阵列管理软件520，虽然在这一方面本发明并不局限于 此。在这个实施例中，更新数据信号也涉及到更新相关的奇偶校验信 号。因此，如图所示分别执行了3个读操作。在这一实施例中，设定 与一次写操作相比执行一次读操作的时间相对小一些，这归因于超高 速缓冲存储器的存在；但是，在这一方面，本发明也并不局限于此。 如图所示，除了读取要被更新的数据信号外，也读取了相关的水平和 对角奇偶校验信号。在560和580，获得了一个新的或更新过的水平和 对角奇偶校验信号。在这一优选实施例中，这些新的信号是通过利用 更新前的水平和对角奇偶校验信号，要被更新的数据信号以及用于替 代被更新数据信号的数据信号来获得的。在570、590和610，对更新 后的数据和奇偶校验信号执行了写操作。当然，本发明并不限止是以 并行，顺序或其他的方式来执行上述这些操作，采取什么方式将取决 于许多与如何实施本发明无关的其他因素。\n在这一优选实施例中，与编码过程相同只需通过XOR运算就可完 成解码过程以使受损的一个或两个存储单元得到恢复。在这一实施例 中，对这两种损坏方式是分别进行处理的。假设F1是损坏的存储单元。 如果F1大于或等于零且小于或等于N，则利用水平奇偶校验信号编码 便可恢复所丢失的数据信号(当F1等于N时)或数据和奇偶校验信号 (当F1小于或等于N-1且大于或等于零时)。以F1替代上述等式(1) 中的N-1-i得到：\nD(i，F1)＝D(i，j)，其中j＝0至N，j≠F1，0≤i≤N-1       (3)\n如果F1等于N+1(即：对角奇偶校验存储单元已损坏)，则按照 等式(2)处理便可将其重建出来。\n另外如果有两个存储单元被损坏。设F1和F2就是这两个受损的 存储单元。一种情况下，假设F1大于或等于零且小于或等于N，而F2 等于N+1。则在这种情况下，按照上述的等式(3)便可恢复F1。同 样，利用等式(2)和重建的存储单元F1便可恢复F2。\n在另一种情况下，F1可能小于F2且F1可能大于或等于零。同样， F2也可能小于或等于N。在这种情况下，在两个受损的存储单元中都 存储着数据或数据和奇偶校验信号信息。同样，由于上述情况，F1大 于或等于零且小于或等于N-1。因此，按照上述的等式(2)，存储单 元F1含有(N-1)个数据块和1个奇偶校验块。在这种情况下，则需 采用如图3中所示的一种较为复杂的方法。\n当然，可以理解到本发明并不局限于如图3中所示的方法。可以 采用其他方式且采用其他方式也会得到满意的结果。对于这一实施 例，如果F1小于或等于N-1且F2等于N，则在如图3所示的第一环 中，利用对角奇偶校验便可获得D(F1，N)，然后使用水平奇偶校验 和D(F1，N)可获得D(F1，F1)。然后，利用包含D(F1，F1)的 对角奇偶校验组使t得到更新以获得D(t，N)，这一过程进行循环直到 t＝N-1-F1为止。由于在这一实施例中存储单元N只含有数据块且设定 N+1为质数，则通过以“Z字”模式“来回穿过”数据块的方法便可恢 复丢失的块。但是，如果F2不等于N，那么存储单元中就既包含数据 块也包含奇偶校验块，这样我们就不能采用前述的方法来恢复D(N-1 -F1，N)块了。对此为了完成重建，当t＝N-1-F1时，如图3中的第 二环所示使t复位。通过上文中结合图2所详细描述的前两个重建例 子也阐明了这一优选的重建术。\n尤其是在发生双重损坏的情况下，上述实施例的一个缺点是：如 果丢失的数据被访问，则只要有访问请求数据就会被再次重建。在另 一实施例中，存储阵列可以包含备份的存储空间。因此，当数据被重 建时就可将其存储在备份空间中，这样在以后访问丢失数据时就不额 外地重建了，至少对于已经重建且保存过的数据信号可以做到这样。 同样，也可采用其他分配备份存储空间的其他方法，本发明并不局限 于一种优选方式。例如，为此可以在该阵列中提供两个备份存储单元。 另外，也可以将两块备份存储空间分配给各个存储单元，以使分配备 份存储空间跨接不同的存储单元。而且也可以对更少或更多的备份空 间进行分配。根据具体情况可以采用各种不同的方法。\n尽管在这里已对本发明的某些特征进行了描述，但对于本领域的 技术人员来说，还可以由此进行许多种变形，替代，改变和等效替换。 因此，应理解为希望通过所附的各项权利要求可以覆盖具有本发明实 质内容的各种变形和改变。\n背景