(57)【要約】【課題】オンドライブＲＡＩＤシステムなどにおけるパリティ・セクタ訂正による誤訂正を防止する符号化システムおよび関連方法を提供すること。【解決手段】このシステムでは、それ自体もＣ３保護を受ける完全なクラスタであるパリティ・クラスタ・ブロックを追加する。信頼性レベルの高いＣ３チェックによってチェックされ検証される、パリティ・セクタによる、クラスタ・レベルのＣ４レベル訂正と、クラスタ・ブロックの整合性をチェックする機能を設けることにより、「ジャミ」エラーが発生しても、不良データ提供の可能性はほとんどなくなる。Ｃ２およびＣ３チェックの完了を記憶装置がアイドル状態になるまで遅らせることにより、スクラブ・アルゴリズムは、読取り−変更−書込み動作を回避する。【選択図】図１
2004171751.tif 000002
【特許請求の範囲】
【請求項１】
パリティ・セクタ訂正による誤訂正を防止する方法であって、
マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成するステップと、
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップと、
誤訂正が検出された場合、どの読取り不可または消去されたセクタも対応するパリティ・セクタで置換されないようにするステップと、
誤訂正が検出されなかった場合、前記読取り不可または消去されたセクタを対応するパリティ・セクタで置換するステップとを含む方法。
【請求項２】
前記マルチレベルの誤り訂正符号に従ってクラスタ・レベルのチェック・バイトを生成するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記クラスタ・レベルのチェック・バイトの少なくともいくつかを使用して、クラスタ・レベルにおける、パリティ・セクタ訂正による誤訂正の発生を判断するステップと、
誤訂正が発生したと判断された場合、エラー・メッセージを返すステップとをさらに含む、請求項２に記載の方法。
【請求項４】
セクタ・レベルのチェック・バイトを生成するステップが、クラスタ内の各セクタを誤訂正から保護するステップと、前記クラスタ内で誤訂正のクロス・チェックを行うステップとを含む、請求項１に記載の方法。
【請求項５】
前記マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成するステップが、４レベル・チェック、すなわちＣ１、Ｃ２、Ｃ３、Ｃ４チェックを生成するステップを含む、請求項２に記載の方法。
【請求項６】
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップが、クラスタ・レベルでＣ３チェックを再計算するステップを含む、請求項５に記載の方法。
【請求項７】
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップが、クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックするステップをさらに含む、請求項６に記載の方法。
【請求項８】
クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックするステップが、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての和を計算するステップを含む、請求項７に記載の方法。
【請求項９】
クラスタ・ブロック・レベルで前記Ｃ３チェックすべての前記和を計算するステップが、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての排他的論理和演算を実施するステップを含む、請求項８に記載の方法。
【請求項１０】
クラスタ・ブロック・レベルで計算された前記Ｃ３チェックすべての前記和が０ではない場合に、誤訂正が検出される、請求項９に記載の方法。
【請求項１１】
クラスタ・ブロック・レベルで計算された前記Ｃ３チェックすべての前記和が０である場合に、誤訂正が検出されない、請求項１０に記載の方法。
【請求項１２】
クラスタ内のセクタの読取り可不可状態を表す、前記セクタ用の読取り可不可バイトを計算するステップをさらに含む、請求項２に記載の方法。
【請求項１３】
前記読取り可不可バイトが仮想的なものである、請求項１２に記載の方法。
【請求項１４】
前記読取り可不可バイトを前記マルチレベルの誤り訂正符号の指定されたレベルに符号化するステップを含む、請求項１３に記載の方法。
【請求項１５】
クラスタ・グループ内のクラスタの読取り可不可状態を表す、前記クラスタ用の読取り可不可バイトを計算するステップをさら含む、請求項２に記載の方法。
【請求項１６】
スクラブ更新操作を用いて、前記セクタ・レベルのチェック・バイトを生成し、前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップをさらに含む、請求項５に記載の方法。
【請求項１７】
前記スクラブ更新操作が、アイドル時間中に実施される、請求項１６に記載の方法。
【請求項１８】
前記スクラブ更新操作を用いるステップが、前記アイドル時間中に前記レベル・チェックの少なくともいくつかを計算するステップを含む、請求項１７に記載の方法。
【請求項１９】
前記アイドル時間中に前記レベル・チェックの少なくともいくつかを計算するステップが、前記アイドル時間中に前記Ｃ２、Ｃ３、Ｃ４チェックを計算するステップを含む、請求項１８に記載の方法。
【請求項２０】
前記Ｃ１チェックをオンザフライに（on-the-fly）計算するステップをさらに含む、請求項１９に記載の方法。
【請求項２１】
パリティ・セクタ訂正による誤訂正を防ぐことのできる記憶装置であって、
マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成する手段と、
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段とを含み、
前記判断手段が誤訂正を検出した場合、前記判断手段が、どの読取り不可または消去されたセクタも対応するパリティ・セクタで置換させず、
前記判断手段が誤訂正を検出しなかった場合、前記判断手段が、前記読取り不可または消去されたセクタを対応するパリティ・セクタで置換する記憶装置。
【請求項２２】
前記マルチレベルの誤り訂正符号によってクラスタ・レベルのチェック・バイトを生成する手段をさらに含む、請求項２１に記載の記憶装置。
【請求項２３】
前記クラスタ・レベルのチェック・バイトの少なくともいくつかを使用して、クラスタ・レベルにおける、パリティ・セクタ訂正による誤訂正の発生を判断する手段をさらに含む、請求項２２に記載の記憶装置。
【請求項２４】
セクタ・レベルのチェック・バイトを生成する手段が、クラスタ内の各セクタを誤訂正から保護し、前記クラスタ内で誤訂正のクロス・チェックを行う、請求項２１に記載の記憶装置。
【請求項２５】
前記マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成する手段が、４レベル・チェック、すなわちＣ１、Ｃ２、Ｃ３、Ｃ４チェックを生成する、請求項２２に記載の記憶装置。
【請求項２６】
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段が、クラスタ・レベルでＣ３チェックを再計算する、請求項２５に記載の記憶装置。
【請求項２７】
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段が、クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をさらにチェックする、請求項２６に記載の記憶装置。
【請求項２８】
クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックする手段が、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての和を計算する、請求項２７に記載の記憶装置。
【請求項２９】
クラスタ内のセクタの読取り可不可状態を表す、前記セクタ用の仮想読取り可不可バイトを計算する手段をさら含む、請求項２２に記載の記憶装置。
【請求項３０】
前記セクタ・レベルのチェック・バイトを生成し、前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するスクラブ更新操作をさらに含む、請求項２５に記載の記憶装置。
【請求項３１】
少なくとも１つのパリティ・ブロックを有するデータ・セットを、前記データ・セット内の不整合なパリティによる誤訂正から保護する方法であって、
前記データ・セット内の情報からクロス・チェックを生成するステップと、
前記クロス・チェックを前記データ・セットと関連付けて保存するステップと、
消去イベントの発生時に、前記パリティ・ブロックから消失データを再構成するステップと、
前記再構成されたデータを含む前記データ・セットから新しいクロス・チェックを生成するステップと、
前記新しいクロス・チェックと前記保存されたクロス・チェックとを比較するステップと、
前記比較された再構成クロス・チェックと前記新しいクロス・チェックとが整合している場合、前記再構成データが有効であると判断し、前記再構成データの使用を許可するステップと、
前記比較された再構成クロス・チェックと前記新しいクロス・チェックとが整合していない場合、前記再構成データが無効であると判断し、エラーを通知するステップを含む方法。
【請求項３２】
前記クロス・チェックを生成するステップが、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成するステップを含む、請求項３１に記載の方法。
【請求項３３】
前記データ・セットが複数のパリティ・セクタを含む、請求項３１に記載の方法。
【請求項３４】
前記クロス・チェックを生成するステップが、前記データ・セットのサブセットに対するパリティ・セクタを生成するステップを含む、請求項３３に記載の方法。
【請求項３５】
前記クロス・チェックを生成するステップが、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックを生成するステップをさらに含む、請求項３４に記載の方法。
【請求項３６】
データ・セットを含むデータ記憶装置であって、前記データ・セットが少なくとも１つのパリティ・ブロックで保護されるとともに、前記データ・セットと関連付けて保存されたクロス・チェックによっても保護され、
前記データ・セットから前記パリティ・ブロックを生成する手段と、
前記データ・セットからクロス・チェックを生成する手段と、
消去イベントによって前記パリティ・ブロックから消失したデータを再構成する手段と、
前記再構成されたデータ・セットから新しいクロス・チェックを生成する手段と、
前記新しいクロス・チェックと保存されたクロス・チェックとを比較する手段と、
前記比較された新しいクロス・チェックと前記保存されたクロス・チェックとが整合していない場合、エラーを通知する手段を含むデータ記憶装置。
【請求項３７】
前記クロス・チェックを生成する手段が、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成する、請求項３６に記載のデータ記憶装置。
【請求項３８】
前記データ・セットが複数のパリティ・セクタを含む、請求項３６に記載のデータ記憶装置。
【請求項３９】
前記クロス・チェックを生成する手段が、前記データ・セットのサブセットに対するパリティ・セクタを生成する、請求項３８に記載のデータ記憶装置。
【請求項４０】
前記クロス・チェックを生成する手段が、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックをさらに生成する、請求項３９に記載のデータ記憶装置。
【請求項４１】
命令コードを有し、データ・セットを含み、前記データ・セットが少なくとも１つのパリティ・ブロックで保護されるとともに、前記データ・セットに関連付けて保存されたクロス・チェックによっても保護される、誤り訂正符号データ構造であって、
前記データ・セットから前記パリティ・ブロックを生成するための、第１組の命令コードと、
前記データ・セットからクロス・チェックを生成するための、第２組の命令コードと、
消去イベントによって前記パリティ・ブロックから消失したデータを再構成するための、第３組の命令コードとを含み、
前記第３組の命令コードが、前記再構成されたデータ・セットから新しいクロス・チェックをさらに生成し、
前記第３組の命令コードが、前記新しいクロス・チェックを保存されたクロス・チェックと比較し、前記比較された新しいクロス・チェックと保存されたクロス・チェックとが整合していない場合、エラーを通知する誤り訂正符号データ構造。
【請求項４２】
前記第２組の命令コードが、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成する、請求項４１に記載の誤り訂正符号データ構造。
【請求項４３】
前記データ・セットが複数のパリティ・セクタを含む、請求項４１に記載の誤り訂正符号データ構造。
【請求項４４】
前記第２組の命令コードが、前記データ・セットのサブセットに対するパリティ・セクタを生成する、請求項４３に記載の誤り訂正符号データ構造。
【請求項４５】
前記第２組の命令コードが、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックをさらに生成する、請求項４４に記載の誤り訂正符号データ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、データ記憶装置およびシステムまたは通信装置およびシステムに関し、詳細には、データ記憶装置およびシステムまたは通信装置およびシステムのための、統合化セクタ・フォーマット（ＩＳＦ）誤り訂正符号（ＥＣＣ）の符号化／復号化処理に関する。より詳細には、本発明は、オンドライブＲＡＩＤシステムにおけるパリティ・セクタ訂正による誤訂正を防止するためのシステムおよび関連方法に関する。
【背景技術】
【０００２】
関連出願の相互参照
本出願は、本出願と同一の出願人に譲渡され、参照によりその全体が本明細書に組み込まれている、「Multiple Level (ML), Integrated Sector Format (ISF), ErrorCorrection Code (ECC) Encoding And Decoding Processes For Data Storage OrCommunication Devices And Systems」と題する、２００２年１月３日出願の同時係属中の米国出願第１０／０４０，１１５号に関連する。
【０００３】
ハードディスク・ドライブ（ＨＤＤ）などのデータ記憶装置およびシステムにおいて、劣悪な書込み／読取り状態と信号対雑音比（ＳＮＲ）が低いデータ検出とが組み合わさると、ディスク上に格納されたデータ・セクタ内で、長いバースト・エラーとランダム・エラーとの混合エラー・モードが発生する可能性が高まる。格納されたセクタ・データの数バイトを冗長なチェック・バイトで保護された符号語にフォーマットするため、また符号語の中のバイト・エラーを発見し訂正するために、一般に、バイト・アルファベットのリード−ソロモン（ＲＳ）符号が用いられる。
【０００４】
長い符号語は、冗長なチェック・バイトのオーバヘッドが長いデータ・ブロックにわたって平均化されるので、長いバースト・エラーからデータを保護するのに有効である。しかし、現在の論理ユニットのデータ・セクタが５１２バイト長であり、現在のコンピュータ・ホスト・オペレーティング・システムが５１２バイト長セクタの論理ユニットを前提としているため、読取り−変更−書込み（ＲＭＷ）処理を用いないかぎり、データ記憶装置において、長い符号語を使用することはできない。
【０００５】
各ＲＭＷ処理は、データ記憶装置媒体の回転を浪費する。データ記憶装置媒体の回転の浪費は、入出力（Ｉ／Ｏ）命令のスループットを低下させる。したがって、ＲＭＷ処理はＩ／Ｏ命令のスループットを低下させることになるので、これを頻繁に用いるべきではない。
【０００６】
ＳＮＲが低い検出と劣悪な書込み／読取り状態とが組み合わさると、ＨＤＤ業界の潮流となっている高い面積密度と低い浮上高のもとでは、ランダム・エラーと長いバースト的なバイト・エラーがともに発生する（「混合エラー・モード」）可能性がますます高くなりうる。ランダム・エラーとバースト・エラーが組み合わさった混合エラー・モードが発生すると、５１２バイト・セクタのインタリーブされたＯＴＦ  ＥＣＣが機能しなくなり、再読取りやヘッドの移動などを必要とするデータ復旧手続き（ＤＲＰ）をより頻繁に用いる結果になる可能性が高い。
【０００７】
これらのＤＲＰ動作は、入出力（Ｉ／Ｏ）のスループットを低下させるディスクの回転の浪費を招く。このパフォーマンスの損失は、ビデオ・データ・ストリームの頻繁な中断を許さない、オーディオ・ビジュアル（ＡＶ）データの転送など、多くの適用分野では容認しがたい。一方、５１２バイトの論理ユニット・セクタ・フォーマットにおいて、すべての単一セクタをランダム・エラーおよびバースト・エラー両方から単一方式で保護しようとすれば、過剰で許容しがたいチェック・バイトのオーバヘッドを招く。そのようなチェック・バイトのオーバヘッドはまた、データの線密度の増加によって、ソフト・エラー率を増加させる。
【０００８】
８セクタを含む４Ｋバイトの物理ブロックなど、長いブロック・データのＥＣＣが、いくつかの適用分野では解決策となりうるが、単一の５１２バイト・セクタを書き込むときに、読取り−変更−書込み（ＲＭＷ）を容認しないかぎり、オペレーティング・システム規格に変更が必要となる。現在のオペレーティング・システムはすべて、５１２バイト長セクタの論理ユニットに基づいている。長い物理ブロックのチェック・バイトを更新することがＲＭＷには必要とされる。したがって、単一の５１２バイト・セクタを書き込むとき、長いブロックの他のセクタを読み取り、その長いブロックのチェック・バイトを再計算し、次にその長いブロック全体を再び書き込まなければならない。したがって、ＲＭＷは、標準的なＨＤＤ動作では一般に容認しがたいＩ／Ｏスループットのパフォーマンスの損失を招く。
【０００９】
したがって、セクタ障害率が低く、ランダム・エラーとバースト・エラーとの混合エラー・モードを発生させにくい、データ記憶装置用のＥＣＣフォーマットであって、ＤＲＰまたはＲＭＷの頻繁な使用を回避し、チェック・バイトのオーバヘッドも許容範囲内にある、データ記憶装置用のＥＣＣフォーマットがあることが望ましい。それゆえ、データ記憶装置およびシステム用または通信装置およびシステム用の、複数レベル（ＭＬ）統合化セクタ・フォーマット（ＩＳＦ）誤り訂正符号（ＥＣＣ）の符号化／復号化処理が必要とされている。この必要を満たすシステムおよび関連方法が、前掲の米国出願第１０／０４０，１１５号に開示されている。
【特許文献１】米国出願番号１０／０４０，１１５
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明に特に関連する問題は、例えば、クラスタ・ブロック内の１つの８セクタ・データ・クラスタの一部または全部が完全に消失する可能性があることである。説明のため、クラスタ・ブロックは１６個のデータ・クラスタで構成できるものとする。オンドライブのＲＡＩＤ５システムなどにおいて、読取り不可または消去されたセクタ（または複数のセクタ）をパリティ・クラスタ内のパリティ・セクタで置換することに伴う問題は、パリティ・セクタがクラスタ・ブロック内のデータ・クラスタと整合しているとの検証を欠いていることである。したがって、さらに必要なことは、パリティ・セクタ訂正が誤訂正でないとのクラスタ・ブロック全体にわたる信頼性をチェックできる機能である。
【００１１】
別の特有の問題は、不整合境界書込み動作に関する。不整合境界書込み動作とは、物理的な８セクタ・データ・クラスタの最初の論理ブロック・アドレス（ＬＢＡ）から始まらない書込み動作、または物理的な８セクタ・データ・クラスタの最後のＬＢＡで終らない書込み動作のことである。不整合境界書込み動作となる場合、８セクタ・データ・クラスタ用の第２および第３レベル（Ｃ２／Ｃ３）符号化処理を完了させるには、読取り−変更−書込み（ＲＭＷ）動作が必要になる。
【００１２】
順次書込みの場合、読取り−変更−書込み（ＲＭＷ）動作が必要になる頻度は低く、したがって、Ｃ２／Ｃ３保護を実施しても、憂慮すべき問題を招くことはないであろう。しかし、ランダム書込みの場合、Ｃ２／Ｃ３保護の実施は、パフォーマンスの見地から許容しがたい。したがって、ＲＭＷ動作を回避しながら、並行して、不整合境界書込みによってＩＳＦ保護が分断されている８セクタ・データ・クラスタ内で、Ｃ２／Ｃ３保護を実施する必要がある。
【００１３】
さらに別の特有の問題は、Ｃ３符号化処理を実施したデータ・クラスタ内に書き込まれたセクタを消去する場合があるデータ消去、「ジャミ（jami）」が発生することである。したがって、「仮想的」なバイトで表される、データ・クラスタ内のセクタの読取り可不可（readability）状態を導入する必要がある。セクタの読取り可不可状態は、実際にディスクに書き込むべきではなく、Ｃ３チェックに符号化すべきである。セクタの読取り可不可状態は、ドライブのスクラブ（scrub）動作の間に、更新し、Ｃ３チェックに再び符号化して、これらのＣ３チェックが、より高いレベルの保護に対する誤訂正チェック（すなわち、ＣＲＣ）として機能するようにすべきである。
【課題を解決するための手段】
【００１４】
本発明は、これらの必要を満足し、オンドライブのパリティ・セクタ・システム内のＩＳＦ−ＥＣＣシステムにおける、パリティ・セクタ更新が原因の誤訂正を防止するための、システム、コンピュータ・プログラム製品、および関連方法（本明細書では、これらをまとめて「システム」または「本システム」と呼ぶ）を提示する。
【００１５】
この目的のため、システムは、パリティ・クラスタによって保護されたクラスタ・ブロックを提供する。パリティ・クラスタ自体もＣ３保護を受ける完全なクラスタである。実際には、この保護は、本明細書で「Ｃ４レベル」、「Ｃ４保護」、または「Ｃ４訂正」と呼ぶ、クラスタ・ブロック上のマルチセクタ・パリティ・ストライプとして実施される第４のＩＳＦ保護レベルを形成する。
【００１６】
セクタ・クラスタ内の読取り不可または消去されたセクタをパリティ・セクタで置換し、またはクラスタ全体をパリティ・クラスタで置換する場合、不正または「不良」データを顧客に提供することのないよう、誤訂正のチェック手段が必要となり、パリティ・セクタ（またはパリティ・クラスタ）がクラスタ・ブロック内のデータと整合していることの保証が必要となる。
【００１７】
信頼性レベルの高いＣ３チェックによってチェックおよび検証される、パリティ・セクタによる、クラスタ・レベルのＣ４レベル訂正と、クラスタ・ブロックの整合性をチェックする機能とを設けることにより、「ジャミ」エラーが発生しても、不良データ提供の可能性はほとんどなくなる。
【００１８】
より具体的には、本発明は、個々のデータ・クラスタがＣ４保護を受けるクラスタ・ブロックに属するかどうかを明らかにするＩＳＦ−ＥＣＣ  Ｃ３チェック・バイトを８セクタ・データ・クラスタ内で巡回冗長検査（ＣＲＣ）として使用することについて教示する。１つまたは複数のセクタがデータ・クラスタ内に書き込まれ、Ｃ２／Ｃ３チェック・バイトが更新されたにもかかわらず、クラスタ・ブロック内のデータ・クラスタに読取り不可または消去されたセクタがあって、Ｃ４パリティ・クラスタが更新されなかった場合、クラスタ・ブロックにわたるＣ３チェックを計算して、クラスタ・ブロックの不整合を検出し、誤訂正を回避することができる。
【００１９】
各データ・クラスタの仮想的な読取り可不可状態をＣ３チェックに符号化することで、「ジャミ」消去が発生した場合の、誤訂正からの保護が提供される。
【００２０】
本発明の利点は、様々な保護レベルを有し、様々なエラー・メカニズムからの保護を提供するＩＳＦ−ＥＣＣの構造に固有のものである。ＩＳＦ−ＥＣＣは、稀にしか起らないエラー事象、すなわち、セクタ、複数のセクタ、またはセクタ・クラスタの長い範囲にわたる欠陥や消失に対する信頼性の高い保護を、可能な限り低いオーバヘッドで可能にする。
【００２１】
本システムは、クラスタ・ブロックがパリティ・ストライプである、オンドライブｒａｉｄとして適用可能であり、オンドライブｒａｉｄレベルの訂正は、複数の下位の訂正レベルによって検証される。ＩＳＦ−ＥＣＣは、オンドライブｒａｉｄ訂正レベルの誤訂正をほとんど起らなくする。
【００２２】
本発明の様々な特徴およびそれらを達成する方法を、以下の詳細な説明、特許請求の範囲、図面を参照しながら詳細に説明する。参照項目の間の対応関係を示すため、該当する場合は、参照番号を再利用する。
【発明を実施するための最良の形態】
【００２３】
図１には、従来技術による、ディスク・ドライブならびに読取りパスおよび書込みパスの一部を表す部分論理図が示されている。直接アクセス記憶装置とも称されるディスク・ドライブは、周期的に回転する磁気ディスク１と、電磁的な変換器３が先端に設けられた、半径方向または軸方向に可動なアクセス・アーム５とを含む。変換器３は、デジタル２進符号語のシーケンスを表す磁束パターンを、ディスク上の所定数の同心トラックのいずれか１つに沿って記録し、または記録された磁束パターンを選択された１つのトラックから読み取って、それらを符号語に変換するためのものである。
【００２４】
デジタル２進データのシーケンスをディスク１に書き込むべき場合、そのデータ・シーケンスは一時的にバッファ１５に格納され、その後、複数の段階を有する書込みパスまたはチャネル（１７、１９、７、５、３）を辿って処理され、変換される。最初、データ・ストリングの中の所定数の２進データ要素（バイトとも称される）がバッファから取り出され、誤り訂正符号（ＥＣＣ）書込みプロセッサ１７の中を流れていく。プロセッサ１７中で、データ・バイトは、従来技術においてよく理解されているように、リード−ソロモン（ＲＳ）符号など、適当な線形ブロック符号または巡回符号から得られる符号語に写像される。次に、各符号語は、書込みパス信号整形ユニット１９中で、ランレングス・リミテッド符号や、他のバンドパスまたはスペクトル整形符号に写像され、時間変化信号に変換される。時間変化信号は、インタフェース７を通り、磁束パターンに変換するため、磁気抵抗変換器または他の適切な変換器３の書込み素子に与えられる。
【００２５】
２進データ要素をバッファ１５から取り出し、回転するディスク１がヘッド３の下を通過したときに磁束パターンを選択されたディスク・トラックに書き込むまでのすべての処理は、同期式かつストリーミング式である。効率的なデータ転送のため、データは同時にディスク・セクタにデステージ（書込み）され、ステージ（読取り）される。したがって、２進符号語をリード−ソロモン符号語へ写像し、磁束を生成する時間変化信号へ変換することを、単位長さの記録トラックが変換器の下を通過する時間で定義される時間間隔の間に、成し遂げなければならない。一般的な記録トラックの単位長は、５１２バイトの固定長バイト・セクタに等しい。
【００２６】
磁束パターンのシーケンスをディスク１から読み取るべき場合、磁束パターンのシーケンスは別のいわゆる読取りパスまたはチャネル（７、９、１１、１３）で処理され、バッファ１５に書き込まれる。変換器３によって感知された時間変化信号は、インタフェース７を通り、信号抽出ユニット９に渡される。ここでは信号を検出し、信号が２進値の１であるか０であるかについて判定する。これらの１および０は、信号抽出ユニット９からパス２５を介して送出され、フォーマッティング・ユニット１１内で符号語に整えられる。読取りパスは、先にディスク１に記録されたＲＳ符号語のシーケンスを評価するので、エラーやデータ消去が発生していない場合は、符号語は同じでなければならない。
【００２７】
エラーやデータ消去が発生したかどうかを検査するため、各符号語は、フォーマッタからパス２７を介してＥＣＣ読取りプロセッサ１３に与えられる。また、ＥＣＣ読取りプロセッサ１３からのエラーを取り除いた（sanitized）出力は、パス２９を介してバッファ１５に書き込まれる。読取りパスもまた、ディスクから読み取られた次の符号語をＥＣＣ読取りプロセッサが受け取るまでの時間に、検出されたエラーが符号語内で発見され訂正されるように、同期データ・ストリーミング方式で動作しなければならない。バッファ１５ならびに読取りパスおよび書込みパスは、効率を保証するため、順次読取り参照などの参照パターンにより、パスがテイクダウンしないように指示できるように、マイクロプロセッサ（図示せず）によって監視および制御することができる。
【００２８】
図２および図３には、本発明の好ましい実施形態による、セクタ数Ｎ＝８、３レベルＥＣＣ（ｎ＝３）を例とする、ＭＬ−ＩＳＦ−ＥＣＣ符号化処理のための方法および装置が示されている。より具体的には、図２には、２分木の各ノードで、累積的なチェック・サムを格納するために使用されるレジスタが示されている。同様に、図３には、チェック・バイト・セットごとに明示的な等式を用いて、これらのレジスタの内容を結合させ、統合化フォーマット・チェックを生成するための方法が示されている。
【００２９】
図２および図３の例は、符号化／復号化用の現在のＭＬ−ＩＳＦ−ＥＣＣ方法が、完全に汎用的であり、統合化セクタの数Ｎがいくつであっても、ＥＣＣレベルの数ｎがいくつであっても、またＮセクタの物理ブロック内のセクタを結合し、ＭＬ−ＩＳＦ−ＥＣＣ符号化／復号化方式において共用されるチェック・バイトを提供するための望ましいパターンが何であっても有効であることを明らかにするために示したものであり、この例のみに限定されるものではない。
【００３０】
本発明の好ましい実施形態では、リード−ソロモン符号器／復号器を実装するかどうかは、設計上の選択の問題であり、その他の符号化／復号化技法を使用してもよい。
【００３１】
本発明の例示的な実施形態としてディスク記憶装置を取り上げて本発明を説明してきたが、本発明の範囲および教示から逸脱することなく、本明細書に記載した方法および手段に様々な変更を加えることができることは理解できるであろう。したがって、本発明の原理はまた、通信システムなどから受信される、線形に誤り訂正符号化を施した長いバイト・ストリングにおけるエラーの検出および訂正にも関する。通信システムでは、情報の単位は好ましくは、情報セクタではなく情報パケットと呼ばれるものであり、セクタもパケットも共に所定量の情報を有する情報の単位を表す。
【００３２】
次に図４を参照すると、複数のデータ・セクタ・クラスタ１、２、３、４ないしＮ−１と、パリティ・クラスタＮ（パリティ・クラスタＣ４とも呼ぶ）とを含む、例示的なクラスタ・ブロック９００が示されている。パリティ・クラスタＣ４は、セクタ消去に対するより強力な保護を提供するために追加される。
【００３３】
本発明は、クラスタおよびセクタに関して説明されるが、本発明がクラスタのストライプ（またはグループ）にも同様に適用可能であることは明らかであろう。
【００３４】
この目的のため、本システムは、それ自体がＣ３保護を受ける完全なクラスタであるパリティ・クラスタＣ４により保護されたクラスタ・ブロック９００を提供する。実際には、この保護は、クラスタ・ブロック上のマルチセクタ・パリティ・ストライプとして実装される第４のＩＳＦ保護レベルを形成する。より具体的には、パリティ・セクタＣ４は、先に説明した他のクラスタ１ないしＮ−１と同様に、Ｃ１、Ｃ２、Ｃ３保護レベルにより保護される。
【００３５】
例として８セクタ・クラスタを考察すると、パリティ・クラスタまたはＣ４チェック保護レベルも、データ・セクタ１ないしＮ−１と同様の保護レベル、Ｃ１、Ｃ２、Ｃ３を備え、以下のように形成される。
【００３６】
以下に示すように、クラスタ・ブロック９００内の、パリティ・クラスタＣ４を含むすべてのセクタ１ないしＮのデータＤｉ、ｉ＝１，．．．，８の排他的論理和（ＸＯＲ）による和は、０に等しい。
【００３７】
【数１】
2004171751.tif 000003
【００３８】
同様に、以下に示すように、クラスタ・ブロック９００内の、パリティ・クラスタＣ４を含むすべてのセクタ１ないしＮのＣ１チェック保護レベルＣｉ、ｉ＝１，．．．，８の排他的論理和（ＸＯＲ）による和は、０に等しい。
【００３９】
【数２】
2004171751.tif 000004
【００４０】
例として、第２列について考察すると、以下に示すように、クラスタ・ブロック９００内の第２列の、パリティ・クラスタＣ４を含むすべてのセクタ１ないしＮのデータＤ２の排他的論理和（ＸＯＲ）による和は、０に等しい。
【００４１】
【数３】
2004171751.tif 000005
同様のＸＯＲによる和が、クラスタ・ブロック９００内のすべてのデータ・セクションＤｉに当てはまる。
【００４２】
以下に示すように、クラスタ・ブロック９００内の第４列の、パリティ・クラスタＣ４を含むすべてのセクタ１ないしＮのＣ２チェック保護レベルの排他的論理和（ＸＯＲ）による和は、０に等しい。
【００４３】
【数４】
2004171751.tif 000006
【００４４】
同様に、以下に示すように、クラスタ・ブロック９００内の第８列の、パリティ・クラスタＣ４を含むすべてのセクタ１ないしＮのＣ３チェック保護レベルの排他的論理和（ＸＯＲ）による和は、０に等しい。
【００４５】
【数５】
2004171751.tif 000007
【００４６】
結果として、本システムは、Ｃ２およびＣ３保護レベルを、パリティ・クラスタＣ４用の巡回冗長検査（ＣＲＣ）に使用している。
【００４７】
加えて、さらに図５を参照すると、本発明の特徴の１つは、クラスタ・ブロック９００内の各クラスタ用の仮想的な読取り可不可バイト９２０を含むことである。仮想的な読取り可不可バイト９２０はディスクに書き込まず、Ｃ３チェックに符号化される。
【００４８】
図４の例では、８セクタ・クラスタ（読取り不可セクタ９０５を含むクラスタ２など）が読み取られるときに、対応する読取り可不可バイト９２０（図５）が生成される。読取り可不可バイトの中の各ビットは、対応するセクタの読取り可不可状態を表す。
【００４９】
この例では、読取り可不可バイト９２０の第１ビット９２１は、クラスタ２内のセクタＤ１に対応する。第２ビット９２２は、セクタＤ２に対応する。第３ビット９２３は、セクタＤ３（９０５）に対応する。第４ビット９２４は、セクタＤ４に対応する。第５ビット９２５は、セクタＤ５に対応する。第６ビット９２６は、セクタＤ６に対応する。第７ビット９２７は、セクタＤ７に対応する。第８ビット９２８は、セクタＤ８に対応する。値が０のビットは対応するセクタが読取り可であることを示し、一方、（セクタ９０５の場合のように）値が１のビットは対応するセクタが読取り不可である（または消去されている）ことを示す。
【００５０】
図６は、図４のＣ４レベルのパリティ・クラスタ保護を生成するための符号化方法（すなわち、コードまたはアルゴリズム）９５０を示すプロセス・フロー・チャートである。方法９５０は、ステップ９５２で、クラスタ・ブロック９００内の１つまたは複数のセクタの部分または全体の消去など、１つまたは複数の読取り不可または消去されたセクタによって開始される。
【００５１】
ステップ９５４で、方法９５０は、読取り不可または消去されたセクタ、すなわち９０５（図４）を、パリティ・クラスタＣ４内の対応するパリティ・セクタ、すなわち９１０で置換する。方法９５０は次に、読取り不可または消去されたセクタ９０５を含むクラスタ（すなわち、クラスタ２）のＣ３チェック９１５を再計算する。
【００５２】
ステップ９６２で、方法９５０は、パリティ・クラスタＣ４を含むすべてのクラスタ１ないしＮのＣ３チェックについて排他的論理和（ＸＯＲ）演算を実施する。次にステップ９６４で、ステップ９６２で計算されたＣ３チェックのＸＯＲによる和が０に等しいかどうかチェックする。
【００５３】
ステップ９６４で、Ｃ３チェックのＸＯＲによる和が０に等しいと判断された場合、方法９５０はステップ９６６に進み、読取り不可または消去されたセクタ９０５を対応するパリティ・セクタ９１０で置換する。次にステップ９６７で、パリティ・セクタ９１０がホスト１８（図１）に返される。
【００５４】
反対に、Ｃ３チェックのＸＯＲによる和が０に等しくないと判断された場合、方法９５０はステップ９６８で誤訂正を宣言（proclaim）し、読取り不可または消去されたセクタ９０５を対応するパリティ・セクタ９１０で置換しない。ステップ９６９で、エラー・メッセージがホスト１８に返される。このエラー・メッセージは本発明の特徴であって、例えば、管理者に不正または読取り不可セクタ９０５を必要に応じて手動で訂正する機会を提供する。読取り不可または消去されたセクタ９０５を対応するパリティ・セクタ９１０で置換しないようにすることで、そうでなければ長時間にわたって未検出となりかねないエラー伝播を防ぐこともできる。
【００５５】
次に図７に移ると、本発明の好ましい方法による、スクラブ（scrub）更新方法９８０を説明するプロセス・フロー・チャートが示されている。スクラブ更新方法９８０は、好ましくは、ドライブのアイドル時間中に実施される。したがって、Ｃ１チェックがオンザフライに書き込まれるのに対して、Ｃ２、Ｃ３、Ｃ４チェックは、スクラブ更新方法９８０によって、計算されチェックされる。
【００５６】
スクラブ更新方法９８０は、ステップ９８２で第１のスクラブ・トラックを選択することにより開始され、次にステップ９８４で、トラックのスクラブを試みる。次に方法９８０は、ステップ９８６でこのトラックを読み取り、ＥＣＣグループ、すなわち、Ｃ２グループ、Ｃ３グループ、Ｃ４グループをチェックする。
【００５７】
方法９８０はステップ９８８で、ＥＣＣグループが整合しているかどうか、すなわち、これらのグループそれぞれのＸＯＲによる和が０に等しいかどうか検査する。等しければ、方法９８０は判断ステップ９９０に進み、スクラブ・トラックが他にも存在しているかどうか調べる。
【００５８】
ステップ９９０で、他にもスクラブ・トラックが存在していることが分かった場合、方法９８０はステップ９９２に進み、次のスクラブ・トラックを選択し、上述したように、ステップ９８４、９８６、９８８を繰り返す。ステップ９９０で、他のスクラブ・トラックが見つからなかった場合、方法９８０はステップ９９９で終了する。
【００５９】
ステップ９８８に戻ると、ＥＣＣグループが整合していないとわかった場合、方法９８０はステップ９９４に進み、Ｃ２、Ｃ３、およびＣ４チェック・グループを再計算し、次にステップ９９６で、再計算されたＥＣＣグループの整合性を評価する。
【００６０】
判断ステップ９９８で、再計算されたＥＣＣグループの整合性が検証されなかった場合、方法９８０は、上述したように、ステップ９９４および９９６を繰り返す。一方、再計算されたＥＣＣグループの整合性が検証された場合、方法９８０はステップ９９９で終了する。
【００６１】
説明した本発明の具体的な実施形態は、本発明の原理のある種の適用例を説明したものにすぎないことを理解されたい。本発明の主旨および範囲から逸脱することなく、本明細書に記載のシステムおよび関連方法に様々な変更を施すことができる。例示のため、セクタに関して本発明を説明したが、本発明が任意のデータ・セットまたは関連性のあるデータのセットにも同様に適用可能であることは明らかであろう。
【００６２】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６３】
（１）パリティ・セクタ訂正による誤訂正を防止する方法であって、
マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成するステップと、
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップと、
誤訂正が検出された場合、どの読取り不可または消去されたセクタも対応するパリティ・セクタで置換されないようにするステップと、
誤訂正が検出されなかった場合、前記読取り不可または消去されたセクタを対応するパリティ・セクタで置換するステップとを含む方法。
（２）前記マルチレベルの誤り訂正符号に従ってクラスタ・レベルのチェック・バイトを生成するステップをさらに含む、上記（１）に記載の方法。
（３）前記クラスタ・レベルのチェック・バイトの少なくともいくつかを使用して、クラスタ・レベルにおける、パリティ・セクタ訂正による誤訂正の発生を判断するステップと、
誤訂正が発生したと判断された場合、エラー・メッセージを返すステップとをさらに含む、上記（２）に記載の方法。
（４）セクタ・レベルのチェック・バイトを生成するステップが、クラスタ内の各セクタを誤訂正から保護するステップと、前記クラスタ内で誤訂正のクロス・チェックを行うステップとを含む、上記（１）に記載の方法。
（５）前記マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成するステップが、４レベル・チェック、すなわちＣ１、Ｃ２、Ｃ３、Ｃ４チェックを生成するステップを含む、上記（２）に記載の方法。
（６）前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップが、クラスタ・レベルでＣ３チェックを再計算するステップを含む、上記（５）に記載の方法。
（７）前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップが、クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックするステップをさらに含む、上記（６）に記載の方法。
（８）クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックするステップが、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての和を計算するステップを含む、上記（７）に記載の方法。
（９）クラスタ・ブロック・レベルで前記Ｃ３チェックすべての前記和を計算するステップが、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての排他的論理和演算を実施するステップを含む、上記（８）に記載の方法。
（１０）クラスタ・ブロック・レベルで計算された前記Ｃ３チェックすべての前記和が０ではない場合に、誤訂正が検出される、上記（９）に記載の方法。
（１１）クラスタ・ブロック・レベルで計算された前記Ｃ３チェックすべての前記和が０である場合に、誤訂正が検出されない、上記（１０）に記載の方法。
（１２）クラスタ内のセクタの読取り可不可状態を表す、前記セクタ用の読取り可不可バイトを計算するステップをさらに含む、上記（２）に記載の方法。
（１３）前記読取り可不可バイトが仮想的なものである、上記（１２）に記載の方法。
（１４）前記読取り可不可バイトを前記マルチレベルの誤り訂正符号の指定されたレベルに符号化するステップを含む、上記（１３）に記載の方法。
（１５）クラスタ・グループ内のクラスタの読取り可不可状態を表す、前記クラスタ用の読取り可不可バイトを計算するステップをさら含む、上記（２）に記載の方法。
（１６）スクラブ更新操作を用いて、前記セクタ・レベルのチェック・バイトを生成し、前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するステップをさらに含む、上記（５）に記載の方法。
（１７）前記スクラブ更新操作が、アイドル時間中に実施される、上記（１６）に記載の方法。
（１８）前記スクラブ更新操作を用いるステップが、前記アイドル時間中に前記レベル・チェックの少なくともいくつかを計算するステップを含む、上記（１７）に記載の方法。
（１９）前記アイドル時間中に前記レベル・チェックの少なくともいくつかを計算するステップが、前記アイドル時間中に前記Ｃ２、Ｃ３、Ｃ４チェックを計算するステップを含む、上記（１８）に記載の方法。
（２０）前記Ｃ１チェックをオンザフライに（on-the-fly）計算するステップをさらに含む、上記（１９）に記載の方法。
（２１）パリティ・セクタ訂正による誤訂正を防ぐことのできる記憶装置であって、
マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成する手段と、
前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段とを含み、
前記判断手段が誤訂正を検出した場合、前記判断手段が、どの読取り不可または消去されたセクタも対応するパリティ・セクタで置換させず、
前記判断手段が誤訂正を検出しなかった場合、前記判断手段が、前記読取り不可または消去されたセクタを対応するパリティ・セクタで置換する記憶装置。
（２２）前記マルチレベルの誤り訂正符号によってクラスタ・レベルのチェック・バイトを生成する手段をさらに含む、上記（２１）に記載の記憶装置。
（２３）前記クラスタ・レベルのチェック・バイトの少なくともいくつかを使用して、クラスタ・レベルにおける、パリティ・セクタ訂正による誤訂正の発生を判断する手段をさらに含む、上記（２２）に記載の記憶装置。
（２４）セクタ・レベルのチェック・バイトを生成する手段が、クラスタ内の各セクタを誤訂正から保護し、前記クラスタ内で誤訂正のクロス・チェックを行う、上記（２１）に記載の記憶装置。
（２５）前記マルチレベルの誤り訂正符号によってセクタ・レベルのチェック・バイトを生成する手段が、４レベル・チェック、すなわちＣ１、Ｃ２、Ｃ３、Ｃ４チェックを生成する、上記（２２）に記載の記憶装置。
（２６）前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段が、クラスタ・レベルでＣ３チェックを再計算する、上記（２５）に記載の記憶装置。
（２７）前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断する手段が、クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をさらにチェックする、上記（２６）に記載の記憶装置。
（２８）クラスタ・レベルで再計算された前記Ｃ３チェックの整合性をチェックする手段が、クラスタ・ブロック・レベルで前記Ｃ３チェックすべての和を計算する、上記（２７）に記載の記憶装置。
（２９）クラスタ内のセクタの読取り可不可状態を表す、前記セクタ用の仮想読取り可不可バイトを計算する手段をさら含む、上記（２２）に記載の記憶装置。
（３０）前記セクタ・レベルのチェック・バイトを生成し、前記セクタ・レベルのチェック・バイトの少なくともいくつかを使用して、パリティ・セクタ訂正による誤訂正の発生を判断するスクラブ更新操作をさらに含む、上記（２５）に記載の記憶装置。
（３１）少なくとも１つのパリティ・ブロックを有するデータ・セットを、前記データ・セット内の不整合なパリティによる誤訂正から保護する方法であって、
前記データ・セット内の情報からクロス・チェックを生成するステップと、
前記クロス・チェックを前記データ・セットと関連付けて保存するステップと、
消去イベントの発生時に、前記パリティ・ブロックから消失データを再構成するステップと、
前記再構成されたデータを含む前記データ・セットから新しいクロス・チェックを生成するステップと、
前記新しいクロス・チェックと前記保存されたクロス・チェックとを比較するステップと、
前記比較された再構成クロス・チェックと前記新しいクロス・チェックとが整合している場合、前記再構成データが有効であると判断し、前記再構成データの使用を許可するステップと、
前記比較された再構成クロス・チェックと前記新しいクロス・チェックとが整合していない場合、前記再構成データが無効であると判断し、エラーを通知するステップを含む方法。
（３２）前記クロス・チェックを生成するステップが、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成するステップを含む、上記（３１）に記載の方法。
（３３）前記データ・セットが複数のパリティ・セクタを含む、上記（３１）に記載の方法。
（３４）前記クロス・チェックを生成するステップが、前記データ・セットのサブセットに対するパリティ・セクタを生成するステップを含む、上記（３３）に記載の方法。
（３５）前記クロス・チェックを生成するステップが、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックを生成するステップをさらに含む、上記（３４）に記載の方法。
（３６）データ・セットを含むデータ記憶装置であって、前記データ・セットが少なくとも１つのパリティ・ブロックで保護されるとともに、前記データ・セットと関連付けて保存されたクロス・チェックによっても保護され、
前記データ・セットから前記パリティ・ブロックを生成する手段と、
前記データ・セットからクロス・チェックを生成する手段と、
消去イベントによって前記パリティ・ブロックから消失したデータを再構成する手段と、
前記再構成されたデータ・セットから新しいクロス・チェックを生成する手段と、
前記新しいクロス・チェックと保存されたクロス・チェックとを比較する手段と、
前記比較された新しいクロス・チェックと前記保存されたクロス・チェックとが整合していない場合、エラーを通知する手段を含むデータ記憶装置。
（３７）前記クロス・チェックを生成する手段が、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成する、上記（３６）に記載のデータ記憶装置。
（３８）前記データ・セットが複数のパリティ・セクタを含む、上記（３６）に記載のデータ記憶装置。
（３９）前記クロス・チェックを生成する手段が、前記データ・セットのサブセットに対するパリティ・セクタを生成する、上記（３８）に記載のデータ記憶装置。
（４０）前記クロス・チェックを生成する手段が、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックをさらに生成する、上記（３９）に記載のデータ記憶装置。
（４１）命令コードを有し、データ・セットを含み、前記データ・セットが少なくとも１つのパリティ・ブロックで保護されるとともに、前記データ・セットに関連付けて保存されたクロス・チェックによっても保護される、誤り訂正符号データ構造であって、
前記データ・セットから前記パリティ・ブロックを生成するための、第１組の命令コードと、
前記データ・セットからクロス・チェックを生成するための、第２組の命令コードと、
消去イベントによって前記パリティ・ブロックから消失したデータを再構成するための、第３組の命令コードとを含み、
前記第３組の命令コードが、前記再構成されたデータ・セットから新しいクロス・チェックをさらに生成し、
前記第３組の命令コードが、前記新しいクロス・チェックを保存されたクロス・チェックと比較し、前記比較された新しいクロス・チェックと保存されたクロス・チェックとが整合していない場合、エラーを通知する誤り訂正符号データ構造。
（４２）前記第２組の命令コードが、マルチレベルの誤り訂正符号によって前記クロス・チェックを生成する、上記（４１）に記載の誤り訂正符号データ構造。
（４３）前記データ・セットが複数のパリティ・セクタを含む、上記（４１）に記載の誤り訂正符号データ構造。
（４４）前記第２組の命令コードが、前記データ・セットのサブセットに対するパリティ・セクタを生成する、上記（４３）に記載の誤り訂正符号データ構造。
（４５）前記第２組の命令コードが、前記データ・セットの他のサブセットが複数の一意的なパリティ・データのサブセットからのデータを含むように、前記他のサブセットから複数のクロス・チェックをさらに生成する、上記（４４）に記載の誤り訂正符号データ構造。
【図面の簡単な説明】
【００６４】
【図１】本発明による、線形誤り訂正符号（ＥＣＣ）符号語を形成し記録するためのオンザフライ（ＯＴＦ）計算およびチェック・バイトの付加を行い、ディスク・トラックから読み取った線形ＥＣＣ符号語の検出および訂正を行うための、ハードディスク・ドライブ（ＨＤＤ）の書込みパスおよび読取りパスを示す部分的なデータ・フロー図である。
【図２】本発明の実施形態による、セクタ数Ｎ＝８、レベル数ｎ＝３を例とする、ＭＬ−ＩＳＦ−ＥＣＣ符号化処理のための方法および装置を示す図である。
【図３】本発明の実施形態による、セクタ数Ｎ＝８、レベル数ｎ＝３を例とする、ＭＬ−ＩＳＦ−ＥＣＣ符号化処理のための方法および装置を示す図である。
【図４】複数のセクタ・クラスタと誤訂正に対する追加の保護を提供するための追加のＣ４レベル・パリティ・クラスタとを含む、本発明の好ましい符号化方法による例示的なクラスタ・ブロックの図である。
【図５】Ｃ３チェック・レベルに符号化される仮想的な読取り可不可バイトの例を示す図である。
【図６】図４のＣ４レベル・パリティ・クラスタ保護を生成するための符号化方法を示すプロセス・フロー・チャートである。
【図７】本発明の好ましい方法によるスクラブ更新方法を説明するプロセス・フロー・チャートである。
【符号の説明】
【００６５】
１  磁気ディスク
３  変換器／ヘッド
５  アクセス・アーム
９  信号抽出ユニット
１１  フォーマッティング・ユニット
１３  ＥＣＣ読取りプロセッサ
１５  バッファ
１７  ＥＣＣ書込みプロセッサ
１９  書込みパス信号整形ユニット
【図１】
2004171751.tif 000008
【図２】
2004171751.tif 000009
【図３】
2004171751.tif 000010
【図４】
2004171751.tif 000011
【図５】
2004171751.tif 000012
【図６】
2004171751.tif 000013
【図７】
2004171751.tif 000014