用於存儲數據信號的編碼方式的製作方法

2023-05-31 11:05:26 1

專利名稱：用於存儲數據信號的編碼方式的製作方法
技術領域：
本發明涉及數據信號的編碼，更具體地說涉及用於存儲的數據信號的編碼。
背景技術：
數據信號在諸如硬碟、磁碟或磁碟陣列等輔助存儲介質中的存儲與個人計算機(PC)或其他計算機的運算是相關的，這一點是普遍公知的。可以用冗餘磁碟陣列來建立高可用性、高穩定性的磁碟子系統。數據信號一般是由一些磁碟經異或運算而得且將其保存在冗餘磁碟上，這樣當某個磁碟受損時，就可利用在現存磁碟和寫到備份磁碟上的數據將受損磁碟上的數據信號重建出來。但是，如果在重建完成之前又有一個磁碟受損，就可能造成數據信號的丟失。令人感到遺憾的是在一個以上的磁碟受損的情況下，利用傳統的磁碟陣列就無法防止數據丟失了。因此，人們就希望獲得一種即使在多個磁碟損壞的情況下仍不會丟失數據的技術，同時，這項技術應具有優良的性能。
概述簡單地說，按照本發明中的一個實施例，用於編碼存儲的數據信號以對存儲介質中的存儲單元進行容錯的方法包含以下內容有N+2個存儲單元，N是一個正整數，又將每個存儲單元分成N個存儲塊，則由(N)(N)塊數據信號會產生出2N個奇偶校驗信號塊。將N(N+2)個奇偶校驗信號塊和數據信號塊分配在存儲介質的N+2個存儲單元中，這樣就可使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元中。
簡單地說，按照本發明中的另一個實施例，一存儲介質包含N+2個存儲二進位數位訊號的存儲單元，N是一個正整數，又將每個存儲單元分成N個存儲塊，在N+2個存儲單元上存儲了2N個奇偶校驗信號塊和(N)(N)個數據信號塊，其中2N個奇偶校驗信號塊是以(N)(N)個數據信號為基礎的。將2N個奇偶校驗信號塊分配存儲在N+2個存儲單元中，這樣就可使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元中。
附圖的簡要說明儘管在說明書的結論部分，指出了本發明的發明主題和清晰的權利要求，仍舊相信當結合下述附圖閱讀時參照其詳細說明將幫助大家更好的理解本發明所述主題內容的操作方法和結構，目的，特徵，和優點。


