(57)【要約】予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法が開示される。方法は、選択するステップ、構成するステップ、決定するステップおよび繰り返すステップを含む。選択するステップは、システムのために予め決定された容認できる故障数を選択するステップを含む。構成するステップは、予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。決定するステップは、第１のタナーグラフから消失符号を決定するステップを含む。繰り返すステップは、システムのために予め決定された故障数に達するまで、容認できる故障数を１つ増加させて、パリティ・ノード数を増加させることにより増加した容認できる故障数に応じて別のタナーグラフを構成することによって、構成するステップおよび決定するステップを繰り返すステップを含む。【選択図】図１
2017533627.tif 000002
【特許請求の範囲】
【請求項１】
予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法であって、前記方法は、
前記システムのために予め決定された容認できる故障数を選択するステップと、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと、
前記第１のタナーグラフから第１の消失符号を決定するステップと、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定するステップによって、前記構成するステップおよび前記決定するステップを繰り返すステップであって、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで前記構成して決定するステップを繰り返す、ステップと
を備える、方法。
【請求項２】
２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップは、
前記予め決定されたデータディスク数に基づいて前記データ・ノード数を決定するステップと、
前記データ・ノード数に基づいて前記システムに必要な前記パリティ・ノード数を決定するステップと、
前記データ・ノードおよびパリティ・ノード数の和に応じて前記タナーグラフ中の前記シンボル・ノード数を決定するステップと、
前記パリティ・ノード数から前記タナーグラフ中のチェック・ノード数を決定するステップと、
前記シンボル・ノードおよびチェック・ノード数を用いることによって２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと
を備える、請求項１に記載の方法。
【請求項３】
前記システムに必要な前記パリティ・ノード数を決定するステップは、
Ａ）ノード・インデックスとして整数セットを選ぶステップと、
Ｂ）各ノードが独自のインデックスを有するように前記ノード・インデックス中のデジット数（ｄ）を決定するステップと、
Ｃ）ｄのｑ−１乗（ｄｑ−１）によって前記パリティ・ノード数を計算するステップと
を備える、請求項２に記載の方法。
【請求項４】
前記繰り返すステップは、３つの故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項５】
前記繰り返すステップは、４つの故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項６】
前記繰り返すステップは、４つを超える故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項７】
前記タナーグラフ中の前記ノード・インデックスとして選ばれる前記整数セットは、２進整数である、請求項３に記載の方法。
【請求項８】
前記タナーグラフ中の前記ノード・インデックスとして選ばれる前記整数セットは、ｑ進（底がｑの）整数である、請求項３に記載の方法。
【請求項９】
予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法をコンピュータに行わせるプログラム命令を含んだ非一時的なコンピュータ可読媒体であって、前記方法は、
前記システムのために予め決定された容認できる故障数を選択するステップと、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定するステップによって、前記構成するステップおよび前記決定するステップを繰り返すステップであって、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで前記構成して決定するステップを繰り返す、ステップと
を備える、非一時的なコンピュータ可読媒体。
【請求項１０】
システムであって、
予め決定された数のデータディスクを有する機器と、
プロセッサを有する、消失符号を定義するためのコンピュータと
を備え、前記プロセッサは、
前記システムのために予め決定された容認できる故障数を選択し、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成し、
前記第１のタナーグラフから第１の消失符号を決定し、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定することによって、前記構成することおよび前記決定することを繰り返し、前記繰り返すことは、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで構成して決定することを繰り返す
ように構成された、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権の主張
本出願は、２０１４年１０月３日出願のシンガポール特許出願第１０２０１４０６３３２号の優先権を主張する。
【０００２】
技術分野
本発明は、データ記憶システムに関する。特に、本発明は、データ記憶システムのための消失符号に関する。
【背景技術】
【０００３】
消失は、（ｎ，ｋ）パラメータのタプルによって特徴付けることができる。符号語は、総数がｎ個のシンボル／コラムを含み、それらのうちで他のｎ−ｋ個のシンボル／コラムが失われた場合にはそれらを回復するために任意のｋ個のシンボル／コラムを用いることができる。記憶システムではディスク／ノード故障を許容するために、レプリケーション、ＲＡＩＤ−５、およびリードソロモン符号のような消失符号が長らく用いられてきた。ディスク故障の際にデータ回復を可能にするために、リードソロモン符号は、最少量の冗長データを記憶する必要があり、任意のｍ個のディスク故障を許容するために正確にｍ個のディスク相当の冗長データが保存される。この特性をもつ符号は、最大距離分離（ＭＤＳ：ｍａｘｉｍｕｍ−ｄｉｓｔａｎｃｅ−ｓｅｐａｒａｂｌｅ）符号と呼ばれる。他方、レプリケーションは、元データと同じくらいかまたはそれより複数倍大きい、はるかに多量の冗長データを必要とする。しかしながら、レプリケーションは、はるかに短い回復式を有し、これは、ディスク故障の際にレプリケーションの方が高い回復効率を有することを意味する。
【０００４】
Ｆｌａｔ  ＸＯＲ符号は、レプリケーションおよびＭＤＳ符号の中間の種類の符号である。Ｆｌａｔ  ＸＯＲ符号は、専らＸＯＲ演算に対して構築される。それらは１次元の符号構造を有し、各パリティ・シンボルは、データ・シンボルのサブセットのＸＯＲ和である。Ｆｌａｔ  ＸＯＲ符号は、ＭＤＳではなく、従って空間効率がＭＤＳ符号のようにはよくない。しかしながら、Ｆｌａｔ  ＸＯＲ符号の方がはるかに短い回復式を有し、その回復効率がＭＤＳ符号よりはるかに高い。レプリケーションと比較したときには、Ｆｌａｔ  ＸＯＲ符号の方がはるかに空間効率がよいが、その回復効率は、レプリケーションほどよくない。結果として、Ｆｌａｔ  ＸＯＲ符号は、記憶効率と回復効率との間の柔軟なトレードオフを提供し、従って、設計パラメータを選択するときに記憶システムにより多くのフレキシビリティを与えることができる。
【０００５】
他の種類の非ＭＤＳ符号としては、回復効率を向上させるためにいくらかの記憶効率を犠牲にするピラミッド符号、ＷＥＡＶＥＲ符号、およびＨＯＶＥＲ符号がある。ピラミッド符号は、ＭＤＳ符号の複数のレベル上に構築され、回復は、ピラミッドを登るようにレベルごとに行われる。ＷＥＡＶＥＲおよびＨＯＶＥＲ符号は、非組織パリティ・アレイＸＯＲ符号であり、データ・コラムのすべてまたは部分がパリティ・シンボルを含む。しかしながら、これらの消失符号は、記憶効率および再構成性能が不十分である。
【０００６】
Ｆｌａｔ  ＸＯＲ符号については、Ｆｌａｔ  ＸＯＲ符号を構成するために極めて少ない方法しかなく、Ｆｌａｔ  ＸＯＲ符号の数が非常に限られる。そのうえ、既存のＦｌａｔ  ＸＯＲ符号は、３つまでの故障を許容できるに過ぎない。
【０００７】
従って、必要とされるのは、記憶効率と回復効率との間のバランスを最適化するデータ記憶システムのためのよりロバストな消失符号である。そのうえ、他の望ましい特徴および特性は、添付図面および本開示のこの背景技術と併せて考えたときに、次の詳細な記載および添付される特許請求の範囲から明らかになるであろう。
【発明の概要】
【０００８】
本発明の開示の第１の態様によれば、予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法が提供される。方法は、選択するステップ、構成するステップ、決定するステップおよび繰り返すステップを含む。選択するステップは、システムのために予め決定された容認できる故障数を選択するステップを含む。構成するステップは、予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。決定するステップは、システムのために予め決定された故障数に達するまで、容認できる故障数を１つ増加させて、パリティ・ノード数を増加させることにより増加した容認できる故障数に応じて別のタナーグラフを構成することによって、構成するステップおよび決定するステップを繰り返すステップを含む。
【０００９】
本発明の開示の第２の態様によれば、予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法をコンピュータに行わせるプログラム命令を含んだ非一時的なコンピュータ可読媒体が提供される。方法は、選択するステップ、構成するステップ、決定するステップおよび繰り返すステップを含む。選択するステップは、システムのために予め決定された容認できる故障数を選択するステップを含む。構成するステップは、予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。決定するステップは、システムのために予め決定された故障数に達するまで、容認できる故障数を１つ増加させて、パリティ・ノード数を増加させることにより増加した容認できる故障数に応じて別のタナーグラフを構成することによって、構成するステップおよび決定するステップを繰り返すステップを含む。
【００１０】
本発明の開示の第３の態様によれば、予め決定された数のデータディスクを有するシステム、および消失符号を定義するための方法を行うコンピュータが提供される。方法は、選択するステップ、構成するステップ、決定するステップおよび繰り返すステップを含む。選択するステップは、システムのために予め決定された容認できる故障数を選択するステップを含む。構成するステップは、予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。決定するステップは、システムのために予め決定された故障数に達するまで、容認できる故障数を１つ増加させて、パリティ・ノード数を増加させることにより増加した容認できる故障数に応じて別のタナーグラフを構成することによって、構成ステップおよび決定するステップを繰り返すステップを含む。
【００１１】
添付図は、同様の参照数字が別々の図にわたって同一かまたは機能的に類似した要素を参照し、以下の詳細な記載とともに本明細書に組み込まれてその部分をなしており、様々な実施形態を示して様々な原理および利点を本発明の実施形態に従って説明するのに役立つ。
【図面の簡単な説明】
【００１２】
【図１】本発明の開示によるＩＮＴ２−２符号のタナーグラフ構造の例を示す。
【図２】本発明の開示によるＩＮＴ３−２符号のタナーグラフ構造の例を示す。
【図３】本発明の開示による図１のＩＮＴ２−２符号に基づくＩＮＴ２−３符号のタナーグラフ構造の例を示す。
【図４】本発明の開示によるＩＮＴ２−３符号の最適化されたタナーグラフ構造を示す。
【図５】本発明の開示による図２のＩＮＴ３−２符号に基づくＩＮＴ３−３符号のタナーグラフ構造の例を示す。
【図６】本発明の実施形態による図３または図４のＩＮＴ２−３符号に基づくＩＮＴ２−４符号のタナーグラフ構造の例を示す。
【図７】本発明の開示に従ってタナーグラフ中のノード・インデックスを解析することによってどのようにＩＮＴ２−４符号が４つのノード故障を許容できるかを示す。
【図８】本発明の開示によるＩＮＴ２−２、ＩＮＴ２−３およびＩＮＴ２−４符号に関する最短回復式のレプリケーションおよびＭＤＳ符号に対する比較を示す。
【図９】本発明の開示によるＩＮＴ２−２、ＩＮＴ２−３およびＩＮＴ２−４符号に関する記憶オーバーヘッドのレプリケーションおよびＭＤＳ符号に対する比較を示す。
【図１０】本発明の開示に従って整数インデックス付きタナーグラフからＦｌａｔ  ＸＯＲ符号を構成する方法のためのフローチャートを示す。
【図１１】本発明の開示に従って２つの故障を容認できるシステムのために第１のタナーグラフを構成する方法のフローチャートを示す。
【図１２】本発明の開示に従って整数インデックス付きタナーグラフからｆｌａｔ  ＸＯＲ符号を構成するためのシステムを示す。
【発明を実施するための形態】
【００１３】
図中の要素は、簡潔さおよび明解さのために示され、必ずしも縮尺通りに描かれなかったことを当業者は理解するであろう。例えば、本発明の実施形態の理解を高めるのを助けるために、説明図、ブロック図またはフローチャート中のいくつかの要素の寸法が他の要素に比べて誇張されることもある。
【００１４】
以下の詳細な記載は、本質的に例示的であるに過ぎず、本発明または本発明の用途および使用を限定することは意図されない。そのうえ、前述の本発明の背景または以下の詳細な記載において提示されるいかなる理論によっても制限されるものではない。
【００１５】
本明細書では、予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法が高記憶効率および高再構成性能の利点を有する本発明の実施形態に従って提示される。
【００１６】
Ｆｌａｔ  ＸＯＲ符号に関して、その構成を記載する直観的な方法は、タナーグラフによる。タナーは、２種類のノード、シンボル・ノードおよびチェック・ノードからなる２部グラフである。シンボル・ノードは、データ・シンボルまたはパリティ・シンボルのいずれかを表し、チェック・ノードは、チェック・ノードに接続されたすべてのシンボル・ノードのＸＯＲ和がゼロであることを示す。
【００１７】
本発明の開示においては、タナーグラフの新しい構造が提案され、タナーグラフ中の各シンボル・ノードにはそのインデックスとして別個の整数が割り当てられる。これらのインデックスは、２進整数、３進整数、または一般にｑ進整数のセットとすることができる。整数の各セットに対して、対応する整数インデックス付きタナーグラフから２つの故障を許容する消失符号の新しいグループが構成される。続いて、２つの故障を許容する消失符号を３つの故障を許容する符号へ拡張するための方法が提案される。さらにまた、３つの故障を許容する符号をより多く故障を許容する符号へ拡張するための別の方法が提案される。
【００１８】
構成される消失符号（ＩＮＴ符号）は、１次元の符号構造をもつＦｌａｔ  ＸＯＲ符号である。それらを記憶システム中に統合するのは容易であり、低計算オーバーヘッドを有する。空間最適なＭＤＳ符号と比較して、ＩＮＴ符号は、記憶空間のわずかな割合を代償として回復性能を大きく向上させることができる。そのうえ、ＩＮＴ符号は、他のＸＯＲ符号と比較して以下の２つの利点を有する、すなわち、
１）ＩＮＴ符号は、任意の故障数を許容するように構成できる。現在、３つを超える故障を許容できるＸＯＲ符号はわずかしかない。
２）ＩＮＴ符号は、異なるレベルをインクリメンタルに構成できて、故障許容度の高い方のレベルへのアップグレーディングは、元の符号構造への変更を何も必要としない。
【００１９】
ＩＮＴ符号の構成は、タナーグラフの新規な形式に基づく。ｎ個のノードをもつＩＮＴ符号を構成するために、ｎ個のシンボル・ノードをもつタナーグラフが構築される。各シンボル・ノードは、ＩＮＴ符号構造においてデータまたはパリティ・ノードに対応する。次に、各シンボル・ノードにそのインデックスとして別個の整数が割り当てられる。ノード・インデックスとして２進整数のセットを選択可能である。同様に、インデックスとして３進整数または一般にｑ進整数のセットも選択可能である。異なる整数のセットに対して、構成されるＩＮＴ符号が異なるであろう。２進整数のインデックスから構成されたＩＮＴ符号がＩＮＴ２符号と示され、３進整数のインデックスから構成されたＩＮＴ符号がＩＮＴ３符号と示されるなどである。以下の記載において、ＩＮＴｘ−ｙは、底がｘの整数をノード・インデックスとして用い、ｙ個の故障を許容できるＩＮＴ符号を表す。
【００２０】
例として、ＩＮＴ２符号を用いることによってどのように２つの故障を許容するＩＮＴ符号を構成するかが示される。各２進インデックスがｍビットを有すると想定する。第１に、ｍ個のチェック・ノードがタナーグラフ中に追加される。第２に、シンボル・ノードごとのインデックスの各ビットがチェックされる。ｉ番目のビットが１であれば、シンボル・ノードは、ｉ番目のチェック・ノードに接続される。このプロセスが済んだときに、タナーグラフが構成される。結果として生じた２つのノードの故障を許容できるＩＮＴ２符号は、ＩＮＴ２−２符号と表される。
【００２１】
図１は、７つのシンボル・ノード１０２、１０４をもつＩＮＴ２−２符号１００のタナーグラフ１００の例を示す。各シンボル・ノード１０２、１０４の２進インデックスは、＜００１＞のように３ビットを有し、それゆえに３つのチェック・ノード１０６がタナーグラフ中に追加される。一般に、インデックスが連続するかまたは特定の順序になければならないという制限は何もないので、（２つの故障を許容する符号には用いられないであろう、特殊なすべてがゼロのインデックス＜０００＞を除いて）インデックスをシンボル・ノードに非常にフレキシブルに割り当てることができる。シンボル・ノード１０２、１０４は、それらのインデックスに従ってチェック・ノード１０６に接続される。例えば、パリティ・ノード１０２における第１のシンボル・ノード＜００１＞は、そのインデックスの（右から）１番目のビットが１で、すべての他のビットが０なので、チェック・ノード１０６の第１のチェック・ノード（ＣＮ１で示される）に接続される。各チェック・ノード１０６は、ＸＯＲパリティ・ストライプを表すので、図１におけるタナーグラフ１００には実際に３つのパリティ・ノード１０２がある。直接的な選択は、図１に示されるように、最初の３つのシンボル・ノードがパリティ・ノード１０２であるように選ぶことである。しかしながら、その他の選択も許される。その理由は、これらのノード１０２の各々が正しく１つのパリティ・ストライプ中のメンバーであり、互いに独立しているためである。
【００２２】
構成されたＩＮＴ２−２符号を２つのシンボル・ノード故障の任意の組み合わせから回復できることが示される。ｉ番目およびｊ番目のシンボル・ノードが失われ、それらの２進インデックスがそれぞれＩＤＸｉおよびＩＤＸｊと示されると想定する。ＩＤＸｉ≠ＩＤＸｊなので、それらのシンボル・ノードは、少なくとも１つの異なるビットを有するはずである。ｒ番目のビットにおいて、ＩＤＸｉが１であり、ＩＤＸｊが０であると想定する。タナーグラフの構成によれば、ｒ番目のチェック・ノードがｉ番目のシンボル・ノードに接続されるが、ｊ番目のシンボル・ノードには接続されないと判断できる。それゆえに、ｉ番目のシンボル・ノードがｒ番目のパリティ・ストライプにおける唯一の失われたシンボル・ノードであり、そのパリティ・ストライプ中のすべての他のシンボル・ノードのＸＯＲ和を計算することによってｉ番目のシンボル・ノードを回復できる。その後、ｊ番目のシンボル・ノードが参加するパリティ・ストライプのいずれかによってｊ番目のシンボル・ノードを回復できる。
【００２３】
２つの故障を許容するＩＮＴ３符号、すなわち、ＩＮＴ３−２符号２００を構成するプロセスは、ＩＮＴ２−２符号のそれと同様である。図２は、４つのデータ・ノード２０４および４つのパリティ・ノード２０２を含んだ、８つのシンボル・ノード２０２、２０４をもつＩＮＴ３−２符号２００の例を示す。上記に示されたように、ＩＮＴ２−２符号では、インデックス中の各ビット値１は、シンボル・ノード１０２、１０４の各々が対応するチェック・ノード１０６に接続することを示し、ビット値０は、何もしない。同様に、ＩＮＴ３−２符号では、インデックス中の各非ゼロビット値は、シンボル・ノード２０２、２０４の各々がビット値１またはビット値２に対応するチェック・ノード２０６に接続することを示し、ビット値０は、何もしない。
【００２４】
次に、２つの故障を許容するＩＮＴ符号を３つの故障を許容するＩＮＴ符号へ拡張するための方法が示される。高い方のレベルのＩＮＴ符号が低い方のレベルのＩＮＴ符号に基づいてインクリメンタルに構成されるのと同様に、３つの故障を許容するＩＮＴ符号構成は、対応する２つの故障を許容するＩＮＴ符号構成中に１つのさらなるパリティ・ノードを単に追加することによって行われる。
【００２５】
ｎ個のシンボル・ノードをもつ２つの故障を許容するＩＮＴ符号があると想定する。それを３つの故障を許容するＩＮＴ符号へアップグレードするために、２つの故障を許容するＩＮＴ符号のタナーグラフ中にもう１つのパリティ・ノードが追加され、このパリティ・ノードが元のタナーグラフ中のすべてのｎ個のシンボル・ノードのＸＯＲパリティとしてセットされる。元のタナーグラフ中のすべてのデータおよびパリティ編成は、変わらないままであり、このため、ＩＮＴ符号ベースの記憶システムに対するデータ信頼性のオンライン・アップグレーディングを大幅に簡略化できる。
【００２６】
図３は、ＩＮＴ２−３構成３００のためのタナーグラフの例を示す。図１に示されるＩＮＴ２−２タナーグラフ１００に基づいて、特殊なすべてがゼロのインデックス＜０００＞をもつ１つのシンボル・ノード３０８がタナーグラフ中に追加される。新しいチェック・ノード３１０がタナーグラフ中に追加されて、新しく追加されたシンボル・ノード３０８を含むすべてのシンボル・ノードに接続される。インデックス＜０００＞をもつ新しく追加されたシンボル・ノード３０８が新しいパリティ・ストライプのパリティ・ノードであるようにセットされる。
【００２７】
ＩＮＴ２−２と同様に、ＩＮＴ２−３の３つの故障の許容度がそのタナーグラフ中の２進インデックスによることが示される。タナーグラフ中の３つのシンボル・ノード（ＳＮｉ、ＳＮｊ、およびＳＮｙと示される）が失われ、それらのインデックスがＩＤＸｉ、ＩＤＸｊおよびＩＤＸｙであると想定する。ＩＤＸｉ≠ＩＤＸｊなので、それらは少なくとも１つの異なるビットを有するはずである。ｒ番目のビットにおいて、ＩＤＸｉが１であり、ＩＤＸｊが０であると想定すると、ＩＤＸｙは、０または１のいずれかでありうる。ＩＤＸｙのｒ番目のビットが０であれば、ＳＮｉがｒ番目のパリティ・ストライプＰｒにおける唯一の失われたノードとなり、ＰｒによってＳＮｉを回復できる。そうでない場合に、ＩＤＸｙのｒ番目のビットが１であれば、以下の２つの式を定式化できる。
ＳＮｉ＋ＳＮｙ＝ＸＯＲ＿ｓｕｍ（Ｐｒ中の他のＳＮ）
ＳＮｉ＋ＳＮｊ＋ＳＮｙ＝ＸＯＲ＿ｓｕｍ（すべての残りのＳＮ）
【００２８】
第２の式は、ＩＮＴ２−３におけるすべてのシンボル・ノードが１つの同じパリティ・ストライプ、ＩＮＴ２−２と比較して新しく追加されたパリティ・ストライプに参加するので成り立つ。第１および第２の式を組み合わせることによって、ＳＮｊを回復できる。ＩＮＴ２−２がＩＮＴ２−３に含まれるという事実に注目しよう。それゆえに、ＩＮＴ２−２回復において記載された方法に単に従って、残りの２つの失われたシンボル・ノードを確かに回復できる。
【００２９】
ＩＮＴ２−２符号において、すべてのパリティ式の左および右部分を加算すれば、次の式が得られる。
ＸＯＲ＿ｓｕｍ（インデックス中に奇数個の１をもつデータ・ノード）＝ＸＯＲ＿ｓｕｍ（パリティ・ノード）。
【００３０】
その理由は、それらのインデックス中に偶数個の１を有するデータ・ノードが式の左部分に偶数回現われることになり、それらのＸＯＲ和がゼロになるためである。他方、それらのインデックス中に奇数個の１を有するデータ・ノードは、式の左部分に奇数回現われることになり、それらのＸＯＲ和は、それらの各々が正確に１度現われる場合と同じであろう。
【００３１】
上記の式に基づいて、ＩＮＴ２−３符号のタナーグラフ構造を最適化できる。インデックス＜０００＞をもつ新しく追加されたパリティ・ノードは、次のように計算できる。
新しいパリティ・ノード＝ＸＯＲ＿ｓｕｍ（インデックス中に偶数個の１をもつデータ・ノード）
【００３２】
その理由は、新しく追加されたパリティ・ノードがＩＮＴ２−２符号におけるすべてのデータ・ノードおよびパリティ・ノードのＸＯＲ和であり、ＩＮＴ２−２符号においてインデックス中に奇数個の１をもつすべてのデータ・ノードおよびすべてのパリティ・ノードのＸＯＲ和がゼロに等しいためである。
【００３３】
図４は、ＩＮＴ２−３符号４００の最適化されたタナーグラフ構造を示す。図３における元のタナーグラフ３００と比較して、最適化されたタナーグラフ４００は、新しいチェック・ノード４１０とデータ・ノード４０４との間により少ない接続を有し、従って、より短い回復式およびより良好な回復効率を有する。
【００３４】
同様の方法で（タナーグラフ中のノード・インデックスとして整数の他のセットを選択することによって構成された）２つの故障を許容するＩＮＴ符号の他のグループを３つの故障を許容する符号へ拡張できる。図５は、ＩＮＴ３−３符号のタナーグラフ構造５００を示す。このタナーグラフ構造は、図２におけるＩＮＴ３−２タナーグラフ２００に新しいパリティ・ノード５０８を追加することによって構成される。上記の最適化方法がＩＮＴ３−３符号およびＩＮＴ符号の他のグループにも適用されるという事実に注目しよう。
【００３５】
次に、３つの故障を許容するＩＮＴ符号を４つ以上の故障を許容する符号へ拡張するための方法が開示される。第１に、どのように４つの故障を許容するＩＮＴ符号を構成するかが開示される。その後、４つの故障を許容する符号構成に非常に類似した、４つを超える故障を許容するためのＩＮＴ符号の構成に関する一般的な記載が示される。
【００３６】
４つの故障を許容するＩＮＴ符号は、３つの故障を許容するＩＮＴ符号にさらなるパリティ・ノードを追加することによって構成される。ＩＮＴ２−３符号からＩＮＴ２−４符号を構成する例による構成が示される。４つの故障を許容するＩＮＴ符号の他のグループは、同様の方法で構成できる。
【００３７】
図６は、ＩＮＴ２−４符号６００のタナーグラフを示す。このタナーグラフは、図４におけるＩＮＴ２−３タナーグラフ４００に基づいて構成される。簡単のために、点線の矩形中のＩＮＴ２−３タナーグラフの詳細な構造は、省略される。ＩＮＴ２−３タナーグラフと比較して、ＩＮＴ２−４タナーグラフは、さらに３つのパリティ・ノード６０８を含む。３つのパリティ・ノード６０８の各々は、別個のチェック・ノード６１０に接続する。これらのパリティ・ノード６０８は、他のシンボル・ノード６０２、６０４のように通常の２進インデックスを有さず、それぞれ＜ｘ１１＞、＜１ｘ１＞、および＜１１ｘ＞と示されるという事実に注目しよう。＜ｘ１１＞のようなインデックス（この例では＜０１１＞および＜１１１＞）を有するＩＮＴ２−３シンボル・ノードは、パリティ・ノード＜ｘ１１＞とともに同じチェック・ノードに接続する。同様のルールが他の２つのパリティ・ノード＜１ｘ１＞および＜１１ｘ＞ならびにデータ・ノードに適用される。
【００３８】
一般に、ＩＮＴ２−３タナーグラフ４００に基づいてＩＮＴ２−４タナーグラフ６００を構成するためには、総数がｍ−ｃｈｏｏｓｅ−２個のパリティ・ノードがタナーグラフ中に追加され、ここでｍは、２進インデックス中のビット数である。これらのパリティ・ノードの各々は、２進インデックス中の２ビットの組み合わせに対応し、別個のチェック・ノードに接続される。ＩＮＴ２−３シンボル・ノードの２進インデックスが２ビットのある組み合わせにおいて１１であれば、そのシンボル・ノードは、対応するパリティ・ノードとともに同じチェック・ノードに接続される。すべてのＩＮＴ２−３シンボル・ノードを対応するチェック・ノードに接続した後に、ＩＮＴ２−４のタナーグラフが構成される。
【００３９】
５つ以上の故障を許容するためのＩＮＴ２符号の構成は、ＩＮＴ２−４と非常に類似している。２進インデックスは、ＩＮＴ２符号タナーグラフを構成するときの主要な構成要素である。４つの故障を許容するためのＩＮＴ２−４を構成するために、２ビットの組み合わせ１１が利用される。さらに多くの故障を許容するためには、ビットの組み合わせをさらに活用する必要がある。例えば、ＩＮＴ２−５を構成するために、シンボル・ノードのインデックス中の各２ビットの組み合わせがさらにチェックされて、その値が１０であれば、そのシンボル・ノードが新しいチェック・ノードに接続される。それに応じて、ｍ−ｃｈｏｏｓｅ−２個の新しいチェック・ノードおよびｍ−ｃｈｏｏｓｅ−２個の新しいパリティ・ノードがタナーグラフ中に追加される。ＩＮＴ２−５に基づいて、各２ビットの組み合わせがチェックされて、値が０１の場合にシンボル・ノードが新しいチェック・ノードに接続されれば、６つの故障の許容度が達成されるであろう。なおさらに、各２ビットの組み合わせを値００と比較して、より多くのチェック・ノードを追加すると、７つの故障の許容度につながるであろう。８つの故障の許容度については、必要なのは、シンボル・ノード・インデックス中の各３ビットの組み合わせをチェックして、ｍ−ｃｈｏｏｓｅ−３個の新しいチェック・ノードをタナーグラフ中に追加するように進めることである。
【００４０】
要約すると、４つ以上の故障を許容するために、各シンボル・ノード・インデックス中のビットの組み合わせの値をチェックする必要がある。もう１つの故障を許容するために、もう１つのタイプの値（例えば、１１，１０，０１，００，１１１，・・・）がチェックされて、対応する数（すなわち、ｉビットの組み合わせに対してｍ−ｃｈｏｏｓｅ−ｉ個）の新しいチェック・ノードおよび新しいパリティ・ノードがタナーグラフに追加される。各パリティ・ノードが別個のチェック・ノードに接続されて、各シンボル・ノードがその２進インデックスの実際の値に従ってチェック・ノードに接続される。
【００４１】
次に、どのようにＩＮＴ２−４〜ＩＮＴ２−７の正しさを証明するかが示される。ＩＮＴ２−８以降の正しさは、同様の方法で証明できる。ＩＮＴ２符号の異なるレベルにわたるインクリメンタルな構成のおかげで、すべての故障が元のＩＮＴ２−３符号構造において生じるケースを証明するだけで十分である。その理由がＩＮＴ２−４を例として示すことによって説明される。４つの故障がＩＮＴ２−４タナーグラフにおいて生じると想定する。１つ以上の故障がＩＮＴ２−４の追加のパリティ・ノード（例えば、図６における＜ｘ１１＞、＜１ｘ１＞および＜１１ｘ＞）において生じるならば、元のＩＮＴ２−３構造は、３つを超えない故障を有するはずである。その場合には、ＩＮＴ２−３構造におけるすべての故障を回復できて、その後に追加のパリティ・ノードにおけるすべての他の故障も回復できる。
【００４２】
すべての故障が元のＩＮＴ２−３構造において生じると想定する。第１に、故障シンボル・ノードのすべてのインデックスが同じではない、２進インデックス中のビット位置のセットとして識別ビットセット（Ｄｉｆｆｅｒｅｎｔｉａｔｅ  Ｂｉｔ  Ｓｅｔ）Ｄが定義される。Ｄは、昇順｛ｒ１，ｒ２，．．．｝に分類されると仮定する。ｒ１番目のビットにおける値に従って、故障シンボル・ノードのインデックスが２つのグループＧ１およびＧ０に分割される。インデックスのｒ１番目のビットが１であれば、そのインデックスがＧ１に置かれる。そうでない場合には、そのインデックスがＧ０に置かれる。２つのグループの故障許容能力（Ｆａｉｌｕｒｅ  Ｔｏｌｅｒａｎｃｅ  Ａｂｉｌｉｔｙ）としてＦＴ１およびＦＴ０が定義される。ＦＴ１（またはＦＴ０）の意味は、Ｇ１（またがＧ０）中のインデックスの数がＦＴ１（またはＦＴ０）を超えなければ、そのグループにおけるシンボル・ノードの少なくとも１つを回復できて、そうでない場合には、それらのどれも回復できない可能性があるということである。表１は、ＩＮＴ２−４〜ＩＮＴ２−７に対するＦＴ１およびＦＴ０の値を示す。
【００４３】
【表１】
2017533627.tif 000003
【００４４】
一例としてＩＮＴ２−４を挙げる。４つのシンボル・ノードが故障して、それらのインデックスがＩＤＸｉ、ＩＤＸｊ、ＩＤＸｙおよびＩＤＸｚであると仮定する。図７は、４つのインデックスのグループＧ１およびＧ０への起こりうる分割を示す。破線より上のインデックスは、それらがｒ１のビット位置でビット値１を有するので、Ｇ１に属する。同様に、破線の下のインデックスは、Ｇ０に属する。第１に、以下の２つの式が定式化される。
ＸＯＲ＿ｓｕｍ（Ｇ１中のＳＮ）＝ＸＯＲ＿ｓｕｍ（Ｐｒ１中の他のＳＮ）
ＸＯＲ＿ｓｕｍ（Ｇ１およびＧ０中のＳＮ）＝ＸＯＲ＿ｓｕｍ（ＩＮＴ２−３中の他のＳＮ）
【００４５】
第１の式は、Ｇ０を除くＧ１中のすべてのシンボル・ノードがパリティ・ストライプＰｒ１に参加するので成り立つ。第２の式は、ＩＮＴ２−３におけるすべてのシンボル・ノードが１つの同じパリティ・ストライプ（図３に示されるようなパリティ・ノード＜０００＞）に参加するので成り立つ。次に、ＦＴ１が２であることが証明される、すなわち、Ｇ１中に２つを超えないシンボル・ノードがあれば、それらのすべてを回復できる。図７（ａ）に示されるようにＧ１中に１つだけのシンボル・ノードがあれば、第１の式によって直接にそれを回復できる。図７（ｂ）に示されるように、Ｇ１中に２つのインデックス、ＩＤＸｉおよびＩＤＸｊがあると想定する。ＩＤＸｉ≠ＩＤＸｊなので、それらは、少なくとも１つの異なるビット（例えば、ｒｔ番目のビット）を有するはずである。ｒ１およびｒｔの２ビットの組み合わせについては、ＩＤＸｉが値１１を有し、ＩＤＸｊが値１０を有する。明らかに、ＩＮＴ２−４における追加のパリティ・ストライプによってｉ番目のシンボル・ノードを回復できる。その後、第１の式によってｊ番目のシンボル・ノードを回復できる。しかしながら、図７（ｃ）に示されるように、Ｇ１中に３つ以上のインデックスがあれば、その時にはシンボル・ノードのどれも回復できない可能性がある。それゆえに、Ｇ１の故障許容能力ＦＴ１は、２である。同様に、Ｇ０の故障許容能力ＦＴ０は、１であることが証明される。第１および第２の式を組み合わせることによって、Ｇ０中のすべてのＳＮ（シンボル・ノード）のＸＯＲ和が得られる。Ｇ０中にただ１つのインデックスがあれば、対応するシンボル・ノードを明らかに回復できる。そうでない場合に、Ｇ０中に２つ以上のインデックスがあれば、それらのどれも回復できない可能性がある。それゆえに、Ｇ０のＦＴ０は、１である。
【００４６】
実際、新しいタイプの値がチェックされて、新しいチェック・ノードおよびパリティ・ノードがタナーグラフに追加されたときには、ＦＴ１またはＦＴ０のいずれかが１つ増加することになる。ＩＮＴ２符号の総合的な故障許容能力は、ＦＴで示され、次の式によって計算できる。
ＦＴ＝ＦＴ１＋ＦＴ０＋１
【００４７】
故障シンボル・ノードの総数がＦＴ以下であるときには、Ｇ１およびＧ０中のインデックスの数がそれらの故障許容能力ＦＴ１およびＦＴ０を同時には超過しないことが保証される。それゆえに、Ｇ１またはＧ０のいずれかにおいて少なくとも１つの故障シンボル・ノードを回復できる。第１の故障ノードが回復したときには、その後にすべての残りの故障ノードを回復できる。その理由は、ＩＮＴ符号のタナーグラフが、低い方のレベルのＩＮＴ符号が高い方のレベルのＩＮＴ符号中に一部分として含まれる、入れ子のように構成されるためである。
【００４８】
図８は、ＩＮＴ２−２（８０２）、ＩＮＴ２−３（８０４）およびＩＮＴ２−４（８０６）符号に関する最短回復式８００のレプリケーション８１０およびＭＤＳ符号８０８に対する比較を示す。回復式が短いほど、回復効率が高いことを意味する。レプリケーション８１０に関する回復式の長さは、最適値１のままである。ＭＤＳ符号８０８に関する回復式の長さは、データ・ノード数とともに線形的に増加する。ＩＮＴ符号に関しては、最短回復式の平均の長さがレプリケーション８１０とＭＤＳ符号８０８との間にある。故障許容度のレベルが高いＩＮＴ符号ほど、短い回復式を有する。４つ以上の故障を許容するＩＮＴ符号では、回復式の長さが最適値１へ徐々に減少する。例えば、ＩＮＴ２−２（８０２）およびＩＮＴ２−３（８０４）に関する最短回復式は、ＭＤＳ符号８０８に関する式と比較して４４％減少する。ＩＮＴ２−４（８０６）に関する最短回復式は、ＭＤＳ符号８０８に関する式と比較して８０％減少する。
【００４９】
図９は、ＩＮＴ２−２（９０４）、ＩＮＴ２−３（９１４）、およびＩＮＴ２−４（９２４）符号に関する記憶オーバーヘッド９００、９１０、９２０の対応するレプリケーション９０２、９１２、９２２およびＭＤＳ符号９０６、９１６、９２６に対する比較を示す。記憶オーバーヘッドが低いほど、記憶効率が高いことを意味する。レプリケーションは、最も高い記憶オーバーヘッドを有し、ｎ個の故障を許容するためにｎ倍の記憶スペースを費やす。ＭＤＳ符号は、最も低い記憶オーバーヘッドを有する。ＩＮＴ符号９０４、９１４、９２４の記憶オーバーヘッドは、レプリケーション９０２、９１２、９２２とＭＤＳ符号９０６、９１６、９２６との間であり、ＭＤＳ符号９０６、９１６、９２６の最も低いオーバーヘッドに非常に近い。
【００５０】
ＭＤＳ符号と比較して、本開示によるＩＮＴ符号は、図９に示されるように記憶スペースの僅かな割合を失うに過ぎない。しかしながら、本開示によるＩＮＴ符号は、図８に示されるようにはるかに良好な再構成性能を有する。
【００５１】
レプリケーションと比較して、本開示によるＩＮＴ符号は、図９に示されるように依然としてはるかに空間効率がよい。いくつかのケースでは、本開示によるＩＮＴ符号の再構成性能は、図８に示されるようにレプリケーション近くまで向上する。
【００５２】
上記の説明に鑑みて、本開示による消失符号は、高記憶効率および高再構成性能の利点を有する。
【００５３】
図１０は、予め決定された数のデータディスクを有するシステムのために消失符号を定義するための方法のフローチャート（１０００）を示す。方法は、選択するステップ１００２、構成するステップ１００４、決定するステップ１００６および繰り返すステップ１００８を含む。
【００５４】
選択するステップ１００２は、システムのために予め決定された容認できる故障数を選択するステップを含む。例えば、図１におけるＩＮＴ２−２符号１００および図２におけるＩＮＴ３−２符号２００は、２つのノード故障を許容できる。図３におけるＩＮＴ２−３符号３００および図５におけるＩＮＴ３−３符号５００は、３つのノード故障を許容できる。図６におけるＩＮＴ２−４符号６００は、４つのノード故障を許容できる。
【００５５】
構成するステップ１００４は、予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。図１１を参照してこのステップがさらに詳細に説明される。
【００５６】
決定するステップ１００６は、第１のタナーグラフから消失符号を決定するステップを含む。このステップでは、タナーグラフ中のシンボル・ノード・インデックスとしての２進整数のセットに対するＩＮＴ２−２符号１００、およびタナーグラフ中のシンボル・ノード・インデックスとしての３進整数のセットに対するＩＮＴ３−２符号２００のように、２つの故障を許容する消失符号が、対応する整数インデックス付きタナーグラフから構成される。
【００５７】
繰り返すステップ１００８は、システムのために予め決定された故障数に達するまで、容認できる故障数を１つ増加させて、パリティ・ノード数を増加させることにより増加した容認できる故障数に応じて別のタナーグラフを構成することによって、構成するステップおよび決定するステップを繰り返すステップを含む。この繰り返すステップでは、ステップ１００６において決定された２つの故障を許容する消失符号がＩＮＴ２−３およびＩＮＴ３−３のように３つの故障を許容する消失符号へ拡張される。さらにまた、３つの故障を許容する消失符号がＩＮＴ２−４のような４つの故障を許容する消失符号へ拡張される。
【００５８】
図１１は、図１０のステップ１００４にも記載された、２つの故障を容認できるシステムのために第１のタナーグラフを構成するための方法のフローチャート（１１００）を示す。方法は、決定するステップ１１０２、１１０４、１１０６、１１０８および構成するステップ１１１０を含む。
【００５９】
決定するステップ１１０２は、予め決定されたデータディスク数に基づいてデータ・ノード数を決定するステップを含む。本開示の例には４つのデータ・ノードがあるが、同様の実装を任意の数のデータ・ノードをもつ消失符号に適用できる。
【００６０】
決定するステップ１１０４は、ステップ１１０２において決定されたデータ・ノード数に基づいてシステムに必要とされるパリティ・ノード数を決定するステップを含む。例えば、図１ではパリティ・ノード数が３である。図１では最初の３つのノードがパリティ・ノードとして選択されるが、任意の他の方法でパリティ・ノードを配置できる。その理由は、これらのノードの各々が正しく単一のパリティ・ストライプに参加し、互いに独立しているためである。
【００６１】
決定するステップ１１０６は、ステップ１１０２および１１０４において決定されたデータ・ノード数およびパリティ・ノード数の和に応じてタナーグラフ中のシンボル・ノード数を決定するステップを含む。例えば、図１ではシンボル・ノード数が７であり、これは、４つのデータ・ノードおよび３つのパリティ・ノードの和である。各シンボル・ノードにはそのインデックスとして別個の整数が割り当てられる。２進整数、３進整数、または一般にｑ進整数のセットをインデックスとして選択できる。
【００６２】
決定するステップ１１０８は、ステップ１１０４において決定されたパリティ・ノード数からタナーグラフ中のチェック・ノード数を決定するステップを含む。一例では、ノード・インデックスとして２進整数のセットが選択され、各シンボル・ノードの２進インデックスがｍビットを有すれば、タナーグラフ中にｍ個のチェック・ノードが追加される。図１では、各シンボル・ノードの２進インデックスが３ビットを有し、タナーグラフ中に３つのチェック・ノードが追加される。
【００６３】
構成するステップ１１１０は、ステップ１１０６において決定されたシンボル・ノード数およびステップ１１０８において決定されたチェック・ノード数を用いることによって、２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップを含む。シンボル・ノードは、それらのインデックスに従ってチェック・ノードに接続される。一般に、インデックスが連続するかまたは特定の順序になければならないという制限は何もないので、インデックスを非常にフレキシブルにシンボル・ノードに割り当てることができる。それゆえに、異なる整数のセットおよびシンボル・ノードにインデックスを割り当てる異なる方法に対して異なるタイプの第１のタナーグラフを構成できる。
【００６４】
記載される実施形態例の方法およびシステムは、図１２に概略的に示される、コンピュータシステム１２００上に実装できる。これらの方法およびシステムは、ソフトウェア、例えば、コンピュータシステム１２００内で実行されてコンピュータシステム１２００に実施形態例の方法を実施するように命令するコンピュータプログラムとして実装されてもよい。
【００６５】
以下の記載のいくつかの部分は、コンピュータメモリ内のデータに対する操作のアルゴリズムおよび関数的または記号的表現の観点から明示的または暗黙的に提示される。これらのアルゴリズム的記述および関数的または記号的表現は、データ処理技術分野の当業者が彼らの仕事の実体を最も効果的に他の当業者に伝えるために用いられる手段である。アルゴリズムは、本明細書において、および一般に、所望の結果に導く自己矛盾のないステップのシーケンスであると考えられる。これらのステップは、記憶、転送、結合、比較されるか、そうでない場合は操作されることが可能な電気的、磁気的または光学的信号などの物理量の物理的操作を必要とするステップである。
【００６６】
具体的に別に明記されない限り、以下から明らかなように、本明細書を通して、「選択する」、「構成する」、「決定する」、「繰り返す」、「選ぶ」、「計算する」などの用語を活用した考察は、コンピュータシステム内の物理量として表されたデータを操作して、コンピュータシステムもしくは他の情報記憶、送信またはディスプレイ・デバイス内の物理量として同様に表された他のデータへ変換するコンピュータシステム、または同様の電子デバイスの動作および処理を参照することが理解されるであろう。
【００６７】
本明細書は、方法の操作を行うための機器も開示する。かかる機器は、必要な目的のために特に構成されてもよく、あるいはコンピュータに記憶されたコンピュータプログラムによって選択的にアクティブ化または再構成される汎用コンピュータまたは他のデバイスを備えてもよい。本明細書に提示されるアルゴリズムおよびディスプレイは、いずれか特定のコンピュータまたは他の機器に本質的に関係していない。本明細書の教示によるプログラムとともに様々な汎用機械が用いられてもよい。代わりに、必要な方法ステップを行うためにより特化した機器の構成が適切なこともある。以下の記載から従来型汎用コンピュータの構造が明らかになるであろう。
【００６８】
加えて、本明細書は、コンピュータプログラムも暗黙的に開示し、本明細書に記載される方法の個々のステップがコンピュータコードによって実施されてもよいことは当業者に明らかであろう。このコンピュータプログラムは、いずれか特定のプログラム言語およびその実装に限定されることは意図されない。当然のことながら、本明細書に含まれる開示の教示を実装するために様々なプログラム言語およびそれらのコーディングが用いられてもよい。そのうえ、このコンピュータプログラムは、いずれか特定の制御フローに限定されることは意図されない。本発明の精神および範囲から逸脱することなく異なる制御フローを用いることができるコンピュータプログラムの多くの他の変形形態がある。
【００６９】
そのうえ、このコンピュータプログラムのステップの１つ以上は、順次ではなく並列に行われてもよい。かかるコンピュータプログラムが任意のコンピュータ可読媒体上に記憶されてもよい。コンピュータ可読媒体は、記憶デバイス、例えば、磁気もしくは光ディスク、メモリチップ、または汎用コンピュータとインターフェースで接続するのに適した他の記憶デバイスを含んでもよい。コンピュータ可読媒体は、インターネットシステムで例示されるようなハードワイアード媒体、またはＧＳＭ（登録商標）移動電話システムで例示されるようなワイヤレス媒体も含んでもよい。このコンピュータプログラムは、かかる汎用コンピュータ上に読み込まれて実行されたときに好ましい方法のステップを実装する機器を効果的にもたらす。
【００７０】
コンピュータシステム１２００は、コンピュータモジュール１２０２、キーボード１２０４およびマウス１２０６のような入力モジュール、ならびにディスプレイ１２０８およびプリンタ１２１０のような複数の出力デバイスを備える。
【００７１】
コンピュータモジュール１２０２は、例えば、インターネットまたはローカルエリアネットワーク（ＬＡＮ：Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）もしくはワイドエリアネットワーク（ＷＡＮ：Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）のような他のネットワークシステムへのアクセスを可能にするために、適切なトランシーバデバイス１２１４を介してコンピュータネットワーク１２１２へ接続される。
【００７２】
本例におけるコンピュータモジュール１２０２は、プロセッサ１２１８、ランダムアクセスメモリ（ＲＡＭ：Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２２０およびリードオンリメモリ（ＲＯＭ：Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２２２を含む。コンピュータモジュール１２０２は、いくつかの入力／出力（Ｉ／Ｏ）インターフェース、例えば、ディスプレイ１２０８へのＩ／Ｏインターフェース１２２４、およびキーボード１２０４へのＩ／Ｏインターフェース１２２６も含む。
【００７３】
コンピュータモジュール１２０２のコンポーネントは、典型的に、相互接続されたバス１２２８を介して当業者に知られた仕方で通信する。一例では、予め決定された数のデータ・ノード１２３２が相互接続バス１２２８を介してコンピュータシステム１２００へ接続される。
【００７４】
アプリケーションプログラムは、典型的に、ＣＤ−ＲＯＭまたはフラッシュメモリ・キャリアのようなデータ記憶媒体上にエンコードされてコンピュータシステム１２００のユーザへ供給され、データ記憶デバイス１２３０の対応するデータ記憶媒体ドライブを利用して読み出される。アプリケーションプログラムは、その実行のときにプロセッサ１２１８によって読み出されて制御される。プログラムデータの中間記憶は、ＲＡＭ１２２０を用いて達成されてもよい。
【００７５】
本発明の前述の詳細な記載では例示的な実施形態が提示されたが、当然のことながら、膨大な数の変形形態が存在する。例えば、当業者は、本明細書における教示から本技術が他のタイプの消失符号の任意の部分に適用されてもよいことを理解するであろう。
【００７６】
さらに当然のことながら、これらの例示的な実施形態は、例であるに過ぎず、いかなる意味でも本発明の範囲、適用性、動作、または構成を限定することは意図されない。もしろ、前述の詳細な記載は、本発明の例示的な実施形態を実装するための便利なロードマップを当業者に提供するであろう、理解すべきは、添付の特許請求の範囲に提示される本発明の範囲から逸脱することなく、例示的な実施形態に記載される要素の機能および配置ならびに動作の方法における様々な変更がなされてもよいことである。
【図１】
2017533627.tif 000004
【図２】
2017533627.tif 000005
【図３】
2017533627.tif 000006
【図４】
2017533627.tif 000007
【図５】
2017533627.tif 000008
【図６】
2017533627.tif 000009
【図７】
2017533627.tif 000010
【図８】
2017533627.tif 000011
【図９】
2017533627.tif 000012
【図１０】
2017533627.tif 000013
【図１１】
2017533627.tif 000014
【図１２】
2017533627.tif 000015
【手続補正書】
【提出日】平成28年5月16日(2016.5.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
予め決定された数のデータディスクを有するシステムのためにｆｌａｔ  ＸＯＲ消失符号を定義するための方法であって、前記方法は、
前記システムのために予め決定された容認できる故障数を選択するステップと、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと、
前記第１のタナーグラフから第１の消失符号を決定するステップと、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定するステップによって、前記構成するステップおよび前記決定するステップを繰り返すステップであって、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで前記構成して決定するステップを繰り返す、ステップと
を備える、方法。
【請求項２】
２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップは、
前記予め決定されたデータディスク数に基づいて前記データ・ノード数を決定するステップと、
前記データ・ノード数に基づいて前記システムに必要な前記パリティ・ノード数を決定するステップと、
前記データ・ノードおよびパリティ・ノード数の和に応じて前記タナーグラフ中の前記シンボル・ノード数を決定するステップと、
前記パリティ・ノード数から前記タナーグラフ中のチェック・ノード数を決定するステップと、
前記シンボル・ノードおよびチェック・ノード数を用いることによって２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと
を備える、請求項１に記載の方法。
【請求項３】
前記システムに必要な前記パリティ・ノード数を決定するステップは、
Ａ）ノード・インデックスとして整数セットを選ぶステップと、
Ｂ）各ノードが独自のインデックスを有するように前記ノード・インデックス中のデジット数（ｄ）を決定するステップと、
Ｃ）ｄのｑ−１乗（ｄｑ−１）によって前記パリティ・ノード数を計算するステップと
を備える、請求項２に記載の方法。
【請求項４】
前記繰り返すステップは、３つの故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項５】
前記繰り返すステップは、４つの故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項６】
前記繰り返すステップは、４つを超える故障を容認できるシステムを構成するために前記タナーグラフ中に前記増加した数のパリティ・ノードおよび増加した数のチェック・ノードの両方を追加するステップをさらに備える、請求項１に記載の方法。
【請求項７】
前記タナーグラフ中の前記ノード・インデックスとして選ばれる前記整数セットは、２進整数である、請求項３に記載の方法。
【請求項８】
前記タナーグラフ中の前記ノード・インデックスとして選ばれる前記整数セットは、ｑ進（底がｑの）整数である、請求項３に記載の方法。
【請求項９】
予め決定された数のデータディスクを有するシステムのためにｆｌａｔ  ＸＯＲ消失符号を定義するための方法をコンピュータに行わせるプログラム命令を含んだ非一時的なコンピュータ可読媒体であって、前記方法は、
前記システムのために予め決定された容認できる故障数を選択するステップと、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成するステップと、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定するステップによって、前記構成するステップおよび前記決定するステップを繰り返すステップであって、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで前記構成して決定するステップを繰り返す、ステップと
を備える、非一時的なコンピュータ可読媒体。
【請求項１０】
システムであって、
予め決定された数のデータディスクを有する機器と、
プロセッサを有する、ｆｌａｔ  ＸＯＲ消失符号を定義するためのコンピュータと
を備え、前記プロセッサは、
前記システムのために予め決定された容認できる故障数を選択し、
前記予め決定された数のデータディスクを有する２つの故障を容認できるシステムのために第１のタナーグラフを構成し、
前記第１のタナーグラフから第１の消失符号を決定し、
前記容認できる故障数を１つ増加させて、（ａ）前記増加した容認できる故障数および増加したパリティ・ノード数に応じて別のタナーグラフを構成し、（ｂ）前記構成されたタナーグラフから後続の消失符号を決定することによって、前記構成することおよび前記決定することを繰り返し、前記繰り返すことは、前記システムのために前記予め決定された故障数に対して消失符号が決定されるまで構成して決定することを繰り返す
ように構成された、
システム。
【国際調査報告】
2017533627.tif 000016
2017533627.tif 000017