(57)【要約】【課題】  誤り訂正符号を用いて、記憶媒体に記憶されたデータ内の誤りを訂正する。【解決手段】  記憶媒体に記憶されたデータは、記憶媒体から複数のデータブロックと複数の誤り訂正符号（ＥＣＣ）とを検索することによって訂正される。１つのＥＣＣは、多数のデータブロックからのデータを有する１つのデータセットに対応しており、ＥＣＣはデータブロックとＥＣＣとを記憶媒体に記憶させる前に生成される。記憶媒体からデータブロックとＥＣＣとを検索した後で、データセットは、データセット内のデータとデータセットとに対応するＥＣＣに基づいて、誤りを有するとして識別され、誤りは、記憶媒体から検索されたデータセット内のデータが、データが元々記憶媒体に記憶されたときのデータセット内のデータとは異なることを示す。誤りを有するとして識別されたデータセット内のデータは、データセットに対応するＥＣＣを用いて訂正される。【選択図】        図５
2004281037.tif 000002
【特許請求の範囲】
【請求項１】
記憶媒体に記憶されたデータを訂正する方法であって、
記憶媒体から複数のデータブロックを検索するステップと、
記憶媒体から複数の誤り訂正符号（ＥＣＣ）を検索するステップとを含み、
１ＥＣＣは、多数のデータブロックからのデータを有する１データセットに対応しており、
ＥＣＣは、データブロックおよびＥＣＣを記憶媒体に記憶させる前に生成されたものであり、前記方法はさらに、
データセットを、データセット内のデータおよびデータセットに対応するＥＣＣに基づいて、誤りを有するとして識別するステップを含み、
誤りは、記憶媒体から検索されたデータセット内のデータが、データが元々記憶媒体に記憶されたときのデータセット内のデータとは異なることを示しており、前記方法はさらに、
誤りを有するとして識別されたデータセット内のデータを、データセットに対応するＥＣＣを用いて訂正するステップを含む、記憶媒体に記憶されたデータを訂正する方法。
【請求項２】
記憶媒体から複数のチェックサムを検索するステップをさらに含み、
１チェックサムは１データブロックに対応しており、前記方法はさらに、
記憶媒体から検索されたデータブロックを、データブロックに対応するチェックサムを用いて、誤りを有するとして識別するステップを含み、
データセット内で訂正されたデータは、誤りを有するとして識別されたデータブロックからのものである、請求項１に記載の方法。
【請求項３】
データセットを識別するステップは、
データセット内のデータおよびデータセットに対応するＥＣＣの排他的論理和（ＸＯＲ）演算を行なうステップと、
ＸＯＲ演算がゼロでない結果を生み出す場合、データセットを、誤りを有するとして識別するステップとを含む、請求項１に記載の方法。
【請求項４】
データセットを識別するステップは、
データセット用に新しいＥＣＣを生成するステップを含み、新しいＥＣＣを生成するために使用されるデータセット内のデータは記憶媒体から検索されたものであり、前記ステップはさらに、
新しいＥＣＣを、データセットに対応する、記憶媒体から検索されたＥＣＣと比較するステップと、
新しいＥＣＣと検索されたＥＣＣとが異なる場合、データセットを、誤りを有するとして識別するステップとを含む、請求項１に記載の方法。
【請求項５】
記憶媒体から検索された複数のデータブロックは、行および列を有する第１の論理データアレイを形成しており、１行は１データブロックに対応し、１列は１データセットに対応している、請求項１に記載の方法。
【請求項６】
第１の論理データアレイから第２の論理データアレイを形成するステップをさらに含み、第２の論理データアレイは、誤りを有するとして識別されたデータセットに対応する、第１の論理データアレイからの列のみを含む、請求項５に記載の方法。
【請求項７】
第２の論理データアレイはチェックサムの列を含み、１チェックサムは１データブロックに対応しており、データセット内で訂正されたデータは、データブロックに対応するチェックサムによって誤りを有するとして識別されたデータブロックからのものである、請
求項６に記載の方法。
【請求項８】
ＥＣＣはリード−ソロモン符号である、請求項１に記載の方法。
【請求項９】
１データセットは、多数のデータブロックのバイトサイズの一部に対応している、請求項１に記載の方法。
【請求項１０】
記憶媒体に記憶されたデータを訂正するシステムであって、
記憶媒体から検索された複数のデータブロックと、記憶媒体から検索された複数の誤り訂正符号（ＥＣＣ）とを含むデータバッファを含み、
１ＥＣＣは、多数のデータブロックからのデータを有する１データセットに対応しており、
ＥＣＣは、データブロックおよびＥＣＣを記憶媒体に記憶させる前に生成されたものであり、前記システムはさらに、
データセットを、データセット内のデータおよびデータセットに対応するＥＣＣに基づいて、誤りを有するとして識別するよう構成されたプロセッサを含み、
誤りは、記憶媒体から検索されたデータセット内のデータが、データが元々記憶媒体に記憶されたときのデータセット内のデータとは異なることを示しており、前記プロセッサはさらに、
誤りを有するとして識別されたデータセット内のデータを、データセットに対応するＥＣＣを用いて訂正するよう構成されている、記憶媒体に記憶されたデータを訂正するシステム。
【請求項１１】
データバッファは、記憶媒体から検索された複数のチェックサムをさらに含み、１チェックサムは１データブロックに対応しており、プロセッサは、記憶媒体から検索されたデータブロックを、データブロックに対応するチェックサムを用いて、誤りを有するとして識別するようさらに構成されており、データセット内で訂正されたデータは、誤りを有するとして識別されたデータブロックからのものである、請求項１０に記載のシステム。
【請求項１２】
データセットは、
データセット内のデータおよびデータセットに対応するＥＣＣの排他的論理和（ＸＯＲ）演算を行なうステップと、
ＸＯＲ演算がゼロでない結果を生み出す場合、データセットを、誤りを有するとして識別するステップとによって識別される、請求項１０に記載のシステム。
【請求項１３】
データセットは、
データセット用に新しいＥＣＣを生成するステップ（新しいＥＣＣを生成するために使用されるデータセット内のデータは、記憶媒体から検索されたものである）と、
新しいＥＣＣを、データセットに対応する、記憶媒体から検索されたＥＣＣと比較するステップと、
新しいＥＣＣと検索されたＥＣＣとが異なる場合、データセットを、誤りを有するとして識別するステップとによって識別される、請求項１０に記載のシステム。
【請求項１４】
記憶媒体から検索された複数のデータブロックは、行および列を有する第１の論理データアレイを形成しており、１行は１データブロックに対応し、１列は１データセットに対応している、請求項１０に記載のシステム。
【請求項１５】
第１の論理データアレイから形成された第２の論理データアレイをさらに含み、第２の論理データアレイは、誤りを有するとして識別されたデータセットに対応する、第１の論理データアレイからの列のみを含む、請求項１４に記載のシステム。
【請求項１６】
第２の論理データアレイはチェックサムの列を含み、１チェックサムは１データブロックに対応しており、データセット内で訂正されたデータは、データブロックに対応するチェックサムによって誤りを有するとして識別されたデータブロックからのものである、請求項１５に記載のシステム。
【請求項１７】
ＥＣＣはリード−ソロモン符号である、請求項１０に記載のシステム。
【請求項１８】
１データセットは、多数のデータブロックのバイトサイズの一部に対応している、請求項１０に記載のシステム。
【請求項１９】
記憶媒体に記憶されたデータをコンピュータに訂正させるためのコンピュータ実行可能命令を含むコンピュータ可読記憶媒体であって、
記憶媒体から複数のデータブロックを検索するステップのための命令と、
記憶媒体から複数の誤り訂正符号（ＥＣＣ）を検索するステップのための命令とを含み、
１ＥＣＣは、多数のデータブロックからのデータを有する１データセットに対応しており、
ＥＣＣは、データブロックおよびＥＣＣを記憶媒体に記憶させる前に生成されたものであり、前記コンピュータ可読記憶媒体はさらに、
データセットを、データセット内のデータおよびデータセットに対応するＥＣＣに基づいて、誤りを有するとして識別するステップのための命令を含み、
誤りは、記憶媒体から検索されたデータセット内のデータが、データが元々記憶媒体に記憶されたときのデータセット内のデータとは異なることを示しており、前記コンピュータ可読記憶媒体はさらに、
誤りを有するとして識別されたデータセット内のデータを、データセットに対応するＥＣＣを用いて訂正するステップのための命令を含む、コンピュータ可読記憶媒体。
【請求項２０】
記憶媒体から複数のチェックサムを検索するステップのための命令をさらに含み、
１チェックサムは１データブロックに対応しており、前記コンピュータ可読媒体はさらに、
記憶媒体から検索されたデータブロックを、データブロックに対応するチェックサムを用いて、誤りを有するとして識別するステップのための命令を含み、
データセット内で訂正されたデータは、誤りを有するとして識別されたデータブロックからのものである、請求項１９に記載のコンピュータ可読媒体。
【請求項２１】
データセットを識別するステップは、
データセット内のデータおよびデータセットに対応するＥＣＣの排他的論理和（ＸＯＲ）演算を行なうステップと、
ＸＯＲ演算がゼロでない結果を生み出す場合、データセットを、誤りを有するとして識別するステップとを含む、請求項１９に記載のコンピュータ可読媒体。
【請求項２２】
データセットを識別するステップは、
データセット用に新しいＥＣＣを生成するステップを含み、新しいＥＣＣを生成するために使用されるデータセット内のデータは記憶媒体から検索されたものであり、前記ステップはさらに、
新しいＥＣＣを、データセットに対応する、記憶媒体から検索されたＥＣＣと比較するステップと、
新しいＥＣＣと検索されたＥＣＣとが異なる場合、データセットを、誤りを有するとして識別するステップとを含む、請求項１９に記載のコンピュータ可読媒体。
【請求項２３】
記憶媒体から検索された複数のデータブロックは、行および列を有する第１の論理データアレイを形成しており、１行は１データブロックに対応し、１列は１データセットに対応している、請求項１９に記載のコンピュータ可読媒体。
【請求項２４】
第１の論理データアレイから第２の論理データアレイを形成するステップのための命令をさらに含み、第２の論理データアレイは、誤りを有するとして識別されたデータセットに対応する、第１の論理データアレイからの列のみを含む、請求項２３に記載のコンピュータ可読媒体。
【請求項２５】
第２の論理データアレイはチェックサムの列を含み、１チェックサムは１データブロックに対応しており、データセット内で訂正されたデータは、データブロックに対応するチェックサムによって誤りを有するとして識別されたデータブロックからのものである、請求項２４に記載のコンピュータ可読媒体。
【請求項２６】
ＥＣＣはリード−ソロモン符号である、請求項１９に記載のコンピュータ可読媒体。
【請求項２７】
１データセットは、多数のデータブロックのバイトサイズの一部に対応している、請求項１９に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
１．発明の分野
この出願は一般に、記憶媒体にデータを記憶させることに関し、より特定的には、記憶媒体に記憶されたデータにおける誤りを訂正するために誤り訂正符号を使用することに関する。
【背景技術】
【０００２】
２．関連技術
データは、記憶装置内の記憶媒体へデータを書込むことによって、記憶装置に記憶される。記憶されたデータは後に、記憶媒体からデータを読出すことによって、記憶装置から検索可能である。しかしながら、多くの理由により、記憶装置から検索されたデータに誤りが存在する、つまり、記憶されたデータが検索できないかまたは記憶媒体に元々記憶されたデータとは異なる場合がある。たとえば、記憶媒体上の記憶されたデータの一部が時を経て劣化し、記憶されたデータのその部分を後で適正に読出すことができなくなる場合がある。
【０００３】
そのような誤りを訂正する従来の手法では、誤り訂正符号（ＥＣＣ）がデータ用に生成され、データとともに記憶媒体に記憶される。記憶されたデータが後に検索されて誤りが検出されると、ＥＣＣを用いて検索されたデータを訂正することができる。
【０００４】
ＥＣＣを用いるあるアプローチでは、データがアレイとなって構成され、ＥＣＣがそのデータ用にそのアレイの２つの次元において（たとえばアレイの行および列に沿って）生成される。これらは通常、２次元ＥＣＣと呼ばれる。このアプローチの１つの欠点は、アレイのサイズが増大するにつれ、ＥＣＣを生成するため、および検索されたデータを訂正するために必要な時間の量も増大する、ということである。
【０００５】
ＥＣＣを用いる別のアプローチでは、ＥＣＣはデータブロック用に生成され、記憶媒体に記憶される際にデータブロック内に分散される。データブロック内に分散されたＥＣＣの位置を記憶する必要があるため、このアプローチの１つの欠点は、それがＥＣＣ専用のオーバーヘッドの量を増大させることであり、それは記憶装置の総記憶容量を減少させる場合がある。
【０００６】
加えて、ＥＣＣを用いて誤りを訂正するための従来の手法では、記憶媒体にデータを記憶させるために使用可能なデータブロックのサイズは、予想される誤りのサイズによって制限され得る。より特定的には、データブロックは通常、予想される誤りの平均サイズに対応するようサイズ変更される。このため、小さいサイズの誤りが予想される場合には小さいサイズのデータブロックが使用され、大きいサイズの誤りが予想される場合には大きいサイズのデータブロックが使用される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、多くの理由により、予想される誤りの平均サイズに比例していないデータブロックサイズを有することが望ましい場合がある。たとえば、大量のデータが通常、記憶媒体に記憶され、記憶媒体から検索される場合には、大きいデータブロックが、アクセス時間およびオーバーヘッドを減らすために、ある意味では望ましい。しかしながら、誤りの平均サイズがデータブロックのサイズに対して小さい場合には、誤り訂正は比較的
非効率的になる。なぜなら、小さい誤りに対してもデータブロック全体を訂正する必要があるためである。
【課題を解決するための手段】
【０００８】
概要
例示的な一実施例では、記憶媒体に記憶されたデータは、記憶媒体から複数のデータブロックおよび複数の誤り訂正符号（ＥＣＣ）を検索することによって訂正される。１つのＥＣＣは、多数のデータブロックからのデータを有する１つのデータセットに対応しており、ＥＣＣは、データブロックおよびＥＣＣを記憶媒体に記憶させる前に生成される。記憶媒体からデータブロックおよびＥＣＣを検索した後で、データセットは、データセット内のデータおよびデータセットに対応するＥＣＣに基づいて、誤りを有するとして識別され、誤りは、記憶媒体から検索されたデータセット内のデータが、データが元々記憶媒体に記憶されたときのデータセット内のデータとは異なることを示す。誤りを有するとして識別されたデータセット内のデータは、データセットに対応するＥＣＣを用いて訂正される。
【発明を実施するための最良の形態】
【０００９】
詳細な説明
以下の説明は多数の特定の構成、パラメータなどを述べている。しかしながら、そのような説明はこの発明の範囲に対する限定としては意図されておらず、その代わり、例示的な実施例をより良く説明するために提供されていることが認識されるべきである。
【００１０】
図１を参照すると、ホスト端末１０２が記憶装置１０４に接続されて図示されている。ホストコンピュータ１０２は、パーソナルコンピュータ、ワークステーション、サーバなどの任意の種類のコンピュータであり得る。記憶装置１０４は、テープドライブ、ハードドライブなどの任意の種類の記憶ドライブであり得る。ホスト端末１０２は任意の数の記憶装置１０４に接続可能であること、および、任意の数のホスト端末１０２が１つ以上の記憶装置１０４に接続可能であることが認識されるべきである。
【００１１】
図１を引続き参照すると、例示的な一実施例では、記憶装置１０４は、記憶装置１０４に記憶されたデータ内の誤りを検出および訂正するよう構成されている。より具体的には、記憶装置１０４に記憶されたデータが検索される際、記憶装置１０４は、サイクリック・リダンダンシー・チェック（ＣＲＣ）符号などの誤り訂正符号（ＥＣＣ）およびチェックサムを用いて、検索されたデータが元々記憶装置１０４に記憶されたデータと異なるかどうか、または記憶されたデータが検索不可能かどうかといった検索されたデータ内の誤りを検出および訂正するよう構成されている。
【００１２】
図１に示す実施例では、記憶装置１０４は、記憶媒体１０６、チャネルおよび読出／書込ヘッド１０８、プロセッサ１１０、および誤り検出／訂正ユニット１１２を含む。記憶装置１０４では、データは記憶媒体１０６に記憶される。読出／書込ヘッド１０８は、記憶媒体１０６からデータを読出し、および／または記憶媒体１０６へデータを書込む。プロセッサ１１０は、チャネルおよび読出／書込ヘッド１０８の動作を含め、記憶装置１０４の動作を制御する。以下により詳細に説明するように、誤り検出／訂正ユニット１１２は、記憶媒体１０６に記憶されたデータ内の誤りを検出および訂正する。
【００１３】
この例示的な実施例では、誤り検出／訂正ユニット１１２は、データバッファ１１４、ＥＣＣエンコーダ／デコーダ１１６、およびＣＲＣエンコーダ／デコーダ１１８を含む。データが記憶媒体１０６に記憶される際、データはホスト端末１０２から受信されてデータバッファ１１４へ書込まれる。ＥＣＣエンコーダ／デコーダ１１６およびＣＲＣエンコーダ／デコーダ１１８は、データバッファ１１４内のデータ用にＥＣＣおよびＣＲＣ符号
を生成する。読出／書込ヘッド１０８は次に、データと生成されたＥＣＣおよびＣＲＣ符号とを、記憶媒体１０６へ書込む。
【００１４】
データが記憶媒体１０６から読出される際、読出／書込ヘッド１０８は、データとＥＣＣおよびＣＲＣ符号とを、記憶媒体１０６からデータバッファ１１４へ読出す。以下により詳細に説明するように、記憶媒体１０６から読出されたデータ内のどの誤りも、ＥＣＣおよびＣＲＣ符号を用いて検出および訂正される。データは次にホスト端末１０２へ転送されてもよい。
【００１５】
例示的な一実施例では、データは、ホスト端末１０２と記憶装置１０４との間を、キャッシュに記憶されるデータレコードの状態で転送される。データレコードは、２キロバイト、４キロバイト、６キロバイトなどの予め定められた長さのデータブロックに分割される。しかしながら、さまざまな長さのデータブロックが使用されてもよいことが認識されるべきである。
【００１６】
この例示的な実施例では、データブロックが記憶媒体１０６から検索された後で、検索されたデータブロック内の誤りを訂正するためにＥＣＣを使用する。より具体的には、データブロックを記憶媒体１０６に記憶させる前に、多数のデータブロックからのデータを有するデータセット用にＥＣＣが生成され、データブロックとともに記憶媒体１０６に記憶される。以下により詳細に説明するように、データブロックが後に検索される際、誤りを有するデータセットが、データセット内のデータおよびデータセットに対応するＥＣＣに基づいて識別可能であり、検索されたデータセット内の誤りは、検索されたデータセット内のデータが、データが元々記憶媒体１０６に記憶されたときのデータセット内のデータとは異なることを示す。誤りを有するとして識別されたデータセット内のデータは次に、データセットに対応するＥＣＣを用いて訂正される。
【００１７】
加えて、この例示的な実施例では、検索されたデータブロック内の誤りを検出するためにＣＲＣ符号を使用し、検索されたデータブロック内の誤りは、検索されたデータブロック内のデータが、データが元々記憶媒体１０６に記憶されたときのデータブロック内のデータとは異なることを示す。より具体的には、データブロックを記憶媒体１０６に記憶させる前に、そのデータブロック用にＣＲＣ符号が生成され、データブロックとともに記憶媒体１０６に記憶される。データブロックが後に検索される際、検索されたデータブロック用に新しいＣＲＣ符号が生成される。検索されたデータブロックを記憶媒体１０６に記憶させる前に、新しいＣＲＣ符号は次に、検索されたデータブロックに対応し、検索されたデータブロック用に元々生成された、記憶媒体１０６から検索されたＣＲＣ符号と比較される。新しいＣＲＣ符号と検索されたＣＲＣ符号とが異なる場合には、そのデータブロックについて誤りが検出される。
【００１８】
例示的な一実施例では、１組のデータブロック、１組のＥＣＣ、および１組のＣＲＣ符号は、「エンティティ」と呼ばれるグループとして、ともに読出および書込可能である。図２を参照すると、１６のデータブロック、４ブロックのＥＣＣ、および２０のＣＲＣ符号を有するエンティティの論理データアレイ２０２が図示されている。しかしながら、エンティティはさまざまな数のデータブロック、ＥＣＣ、およびＣＲＣ符号を含み得ることが認識されるべきである。
【００１９】
図２に示すように、データアレイ２０２は行２０４および列２０６を含む。より具体的には、データアレイ２０２は、データ行２０８、ＥＣＣ行２１０、データ列２１２、およびＣＲＣ列２１４を含む。この例示的な実施例では、１データ行２０８は１データブロックに対応する。１ＥＣＣ行２１０はＥＣＣの１ブロックに対応する。１データ列２１２は、多数のデータブロックからのデータを有する１データセットに対応する。１ＣＲＣ列２
１４は、データ行２０８およびＥＣＣ行２１０用の１組のＣＲＣ符号に対応する。
【００２０】
例示的な一実施例では、論理データアレイ２０２は、エンティティがデータバッファ１１４（図１）に記憶される形を示す。しかしながら、データアレイ２０２は図２および図３に示す形で物理的に存在する必要はないことが認識されるべきである。データアレイ２０２内のデータ、より特定的にはデータ行２０８およびデータ列２１２によって規定されるデータは、連続している必要がないことも認識されるべきである。その代わり、例示的な一実施例では、ホスト端末１０２（図１）から受信されたデータはインタリーブされている。したがって、データ行２０８およびデータ列２１２によって規定されるデータは、ホスト端末１０２（図１）から受信される別個のファイルの一部に対応可能である。
【００２１】
図２は、データアレイ２０２のデータ行２０８、ＥＣＣ行２１０、データ列２１２、およびＣＲＣ列２１４間の論理的な関係を示している。図３を参照すると、データ行２０８、ＥＣＣ行２１０、データ列２１２、およびＣＲＣ列２１４間の論理的な関係をより明確に示すために、データアレイ２０２の一部がより詳細に示されている。
【００２２】
図３に示すように、ＣＲＣ列２１４の１つのＣＲＣ符号は、データアレイ２０２の１つの行２０４に対応しており、１つの行２０４における誤りを検出するために使用される。たとえば、ＣＲＣ符号Ｃ1は、第１のデータブロックに対応しているデータアレイ２０２の第１のデータ行２０８に対応する。このため、第１のデータ行２０８における誤りを検出するために、記憶媒体１０６（図１）から第１のデータ行２０８を検索した後で、検索された第１のデータ行２０８用に新しいＣＲＣ符号Ｃ1′が生成される。新しいＣＲＣ符号Ｃ1′は次に、検索された第１のデータ行２０８に対応する、記憶媒体１０６（図１）から検索されたＣＲＣ符号（つまりＣＲＣ符号Ｃ1）と比較される。新しいＣＲＣ符号Ｃ1′と検索されたＣＲＣ符号Ｃ1とが異なる場合には、第１のデータ行２０８について誤りが検出される。
【００２３】
図３に同様に示すように、ＥＣＣ行２１０内のＥＣＣは、多数のデータブロックからのデータを有するデータセットに対応するデータ列２１２に対応しており、データ列２１２における誤りを訂正するために使用されてもよい。たとえば、ＥＣＣ  Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1は第１のデータ列２１２に対応しており、第１のデータ列２１２（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）における任意の誤りを訂正するために使用されてもよい。ＥＣＣ  Ｅ1,i、Ｅ2,i、Ｅ3,i、およびＥ4,iは最後のデータ列２１２に対応しており、最後のデータ列２１２（つまりデータＤ1,i、Ｄ2,i、…、Ｄj,i）における任意の誤りを訂正するために使用されてもよい。
【００２４】
この例示的な実施例では、１データ列２１２における１つのセル（つまりデータセル）は、１データブロックの１バイトを表わす。このため、データアレイ２０２の１データ列２１２およびＥＣＣ行２１０内の１つのセル（つまりＥＣＣセル）は、データ行２０８のデータブロックの１バイトに対応している。
【００２５】
たとえば、第１のデータ列２１２およびＥＣＣ  Ｅ1,1は、データ行２０８におけるデータブロックの１番目のバイト（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）に対応する。このため、ＥＣＣ  Ｅ1,1は、第１のデータ列２１２（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）におけるデータセルを訂正するために使用されてもよい。第２のデータ列２１２およびＥＣＣ  Ｅ1,2は、データ行２０８におけるデータブロックの２番目のバイト（つまりデータＤ1,2、Ｄ2,2、…、Ｄj,2）に対応する。このため、ＥＣＣ  Ｅ1,2は、第２のデータ列２１２（つまりデータＤ1,2、Ｄ2,2、…、Ｄj,2）におけるデータセルを訂正するために使用されてもよい。
【００２６】
加えて、この例示的な実施例では、１データ列２１２における単一のデータセルを訂正するためにＥＣＣを使用してもよい。このため、１データ列２１２につき、合計４つのデータセルが、そのデータ列２１２内の４つのＥＣＣセルを使用して訂正可能である。たとえば、ＥＣＣ  Ｅ1,1は、第１のデータ列２１２における１データセル（つまりデータＤ1,1、Ｄ2,1、…、またはＤj,1）を訂正するために使用されてもよい。ＥＣＣ  Ｅ2,1は、第１のデータ列２１２における第２のデータセルを訂正するために使用されてもよい。ＥＣＣ  Ｅ3,1は、第１のデータ列２１２における第３のデータセルを訂正するために使用されてもよい。ＥＣＣ  Ｅ4,1は、第１のデータ列２１２における第４のデータセルを訂正するために使用されてもよい。
【００２７】
この例示的な実施例では、１データ列２１２用のＥＣＣは、そのデータ列２１２内のデータに基づいて生成される。たとえば、ＥＣＣ  Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1は、第１のデータ列２１２（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）に基づいて生成される。上述のように、図１を参照すると、ＥＣＣはＥＣＣエンコーダ１１６によって生成される。また、上述のように、ＥＣＣは最初、ホスト端末１０２から受信されたデータ用に生成される。生成されたＥＣＣおよび受信されたデータは次に、記憶媒体１０６に記憶される。
【００２８】
図３を再度参照すると、例示的な一実施例では、ＥＣＣ行２１０内のＥＣＣは、データ列２１２に基づいて生成されたリード−ソロモン符号である。たとえば、ＥＣＣ  Ｅ1,1は、第１のデータ列２１２（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）に基づいて生成されたリード−ソロモン符号である。リード−ソロモン符号のより詳細な説明については、ここにその全体を引用により援用する、ピーターソンおよびウェルドン（Peterson & Weldon）著「誤り訂正符号（Error Correcting Codes）」、第２版、ＭＩＴプレス、１９７２年を参照されたい。しかしながら、さまざまな種類の誤り訂正符号が使用されてもよいことが認識されるべきである。
【００２９】
この例示的な実施例では、ＥＣＣ  Ｅ2,1、Ｅ3,1、およびＥ4,1も、第１のデータ列２１２（つまりデータＤ1,1、Ｄ2,1、…、Ｄj,1）に基づいて生成されたリード−ソロモン符号である。ＥＣＣ  Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1は同じ組のデータ（つまり第１のデータ列２１２）に基づいて生成されているものの、各ＥＣＣは互いに関して固有のものである。より具体的には、１組のデータに基づいてリード−ソロモン符号を生成する際、その１組のデータの要素の排他的論理和（ＸＯＲ）演算をさまざまな組合せで行なうためにマトリックスが使用される。このため、この例示的な実施例では、ＥＣＣ  Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1は異なるマトリックスを用いて生成される。たとえば、Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1はそれぞれ、第１、第２、第３、および第４のマトリックスを用いて生成される。
【００３０】
上述のように、データアレイ２０２は、行２０４内の誤りを検出するために使用可能なＣＲＣ列２１４を含む。しかしながら、ＣＲＣ列２１４は、誤りが存在する列２０６を示さない。たとえば、ＣＲＣ  Ｃ2を用いて、第２のデータ行２０８内のどこかにある誤りを検出することは可能であるが、その誤りは、第２のデータ行２０８（つまりデータＤ2,1、Ｄ2,2、…、Ｄ2,i）における任意の１つ以上のデータセルに存在する可能性がある。
【００３１】
このため、例示的な一実施例では、ＥＣＣ行２１０内のＥＣＣは、多数のデータブロックからのデータを有する１データセットに対応している１データ列２１２が誤りを有するかどうかを判断するために使用される。より具体的には、リード−ソロモン符号が使用される場合、排他的論理和（ＸＯＲ）演算を含む数学的計算が１データ列内の１つのＥＣＣおよびデータに対して行なわれ、不良の列が判断される。リード−ソロモン符号の一特性に従って、ＥＣＣが計算されたときとデータ列内のデータが同じであるならば、ＸＯＲ演
算の結果は０（ゼロ）となるはずである。このため、ＸＯＲ演算の結果を用いて、データ列が誤りを有するかどうかを判断可能である。
【００３２】
たとえば、データアレイ２０２が、記憶媒体１０６（図１）から検索されたデータ、ＥＣＣ、およびＣＲＣ符号を図示していると仮定する。このため、ＥＣＣ行２１０内のＥＣＣおよびＣＲＣ列２１４内のＣＲＣ符号は、元々ホスト端末１０２（図１）から受信されたデータに基づいて、以前に生成されたものである。上述のように、第１のデータ列２１２に誤りがあるかどうかを判断するために、ＸＯＲ演算がＥＣＣ  Ｅ1,1およびデータＤ1,1、Ｄ2,1、…、またはＤj,1に対して行なわれる。このため、ＥＣＣ  Ｅ1,1が元々生成されたときからデータＤ1,1、Ｄ2,1、…、またはＤj,1が変わっていなかった場合には、ＸＯＲ演算はゼロ結果を生み出すはずである。このため、例示的な一実施例では、１データ列２１２の１ＥＣＣおよびそのデータ列２１２のＸＯＲ演算がゼロ結果を生み出す場合、そのデータ列２１２は誤りを有さないと判断される。ＸＯＲ演算がゼロではない結果を生み出す場合、そのデータ列２１２は誤りを有すると判断される。
【００３３】
別の例示的な実施例では、１データ列２１２に基づいて新しいＥＣＣが生成される。新しく生成されたＥＣＣは次に、検索されたＥＣＣ（つまり、ホスト端末１０２（図１）から受信されたデータから元々生成された、記憶媒体１０６（図１）から検索されたＥＣＣ）と比較される。比較の結果を用いて、そのデータ列２１２が誤りを有するかどうかが判断可能である。
【００３４】
たとえば、ＥＣＣ  Ｅ1,1が第１のデータ列２１２（つまりＤ1,1、Ｄ2,1、…、またはＤj,1）から生成され、ＥＣＣ  Ｅ1,1および第１のデータ列２１２が記憶媒体１０６（図１）に記憶されていると仮定されたい。ここで、ＥＣＣ  Ｅ1,1および第１のデータ列２１２が記憶媒体１０６（図１）から検索されると仮定されたい。検索された第１のデータ列２１２が任意の誤りを有するかどうかを判断するために、検索された第１のデータ列２１２に基づいて、新しいＥＣＣ（つまりＥＣＣ  Ｅ1,1′）が生成される。Ｅ1,1′とＥ1,1とは次に比較される。Ｅ1,1′とＥ1,1とが同じ場合、検索された第１のデータ列２１２には誤りがない。Ｅ1,1′とＥ1,1とが異なる場合、検索された第１のデータ列２１２には誤りがある。
【００３５】
上述のように、例示的な一実施例では、ＥＣＣ  Ｅ2,1、Ｅ3,1、およびＥ4,1も第１のデータ列２１２から生成される。このため、１データ列２１２に誤りが存在するかどうかを判断する精度を高めるために、１データ列２１２に対応する２つ以上の新しいＥＣＣを、検索されたデータ列２１２に基づいて生成することが可能である。
【００３６】
たとえば、新しいＥＣＣ  Ｅ2,1（つまりＥ2,1′）を第１のデータ列２１２から生成し、検索されたＥＣＣ  Ｅ2,1と比較することが可能である。加えて、またはこれに代えて、新しいＥＣＣ  Ｅ3,1（つまりＥ3,1′）を第１のデータ列２１２から生成し、検索されたＥＣＣ  Ｅ3,1と比較することが可能である。加えて、またはこれに代えて、新しいＥＣＣ  Ｅ4,1（つまりＥ4,1′）を第１のデータ列２１２から生成し、検索されたＥＣＣ  Ｅ4,1と比較することが可能である。
【００３７】
また、上述のように、ＥＣＣ  Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1は異なるマトリックスから生成される。たとえば、Ｅ1,1、Ｅ2,1、Ｅ3,1、およびＥ4,1がそれぞれ、第１、第２、第３、および第４のマトリックスから生成されると仮定されたい。このため、上述の例では、Ｅ1,1′、Ｅ2,1′、Ｅ3,1′およびＥ4,1′もそれぞれ、第１、第２、第３、および第４のマトリックスから生成される。
【００３８】
図４を参照すると、例示的な一実施例では、減少した論理データアレイ４０２が、論理
データアレイ２０２（図２）から形成される。この例示的な実施例では、減少した論理データアレイ４０２は、誤りを有するとして識別されたデータアレイ２０２（図２）内のデータ列２１２のみを含む。ＥＣＣ行２１０が次に、誤りを有するとしてＣＲＣ列２１４により識別されたデータ行２０８を訂正するために使用される。減少したデータアレイ４０２はデータアレイ２０２（図２）よりも小さいため、減少したデータアレイ４０２は、データアレイ２０２（図２）よりも短い時間で、および少ない数値計算で訂正可能である。
【００３９】
また、これに代えて、例示的な一実施例では、誤りを有するとして識別されたデータアレイ２０２（図２）内のデータ列２１２は、論理データアレイ４０２を形成することなく訂正される。このため、データアレイ２０２（図２）内の１データ列２１２は、それが誤りを有するかどうかを判断するために調べられる。そのデータ列２１２が誤りを有するとして識別される場合には、データ列２１２は、別のデータ列２１２を調べる前に訂正される。
【００４０】
ここで図５を参照すると、記憶媒体に記憶されたデータを訂正する例示的なプロセス５００が示されている。より具体的には、図５は、コンピュータが実行可能な、記憶装置の動作を指示する命令を含むコンピュータプログラムとして実現される例示的なプロセス５００を示す。たとえば、図１を参照すると、図５に示すプロセスは、記憶装置１０４のプロセッサ１１０の動作を指示可能である。しかしながら、例示的なプロセス５００は、特定用途向け集積回路（ＡＳＩＣ）といったハードウェアにおいて実現可能であることが認識されるべきである。
【００４１】
図５を再度参照すると、この例示的なプロセスでは、記憶装置はテープドライブであり、記憶媒体は磁気テープである。例示のため、ステップ５０２の前に、データおよびそのデータ用のＥＣＣがテープドライブ内のテープに記憶されたと仮定されたい。このため、図５は、テープに記憶されたデータを検索し、検索されたデータ内の任意の誤りを訂正する例示的なプロセスを示している。
【００４２】
より具体的には、ステップ５０２で、テープから検索されたデータブロック用に新しいＥＣＣが生成される。より具体的には、この例示的な実施例では、テープから検索されたデータブロック（つまり“FromTapeEntity.DataBlocks”）が、ＥＣＣを生成する（つまり“GenerateECC”）ルーチンへパスされる。結果は“NewECC”として記憶される。
【００４３】
上述のように、および図２に示すように、例示的な一実施例では、１ＥＣＣ行２１０は、論理データアレイ２０２のデータ行２０８内のデータに対応する。１ＥＣＣ行２１０内の各ＥＣＣは、１データ列２１２に対応している、多数のデータ行２０８からのデータを有する１データセットに対応する。加えて、例示的な一実施例では、論理データアレイ２０２は、１６のデータ行２０８に対応する１６のデータブロック用の、ＥＣＣ行２１０に対応するＥＣＣの４ブロックを含む。このため、論理データアレイ２０２が例示的なプロセス５００（図５）で使用されると仮定すると、ステップ５０２（図５）は、テープから検索されたデータ行２０８に基づいてＥＣＣの４つの新しいブロックを生成することに該当する。しかしながら、新しいＥＣＣは、全部一斉にというよりもむしろ、一度に１つのデータ列２１２について生成可能であることが認識されるべきである。
【００４４】
図５を再度参照すると、ステップ５０４で、新しく生成されたＥＣＣブロック、およびテープから検索されたＥＣＣブロックに対し、論理ＸＯＲ演算が行なわれる。より具体的には、この例示的な実施例では、新しく生成されたＥＣＣブロック（つまり“NewECCBlock[I]”）、およびテープから検索されたＥＣＣ（つまり“FromTape.ECCBlock[I]”）に対し、ＸＯＲが行なわれる。結果は“XorResult[I]”として記憶される。
【００４５】
上述のように、例示的な一実施例では、１６のデータブロック用に４つのＥＣＣブロックが使用される。したがって、信頼性追加のため、４つの新しいＥＣＣブロックが生成され、４つの新しく生成されたＥＣＣブロックおよび４つの検索されたＥＣＣブロックに対して、４つのＸＯＲ演算が行なわれる。４つのＸＯＲ演算の結果は、４つのXorResult変数（つまり、XorResult[０]、XorResult[１]、XorResult[２]、およびXorResult[３]）として記憶される。
【００４６】
このため、図５を再度参照すると、ステップ５０６で、ステップ５０４での４つのＸＯＲ演算の結果に対し、論理和演算が行なわれる。結果は“EntityErrorMap”として記憶される。この例示的なプロセスでは、“EntityErrorMap”変数の各ビットは１データ列２１２（図２）に対応しており、０ビットは１データ列２１２（図２）が誤りを有していないことを示し、１ビットは１データ列２１２（図２）が誤りを有することを示す。１つの新しく生成されたＥＣＣブロックおよび１つの検索されたＥＣＣブロックを用いて、単一のＸＯＲ演算が実行可能であることが認識されるべきであり、その場合、ステップ５０６は省略可能である。
【００４７】
ステップ５０８で“EntityErrorMap”変数の１ビットが調べられ、そのビットが０ビットであるかどうかが判断される。上述のように、そのビットが１ビットである場合には、そのビットに対応するデータ列２１２（図２）は誤りを有する。このため、ステップ５１０で、誤りを有するとして識別されたデータ列２１２（図２）（つまり“FromTapeEntity[column]”）は、別のアレイにおける１列にコピーされる（つまり“PackedErrorEntity[PackedColumn]”）。このため、“PackedErrorEntity”アレイは、誤りを有するとして識別された列のみを含む。ステップ５１２で、変数“PackedColumn”はインクリメントされる。
【００４８】
ステップ５１４で、“EntityErrorMap”変数が調べられ、調べる必要があるビットおよびデータ列がもっとあるかどうかが判断される。調べられるべきビットおよびデータ列がさらにある場合には、ステップ５０８が繰返される。
【００４９】
ステップ５１６で、誤りを有するとして識別されたデータ列が訂正される。より具体的には、この例示的な実施例では、“PackedErrorEntity”アレイは、“PackedErrorEntity”アレイのサイズとともに、アレイを訂正する（つまり“DoGeneralCorrection”）ルーチンへパスされる。
【００５０】
ステップ５１８、５２０、および５２２で、訂正されたアレイ内の訂正された列（つまり“PackedErrorEntity[PackedColumn]”）は、元のアレイ（つまり“FromTapeEntity[Column]”）へ逆にコピーされる。
【００５１】
図２および図４を再度参照すると、上述のように、データアレイ２０２（図２）および減少したデータアレイ４０２（図４）は、行２０４内の誤りを検出するために使用されるチェックサムの列を含む。より特定的には、データアレイ２０２（図２）および４０２（図４）はＣＲＣ列２１４を含む。
【００５２】
また、上述のように、データアレイ２０２（図２）および減少したデータアレイ４０２（図４）は、多数のＥＣＣ行２１０を含み、各ＥＣＣ行２１０は１データ列２１２における単一のセルを訂正するために使用可能である。このため、ＣＲＣ列２１４によって誤りを有するとして示された、データアレイ２０２（図２）または４０２（図４）内の行２０４の数が、ＥＣＣ行２１０の数よりも大きい場合には、データアレイ２０２（図２）または４０２（図４）を従来の手法でＥＣＣ行２１０を用いて訂正することは、通常できない。
【００５３】
たとえば、図２に示す例示的な実施例では、データアレイ２０２は４つのＥＣＣ行２１０を含む。このため、データアレイ２０２内の５つ以上の行２０４がＣＲＣ列２１４によって誤りを有するとして示された場合には、データアレイ２０２を従来の手法でＥＣＣ行２１０を用いて訂正することは、通常できない。
【００５４】
しかしながら、ＣＲＣは行２０４内のセルのすべてが誤りを有するとは示さないため、どの単一の列２０６も、ＣＲＣ列２１４によって示されるのと同数の誤りを持たなくてもよい。たとえば、データアレイ２０２内に誤りを有する行２０４が５つあることをＣＲＣ列２１４が示す場合、それらの誤りは、どの単一の列２０６も誤りを有するセル（つまり行）を５つ持たないように、データアレイ２０２中に分散されてもよい。代わりに、誤りは完全に別々の列２０６に存在してもよい。
【００５５】
こうして、例示的な一実施例では、ＣＲＣ列２１４によって誤りを有するとして示された、データアレイ２０２（図２）または４０２（図４）内の行２０４の数が、ＥＣＣ行２１０の数よりも大きい場合、列２０６は、データアレイ２０２（図２）または４０２（図４）を訂正するために個々に処理される。より特定的には、列２０６は、１列２０６内の行がＣＲＣ列２１４によって示されるように誤りを有することを検証するために、個々に処理される。
【００５６】
図６を参照すると、誤りを有するとして示された行をＥＣＣ行よりも多く有するデータアレイを訂正するための例示的なプロセス６００が示されている。より特定的には、ｋ個の行が誤りを有し、データアレイがｎ個のＥＣＣ行を有することをデータアレイのＣＲＣ列が示す場合、ｋはｎよりも大きい。このため、データアレイを従来の手法でＥＣＣ行を用いて訂正することはできない。
【００５７】
ステップ６０２で、データアレイ内の１列につき、ＣＲＣ列によって誤りを有するとして示された１つ以上の行が選択される。選択される行の数はＥＣＣ行の数と等しい。
【００５８】
ステップ６０４で、選択された行についてのデータが、ＥＣＣ行を用いて生成される。非選択行（つまり、ステップ６０２で選択されなかった、誤りを有するとして識別された行）内のデータは正しいと仮定される。
【００５９】
ステップ６０６で、選択行についての生成されたデータを用いて、誤りを有するとして示された行を検証する。より特定的には、選択行についての生成されたデータが、元々選択行にあったデータと比較される。これらの行のすべてについて、生成されたデータと元のデータとが同じであるならば、この列の選択行および非選択行のうちのいずれにおいても誤りはない（つまり、この列についての選択行および非選択行内のデータは正しい）。
【００６０】
ステップ６０８で、誤りを有するとして示されたどの行も、ステップ６０６で実際には誤りを持っていなかった場合、処理されるべき別の列があれば別の列が処理される。たとえば、図２を参照すると、第１の列２０６を処理した後で、第２の列２０６が処理可能である。このように、データアレイ２０２の各列２０６が処理可能である。しかしながら、列２０６はどの順序でも処理可能であることが認識されるべきである。
【００６１】
図４を参照すると、減少したデータアレイ４００にプロセス６００（図６）を適用する場合、ステップ６０６（図６）における判断は決して否定的にはならない。なぜなら、データアレイ４００（図４）の各列２０６は、誤りを有する少なくとも１つの行を含むはずだからである。このため、データアレイ４００にプロセス６００（図６）を適用する場合、ステップ６０６および６０８（図６）は省略可能である。
【００６２】
図６を再度参照すると、ステップ６１０で、選択行について生成されたデータのうちのいずれかが、元々選択行にあったデータと整合するかどうかについて、判断がなされる。ステップ６１０で選択行について生成されたデータと元のデータとがどれも整合しない場合には、選択行および非選択行についてのデータは、おそらく正しくない。
【００６３】
このため、ステップ６１２で、選択行の可能な組合せのすべてが試みられたかどうかについて判断がなされる。ステップ６１４で、行の別の組合せが選択され、プロセスが繰返される。ステップ６１６で、処理すべき別の列がある場合には別の列が処理される。
【００６４】
ステップ６１０で選択行のうちのいずれかについて生成されたデータと元のデータとが同じである場合には、残りの行（つまり、生成されたデータと元のデータとが整合しなかった選択行）について生成されたデータは、これらの行についての正しいデータであり、非選択行についてのデータも正しい。このため、ステップ６１８で、生成されたデータと元のデータとが整合しなかった選択行内のデータは、これらの行についての生成されたデータと置き換えられる。ステップ６２０で、これらの行（つまり、訂正されたデータと元のデータとが整合しなかった選択行）用のＣＲＣが再計算される。
【００６５】
ステップ６２２で、再計算されたＣＲＣを含め、ＣＲＣによって誤りを有するとして示された行の数がＥＣＣ行の数よりも大きいかどうかについて判断がなされる。ステップ６２４で、誤りを有するとして示された行の数が依然としてＥＣＣ行の数よりも大きい場合、処理すべき別の列が残っている場合には別の列が処理される。ステップ６２６で、新しいＣＲＣによって誤りを有するとして示された行の数がＥＣＣ行の数より大きくない場合、データアレイはここでＥＣＣ行を用いて訂正可能である。
【００６６】
プロセス６００をより明確に説明するため、図２を参照して、データアレイ２０２は４つのＥＣＣ行２１０（つまりｎ＝４）を含み、ＣＲＣ列２１４は、５つの行２０４（たとえば１番目、３番目、５番目、６番目、および１６番目の行）が誤りを有する（つまりｋ＝５）ことを示していると仮定されたい。より特定的には、１番目、３番目、５番目、６番目、および１６番目の行に対応するデータブロックを検索した後で、検索されたデータブロックの各々に対して新しいＣＲＣが生成されると仮定されたい。検索されたデータブロックを記憶媒体１０６（図１）に記憶させる前に、新しいＣＲＣは、検索されたデータブロック用に元々生成されたＣＲＣと比較され、これらの行２０４についての新しいＣＲＣと元々生成されたＣＲＣとが整合しなかった場合、それは、検索されたデータブロック内のデータが元々データブロックに記憶されたデータと同じではないことを示す。
【００６７】
このため、この例では、ステップ６０２（図６）で、データアレイ２０２内の１列２０６につき、誤りを有するとして示された行のうちの４つが選択される。なぜなら、ＥＣＣ行２１０が４つあるためである。例示のため、データアレイ２０２の１番目の列が選択され、１番目の列の３番目、５番目、６番目、および１６番目の行が選択されると仮定されたい。
【００６８】
ステップ６０４（図６）で、１番目の列の３番目、５番目、６番目、および１６番目の行に対応する新しいデータが、４つのＥＣＣ行を用いて生成される。この例では、１番目の列の３番目、５番目、６番目、および１６番目の行についての元のデータをそれぞれＡ、Ｂ、Ｃ、およびＤと仮定し、新しい生成データをＡ′、Ｂ′、Ｃ′、およびＤ′と仮定されたい。１番目の列内のデータは正しいデータを含むと仮定される。
【００６９】
ステップ６０６で、生成データ（つまりＡ′、Ｂ′、Ｃ′、およびＤ′）と元のデータ（つまりＡ、Ｂ、Ｃ、およびＤ）とを用いて、３番目、５番目、６番目、または１６番目
の行が実際に誤りを有するかどうかを判断する。より特定的には、Ａ′、Ｂ′、Ｃ′、およびＤ′がＡ、Ｂ、Ｃ、およびＤと比較される。
【００７０】
ステップ６０８で、Ａ′、Ｂ′、Ｃ′、およびＤ′とＡ、Ｂ、Ｃ、およびＤとの比較が全データの整合をもたらす場合、１番目の列には誤りはなかった。このため、２番目の列といった別の列が処理される。
【００７１】
ステップ６１０で、比較されたデータのうちのいずれかが整合したかどうかについて判断がなされる。比較されたデータがどれも整合しなかった場合、次にステップ６１２で、選択行および非選択行の可能な組合せのすべてがなされたかどうかについて判断がなされる。この例では、誤りを有するとして示された行は５つあり、ＥＣＣ行は４つあるため、選択行および非選択行の可能な組合せは合計で５つある。より特定的には、以下の表は選択行および非選択行のさまざまな組合せを記載する。
【００７２】
【表１】
2004281037.tif 000003
【００７３】
ステップ６１４で、選択行および非選択行の別の組合せが使用される。この例では、表１に記載された組合せ１を使用した後で、組合せ２が使用可能である。こうして、ステップ６１４で、１番目の列の３番目の行がここで正しいデータを含むと仮定される。ステップ６０４を繰返して、１番目、５番目、６番目、および１６番目の行についてのデータが、ＥＣＣ行を用いて生成される。
【００７４】
ステップ６１６で、すべての組合せが試みられていた場合、別の列が処理される。たとえば、１番目の列を処理した後で、２番目の列が処理可能である。
【００７５】
ステップ６１０で３番目の列だけについて生成データと元のデータとが整合した（つまりＡ′＝Ａ）と仮定されたい。このため、ステップ６１８で、５番目、６番目、および１６番目の行についてのデータはそれぞれ、Ｂ′、Ｃ′およびＤ′と置き換えられる。ステップ６２０で、５番目、６番目、および１６番目の行用のＣＲＣが再計算される。
【００７６】
ステップ６２２で、再計算されたＣＲＣを含め、ＣＲＣによって誤りを有するとして示された行の数が依然としてＥＣＣ行の数よりも大きいかどうかについて判断がなされる。このため、この例では、５番目、６番目、および１６番目の行用の再生成されたＣＲＣのすべてが依然として、これらの行が誤りを有することを示す場合、ステップ６２４で、処理されるべき別の列がある場合には別の列が処理される。しかしながら、５番目、６番目、および１６番目の行用の再生成されたＣＲＣのうちのいずれか１つが、これらの行のどれにももはや誤りがないことを示す場合、ステップ６２６で、データアレイはＥＣＣ行を用いて訂正される。
【００７７】
上述の例は、データアレイが４つのＥＣＣ行を含み、５つの行が誤りを有するとして示されたことを仮定した。上述のように、データアレイは任意の数のＥＣＣ行を含むことが可能であり、任意の数の行が誤りを有するとして示され得る。たとえば、データアレイが４つのＥＣＣ行を含み、６つの行が誤りを有するとして示された場合、誤りを有するとして示された行のうちの４つが選択され、これらの行についてのデータが４つのＥＣＣ行を用いて生成される。２つの非選択行は次に正しいデータを含むと仮定される。また、上述のように、誤りを有するとして示された行のさまざまな組合せは、列を訂正する際に選択行および非選択行として使用可能である。
【００７８】
例示的な実施例が説明されてきたが、この発明の精神および／または範囲から逸脱することなく、さまざまな変更がなされ得る。したがって、この発明は、図面に示された、および上述された特定の形態に限定されるものとして解釈されるべきではない。
【図面の簡単な説明】
【００７９】
【図１】例示的な記憶装置に接続された例示的なホスト端末を示す図である。
【図２】例示的な論理データアレイを示す図である。
【図３】図２の例示的な論理データアレイの一部を示す図である。
【図４】図２の例示的な論理データアレイから派生した、減少した論理データアレイを示す図である。
【図５】記憶媒体から検索されたデータを訂正する例示的なプロセスを示す図である。
【図６】記憶媒体から検索されたデータ内の誤りを検証する例示的なプロセスを示す図である。
【符号の説明】
【００８０】
１０２  ホスト端末、１０６  記憶媒体、１１０  プロセッサ、１１４  データバッファ。
【図１】
2004281037.tif 000004
【図２】
2004281037.tif 000005
【図３】
2004281037.tif 000006
【図４】
2004281037.tif 000007
【図５】
2004281037.tif 000008
【図６】
2004281037.tif 000009