圖1說明了按照本發明中所述的一種用於存儲的數據信號的編碼方法的應用；圖2說明了現有技術中用於存儲的數據信號的編碼方法的應用；圖3是一個用於說明按照本發明的一種對已經編碼的用於存儲的數據信號進行重建的方法的一個實施例中的一部分內容的流程圖；圖4說明了按照圖1所示應用更新用於存儲的已經編碼的數據信號的處理的一個實施例。
發明的詳細描述為了全面的理解本發明，在以下的內容中闡述了許多個實施例。但是不具備實施例中所述的各個具體細節也可以實施本發明，這對於本領域技術人員來說是可以理解的。為了不使本發明變得模糊，在他處對公知的方法、步驟、組成和線路進行了詳細地描述。
圖2是用於說明採用現有技術來對要存儲的數據信號進行編碼的方法的應用的一個簡略示圖。這個方案稱為「EVENODD」方法，是在載於1995年2月出版的第44卷第2期的IEEE計算機報上的第192-202頁的題為「EVENODDAn efficient scheme for toleratingdouble disk failures in Raid architectures」文章中提出的，在圖2所示的這一具體實施例中，使用了很多的冗餘磁碟來存儲以二進位數位訊號形式存在的奇偶校驗或冗餘信息。也可參見於1996年11月授予Blaum，Brady，Bruck，Menon的題為「Methods and means forencoding and rebuilding data contents up to two unavailableDASDSs in a DASD array using simple non-recursive diagonal androw parity」的第5,579,475號美國專利。還可參見下述書籍PaulMassiglia，The RAID book，RAID Advisory Board，1997(在這本書的第6章描述了RAID Level 6)。方便地話，用於存儲數據信號的磁碟數N應設定為一個質數。但是，這並不會對上述方案造成任何限制，這是由於通過假定在某些磁碟上沒有容納任何信息，即在某些磁碟上所存儲的所有二進位數位訊號或字節都是零，這樣就可以處理存儲數據信號的任意磁碟數。因此，當數據磁碟數不是質數時，例如就可以對N值進行選擇以使其為大於數據磁碟數的最近質數。
如圖2所示，以5個數據磁碟為例來說明上述方案的實施過程。在標有「冗餘磁碟」的磁碟中存儲了奇偶校驗數據信息，上述磁碟標誌成下數據塊D(0，5)，D(1，5)，D(2，5)，D(3，5)，D(0，6)，D(1，6)，D(2，6)，和D(3，6)。在這一實施例中，如圖2所示磁碟被分成了數據信號塊或奇偶校驗信號塊。奇偶校驗信號信息可按照下述等式進行計算D(0，5)＝D(0，0)D(0，1)D(0，2)D(0，3)D(0，4)D(1，5)＝D(1，0)D(1，1)D(1，2)D(1，3)D(1，4)D(2，5)＝D(2，0)D(2，1)D(2，2)D(2，3)D(2，4)D(3，5)＝D(3，0)D(3，1)D(3，2)D(3，3)D(3，4)D(0，6)＝SD(0，0)D(3，2)D(2，3)D(1，4)D(1，6)＝SD(1，0)D(0，1)D(3，3)D(2，4)D(2，6)＝SD(2，0)D(1，1)D(0，2)D(3，4)D(3，6)＝SD(3，0)D(2，1)D(1，2)D(0，3)S＝D(3，1)D(2，2)D(1，3)D(0，4)採用這種方法，對於一個帶有五個磁碟數據容量的磁碟陣列上的奇偶校驗信號信息進行編碼的話，就需要執行35次的異或運算(「XOR」)。在這個例子中，如果假定在數據存儲塊D(0，4)，D(1，4)，D(2，4)，D(3，4)中存儲的均為零，則如果僅有四個數據磁碟的話，要對數據信號進行編碼就需要執行27次的異或運算(XOR)。
應用已編碼的冗餘信號信息的一個方面是在更新數據塊時執行寫操作方法的效率。例如採用這種技術時，只要寫的數據塊不是圖2中所示的主對角線上的部分時，每次寫該技術應用都需要執行附加的兩個寫操作(「寫」)。如果要寫的數據塊是主對角線上的部分，則需要使用附加的5個寫操作。總之，需要使用N次另外的寫操作。因此，如果都要以相同的概率訪問數據塊，則對於一個含有5個數據磁碟的陣列來說，進行更新所需的附加寫操作的預期值為2.6。如果有四個數據磁碟，則每次更新所要進行的附加寫操作的預期值為2.56。總之，每次更新所進行的附加寫操作的預期值為3-(1/N)，因此對大值N越接近3。
如果兩個冗餘磁碟都受到損壞，則採用上述的編碼步驟可以由數據磁碟或數據存儲單元中的存儲信息計算出所丟失的奇偶校驗信號信息。因此，重建的複雜性與編碼的複雜性是相等的。然而如果兩個數據磁碟受到損壞，則需要執行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)可採用下述的運算順序獲得S＝D(0，5)D(1，5)D(2，5)D(3，5)D(0，6)D(1，6)D(2，6)D(3，6)S(0)0＝D(0，1)D(0，3)D(0，4)S(0)1＝D(1，1)D(1，3)D(1，4)S(0)2＝D(2，1)D(2，3)D(2，4)S(0)3＝D(3，1)D(3，3)D(3，4)S(0)4＝D(4，1)D(4，3)D(4，4)S(1)0＝SD(0，6)D(4，1)D(2，3)D(1，4)S(1)1＝SD(1，6)D(0，1)D(3，3)D(2，4)S(1)2＝SD(2，6)D(1，1)D(4，3)D(3，4)S(1)3＝SD(3，3)D(2，1)D(0，3)D(4，4)S(1)4＝SD(4，6)D(3，1)D(1，3)D(0，4)D(2，2)＝S(1)4D(2，0)＝S(0)2D(2，2)D(0，2)＝S(1)2D(2，0)D(0，0)＝S(0)0D(0，2)D(3，2)＝S(1)0D(0，0)D(3，0)＝S(0)3D(3，2)D(1，2)＝S(1)3D(3，0)D(1，0)＝S(0)1D(1，2)因此，執行44次的XOR運算就可重建出包含在兩個受損壞的存儲單元中的數據信號。同樣，指示如果存儲單元的個數是4，則執行34次XOR運算就可重建出所丟失的數據存儲塊。假設陣列中的所有數據存儲單元受到損壞的概率相同，則在四個存儲單元陣列中有兩個單元受到損壞的情況下重建數據所要執行的XOR運算的預期次數為大約29.8。
圖1是說明了按照本發明中所述存儲數據編碼方法的一個實施例的應用情況示意圖。在這個例子中，存儲陣列包含6個存儲單元，其中既有數據信號單元也有奇偶校驗信號存儲單元。因此，該存儲陣列具有匹配等效儲存能力的數據存儲單元數為N。在這個例子中，N＝4。當然，本發明並不局限於這一數據存儲容量也不局限於這一特定實施例。存儲總數據量是N個存儲單元的容量，在這一實施例中N為4，N個存儲單元中的每一個單元又被分成N個數據存儲塊。另外，從(N)(N)數據信號塊中產生了2N個奇偶校驗信號塊，在下面的內容中將對此進行更為詳細的描述。而且，在這一特定實施例中，N(N+2)個奇偶校驗和數據信號被分配在存儲介質的N+2個存儲單元中，這樣便可使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元中，在這一點上與EVENODD方案是不相同的。
在這一實施例中，奇偶校驗信號既有水平奇偶校驗信號也有對角奇偶校驗信號。如圖1所示，在這一實施例中，對角奇偶校驗信號只存儲在N+2個存儲單元中的一個單元中。同樣，在這一實施例中，不同於EVENODD方案，水平奇偶校驗信號被分配存儲在N+2個存儲單元中的N個單元中。而且，如圖1所示在這一實施例中，N+2個存儲單元中的一個單元只存儲數據信號。
在這一實施例中，假設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)可按照下列等式計算出
水平奇偶校驗D(0，3)＝D(0，0)D(0，1)D(0，2)D(0，4)D(1，2)＝D(1，0)D(1，1)D(1，3)D(1，4)D(2，1)＝D(2，0)D(2，2)D(2，3)D(2，4)D(3，0)＝D(3，1)D(3，2)D(3，3)D(3，4)對角奇偶校驗D(0，5)＝D(3，4)D(2，0)D(1，1)D(0，2)D(1，5)＝D(3，3)D(2，4)D(1，0)D(0，1)D(2，5)＝D(3，2)D(2，3)D(1，4)D(0，0)D(3，5)＝D(3，1)D(2，2)D(1，3)D(0，4)如這個例子所示，對於一個存儲容量相當於由四個存儲單元所組成的存儲陣列中的奇偶校驗信號信息進編碼要執行24次XOR運算。而在前所述的EVENODD方案中，要對相等數據容量進行編碼則需要執行27次XOR運算。因此，由這一實施例便可看出按照本發明中所述的編碼方法進行編碼儲存的數據信號的複雜性小於EVENODD方案中的編碼複雜性。總之，需執行2N(N-1)次XOR運算。
在數據塊更新方面，所建議的技術僅採用執行兩次額外的寫操作，與數據塊的位置無關，這一點將在下面的內容作詳細的描述。因此，本方案的更新性能也優於EVENODD方案中的更新性能。
按照本發明中所述的編碼存儲數據信號方法的這一實施例在雙盤或受損存儲單元的恢復方面也提供更好的性能。設F1和F2為受到損壞的存儲單元。如果F1大於或等於零且小於或等於N，F2等於N+1，則使用水平奇偶校驗便可重建F1。在F1重建之後，由於可以獲得這些受損的所有數據塊，則使用編碼步驟便可直接重建出存儲在F2中的對角奇偶信號信息了。因此，在這種情況下，這一實施例執行24次XOR運算就可重建存儲在兩個受損的存儲單元中的信號信息了。但是，如果F1小於F2且F1大於或等於零，F2小於或等於N，則兩個存儲單元含有數據信號信息或既有數據也有奇偶校驗信號信息。在這一例子中，即使在上述情況下，按照本發明所述的方法也僅需執行24次XOR運算便可恢復丟失的數據和/或奇偶校驗信號信息。
通過下面的幾個例子可以說明本發明中所提出的編碼技術只需執行24次XOR運算便可重建所丟失的數據，而按照EVENODD方案則需執行34次運算。在有兩個相獨立的受損存儲單元的實施例中，本發明中的所述方案總是正好執行24次XOR運算以從保持完好的存儲單元中重建數據信號。而在EVENODD方案中則需執行29.8次XOR運算才能恢復受損的兩個存儲單元。因此，本發明中編碼存儲的數據信號方法的這一實施例中的重建複雜性小於EVENODD方案中的重建複雜性。
例如，假設存儲單元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)D(1，4)＝D(3，2)D(2，3)D(0，0)D(2，5)在這一例子中，使用水平奇偶校驗組D(1，0)，D(1，2)，D(1，3)，D(1，4)，按如下等式來建立D(1，1)D(1，1)＝D(1，0)D(1，2)D(1，3)D(1，4)使用含有D(1，1)的對角奇偶校驗組按如下等式來獲得D(3，4)D(3，4)＝D(2，0)D(1，1)D(0，2)D(0，5)使用水平奇偶校驗組D(3，1)，D(3，2)，D(3，3)，D(3，4)，按如下等式來建立D(3，1)D(3，1)＝D(3，0)D(3，2)D(3，3)D(3，4)然後，使用含有D(3，1)的對角奇偶校驗組按如下等式來獲得D(0，4)D(0，4)＝D(3，1)D(2，2)D(1，3)D(3，5)然後，使用下述的水平組來建立D(0，1)D(0，1)＝D(0，0) D(0，2)D(0，3)D(0，4)然後，使用含有D(0，1)的對角奇偶校驗組來獲得D(2，4)D(2，4)＝D(3，3)D(1，0)D(0，1)D(1，5)
然後，使用下述的水平組來建立D(2，1)D(2，1)＝D(2，0)D(2，2)D(2，3)D(2，4)在這一例子中，一個受損存儲單元4中只有數據塊。而用下一個例子來說明兩個受損的存儲單元只包含數據和奇偶校驗信號。
代之以，假設存儲單元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)D(2，2)＝D(3，1)D(3，5)D(1，3)D(0，4)利用如下的水平奇偶校驗組來建立D(2，0)D(2，0)＝D(2，1)D(2，2)D(2，3)D(2，4)利用含有D(2，0)的對角奇偶校驗組來獲得D(0，2)D(0，2)＝D(3，4)D(2，0)D(1，1)D(0，5)利用如下的水平奇偶校驗組來建立D(0，0)D(0，0)＝D(0，3)D(0，1)D(0，2)D(0，4)利用含有D(0，0)的對角奇偶校驗組來獲得D(3，2)D(3，2)＝D(2，5)D(2，3)D(1，4)D(0，0)利用如下的水平奇偶校驗組來建立D(3，0)D(3，0)＝D(3，1)D(3，2)D(3，3)D(3，4)在這個例子中，D(3，0)是一個水平奇偶校塊。因此，為了從一個對角奇偶校驗組中獲得另一個塊，利用了不含存儲單元2的數據塊D(3，3)，D(4，4)，D(1，0)，D(0，1)按下式來建立D(1，0)D(1，0)＝D(3，3)D(2，4)D(1，5)D(0，1)在這一例子中，通過利用如下的水平奇偶校驗組來獲得D(1，2)的重建工作就完成了D(1，2)＝D(1，0)D(1，1)D(1，3)D(1，4)總之，對於這一具體實施例，當兩個存儲單元同時受損時，則重建過程需要執行2N(N-1)次XOR運算，這與在這一實施例中對數據信號進行編碼所需執行的XOR運算次數是相等的。因此，由前述內容可以看出當兩個存儲單元受損時，本發明中編碼存儲的數據信號方法的具體實施例在編碼、更新以及在重建數據信號方面都具有比EVENODD方案更好的性能。
圖1闡明了一個具有四個數據存儲單元的具體實施例，下面將描述另一個實施例，其中數據存儲單元的個數可以是不確定的。考慮一個具有N+2個存儲單元的存儲陣列。在這個具體實施例中，與EVENODD方案相同使用兩個有存儲容量價值的存儲單元來存儲奇偶校驗信號信息。為了使這個實施例簡化，如果N-1是一個質數，則假設N+2個存儲單元每個單元都有N個存儲塊；在其他情況下，則假設有M個存儲塊，其中M+1為大於N-1的最小質數。當然，在另外的實施例中，通過考慮每個與一個存儲單元單獨相關的N個(如果N+1不是質數則為M個)存儲塊，可以處理具有不同容量的存儲單元。如果一個存儲單元中的一個存儲塊含有奇偶校驗信號信息，則在這裡將其稱為奇偶校驗塊。同樣，如果一個存儲單元中的一個存儲塊含有數據信號信息，則將其稱為數據塊。
考慮一個N(N+2)個數據塊陣列以使D(i，j)(其中i大於或等於零且小於或等於N-1，j大於或等於零且小於或等於N+1)為第j個存儲單元中的第i個數據塊。數據陣列中有(N)(N)個數據信號塊和2N個奇偶校驗信號塊。問題是如何獲得奇偶校驗信號並將其放在存儲陣列中的2N個奇偶校驗塊中，以使得任意兩個存儲單元都可以由陣列中的其他N個存儲單元的內容建立起來。在這一實施例中，按照以下等式只需使用XOR運算便可生成奇偶校驗信號信息且可將其放在存儲陣列中D(i，N-1-i)＝D(i，j)，其中j＝0至N，j≠N-1-i，0≤i≤N-1 (1)D(i，N+1)＝D(N-1-j，(N-i+j)mod(N+1))，其中j＝0至N，0≤i≤N-1(2)等式(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個存儲單元中。
如前所述，這一優選實施例的一次更新操作中每次寫需執行兩次附加的寫運算，這與要寫的塊無關。假設要寫對塊D(i，j)進行寫操作，為了完成這一寫操作，就要對奇偶校驗塊D(i，N-1-i)(水平奇偶校驗)和D((2N-1-i-j)mod(N+1)，N+1)(對角奇偶校驗)執行附加的寫運算。利用上述的等式(1)和(2)就可獲得要寫的信號值。
圖4是一說明這個優選實施例所執行的一次更新過程的方框圖。如圖所示，由存儲單元發出了一個寫請求510。在這一實施例中，該請求繼發到存儲陣列管理軟體520，雖然在這一方面本發明並不局限於此。在這個實施例中，更新數據信號也涉及到更新相關的奇偶校驗信號。因此，如圖所示分別執行了3個讀操作。在這一實施例中，設定與一次寫操作相比執行一次讀操作的時間相對小一些，這歸因於超高速緩衝存儲器的存在；但是，在這一方面，本發明也並不局限於此。如圖所示，除了讀取要被更新的數據信號外，也讀取了相關的水平和對角奇偶校驗信號。在560和580，獲得了一個新的或更新過的水平和對角奇偶校驗信號。在這一優選實施例中，這些新的信號是通過利用更新前的水平和對角奇偶校驗信號，要被更新的數據信號以及用於替代被更新數據信號的數據信號來獲得的。在570、590和610，對更新後的數據和奇偶校驗信號執行了寫操作。當然，本發明並不限止是以並行，順序或其他的方式來執行上述這些操作，採取什麼方式將取決於許多與如何實施本發明無關的其他因素。
在這一優選實施例中，與編碼過程相同只需通過XOR運算就可完成解碼過程以使受損的一個或兩個存儲單元得到恢復。在這一實施例中，對這兩種損壞方式是分別進行處理的。假設F1是損壞的存儲單元。如果F1大於或等於零且小於或等於N，則利用水平奇偶校驗信號編碼便可恢復所丟失的數據信號(當F1等於N時)或數據和奇偶校驗信號(當F1小於或等於N-1且大於或等於零時)。以F1替代上述等式(1)中的N-1-i得到D(i，F1)＝D(i，j)，其中j＝0至N，j≠F1，0≤i≤N-1(3)如果F1等於N+1(即對角奇偶校驗存儲單元已損壞)，則按照等式(2)處理便可將其重建出來。
另外如果有兩個存儲單元被損壞。設F1和F2就是這兩個受損的存儲單元。一種情況下，假設F1大於或等於零且小於或等於N，而F2等於N+1。則在這種情況下，按照上述的等式(3)便可恢復F1。同樣，利用等式(2)和重建的存儲單元F1便可恢復F2。
在另一種情況下，F1可能小於F2且F1可能大於或等於零。同樣，F2也可能小於或等於N。在這種情況下，在兩個受損的存儲單元中都存儲著數據或數據和奇偶校驗信號信息。同樣，由於上述情況，F1大於或等於零且小於或等於N-1。因此，按照上述的等式(2)，存儲單元F1含有(N-1)個數據塊和1個奇偶校驗塊。在這種情況下，則需採用如圖3中所示的一種較為複雜的方法。
當然，可以理解到本發明並不局限於如圖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所詳細描述的前兩個重建例子也闡明了這一優選的重建術。
尤其是在發生雙重損壞的情況下，上述實施例的一個缺點是如果丟失的數據被訪問，則只要有訪問請求數據就會被再次重建。在另一實施例中，存儲陣列可以包含備份的存儲空間。因此，當數據被重建時就可將其存儲在備份空間中，這樣在以後訪問丟失數據時就不額外地重建了，至少對於已經重建且保存過的數據信號可以做到這樣。同樣，也可採用其他分配備份存儲空間的其他方法，本發明並不局限於一種優選方式。例如，為此可以在該陣列中提供兩個備份存儲單元。另外，也可以將兩塊備份存儲空間分配給各個存儲單元，以使分配備份存儲空間跨接不同的存儲單元。而且也可以對更少或更多的備份空間進行分配。根據具體情況可以採用各種不同的方法。
儘管在這裡已對本發明的某些特徵進行了描述，但對於本領域的技術人員來說，還可以由此進行許多種變形，替代，改變和等效替換。因此，應理解為希望通過所附的各項權利要求可以覆蓋具有本發明實質內容的各種變形和改變。
權利要求
1.一種存儲介質，包含N+2個存儲二進位數位訊號的存儲單元，N是一個正整數，又將每個存儲單元分成N個存儲塊，在所述的N+2個存儲單元上存儲了2N個奇偶校驗信號塊和(N)(N)個數據信號塊，其中2N個奇偶校驗信號塊是以(N)(N)個數據信號塊為基礎的；將所述的2N個奇偶校驗信號塊分配存儲在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，0≤i≤N-1。
5.如權利要求2所述的存儲介質，其特徵在於對角奇偶校驗信號只存儲在N+2個存儲單元的其中一個單元中。
6.如權利要求5所述的存儲介質，其特徵在於水平奇偶校驗信號只被分配存儲跨接N+2個存儲單元的僅N個單元。
7.如權利要求6所述的存儲介質，其特徵在於N+2個存儲單元的其中1個單元中只存儲數據信號。
8.一種設備，包括採用N+2個存儲單元來存儲二進位數位訊號，N是一個正整數，又將所採用的每個存儲單元分成N個存儲塊，在所採用N+2個存儲單元中存儲著2N個奇偶校驗信號塊和(N)(N)個數據信號塊，其中2N個奇偶校驗信號塊是以(N)(N)個數據信號為基礎的；採用了所述的N+2個存儲單元以使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元上。
9.如權利要求8所述的設備，其特徵在於所述的2N個奇偶校驗信號塊將包含水平奇偶校驗信號和對角奇偶校驗信號。
10.如權利要求9所述的設備，其特徵在於對角奇偶校驗信號實質上將是按照下述等式的D(i，N-1-i)＝D(i，j)，其中j＝0至N，j≠N-1-i，0≤i≤N-1。
11.如權利要求9所述的設備，其特徵在於水平奇偶校驗信號實質上將是按照下述等式D(i，N+1)＝D(N-1-j，(N-i+j)mod(N+1))，其中j＝0至N，0≤i≤N-1。
12.如權利要求9所述的設備，其特徵在於對角奇偶校驗信號將只存儲在N+2個存儲單元的其中一個單元中。
13.如權利要求13所述的設備，其特徵在於水平奇偶校驗信號將只被分配存儲跨接N+2存儲單元的其中N個單元。
14.如權利要求13所述的設備，其特徵在於N+2個存儲單元的其中1個單元中只存儲數據信號。
15.一種設備，包含N+2個存儲單元適於存儲二進位數位訊號，N是一個正整數，每個存儲單元適於分成N個存儲塊，在所述的N+2個存儲單元中存儲著(N)(N)個數據和奇偶校驗信號塊，其中奇偶校驗信號塊是以數據信號塊為基礎的；採用了所述的N+2個存儲單元以使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元上；以及採用了所述的N+2個存儲單元以使所述2N個塊含有用於任一種數據信號和奇偶校驗信號的備份存儲空間。
16.如權利要求15所述的設備，其特徵在於2N個備份存儲空間塊只處在所述的N+2存儲單元的其中兩個單元中。
17.如權利要求16所述的設備，其特徵在於2N個備份存儲空間塊被分配跨接所述的N+2個存儲單元。
18.一種存儲，介質，包含N+2個存儲單元，儲存二進位數位訊號，N是一個正整數，又將每個存儲單元分成N個存儲塊，在所述的N+2存儲單元上已存儲著(N)(N)個數據和奇偶校驗信號塊，奇偶校驗信號塊是以數據信號塊為基礎的；所述的奇偶校驗信號塊被分配存儲在所述的N+2個存儲單元中以使所述的奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元中的其中兩個單元上；以及所述N+2個存儲單元中的所述2N個塊含有用於任一種數據信號和奇偶校驗信號的備份存儲空間。
19.如權利要求18所述的存儲介質，其特徵在於2N個備份存儲空間塊只處在所述的N+2存儲單元的其中兩個存儲單元中。
20.如權利要求18所述的存儲介質，其特徵在於2N個備份存儲空間塊被分配跨接所述的N+2個存儲單元。
全文摘要
按照本發明中的一個實施例，一種用於編碼存儲的數據信號以對存儲介質中的存儲單元進行容錯的方法包含以下內容有N+2個存儲單元(110，120，130，140，150，160)，N是一個正整數，又將每個存儲單元分成N個存儲塊(D0，0...D3，0；D0，1...D3，1；D0，2...D3，2；D0，3...D3，3；D0，4...D3，4；D0，5...D3，5)，則由(N)(N)塊數據信號會產生出2N個奇偶校驗信號塊。將2N個奇偶校驗信號塊分配存儲在N+2個存儲單元中，以使2N個奇偶校驗信號塊不是僅僅存儲在N+2個存儲單元的其中兩個單元中。
文檔編號G06F11/10GK1574024SQ0315306
公開日2005年2月2日 申請日期1999年4月27日 優先權日1998年5月13日
發明者S·J·W·埃迪裡索裡雅 申請人:英特爾公司