JP2004362758A

JP2004362758A - 記憶媒体から検索されたデータの誤りを訂正するシステムおよび方法、ならびにコンピュータにこれらの誤りを訂正させるためのコンピュータ実行可能な命令を含むコンピュータ読取可能な記憶媒体

Info

Publication number: JP2004362758A
Application number: JP2004164729A
Authority: JP
Inventors: Matt Ball; マット・ボール
Original assignee: Quantum Corp
Current assignee: Quantum Corp
Priority date: 2003-06-03
Filing date: 2004-06-02
Publication date: 2004-12-24
Also published as: US7290197B2; US20040260971A1; DE602004008150T2; EP1486872A1; EP1486872B1; DE602004008150D1

Abstract

【課題】複数のデータブロックと複数のデータブロックに関連する複数の冗長ブロックとを記憶媒体から検索することにより、記憶媒体から検索したデータの誤りを訂正する。
【解決手段】記憶媒体から検索されて誤りを有する１つ以上のデータブロックが、識別されて削除される。誤りを有していると識別されたデータブロックの数が、検索された冗長ブロックの数よりも小さい場合、１つ以上の余分な冗長ブロックが除去され、検索された冗長ブロックから１つ以上の保存される冗長ブロックが保持される。検索されたデータブロックに基づいて１つ以上の新規の冗長ブロックが生成される。１つ以上の新規の冗長ブロックと１つ以上の保存される冗長ブロックとに基づいて１つ以上の残余ブロックが生成される。生成された１つ以上の残余ブロックを用い、誤りを有していると識別された１つ以上のデータブロックが訂正される。
【選択図】図１

Description

背景
１．発明の分野
本願は一般に、記憶媒体から検索されたデータの訂正に関し、より具体的に、記憶媒体から検索されたデータの誤りを訂正するための冗長ブロックの使用に関する。

２．関連技術
データは、記憶装置の記憶媒体にデータを書込むことによって記憶装置に格納される。格納されたデータは、記憶媒体からそのデータを読出すことによって記憶装置から後に検索され得る。しかしながら、多数の理由により、記憶装置から検索されたデータに誤りが存在する場合があり、格納されたデータが検索され得ないか、または記憶媒体に最初に格納されたデータとは異なっていることを意味する。たとえば、記憶媒体に格納されたデータの一部は時間がたつと劣化することがあり、格納されたデータの一部を後で適切に読出すことができなくなってしまう。

このような誤りを訂正するための従来の技術では、データに対して冗長ブロックの集合が生成され、そのデータとともに記憶媒体に格納される。格納されたデータが後に検索されて誤りが検出されると、検索されたデータを訂正するために冗長ブロックが用いられる。一般に、冗長ブロックの集合内の冗長ブロックのすべてが、検索されたデータの誤りの大きさに関係なく検索されたデータを訂正するために用いられる。しかしながら、冗長ブロックのすべてにアクセスすることによって記憶媒体へのアクセス時間を消費し、行なわなければならない計算の数を増やし、訂正時間を増長させる。

概要
例示的な一実施例では、複数のデータブロックと、複数のデータブロックに関連する複数の冗長ブロックとが記憶媒体から検索される。記憶媒体から検索されて誤りを有する１つ以上のデータブロックが、識別されて除去される。誤りを有していると識別されたデータブロックの数が、検索された冗長ブロックの数よりも小さい場合、１つ以上の余分な冗長ブロックが除去されて、検索された冗長ブロックから１つ以上の保存される冗長ブロックが保持される。検索されたデータブロックに基づいて１つ以上の新規の冗長ブロックが生成される。１つ以上の新規の冗長ブロックと１つ以上の保存される冗長ブロックとに基づいて１つ以上の残余ブロックが生成される。生成された１つ以上の残余ブロックを用い、誤りを有していると識別された１つ以上のデータブロックが訂正される。

詳細な説明
以下の説明は、多数の特定の構成、パラメータ等を明示する。しかしながら、このような説明が、この発明の範囲に対する限定とは意図されず、例示的な実施例のより良い説明をもたらすために提供されていることを認識されたい。

図１を参照すると、記憶装置１０４に接続されたホスト端末１０２が示される。ホスト
コンピュータ１０２は任意の種類のコンピュータ、たとえばパーソナルコンピュータ、ワークステーション、サーバ等であり得る。記憶装置１０４は任意の種類の記憶ドライブ、たとえばテープドライブ、ハードドライブ等であり得る。ホスト端末１０２を任意の数の記憶装置１０４に接続でき、任意の数のホスト端末１０２を１つ以上の記憶装置１０４に接続できることを認識されたい。

引続き図１を参照すると、例示的な一実施例において、記憶装置１０４は記憶装置１０４に格納されたデータの誤りを検出して訂正するように設定される。より具体的に、記憶装置１０４に格納されたデータが検索されると、たとえばその検索されたデータが記憶装置１０４に最初に格納されていたデータと異なる場合、または格納されたデータを検索できない場合に、記憶装置１０４は、検索されたデータの誤りを訂正するために誤り訂正符号（ＥＣＣ）冗長ブロックとも呼ばれる冗長ブロックを用いるように設定される。加えて、この例示的な実施例では、検索されたデータの誤りを検出するために、巡回冗長検査（ＣＲＣ）符号等のチェックサムが用いられる。しかしながら、冗長ブロックを用いて誤りの訂正だけでなく検出も可能であることを認識されたい。

