(57)【要約】【課題】  ３次元データ記憶媒体内に記憶された符号化データのワード総数に対するデータワードの比率を高くする。【解決手段】  本発明の一実施の形態は、３次元データ記憶媒体にデータを符号化する、空間効率のよい技法である。本発明の一実施の形態は、３次元データ記憶媒体のクラスの障害モードの認識および特徴付けと、一定のエラー制御符号化技法の選択および組み合わせと、選択して組み合わせたエラー制御符号化技法を使用して、３次元データ記憶媒体のクラスの一定の障害モードの検出および訂正を行う方法の実施とを含む。【選択図】図１
2004334845.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ記憶ユニット（１０２）を含む３次元データ記憶ボリューム（１００）にデータを符号化する方法であって、
データの列を受け取ることと、
線形積符号（８０２、８０４〜８０６）を使用してデータ（９０２、１１０４）をデータ値の符号配列（１１０２）に符号化し、かつ、２つの線形ブロック符号（７０４）を使用してデータ（１７０２、２１０６）をデータ値のベクトル（１７０８、２１０８）に符号化することにより、前記データの列を符号化することと
を含む３次元データ記憶ボリュームにデータを符号化する方法。
【請求項２】
前記データの列の受け取ることは、
データ値の順序列を受け取ること
をさらに含み、
各データ値（５０２）は、体から選択された要素である
請求項１に記載の３次元データ記憶ボリュームにデータを符号化する方法。
【請求項３】
前記受け取った元のデータが、前記３次元データ記憶ボリュームのサブボリューム（１３０２）内で平文の形で現れ、前記符号配列（１００２）が、前記３次元データ記憶ボリューム内で平面として記憶され、かつ、前記ベクトル（１７０８、２１０８）が、符号配列データ値をすでに含んでいるデータ記憶ユニットに記憶されるように、前記符号化されたデータを前記３次元データ記憶ボリューム（１００）に記憶すること
をさらに含む請求項１に記載の３次元データ記憶ボリュームにデータを符号化する方法。
【請求項４】
前記３次元データ記憶ボリューム（１００）の前記データ記憶ユニット（１０２）は、３つの座標軸ｘ、ｙ、およびｚ（１０６、１０８、１１０）に関して、ｘ方向の０からｎｘ−１の範囲、ｙ方向の０からｎｙ−１の範囲、およびｚ方向の０からｎｚ−１の範囲のデータ記憶インデックスによってインデックスされ、
前記線形ブロック符号は、
ｋｘｋｙ個のデータ値を、ｒｘｒｙ個のパリティチェック値を有する寸法ｎｘｎｙの符号配列に符号化する積符号ＣｘＣｙ（８０２、８０４〜８０６）と、
ｋｚ個のデータ値（１７０６）を、ｒｚ＝ｎｚ−ｋｚ個のパリティチェック値を有する長さｎｚのベクトル（１７０８）に符号化する線形ブロック符号（７０４）Ｃｚと、
ｋｚ'個のデータ値（２１０６）を、ｒｚ'個のパリティチェック値を有する長さｎｚのベクトル（２１０８）に符号化する線形ブロック符号（７０４）Ｃｚ'と
を含み、
ｋｘｋｙ（ｎｚ−１）個のデータ値は、ｚ軸座標０を有する平面から開始するｚ方向に対して垂直なｎｚ−１個の平面（１００２）に符号化され、
ｋｚ'（ｎｘｎｙ−ｎｘ−ｎｙ＋１−ｋｘｋｙ）個のデータ値は、１とｒｘ−１との間のｘ軸座標を有するｘ方向に対して垂直な平面（１８０２）、および、１とｒｙ−１との間のｙ軸座標を有するｙ方向に対して垂直な平面（２００２）に符号化され、
ｋｚ（ｎｘ＋ｎｙ＋１）個のデータ値は、ｘ軸座標０を有するｘ方向に対して垂直な平面（２２０２）、および、ｙ軸座標０を有するｙ方向に垂直な平面に符号化される
請求項３に記載の３次元データ記憶ボリュームにデータを符号化する方法。
【請求項５】
コンピュータ可読媒体内に符号化された
請求項１に記載の方法を実施するコンピュータ命令。
【請求項６】
請求項１に記載の方法を実施して、データ値を３次元データ記憶ボリューム（１００）に符号化するコンピュータ命令
を実行するコンピュータ。
【請求項７】
３次元データ記憶ボリューム（１００）であって、
請求項１に記載の方法によって符号化されたデータ
を含む３次元データ記憶ボリューム。
【請求項８】
複数のデータ記憶ユニットを含む３次元データ記憶ボリューム
【数１】
2004334845.tif 000061
（２６０４）のデータを復号する方法であって、
前記３次元データ記憶ボリューム
【数２】
2004334845.tif 000062
内のデータ値の符号化に使用された積符号（８０２、８０４〜８０６）に関連したパリティチェック行列（２６０６）の転置行列を使用して初期シンドロームボリューム（２６１０）を計算することと、
前記初期シンドロームボリューム内のベクトルに復号器を適用することにより、前記初期シンドロームボリュームから２次シンドロームボリュームを計算することと、
前記２次シンドロームボリュームおよび
【数３】
2004334845.tif 000063
の平面から、前記３次元データ記憶ボリューム
【数４】
2004334845.tif 000064
内の複数の平面破損エラーを判断することと、
平面破損エラーが検出されると、エラーボリュームを計算して、該エラーボリュームを３次元データ記憶ボリューム
【数５】
2004334845.tif 000065
から減算することにより、該平面破損エラーを訂正することと
とを含む３次元データ記憶ボリュームのデータを復号する方法。
【請求項９】
線形ブロック復号器を使用して、前記初期シンドロームボリュームおよび前記完成した２次シンドロームボリュームから差分シンドロームボリュームを計算することと、
前記差分シンドロームボリュームからエラーボリュームを計算して、該エラーボリュームを前記３次元データ記憶ボリューム
【数６】
2004334845.tif 000066
から減算することにより、前記３次元データ記憶ボリューム
【数７】
2004334845.tif 000067
内の十字交差（４０２、４０４、４０６）エラーを訂正することと
をさらに含む請求項８に記載の３次元データ記憶ボリュームのデータを復号する方法。
【請求項１０】
前記３次元データ記憶ボリューム
【数８】
2004334845.tif 000068
の前記データ記憶ユニットは、３つの座標軸ｘ、ｙ、およびｚ（１０６、１０８、１１０）に関して、ｘ方向の０からｎｘ−１の範囲、ｙ方向の０からｎｙ−１の範囲、およびｚ方向の０からｎｚ−１の範囲のデータ記憶インデックスによってインデックスされ、
前記ｚ方向に対して垂直な前記初期シンドロームボリューム
【数９】
2004334845.tif 000069
（２６０８）および
【数１０】
2004334845.tif 000070
の平面は、
【数１１】
2004334845.tif 000071
および
【数１２】
2004334845.tif 000072
によって、パリティチェック行列（２６０６）の転置行列から計算され、
２次シンドロームボリュームＳｘおよびＳｙは、ｚ方向の
【数１３】
2004334845.tif 000073
および
【数１４】
2004334845.tif 000074
内のベクトルを線形ブロック復号器Ｄｔｚを使用して復号することにより、前記初期シンドロームボリュームから計算され、
初期の個数の平面破損エラーは、ゼロでない値を含むｚ方向に対して垂直なＳｘおよびＳｙの平面の個数によって決定され、
ｚ軸座標０を有する前記ｚ方向に対して垂直な
【数１５】
2004334845.tif 000075
の前記平面が、ゼロでない場合、平面破損エラーの個数は、線形ブロック復号器Ｄ１ｚ'によって復号された
【数１６】
2004334845.tif 000076
および
【数１７】
2004334845.tif 000077
の前記ｚ方向のゼロでないベクトルの個数
をさらに含む請求項９に記載の３次元データ記憶ボリュームのデータを復号する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶データのエラーの検出および訂正に関し、特に、階層化された３次元メモリのデータを符号化して、予想される一定のエラーのクラスの検出および訂正を可能にする、空間効率のよい方法に関する。
【背景技術】
【０００２】
本発明は、一般に、電子データの伝送、記憶、および検索の間に発生するエラーの検出、ならびに、多くの場合、訂正を可能にするエラー符号訂正に関する。
多くの線形ブロック符号化エラー制御符号化方法および技法は、長さｋのメッセージに分割可能なシリアル伝送データの符号化で既知である。
一般に、現在利用可能なエラー制御符号化技法が適用されるデータの記憶モデルは、記憶デバイス内における線形で２次元のワードの配置である。
２次元メモリの一定のタイプのエラーを認識して訂正する技法が開発されてきた。
このエラーには、次の小節で説明する十字交差（criss-cross）エラーが含まれる。
これらの技法の多くは、以下でも説明するように、組織線形符号を使用する。
いくつかのこれらの方法は、非特許文献１，２（Gabidulin著「Theory of Codes with Maximum Rank Distance」 Probl. Peredach. Inform., 21, pp. 3-16 (1985)、Gabidulin著「Optimal Array Error-Correcting Codes」Probl. Peredach. Inform., 21, pp. 102-106 (1985)、ならびにRothおよびSeroussi著「Reduced-Redundancy Product Codes for Burst Error Correction」IEEE Trans. Inform. Theory, 44, pp. 1395-1406 (1998)）に記載されている。
【非特許文献１】Gabidulin著「Theory of Codes with Maximum Rank Distance」 Probl. Peredach. Inform., 21, pp. 3-16 (1985)、Gabidulin著「Optimal Array Error-Correcting Codes」Probl. Peredach. Inform., 21, pp. 102-106 (1985)
【非特許文献２】RothおよびSeroussi著「Reduced-Redundancy Product Codes for Burst Error Correction」IEEE Trans. Inform. Theory, 44, pp. 1395-1406 (1998)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
最近、３次元記憶デバイスの新しいクラスが開発された。
この３次元記憶デバイスのクラスの障害モードは、所与のサイズの３次元データ記憶デバイス内の最大記憶容量を大きくするために、３次元データ記憶媒体内に記憶された符号化データのワード総数に対するデータワードの比率を高くする効率的な３次元データエラー制御符号化技法を必要とすることが予想される。
【課題を解決するための手段】
【０００４】
本発明の一実施の形態は、積符号およびいくつかの線形ブロック符号を使用して、３次元データ記憶媒体にデータを符号化する空間効率のよいエラー制御符号化技法を提供する。
この技法により、３次元データ記憶媒体のクラスに起こり得る既知の障害モードに対応した一定のタイプのエラーについて、制限された個数のエラーを検出して訂正することが可能となる。
【発明を実施するための最良の形態】
【０００５】
本発明の一実施の形態は、３次元データ記憶媒体にデータを符号化する、空間効率のよい技法である。
以下に説明する本発明の一実施の形態は、３次元データ記憶媒体のクラスの障害モードの認識および特徴付けと、一定のエラー制御符号化技法の選択および組み合わせと、選択して組み合わせたエラー制御符号化技法を使用して、３次元データ記憶媒体のクラスの一定の障害モードの検出および訂正を行う方法の実施とを含む。
したがって、この節は、次の３つの小節：（１）３次元データ記憶媒体のクラスの説明および３次元データ記憶媒体のクラスの障害モードの特徴付け、（２）選択したエラー制御符号化技法の数学的記述、ならびに（３）本発明の一実施の形態を表す方法の実施、に分割される。
【０００６】
［３次元データ記憶媒体のクラスの説明および３次元データ記憶媒体のクラスの障害モードの特徴付け］
図１は、本発明の一実施の形態を表す方法によってデータが符号化される３次元データ記憶媒体を示している。
このデータ記憶媒体は、例えばセル１０２などの複数のセル、すなわちデータ記憶ユニットを含む実線の長方形と考えることができる。
このデータ記憶媒体は、３つの直交軸ｘ、ｙ、およびｚ１０４に平行なエッジに沿った寸法、すなわちエッジに沿ったデータ記憶ユニットの個数によって特徴付けられる。
この図およびこれ以降の図ならびに説明では、伝統的でない左手座標系を使用する。
したがって、図１に示す３次元データ記憶媒体は、左方向のｘ軸１０６、上方向のｙ軸１０８、および用紙の平面から外部に向かうｚ軸１１０を有する寸法ｎｘ、ｎｙ、およびｎｚを有する。
以下の解説では、３次元データ記憶ボリュームＶを、以下のように、インデックスｉ、ｊ、およびｌを有するデータ記憶ユニットの集合として表記する。
｛（ｉ，ｊ，ｌ）：０≦ｉ<ｎｘ，０≦ｊ<ｎｙ，０≦ｌ<ｎｚ｝
以下の擬似コードの実施態様では、３次元データ記憶ボリュームＶの各要素を、以下に示すように、ｘ軸に対応するインデックスｘ、ｙ軸に対応するインデックスｙ、およびｚ軸に対応するインデックスｚによって指定することができる。
Ｖ［ｘ］［ｙ］［ｚ］
【０００７】
単一の３次元データ記憶ボリュームＶにデータを符号化することについて、本発明の一実施の形態を説明する。
一般に、実際の３次元データ記憶媒体は、例えば図１に示す３次元データボリュームＶのような個々の３次元データボリュームを数十万個、数百万個、さらには数十億個含む。
説明する本発明の実施の形態は、３次元データ記憶媒体全体の３次元データボリュームのそれぞれに対して、明確な順序で連続的に適用することができる。
【０００８】
単一の３次元データ記憶ボリュームＶ内のデータ記憶ユニットのいくつかのタイプのサブセットが、以下の解説および以下に提供する擬似コードの実施態様で使用される。
第１のタイプのサブセット、すなわちパーティションは、「ｚライン」と呼ばれる。
図２は、３次元データ記憶ボリュームＶ内のｚラインを示している。
ｚラインは、すべてが同一のｘ軸座標およびｙ軸座標を有するデータ記憶ユニットの集合である。
換言すると、ｘ座標「ａ」およびｙ座標「ｂ」によって指定されるｚラインは、次のように表記することができる。
｛（ｉ，ｊ，ｌ）：ｉ＝ａ，ｊ＝ｂ，０≦ｌ<ｎｚ｝
また、ｚラインは、「Ｖｘｙ」と表記して指定することもできる。
ｚライン内の特定のデータ記憶ユニットは、表記「Ｖｘｙ［ｚ］」を使用して擬似コードルーチンで指定してアクセスすることができる。
図２から分かるように、ｚライン２０２は、本質的には、ｚ軸の方向に向いたデータ記憶ユニットからなる直線状の配列である。
【０００９】
データ記憶ユニットの第２のタイプのサブセット、すなわちパーティションは、「ｘｙスライス」と呼ばれる。
図３は、３次元データ記憶ボリュームＶ内のｘｙスライスを示している。
図３に示すように、ｘｙスライスは、データ記憶ボリュームＶ内において、ｚ軸に垂直なデータ記憶ユニットからなる平面である。
ｘｙスライス内のすべてのデータ記憶ユニットは、同一のｚインデックスを有する。
したがって、ｚ軸座標「ｃ」におけるｘｙスライスは、次のように指定することができる。
｛（ｉ，ｊ，ｌ）：０≦ｉ<ｎｘ，０≦ｊ<ｎｙ，ｌ＝ｃ｝
あるいは、次のように指定することもできる。
Ｖｚ＝ｃ
本発明の一実施の形態を説明する擬似コードルーチンでは、ｘｙスライス内のデータ要素を、表記「Ｖｚ［ｘ］［ｙ］」を介して指定しアクセスすることができる。
付加的なサブセットとしては、ｙｚスライスＶｘ、ｘｚスライスＶｙ、ｘラインＶｙｚ、およびｙラインＶｘｚがある。
【００１０】
３次元データ記憶媒体のクラスには、エラー制御符号を介して検出および訂正を行う必要のある２つの異なるタイプの障害モードが存在する。
第１の障害モードは、「十字交差エラー」と呼ばれる。
図４は、データ記憶ボリュームＶ内におけるデータ記憶ユニットの十字交差を示している。
図４に示すように、３次元データ記憶ボリューム内のｘライン４０２およびｙライン４０４は、共通のデータ記憶ユニット４０６で交差する。
ｘライン４０２およびｙライン４０４は、特定のｘｙスライス内に存在する。
第１のタイプの障害モードには、図４に示すような十字交差内の１つまたは２つ以上のデータユニットの障害が含まれる。
３次元データ記憶ボリュームＶの第２のタイプの障害モードは、ｘｙスライス全体の障害である。
以下の解説では、これらの２つの異なるタイプの障害モードを、「十字交差障害」および「スライス障害」、あるいは、「タイプ１傷害」および「タイプ２障害」と呼ぶこととする。
十字交差障害は、十字交差エラー、すなわちタイプ１エラーを引き起こし、スライス障害は、スライスエラー、すなわちタイプ２エラーを引き起こす。
説明する本発明の実施の形態は、３次元データ記憶ボリュームＶ内の異なるｔ個の十字交差エラーと、多くとも単一のスライスエラーの検出および訂正を行うように設計される。
これらのエラーは、３次元データ記憶媒体のクラスに発生し得る最も確率の高いエラーと認められる。
【００１１】
［選択したエラー制御符号化技法の数学的記述］
説明する本発明の実施の形態は、エラー制御符号化のいくつかの既知の技法を使用する。
この分野の優れた参考文献は、LinおよびCostello著「Error Control Coding: The Fundamentals and Applications」Prentice-Hall, Incorporated, New Jersey, 1983という教科書である。
この小節では、本発明に使用されるエラー検出技法およびエラー訂正技法の簡単な説明を行う。
さらに詳細な内容は、上記参考にした教科書、または、この分野の他の多くの教科書、論文、および雑誌記事から得ることができる。
【００１２】
エラー検出およびエラー訂正を説明する際に、伝送、記憶、および検索が行われるデータを１つまたは２つ以上のメッセージとして記述することが役に立つ。
ここで、メッセージμは、体（field）Ｆの要素であるシンボルμｉの順序列を含む。
メッセージμは、次のように表現することができる。
μ＝（μ０，μ１，…μｋ−１）
上記数式において、μｉ∈Ｆである。
体Ｆは、乗算および加算のもとで閉じた集合であり、逆数と加法の逆元とを含む集合である。
計算によるエラー検出およびエラー訂正では、素数と等しい大きさを有する整数の部分集合を含んだ体を使用することが一般的であり、この体では、加算演算子および乗算演算子が、モジュロ加算およびモジュロ乗算として定義される。
実際には、バイナリ体が一般的に使用される。
素数、その最も多くは２、の累乗に等しい大きさを有する体が、かなり一般的に使用される。
これらの体では、加算演算子および乗算演算子は、モジュロ既約多項式により実行される。
一般に、元のメッセージは、同様に体Ｆの要素の順序列を含む符号化メッセージｃに符号化される。
この符号化メッセージｃは、次のように表現される。
ｃ＝（ｃ０，ｃ１，…ｃｎ−１）
上記数式において、ｃｉ∈Ｆである。
【００１３】
説明する本発明の実施の形態は、ブロック符号化技法を使用する。
このブロック符号化技法では、データは、ブロックに符号化される。
この解説では、ブロックは、一定数のｋ個のシンボルを含むメッセージμであって、ｎ個のシンボルの順序列を含むメッセージｃに符号化されるメッセージμとみなすことができる。
符号化メッセージｃは、一般に、元のメッセージμよりも多くの個数のシンボルを含み、したがって、ｎは、ｋよりも大きい。
ｒをｎ−ｋに等しいものとすると、符号化メッセージのｒ個の余分のシンボルは、冗長検査情報を運ぶのに使用され、この冗長検査情報により、伝送、記憶、および検索の間に発生するエラーを、極めて高い検出確率で検出することが可能になり、多くの場合、訂正することが可能になる。
【００１４】
伝送、記憶、および検索のためのデータの符号化、ならびに、その後の符号化データの復号は、この符号化データの転送、記憶、および検索の間にエラーが発生しない場合には、次のように表記することができる。
μ→ｃ（ｓ）→ｃ（ｒ）→μ
上記数式において、ｃ（ｓ）は、伝送前の符号化メッセージであり、ｃ（ｒ）は、最初に検索したメッセージまたは最初に受信したメッセージである。
このように、最初のメッセージμは、符号化されて、符号化メッセージｃ（ｓ）が生成され、その後、この符号かメッセージｃ（ｓ）は、送信もしくは記憶されるか、または、送信されて記憶され、その後、最初の受信メッセージｃ（ｒ）として検索されるか、または、受信される。
最初の受信メッセージｃ（ｒ）は、破損を受けていない場合、その後、復号されて、元のメッセージμが生成される。
上述したように、エラーが発生していない場合、元の符号化メッセージｃ（ｓ）は、最初の受信メッセージｃ（ｒ）に等しく、最初の受信メッセージｃ（ｒ）は、エラー訂正を受けることなく、直接、元のメッセージμに復号される。
【００１５】
符号化メッセージの伝送、記憶、または検索の間にエラーが発生した場合、メッセージの符号化および復号は、次のように表現することができる。
μ（ｓ）→ｃ（ｓ）→ｃ（ｒ）→μ（ｒ）
したがって、上述したように、最終メッセージμｒは、最初のメッセージμｓに等しくなることもあるし、等しくならないこともある。
等しくなるかならないかは、元のメッセージμｓを符号化し、最初の受信メッセージｃ（ｒ）を復号または復元して最終受信メッセージμｒを生成するのに使用されるエラー検出技法およびエラー訂正技法の忠実度に依存する。
エラー検出は、次のことを判断するプロセスである。
Ｃ（ｒ）≠ｃ（ｓ）
一方、エラー訂正は、以下に示すように、破損した最初の受信メッセージから最初の符号化メッセージを復元するプロセスである。
ｃ（ｒ）→ｃ（ｓ）
【００１６】
符号化プロセスは、μという記号で表されるメッセージを符号化メッセージｃに変換するプロセスである。
あるいは、メッセージμは、Ｆの要素からなる文字からのシンボルの順序集合を含むワードとみなすことができ、符号化メッセージｃは、同様に、Ｆの要素からなる文字からのシンボルの順序集合を含む符号ワードとみなすことができる。
ワードμは、Ｆの要素から選択されたｋ個のシンボルの任意の順序付けられた組み合わせとすることができる一方、符号ワードｃは、以下の符号化プロセスを介してＦの要素から選択されたｎ個のシンボルの順序列と定義される。
｛ｃ：μ→ｃ｝
【００１７】
線形ブロック符号化技法は、ワードμをｋ次元ベクトル空間のベクトルとみなして、以下のようにベクトルμを生成行列と乗算することにより、長さｋのワードを符号化する。
ｃ＝μ・Ｇ
上記方程式のシンボル表記を展開すると、次の代わりとなる表現のいずれもが生成される。
【００１８】
【数１８】
2004334845.tif 000003
【００１９】
上記方程式において、ｇｉ＝（ｇｉ，０，ｇｉ，１，ｇｉ，２…ｇｉ，ｎ−１）である。
【００２０】
線形ブロック符号の生成行列Ｇは、次の形を有することができる。
【００２１】
【数１９】
2004334845.tif 000004
【００２２】
あるいは、次の形を有することができる。
Ｇｋ，ｎ＝［Ｐｋ，ｒ｜Ｉｋ，ｋ］
このように、生成行列Ｇは、行列Ｐをｋ×ｋの単位行列Ｉｋ，ｋにより増強した形に配列することができる。
生成器によってこの形に生成された符号は、「組織符号」と呼ばれる。
この生成行列が、ワードμに適用された結果、符号ワードｃは、次の形を有する。
ｃ＝（ｃ０，ｃ１，…，ｃｒ−１，μ０，μ１，…，μｋ−１）
上記数式において、ｃｉ＝μ０ｐ０，ｉ＋μ１ｐ１，ｉ，…，μｋ−１ｐｋ−１，ｉである。
このように、組織線形ブロック符号では、符号ワードは、ｒ個のパリティチェックシンボルｃｉと、その後に続く元のワードμを含んだシンボルとを含む。
エラーが発生しない場合、元のワード、すなわちメッセージμは、対応する符号ワード内で平文の形で現れ、対応する符号ワードから容易に抽出することができる。
パリティチェックシンボルは、元のメッセージ、すなわちワードμのシンボルの線形結合であることが分かる。
【００２３】
有用な第２の行列の１つの形は、次のように定義されるパリティチェック行列Ｈｒ，ｎである。
Ｈｒ，ｎ＝［Ｉｒ，ｒ｜−ＰＴ］
すなわち、次のようになる。
【００２４】
【数２０】
2004334845.tif 000005
【００２５】
パリティチェック行列は、組織エラー検出（systematic error detection）および組織エラー訂正（systematic error correction）に使用することができる。
エラー検出およびエラー訂正には、以下のように、最初の受信メッセージまたは最初の検索メッセージｃ（ｒ）からシンドロームＳを計算することが必要となる。
Ｓ＝（ｓ０，ｓ１，…，ｓｎ−ｋ）＝ｃ（ｒ）・ＨＴ
上記数式において、ＨＴは、パリティチェック行列Ｈｒ，ｎの転置行列であり、次のように表現される。
【００２６】
【数２１】
2004334845.tif 000006
【００２７】
シンドロームベクトルＳの要素は、次のようになる。
ｓｉ＝（ｃ（ｒ）ｉ−ｃ（ｒ）ｒｐ０，ｉ−ｃ（ｒ）ｒ＋１ｐl，ｉ−ｃ（ｒ）ｒ＋２ｐ２，ｉ−…−ｃ（ｒ）ｎ−１ｐｋ−１，ｉ）
【００２８】
エラーベクトルｅが、最初の受信メッセージｃ（ｒ）と最初に準備された送信符号ワードｃ（ｓ）との差分、すなわちそれら両者のベクトル減算の結果として次のように定義される。
【００２９】
【数２２】
2004334845.tif 000007
【００３０】
シンドロームベクトルＳは、次のように、エラーベクトルに関係する。
Ｓ＝ｃ（ｒ）ＨＴ＝（ｃ（ｓ）＋ｅ）ＨＴ＝ｃ（ｓ）ＨＴ＋ｅＨＴ＝ｅＨＴ
エラー訂正には、以下の符号ワードｃ（ｓ）を準備した後、最初の受信メッセージｃ（ｒ）を受信または検索するまでに発生したエラーを特定することが必要となる。
エラー訂正の問題は、次のようなエラーベクトルｅを見つける問題である。
ｅＨＴ＝ｃ（ｒ）ＨＴ
その後、エラー訂正が実行され、訂正されたワード
【００３１】
【数２３】
2004334845.tif 000008
【００３２】
が生成される。
この訂正されたワードは、最も確率の高い最初に送信された符号ワードまたは最初に記憶された符号ワードを表し、次の数式によって表される。
【００３３】
【数２４】
2004334845.tif 000009
【００３４】
［本発明の一実施の形態を表す方法の実施態様］
説明する実施の形態では、３次元データ記憶ボリュームＶ内の各データ記憶ユニットは、ｑ個の要素を有する体Ｆの要素ｆである。
説明する実施の形態では、ｆは、４ビットで記憶できる整数の範囲と等しい０〜１５の範囲にある整数値のいずれであってもよい。
図５Ａは、本発明の一実施の形態を実践できるデータ記憶ボリューム内のデータ記憶ユニットを示している。
図５Ａは、単一のデータ記憶ユニット５０２を、４つの別々のビットＡ〜Ｄを含むものとして考えることができることを示している。
図５Ｂは、データ記憶ユニットｆの可能な値のそれぞれを、ビットＡ〜Ｄのビット値の順序付けられた異なる組み合わせとして考えることができることを示している。
図５Ｂでは、体Ｆの異なる要素ｆに、整数「０」〜「１５」に相応する文字「ａ」〜「ｐ」のラベルが付けられている。
明瞭にすると、図６は、３次元データ記憶ボリュームＶの各データ記憶ユニットが、１６要素の体Ｆの４ビット相当の要素ｆであることを示している。
【００３５】
上述したように、線形ブロック符号を使用して、メッセージ、すなわちワードを符号化するには、メッセージ、すなわちワードを使用して、追加するパリティチェックシンボルと共に、メッセージ、すなわちワードを平文の形で含む符号ワードを生成する必要がある。
図７は、符号化プロセスおよび復号プロセスを示している。
図７に示すように、各メッセージ、すなわち各ワードは、ｋ個のシンボルの順序列を含む。
したがって、図７の左側の配列７０２（図７には配列７０２の一部のみを示す）は、長さｋのｑｋ個のさまざまな異なる有効メッセージ、すなわちワードを列挙している。
配列７０２では、各行が、異なるメッセージ、すなわちワードを表す。
図７に示す例では、各ワード、すなわちメッセージは、長さｋ＝４を有する。
このメッセージ、すなわちワードは、図７の右側の配列７０４に含まれる符号ワードに符号化される。
図７では、右側の配列７０４の各行は、左側の配列の対応する行のメッセージに対応する異なる符号ワードである。
図７から分かるように、各符号ワード内の最後の４つのシンボルが、その符号ワードを生成した平文メッセージに対応する。
したがって、どの特定の符号化／復号線形ブロック方式についても、パラメータｋは、メッセージ、すなわちワードの長さをいい、パラメータｎは、符号化メッセージまたは符号ワードの長さをいい、パラメータｒは、その符号の最小ハミング距離をいう。
以下では、特定の組織線形ブロック符号を、表記「Ｃ［ｎ，ｋ，ｒ］」によって参照することとする。
この表記において、Ｃは、符号の名前であり、ｎは、符号ワードの長さであり、ｋは、長さｎの符号ワードを生成するワードの長さであり、ｒは、符号の最小ハミング距離である。
【００３６】
本発明の一実施の形態を、擬似コードの実施態様およびいくつかの例図の双方を同時に参照して以下に説明する。
擬似コードの実施態様は、表記規約とプログラム言語Ｃ＋＋の要素とのうちのいくつかを使用する高級擬似コード言語で記述される。
ただし、この高級擬似コード言語には、本発明の一実施の形態を表す方法の動作を簡潔かつ明瞭に指定するのに適した高レベルの数学表記も使用される。
以下の擬似コードには、簡潔にするために、サブルーチンのローカル変数およびスコーピングルールは使用されないことに留意されたい。
例えばＣ＋＋といった通常のプログラム言語による実際の実施では、グローバル変数の除去、および、十分に構造化されたインターフェースを通じたルーチン間のデータの交換の制御といった通常のプログラムの規約に従うものと予想される。
【００３７】
まず、ルーチン「ｅｎｃｏｄｅ（符号化）」を提供する。
このルーチン「ｅｎｃｏｄｅ」は、以下の宣言から開始する。
【００３８】
ルーチンｅｎｃｏｄｅ
１  Declarations（宣言）： 
２
３    Ｆ          ｑ個の要素の体
４    Ｖ，Ｖ'    寸法ｎｘ×ｎｙ×ｎｚのセルのボリューム。
各セルは体Ｆの要素を含む
５
６    Ｃｘ        ｒｘ＝ｎｘ−ｋｘの組織線形符号Ｃｘ［ｎｘ，ｋｘ，３］
７    Ｃｙ        ｒｙ＝ｎｙ−ｋｙの組織線形符号Ｃｙ［ｎｙ，ｋｙ，３］
８    ＣｘＣｙ    ｒｘｙ＝ｎｘｎｙ−ｋｘｋｙの組織積符号ＣｘＣｙ［ｎｘｎｙ，ｋｘｋｙ，９］
９    Ｃｚ        ｒｚ＝ｎｚ−ｋｚの組織線形符号Ｃｚ［ｎｚ，ｋｚ，２ｔ＋１］
１０  Ｃｚ'      ｒｚ'＝ｎｚ−ｋｚ'の組織線形符号Ｃｚ'［ｎｚ，ｋｚ'，ｔ＋１］
１１  ｖ０      長さｎｚを有する体Ｆの要素のベクトル
１２  ｖ１    長さｋｚ'を有する体Ｆの要素のベクトル
１３  ｖ２、ｖ３    長さｋｚを有する体Ｆの要素のベクトル
１４  ｓｕｍ（和）    体Ｆの要素の値を有する変数
１５  ｘ、ｙ、ｚ、ｉ  整数
１６  ｇｅｔＩｎｆｏ（ｎ）（情報取得（ｎ））  入力ストリームから体Ｆのｎ個の情報要素を取得する
【００３９】
このルーチン「ｅｎｃｏｄｅ」は、複数のデータ記憶ユニットを含む３次元データ記憶ボリュームにデータを符号化する方法を含む。
この方法は、データの列を受信するステップと、線形積符号を使用してそのデータの列を符号化するステップであって、それによりデータをデータ値の符号配列に符号化する、データ列を符号化するステップと、２つの線形ブロック符号を使用するステップであって、それによりデータ値のベクトルにデータを符号化する、使用するステップとを含む。
【００４０】
ルーチン「ｅｎｃｏｄｅ」は、上記ライン３で宣言されるような体Ｆの要素ｑｉを含むワードを受け取って符号化する。
上記ライン４で宣言されるような、データ記憶ユニットからなる２つの異なる３次元ボリュームＶおよびＶ'が使用される。
説明する実施の形態は、上記ライン６〜１０で宣言されるような５つの異なる組織線形ブロック符号Ｃｘ、Ｃｙ、ＣｘＣｙ、Ｃｚ、およびＣｚ'を使用する。
これら５つの異なる組織線形ブロック符号のそれぞれについてのパラメータｋ、ｎ、およびｒは、この宣言で指定される。
組織線形ブロック符号ＣｘＣｙは、積符号である。
積符号は、１次元符号ワードではなく、２次元符号配列を生成する２つの簡単な組織線形符号を結合したものである。
図８は、積符号により生成される符号配列のレイアウトを示す。
図８に示すように、この符号配列は、３つのパリティチェックシンボル領域８０４〜８０６に加えて、符号配列の平文領域８０２内にｋｘｋｙ個の平文シンボルを含む。
これらの領域は、図８に示すような寸法および配置を有する。
符号配列は、３次元データ記憶ボリューム内では平面として記憶される。
積符号は、エラー制御符号化の分野で既知であり、上記で引用した教科書"Error Control Coding: Fundamentals and Applications"に記載されている。
ルーチン「ｅｎｃｏｄｅ」は、上記ライン１１〜１３で宣言される体Ｆの要素の４つの異なるベクトルｖ０、ｖ１、ｖ２、およびｖ３を使用する。
これらのベクトルは、その宣言で指定された長さを有する。
上記ライン１４で宣言される変数「ｓｕｍ」は、体Ｆの要素を記憶し、この要素は、体Ｆの２つの要素の和を表す。
ルーチン「ｅｎｃｏｄｅ」は、上記ライン１５で宣言される４つの異なる整数変数「ｘ」、「ｙ」、「ｚ」、および「ｉ」を使用する。
最後に、ルーチン「ｅｎｃｏｄｅ」は、符号化のため、体Ｆの指定された個数の情報要素を入力ストリームから取得する関数「ｇｅｔＩｎｆｏ」を使用する。
ルーチン「ｅｎｃｏｄｅ」は、上記ライン１６で宣言される関数「ｇｅｔＩｎｆｏ」を呼び出して、３次元データ記憶ボリュームＶに符号化される情報要素の連続したそれぞれの集合を取得する。
【００４１】
以下に示すように、ルーチン「ｅｎｃｏｄｅ」は、次の表記規約を使用する。
１  Notational Conventions（表記規約）：
２
３    ｍ＝Ｃ（ｋ）      符号Ｃを長さｋの体Ｆの要素の列に適用して符号ワードｍを生成する
４
５
６    ｍ＝Ｃ１Ｃ２（ｋ１ｋ２）    積符号Ｃ１Ｃ２を長さｋ１ｋ２の体Ｆの要素の列に適用して、寸法ｎ１、ｎ２の符号配列ｍを生成する
７
８
【００４２】
ルーチン「ｅｎｃｏｄｅ」は、４つのサブルーチンを使用する。
これらのサブルーチンを以下に個別に説明する。
第１のサブルーチンＳｕｂｔｒａｃｔＺＬｉｎｅＦｒｏｍＩｎｆｏＶｅｃｔｏｒ（情報ベクトルからｚラインの減算）を以下に提供する。
１  Routine SubtractZLineFromInfoVector(x,y)
２
３ /*
【００４３】
【数２５】
2004334845.tif 000010
【００４４】
を計算する。
ここで、μｉ，ｊは、体Ｆの情報要素のベクトルであり、
【００４５】
【数２６】
2004334845.tif 000011
【００４６】
は、ボリュームＶのｚラインベクトルＶｉ，ｊの上位のｋｚ'個の要素である。
４
５
６ */
７
８ v1=getInfo(kz');
９ for (i = 0, z = nz - kz'; z<nz; i++, z++)
１０ {
１１  v1[i] = v1[i] - Vxy[z];
１２ }
【００４７】
ＳｕｂｔｒａｃｔＺＬｉｎｅＦｒｏｍＩｎｆｏＶｅｃｔｏｒは、関数「ｇｅｔＩｎｆｏ」を介して情報要素ストリームからｋｚ'個の情報ユニットをフェッチし、それらの情報ユニットから、３次元データ記憶ボリュームＶのｚラインの現在の内容を減算する。
その結果は、ベクトルｖ１に残される。
【００４８】
サブルーチンＣｏｍｐｕｔｅＸＺＰｒｏｊｅｃｔｉｏｎＶｅｃｔｏｒ（ＸＺ投影ベクトルの計算）を次に提供する。
１ Routine ComputeXZProjectionVector(y)
２
３ v0 = 0;
４ for (x =1; x < nx; x++)
５    for (z = 0; z < nz; z++)
６    {
７        v0[z] = v0[z] + Vxy'[z]
８    }
【００４９】
ＣｏｍｐｕｔｅＸＺＰｒｏｊｅｃｔｉｏｎＶｅｃｔｏｒは、３次元データ記憶ボリュームＶ'内のｘｚスライス、すなわちｘｚ平面の内容をベクトル「ｖ０」に投影する。
サブルーチンＣｏｍｐｕｔｅＹＺＰｒｏｊｅｃｔｉｏｎＶｅｃｔｏｒ（ＹＺ投影ベクトルの計算）は、上記ルーチンの計算と同様にして、３次元データ記憶ボリュームＶ'内のｙｚスライスから投影ベクトル（projection vector）を計算する。
１ Routine ComputeYZProjectionVector(x)
２
３ v0 = 0;
４ for (y =1; y < ny; y++)
５    for (z = 0; z < nz; z++)
６    {
７        v0[z] = v0[z] + Vxy'[z]
８    }
【００５０】
サブルーチンＣｏｍｐｕｔｅＰｒｏｊｅｃｔｉｏｎＶｏｌｕｍｅＤｉｆｆｅｒｅｎｃｅ（投影ボリュームの差分の計算）を次に提供する。
１ Routine ComputeProjectionVolumeDifference(x,y)
２
３ for (z = nz - kz, i = 0; z < nz; z++, i++)
４ {
５    v2[i] = v0[z] + Vxy[z]
６ }
【００５１】
このサブルーチンは、３次元データ記憶ボリュームＶのｚラインの内容をベクトル「ｖ０」の内容に加算し、その和をベクトル「ｖ２」に置く。
【００５２】
最後に、ルーチン「ｅｎｃｏｄｅ」の主要部分を提供する。
１ Main (Encode)（メイン（Ｅｎｃｏｄｅ））
２
３ /* 体Ｆのｋｘｋｙ（ｎｚ−１）＋ｋｚ'（ｎｘｎｙ−ｎｘ−ｎｙ＋１−ｋｘｋｙ）＋ｋｚ（ｎｘ＋ｎｙ＋１）個の情報要素を、寸法ｎｘ、ｎｙ、ｎｚを有する体Ｆの要素からなる記憶ボリュームＶに符号化する
４
５
６ */
７ for (z = 1; z < nz; z++)
８ {
９  Vz = CxCy (getInfo(kxky));
１０ }
１１ for (x = 0; x < nx; x++)
１２    for (y = 0; y < ny; y++)
１３    {
１４        sum = 0;
１５        for(z = 1; z < nz; z++)
１６        {
１７            sum += Vxy[z];
１８        }
１９        Vxy[z] = -sum
２０    }
２１ for (x = 1; x < rx; x++)
２２    for(y=1; y = ny; y++)
２３    {
２４        SubtractZLineFromInfoVector(x,y);
２５        Vxy' = Cz'(v1);
２６ }
２７ for (y=1; y = ry; y++)
２８    for (x = rx; x < nx; x++)
２９    {
３０        SubtractZLineFromInfoVector(x,y);
３１        Vxy' = Cz'(v1);
３２ }
３３ for (y=1; y < ny; y++)
３４ {
３５    v3 = getInfo(kz);
３６    ComputeXZProjectionVector(y);
３７    ComputeProjectionVolumeDifference(0,y);
３８    V0,y' = Cz(v3 - v2) - v0;
３９ }
４０ for (x = 0; x < nx; x++)
４１ {
４２    v3 = getInfo(kz);
４３    ComputeYZProjectionVector(x);
４４    ComputeProjectionVolumeDifference(x,0);
４５    Vx,0' = Cz(v3 - v2) - v0;
４６ }
４７ for (x = 0; x < nx; x++)
４８    for (y = 0; y < ny; y++)
４９    {
５０        Vxy = Vxy + Vxy';
５１    }
【００５３】
このルーチンは、基本的には、入力ストリームから複数の情報要素、すなわち、ライン３のコメントで上述した個数の情報要素を取得し、これらの情報要素を３次元データ記憶ボリュームＶに符号化する。
符号化の終わりにあたり、比較的少ない個数のパリティチェックシンボルと共に、これらの情報要素は、データ記憶ボリュームＶ内では平文の形で現れる。
最初に、ライン７〜１０のｆｏｒループで、ルーチン「ｅｎｃｏｄｅ」は、ｋｘｋｙという長さの情報要素を入力ストリームからフェッチし、これらの情報要素を積符号ＣｘＣｙを介して符号配列に符号化し、ｎｚ−１個のｘｙスライスを３次元データ記憶ボリュームＶ内に形成する。
図９〜図１３は、ライン７〜１０のｆｏｒループによりｎｚ−１個のｘｙスライスで３次元データ記憶ボリュームＶを満たす様子を示している。
この最初のステップでは、ｚ軸座標「０」を有するｘｙスライスは、３次元データ記憶ボリュームＶに入力されないことに留意されたい。
図９に示すように、ｚ座標１を有する最初のｘｙスライスの行のパリティチェックシンボルは、Ｃｘのパリティチェックルールを情報シンボルの行９０２に適用して長さｎｘの符号化された行９０４を生成し、これらの符号化された行、例えば符号化された行９０４を３次元データ記憶ボリュームＶ１００に入力することにより満たされるものと考えることができる。
図１０に示すように、特定のｘｙスライス１００２は、部分的には、組織線形ブロック符号Ｃｘを適用して長さｎｘの符号化された行を得ることにより生成されるｋｙ個の行から構築されると考えることができる。
図１１に示すように、特定のｘｙスライスは、は、組織線形ブロック符号Ｃｙをｋｙ個の情報要素１１０４に適用することにより得られる列１１０２からさらに構成される。
各行の最初のｋｘ個の情報ユニットの内容および各列の最初のｋｙ個の情報ユニットの内容は、情報入力ストリームから得られる平文の情報シンボルである。
図１２に示すように、最終的なｘｙスライス１００２は、積符号ＣｘＣｙをｋｘｋｙ個の情報要素に適用した結果を表す符号配列である。
ｘｙスライス１００２は、パリティチェックシンボルからなる垂直な領域１００４および水平な領域の１００６（図１２の陰影を付けた部分）と共に、ｋｘｋｙ個の平文の情報ユニット（図１２の陰影のない部分）を含むことに留意されたい。
図１３に示すように、ライン７〜１０のｆｏｒループは、ｚ座標１からｚ座標ｎｚ−１に実行して、パリティチェック要素１３０４および１３０６（これらのパリティチェック要素は陰影を有する）の左上のボリュームに平文の情報要素１３０２のボリュームを生成する。
積符号は、３次元データ記憶ボリュームＶを満たし、パリティチェックシンボルの個数ｎｚｒｘｒｙと同等のエラー検出機能およびエラー訂正機能を提供するために使用できることに留意されたい。
しかしながら、以下から分かるように、このような技法は、上述した可能性のある２つのタイプの障害モードから発生するエラーの検出および訂正に必要な個数よりもずっと多い個数のパリティチェックシンボルを使用する。
したがって、説明する本発明の実施の形態は、３次元データ記憶ボリュームＶ内において、平文の情報要素を記憶するデータ記憶ユニットの使用比率をより大きくし、それに応じて、３次元データ記憶ボリュームＶ内におけるパリティチェック情報要素の比率を削減するために使用される。
【００５４】
次に、ライン１１〜２０のネストしたｆｏｒループにおいて、ルーチン「ｅｎｃｏｄｅ」は、図１３に示す３次元データ記憶ボリュームＶの各ｚラインのデータ記憶ユニットの和を計算し、３次元データ記憶ボリュームＶ内の各ｚラインの最初の要素にその和の加法の逆元を記憶する。
このプロセスを図１４および図１５に示す。
図１４に示すように、ｘおよびｙの座標が（０，０）である最初のｚライン１４０２が、ライン１１〜２４のネストしたｆｏｒループの最初の繰り返しで考慮される。
ｚライン１４０２内のデータユニットは、モジュロ加算を使用して和が求められ、その和の加法の逆元が、ｚラインの最初のデータ記憶ユニット１４０４に記憶される。
ライン１１〜２０のネストしたｆｏｒループの実行の結果、３次元データ記憶ボリュームＶ１００の最初のｘｙスライスは、ｚラインの和の加法の逆元により満たされる。
図１６は、ライン１１〜２０のネストしたｆｏｒループの実行後の３次元データ記憶ボリュームＶの内容を示している。
ボリュームの底部側および右側におけるボリュームのパリティチェック領域内のｚラインのそれぞれ、例えばｚライン１６０２は、パリティチェックシンボルのみを含む。
ボリュームの大部分の平文情報シンボルの部分の内部のｚラインのそれぞれ、例えばｚライン１６０４は、そのｚラインの最初のデータ記憶ユニットを除くすべてで平文の情報シンボルを含む。
最初のデータ記憶ユニット、例えばｚライン１６０４のデータ記憶ユニット１６０６は、そのｚラインの残りのデータ記憶ユニットに記憶された情報要素の和の加法の逆元を含む。
【００５５】
次に、ライン２１〜２６のネストしたｆｏｒループにおいて、ルーチン「ｅｎｃｏｄｅ」は、追加情報シンボルを第２の３次元データ記憶ボリュームＶ'に符号化する。
この追加情報シンボルは、３次元データ記憶ボリュームＶ'の右側の複数の垂直なｙｚスライスを形成するｚラインに符号化される。
ｆｏｒループの引数から分かるように、ライン２１〜２６のネストしたｆｏｒループでは、ｒｘ個未満の個数に等しい複数の垂直なｙｚスライス、すなわち、組織線形ブロック符号Ｃｘによって生成されるパリティチェックシンボルの個数のｙｚスライスが、ｘ軸座標１から開始してｘ軸座標ｒｘ−１まで生成される。
この符号化は、特定のｚラインの３次元データ記憶ボリュームＶの現在の内容を、新しく得た情報要素を含むベクトルから減算すること、ライン２９で、その結果のベクトルを組織線形ブロック符号Ｃｚ'を使用して符号化して、３次元データ記憶ボリュームＶ'内のｚ軸として記憶される符号ワードを生成することとを含む。
このプロセスを図１７および図１８に示す。
図１７に示すように、３次元データ記憶ボリュームＶ'に加えられる最初のｚラインに対して、ｋｚ'個の情報要素が、入力ストリームから得られ、ベクトルμ１７０２にロードされる。
このベクトルμ１７０２から、３次元データ記憶ボリュームＶ１７０４の対応するｚラインの内容が減算され、その結果が、ベクトル１７０６に置かれる。
次に、このベクトルは、ルーチン「ｅｎｃｏｄｅ」のライン２９で、組織線形ブロック符号Ｃｚ'を使用して符号化され、符号ワード、すなわちベクトル１７０８が生成される。
次に、この符号ワード１７０８は、３次元データ記憶ボリュームＶ'１７１０に記憶される。
記憶される座標は、得られた情報要素のベクトルμ１７０２から減算された３次元データ記憶ボリュームＶ１７０４のｚラインの座標ｘ、ｙに対応するｘ、ｙ座標である。
ライン２１〜２６のｆｏｒループの実行の結果、複数の垂直なｙｚスライス、例えばｙｚスライス１８０２が、３次元データ記憶ボリュームＶ'に入力される。
１つのｙｚスライスのみを図１８に示しているが、ライン２１〜２６のネストしたｆｏｒループは、一般に、ｒｘ−１個のこのようなｙｚスライスを３次元データ記憶ボリュームＶ'に配置する。
ライン２７〜３２のネストしたｆｏｒループも、同様にして、組織線形ブロック符号「Ｃｚ'」によって符号化されたｚラインの水平ブロックをデータ記憶ボリュームＶ'に挿入する。
ライン２１〜２６およびライン２７〜３２のネストしたｆｏｒループの実行の結果は、データ記憶ボリュームＶ'内において、鏡像のＬ字型のｚラインの領域となる。
図１９は、ルーチン「ｅｎｃｏｄｅ」のライン２１〜２６およびライン２７〜３２のネストしたｆｏｒループの実行の結果を示している。
図１９では、単一のｙｚスライスおよび単一のｘｙスライスのみを示しているが、上述したように、ライン２１〜２６およびライン２７〜３２のネストしたｆｏｒループは、一般に、３次元データ記憶ボリュームＶ'内のｚラインの垂直なブロックおよび水平なブロックを生成する。
垂直なｙｚスライスは、ｘ軸座標１から開始して、ｘ軸座標ｒｘ−１を通る左側まで続く。
水平なｘｚスライスは、ｙ軸座標１から開始して、ｙ軸座標ｒｙ−１を通る上側まで続く。
３次元データ記憶ボリュームＶ'の最右端のｙｚスライスおよび最下端のｘｚスライスは、ライン２７〜３２のネストしたｆｏｒループの実行後であってもまだ満たされないことに留意されたい。
【００５６】
次に、ライン３３〜３９およびライン４０〜４６のｆｏｒループにおいて、３次元データ記憶ボリュームＶ'の最右端のｙｚスライスおよび最下端のｘｚスライスが、投影ベクトルの計算および符号化を含む多少複雑な操作を介して満たされる。
この操作は、上記擬似コードを考察することにより理解できるが、おそらくは、図２０〜図２３と同時に擬似コードを考察することにより最もよく理解できる。
最右端のｙｚスライスには、ｘｚ投影ベクトルの計算が必要となる。
図２０は、この投影ベクトルの計算を示している。図２０に示すように、長さｋｚの投影ベクトル
【００５７】
【数２７】
2004334845.tif 000012
【００５８】
が、ｙ軸座標１を有するｘｚ平面２００２内のすべてのデータ記憶ユニットの値の和を求めて、その和をベクトル
【００５９】
【数２８】
2004334845.tif 000013
【００６０】
に置くことによって計算される。
換言すると、任意の特定のｚ軸座標に対して、特定のｚ軸座標ｚを有する投影ベクトル
【００６１】
【数２９】
2004334845.tif 000014
【００６２】
のデータ記憶ユニットは、ｚ軸座標ｚを有するｘｚ平面２００２内のすべてのデータ記憶ユニットの和を含む。
同様に、投影ベクトル
【００６３】
【数３０】
2004334845.tif 000015
【００６４】
２００４は、１とｒｘ−１との間のｘ軸座標およびｙ軸座標２を有するｘｚスライスのすべてのｚラインの和を表す。
図２１は、計算された投影ベクトルを使用して、３次元データ記憶ボリュームＶ'に記憶するためのｚラインを生成する様子を示している。
図２１に示すように、３次元データ記憶ボリュームＶの対応するｚライン２１０２が、計算された投影ベクトル２１０４から減算され、その結果が、入力ストリームから得られたｋｚ個の情報要素２１０６に加算される。
その結果のベクトルは、組織線形符号Ｃｚによって（ルーチン「ｅｎｃｏｄｅ」のライン３８および４５で）符号化され、符号ワードベクトル２１０８が生成される。
この符号ワードベクトル２１０８から、投影ベクトルが減算される。
符号ワード２１０８は、３次元データ記憶ボリュームＶ'に記憶される。
記憶場所は、ｘ軸座標０と、計算する投影ベクトルから減算された３次元データ記憶ボリュームＶの対応するｚライン２１０２のｙ軸座標に等しいｙ軸座標とを有するｚラインである。
【００６５】
図２２に示すように、ライン３３〜３９のｆｏｒループの完了により、３次元データ記憶ボリュームＶ'の最右端のｙｚスライス２２０２が満たされる。
ただし、このｙｚスライスの最初のｚラインは除かれる。
ライン４０〜４６のｆｏｒループの実行の結果、３次元データ記憶ボリュームＶ'の最下端の水平なｘｚスライスにｚラインが記憶される。
これらのｚラインは、組織線形ブロック符号Ｃｚの符号ワードを表すものである。
ライン４０〜４６のｆｏｒループの実行が終了すると、３次元データ記憶ボリュームＶ'は、０とｒｘ−１との間のｘ座標を有するｙｚスライスと、０からｒｙ−１までのｙ軸座標を有するｘｚスライスとを含む。
図２３に示すように、３次元データ記憶ボリュームＶ'のこれらの最も外側のｚライン、例えば最も外側のｚライン２３０３は、ｋｚ個の平文の情報シンボルと、ｒｚ個のパリティチェックシンボル２３０４（図２３に陰影を付けて示す）とを含む。
内部のｙｚスライスおよびｘｚスライスは、ｋｚ'個の平文の情報シンボル２３０６と、ｒｚ'個のパリティチェックシンボル２３０８とを有するｚラインを含む。
【００６６】
最後に、ライン４７〜５１のネストしたｆｏｒループにおいて、３次元データ記憶ボリュームＶおよびＶ'のｚラインが、共に加算されて、３次元データ記憶ボリュームＶに記憶される。
図２４は、ライン４７〜５１のネストしたｆｏｒループの操作を示している。
図２５は、ルーチン「ｅｎｃｏｄｅ」によって実行される符号化操作の最終的な結果を示している。
図２５に示すように、３次元データ記憶ボリュームＶ１００内の膨大な大部分のデータ記憶ユニットは、平文の情報シンボルを含む。
これらの記憶ユニットは、図２５では、陰影を付けていない部分で示される。
ｚ軸座標「０」を有するｘｙスライス２５０２、小さな垂直のパリティチェックシンボルの領域２５０４、および同様に小さな水平のパリティチェックシンボルの領域（図２５では見えない）のみが、３次元データ記憶ボリュームＶに含まれる。
【００６７】
次に、ルーチン「ｄｅｃｏｄｅ（復号）」を説明する。
このルーチンは、上述したタイプ１障害モードおよびタイプ２障害モードによって生成されたエラーが、受信または検索された３次元データ記憶ボリューム
【００６８】
【数３１】
2004334845.tif 000016
【００６９】
内に存在するかどうかを判断するために使用される。
ルーチン「ｄｅｃｏｄｅ」は、複数のデータ記憶ユニットを含む３次元データ記憶ボリューム
【００７０】
【数３２】
2004334845.tif 000017
【００７１】
のデータを復号する方法を提供する。
この方法は、３次元データ記憶ボリューム
【００７２】
【数３３】
2004334845.tif 000018
【００７３】
内のデータ値の符号化に使用される積符号に関連したパリティチェック行列の転置を使用して初期シンドロームボリュームを計算するステップと、初期シンドロームボリューム内のベクトルに復号器を適用することにより、初期シンドロームボリュームから２次シンドロームボリュームを計算するステップと、２次シンドロームボリュームおよび３次元データ記憶ボリューム
【００７４】
【数３４】
2004334845.tif 000019
【００７５】
の平面から３次元記憶ボリューム
【００７６】
【数３５】
2004334845.tif 000020
【００７７】
内の複数の平面破損エラーを判断するステップと、平面破損エラーが検出されると、エラーボリュームを計算して、そのエラーボリュームを３次元データ記憶ボリューム
【００７８】
【数３６】
2004334845.tif 000021
【００７９】
から減算することにより、その平面破損エラーを訂正する訂正するステップとを含む。
【００８０】
ルーチン「ｄｅｃｏｄｅ」は、次の宣言を含む
１ ROUTINE DECODE
２ Declarations:
３
４  ｔ    符号化されたボリュームに許容されるタイプ１エラーの個数
５  F    ｑ個の要素からなる体
６  Ｓｘ、
【００８１】
【数３７】
2004334845.tif 000022
【００８２】
、ΔＳｘ    寸法ｒｘ×ｎｙ×ｎｚのセルのボリューム。
各セルは、体Fの要素を含む。
７
８  Ｓｙ、
【００８３】
【数３８】
2004334845.tif 000023
【００８４】
、ΔＳｙ    寸法ｎｘ×ｒｙ×ｎｚのセルのボリューム。
各セルは、体Fの要素を含む。
９
１０  Ｅ    寸法ｎｘ×ｎｙ×ｎｚのセルのボリューム。
各セルは、体Ｆの要素を含む。
１１
１２  Ｌ    ｘｙスライスの異なるｚインデックスの集合
１３        その集合のメンバの個数を返すｓｉｚｅ（）（サイズ（））、その集合の最初のメンバを返すｇｅｔＦｉｒｓｔ（）（最初の取得（））、およびその集合の連続した次のメンバを返すｇｅｔＮｅｘｔ（）（次の取得（））を含む。
１４
１５
１６
１７
【００８５】
【数３９】
2004334845.tif 000024
【００８６】
寸法ｎｘ×ｎｙ×ｎｚのセルの受信ボリューム
１８        各セルは、体Ｆの要素を含む。
１９  Σ    寸法ｎｘ×ｎｙのセルの平面
２０        各セルは、体Ｆの要素を含む。
２１  Ｄ１ｘ    ｒｘ＝ｎｘ−ｋｘを有する組織線形符号Ｃｘ［ｎｘ，ｋｘ，３］の１エラー訂正復号器
２２
２３  Ｄ１ｙ    ｒｙ＝ｎｙ−ｋｙを有する組織線形符号Ｃｙ［ｎｙ，ｋｙ，３］の１エラー訂正復号器
２４
２５  Ｄ１ｚ    ｒｚ＝ｎｚ−ｋｚを有する組織線形符号Ｃｚ［ｎｚ，ｋｚ，２ｔ＋１］の１エラー訂正復号器
２６
２７  Ｄｔｚ    ｒｚ＝ｎｚ−ｋｚを有する組織線形符号Ｃｚ［ｎｚ，ｋｚ，２ｔ＋１］のｔエラー訂正復号器
２８
２９
３０  Ｄ１ｚ'    ｒｚ＝ｎｚ−ｋｚ'を有する組織線形符号Ｃｚ'［ｎｚ，ｋｚ'，ｔ＋１］の１エラー訂正復号器
３１
３２  Ｄｔｚ'    ｒｚ＝ｎｚ−ｋｚ'を有する組織線形符号Ｃｚ'［ｎｚ，ｋｚ'，ｔ＋１］のｔ消去訂正復号器
３３
３４  ｘ，ｙ，ｚ    整数
３５  ｇｅｔＤａｔａ（）    体Ｆの情報要素を含む符号化されたボリュームを得て、その情報要素を
【００８７】
【数４０】
2004334845.tif 000025
【００８８】
に記憶する。
３６
３７  ｅｒｒｏｒ（）    復号障害ルーチン
３８  ｏｕｔｐｕｔ（Ｖ）    体Ｆの情報要素を含む、訂正を受けた、符号化されたボリュームを出力する。
３９
４０
【００８９】
ライン４の定数ｔは、上記で宣言されるように、十字交差エラーの個数であり、説明する符号化技法が、説明する本発明の実施の形態によって検出して訂正するように設計された個数である。
上記ライン６〜９で宣言されるシンドロームボリュームＳｘ、
【００９０】
【数４１】
2004334845.tif 000026
【００９１】
、ΔＳｘ、Ｓｙ、
【００９２】
【数４２】
2004334845.tif 000027
【００９３】
、およびΔＳｙは、すべて、上記宣言で指定した寸法を有するデータ記憶ユニットのボリュームであり、上記ライン１７〜１８で宣言される受信３次元データ記憶ボリューム
【００９４】
【数４３】
2004334845.tif 000028
【００９５】
の計算されたシンドロームを記憶するために使用される。
上記ライン１０〜１１で宣言される３次元データ記憶ボリュームＥは、上述したエラーベクトルｅの３Ｄの類似物であるエラーボリュームを記憶する。
上記ライン１２〜１６で宣言される集合Ｌは、エラーを含むと判断される受信３次元データ記憶ボリューム
【００９６】
【数４４】
2004334845.tif 000029
【００９７】
のｘｙスライスのｚインデックスを含む。
この集合Ｌは、含まれるｚインデックスの個数を報告し、含まれるｚインデックスにアクセスするためのメンバ関数「ｓｉｚｅ」、「ｇｅｔＦｉｒｓｔ」、および「ｇｅｔＮｅｘｔ」を使用する。
寸法ｎｘ×ｎｙのセルの平面は、ライン１９〜２０のセル配列「Ｓ」として宣言される。
このセル配列は、
【００９８】
【数４５】
2004334845.tif 000030
【００９９】
のｚ平面の和を求めるために使用される。
上記ライン２１〜３３で宣言される復号器Ｄ１ｘ、Ｄ１ｙ、Ｄ１ｚ、Ｄｔｚ、Ｄ１ｚ'、およびＤｔｚ'は、上述したルーチン「ｅｎｃｏｄｅ」で使用される組織線形ブロック符号化器に対応する線形ブロック復号器である。
これらの復号器は、上記宣言に付随したコメントに説明されている。
ライン３４では、ルーチン「ｄｅｃｏｄｅ」内で使用される整数ｘ、ｙ、およびｚが宣言される。
上記ライン３５で宣言される関数「ｇｅｔＤａｔａ」は、データ記憶源またはデータ伝送源からの符号化された情報要素を得て、それらの情報要素を３次元データ記憶ボリューム
【０１００】
【数４６】
2004334845.tif 000031
【０１０１】
に置く。
上記ライン３７で宣言される関数「ｅｒｒｏｒ（エラー）」は、復号障害を報告する。
上記ライン３８で宣言される関数「ｏｕｔｐｕｔ（出力）」は、訂正を受けた、符号化された情報シンボルを出力ストリームに出力する。
【０１０２】
ルーチン「ｄｅｃｏｄｅ」は、以下に提供するサブルーチンｃｏｍｐｕｔｅＥ（Ｅを計算）を使用する。
１ Routine computeE
２
３  ２つの方程式を満たすＥｚを計算して返す。
４
【０１０３】
【数４７】
2004334845.tif 000032
【０１０４】
５
【０１０５】
【数４８】
2004334845.tif 000033
【０１０６】
このサブルーチンは、当該ルーチンのライン４および５に設けられた２つの行列方程式を満たすエラーボリュームのｘｙスライスＥｚを計算する。
ＨｘＴおよびＨｙＴは、上述したルーチン「ｅｎｃｏｄｅ」で使用される組織線形ブロック符号ＣｘおよびＣｙのパリティチェック行列ＨｘおよびＨｙを転置することにより得られる。
２つの制約方程式を満たすエラーボリュームのｘｙスライスを計算することは、エラー制御符号化およびエラー制御復号においては、既知の数学的問題であり、当業者は、さまざまな既知の技法を提供することができる。
この計算には、復号器Ｄ１ｘおよびＤ１ｙが使用される。
【０１０７】
【数４９】
2004334845.tif 000034
【０１０８】
の各ｘラインから、Ｄ１ｘは、Ｅｚの各ｘラインを計算する。
次に、
【０１０９】
【数５０】
2004334845.tif 000035
【０１１０】
の各ｙラインから、Ｄ１ｙは、Ｅｚの各ｙラインを計算する。
図４を参照して、Ｅｚを、その図の十字交差パターンを含むｘｙスライスとし、そのパターンをエラーパターンとみなす。
ｘライン４０２を除くＥｚの各ｘラインは、多くとも１つのエラーしか含まないので、復号器Ｄ１ｘは、おそらく４０６を除くＥｚ内のｙライン４０４のすべての項目を復元するが、ｘライン４０２を誤って復号することがある。
その復号器は、Ｅｚのただ１つの破損したｘラインであるｘライン４０２を残す。
このｘライン４０２は、Ｄ１ｙに訂正される。
【０１１１】
ルーチン「ｄｅｃｏｄｅ」の本体は、次のようになる。
【０１１２】
【数５１】
2004334845.tif 000036
【数５２】
2004334845.tif 000037
【０１１３】
まず、上記ライン３において、受信されるか、または、検索される符号化情報が取得され、ルーチンｇｅｔＤａｔａの呼び出しを介して、３次元データ記憶ボリューム
【０１１４】
【数５３】
2004334845.tif 000038
【０１１５】
に置かれる。
次に、ライン４〜８のｆｏｒループにおいて、２つの初期シンドロームボリューム
【０１１６】
【数５４】
2004334845.tif 000039
【０１１７】
および
【０１１８】
【数５５】
2004334845.tif 000040
【０１１９】
が、３次元データ記憶ボリューム
【０１２０】
【数５６】
2004334845.tif 000041
【０１２１】
内に連続的なｘｙスライスの行列乗算によって計算される。
この行列乗算は、上述したルーチン「ｅｎｃｏｄｅ」に使用される組織線形ブロック符号ＣｘおよびＣｙのパリティチェック行列ＨｘおよびＨｙの転置行列によって行われる。
図２６は、シンドロームボリューム
【０１２２】
【数５７】
2004334845.tif 000042
【０１２３】
の計算を示している。
３次元データ記憶ボリューム
【０１２４】
【数５８】
2004334845.tif 000043
【０１２５】
２６０４の各ｘｙスライス、例えばｘｙスライス２６０２は、符号Ｃｘのパリティチェック行列Ｈｘのｎｘ×ｒｘ転置行列２６０６と乗算されて、ｎｙ×ｒｘのｘｙスライス２６０８が、シンドロームボリューム
【０１２６】
【数５９】
2004334845.tif 000044
【０１２７】
２６１０内に生成される。
図２７は、図２６と同様の方法によるシンドロームボリューム
【０１２８】
【数６０】
2004334845.tif 000045
【０１２９】
の計算を示している。
【０１３０】
ライン９で、エラーボリュームＥは、すべてのデータ記憶ユニットに値「０」を含むように設定される。
次に、初期シンドロームボリューム内のベクトルに復号器を適用することにより、初期シンドロームボリュームから、２次シンドロームボリュームが計算される。
ライン１０〜１３のｆｏｒループにおいて、シンドロームボリュームＳｘのｚラインが、シンドロームボリューム
【０１３１】
【数６１】
2004334845.tif 000046
【０１３２】
からの対応するｚラインを復号することにより計算される。
同様に、ライン１４〜１７のｆｏｒループにおいて、シンドロームボリュームＳｙのｚラインが、シンドロームボリューム
【０１３３】
【数６２】
2004334845.tif 000047
【０１３４】
の対応するｚラインを復号することにより計算される。
ライン１９では、集合Ｌが、ｚ座標を含まないように初期化される。
次に、ライン２１〜２４のｆｏｒループにおいて、シンドロームボリュームＳｘおよびＳｙ内の各ｘｙスライスが、破損したｘｙスライスを検出するために検査され、ｚ軸座標ｚを有する破損したｘｙスライスをそれぞれ検出することにより、そのｚ軸座標ｚが集合Ｌに置かれる。
平面破損エラーの個数は、集合Ｌに置かれたｚ軸座標の個数に基づいて決定することができる。
【０１３５】
ライン２５において、ルーチン「ｄｅｃｏｄｅ」は、ライン２１〜２４のｆｏｒループでエラーが検出されたかどうかを判断する。
エラーが検出された場合には、ライン２７で、ルーチン「ｄｅｃｏｄｅ」は、セル配列Ｓを０の値を含むように設定し、次に、ライン２８〜３１のｆｏｒループで、
【０１３６】
【数６３】
2004334845.tif 000048
【０１３７】
のｘｙスライスの和をＳに加算する。
次に、ライン３２で、ルーチン「ｄｅｃｏｄｅ」は、３次元データ記憶ボリューム
【０１３８】
【数６４】
2004334845.tif 000049
【０１３９】
に、パリティエラーが存在するかどうかを判断する。
パリティエラーは、Ｓのゼロでない値によって示される。
パリティエラーが存在する場合において、ｔの値が１であるときは、復号エラーが、ライン３６で返されて、ルーチン「ｄｅｃｏｄｅ」は，ライン３７で終了する。
ｔが１である場合、エラーを訂正することができない。
次に、ライン３９〜４３のネストしたｆｏｒループにおいて、シンドロームボリューム
【０１４０】
【数６５】
2004334845.tif 000050
【０１４１】
および
【０１４２】
【数６６】
2004334845.tif 000051
【０１４３】
のｚラインが、エラーを検出するためにチェックされ、エラーが発見されると、ｘｙスライスのｚ軸座標が、集合Ｌに記憶される。
集合Ｌが、この時、ルーチン「ｄｅｃｏｄｅ」のライン４４によって検出されるように、１とは異なるサイズを有する場合には、エラーが、ライン４６で返され、ルーチン「ｄｅｃｏｄｅ」は、ライン４７で終了する。
上述したように、本発明の一実施の形態を表すエラー制御符号化／復号技法によると、１つの破損したｘｙスライスしか訂正することができないので、この場合、終了は適切な動作である。
そうでない場合において、上記ライン２５の判断として、エラーが検出されないときは、３次元データ記憶ボリューム
【０１４４】
【数６７】
2004334845.tif 000052
【０１４５】
内の符号化された情報シンボルが、ライン５２で出力され、ルーチン「ｄｅｃｏｄｅ」は、ライン５３で終了する。
平文の情報シンボルは、ルーチン「ｅｎｃｏｄｅ」による符号化中に記憶された順序と逆の順序で平文の情報シンボルを単に抽出することにより、符号化された情報シンボルの出力から抽出できることに留意されたい。
【０１４６】
次に、ルーチン「ｄｅｃｏｄｅ」は、ライン５６で、単一のエラーが検出されたかどうかを判断する。
単一のエラーが検出された場合には、単一の平面破損エラーが検出され、その平面破損エラーは、エラーボリュームを計算して、３次元データ記憶ボリューム
【０１４７】
【数６８】
2004334845.tif 000053
【０１４８】
からエラーボリュームを減算することにより訂正することができる。
エラーボリュームＥ内のｘｙスライスは、３次元データ記憶ボリューム
【０１４９】
【数６９】
2004334845.tif 000054
【０１５０】
内のすべてのｘｙスライスの和を求めることにより計算することができる。
このエラーボリュームを、３次元データ記憶ボリューム
【０１５１】
【数７０】
2004334845.tif 000055
【０１５２】
から減算して、ライン５９で出力することができる。
ライン６１の判断として、２以上で、かつ、ｔ個以下のエラーが検出されると、ライン６３〜６７およびライン６８〜７２のｆｏｒループで、ルーチン「ｄｅｃｏｄｅ」は、シンドロームボリューム
【０１５３】
【数７１】
2004334845.tif 000056
【０１５４】
および
【０１５５】
【数７２】
2004334845.tif 000057
【０１５６】
の対応するｚラインを復号することにより、シンドロームボリュームＳｘおよびＳｙの計算を終了する。
次に、ライン７３および７４で、ルーチン「ｄｅｃｏｄｅ」は、計算した初期シンドロームボリュームを、計算した２次シンドロームボリュームから減算することにより、差分シンドロームボリュームΔＳｘおよびΔＳｙを計算する。
次に、ライン７６〜８０のｗｈｉｌｅループで、ルーチン「ｄｅｃｏｄｅ」は、エラーボリュームＥのｘｙスライスを計算し、最後に、エラーボリュームＥを３次元データ記憶ボリューム
【０１５７】
【数７３】
2004334845.tif 000058
【０１５８】
から減算した結果を出力する。
しかしながら、ｔ個よりも多くのエラーがある場合、換言すると、エラーの個数が、本発明の一実施の形態を表すエラー訂正技法の設計限界を超えている場合には、エラーが、ライン８３で返される。
【０１５９】
以上に示した本発明にかかる処理は、例えば、コンピュータ上で動作する専用のハードウエア、あるいは、コンピュータにより実行されるソフトウエアにより実現されることは、当業者にとって自明のことである。
また、本発明にかかる処理がソフトウエアにより実現されるときには、このソフトウエアは、記録媒体に記録されてコンピュータに供給され、記録媒体から読み出され、コンピュータのメモリにロードされて実行されることも、当業者にとって自明のことである。
【０１６０】
本発明を特定の実施の形態の観点から説明してきたが、本発明をこの実施の形態に限定することを意図したものではない。
当業者には、本発明の精神の範囲内に含まれる変更が容易に分かる。
例えば、本発明の方法は、多数のプログラム言語の任意のものを使用するほぼ無限の個数の方法で、かつ、ほぼ無限個の異なる制御構造、モジュール編成、および他のこのような特徴で実施することができる。
特別な場合に、短く巡回するｆｏｒループ、ならびに、全行列ではなく部分行列の乗算および他の処理によって、一定の効率性を得ることができる。
本発明の技法は、ほぼ無限個の異なるタイプの体からの要素を含む多くの異なる寸法の３次元データ記憶ボリュームに適用することができる。
多種多様の適切な組織線形ブロック符号化器および対応する復号器が、本発明によって使用可能である。
もちろん、３次元データ記憶ボリュームの論理的なｘ軸、ｙ軸、およびｚ軸の向き、ならびに、３次元データ記憶ボリュームの他のコンポーネントおよびサブコンポーネントを、物理的なデータ記憶媒体に対して任意に適応させることができる。
別のエラー検出機能およびエラー訂正機能の追加が必要とされる場合には、本発明の範囲内の代わりの方法を考え出すことができる。
例えば、パリティチェックシンボルをより多く使用すると、２つまたは３つ以上のｘｙスライスエラーを訂正することができる。
本発明の実施の形態を表す方法を上述したが、本発明は、これらの方法のさまざまなソフトウェアの実施態様、および、これらの方法を使用して３次元記憶ボリュームに情報を符号化するさまざまなコンピュータシステムを包含する。
【０１６１】
上記説明は、説明のためのものであり、具体的な専門用語を使用して本発明の十分な理解を提供した。
しかしながら、これらの具体的な詳細は、本発明の実践するために必要とされないことが当業者にはよく分かる。
本発明の特定の実施の形態の上記説明は、例示および説明の目的で提供される。
上記説明は、本発明を網羅することを意図するものでもなく、また、開示した正確な形に本発明を限定することを意図するものでもない。
多くの変更および変形が、上記教示に鑑みて可能であることは明らかである。
実施の形態は、本発明の原理およびその実際の応用を最もよく説明するために、図示して説明したものである。
それによって、他の当業者は、本発明と、意図する特定の使用に適するようなさまざまな変更を有するさまざまな実施の形態とを最もよく利用することが可能になる。
本発明の範囲は、添付の特許請求の範囲およびその均等物によって画定されることが意図されている。
【図面の簡単な説明】
【０１６２】
【図１】本発明の一実施の形態を表す方法によってデータが符号化される３次元データ記憶媒体を示す図である。
【図２】３次元データ記憶ボリュームＶ内のｚラインを示す図である。
【図３】３次元データ記憶ボリュームＶ内のｘｙスライスを示す図である。
【図４】データ記憶ボリュームＶ内のデータ記憶ユニットの十字交差を示す図である。
【図５Ａ】本発明の一実施の形態を実践できるデータ記憶ボリューム内のデータ記憶ユニットを示している。
【図５Ｂ】データ記憶ユニットｆの可能な値のそれぞれを、ビットＡ〜Ｄのビット値の順序付けられた異なる組み合わせとして考えることができることを示している。
【図６】１６要素の体Ｆの４ビット要素ｆを含む３次元データ記憶ボリュームＶのデータ記憶ユニットを示す図である。
【図７】符号化プロセスおよび復号プロセスを示す図である。
【図８】積符号によって生成される符号配列のレイアウトを示す図である。
【図９】ｎｚ−１個のｘｙスライスを有する３次元データ記憶ボリュームＶを満たす様子を示す図である。
【図１０】ｎｚ−１個のｘｙスライスを有する３次元データ記憶ボリュームＶを満たす様子を示す図である。
【図１１】ｎｚ−１個のｘｙスライスを有する３次元データ記憶ボリュームＶを満たす様子を示す図である。
【図１２】ｎｚ−１個のｘｙスライスを有する３次元データ記憶ボリュームＶを満たす様子を示す図である。
【図１３】ｎｚ−１個のｘｙスライスを有する３次元データ記憶ボリュームＶを満たす様子を示す図である。
【図１４】ｚ座標「０」を有するボリュームＶのｘｙスライスにｚラインのセルの和の加法の逆元を記憶する様子を示す図である。
【図１５】ｚ座標「０」を有するボリュームＶのｘｙスライスにｚラインのセルの和の加法の逆元を記憶する様子を示す図である。
【図１６】本発明の一実施の形態の擬似コードの実施態様におけるライン１１〜２４のネストしたｆｏｒループの実行後の３次元データ記憶ボリュームＶの内容を示す図である。
【図１７】ボリュームＶ'の部分的なｙｚスライスおよびｘｚスライスを満たす様子を示す図である。
【図１８】ボリュームＶ'の部分的なｙｚスライスおよびｘｚスライスを満たす様子を示す図である。
【図１９】ルーチン「ｅｎｃｏｄｅ」のライン２５〜３０およびライン３１〜３６のネストしたｆｏｒループの実行結果を示す図である。
【図２０】投影ベクトルの計算を示す図である。
【図２１】計算された投影ベクトルを使用して、３次元データ記憶ボリュームＶ'のｚラインにデータを記憶する様子を示す図である。
【図２２】３次元データ記憶ボリュームＶ'の最右端のｙｚスライスへのデータの入力を示す図である。
【図２３】３次元データ記憶ボリュームＶ'内のパリティチェックシンボルを示す図である。
【図２４】本発明の一実施の形態の擬似コードの実施態様におけるライン５１〜５５のネストしたｆｏｒループの操作を示す図である。
【図２５】ルーチン「ｅｎｃｏｄｅ」によって実行される符号化操作の最終的な結果を示す図である。
【図２６】シンドロームボリューム
【数７４】
2004334845.tif 000059
の計算を示す図である。
【図２７】図２６と同様の方法によるシンドロームボリューム
【数７５】
2004334845.tif 000060
の計算を示す図である。
【符号の説明】
【０１６３】
１００・・・３次元データ記憶ボリュームＶ、
１０２・・・セル、
１０４〜８・・・直交軸ｘ，ｙ，ｚ、
２０２・・・ｚライン、
４０２・・・ｘライン、
４０４・・・ｙライン、
４０６・・・データ記憶ユニット、
５０２・・・データ記憶ユニット、
７０２・・・配列、
７０４・・・配列、
８０４〜８０６・・・パリティチェックシンボル領域、
９０２・・・行、
９０４・・・行、
１００２・・・ｘｙスライス、
１００４・・・領域、
１００６・・・領域、
１１０２・・・列、
１１０４・・・要素、
１１０２・・・列、
１３０２・・・情報要素、
１３０４，１３０６・・・パリティチェック要素、
１４０２・・・ｚライン、
１４０４・・・データ記憶ユニット、
１６０６・・・データ記憶ユニット、
１７０２・・・ベクトルμ、
１７０４・・・３次元データ記憶ボリュームＶ、
１７０６・・・ベクトル、
１７０８・・・ベクトル、
１７１０・・・３次元データ記憶ボリュームＶ'、
１８０２・・・・ｙｚスライス、
２００２・・・ｘｚ平面、
２００４・・・投影ベクトル、
２１０２・・・ｚライン、
２１０４・・・投影ベクトル、
２１０６・・・情報要素、
２１０８・・・符号ワードベクトル、
２２０２・・・ｙｚスライス、
２３０６・・・情報シンボル、
２３０８・・・パリティチェックシンボル、
２３０３・・・ｚライン、
２３０４・・・パリティチェックシンボル、
２３０６・・・情報シンボル、
２３０８・・・パリティチェックシンボル、
２５０２・・・ｘｙスライス、
２５０４・・・パリティチェックシンボルの領域、
２６０２・・・ｘｙスライス、
２６０４・・・３次元データ記憶ボリューム、
２６０６・・・転置行列、
２６０８・・・ｘｙスライス、
【図１】
2004334845.tif 000078
【図２】
2004334845.tif 000079
【図３】
2004334845.tif 000080
【図４】
2004334845.tif 000081
【図５Ａ】
2004334845.tif 000082
【図５Ｂ】
2004334845.tif 000083
【図６】
2004334845.tif 000084
【図７】
2004334845.tif 000085
【図８】
2004334845.tif 000086
【図９】
2004334845.tif 000087
【図１０】
2004334845.tif 000088
【図１１】
2004334845.tif 000089
【図１２】
2004334845.tif 000090
【図１３】
2004334845.tif 000091
【図１４】
2004334845.tif 000092
【図１５】
2004334845.tif 000093
【図１６】
2004334845.tif 000094
【図１７】
2004334845.tif 000095
【図１８】
2004334845.tif 000096
【図１９】
2004334845.tif 000097
【図２０】
2004334845.tif 000098
【図２１】
2004334845.tif 000099
【図２２】
2004334845.tif 000100
【図２３】
2004334845.tif 000101
【図２４】
2004334845.tif 000102
【図２５】
2004334845.tif 000103
【図２６】
2004334845.tif 000104
【図２７】
2004334845.tif 000105