通過綜合的錯誤校正和檢測對存儲設備的數據進行恢復的方法和系統的製作方法
2023-07-09 16:03:26
專利名稱：通過綜合的錯誤校正和檢測對存儲設備的數據進行恢復的方法和系統的製作方法
技術領域：
本發明涉及數據處理技術，更具體地說，涉及一種通過綜合的錯誤校正和檢測對存儲設備的數據進行恢復的方法和系統。
背景技術：
對存儲於存儲設備的數據的進行錯誤檢測和錯誤校正的基礎，是使用數據的冗餘信息。冗餘信息(即奇偶校驗或冗餘符號)被特殊硬體和/或軟體用來進行檢測和校正錯誤，以恢復存儲設備的介質中已丟失的或被破壞的數據。存儲於諸如磁碟驅動器等存儲設備中的數據，通常使用兩類代碼編碼錯誤校正碼(Error Correction Code，ECC)和錯誤檢測碼(Error Detection Code，EDC)。當從存儲設備中讀取數據時，錯誤校正碼用於校正數據錯誤，而錯誤檢測碼則用於檢測數據錯誤。不幸的是，在許多情況下，該錯誤校正碼和錯誤檢測碼使用的是在硬體或固件(firmware)中執行的算法，其不能從存儲設備中恢復數據。
當對存儲於磁碟驅動器中的數據使用錯誤校正碼和錯誤檢測碼時，在一個數據扇區中可被校正的錯誤(即符號錯誤)的數量限於一個特定的最大值。不幸的是，當這些錯誤的數量超過該最大值時，該扇區的相關數據不可讀。而結果是，關鍵數據可能再不能從磁碟驅動器恢復。
此外，通過比較常規的和傳統的方法與本發明(將結合附圖在本申請的後續部分描述)，本技術領域的人員將清楚常規的和傳統的方法局限和缺點。
發明內容
本發明提供一種更有效地讀取存儲於存儲設備的介質中的數據的方法和系統，它使用一個三級解碼過程來校正和檢測錯誤。
一方面，本發明提供一種對存儲於存儲設備中的數據進行編碼的方法，其中包括生成第一多項式，其根包括伽羅瓦域中一個原始元素的一次或多次冪；生成第二多項式，其根包括所述伽羅瓦域中一個原始元素的一次或多次冪；生成所述第一多項式與第二多項式的乘積。
另一方面，本發明還提供一種對存儲於存儲設備中的數據進行解碼的方法，其中包括從所述存儲設備讀取所述編碼代碼字；執行第一次除法算法，用所述編碼代碼字除以所述第一多項式；確定所述第一次除法算法中是否有第一餘數；用所述第一餘數來對所述編碼代碼字進行第一次校正；執行第二次除法算法，用所述編碼代碼字除以所述第二多項式；確定所述第二次除法算法中是否有第二餘數；如果所述第二次除法算法中有第二餘數，則執行第三次除法算法，用所述編碼代碼字除以所述第一多項式與第二多項式的乘積；確定所述第三次除法算法中是否有第三餘數；用所述第三餘數來對所述編碼代碼字進行第二次校正。
本發明還提供一種對存儲於存儲設備中的數據進行錯誤校正和檢測的方法，其中包括生成第一多項式，其根包括伽羅瓦域中一個原始元素的一個或多個連續次冪；生成第二多項式，其根包括所述伽羅瓦域中一個原始元素的一個或多個連續次冪；生成所述第一多項式與第二多項式的乘積。然後，執行第一次除法算法，用一個第三多項式除以所述乘積以生成一個第一餘數，用所述第一餘數來生成一個編碼代碼字，所述第三多項式代表數據的一個區，所述數據扇區包括多個符號。然後，將所述編碼代碼字寫到所述存儲設備的一個介質中。本方法中，還包括從所述存儲設備讀取所述編碼代碼字；執行第二次除法算法，用所述編碼代碼字除以所述第一多項式；確定所述第二次除法算法中是否有一個第二餘數；用所述第二餘數來對所述編碼代碼字進行校正；執行第三次除法算法，用所述編碼代碼字除以所述第二多項式；確定所述第三次除法算法中是否有第三餘數；如果所述第三次除法算法中有第三餘數，則執行第四次除法算法，用所述編碼代碼字除以所述第一多項式與第二多項式的乘積；確定所述第四次除法算法中是否有第四餘數；用所述第四餘數來對所述編碼代碼字進行校正。
此外，本發明還提供一種用於有效地校正和檢測存儲設備的一個介質中的錯誤的系統，其中包括一個編碼器，它對寫到所述存儲設備的所述介質中的數據進行編碼；還包括一個解碼器，它使用至少兩個錯誤校正處理級，對從所述存儲設備的所述介質中讀取的數據進行解碼。
圖1是本發明的一個實施例中的錯誤校正和檢測系統的框圖；圖2是本發明的一個實施例中用於生成編碼代碼字的編碼處理的流程圖；圖3A和圖3B是本發明一個實施例中用於對編碼代碼字進行解碼的處理的流程圖。
具體實施例方式
本發明提供一種更有效地恢復存儲於存儲設備的介質中的數據的方法和系統，其通過使用多級解碼過程進行校正和檢測錯誤。在一個實施例中，該存儲設備包括磁碟驅動器。所述數據在從存儲設備中讀取時被校正和檢測。在本發明的一個實施例中，通過裡德-所羅門碼(reed-solomon code)實現錯誤校正和檢測。在一個實施例中，所述系統和方法在許多連續解碼級或處理級上使用編碼/解碼技術，該技術允許錯誤校正和檢測。在一個實施例中，執行至少兩個錯誤校正處理級。所述系統和方法的使用增大了在編碼代碼字中可被校正的最大符號錯誤數，從而改進了數據恢復。
圖1為本發明的一個實施例中的錯誤校正和檢測系統的框圖。該系統包括編碼器/解碼器子系統104、存儲設備116、存儲器124、控制處理器(CPU)128、以及數據接口132。編碼器/解碼器子系統104包括編碼器/解碼器電路108和編碼器/解碼器存儲器112。編碼器/解碼器電路108包括可編碼其接收自數據接口130的數據的數字邏輯電路。此外，編碼器/解碼器存儲器112可存儲一組可編碼和解碼其從一個或多個設備(例如數據接口132、存儲設備116、存儲器124、CPU128)接收的數據的指令、軟體、或固件。由編碼器/解碼器電路108完成的數據的編碼和解碼可通過執行一個或多個保存於編碼器/解碼器存儲器112中的指令實現。在一個實施例中，編碼器/解碼器存儲器112可存儲一組保存於編碼器/解碼器存儲器112的指令，所述指令可使用一個或多個算法進行編碼和解碼數據。當CPU執行該組指令時，執行所述一個或多個算法。
所述一個或多個算法包括如圖2、3A及3B所示的編碼和/或解碼算法。該編碼器/解碼器存儲器112包括一個只讀存儲器(ROM)例如可編程只讀存儲器(PROM)。在一種實施方式中，編碼器/解碼器電路108和/或編碼器/解碼器存儲器112可以是一個Reed-Solomon編碼器/解碼器。例如，編碼器/解碼器電路108和/或編碼器/解碼器存儲器112在從數據接口132接收數據後，可以生成一些編碼代碼字，如Reed-Solomon代碼字。當編碼器/解碼器子系統104寫入存儲設備116時，一個或多個適合的寫控制信號被傳送至該存儲設備116。另一方面，當編碼器/解碼器子系統104從存儲設備116讀出數據時，一個或多個適合的控制信號被傳送至存儲設備116。在寫或讀的操作中，數據在編碼器/解碼器子系統104與存儲設備116間傳輸。存儲設備116從一個介質120寫入或讀出數據。該介質120存在於存儲設備116內，可以是一個可移動的或可攜帶的介質120。該介質120包括一個磁性介質，例如一個磁碟驅動器。介質120存儲由編碼器/解碼器子系統104所生成的一個或多個編碼代碼字。編碼器/解碼器子系統104及控制處理器128可利用存儲器124，在編碼及解碼過程中存儲及處理數據。存儲器124包括隨機存取存儲器(RAM)，例如動態隨機存取存儲器(DRAM)。
通過編碼器/解碼器子系統104生成的每一個編碼代碼字中，包括一些符號。每個符號包括多個位。在一種實施方式中，符號位的數量等於10，而一個編碼代碼字中的符號的最大數量等於1023。通過編碼器/解碼器子系統接收的數據被分為一個或多個數據扇區。每個數據扇區可由一個編碼代碼字表示。該編碼代碼字包括一個或多個數據符號及一個或多個冗餘或奇偶符號。該冗餘或奇偶符號可包括例如由Reed-Solomon編碼器生成的符號。
如果一個編碼代碼字(要求表示數據扇區)內的數據和奇偶符號的數量為n，則編碼代碼字內使用的奇偶符號的數量等於2(t+k)。在一種實施方式中，錯誤校正及檢測系統生成一個次數為2t的第一多項式，及一個次數為2k的第二多項式。第一多項式的根及第二多項式的根均包括一個伽羅瓦域原始元素的連續次冪。在一種實施方式中，第二多項式的第一個根與第一多項式的最後一個根連續。上述的關係可以由經下數學式表示p(x)＝(x-a1)…(x-a2k) [第一多項式]f(x)＝(x-a2k+1)…(x-a2(t+k)) [第二多項式]如上述等式所示，伽羅瓦域的原始元素表示為a。編碼器/解碼器子系統104利用一個稱為是生成多項式的第三多項式，該第三多項式對應於第一多項式p(x)及第二多項式f(x)的乘積，該生成多項式g(x)可由下式表示g(x)＝p(x)f(x)＝(x-a1)…(x-a2(t+k))[第三多項式]所述編碼代碼字中的一個或多個數據符號c2(t+k)，c2(t+k)+1，…，cn-1，可由下式表示C(x)＝c2(t+k)x2(t+k)+c2(t+k)x2(t+k)+1+…+cn-1x(n-1)用C(x)除以g(x)之後，所得餘數提供一個或多個編碼代碼字的奇偶符號。所述餘數多項式為r(x)，其次數為2(t+k)-1，其由下式表示r(x)＝r0+r1x+…+r2x2(t+k)-1該編碼代碼字(如，一個或多個數據及奇偶符號)通過將r(x)加上C(x)而生成，可由下式表示C*(x)＝r(x)+C(x)＝r0+r1x+…+r2x2(t+k)-1+c2(t+k)x2(t+k)+c2(t+k)x2(t+k)+1+…+cn-1x(n-1)上式中，C*(x)表示n個符號的總數。
圖2為本發明的一種實施方式中，生成一個編碼代碼字的編碼過程及編碼算法的流程圖。編碼過程或算法利用上述的多項式f(x)，p(x)，g(x)，r(x)，C(x)及C*(x)，其均在伽羅瓦域中被定義。編碼算法利用一個處理過程，以使後續的解碼可以在後面將要描述的圖3A及圖3B中的多個處理級中被執行。所述編碼過程開始於步驟204，其中，基於t確定f(x)。如圖1所述的編碼器/解碼器子系統生成一個次數為2t的多項式f(x)，其根為伽羅瓦域中一個原始元素的連續次冪。當使用多項式f(x)時，變量t可定義可被圖1中所示的錯誤校正及檢測系統所校正的最大符號錯誤數。在一種實施方式中，定義變量t+k為一個代碼字中的符號總數與代碼字中的數據符號數量之間的差值的一半。如前所述，f(x)包括一個次數為2t的多項式。在一種實施方式中，t＝24或2t＝48。如步驟208所示，編碼器/解碼器子系統生成一個次數為2k的多項式，其根是同一原始元素的連續次冪。在一種實施方式中，k＝2或2k＝4。當使用多項式p(x)時，變量k定義了可通過圖1中所示的錯誤校正及檢測系統被校正的最大符號錯誤數。在一種實施方式中，在生產時(如在建構及生產圖1所述的錯誤校正及檢測系統時)，可先計算及執行多項式f(x)及p(x)。例如，在建構錯誤校正及檢測系統時，α及f(x)和p(x)的順序只被確定一次。在步驟212中，編碼器/解碼器子系統生成生成多項式g(x)。如前所述，g(x)為f(x)與p(x)的乘積。可通過一個Reed-Solomon碼編碼器定義及生成多項式f(x)，p(x)及g(x)。在一種實施方式中，多項式g(x)是預先確定的，因為如前所述，在生產時會先計算f(x)與p(x)。在步驟216中，通過C(x)除以g(x)生成餘數多項式r(x)。該餘數多項式r(x)包括2(t+k)奇偶位或冗餘項。然後，在步驟220中，通過將2(t+k)奇偶位或冗餘項與代碼字C(x)的數據部分相加，得到編碼代碼字C*(x)。C(x)是一個定義於伽羅瓦域定的多項式，其參數表示一個或多個數據符號。因此，可將編碼代碼字C*(x)寫入一個存儲設備的介質中，如一個磁碟驅動器中。在參數表示一個或多個數據及奇偶(或冗餘)符號的伽羅瓦域定義多項式C*(x)。本發明揭示了C*(x)的計算，對於通過錯誤校正及檢測系統接收的第個C(x)，將先計算值用於f(x)及p(x)。在一個算法實施例中，一個或多個符號由包括10比特的C(x)及C*(x)表示。
圖3A及圖3B為本發明一種實施方式的對編碼代碼字使用的解碼過程或解碼算法的流程圖。該解碼過程或算法利用前述的多項式f(x)，p(x)，g(x)，r(x)，C(x)及C*(x)。該解碼算法利用至少兩個錯誤校正級，以使當從存儲設備讀數據時，更有效地校正符號錯誤。在一種實施方式中，解碼算法利用一個三級解碼過程，其中，1)在第一處理級使用f(x)執行第一錯誤校正，2)在第二處理級使用p(x)執行錯誤檢測，及3)在第三處理級使用g(x)執行第二錯誤校正。第一處理級在步驟304中發生，其中，編碼代碼字C*(x)被圖3中所述的多項式f(x)除以。在步驟308中，解碼器電路決定了在C*(x)被f(x)除以後是否生成餘數。如果存在一個餘數，將處理程序轉到步驟312，校正t符號錯誤。否則，如果不存在餘數，處理程序轉到步驟316，以執行錯誤檢測。在第一處理級，通過利用餘數將編碼代碼字C*(x)校正至t錯誤的一個最大值。在一種實施方式中，使用Reed-Solomon在編碼代碼字C*(x)中校正t錯誤(用g(x)除以C*(x)，因而其也被f(x)除，其中，f(x)的次數為2t；所以，在第一級，利用該結果校正t符號錯誤)。在步驟314中，解碼器決定編碼代碼字是否已被成功解碼。如果該編碼代碼字沒有被成功解碼，處理過程轉到步驟324。否則，處理過程轉到步驟316，執行錯誤檢測。在步驟316中發生第二處理級，多項式p(x)除以編碼代碼字，以執行錯誤檢測。在步驟312中被校正的一個或多個符號錯誤可能過錯誤檢測被驗證。如果在步驟320中，被p(x)除以後有餘數，則編碼代碼字C*(x)中仍存在一個或多個錯誤，處理過程轉到步驟324。如前所述，第二處理級確定在第一處理級執行後是否存在錯誤。然而，如果在步驟320中，被p(x)除以後沒有餘數，則C*(x)中的所有錯誤被校正，該處理過程以成功解碼而結束。在一種實施方式中，利用具有2k次及冗餘符號的Reed-Solomon算法執行由第二處理級提供的錯誤檢測。如果被p(x)除以後有餘數，在步驟324中執行第三處理級的處理過程，用圖2中所述的發生多項式g(x)除以編碼代碼字C*(x)。如前所述，發生多項式g(x)的次數為2(t+k)。在步驟324中，確定被p(x)除以後是否有餘數。如果有餘數，在步驟328中，利用餘數校正C*(x)中的(t+k)個符號錯誤。在一種實施方式中，用Reed-Solomon算法校正C*(x)中的(t+k)個符號錯誤。g(x)除以C*(x)，其中，g(x)的次數為2(t+k)。作為結果，第三處理級利用結果校正(t+k)個符號錯誤。當被g(x)除以時，錯誤校正能力所允許的錯誤校正的錯誤最大值為(t+k)個。在步驟332中確定是否成功完成了解碼。如果數據沒有被解碼，在程序結尾發生了失敗的解碼或錯誤。否則，程序結果時期解碼成功。前述的錯誤校正及檢測處理在除了第三級處理的其它級中執行，以提供其它的錯誤校正/檢測能力。
可選擇地，在上述的編碼/解碼過程的另一實施方式中，執行寫或讀操作的校正是為了避免一個問題的發生，該問題是在實際的同步記號區域之前或之後，讀操作遇到一個替換的同步標記符號的整數數量。在一種實施方式中，由這樣的替換同步標記導致的編碼代碼字中的周期替換可能會導致另一個有效的代碼字，例如，當使用Reed-Solomon代碼字時。符號(或字節，當符號包括8位時)數量被加到相應的符號(或字節)值。例如，在前述的編碼之後執行的變換，但是在將編碼代碼字寫入存儲設備的介質之前c*→c*j+j，j＝0，…，n-1這裡，c*表示符號而j表示符號數量。在本實施方式中，當從存儲設備讀入數據時，為了正確讀入數據，在執行編碼代碼字的解碼之前執行變換。
權利要求
1.一種對存儲於存儲設備中的數據進行編碼的方法，其特徵在於，包括生成第一多項式，其根包括伽羅瓦域中一個原始元素的一次或多次冪；生成第二多項式，其根包括所述伽羅瓦域中一個原始元素的一次或多次冪；生成所述第一多項式與第二多項式的乘積。
2.根據權利要求1所述的方法，其特徵在於，所述第一多項式的所述原始元素的一次或多次冪包括連續的整數值。
3.根據權利要求2所述的方法，其特徵在於，所述第一多項式的次數等於48。
4.根據權利要求1所述的方法，其特徵在於，所述第二多項式的所述原始元素的一次或多次冪包括連續的整數值。
5.一種對存儲於存儲設備的一個介質中的數據進行編碼和解碼的方法，其特徵在於，包括生成第一多項式，其根包括伽羅瓦域中一個原始元素的一個或多個連續次冪；生成第二多項式，其根包括所述伽羅瓦域中一個原始元素的一個或多個連續次冪；生成所述第一多項式與第二多項式的乘積；執行第一次除法算法，用一個第三多項式除以所述乘積以生成一個第一餘數，用所述第一餘數來生成一個編碼代碼字，所述第三多項式代表數據的一個區，所述數據扇區包括多個符號；將所述編碼代碼字寫到所述存儲設備的一個介質中；從所述存儲設備讀取所述編碼代碼字；執行第二次除法算法，用所述編碼代碼字除以所述第一多項式；確定所述第二次除法算法中是否有一個第二餘數；用所述第二餘數來對所述編碼代碼字進行校正；執行第三次除法算法，用所述編碼代碼字除以所述第二多項式；確定所述第三次除法算法中是否有第三餘數；如果所述第三次除法算法中有第三餘數，則執行第四次除法算法，用所述編碼代碼字除以所述第一多項式與第二多項式的乘積；確定所述第四次除法算法中是否有第四餘數；用所述第四餘數來對所述編碼代碼字進行校正。
6.根據權利要求5所述的方法，其特徵在於，所述第一多項式的次數為48。
7.根據權利要求5所述的方法，其特徵在於，所述第二多項式的次數為4。
8.一種用於有效地校正和檢測存儲設備的一個介質中的錯誤的系統，其特徵在於，包括一個編碼器，它對寫到所述存儲設備的所述介質中的數據進行編碼；一個解碼器，它使用至少兩個錯誤校正處理級，對從所述存儲設備的所述介質中讀取的數據進行解碼。
9.根據權利要求8所述的系統，其特徵在於，還包括一個存儲器，駐留於所述存儲器中的一指令集，所述指令可實現使用於所述數據編碼和解碼中的一個或多個算法。
10.根據權利要求9所述的系統，其特徵在於，所述指令集可實現一個可執行於多個處理級的解碼過程，所述解碼過程包括第一處理級，它用於校正一個編碼代碼字的第一最大符號錯誤數；第二處理級，它用於在執行了所述第一處理級的校正之後，檢測所述編碼代碼字中的符號錯誤；第三處理級，它用於校正所述編碼代碼字的第二最大符號錯誤數。
全文摘要
本發明提供了一種可有效地重現存儲於存儲設備的介質中的數據的方法和系統。其中，通過使用一個多級解碼過程來校正和檢測錯誤，以實現所述方法和系統。在一個實施例中，所述存儲設備包括一個磁碟驅動器。在一個實施例中，所述方法和系統使用了一種編碼/解碼技術，使得錯誤校正和檢測可執行於多個連續的解碼級或處理級。使用所述方法和系統，可提高最大符號錯誤數，該最大符號錯誤數在一個編碼代碼字中是可被校正的，從而提供一種更好的數據恢復手段。
文檔編號G11B20/18GK1648868SQ20051000664
公開日2005年8月3日 申請日期2005年1月14日 優先權日2004年1月14日
發明者安德烈·維蒂爾夫 申請人:美國博通公司