図１に示された実施例において、記憶装置１０４は、記憶媒体１０６、チャネルおよび読出／書込ヘッド１０８、プロセッサ１１０、および誤り検出／訂正ユニット１１２を含む。記憶装置１０４において、データは記憶媒体１０６に格納される。読出／書込ヘッド１０８は記憶媒体１０６とデータの読出および／または書込を行なう。プロセッサ１１０はチャネルおよび読出／書込ヘッド１０８の動作を含む、記憶装置１０４の動作を制御する。以下により詳細に説明するように、誤り検出／訂正ユニット１１２は、記憶媒体１０６に格納されたデータの誤りを検出して訂正する。

この例示的な実施例において、誤り検出／訂正ユニット１１２は、データバッファ１１４、冗長ブロック符号器／復号器１１６、およびＣＲＣ符号器／復号器１１８を含む。データが記憶媒体１０６に格納されるべき場合、データがホスト端末１０２から受取られてデータバッファ１１４に書込まれる。冗長ブロック符号器／復号器１１６およびＣＲＣ符号器／復号器１１８は、データバッファ１１４のデータに対して冗長ブロックとＣＲＣ符号とを生成する。次に、読出／書込ヘッド１０８は、生成された冗長ブロックおよびＣＲＣ符号とデータとを記憶媒体１０６に書込む。

データが記憶媒体１０６から読出されるべき場合、読出／書込ヘッド１０８は記憶媒体１０６からデータバッファ１１４にデータと冗長ブロックとを読出す。以下により詳細に説明するように、記憶媒体１０６から読出されたデータのどのような誤りも、ＣＲＣ符号および冗長ブロックを用いて検出および訂正される。次に、このデータをホスト端末１０２に転送できる。

例示的な一実施例において、データはホスト端末１０２と記憶装置１０４との間をデータレコードとして転送され、このデータレコードはキャッシュに格納される。データレコードは、予め規定された長さ、たとえば２ｋバイト、４ｋバイト、６ｋバイト等のデータブロックに分割される。しかしながら、さまざまな長さのデータブロックを用いてよいことを認識されたい。

この例示的な実施例では、データブロックが記憶媒体１０６から検索された後に、検索されたデータブロックの誤りを検出するためにＣＲＣ符号が用いられ、検索されたデータブロックの誤りは、データが記憶媒体１０６に最初に格納されたときのデータブロックのデータと検索されたデータブロックのデータとが異なることを示す。より具体的に、記憶媒体１０６にデータブロックを格納する前に、そのデータブロックに対してＣＲＣ符号が生成され、記憶媒体１０６にデータブロックとともに格納される。データブロックが後に
検索されると、その検索されたデータブロックに対して新規のＣＲＣ符号が生成される。次に、この新規のＣＲＣ符号が、記憶媒体１０６から検索されたＣＲＣ符号と比較される。記憶媒体１０６から検索されたこのＣＲＣ符号は、検索されたデータブロックに対応しており、検索されたデータブロックが記憶媒体１０６に格納される前に、この検索されたデータブロックに対して最初に生成されたものである。新規のＣＲＣ符号と検索されたＣＲＣ符号とが異なる場合、そのデータブロックに誤りが検出される。

加えて、この例示的な実施例において、検索されたデータブロックの誤りを訂正するために冗長ブロックが用いられる。より具体的に、記憶媒体１０６にデータブロックを格納する前に、そのデータブロックに基づいて冗長ブロックが生成され、記憶媒体１０６にデータブロックとともに格納される。以下により詳細に説明するように、データブロックが後に検索されたときに、誤りを有していると識別されたデータブロックは、冗長ブロックを用いて訂正される。

例示的な一実施例において、冗長ブロック２０４はボース−チャウドゥーリー−オッカンガム（Bose-Chaudhuri-Hocquenghem）（ＢＣＨ）符号であり、より具体的にリード−ソロモン（Reed-Solomon）符号である。リード−ソロモン符号のより詳細な説明については、この明細書においてその全体が引用によって援用される、１９７２年、ＭＩＴプレス（MIT Press）、ピーターソン（Peterson）およびウェルドン（Weldon）による「誤り訂正符号（Error Correcting Codes）」第２版を参照されたい。しかしながら、さまざまな種類の誤り訂正符号を用いてよいことを認識されたい。

例示的な一実施例において、データブロックの集合、冗長ブロックの集合、およびＣＲＣ符号の集合は、「エンティティ」と呼ばれるグループとしてまとめて読出および書込が行なわれ得る。たとえば図２を参照すると、エンティティ２０２は１６個のデータブロック２０４、４個の冗長ブロック２０６、および２０個のＣＲＣ符号２０８を有していることが示される。しかしながら、エンティティ２０２がさまざまな数のデータブロック２０４、冗長ブロック２０６、およびＣＲＣ符号２０８を含み得ることを認識されたい。加えて上述のように、冗長ブロックは、検索されたデータブロックの誤りを訂正するだけではなく検出するためにも用いられ得る。したがって、ＣＲＣ符号２０８を冗長ブロックの集合と置換できる。

図２はエンティティ２０２がデータバッファ１１４（図１）に格納されている形を示す。しかしながら、エンティティ２０２が図２に示された形で物理的に存在しなくてよいことを認識されたい。また、エンティティ２０２のデータ、より具体的にデータブロック２０４のデータが１つのファイルに対応する必要のないことも認識されたい。むしろ、例示的な一実施例において、ホスト端末１０２（図１）から検索されたデータはインタリーブされる。したがって、特定のデータブロック２０４のデータは、ホスト端末１０２（図１）から検索された別個のファイルの一部に対応し得る。

図２はまた、エンティティ２０２のデータブロック２０４、冗長ブロック２０６、およびＣＲＣ符号２０８の間の論理関係を示す。図３を参照すると、データブロック２０４、冗長ブロック２０６、およびＣＲＣ符号２０８の間の論理関係をより明らかに示すために、エンティティ２０２の一部がより詳細に示される。

図３に示されるように、ＣＲＣ符号２０８はデータブロック２０４または冗長ブロック２０６に対応しており、データブロック２０４または冗長ブロック２０６の誤りを検出するために用いられる。たとえばＣＲＣ符号のＣＲＣ₁₉は、エンティティ２０２のデータブロックＤ₁₉に対応する。したがって、データブロックＤ₁₉の誤りを検出するために、記憶媒体１０６（図１）からデータブロックＤ₁₉を検索した後に、検索されたデータブロック
Ｄ₁₉に対して新規のＣＲＣ符号のＣＲＣ₁₉´が生成される。次に、記憶媒体１０６（図１）から検索されて、検索されたデータブロックＤ₁₉に対応するＣＲＣ符号（すなわちＣＲＣ符号のＣＲＣ₁₉）と、新規のＣＲＣ符号のＣＲＣ₁₉´とが比較される。新規のＣＲＣ符号のＣＲＣ₁₉´と検索されたＣＲＣ符号のＣＲＣ₁₉とが異なる場合、データブロックＤ₁₉に誤りが検出される。

この例示的な実施例では、１つの冗長ブロックを用いてエンティティ２０２の１つのデータブロック２０４を訂正できる。したがって、図２に示された例では、全部で４個の冗長ブロック２０６を用いて、全部で１６個のデータブロック２０４を有するエンティティ２０２のうち、全部で４個のデータブロック２０４を訂正できる。たとえば、冗長ブロックＥ₃を用いてエンティティ２０２の第１のデータブロックを訂正できる。冗長ブロックＥ₂を用いてエンティティ２０２の第２のデータブロックを訂正できる。冗長ブロックＥ₁を用いてエンティティ２０２の第３のデータブロックを訂正できる。冗長ブロックＥ₀を用いてエンティティ２０２の第４のデータブロックを訂正できる。

この例示的な実施例において、各冗長ブロック２０６はエンティティ２０２のすべてのデータブロックのデータに基づいて生成される。たとえば冗長ブロックＥ₀、Ｅ₁、Ｅ₂、およびＥ₃の各々は、データブロックＤ₄、Ｄ₅…Ｄ₁₉のデータに基づいて生成される。上で述べたように、図１を参照すると、冗長ブロック２０６は冗長ブロック符号器１１６によって生成される。また上で述べたように、冗長ブロックは、ホスト端末１０２から受取られたデータに対して最初に生成される。次に、生成された冗長ブロックと受取られたデータとが記憶媒体１０６に格納される。

再び図３を参照すると、冗長ブロックＥ₀、Ｅ₁、Ｅ₂、およびＥ₃は同じ集合のデータ（すなわちエンティティ２０２のデータブロック２０４）に基づいて生成されているが、各冗長ブロック２０４は互いに固有である。より具体的に、この実施例において、冗長ブロックＥ₀、Ｅ₁、Ｅ₂、およびＥ₃はボース−チャウドゥーリー−オッカンガム（ＢＣＨ）符号であり、より具体的にリード−ソロモン符号である。冗長ブロックＥ₀、Ｅ₁、Ｅ₂、およびＥ₃は冗長ブロック符号器１１６（図１）を用いて生成される。例示的な符号器の説明については、この明細書においてその全体が引用によって援用される、１９９２年８月４日付で出願されて「長いバースト誤りに対する誤りの検出および訂正システム（ERROR DETECTION AND CORRECTION SYSTEM FOR LONG BURST ERRORS）」と題された米国特許第５，１３６，５９２号を参照されたい。

図４を参照すると、記憶媒体から検索されたデータブロックの誤りを冗長ブロックを用いて訂正するための例示的なプロセス４０２が示される。より具体的に、図４はコンピュータプログラムとして実現される例示的なプロセス４０２を示し、このコンピュータプログラムはコンピュータ実行可能な命令を含んで記憶装置の動作を指示する。たとえば図１を参照すると、図４に示されたプロセスは、記憶装置１０４のプロセッサ１１０の動作を指示することができる。しかしながら、例示的なプロセス４０２（図４）が特定用途向け集積回路（Application-Specific Integrated Circuit）（ＡＳＩＣ）等のハードウェアにおいて実現され得ることを認識されたい。

図４に関して、データブロックの集合に対して冗長ブロックの集合が事前に生成されており、冗長ブロックの集合およびデータブロックの集合が記憶媒体に事前に格納されているものとプロセス４０２が仮定していることを認識されたい。例示のため、ｍ個のデータブロックに対してｎ個の冗長ブロックが生成されたと考えられたい。したがって図２に示された例では、ｎは４であり、ｍは１６である。

再び図４を参照すると、４０４においてデータブロックの集合および冗長ブロックの集
合が記憶媒体から読出される。加えて、この例示的な実施例では、ＣＲＣ符号の集合が記憶媒体から読出される。上で述べたように、ＣＲＣ符号の集合ではなく冗長ブロックの別の集合の使用が可能である。

４０６において、誤りを有するデータブロックが識別されて除去される。上で述べたように、この実施例では、誤りを有するデータブロックを識別するためにＣＲＣ符号が用いられる。次に、誤りを有していると識別されたデータブロックは、消失部（erasure）としてマークされ得る。

記憶装置１０４（図１）がテープドライブであって記憶媒体１０６（図１）が磁気テープである例示的な一実施例において、データブロックおよび冗長ブロックは、磁気テープから読出されてデータバッファに格納される。データブロックまたは冗長ブロックが読出されると、そのデータブロックまたは冗長ブロックに対応するＣＲＣ符号もまた磁気テープから読出される。磁気テープから読出されたデータブロックまたは冗長ブロックに基づいて新規のＣＲＣ符号が生成され、次にこの新規のＣＲＣ符号が、検索されたＣＲＣ符号と比較される。新規のＣＲＣ符号と検索されたＣＲＣ符号とが異なっている場合、誤りが検出されて、検索されたデータブロックまたは冗長ブロックは誤りを有しているとしてフラグ付けされる。したがって、この例示的な実施例において、ＣＲＣ符号は検索されたデータブロックおよび冗長ブロックとともにデータバッファに格納されない。しかしながら、後の使用のためにＣＲＣ符号を格納できることを認識されるべきである。加えて、データブロック、冗長ブロック、およびＣＲＣ符号はともに磁気テープから検索されてデータバッファに格納され得、その後、誤りを有するデータブロックおよび／または冗長ブロックが、データバッファに格納されたＣＲＣ符号を用いて識別され得る。

４０８において、任意の余分な冗長ブロックが除去される。上で述べたように、１つの冗長ブロックを用いて、記憶媒体から検索されたデータブロックの集合のうち１つのデータブロックを訂正できる。したがって、記憶媒体から検索されたｍ個のデータブロックのうち、ｎ個の冗長ブロックを用いてｎ個のデータブロックを訂正できる。／ｌ（／ｌはＬの小文字とする）個のデータブロックが誤りを有していると識別されて／ｌがｎ未満である場合、余分なデータブロック（すなわちｎ−／ｌ個）が除去され得る。

したがって、４個の冗長ブロックが用いられている（ｎ＝４）図２に示された例において、４個のデータブロックが誤りを有していると識別された場合（／ｌ＝４）、除去される冗長ブロックはない（ｎ−／ｌ＝４−４＝０）。しかしながら、３個のデータブロックが誤りを有していると識別された場合（／ｌ＝３）、１個の冗長ブロックが除去される（ｎ−／ｌ＝４−３＝１）。２個のデータブロックが誤りを有していると識別された場合（／ｌ＝２）、２個の冗長ブロックが除去される（ｎ−／ｌ＝４−２＝２）。１個のデータブロックが誤りを有していると識別された場合（／ｌ＝１）、３個の冗長ブロックが除去される（ｎ−／ｌ＝４−１＝３）。再び図４を参照すると、誤りを有していると識別されたデータブロックがない場合（／ｌ＝０）、誤り訂正のプロセス４０２は実行されなくてよい。

４１０において、検索されたデータブロックに基づいて新規の冗長ブロックが生成される。この例示的な実施例では、検索されたデータブロックに基づいて新規の冗長ブロックを生成する際に、４０８において誤りを有していると識別されたデータブロックが、すべて０を含むダミーのデータブロックと置換される。代替的に、新規の冗長ブロックは、検索されたデータブロックが誤りを有していると識別されたデータブロックを保持したまま、検索されたデータブロックに基づいて生成され得る。加えて、この例示的な実施例では、図１を参照すると、冗長ブロック符号器１１８を用いて新規の冗長ブロックが生成される。

たとえば図２を参照して、第１および第３のデータブロックが誤りを有していると識別されたものと仮定されたい。したがって、２個のデータブロックが誤りを有していると識別される（すなわち／ｌ＝２）。したがって、検索されたデータに基づいて２個の新規の冗長ブロック（すなわち／ｌ＝２）が計算される。上で述べたように、２個の新規の冗長ブロックを生成する際に、第１および第３のデータブロックは、すべて０を含むダミーのデータブロックと置換される。

４１２では、新規の冗長ブロックおよび検索された冗長ブロックに基づいて残余（residual）ブロックが生成される。より具体的に、残余ブロックは、新規の冗長ブロックと検索された冗長ブロックとの間で排他的論理和（Exclusive-OR）（ＸＯＲ）演算を行なうことによって生成される。数学的に、残余ブロックは、検索された符号語を生成多項式で割った剰余である。ここでもまた、生成される残余ブロックの数は、誤りを有していると識別されたデータブロックの数（すなわち／ｌ）に対応する。

４１４において、誤りを有していると識別されたデータブロックは、生成された残余ブロックを用いて訂正される。リード−ソロモン符号が用いられるこの例示的な実施例において、誤りを有していると識別されたデータブロックは、生成された残余ブロックの集合と訂正行列との間でガロア体（Galois Field）の行列乗算演算を行なうことによって訂正される。

この例示的な実施例では、誤りを有するデータブロックを訂正する際に用いるための訂正行列を生成するために、基本的な冗長ブロックの単位を形成する冗長ブロック記号とデータとが符号語としてグループ化される。たとえば図２を参照すると、符号語２１０はエンティティ２０２においてデータブロック２０４および冗長ブロック２０６各々の８ビット記号を含む。したがってデータブロック２０４が２ｋバイトの長さである場合、２０００個の符号語が存在する。しかしながら、符号語２１０およびデータブロック２０４がどのような長さでもよいことを認識されたい。

符号語多項式はデータ多項式と冗長ブロック多項式との組合せである。より具体的に、データブロック多項式は以下のとおりである。

ここでＭはデータブロックの数であり、Ｄ_iは特定のデータブロックである。冗長ブロック多項式は以下のとおりである。

ここでＮは冗長ブロックの数であり、Ｅ_iは特定の冗長ブロックである。したがって符号語多項式は以下のとおりである。

冗長ブロック多項式は、データブロック多項式を生成多項式（Ｇ（ｘ））で割った剰余である。生成多項式Ｇ（ｘ）はαのＮ個の連続する冪を根として含み、ここでαはガロア体の原始要素である。この例示的な実施例では、Ｇ（ｘ）の第１の根がα⁰であるとみなされて計算量を減じる。したがって第１の根がα⁰であるものとされた生成多項式は以下のとおりである。

例示的な一実施例では以下の生成多項式を使用できる。

ここでガロア体は、ｇ（ｘ）＝ｘ⁸＋ｘ⁴＋ｘ³＋ｘ²＋１およびα＝００００００１０によって定義される。ガロア体の数学的処理が加算と減算とを区別しないことに注意されたい。したがってＡ−Ａ＝０であるのとちょうど同様に、Ａ＋Ａ＝０である。しかしながら、Ａ＋Ａ＝０を強調するために「−」の演算子を使用すると都合がよい場合がある。

Ｄ（ｘ）、Ｅ（ｘ）、およびＧ（ｘ）の関係をまとめると以下のようになる。

Ｑ（ｘ）が、Ｄ（ｘ）ｘ^NをＧ（ｘ）で割った商であることに注意されたい。この方程式を整理し直すと、以下のものが得られる。

この方程式の左側もまた、符号語多項式の定義であることに注意されたい。すなわち、以下のようになる。

したがって、符号語多項式は生成多項式の倍数である。加えて、ｘがＧ（ｘ）の根である場合、Ｃ（ｘ）は０である。

次に、Ｃ′（ｘ）が誤りを有するデータブロックを備えた符号語であると仮定されたい。Ｇ（ｘ）の根においてＣ′（ｘ）の値を求めることによって部分シンドロームが生成される。Ｇ（ｘ）の各根に対して１つの部分シンドロームが存在する。すべての部分シンドロームが０であれば、その符号語内に誤りは存在しない。部分シンドロームのいずれかが０でない場合、その符号語内のどこかに誤りが存在する。

次に、Ｙ（ｘ）が誤り多項式であると仮定されたい。以下の２つの方程式はＹ（ｘ）を記述する。

ここでｐは、誤りを有する、検索されたデータブロックおよび冗長ブロックの数であり、Ｙ_iは特定の誤りの値であり（ここでｉは０とｐ−１との間にある）、Ｂ_iは特定の誤りのブロック番号（位置）である。Ｄ′（ｘ）が取り出されたデータブロックの集合を含み、Ｅ′（ｘ）が取り出された冗長ブロックの集合を含むものと仮定されたい。したがって、

となる。

上で述べたように、この例示的な実施例では、データ記憶媒体から検索されたデータブロック（Ｄ′（ｘ））に基づき、冗長ブロック符号器１１６（図１）を用いて冗長ブロックの新規の集合（／Ｅ（ｘ））が生成される（／ＥはＥの上付きバーを示す）。対応する符号語（／Ｃ（ｘ））は以下のようになる（／ＣはＣの上付きバーを示す）。

ｘが生成多項式Ｇ（ｘ）の根に等しいとき、Ｃ（ｘ）と同様に／Ｃ（ｘ）＝０であることに注意されたい。

次に、上の方程式に基づいて、誤り多項式（Ｙ（ｘ））が得られる。第１の方程式はＣ′（ｘ）ついての方程式である。

第２の方程式は／Ｃ（ｘ）についての方程式である。

これらの方程式を加えることにより、以下のものが得られる。

ガロア体の数学的処理において、Ａ＋Ａ＝０である。したがってＤ′（ｘ）の項を除去できる。

ｘがこの生成多項式の根である場合にこの方程式を求めることにより、Ｃ（ｘ）および／Ｃ（ｘ）の項は両方とも０になる。

Ｙ（ｘ）、Ｅ′（ｘ）および／Ｅ（ｘ）にそれらの合計記述を代入することによって以下の方程式が得られる。

誤り位置多項式を記述するＮ個の方程式が存在し、Ｇ（ｘ）の各根に対して１つの方程式が存在する。α⁰がＧ（ｘ）の第１の根である場合、上の方程式は、

となる。この方程式はｊ番目の部分シンドロームを表わす。

一般に、従来のリード−ソロモン復号技術は、部分シンドロームを直接計算してＹ（ｘ）について解く。しかしながら、部分シンドロームの計算は、さらに別のハードウェアを一般に必要とする。以下に述べるように、この例示的な実施例において、Ｙ（ｘ）は、部分シンドロームを計算するためのハードウェアを使用せずに求められる。

この例示的な実施例において、誤り位置値（Ｘ_i）は以下の方程式を用いて求められる。

誤り位置値は訂正プロセスの全体にわたって一定であり、ルックアップテーブルを用いて、または他の冪法技術を用いて計算され得る。

部分シンドロームの方程式は、Ｂ_iではなくＸ_iを用いて単純化できる。より具体的に、部分シンドロームの方程式は以下のようになる。

Ｎ個の部分シンドローム方程式をすべて書き出すことにより、以下の行列方程式が得られる。

最も左の行列は誤り位置行列である。誤り位置行列が、誤りを有するデータブロックの位置にのみ依存することに注意されたい。最も右の行列は冗長ブロック位置行列であり、これは冗長ブロックの定位の位置にのみ依存する。冗長ブロックのブロック番号は０〜Ｎ−１であり、Ｎは冗長ブロックの数である。データブロックはブロック番号Ｎで始まり、大きくなって続いてゆく。加えて、最も右の列ベクトルは残余ブロックの集合である。

誤り位置行列および冗長ブロック位置行列はともに、ヴァンデルモンド（Vander monde）行列である。ヴァンデルモンド行列の１つの特性は、その行列が平方でない場合でも常に逆行列を有することである。ヴァンデルモンド行列の別の特性は、Ｏ（Ｎ³）演算を必要とする一般的な行列とは対照的に、逆がＯ（Ｎ²）演算を必要とすることである。

誤り値（Ｙ_i）について解くために、誤り位置行列の逆を得る。次に、この結果を冗長ブロック位置行列で乗算する。

誤り位置行列の逆を得るために、誤り位置多項式（σ（ｘ））が計算される。誤り位置多項式は以下のように定義される。

ここでｐは誤りを有するデータブロックおよび冗長ブロックの数であり、Ｘ_iは特定の誤り位置である。ｘが誤り位置に等しい場合、誤り位置多項式が０であることに注意されたい。

加えて、以下のように各誤り位置ｊにおける関数σ^（j）（ｘ）が求められる。

ｘが誤り位置ｊを除く誤り位置に等しい場合、この関数σ^(j)（ｘ）は０である。

誤り位置行列の逆の各行は、以下の多項式の係数を含む。

行列形式において、誤り位置行列の逆は以下のようになる。

誤り位置行列の列が、昇冪で累乗された定数に等しいことに注意されたい。したがって、誤り位置行列をその逆で乗算することは、誤り位置（Ｘ_i）に等しいｘでσ^(j)（ｘ）を求めることと同じである。その結果が単位行列である。

誤り訂正行列を計算するために、誤り位置行列の逆が冗長ブロック位置行列で乗算される。冗長ブロック位置行列がヴァンデルモンド行列であるため、各列は昇冪で累乗された定数に等しい。これらの２つの行列をともに乗算することは、冗長ブロックの位置行列の各列の定数においてσ^(j)（ｘ）を求めることと同じである。したがって、誤り訂正行列の一般形式は以下のようになる。

分母が特定の行に対する定数であることに注意されたい。したがって、分母は（ｐ×Ｎ）回ではなくｐ回計算されるだけでよい。この誤り訂正行列は、訂正されるべきデータを残余ブロックに関連付ける。

この例示的な実施例において、誤り訂正行列は単純化／簡約化される。より具体的に、失われたデータブロックの数が冗長ブロックの最大数（Ｎ）よりも小さい場合、誤り訂正行列をより単純化できる。上で述べたように、冗長ブロックの数が誤りを有するデータブロックの数を上回る場合、余分な冗長ブロックが除去される。誤り訂正行列の大きさがｐ×ＮからＮ×Ｎの大きさに変化し、これは当初、誤り訂正行列の大きさを拡大したように見え得る。しかしながら、ここで新規の誤り訂正行列は、余分な冗長ブロックの各々に一致する自明な列を有する（なぜなら、除去された冗長ブロックの位置が、誤り位置多項式σ（ｘ）の一部であるためである）。さらに、余分な冗長ブロックが再構築されないと仮定すれば、余分な冗長ブロックに一致する各行を削除できる。これらの変更により、誤り訂正行列の大きさはｖ×ｖとなり、ここでｖは誤りを有するデータブロックの数である。したがって、誤りを有するデータブロックを再形成するための一般的な解法は、以下のようになる。

ここで、Ｚ_iは消去されなかった冗長ブロックの位置である。加えて、最も右の列ベクトルは残余ブロックの集合である。単純化された訂正行列は、訂正されるべきデータブロックを残余ブロックに関連付ける。

ｖ×ｖの行列である誤り訂正行列（Ｕ）の行ｉおよび列ｊにおける各成分についての一般的な方程式は以下の通りである。

Ｚ_jの任意の成分がＸ_kに等しい場合、Ｕの成分が０になることに注意されたい。これは、余分な冗長ブロックの位置がＸ_k内に含まれる場合に生じる。これらの列は、自明であるため含まれない。

加えて、図５を参照すると、誤り訂正行列の各成分を生成するための例示的なプロセス５０２が示される。例示的なプロセス５０２はコンピュータプログラムとして実現可能であり、このコンピュータプログラムはコンピュータ実行可能な命令を含んで記憶装置の動作を指示する。たとえば図１を参照すると、例示的なプロセス５０２（図５）は、記憶装置１０４のプロセッサ１１０の動作を指示することができる。しかしながら、例示的なプロセス５０２（図５）が特定用途向け集積回路（ＡＳＩＣ）等のハードウェアで実現され得ることを認識されたい。

例示的な実施例を説明してきたが、この発明の精神および／または範囲から逸脱することなくさまざまな変更を行なうことができる。したがってこの発明は、図面に示し上で説明した特定の形に限定されるものと解釈されるべきではない。

例示的な記憶装置に接続された例示的なホスト端末を示す図である。データブロック、冗長ブロック、および巡回冗長検査符号の集合を有する例示的なエンティティを示す図である。図２の例示的なエンティティの一部を示す図である。記憶媒体から検索されたデータを訂正するための例示的なプロセスを示す図である。誤り訂正行列の成分を生成するための例示的なプロセスを示す図である。

符号の説明

１０２ホスト端末、１０４記憶装置、１０６記憶媒体、１０８チャネルおよび読出／書込ヘッド、１１０プロセッサ、１１２誤り検出／訂正ユニット、１１４データバッファ、１１６冗長ブロック符号器／復号器、１１８ＣＲＣ符号器／復号器。

Claims

記憶媒体から検索されたデータの誤りを訂正する方法であって、
前記記憶媒体から複数のデータブロックを検索するステップと、
前記複数のデータブロックに関連する複数の冗長ブロックを前記記憶媒体から検索するステップと、
前記記憶媒体から検索されて誤りを有する１つ以上のデータブロックを識別するステップと、
誤りを有していると識別された前記１つ以上のデータブロックを除去するステップと、
誤りを有していると識別されたデータブロックの数が、検索された冗長ブロックの数よりも小さい場合、１つ以上の余分な冗長ブロックを除去し、前記検索された冗長ブロックから１つ以上の保存される冗長ブロックを保持するステップと、
検索されたデータブロックに基づいて１つ以上の新規の冗長ブロックを生成するステップと、
前記１つ以上の新規の冗長ブロックおよび前記１つ以上の保存される冗長ブロックに基づいて１つ以上の残余ブロックを生成するステップと、
生成された１つ以上の残余ブロックを用い、誤りを有していると識別された前記１つ以上のデータブロックを訂正するステップとを含む、方法。
前記記憶媒体から検索されて誤りを有する１つ以上のデータブロックを識別する前記ステップは、
検索されたデータブロックに関連するチェックサムを前記記憶媒体から検索するステップと、
前記検索されたデータブロックに基づいて新規のチェックサムを生成するステップと、
前記検索されたデータブロックが誤りを有しているかどうかを判断するために、検索されたチェックサムと前記新規のチェックサムとを比較するステップとを含む、請求項１に記載の方法。
前記チェックサムは巡回冗長符号である、請求項２に記載の方法。
誤りを有していると識別された前記１つ以上のブロックを除去する前記ステップは、誤りを有していると識別された前記１つ以上のデータブロックを消失部としてフラグ付けするステップを含む、請求項１に記載の方法。
保存される冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に等しい、請求項１に記載の方法。
前記１つ以上の新規の冗長ブロックは、誤りを有していると識別された前記１つ以上のデータブロックが除去されている前記検索されたデータブロックに基づいて生成される、請求項１に記載の方法。
新規の冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に等しい、請求項１に記載の方法。
１つ以上の残余ブロックを生成する前記ステップは、新規の冗長ブロックと検索された冗長ブロックとの間で排他的論理和演算を行なうステップを含む、請求項１に記載の方法。
前記残余ブロックはシンドロームである、請求項１に記載の方法。
残余ブロックは、検索された符号語を生成多項式で割った剰余である、請求項１に記載の方法。
誤りを有していると識別された前記１つ以上のデータブロックを訂正する前記ステップは、１つ以上の生成された残余ブロックと訂正行列との間でガロア体の行列乗算演算を行なうステップを含む、請求項１に記載の方法。
前記訂正行列は、訂正されるべき１つ以上のデータブロックを前記１つ以上の残余ブロックに関連付ける、請求項１１に記載の方法。
簡約化された訂正行列を生成するために、前記１つ以上の余分な冗長ブロックに対応する１つ以上の行を前記訂正行列から除去するステップをさらに含み、前記ガロア体の行列乗算演算は、前記訂正行列ではなく前記簡約化された訂正行列と前記１つ以上の生成された残余ブロックとの間で行なわれる、請求項１１に記載の方法。
前記簡約化された訂正行列の行の数は、誤りを有していると識別されたデータブロックの数に等しい、請求項１３に記載の方法。
前記複数の冗長ブロックは、ボース−チャウドゥーリー−オッカンガム（ＢＣＨ）符号である、請求項１に記載の方法。
ＢＣＨ符号はリード−ソロモン符号である、請求項１５に記載の方法。
記憶媒体から検索されたデータの誤りを訂正するシステムであって、
データバッファを備え、前記データバッファは、
前記記憶媒体から検索された複数のデータブロックと、
前記記憶媒体から検索された複数の冗長ブロックとを含み、前記システムはさらに、
プロセッサを備え、前記プロセッサは、
前記記憶媒体から検索されて誤りを有する１つ以上のデータブロックを識別し、
誤りを有していると識別された前記１つ以上のデータブロックを除去し、
誤りを有していると識別されたデータブロックの数が、検索された冗長ブロックの数よりも小さい場合、１つ以上の余分な冗長ブロックを除去し、前記検索された冗長ブロックから１つ以上の保存される冗長ブロックを保持し、
検索されたデータブロックに基づいて１つ以上の新規の冗長ブロックを生成し、
前記１つ以上の新規の冗長ブロックおよび前記１つ以上の保存される冗長ブロックに基づいて１つ以上の残余ブロックを生成し、
生成された１つ以上の残余ブロックを用い、誤りを有していると識別された前記１つ以上のデータブロックを訂正するように設定される、システム。
保存される冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に等しい、請求項１７に記載のシステム。
前記１つ以上の新規の冗長ブロックは、誤りを有していると識別された前記１つ以上のデータブロックが除去されている前記検索されたデータブロックに基づいて生成される、請求項１７に記載のシステム。
新規の冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に等しい、請求項１７に記載のシステム。
前記１つ以上の残余ブロックは、新規の冗長ブロックと検索された冗長ブロックとの間
で排他的論理和演算を行なうことによって生成される、請求項１７に記載のシステム。
誤りを有していると識別された前記１つ以上のデータブロックは、前記１つ以上の生成された残余ブロックと訂正行列との間でガロア体の行列乗算演算を行なうことによって訂正される、請求項１７に記載のシステム。
前記プロセッサは、簡約化された訂正行列を生成するために、前記１つ以上の余分な冗長ブロックに対応する１つ以上の行を前記訂正行列から除去するようにさらに設定され、前記ガロア体の行列乗算演算は、前記訂正行列ではなく簡約化された訂正行列と前記１つ以上の生成された残余ブロックとの間で行なわれる、請求項２２に記載のシステム。
前記簡約化された訂正行列の行の数は、誤りを有していると識別されたデータブロックの数に等しい、請求項２３に記載のシステム。
記憶媒体から検索されたデータの誤りをコンピュータに訂正させるためのコンピュータ実行可能な命令を含むコンピュータ読取可能な記憶媒体であって、
前記記憶媒体から複数のデータブロックを検索するステップと、
前記複数のデータブロックに関連する複数の冗長ブロックを前記記憶媒体から検索するステップと、
前記記憶媒体から検索されて誤りを有する１つ以上のデータブロックを識別するステップと、
誤りを有していると識別された前記１つ以上のデータブロックを除去するステップと、
誤りを有していると識別されたデータブロックの数が、検索された冗長ブロックの数よりも小さい場合、１つ以上の余分な冗長ブロックを除去し、前記検索された冗長ブロックから１つ以上の保存される冗長ブロックを保持するステップと、
前記検索されたデータブロックに基づいて１つ以上の新規の冗長ブロックを生成するステップと、
前記１つ以上の新規の冗長ブロックおよび前記１つ以上の保存される冗長ブロックに基づいて１つ以上の残余ブロックを生成するステップと、
生成された１つ以上の残余ブロックを用い、誤りを有していると識別された前記１つ以上のデータブロックを訂正するステップとを行なうための命令を含む、コンピュータ読取可能な記憶媒体。
前記記憶媒体から検索されて誤りを有する１つ以上のデータブロックを識別する前記ステップは、
検索されたデータブロックに関連するチェックサムを前記記憶媒体から検索するステップと、
前記検索されたデータブロックに基づいて新規のチェックサムを生成するステップと、
前記検索されたデータブロックが誤りを有しているかどうか判断するために、検索されたチェックサムと前記新規のチェックサムとを比較するステップとを含む、請求項２５に記載のコンピュータ読取可能な記憶媒体。
前記チェックサムは巡回冗長符号である、請求項２６に記載のコンピュータ読取可能な記憶媒体。
誤りを有していると識別された前記１つ以上のブロックを除去する前記ステップは、誤りを有していると識別された前記１つ以上のデータブロックを消失部としてフラグ付けするステップを含む、請求項２５に記載のコンピュータ読取可能な記憶媒体。
保存される冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に
等しい、請求項２５に記載のコンピュータ読取可能な記憶媒体。
前記１つ以上の新規の冗長ブロックは、誤りを有していると識別された前記１つ以上のデータブロックが除去されている前記検索されたデータブロックに基づいて生成される、請求項２５に記載のコンピュータ読取可能な記録媒体。
新規の冗長ブロックの数は、誤りを有していると識別されたデータブロックの数に等しい、請求項２５に記載のコンピュータ読取可能な記憶媒体。
１つ以上の残余ブロックを生成する前記ステップは、新規の冗長ブロックと検索された冗長ブロックとの間で排他的論理和演算を行なうステップを含む、請求項２５に記載のコンピュータ読取可能な媒体。
前記残余ブロックはシンドロームである、請求項２５に記載のコンピュータ読取可能な記憶媒体。
残余ブロックは、検索された符号語を生成多項式で割った剰余である、請求項２５に記載のコンピュータ読取可能な記憶媒体。
誤りを有していると識別された前記１つ以上のデータブロックを訂正する前記ステップは、１つ以上の生成された残余ブロックと訂正行列との間でガロア体の行列乗算演算を行なうステップを含む、請求項２５に記載のコンピュータ読取可能な記憶媒体。
前記訂正行列は、訂正されるべき１つ以上のデータブロックを前記１つ以上の残余ブロックに関連付ける、請求項３５に記載のコンピュータ読取可能な記憶媒体。
簡約化された訂正行列を生成するために、前記１つ以上の余分な冗長ブロックに対応する１つ以上の行を前記訂正行列から除去するステップをさらに含み、前記ガロア体の行列乗算演算は、前記訂正行列ではなく簡約化された訂正行列と前記１つ以上の生成された残余ブロックとの間で行なわれる、請求項３５に記載のコンピュータ読取可能な記憶媒体。
前記簡約化された訂正行列の行の数は、誤りを有していると識別されたデータブロックの数に等しい、請求項３７に記載のコンピュータ読取可能な記憶媒体。
前記複数の冗長ブロックは、ボース−チャウドゥーリー−オッカンガム（ＢＣＨ）符号である、請求項２５に記載のコンピュータ読取可能な記憶媒体。
ＢＣＨ符号はリード−ソロモン符号である、請求項３９に記載のコンピュータ読取可能な記憶媒体。