(57)【要約】本発明の実施形態は、エラーまたは消失のフェーズドバースト並びに他のシンボルエラー及びビットエラーを訂正するのに適したECCベースの符号化及び復号化方式を含む。本発明の１実施形態を表す符号化及び復号化方式の各々は、２つ以上のコンポーネントエラー訂正コード及び写像関数f(・)から構成される。本発明の実施形態を表すコンポジットエラー訂正コードは、単一ビットエラー及びシンボルエラーに加えて、コンポーネントコードだけの場合よりも長いフェーズドバーストエラーまたは多くの消失を訂正することができ、他のビットエラー及びシンボルエラーと結合したシンボルエラー及び消失のフェーズドバーストを訂正するためにこれまでに開発されているECCベースの符号化及び復号化方式よりも効率が良い。【選択図】図１５Ａ
2011514743.tif 000002
【特許請求の範囲】
【請求項１】
Ｋ個の情報シンボルを符号化するための方法であって、
第１のコンポーネントコードＣ１を用いて、長さＮ１のシンボルのＣ１符号語
【数２６９】
2011514743.tif 000277
中のＫ１個の情報シンボルを符号化するステップと、
第２のコンポーネントコードＣ２を用いて、長さＮ２のＣ２符号語
【数２７０】
2011514743.tif 000278
中のＫ２個の情報シンボルを符号化するステップと、
【数２７１】
2011514743.tif 000279
の非恒等写像
【数２７２】
2011514743.tif 000280
を
【数２７３】
2011514743.tif 000281
に追加することによって、長さＮ２のシンボルのベクトル
【数２７４】
2011514743.tif 000282
を生成するステップと、
【数２７５】
2011514743.tif 000283
を連結することによって、コンポジットコードＣ符号語を生成するステップ
を含み、
長さＮ＝Ｎ１＋Ｎ２のコンポジット符号語は、Ｋ＝Ｋ１＋Ｋ２個の情報シンボルを含むことからなる、方法。
【請求項２】
コンポーネントコードＣ１及びＣ２とコンポジットコードＣは、各々がＧＦ（ｑ）の要素からなるシンボルを含むＧＦ（ｑ）上の線形ブロック符号である、請求項１の方法。
【請求項３】
コンポーネントコードＣ１及びＣ２とコンポジットコードＣは、各々がＧＦ（２８）の８ビット要素からなるシンボルを含むＧＦ（２８）上の線形ブロック符号である、請求項１の方法。
【請求項４】
Ｎ１が３６個のシンボルに等しく、
Ｋ１が３４個のシンボルに等しく、
Ｎ２が３６個のシンボルに等しく、
Ｋ２が３２個のシンボルに等しく、
Ｎは７２個のシンボルであり、
Ｋは６６個のシンボルである、請求項３の方法。
【請求項５】
前記非恒等写像ｆ（・）が、シンボル毎に、ベクトル
【数２７６】
2011514743.tif 000284
内の各シンボル
【数２７７】
2011514743.tif 000285
に適用されて、特定のタイプの予測されたエラーワードシンボル値に等しいシンボル値の各々を異なるシンボル値に写像する請求項１の方法であって、該異なるシンボル値は、前記Ｃ符号語の復号化時に検出される、予測されたタイプのエラーが、
【数２７８】
2011514743.tif 000286
中で発生したか否かをその後識別するために使用されることができる、方法。
【請求項６】
【数２７９】
2011514743.tif 000287
を満たす逆関数ｆ−１（・）が存在する、請求項１の方法。
【請求項７】
前記非恒等写像ｆ（・）は、２進値「１」を有する単一ビットだけを含むビットタプル表現であるシンボル
【数２８０】
2011514743.tif 000288
を、２進値「１」を有する少なくとも２つのビットを含むビットタプル表現である異なるシンボル
【数２８１】
2011514743.tif 000289
に写像する、請求項１の方法。
【請求項８】
エンコーダを備えるメモリ装置であって、該エンコーダは、該メモリへの格納のために、請求項１の方法によって、受信したワードを符号化することからなる、メモリ装置。
【請求項９】
請求項１の方法によってＫ個の情報シンボルを符号化するためにコンピュータ読み取り可能媒体中に符号化されたコンピュータ命令。
【請求項１０】
Ｋ個の情報シンボルを含む長さＮのコンポジットコードＣ符号語を復号化して、該Ｋ個の情報シンボルを取り出すための方法であって、
Ｋ２個の情報シンボルを含むコンポーネントコードＣ２符号語から符号化中に生成された、Ｋ１個の情報シンボルを含む長さＮ１のコンポーネントコードＣ１符号語及び長さＮ２の修正されたコンポーネントコードＣ２符号語を、前記コンポジットコードＣ符号語から取り出すステップであって、Ｋ＝Ｋ１＋Ｋ２、Ｎ＝Ｎ１＋Ｎ２、非恒等写像関数がｆ（・）であることからなる、ステップと、
Ｃ２デコーダを前記修正されたコンポーネントコードＣ２符号語に適用することによって、前記修正されたコンポーネントコードＣ２符号語から、予測されたコンポーネントコードＣ２符号語
【数２８２】
2011514743.tif 000290
及び、予測されたエラーワード
【数２８３】
2011514743.tif 000291
を生成するステップと、
いくつかの予測されたエラーのタイプのうちのどれが前記コンポジットコードＣ符号語の符号化の後に発生したかを、前記エラーワード
【数２８４】
2011514743.tif 000292
から決定するステップと、
第１の消失閾値数より多くの消失が発生したが、第２のエラー閾値数より少ないエラーが発生した場合に、決定されたエラーを、前記コンポーネントコードＣ１符号語と前記修正されたコンポーネントコードＣ２符号語のいずれかに割り当てるステップと、
前記予測されたコンポーネントコードＣ２符号語
【数２８５】
2011514743.tif 000293
及び、予測されたエラーワード
【数２８６】
2011514743.tif 000294
に基づいて訂正可能なコンポーネントコードＣ１符号語中の前記決定された任意のエラーを訂正するステップと、
Ｃ１デコーダを前記コンポーネントコードＣ１符号語に適用することによって、予測されたコンポーネントコードＣ２符号語
【数２８７】
2011514743.tif 000295
を生成するステップと、
前記予測されたコンポーネントコードＣ２符号語
【数２８８】
2011514743.tif 000296
からＫ１個の情報シンボルを取り出し、及び、前記予測されたコンポーネントコードＣ２符号語
【数２８９】
2011514743.tif 000297
からＫ２個の情報シンボルを取り出して、Ｋ個の取り出された情報シンボルを生成するステップ
を含む、方法。
【請求項１１】
コンポーネントコードＣ１及びＣ２とコンポジットコードＣは、各々がＧＦ（ｑ）の要素からなるシンボルを含むＧＦ（ｑ）上の線形ブロック符号である、請求項１０の方法。
【請求項１２】
コンポーネントコードＣ１及びＣ２とコンポジットコードＣは、各々がＧＦ（２８）の８ビット要素からなるシンボルを含むＧＦ（２８）上の線形ブロック符号である、請求項１０の方法。
【請求項１３】
Ｎ１が３６個のシンボルに等しく、
Ｋ１が３４個のシンボルに等しく、
Ｎ２が３６個のシンボルに等しく、
Ｋ２が３２個のシンボルに等しく、
Ｎは７２個のシンボルであり、
Ｋは６６個のシンボルである、請求項１２の方法。
【請求項１４】
いくつかの予測されたエラーのタイプのうちのどれが前記コンポジットコードＣ符号語の符号化の後に発生したかを、前記エラーワード
【数２９０】
2011514743.tif 000298
から決定するステップが、さらに、
前記コンポジットコードＣ符号語中の追加的に受信した消失したシンボルの指標を考慮して、任意の数の異なるタイプのエラーが、前記コンポジットコードＣ符号語の符号化の後で、該コンポジットコードＣ符号語中で発生したか否かを決定するステップ
を含む、請求項１０の方法。
【請求項１５】
前記いくつかの異なるタイプのエラーが、フェーズドバーストエラー、タイプｔＳエラー、及びタイプ１Ｒエラーを含み、
前記フェーズドバーストエラーが、前記コンポジットコードＣ符号語内のシンボルの隣接するサブブロックの閾値数以内のエラーのあるシンボルのみからなり、
前記タイプｔＳエラーが、最大である閾値数までの数のシンボルの消失したサブブロック、及び、追加のエラーのあるシンボルからなり、
前記タイプ１Ｒエラーが、最大で第１の閾値数までの数の消失したサブブロック、及び、最大で第２の閾値数までの追加の単一ビットエラーからなる、請求項１０の方法。
【請求項１６】
決定されたエラーを前記コンポーネントコードＣ１符号語と前記コンポーネントコードＣ２符号語のいずれかに割り当てる前記ステップが、
予測されたエラーのタイプを示すエラーワード
【数２９１】
2011514743.tif 000299
中の非ゼロシンボルの各々について、該予測されたエラーのタイプのエラーを前記予測されたコンポーネントコードＣ２符号語
【数２９２】
2011514743.tif 000300
に割り当てるステップと、
非恒等写像ｆ（・）の逆関数であるｆ−１（・）によってある予測されたエラーのタイプを示すシンボルに各々が写像されることができるエラーワード
【数２９３】
2011514743.tif 000301
中の非ゼロシンボルの各々
【数２９４】
2011514743.tif 000302
について、予測されたエラーのタイプのうちの１つのエラーをコンポーネントコードＣ１符号語に割り当てるステップ
をさらに含む、請求項１５の方法。
【請求項１７】
前記非恒等写像ｆ（・）が、２進値「１」を有する単一ビットのみを含むビットタプル表現であるシンボル
【数２９５】
2011514743.tif 000303
を、２進値「１」を有する少なくとも２つのビットを含むビットタプル表現であるシンボル
【数２９６】
2011514743.tif 000304
に写像する、請求項１５の方法。
【請求項１８】
予測されたコンポーネントコードＣ２符号語
【数２９７】
2011514743.tif 000305
及び、予測されたエラーワード
【数２９８】
2011514743.tif 000306
に基づいて訂正可能なコンポーネントコードＣ１符号語中の決定された任意のエラーを訂正する前記ステップが、さらに、
消失を含むサブブロックを、前記コンポーネントコードＣ１符号語中で消失したものとしてマークするステップと、
非恒等写像ｆ−１（・）の逆関数によって予測されたエラーのタイプを示すシンボルに写像されることができるエラーワードシンボルに対応するコンポーネントコードＣ１符号語中の任意のシンボルを訂正するステップ
を含む、請求項１５の方法。
【請求項１９】
デコーダを備えるメモリ装置であって、該デコーダが、該メモリ装置のメモリ要素から取り出されたワードを請求項１０の方法によって復号化することからなる、メモリ装置。
【請求項２０】
請求項１０の方法によってＫ個の情報シンボルを符号化するためにコンピュータ読み取り可能媒体中に符号化されたコンピュータ命令。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シンボル列（記号列ともいう）の電子的伝送または電子的記憶装置（電子メモリ）へのシンボル列の格納、及び、電子的記憶装置からのシンボル列の取り出しを含む、エラー及び消失導入チャンネルを通った記号列に生じるエラーまたは消失の訂正に関連する。
【背景技術】
【０００２】
エラー訂正コード（誤り訂正符号：「ＥＣＣ」）の分野は、５０年にわたって十分に調査研究されてきた。多くの様々な問題領域に適用するために、エラー訂正コードに基づく多くの様々なタイプの符号化−復号化方式が開発されてきた。ＥＣＣベースの符号化−復号化方式は、一般に、符号化された情報ストリームに冗長な情報を導入して、その後該情報ストリームに導入された種々のタイプの誤り（エラー）を検出して訂正することができるようにすることを含む。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ほとんどの計算技法に関して、任意の特定の問題領域に適用される任意の特定の符号化−復号化方式に関連して、種々の有利、不利、効率の良さ、効率の悪さが存在する。たとえば、情報ストリームに追加される冗長情報の量が多くなるにつれて、該情報ストリーム内で検出され訂正されることができるエラーの量及びタイプは一般に増加するが、該情報、または、該情報ストリームの伝送空間及び伝送効率は、該冗長情報のオーバーヘッドが大きくなるために減少する。空間の非効率性は、後述する復号化テーブルなどの符号化または復号化に必要な多量のデータを生成して維持するための必要性からも生じうる。別の例として、シンボル効率化符号（symbol efficient code）は、複雑な計算を必要とする場合があり、したがって、計算処理上、または、時間的に効率が悪くなりうる。符号（コード）の全体的な効率は、符号の空間効率と時間効率の合計に関連するが、空間効率は、しばしば、時間効率を犠牲にして得られるものであり、逆もまたそうである。ＥＣＣベースの符号化−復号化方式のいくつかのタイプは、あるタイプのエラーを検出して訂正するのにより適しており、他のタイプのエラーを検出して訂正するのにはそれほど適していない場合がある。新しい問題領域が認識されるにつれ、または、新しいタイプの技術の開発の結果として新しい問題領域が顕在化するにつれ、効率が良くかつ正確な誤り検出及び訂正を提供するために、該新たに認識された問題領域、または、該新たに開発された技術に十分に適合した新しいＥＣＣ、及び、ＥＣＣベースの符号化−復号化方式の継続的な開発が必要とされる。
【課題を解決するための手段】
【０００４】
本発明の実施形態は、誤りまたは消失のフェーズドバースト（phased burst）並びに追加のシンボルエラー及びビットエラーを訂正するのに適したＥＣＣベースの符号化−復号化方式を含む。本発明の１実施形態を表す符号化−復号化方式の各々は、２つ以上のコンポーネントからなるエラー訂正コード及びマッピング関数ｆ（・）から構成される。本発明の実施形態を表すコンポジットエラー訂正コードは、コンポーネントコード単独の場合と、追加のビットエラー及びシンボルエラーと組み合わされたシンボルエラー及び消失のフェーズドバーストを訂正するためにこれまでに開発されているＥＣＣベースの符号化−復号化方式とのいずれよりも、単一ビットエラー及びシンボルエラーに加えて、より長いフェーズドバーストまたはより多数の消失を訂正することができ、該これまでに開発されているＥＣＣベースの符号化−復号化方式よりも効率がよい。
【０００５】
本発明の１実施形態によれば、コンポジットコード（composite code。複合符号またはコンポジット符号ともいう）符号語への情報の符号化は、Ｋ１個の情報シンボルを受信し、第１のコンポーネントコード（コンポーネント符号ともいう。以下同じ）Ｃ１エンコーダによって該Ｋ１個の情報シンボルを符号化して、長さＮ１のシンボルのＣ１符号語（コードワードともいう）
【数１】
2011514743.tif 000003
を生成することによって実施される。次に、Ｋ２個の情報シンボルが、第２のコンポーネントコードＣ２エンコーダによって符号化されて長さＮ２の符号語
【数２】
2011514743.tif 000004
が生成される。長さＮ２のシンボルのベクトル
【数３】
2011514743.tif 000005
は、
【数４】
2011514743.tif 000006
の
【数５】
2011514743.tif 000007
への非恒等写像を追加することによって得られる。最後に、コンポジットコードＣ符号語が、
【数６】
2011514743.tif 000008
を連結（または結合）することによって生成される。
【０００６】
本発明の１実施形態によれば、コンポジットコード符号語の復号化（デコード）は、コンポーネントコード符号語を復号することによって実行される。Ｋ１個の情報シンボルを含む長さＮ１のコンポーネントコードＣ１符号語
【数７】
2011514743.tif 000009
及び、長さＮ２の修正されたコンポーネントコードＣ２符号語
【数８】
2011514743.tif 000010
が、Ｋ２個の情報シンボルを含むコンポーネントコードＣ２符号語
【数９】
2011514743.tif 000011
から、符号化中に生成され、これらの符号語、及び、非恒等写像関数ｆ（・）が、コンポジットコードＣ符号語から抽出される（すなわち、取り出される）。ここで、Ｋ＝Ｋ１＋Ｋ２、Ｎ＝Ｎ１＋Ｎ２である。次に、推定されたコンポーネントコードＣ２符号語
【数１０】
2011514743.tif 000012
及び、推定されたエラーワード
【数１１】
2011514743.tif 000013
が、修正されたコンポーネントコードＣ２符号語にＣ２デコーダ（復号化器）を適用することによって該修正されたコンポーネントコードＣ２符号語から生成される。コンポジットコードＣ符号語の符号化に続いて発生しうる複数のタイプの予測されるエラーのうちのどれであるかが、エラーワード
【数１２】
2011514743.tif 000014
から決定される。第１の消失閾値数より多い消失が発生したが、第２のエラー閾値数より少ないエラーが発生したときには、決定されたエラーは、コンポーネントコードＣ１符号語、または、修正されたコンポーネントコードＣ２符号語のいずれかに割り当てられて、コンポーネントコードＣ１符号語に割り当てられたときに、該エラーが訂正される。他のエラー及び消失の発生がマーク（または記録）される。推定されたコンポーネントコードＣ１符号語
【数１３】
2011514743.tif 000015
は、推定されたコンポーネントコードＣ１符号語
【数１４】
2011514743.tif 000016
にＣ１デコーダを適用することによって得られる。最後に、Ｋ１個の情報シンボルが、予測されたコンポーネントコードＣ１符号語
【数１５】
2011514743.tif 000017
から抽出され、Ｋ２個の情報シンボルが、予測されたコンポーネントコードＣ２符号語
【数１６】
2011514743.tif 000018
から抽出されて、Ｋ個の抽出された情報シンボルが生成される。
【図面の簡単な説明】
【０００７】
【図１】ＥＣＣベースの符号化及び復号化方式が適用される基本的問題を示す。
【図２】デジタル的に符号化された情報ストリームを種々の異なる視点から示す図である。
【図３Ａ】情報を長さｎの符号語に符号化する系統的線形ブロックコード（線形ブロックコードは線形ブロック符号ともいう。以下同じ）によって生成された可能性のある全ての符号語のベクトル空間Ｖを示す。
【図３Ｂ】図３Ａに示すベクトル空間Ｖの、例示的なコード、すなわち、ベクトルサブ空間を示す。
【図４】任意の２つの符号語
【数１７】
2011514743.tif 000019
の間の距離を示す。
【図５】系統的線形ブロックコードによるｋ個の情報ビットのベクトル
【数１８】
2011514743.tif 000020
の符号化及び伝送を示す。
【図６】図５に関して説明される情報ビットベクトル
【数１９】
2011514743.tif 000021
を符号化して、符号語
【数２０】
2011514743.tif 000022
を生成することを示す。
【図７Ａ】系統的線形ブロックコードに関する例示的な系統的生成行列
【数２１】
2011514743.tif 000023
を示す。
【図７Ｂ】系統的線形ブロックコードに関する例示的な系統的パリティチェック行列
【数２２】
2011514743.tif 000024
を示す。
【図８】パリティチェック行列
【数２３】
2011514743.tif 000025
の転置行列の特性を示す。
【図９】系統的線形ブロックコードの復号化処理の一部を示す。
【図１０】ＧＦ（２）上の任意の系統的線形ブロックコードについて構成されることができる復号化テーブルを示す。
【図１１】ＧＦ（２８）の要素のテーブルの一部を示す。
【図１２】本発明の１実施形態を表すコンポジットコードの基本的な特性を示す。
【図１３】本発明の実施形態で使用されるシンボル対シンボル写像関数ｆ（・）の特徴を示す。
【図１４】シンボル対シンボル写像関数ｆ（・）の２つの異なる実施を示す。
【図１５Ａ】本発明の１実施形態にしたがって、情報ビットをコンポジットコード符号語に符号化するための高レベル制御フロー図である。
【図１５Ｂ】本発明の１実施形態を表すコンポジットコードＣ［７２、６６、５］の構成を示す。
【図１６】情報シンボルの入力ストリームに対して繰り返し実行されることができるコンポジットコード符号語を符号化して、コンポジットコード符号語の出力ストリームを生成する方法を示す。
【図１７Ａ】本発明の１実施形態を表すコンポジットコードの符号語内のサブブロックの概念を示す。
【図１７Ｂ】本発明の１実施形態を表すコンポジットコードが検出して訂正する種々の異なるタイプのエラーを示す。
【図１８】本発明の１実施形態を表すコンポジットコードの復号化のための高レベル制御フロー図を示す。
【図１９】本発明の実施形態を表すコンポジットコードに対する復号化処理の１実施形態を示す制御フロー図である。
【図２０】本発明の実施形態を表すコンポジットコードに対する復号化処理の１実施形態を示す制御フロー図である。
【図２１】本発明の１実施形態を表すコンポジットコードに対する復号化方法の各ステップで受信された情報を示す。
【図２２】本発明の実施形態を利用することができる物理的記憶装置のブロック図を示す。
【図２３】図２２に示す物理的記憶装置の電子データ記憶コンポーネントを共に構成するＤＲＡＭユニットのバンク内のＤＲＡＭユニットと符号語シンボルとの間の写像（マッピング）を示す。
【発明を実施するための形態】
【０００８】
本発明の詳細な説明
本発明は、消滅及びエラーを導入するチャンネルを通過したシンボル列における、シンボルエラー及び／または消失のフェーズドバースト、その他の単一ビットエラー及びシンボルエラーをそれぞれ検出して訂正するために適したエラー訂正コード（ＥＣＣ）及びＥＣＣベースの符号化及び復号化方式に向けられている。本発明は、下記の３つのサブセクションにおいて説明される。第１のサブセクションでは、エラー訂正コードの１つのファミリーの概観が提供される。これらのエラー訂正コードは、本発明の実施形態を表すコンポジットＥＣＣを構成するために使用されることができるコンポーネントＥＣＣの例であるが、多くの追加のタイプのＥＣＣを、コンポジットＥＣＣのコンポーネント（要素）として使用することができる。その次のサブセクションでは、群（group）及び体（field）の概要が提供される。最後の第３のサブセクションでは、本発明が向けられているコンポジットコード及びコンポジットコードベースの符号化及び復号化方式が、１つの開示されたコンポジットコードのための符号化及び復号化法の詳細な説明と共に説明される。
【０００９】
系統的線形ブロックコード
図１は、ＥＣＣベースの符号化及び復号化方式が適用される基本的な問題を示す。図１において、２進符号化された情報ストリーム１０２が、エラーを導入するチャンネル（以下、エラー導入チャンネルという）１０５の特性を表すメモリ、通信システム、または、他の電子デバイス（電子装置）、サブシステム、またはシステム１０４に入力される。その後、デジタル的に符号化された情報ストリームが、メモリ、通信システム、または、他の電子デバイス（電子装置）、サブシステム、または、システム１０４から取り出される（１０６）。取り出された情報ストリーム１０６は、入力された元の情報ストリーム１０２と同じであることが望ましく、かつ、一般的に必要とされる。メモリ、通信システム、または、他の電子デバイス（電子装置）、サブシステム、または、システム１０４に入力された情報をエラーなく復元するために、エンコーダ１０８を使用して、情報ストリーム中に冗長情報を導入することができ、デコーダ１１０を使用して、その冗長情報を利用して、メモリ、通信システム、または、他の電子デバイス（電子装置）、サブシステム、または、システム１０４のエラー導入チャンネル特性によって導入された任意のエラーを検出して訂正することができる。図１において、２進符号化された情報ストリームは、入力される（１０２）ときには左から右方向で表されており、取り出される（１０６）ときには右から左方向で表されている。しかしながら、ＥＣＣベースの符号化及び復号化方式の一般的な説明では、符号化情報は、一般に、ビット毎またはバイト毎に順次（または連続的に）伝送され、その後、受信時に再度組み立てられるという了解の下に、符号化情報ストリームは、該情報ストリームが入力情報ストリームを表すか受信情報ストリームを表すかに関係なく、一般に、左から右方向の順で表される。
【００１０】
エラー導入チャンネル特性を、電子通信媒体によって表すことができ、それらの媒体には、一方の端部にある送信ポートと他方の端部にある受信ポートを有する光ファーバーケーブル、イーサネットポート、及び、イーサネットリンクによって接続されたコンピューティング装置に含まれているコントローラを有するイーサネットリンク、及び、他のよく知られている電子通信媒体がある。代替的には、エラー導入チャンネル特性を、種々のタイプの電気的メモリ、大容量記憶装置、または、ＤＶＤやＣＤなどの物理的データ記憶媒体を含む情報記憶装置または情報記憶要素（情報記憶コンポーネント）によって表すことができる。通信媒体の場合には、送信ポートに最初に入力された情報ストリームを、その後、受信ポートによって破損した情報ストリームとして受信する場合があり、この場合、その受信した情報ストリームには、ポート処理コンポーネント、伝送媒体中のノイズ、及び、他のそのようなエラー導入現象によって導入されたエラーが含まれている。記憶媒体の場合には、該記憶媒体に入力された最初の情報ストリームが、その後、破損した形態で該記憶媒体から取り出される場合があり、この場合、その情報ストリームには、記憶コンポーネントコントローラ及び他の処理コンポーネントによって導入されたエラー、及び、ノイズ及び伝送媒体、及び、該記憶媒体における電子的、磁気的、及び／または光学的不安定性によって導入されたエラーが含まれている。
【００１１】
符号化された情報ストリームを破損させうる種々のタイプのエラーがある。ランダムなビットエラーまたはシンボルエラーは、情報ストリーム内のいくつかのビットのビット値またはシンボルのシンボル値を変化させる場合があり、その場合には、情報ストリーム内のビットまたはシンボルは、既知のまたは見積もることが可能な破損可能性を有する。バーストエラーは、一連の隣接するビット及び／またはシンボルの破損をもたらす。バーストエラーの他にも、多くの異なるタイプの系統誤差（系統的エラー）が生じる場合がある。
【００１２】
図２は、デジタル的に符号化された情報ストリームの種々の異なる外観を示す。デジタル的に符号化された情報ストリームは、順序付けられたビット値のシーケンス（並び）として見ることができ、換言すれば、該情報ストリームは、ビット値の長い直線配列から構成される。代替的には、同じ符号化された情報ストリームは、各シンボルが一定数のビット値からなる順序付けられたシンボルのシーケンスと見ることができる。たとえば、図２において、２進符号化された情報ストリーム２０２は、代替的に、順序付けられた４ビットシンボル２０４のシーケンスと見ることができる。シンボルの順序付けられたシーケンス内の第２のシンボル２０６について図２に示されている値「９」は、符号化された情報ストリーム２０２のビット値表現におけるビット値２０８−２１１の順序付けられた組に対応する。さらに別の視点からは、符号化された情報ストリームは、各ブロックが一定数のシンボルの順序付けられたシーケンスを含む、順序付けられたブロックのシーケンス２１２と見ることができる。最後に、情報ストリームを、系統的線形ブロックコードによって冗長情報を含むように符号化して、後で、エラーを検出して訂正できるようにすることができる。符号化された情報ストリーム２１４は、順序付けられたブロックまたは符号語のシーケンスからなり、この場合、各符号後は、情報ストリーム内の１つのブロックに対応する。たとえば、符号化された情報ストリームの符号語２１６は、情報ストリーム２１２のブロック視点におけるシンボルのブロック２１８に対応する。各符号語は、図２において文字Ｒ'、Ｒ''、及びＲ'''によって表されている追加のシンボル２２０−２２２を含む。この追加のシンボルは、１つのタイプの系統的線形ブロックコードによって情報ストリームに含められた冗長情報を表す。線形ブロックコードの代替のタイプでは、各符号語は、第１の選択された数の情報シンボル、並びに、追加された冗長情報を表す第２の選択された数の追加のシンボルを含むことができ、この場合、情報シンボルに対する冗長情報シンボルの比は、検出することができるエラーまたは消失の数、及び、訂正することができるエラーまたは消失の数と概ね相関関係がある。
【００１３】
よく使用されている１つのタイプのＥＣＣは、有限体ＧＦ（ｑ）上の系統的線形ブロックコードであり、ｑは、コードが定義される体（フィールド）内のシンボルの数を表す。ｑが２の累乗、すなわち、２ｍのときは、この体のシンボルはｍタプルとして表される。ｍが８に等しいときは、シンボルはバイトとして都合よく表される。「ＧＦ（２）」という表記は、２つの要素、すなわち、シンボル、「０」及び「１」を有する２進ガロア体を表す。ＧＦ（２）上の系統的線形ブロックコードによって生成された、符号化された各ブロックまたは符号語に一定数のビットがある場合には、全ての可能性のある符号語は共にベクトル空間を構成する。ベクトル空間は、加算の下での可換性やスカラ乗算の下での閉包を含むいくつかの代数的特性を有し、ベクトル加算及びベクトルのスカラ乗算に関して分配性（分配則）及び結合性（結合則）を有する。図３Ａは、ＧＦ（２）上の長さｎの全ての可能性のあるビットベクトルのベクトル空間Ｖを示す。長さｎの符号語を生成する特定の系統的線形ブロックコードＣは、Ｖのｋ次元ベクトルサブ空間であり、このベクトルサブ空間は、ベクトル空間の全ての特性を有している。図３Ｂは、図３Ａに示すベクトル空間Ｖの例示的なコード、すなわち、ベクトルサブ空間を示す。ベクトルサブ空間におけるｋ次元ベクトルの各々は、情報ストリームからの情報のｋ個のビットを表している。情報のｋ個のビットは、符号語を生成するために、系統的線形ブロックコードによってｒ＝（ｎ−ｋ）個の追加のビットが付け足される。情報ビットの異なる可能性のあるｋ次元ベクトルの各々について、ｒ個の追加ビットまたはパリティビットの１つの特定のパターンが存在する。したがって、系統的線形ブロックコードは、ベクトルサブ空間を構成するベクトル空間Ｖの２ｋ個の異なるｎビットベクトルから構成される。ビットではなく、ＦＧ（ｑ）上の系統的線形ブロックコードの場合、ｎ個のシンボル（これらのうちｋ個のシンボルが情報シンボルであり、（ｎ−ｋ）個のシンボルが冗長情報である）を含む各ベクトルがエラーを検出して訂正するために使用される。ＧＦ（ｑ）上の系統的線形ブロックコードの符号語から構成されるベクトルサブ空間はｑｋ個のベクトルを含んでいる。
【００１４】
ＥＣＣの１つの重要な特徴は、コード（符号）の任意の２つの符号語間の最小距離ｄである。図４は、ＧＦ（２）上のＥＣＣの任意の２つの符号語
【数２４】
2011514743.tif 000026
の間の距離
【数２５】
2011514743.tif 000027
を示す。ベクトル
【数２６】
2011514743.tif 000028
は１２ビット符号語４０２であり、ベクトル
【数２７】
2011514743.tif 000029
は、もう１つの１２ビット符号語４０４である。ビット毎のＸＯＲ演算と等価なモジュロ２減算によって
【数２８】
2011514743.tif 000030
から
【数２９】
2011514743.tif 000031
を減じると、
【数３０】
2011514743.tif 000032
の間の距離
【数３１】
2011514743.tif 000033
が得られる。ＧＦ（２）上のＥＣＣの場合には、ベクトル
【数３２】
2011514743.tif 000034
中のビット値「１」を有するビットの数が、
【数３３】
2011514743.tif 000035
の間の距離
【数３４】
2011514743.tif 000036
に等しい。ＧＦ（ｑ）上のＥＣＣの一般的な場合には、差ベクトル
【数３５】
2011514743.tif 000037
中の非ゼロ位置の数が２つの符号語
【数３６】
2011514743.tif 000038
の間の距離である。任意の特定の符号語
【数３７】
2011514743.tif 000039
の重み
【数３８】
2011514743.tif 000040
は該符号語内の非ゼロ位置の数である。したがって、図４に示す例では、
【数３９】
2011514743.tif 000041
である。
【００１５】
図５は、ｑに関する（またはｑ変数の）系統的線形ブロックコードによるｋ個の情報シンボルのベクトル
【数４０】
2011514743.tif 000042
の符号化（エンコード）及び伝送を示す。ｋ個の情報シンボルは、ｋ次元ベクトル
【数４１】
2011514743.tif 000043
であると見なされる。系統的線形ブロックコードは、ベクトル
【数４２】
2011514743.tif 000044
によって表されるｋ個の情報シンボルを長さｋ＋ｒ＝ｎ  ５０４のベクトル
【数４３】
2011514743.tif 000045
として符号化する。系統的線形ブロックコードは、ｒ個のチェックシンボルまたはパリティシンボルを、ベクトル
【数４４】
2011514743.tif 000046
の長さｒのサブベクトルに、一般的にはベクトル
【数４５】
2011514743.tif 000047
の最初または最後のいずれかにおいて共に配置する。図５及びそれに続く図に示す例では、パリティシンボルｐ０、ｐ１、…、ｐｒ−１  ５０６がベクトル
【数４６】
2011514743.tif 000048
の最初の部分に示されており、ｋ個の情報シンボル５０８がこれに続いている。次に、符号語
【数４７】
2011514743.tif 000049
が通信媒体を通じて伝送され、または、記憶媒体に格納されて、該記憶媒体から取り出されて、対応する受信符号語
【数４８】
2011514743.tif 000050
が生成される。伝送または格納の際にエラーが生じなかったときには、
【数４９】
2011514743.tif 000051
であるが、ランダムな伝送または格納エラーが生じたときには、
【数５０】
2011514743.tif 000052
である。多くの場合に、ベクトル
【数５１】
2011514743.tif 000053
の受信側では、エラーが発生したかしなかったかを確かめるために、
【数５２】
2011514743.tif 000054
を、最初の対応するベクトル
【数５３】
2011514743.tif 000055
と比較することはできない。したがって、ベクトル
【数５４】
2011514743.tif 000056
の受信側は、
【数５５】
2011514743.tif 000057
内の各シンボルまたはビットがある破損確率で破損している場合があることを想定する。したがって、図５において、
【数５６】
2011514743.tif 000058
内のシンボルには、それらのシンボルが既知のまたは推定可能な破損確率でもって破損している場合があることを示すための用意がされている。したがって、符号語
【数５７】
2011514743.tif 000059
内のシンボルｐ０  ５１２は、受信語（受信ワードともいう）
【数５８】
2011514743.tif 000060
中のシンボルｐ０’  ５１４に対応する。
【００１６】
図６は、図５を参照して説明したように、情報−ビットベクトル
【数５９】
2011514743.tif 000061
を符号化して、符号語
【数６０】
2011514743.tif 000062
を生成する様子を示す。所与の系統的線形ブロックコードに対して、ｋ×ｎ行列
【数６１】
2011514743.tif 000063
を見つけて、可能性のある情報−シンボルベクトル
【数６２】
2011514743.tif 000064
の各々に対応する固有の符号語
【数６３】
2011514743.tif 000065
を生成することができる。図６に示すように、
【数６４】
2011514743.tif 000066
に、
【数６５】
2011514743.tif 000067
を乗じて、
【数６６】
2011514743.tif 000068
に対応する符号語
【数６７】
2011514743.tif 000069
を生成する。行列
【数６８】
2011514743.tif 000070
は、系統的線形ブロックコードのための生成行列と呼ばれる。行列
【数６９】
2011514743.tif 000071
は、系統的線形ブロックコードＣのｋ個の線形的に独立した符号語からなる。したがって、系統的線形ブロックコードの符号語は、行列乗算によって情報シンボルの対応するブロックから容易かつ機械的（または自動的）に生成される。実際、各々の行列
【数７０】
2011514743.tif 000072
は、系統的線形ブロックコードを画定する。
【００１７】
図７Ａ及び７Ｂは、系統的線形ブロックコードに対する、例示的な系統的生成行列
【数７１】
2011514743.tif 000073
及び、例示的な系統的パリティチェック行列
【数７２】
2011514743.tif 000074
を示す。図７Ａに示すように、生成行列
【数７３】
2011514743.tif 000075
を、ｋ×ｒの大きさのパリティビット行列
【数７４】
2011514743.tif 000076
と、ｋ×ｋの恒等行列
【数７５】
2011514743.tif 000077
に空間的に分割することができる。パリティビット行列
【数７６】
2011514743.tif 000078
は、行列乗算
【数７７】
2011514743.tif 000079
中に、
【数７８】
2011514743.tif 000080
のｒ個のパリティシンボルを生成し、恒等行列
【数７９】
2011514743.tif 000081
は、符号語
【数８０】
2011514743.tif 000082
内に、
【数８１】
2011514743.tif 000083
のｋ個の情報シンボルを生成する。
【００１８】
系統的線形ブロックコードの各々について、生成行列
【数８２】
2011514743.tif 000084
に対応するパリティチェック行列
【数８３】
2011514743.tif 000085
が存在する。図７Ｂは、パリティチェック行列
【数８４】
2011514743.tif 000086
の形式を示す。図７Ｂから理解されるように、パリティチェック行列は、ｒ×ｒの恒等行列
【数８５】
2011514743.tif 000087
と、パリティチェック行列
【数８６】
2011514743.tif 000088
の転置行列に空間的に分割することができるｒ×ｎ行列である。任意の特定の系統的線形ブロックコードは、生成行列
【数８７】
2011514743.tif 000089
または、生成行列
【数８８】
2011514743.tif 000090
に対応するパリティチェック行列
【数８９】
2011514743.tif 000091
のいずれかによって完全に指定される。パリティチェック行列
【数９０】
2011514743.tif 000092
は、それ自体、各符号語がｒ個の情報シンボルを含む線形コード（線形符号）の生成器である。パリティチェック行列によって生成された線形コードは、生成行列
【数９１】
2011514743.tif 000093
によって生成された系統的線形ブロックコードＣの２重コード（または双対符号）である。図８は、パリティチェック行列
【数９２】
2011514743.tif 000094
の転置行列の特性を示す。図８に示すように、パリティチェック行列
【数９３】
2011514743.tif 000095
の転置行列は、系統的線形ブロックコードＣの符号語
【数９４】
2011514743.tif 000096
に乗じるために使用されると、常に、次元がｒの全てが０のベクトル
【数３３０】
2011514743.tif 000097
を生成する。換言すれば、系統的線形ブロックコードＣの符号語
【数９５】
2011514743.tif 000098
の各々について、
【数９６】
2011514743.tif 000099
である。
【００１９】
図９は、系統的線形ブロックコードの復号化処理の一部を示す。上述したように、受信語
【数９７】
2011514743.tif 000100
は、対応する最初に伝送されたまたは格納された符号語
【数９８】
2011514743.tif 000101
に関してエラーを含んでいる場合がある。上述したように、
【数９９】
2011514743.tif 000102
が両方とも既知の場合に、
【数１００】
2011514743.tif 000103
から
【数１０１】
2011514743.tif 000104
を減じると、冗長ベクトル９０６が生成され、該ベクトルにおいて、非加法単位元シンボル（non-additive-identity symbol）（ＧＦ（２）の場合には「１」）が、ベクトル
【数１０２】
2011514743.tif 000105
が異なる全ての位置に現れる。したがって、
【数１０３】
2011514743.tif 000106
であり、ここで、
【数１０４】
2011514743.tif 000107
は、「エラーベクトル」と呼ばれ、本質的に発生したエラーの写像（マップ）である。もちろん、一般的には、
【数１０５】
2011514743.tif 000108
だけが既知である。したがって、
【数１０６】
2011514743.tif 000109
は、
【数１０７】
2011514743.tif 000110
に等しく、ここで、
【数１０８】
2011514743.tif 000111
はいずれも一般的には既知である。受信語
【数１０９】
2011514743.tif 000112
にパリティチェック行列の転置行列
【数１１０】
2011514743.tif 000113
を乗じると、
【数１１１】
2011514743.tif 000114
の「シンドローム」と呼ばれるｒ次元ベクトル
【数１１２】
2011514743.tif 000115
が生成される。
【数１１３】
2011514743.tif 000116
のシンドロームは、
【数１１４】
2011514743.tif 000117
に等しい。したがって、
【数１１５】
2011514743.tif 000118
である。
【００２０】
図１０は、ＧＦ（ｑ）上の任意の系統的線形ブロックコードに対して構成することができる復号化テーブルを示す。図１０に示すように、「標準配列（standard array）」と呼ばれるｑｒ×ｑｋテーブル１００２を、任意の系統的線形ブロックコードについて構成することができる。標準配列の最初の行１００４は、符号語
【数１１６】
2011514743.tif 000119
の順序付けられたシーケンスである。符号語
【数１１７】
2011514743.tif 000120
は、全て０のシンボルからなるコードベクトル（０、０、…、０）である。標準配列の各々の列ｉは、該列の最初の要素中の符号語
【数１１８】
2011514743.tif 000121
に対応する全ての可能性のある受信語
【数１１９】
2011514743.tif 000122
を含むとみなすことができる。換言すれば、全ての可能性のある受信語
【数１２０】
2011514743.tif 000123
の集合は、ｑｎ個の要素を有しており、各区画が系統的線形ブロックコードＣの符号語に対応するｑｋ個の区画に分割され、この場合、任意の受信語
【数１２１】
2011514743.tif 000124
は、
【数１２２】
2011514743.tif 000125
が属する全ての可能性のある符号語の区画に関連する符号語に対応すると考えられる。たとえば、標準配列
【数１２３】
2011514743.tif 000126
の最初の列１００６の全ての要素は、全て０の符号語
【数１２４】
2011514743.tif 000127
に追加されると、該全て０の符号語
【数１２５】
2011514743.tif 000128
に復号化される受信語を生成する全ての可能性のあるエラーベクトルに対応する。
【００２１】
図９を参照して説明したように、受信語
【数３３１】
2011514743.tif 000129
にパリティチェック行列
【数１２６】
2011514743.tif 000130
の転置行列を乗じることによって、
【数１２７】
2011514743.tif 000131
に等しいシンドロームベクトル
【数３３２】
2011514743.tif 000132
が生成される。標準配列の各行における全ての要素について計算されたシンドロームは、それゆえ、同一であって、
【数１２８】
2011514743.tif 000133
にのみ依存する。したがって、復号化のために、標準配列に含まれている情報を、認識されたエラーパターン
【数１２９】
2011514743.tif 000134
の各々と、そのエラーパターン
【数１３０】
2011514743.tif 000135
に対応するシンドロームとの間の関連性を示す復号化テーブル１００８へと圧縮することができる。系統的線形ブロックコードの符号語の復号化は、符号化と同様に、概念的に比較的単純な次の処理によって実行される。
【数１３１】
2011514743.tif 000136
しかしながら、概念的には単純であるけれども、効率良く復号化可能なコード（符号）を設計することは明らかに労力のかかる作業である。たとえば、復号化テーブルは、中程度及び大きなｑ、ｒ、及び／またはｎ個のパラメータを有するコードついては実際的ではない。なぜなら、復号化テーブル１００８のサイズは２（ｑ’）（ｎ）に比例するからである。したがって、空間と時間の両方に関して効率の良い復号化アルゴリズムを可能にする特性を有するコードを設計するためには、一般に、多大な努力が必要とされる。
【００２２】
図１０に示す標準配列から理解されるように、各符号語に含められているパリティシンボルの数を増やすことによって、より多数の異なるエラーパターンを認識することができる。しかしながら、比ｒ／ｎが大きくなると、符号化の空間効率が減少する。一般的に、系統的線形コードによって認識されるエラーパターンは、エラーパターンが生じる確率が最大になるように選択される。ランダムなビットエラーの場合は、重みが最小のエラーベクトルが一般的には生じる確率が最大になるエラーパターンである。他のタイプのエラーの場合は、異なるエラーパターンの組がより生じる可能性が高い場合がある。
【００２３】
ＧＦ（２）上の系統的線形ブロックコードについて説明したが、リードソロモン符号を含む系統的線形ブロックコードを、任意の体ＧＦ（ｑ）上に同様にして構成することができる。往々にして、一般にＧＦ（２ｍ）として指定されるＧＦ（２）の拡大体（extension field）上に系統的線形ブロックコードを構成することが便利である。ここで、ｍは、１より大きな整数である。
【００２４】
群（Group）及び体（field）
このサブセクションでは、群と体の概要を説明する。群は要素の集合であり、それらの要素に対して２項演算（または２進演算）
【数１３２】
2011514743.tif 000137
が定義される。群は２項演算
【数１３３】
2011514743.tif 000138
に関して閉じている。換言すれば、群の任意の２つの要素ａ１及びａ２について、
【数１３４】
2011514743.tif 000139
である。ここで、ａｉは群の要素でもある。２項演算
【数１３５】
2011514743.tif 000140
は次のような結合性がある。
【数１３６】
2011514743.tif 000141
群は、固有の単位元ｅを有しており、該群内の全ての要素ａｉについて
【数１３７】
2011514743.tif 000142
が成立する逆元
【数１３８】
2011514743.tif 000143
が存在する。
群は、要素ａｉとａｊの任意の対に関して、次のように、可換性があり、すなわち、アーベル群である。
【数１３９】
2011514743.tif 000144
【００２５】
体は、２つの異なる２項演算（または２進演算）に関して可換群（アーベル群）である。一方の演算を「＋」で表し、他方の演算を
【数１４０】
2011514743.tif 000145
で表すことができる。この場合、該演算＋に関する単位元ｅ＋は０に等しく、演算
【数１４１】
2011514743.tif 000146
に関する単元
【数１４２】
2011514743.tif 000147
は１に等しい。さらに、演算
【数１４３】
2011514743.tif 000148
は、次のように分配性がある。
【数１４４】
2011514743.tif 000149
【００２６】
ＧＦ（２）は、モジュロ２加算すなわち２進ＸＯＲ演算と等価な＋演算と、モジュロ２乗算すなわちブールＡＮＤ演算と等価な
【数１４５】
2011514743.tif 000150
演算を有する２進体（２元体、または２進数フィールドともいう）である。ＧＦ（ｑ）は、要素｛０、１、…、ｑ−１｝に対する体であり、ｑは素数である。体ＧＦ（ｑｍ）は、ＧＦ（ｑ）の拡大体（extension field）であり、要素は、ＧＦ（ｑ）中の係数を有する多項式として定義される。ＧＦ（２ｍ）は、ＧＦ（２）の拡大体であり、要素は、ＧＦ（２）中の係数を有する多項式である。
【００２７】
次数ｍの多項式ｐ（ξ）は、ｐ（ξ）がξｎ＋１を分割する最小の正の整数ｎがｎ＝２ｍ−１のときの原始関数である。拡大体ＧＦ（２ｍ）を、多項式要素の体Ｆとして次のように表すことができる。
【数１４６】
2011514743.tif 000151
ここで、αは、１及び０以外の第３のシンボルであり、
【数１４７】
2011514743.tif 000152
である。
Ｆにおける演算
【数１４８】
2011514743.tif 000153
については、
【数１４９】
2011514743.tif 000154
であり、
Ｆにおける演算＋については、
【数１５０】
2011514743.tif 000155
である。Ｆの要素をαの累乗として表すことに加えて、Ｆ内の各要素を、次のように、２値係数を有する多項式として表すこともできる。
【数１５１】
2011514743.tif 000156
Ｆの要素の加算は、多項式加算によって容易に実行され、Ｆの要素の乗算は、αの累乗として表される要素の指数部を加算することによって容易に実行される。
【００２８】
ＧＦ（２８）などの拡大体の場合、ＧＦ（２８）中の各要素に対してテーブルを構成することができ、該テーブルのそれぞれのエントリは、該要素の累乗表現、該要素の多項式表現、及び、該要素の多項式表現の係数を構成する２値のタプルを示している。図１１は、ＧＦ（２８）に対する要素のテーブルの一部を示している。テーブル１１００の最初の列１１０２は、ＧＦ（２８）の要素の累乗表現を示し、中間の列１１０３は、それらの要素の多項式表現を提供しており、最後の列１１０４は、各要素の８ビットの２値係数タプル表現を示す。乗算及び加算について追加のテーブルを構成することができる。したがって、体ＧＦ（２８）を、各要素が８ビットタプルで表される２５６個の要素の集合として表現することができ、この場合、乗算、加算、及び減算は、背景にある多項式に対して実行される演算に基づいてテーブルによって指定される。ＧＦ（２８）の８ビット要素に対する乗算、減算、及び加算は、電子計算機によって支援されるなじみのある２進演算（または２項演算）とは等価ではないことに留意することが重要である。１例として、２進演算では、
【数１５２】
2011514743.tif 000157
であるが、ＧＦ（２８）の加算では、
【数１５３】
2011514743.tif 000158
である。
【００２９】
ＧＦ（２８）の例を提示したのは、開示した本発明の１実施形態において、ＧＦ（２８）上のコンポジットコードがＧＦ（２８）上の２つのコンポーネントコードから構成されるからである。符号語内の各シンボルをＧＦ（２８）の要素を表す８ビットタプルとみなすことができる。ＧＦ（２８）には２５６個の要素があることに留意されたい。したがって、全ての可能性のある８ビットタプルがＧＦ（２８）の要素である。一般的に、符号化及び復号化のために、情報バイトはＧＦ（２８）内のシンボルであるとみなされるが、符号化の前と復号化の後では、情報バイトは標準的な２値符号化バイトとみなされる。本発明の以下の説明においてＧＦ（２８）上の例示的なコードを説明するが、本発明の方法は、任意の体ＧＦ（ｑ）上のコンポジットコードの生成に適用することができる。計算効率のためには、ＧＦ（２ｍ）上のコンポジットコードが望ましく、これは、シンボル表現における効率及び計算処理における効率の点でも望ましい。
【００３０】
本発明の実施形態
本発明は、後述するように、少なくとも２つのコンポーネントコード、及び１つの体のシンボルを写像（マッピング）する１つの関数ｆ（・）を使用して構成されるコンポジットエラー訂正コードのファミリーに向けられており、この場合、該体上のコンポジットコードは該体の他のシンボルに対して定義される。以下では、本発明の実施形態を表すコンポジットコードのファミリーのうちの１つの特定のコンポジットコードが説明される。説明されるコンポジットコードは、拡大体ＧＦ（２８）の８ビットシンボルに対するコードである。しかしながら、任意の体ＧＦ（ｑ）またはＧＦ（ｑｍ）のシンボルに対して構成されたコンポーネントコードを使用して、それらの任意の体のシンボルに対するコンポジットコードを同様に構成することができる。
【００３１】
図１２は、本発明の１実施形態を表すコンポジットコードの基本的な特性を示す。コンポジットコードは、ＧＦ（２８）上に構成され、８ビットのシンボルにおいて長さＮ＝７２の符号語を生成する（Ｎは長さである）。例示的な符号語１２０２を図１２に示す。この符号語は、Ｋ＝６６の情報シンボル及びＲ＝６のパリティチェックシンボルを含んでいる。符号語間の最小距離はＤ＝５シンボルである。このコンポジットコードを、ＧＦ（２）上のコードとみなすこともできる。ＧＦ（２）１２１０上のコンポジットコードの例示的な符号語も図１２に示されている。ＧＦ（２）上の符号語とみなされるときには、各符号語はｎ＝５７６ビットを有し、これらのうちｋ＝５２８ビット１２１２が情報ビットであり、ｒ＝４８ビット１２１４がパリティチェックビットである。符号語間の最小距離は、コードを構成するために使用される特定のコンポーネントコードの性質に依存して、５≦ｄ≦４０の範囲にある。特性Ｎ＝７２、Ｋ＝６６、及びＤ＝５を有する線形ブロックコードは、（Ｄ−１）／２＝２個のシンボルエラーまたは４つのシンボル消失を検出して訂正できることが期待される。しかしながら、本発明の１実施形態を表すコンポジットコードは、（シンボルエラーがバースト状に発生するときには）より多数のシンボルエラー、より多数の消失、及び、エラーバーストおよび消失に加えて、多数のシンボルエラー及びビットエラーを訂正することができる。
【００３２】
本発明の１実施形態を表すコンポジットコードに関する符号化及び復号化方法は、シンボル対シンボル写像関数（マッピング関数）ｆ（・）に依存する。図１３は、本発明の実施形態で使用されるシンボル対シンボル写像関数ｆ（・）の特性を示す。図１３において、ＧＦ（２８）１３０２の２５６個の要素を表す一連の２５６個の８ビットシンボルが部分的に表示されている。集合「Ｍ」１３０４と呼ばれるＧＦ（２８）の２番目〜９番目のシンボルは、各々のシンボルがビット値「１」を有する単一ビットだけを含む８ビット−タプル表現を有するシンボルを含んでいる。集合Ｍ中のこれらの８ビットベクトルは、図１１に示すＧＦ（２８）の表現におけるＧＦ（２８）の要素｛１、α１、α２、…、α７｝に対応する。関数ｆ（・）が線形であって、次のように、厳密な逆関数ｆ（・）−１を有し、集合Ｍの任意のシンボルを集合ＭにはないＧＦ（２８）のシンボルに写像するということを条件として、ＧＦ（２８）のシンボルをＧＦ（２８）の他のシンボルに写像する任意の該関数ｆ（・）を、本発明の１実施形態を表すコンポジットコードの符号化及び復号化のために利用することができる。
【数１５４】
2011514743.tif 000159
【００３３】
図１４は、シンボル対シンボル写像関数ｆ（・）の２つの異なる実施を示す。１つの実施では、ｆ（ｕ）を、シンボルｕのビット−ベクトル表現とｍ×ｍ行列１４０２との乗算として実施することができ、ここで、ｍは、２値拡大体ＧＦ（２ｍ）のｍであって今の例では８であり、該体上にコードが構成される。代替的な実施形態では、ルックアップテーブル１４０４を、可能性のある各シンボルｕに対するｆ（ｕ）値を提供するために用意することができる。ＧＦ（２８）シンボルの場合には、ビット−ベクトル
【数１５５】
2011514743.tif 000160
によって表されているシンボルをバイト値として用いて、ルックアップテーブルを索引付けすることができる。
【００３４】
代替的な実施形態では、写像関数ｆ（・）を異なる関数とすることができる。一般的に、ｆ（・）の目的は、あるタイプのエラーワードシンボルを代替的なシンボル値に写像して、そのタイプのエラーの発生を、予測されたＣ２符号語と復号化中にコンポジットコード符号語から抽出されたＣ１符号語のいずれかに割り当てることができるようにすることである。本発明の全ての実施形態は、非恒等写像関数ｆ（・）を利用する。
【００３５】
関数ｆ（・）は、上述したようにシンボルに適用することができ、または、シンボルのベクトルに適用することができる。たとえば、関数ｆ（・）を符号語
【数３３３】
2011514743.tif 000161
全体に適用して修正された符号語
【数１５６】
2011514743.tif 000162
を生成することができる。この場合、該修正された符号語の対応する各シンボルを生成するために、シンボル関数ｆ（・）が、該符号語の各シンボルに適用される。
【００３６】
図１５Ａは、本発明の１実施形態にしたがって情報ビットをコンポジットコード符号語に符号化するための高レベルの制御フロー図を示す。ステップ１５０２では、Ｋ１個の情報シンボルが受信される。ステップ１５０３では、Ｋ１個の情報シンボルが第１のコンポーネントコードＣ１エンコーダによって符号化されて長さＮ１シンボルのＣ１符号語
【数１５７】
2011514743.tif 000163
が生成される。ステップ１５０４では、Ｋ２個の情報シンボルが第２のコンポーネントコードＣ２エンコーダによって符号化されて、長さＮ２の符号語
【数１５８】
2011514743.tif 000164
が生成される。ステップ１５０５では、長さＮ２シンボルのベクトル
【数１５９】
2011514743.tif 000165
が、
【数１６０】
2011514743.tif 000166
の非恒等写像
【数１６１】
2011514743.tif 000167
を
【数１６２】
2011514743.tif 000168
に加えることによって得られる。最後に、ステップ１５０６において、コンポジットコードＣ符号語が、
【数１６３】
2011514743.tif 000169
を共に連結することによって生成され、この場合、コンポジットコードＣ符号語は、長さＮ＝Ｎ１＋Ｎ２を有し、Ｋ＝Ｋ１＋Ｋ２個の情報シンボルを含む。
【００３７】
図１５Ｂは、本発明の１実施形態を表すコンポジットコードＣ［７２、６６、５］の構成を示す。上述したように、コンポジットコードは２つのコンポーネントコードに依存する。コンポーネントコードを、リードソロモン符号、ＧＦ（ｑ）上に定義された系統的線形ブロックコード、２値の系統的線形ブロックコード、または他のタイプのコードとすることができる。開示した実施形態では、第１のコンポーネントコードＣ１は、Ｎ１＝３６、Ｋ１＝３４、Ｄ１＝３の符号語を生成し、第２のコンポーネントＣ２は、Ｎ２＝３６、Ｋ２＝３２、Ｄ２＝５という特性を有する。Ｃ１はｓ１個のシンボル消失及びｔ１個のシンボルエラーを検出して訂正できること、及び、Ｃ２は、ｓ２個のシンボル消失及びｔ２個のシンボルエラーを検出して訂正できることが想定されており、ここで、ｓ１＋２ｔ１＜Ｄ１、ｓ２＋２ｔ２＜Ｄ２である。実際に、このようなコードは周知である。
【００３８】
図１５Ｂに示すように、Ｃ１はＫ１＝３４の情報シンボル１５１２を符号化して３６−シンボルＣ１符号語
【数１６４】
2011514743.tif 000170
を生成し、Ｃ２はＫ２＝３２情報シンボル１５１４を符号化して３６−シンボルＣ２符号語
【数１６５】
2011514743.tif 000171
を生成する。これらの符号語を組み合わせて、本発明の１実施形態を表すコンポジットコードＣ［７２、６６、５］の符号語を生成する。こうして、Ｋ１＋Ｋ２＝３２＋３４＝６６個の情報シンボルが、本発明の１実施形態を表すコンポジットコードの７２−シンボル符号語の各々に符号化される。Ｃ１符号語
【数１６６】
2011514743.tif 000172
とＣ２符号語
【数１６７】
2011514743.tif 000173
はいずれもＮ＝３６のシンボルを有する。関数ｆ（・）は、
【数１６８】
2011514743.tif 000174
内の各シンボルに連続的に適用されて、ベクトル
【数１６９】
2011514743.tif 000175
が生成される。ベクトル
【数１７０】
2011514743.tif 000176
は、次に、Ｃ２符号語
【数１７１】
2011514743.tif 000177
に加えられて、ベクトル
【数１７２】
2011514743.tif 000178
が生成される。次に、符号語
【数１７３】
2011514743.tif 000179
が、
【数１７４】
2011514743.tif 000180
と連結されて、本発明の１実施形態を表すコンポジットコードのＮ＝７２符号語１５２６が生成される。この符号語のシンボルが伝送されて格納されると、
【数１７５】
2011514743.tif 000181
からのシンボルが、一連の伝送されたシンボル１５２８で示されるように、該伝送されたシンボルにおいて交互に並び、この場合、シンボル
【数１７６】
2011514743.tif 000182
が最初に伝送され、シンボル
【数１７７】
2011514743.tif 000183
が最後に伝送される。
【００３９】
図１６は、情報シンボルの入力ストリームに対して繰り返し実行することができるコンポジットコード符号語を符号化して、コンポジットコード符号語の出力ストリームを生成する方法を示す。ステップ１６０２において、Ｋ１＋Ｋ２個の情報シンボルが符号化のために受信される。ステップ１６０４において、最初のＫ１個の情報シンボルがＣ１エンコーダによって符号化されてＣ１符号語
【数１７８】
2011514743.tif 000184
が生成される。ステップ１６０６において、次のＫ２個の情報シンボルがＣ２エンコーダによって符号化されてＣ２符号語
【数１７９】
2011514743.tif 000185
が生成される。ステップ１６０８において、ベクトル
【数１８０】
2011514743.tif 000186
が、シンボル対シンボル写像関数ｆ（・）を用いて、
【数１８１】
2011514743.tif 000187
から生成される。最後に、ステップ１６１０において、
【数１８２】
2011514743.tif 000188
を共に連結して、コンポジットコード符号語を生成する。図１６に示す方法によるコンポジットコード符号語の符号化を、情報シンボルの入力ストリームに対して繰り返し実行して、コンポジットコード符号語の出力ストリームを生成することができる。
【００４０】
ベクトル
【数１８３】
2011514743.tif 000189
を計算する上記方法は、非系統的コードＣを生成する。系統的コードＣはプリコーディング（precoding）によって得ることができる。プリコーディングは、
【数１８４】
2011514743.tif 000190
から長さＫ２のプレフィックス
【数１８５】
2011514743.tif 000191
を抜き取り、入力ストリームから次のＫ２個の情報シンボルを構成するベクトル
【数１８６】
2011514743.tif 000192
を生成することによって実行される。次に、語（ワード）
【数１８７】
2011514743.tif 000193
が、
【数１８８】
2011514743.tif 000194
として生成される。最後に、
【数１８９】
2011514743.tif 000195
が、Ｃ２符号語
【数１９０】
2011514743.tif 000196
に符号化されるＫ２個の情報シンボルとして使用され、次に、
【数１９１】
2011514743.tif 000197
を用いて、ベクトル
【数１９２】
2011514743.tif 000198
を
【数１９３】
2011514743.tif 000199
によって計算する。
【００４１】
本発明の代替的な実施形態では、コンポジットコード符号語を他の方法によって生成することができる。コンポーネントコードを使用する符号化の順序が異なる場合があり、コンポーネントコードが異なる場合があり、異なるシンボル対シンボル写像関数が使用される場合がある。本発明の実施形態を表すコンポジットコードのファミリー内の代替的なコンポジットコードは、コンポーネントコードＣ１及びＣ２の根底をなすコード特性に依存して、異なる特性Ｎ、Ｋ、及びＤを有する場合がある。本発明の代替的な実施形態では、それぞれのコンポーネントコードそれ自体を、２つ以上の背後にあるコンポーネントコードから生成することができる。
【００４２】
図１７Ａは、本発明の１実施形態を表すコンポジットコードの符号語内のサブブロックの概念を示す。図１７に示すように、コンポジットコード符号語１７０２を、代替的に８ビットシンボルベクトル１７０６に拡張されて示されているシンボル１７０４などの８ビットシンボルを含むものとみなすことができる。シンボルの対１７０８−１７０９などのシンボルの対の各々は合わせてサブブロック１７１０とみなすことができる。したがって、コンポジットコード符号語を、代替的には、順序付けられたビットのシーケンス、８ビットシンボルの順序付けられたシーケンス、または、順序付けられたサブブロックのシーケンスとみなすことができる。
【００４３】
図１７Ｂは、種々の異なるエラーのタイプを示しており、本発明の１実施形態を表すコンポジットコードはこれらのエラーを検出して訂正するように設計されている。コンポジットコードの重要な追加のパラメータは、Ｄ／２よりも小さな最大の整数であるパラメータＬである。種々のタイプの代替のコンポジットコードについて、値Ｌを、１＜Ｌ＜Ｄ／２の範囲の整数に固定することができる。第１のタイプのエラーは、「フェーズドバースト(phased-burst)」エラーと呼ばれる。フェーズドバーストエラーは図１７Ｂに示す第１のワード（語）１７１２において示されている。フェーズドバーストエラーは、Ｌ個のサブブロックから構成される隣接するシンボルからなるブロック内の任意の数の破損したシンボルである。図１７Ｂのワード１７１２に示されているように、クロスハッチングされた４つのシンボル１７１４−１７１７が破損しており、４つの全てのシンボルが、サブブロック４及び５から構成されるブロック内にある。フェーズドバーストエラーを含む符号語は、どのサブブロック消失も含んでいないということが想定されている。フェーズドバーストエラーの場合に、１つのブロック内の４つの全てのシンボルが破損しているときは、コンポジットコードがエラーを訂正することができない確率は小さいが存在する。しかしながら、この小さな確率は、等価な冗長性を有するリードソロモン符号がそのエラーを訂正できない可能性よりも小さく、本発明のコンポジットコードは、等価な冗長性を有するリードソロモン符号よりも時間的効率がよい。ブロック内の破損したシンボルが４つより少ないときには、破損した全てのシンボルを訂正することができる。
【００４４】
ｔＳエラータイプが、図１７Ｂの２番目の符号語１７３０に示されている。ｔＳエラータイプは、（Ｌ−ｔ）個までのサブブロック消失及びｔ個の破損シンボルを含む。図１７Ｂに示す例では、１つのサブブロック消失１７２２と他に１つの破損シンボル１７２４が存在するので、ｔ＝１であり、Ｌ−ｔ＝１の消失したサブブロックがある。代替的には、消失したサブブロックが２つで、破損シンボルはない場合、または、破損したシンボルが２つで、消失したサブブロックがない場合がある。本発明のコンポジットコードが向けられている第３のタイプのエラー状態は、Ｌ個までのサブブロックが消失しており、さらに１つの１ビットエラーが発生している１Ｒエラーである。図１７Ｂにおける第３の符号語１７３６は、２つのサブブロック１７３８−１７３９が消失して、シンボル１７４２において単一ビットエラー１７４０が発生している１Ｒエラーを示す。
【００４５】
本発明の実施形態を表すコンポジットコードの開発の１つの動機は、新しく開発されたタイプの電子メモリ（電子記憶装置）のエラー訂正をすることである。このメモリの構成のために、予測されるエラーの大部分は、フェーズドバーストエラー、ｔＳタイプのエラー、及び、１Ｒタイプのエラーを含む。エラー訂正は、これらの電子メモリシステムではハードウエアで実行され、したがって、エラー訂正コンポーネントは、多大な設計及び製造のオーバーヘッドを伴う。このため、設計者及び製造者は、これらの予測されるフェーズドバースト、ｔＳ、及び１Ｒエラーを検出して訂正するための可能なかぎり効率のよいコード（符号）を使用することを望んでいる。本発明の実施形態を表すコンポジットコードは、同じ数の情報シンボルに対して従来のリードソロモン符号によって必要とされるであろう数よりも少ないパリティチェックシンボルを用いてこれらの予測されるエラータイプを首尾よく検出して訂正する。
【００４６】
図１８は、本発明の１実施形態を表すコンポジットコードの復号化の高レベル制御フロー図を示す。ステップ１８０２において、Ｋ個の情報シンボルを含む長さＮのコンポジットコードＣ符号語が受信される。ステップ１８０４−１８０６において、Ｋ１個の情報シンボルを含む長さＮ１のコンポーネントコードＣ１符号語
【数１９４】
2011514743.tif 000200
と、符号化中に、Ｋ２個の情報シンボルを含むコンポーネントコードＣ２符号語
【数１９５】
2011514743.tif 000201
及び非恒等写像関数ｆ（・）から生成された、長さＮ２の修正されたコンポーネントコードＣ２符号語
【数１９６】
2011514743.tif 000202
とがコンポジットコードＣ符号語から抽出され、予測されたコンポーネントコードＣ２符号語
【数１９７】
2011514743.tif 000203
及び予測されたエラーワード
【数１９８】
2011514743.tif 000204
が、修正されたコンポーネントコードＣ２符号語にＣ２デコーダを適用することによって、該修正されたコンポーネントコードＣ２符号語から生成される。ここで、Ｋ＝Ｋ１＋Ｋ２及びＮ＝Ｎ１＋Ｎ２である。ステップ１８０８において、複数のタイプの予測されるエラーのどれがコンポジットコードＣ符号語の符号化の後で発生したかがエラーワード
【数１９９】
2011514743.tif 000205
から決定される。ステップ１８１６において、消失の第１閾値数より多い消失が発生したが、エラーの第２閾値数より少ないエラーが発生したと判定されたときは、該判定されたエラーは、コンポーネントコードＣ１符号語と修正されたコンポーネントコードＣ２符号語のいずれかに割り当てられ、コンポーネントコードＣ１符号語に割り当てられたときには、ステップ１８１８及び１８２０において訂正される。他のエラー及び消失の発生がステップ１８１０、１８１２及び１８１４に記載されている。ステップ１８２２において、予測されたコンポーネントコードＣ２符号語
【数２００】
2011514743.tif 000206
が、予測されたコンポーネントコードＣ１符号語
【数２０１】
2011514743.tif 000207
にＣ１デコーダを適用することによって得られる。最後に、ステップ１８２４において、Ｋ１個の情報シンボルが、予測されたコンポーネントコードＣ２符号語
【数２０２】
2011514743.tif 000208
から抽出され、Ｋ２個の情報シンボルが、予測されたコンポーネントコードＣ２符号語
【数２０３】
2011514743.tif 000209
から抽出されて、Ｋ個の抽出された情報シンボルが生成される。
【００４７】
次に、受信したコンポジットコード符号語の復号化について説明する。図１９−２０は、本発明の実施形態を表すコンポジットコードに対する復号化処理の１実施形態を示す制御フロー図である。先ず、ステップ１９０２において、コンポジットコードＣ符号語が受信される。受信されたワード（語）を次の２つの部分と見ることができる。
【数２０４】
2011514743.tif 000210
ここで、
【数２０５】
2011514743.tif 000211
は、受信した
【数２０６】
2011514743.tif 000212
であり、
【数２０７】
2011514743.tif 000213
は、受信した
【数２０８】
2011514743.tif 000214
である。次に、ステップ１９０３において、符号化時の
【数２０９】
2011514743.tif 000215
への
【数２１０】
2011514743.tif 000216
の加算が次のように逆にされる。
【数２１１】
2011514743.tif 000217
次に、ステップ１９０４において、計算されたワード
【数２１２】
2011514743.tif 000218
が、Ｃ２デコーダを用いて復号化されて、予測された符号語
【数２１３】
2011514743.tif 000219
及び予測されたエラーワード
【数２１４】
2011514743.tif 000220
が生成される。すなわち、
【数２１５】
2011514743.tif 000221
であり、関数様のシンボル
【数２１６】
2011514743.tif 000222
は、デコーダによるコンポーネントコードＣ２の復号化を表す。
【００４８】
ステップ１９０５において、
【数２１７】
2011514743.tif 000223
のＣ２復号化が失敗したと判断されたときには、コンポジットコード符号語の復号化は失敗である。次に、一連の条件ステップにおいて、フェーズドバースト（「ＰＢ」）、ｔＳ、及び１Ｒエラーを表すブールフラグをセットして、これらのタイプのエラーが受信ワード内で発生したか否かが示される。「_１Ｒ」という表記は、後述する擬似コードと整合させられる１Ｒフラグについて使用されるということに留意されたい。消失したサブブロックの存在は、一般に、受信ワードの一部ではない別個の帯域外消失（out-of-band erasure）指標によって示されるということに留意すべきである。ステップ１９０６において、及び、図１７Ｂを参照して上述したように、消失が発生しなかったとき、及び、全てのシンボルエラーが、１つのブロック範囲内のＬ個の隣接するサブブロック内で発生したと判断されたときは、ステップ１９０８においてフラグＰＢがＴＲＵＥ（真）に設定される。そうでなければ、ステップ１９１０においてフラグＰＢがＦＡＬＳＥ（偽）に設定される。ステップ１９１２において、フラグＰＢが値ＦＡＬＳＥを含み、かつ、消失したサブブロックの数と予測されたエラーベクトル
【数２１８】
2011514743.tif 000224
内の任意の追加の非ゼロシンボルの数の合計がＬ以下であると判定されたときには、ステップ１９１４においてフラグｔＳがＴＲＵＥに設定される。そうでなければ、ステップ１９１６においてフラグｔＳがＦＡＬＳＥに設定される。ステップ１９１８において、ＰＢとｔＳの両方がブール値ＦＡＬＳＥを含み、かつ、消滅したサブブロックの数がＬ以下で、最大でも１つの追加の１ビットシンボルエラーだけがエラーベクトル
【数２１９】
2011514743.tif 000225
で見つかったと判定されたときは、ステップ１９１９においてフラグ_１ＲがＴＲＵＥに設定さる。そうでなければ、ステップ１９２０においてフラグ_１ＲがＦＡＬＳＥに設定される。１ビットエラーは、予測されたエラーベクトル
【数２２０】
2011514743.tif 000226
内の非ゼロシンボルｓが集合Ｍの要素であるか、または、−ｓが、シンボル対シンボル関数ｆ−１（）によって集合Ｍに写像されるときに検出され、代替的に、
【数２２１】
2011514743.tif 000227
と表される。したがって、ｆ（・）は、
【数２２２】
2011514743.tif 000228
で発生する単一ビットエラーをビット値「１」を持つ３つ以上のビットを有するシンボルに写像（マッピング）し、これによって、
【数２２３】
2011514743.tif 000229
内の単一ビットエラーを
【数２２４】
2011514743.tif 000230
内の単一ビットエラーから区別することができる。符号化は、図２０の制御フロー図で再開する。ステップ２００２において、３つのブールフラグＰＢ、ｔＳ、_１ＲがいずれもＴＲＵＥに設定されていないと判定された場合は、デコーダは、ステップ２００４でＦＡＬＳＥ値を返す。そうでない場合には、ステップ２００６で、ベクトル
【数２２５】
2011514743.tif 000231
が、受信したＣ符号語
【数２２６】
2011514743.tif 000232
の前半部にセットされる。ステップ２００８において、フラグ_１ＲがＴＲＵＥに設定されていると判定され、ステップ２０１０において、予測されたエラーベクトル
【数２２７】
2011514743.tif 000233
内の位置γで、単一の非ゼロシンボルｓγが見つかり、かつ、ｓγが集合Ｍの要素ではないと判定された場合には、ステップ２０１２において、
【数２２８】
2011514743.tif 000234
内の同じ位置γにおけるシンボルが元のシンボルで置き換えられ、ＧＦ（２８）減算によって、該元のシンボルから逆写像された負のエラーシンボルが減算される。ステップ２００８、２０１０、及び２０１２によって、Ｌ個のサブブロック消失に加えて単一ビットエラーの検出が可能である。非ゼロ
【数２２９】
2011514743.tif 000235
シンボルｓγがＭの要素であるときには、単一ビットエラーが、受信ワード、すなわち、
【数２３０】
2011514743.tif 000236
の後半部で発生した。しかしながら、Ｆ−１（−ｓγ）によってｓγをＭに写像できるときには、該単一ビットエラーは、Ｃ符号語の最初の部分で発生した。この場合は、ステップ２０１２でそのエラーが訂正される。次に、ステップ２０１４において、ブールフラグＰＢが値ＴＲＵＥを含んでいると判定され、ステップ２０１６において、
【数２３１】
2011514743.tif 000237
内に非ゼロシンボルが存在すると判定された場合には、ステップ２０１８において、エラーを含んでいるブロック内のシンボルが消失したものとして記録（マーク）される。ステップ２０２０において、フラグｔＳがブール値ＴＲＵＥを含んでいると判定され、ステップ２０２２において、任意の検出された消失の他に、
【数２３２】
2011514743.tif 000238
内に任意の非ゼロシンボルが存在すると判定された場合には、ステップ２０２４において、それらの追加のシンボルエラーが消失したものとして記録（マーク）される。ステップ２０２６において、Ｃ１デコーダを
【数２３３】
2011514743.tif 000239
に適用して、予測された元のベクトル
【数２３４】
2011514743.tif 000240
を生成する。ステップ２０２７において、Ｃ１デコーダが失敗したと判定された場合には、コンポジットコードの復号化は失敗である。そうでない場合には、ステップ２０２８において、Ｋ１個のシンボルが、
【数２３５】
2011514743.tif 000241
から抽出され、Ｋ２個のシンボルが、
【数２３６】
2011514743.tif 000242
から抽出され、これらは合わさって、ステップ２０３０において返されるＫ個の復号化された一連の情報シンボルを形成する。ステップ１９０４の場合と同様に、ステップ２０２６においてＣ１デコーダが失敗した場合には、復号化は失敗である。
【００４９】
次に、本発明の１実施形態を表す上述のコンポジットコードを復号化（デコード）するための復号化方法をＣ＋＋ライクな疑似コードで実施することについて説明する。図２１は、本発明の１実施形態を表すコンポジットコードの復号化方法の各ステップで受信される情報を示す。受信された情報は、符号語内の各シンボルについて単一ビットが該シンボルが消失したか否かを示すところの消失マップ２１０２を含む。受信された情報は、受信されたワード（語）の各シンボルについて、該シンボルが消失しているか否かを示すビットフラグを有する消失マップ２１０２と、上述したように、
【数２３７】
2011514743.tif 000243
に等しい第１の部分２１０６
【数２３８】
2011514743.tif 000244
及び、
【数２３９】
2011514743.tif 000245
に等しい第２の部分２１０８
【数２４０】
2011514743.tif 000246
を有する受信ワード２１０４とを含む。
【００５０】
疑似コードによる実施は、先ず、以下のいくつかの整数定数宣言を含む。
【数２４１】
2011514743.tif 000247
これらの定数は、上述したコンポジットコードＣ及びコンポーネントコードＣ１及びＣ２に関する基本パラメータ、すなわち、以下（１）−（８）のパラメータを含む。（１）Ｃ１Ｋ、Ｃ２Ｋ、及び、ＣＫ、すなわち、Ｃ１、Ｃ２、及びＣのそれぞれの符号語内の情報シンボルの数、（２）Ｃ１Ｒ、Ｃ２Ｒ、及びＣＲ、すなわち、Ｃ１、Ｃ２、及びＣのそれぞれの符号語内のパリティチェックシンボルの数、（３）Ｃ１、Ｃ２、及びＣのそれぞれの符号語に関する符号語Ｃ１Ｄ、Ｃ２Ｄ、及びＣＤ間の最小距離、（４）コンポジットコードＣの符号語内のシンボルの数である定数Ｎ、（５）上述したように、開示した実施において（ＣＤ−１）／２より小さい最大の整数に等しい数Ｌ、（６）コンポーネントコードＣ１及びＣ２の符号語内のシンボルの数Ｎ２（ここで、Ｎ２＝Ｎ／２であり、symPSubBlkはサブブロック当たりのシンボルの数）、（７）コンポジット符号語の第１の部分（または最初の部分）のブロックのサブブロックインデックスに付加されたときに、コンポジット符号語の第２部分の対応するサブブロックのサブブロックインデックスを生成するblkPlus、（８）シンボル内のビットの数である定数ｂ、または、等価的に、コンポジットコードＣが構成される体の表現ＧＦ（２ｍ）内のｍに等しい数。
【００５１】
次に、（１）符号語シンボル、（２）Ｃ、Ｃ１、及びＣ２符号語、（３）Ｃ、Ｃ１、及びＣ２符号語に対する消失マップに関する型定義が次のように提供される。
【数２４２】
2011514743.tif 000248
Ｃ＋＋型「unsigned char」は、定数ｂが８以下のときにシンボルを表すためだけに使用されることができることに留意すべきである。ｂ＝８のときは、unsigned-charデータ型は、「バイト」とも呼ばれ、２値係数のタプルとして表現される各シンボルを表すために必要なサイズそのものであり、したがって、ＧＦ（２８）は、計算効率上、最も都合のよい体であり、この体上に符号（コード）が構成される。
【００５２】
次に、ビット値が「１」の単一ビットだけを含む８ビットタプル表現を有する全てのシンボルを含む集合Ｍについてある宣言が提供される。この宣言は、集合Ｍ内のタプルが、次のように、通常の２進バイト値表現におけるバイト、すなわち、２の累乗に対応するという事実を利用している。
【数２４３】
2011514743.tif 000249
【００５３】
次に、５つの関数に関する宣言が以下のように提供される。
【数２４４】
2011514743.tif 000250
最初の２つの関数はコンポーネントコードＣ１及びＣ２用のデコーダである。これらの２つの関数は、上述したように、符号語及び消失マップを受け取って、復号化された符号語及びエラーワードを返す。上述の関数ｆ（・）及び関数ｆ−１（・）は、上記のコードブロックの行５及び６で宣言されている。最後に、行７で、ＧＦ（２８）シンボルｙからＧＦ（２８）シンボルｚを減算するためのＧＦ（２８）減算関数が提供されている。上述したように、コンポーネントコードＣ１及びＣ２が存在し、エンコーダとデコーダがこれらコンポーネントコードに対して利用可能であることが想定されている。デコーダの実施は、コンポジットコードを構成する際に使用するために選択された特定のコンポーネントコードに依存するので、上記５つの関数に対する実施例は提供していない。これは、関数ｆ（・）及びｆ−１（・）は実施するのが容易であり（これらの実施はコンポジットコードが定義される体に依存する）、かつ、ＧＦ（２ｂ）減算が周知だからである。
【００５４】
次に、いくつかのクラス宣言が提供される。先ず、次にように、入力シンボルストリーム、入力消失ストリーム、及び出力シンボルストリームを表す３つのクラスが提供される。
【数２４５】
2011514743.tif 000251
指定された数のシンボルを入力しまたは出力するために、種々のストリームを開始し、その後、それらのストリームにアクセスすることができる。これらのクラスに対する実施例は提供していない。なぜなら、ストリームの入力及び出力はいずれも周知であって、オペレーティングシステムに依存し、及び、おそらくはハードウェアプラットホームに依存するからである。
【００５５】
次に、次のようにクラス「Ｃ_デコーダ（C_decoder）」に対するクラス宣言が提供される。
【数２４６】
2011514743.tif 000252
クラス「Ｃ_デコーダ」は、シンボルストリームクラス、消失ストリームクラス、及び出力ストリームクラスの実例をそれぞれ表す３つのプライベートデータメンバーｓ、Ｅｒ、及びoutを含む。クラス「Ｃ_デコーダ」は、行８−１０で宣言されている２つのプライベート関数メンバーを含む。第１のプライベート関数メンバーである「deInterleave」は、インターリーブされているシンボルをデインターリーブする（インターリーブを解く）ことによって、図１５（特に図１５の１５１８）に関して説明したように、入力ストリームから受け取ったｎ個のシンボルをＣ符号語に変換する。プライベート関数メンバー「decodeNextBlock」は、Ｃ符号語及び対応する消失マップを受け取って、Ｋ個の復号化された情報シンボルを出力ストリームへと出力する。行１３で宣言されている単一のパブリック関数メンバー「decode」は、入力ストリームからのシンボルを連続的に復号化して、対応する復号化された情報シンボルを出力ストリームへと出力する。
【００５６】
関数メンバー「decode」の実施例を以下に示す。
【数２４７】
2011514743.tif 000253
【００５７】
行１０−１５のwhileループにおいて、関数メンバー「decode」は、入力ストリームｃ及びＥｒから次の符号語と対応する消失マップを取り出し、行１２で入力シンボルをデインターリーブし、行１３で符号語を復号化し、行１４で対応する復号化された情報シンボルを出力する。このループは、行１３において復号化が失敗するか、または、行１０において情報ストリームから利用可能な他の符号化されたシンボルがないと判定されるまで継続する。
【００５８】
次に、関数メンバー「decodeNextBlock」の実施例を、次の数２４８−１〜数２４８−３に示す。
【数２４８−１】
2011514743.tif 000254
【数２４８−２】
2011514743.tif 000255
【数２４８−３】
2011514743.tif 000256
【００５９】
関数メンバー「decodeNextBlock」は、コンポジットコード符号語ｃ、対応する消失マップｅｒ、及び、受信したワードｃに対応する復号化された情報シンボルを配置するためのシンボルバッファを受け取る。行４−５において、受信したワード（受信ワード）ｃの前半部と後半部を指し示すためにシンボルポインタur及びwrが宣言される。これらのシンボルポインur及びwrは、図２１の
【数２４９】
2011514743.tif 000257
に対応する。同様に、行７−８において、受信したワードＣの前半部と後半部にそれぞれ対応する受信した消失ワードerの各部を指し示すために、消失マップポインタer1及びer2が宣言される。
【００６０】
行１０−２１で、いくつかの局所変数が宣言される。これらの局所変数は、コンポジットコード、コンポーネントコード、コンポジットコード符号化、及びコンポジットコード復号化についての上記説明で使用した表記に対応する名称を有する。たとえば、行１１で宣言されている変数vHatは、上述の予測された復号化された符号語
【数２５０】
2011514743.tif 000258
を表す。行１８及び２０でそれぞれ宣言されている配列「erasures」及び「nonZeroSymbols」は、それぞれ、消失マップ及び予測されたエラーベクトルe2Hatにおいて検出された消失したサブブロックのインデックス（指標）及び他のエラーのインデックス（指標）を含む。局所変数の用法は、関数メンバー「decodeNextBlock」における後述するそれらの使用によって明らかにされている。
【００６１】
行２３−２４において、ベクトルvrがvr＝wr−ｆ(ur)として計算される。行２６で、vrが復号化されて、それぞれ、コードにおいてvHat、e2Hatと呼ばれる
【数２５１】
2011514743.tif 000259
が生成される。行２８−３７のforループでは、全ての消失したサブブロックのインデックス（指標）が決定されて配列「erasures」に格納される。疑似コードに実装されたコンポジットコードによって検出して訂正できるのは最大でもＬ個の消失だけであるので、サブブロック消失の数がＬ個より多い場合には、復号化ルーチンは失敗することに留意されたい。さらに、行２６において呼び出されたＣ２デコーダが失敗した場合にも復号化は失敗することに留意されたい。次に、行３９−５８のforループにおいて、任意の検出された消失したサブブロックとは別に、非ゼロシンボルによって表される
【数２５２】
2011514743.tif 000260
内の任意エラーが指摘（または表示）され、該エラーに対応する非ゼロシンボルのインデックス（指標）が配列「nonZeroSymbols」に格納される。
【００６２】
行６０−６７において、フェーズドバーストエラーが符号語内で検出されたか否かに応じて、ブールフラグＰＢがＴＲＵＥ（新）またはＦＡＬＳＥ（偽）に設定される。消失がなく、並びに、他のエラーシンボルがないか若しくは全てのエラーシンボルがＬ個の隣接するサブブロックからなる単一ブロック内で発生したとき（または、Ｌ個の隣接するサブブロックからなる単一ブロック内で、消失がなく、及び、他のエラーシンボルがないか若しくは全てのエラーシンボルが発生したとき）に、ＰＢはＴＲＵＥに設定される。消失したサブブロックがＬ個より多い場合には関数メンバー「decodeNextBlock」が既に失敗しているであろうことを想起されたい。次に、行６９−７０において、ｔＳタイプのエラーが受信したワード（語）において検出されたか否かに応じて、ブールフラグｔＳがＴＲＵＥまたはＦＡＬＳＥに設定される。ＰＢがＦＡＬＳＥであって、他のエラーシンボルの数と消失したサブブロックの数の和がＬ以下のときに、フラグｔＳはＴＲＵＥに設定される。
【００６３】
次に、行７２−９６において、ブールフラグ_１ＲがＴＲＵＥまたはＦＡＬＳＥに設定される。最大Ｌ個までの消失したサブブロックに加えて、単一の追加の１ビットエラーが存在するとき、または、追加のエラーが存在しないときにブールフラグ_１ＲはＴＲＵＥに設定される。行３４において、Ｌ個より多くの消失したサブブロックが検出されたときには、復号化は既に失敗していることに留意されたい。行８１において、エラーシンボルが集合Ｍのメンバーであると判定されたか、または、行８８において、エラーシンボルのシンボル値のＧＦ（２ｂ）-加法的逆元ｆ−１（・）による逆写像がＭに写像すると判定されたときには、該エラーシンボルは１ビットエラーを表す。
【００６４】
行９８において、全てのブールフラグがＦＡＬＳＥであると判定された場合は、復号化は失敗である。そうでない場合には、行１００で、uPrimeが、受信したワードｃの前半部（または第１の部分）に設定される。ＰＢがＴＲＵＥのときは、行１０２−１０５において、エラーを含む全てのサブブロックの全てのシンボルが消失（erasures）として記録（マーク）される。行１０７−１０９において、ｔｓがＴＲＵＥのときは、全ての追加のエラーシンボルが消失（erasures）として記録（マーク）される。行８８において、符号語の前半部（または第１の部分）において１ビットの追加のエラーが検出された場合には、行１０９において、uPrimeが変更されて、行１１１において、uPrimeから逆写像された逆シンボル値（inverse symbol value）を減算することにより領域を補正する。最後に、行１１３において、uPrimeがＣ１デコーダによって復号化される。Ｃ１デコーダが失敗した場合には、復号化は失敗する。そうでない場合には、uPrime及びvHat内の情報シンボルは、メンバー関数「decode」に返すためにバッファ内に配置される。
【００６５】
上述したように、本発明の実施形態を表すコンポジットコードを、特定のタイプのエラー及び消失のパターン及び発生を効率的に検出して訂正するように構成することができる。たとえば、最大Ｌ個までの消失したサブブロック（または１つのシンボル内の最大Ｌ個までの消失したサブブロック）、及び、１つのシンボル内のｔ個の追加のランダム単一ビットエラーを検出して訂正することが望まれている場合を想定する。Ｌ＜Ｄ１及びＬ＋２ｔ＜Ｄ２のときで、かつ、ＧＦ（２）上の線形符号Ｃ’が、Ｃ'Ｎが、
【数２５３】
2011514743.tif 000261
に等しい状態で存在し、次元（dimension）Ｋ’＝ｂであり、最小符号語距離が
【数２５４】
2011514743.tif 000262
のときは、上述のコンポジットコードの場合には、該コンポジットコードを用いて、最大Ｌ＝２までの消失したサブブロック、及び、ｔ＝２の追加のランダム単一ビットエラーを検出することができる。ここで、Ｃ'は、パリティチェック行列
【数２５５】
2011514743.tif 000263
によって定義され、
【数２５６】
2011514743.tif 000264
は可逆である。
【数２５７】
2011514743.tif 000265
はＧＦ（２）上のｂ×ｂ行列であることに留意されたい。この場合、上述のコンポジットコードについては、シンボル対シンボル写像関数ｆ（・）は、
【数２５８】
2011514743.tif 000266
と定義される。ここで、
【数２５９】
2011514743.tif 000267
は、ＧＦ（２８）のシンボルである。「Ｌ＜Ｄ１及びＬ＋２ｔ＜Ｄ２」という条件によって、Ｃ２デコーダが、
【数２６０】
2011514743.tif 000268
を成功裏に復号化できることが確保される。線形符号Ｃ’に関連する条件は、ｆ（・）が、１つまたは２つのランダムビットエラーを有するシンボル
【数２６１】
2011514743.tif 000269
を、１または２のランダムビットエラー（one-or-two-random-bit-error）を有する破損シンボルから識別可能な異なるシンボルに首尾良く写像することを確保し、これによって、コンポジットコードデコーダが、１または２のランダムビット破損が発生したのが符号語の２つの部分（前半分と後ろ半分）のうちのどれであるかを決定できるようにする。今の例では、Ｃ２エラーワード
【数２６２】
2011514743.tif 000270
中の非ゼロシンボル
【数２６３】
2011514743.tif 000271
を用いて、Ｃ’に対するシンドローム
【数２６４】
2011514743.tif 000272
を生成することができ、次に、シンドローム
【数２６５】
2011514743.tif 000273
を用いて、
【数２６６】
2011514743.tif 000274
の連結から構成される対応するＣ’エラーワード
【数２６７】
2011514743.tif 000275
を選択することができる。したがって、
【数２６８】
2011514743.tif 000276
中のランダム２ビットエラーを有する破損シンボルを、コンポジットコード符号語の前半部または後半部に帰することができる。
【００６６】
図２２は、本発明の実施形態を利用できる物理メモリ装置のブロック図である。メモリ２２０２は、個々のＤＲＡＭコンポーネントメモリ２２０４−２２０８のバンク、データを送受信するためのバスコントローラ及びロジック２２１０、メモリに格納する前にコンポジットコードをデータ値に適用するためのエンコーダ２２１２、及び、メモリから取り出された符号化された値を復号化するためのデコーダ２２１４を備える。メモリ動作には、アドレス及びサイズ２２１８によって識別されるデータワードのブロック２２１６をワード単位でメモリに格納すること、及び、アドレス及びサイズ２２２２によって識別されるワードのブロック２２２０をワード単位でメモリから取り出すことが含まれる。
【００６７】
図２３は、図２２に示す物理メモリ装置の電子データ記憶要素を共に構成する、符号語シンボルとＤＲＡＭユニットのバンク内のＤＲＡＭユニットとの間の写像を示す。１実施形態では、メモリに格納するための受信された各ワードは、メモリのエンコーダ要素（図２２の２２１２）によってコンポジットコード符号語２３０３に符号化される。尚、該符号語は、ブロック２３０４などのブロックの配列とみなすことができ、各ブロックは、サブブロック２３０６などのいくつかのサブブロックから構成される。図２３において双方向矢印２３０８−２３１３によって示されているように、各ブロックは、対応するＤＲＡＭに写像（マッピング）される。したがって、たとえば、ＤＲＡＭが故障すると、符号語の１ブロックにわたってフェーズドバーストエラーが生じることになる。本発明のコンポジットコードは、メモリの最も可能性の高い故障モードを訂正するように設計されている。たとえば、上述のコンポジットコードは、単一ＤＲＡＭ故障、いくつかのＤＲＡＭにおけるいくつかのサブブロック及びシンボル破損を訂正することができる。コンポジットコードを用いることによって、メモリエラーの確率−この確率は、メモリ要素エラーの確率が低いためにただでさえ非常に低いのであるが−は、任意の最も可能性の高い要素エラーを補正することによって大幅に小さくなる。
【００６８】
本発明を特定の実施形態に関して説明したが、本発明をそれらの実施形態に限定することは意図していない。当業者には本発明の思想の範囲内における変更が明らかであろう。たとえば、上述したように、いくつかのエラーを、コンポーネントコード符号化を受ける対応するシンボルに写像するための適切なシンボル対シンボル写像関数ｆ（・）を見つけることができるということを条件として、任意の数の異なるコンポーネントコードを組み合わせて、コンポジットコードを生成することができる。コンポジットコードに対する符号化及び復号化法を、ソフトウエア、ファームウエア、ハードウエア、または、ソフトウエアとファームウエアとハードウエアのうちの２つ以上の組み合わせで実施することができる。ソフトウエアによる実施は、任意の様々な異なるプログラミング言語、モジュール構造化、制御構造、データ構造を利用することができ、及び、任意の他の多くのプログラミングパラメータによって異なりうる。本発明のコンポジットコードを、エラー及び消失の多くの異なるタイプのパターン及び発生を効率よく検出して訂正するように工夫することができる。本発明の代替的な実施形態では、異なるシンボル対シンボル写像関数を利用して、コンポジットコード符号語内の所定のタイプのエラーの位置を決定することができる。本発明のさらに代替的な実施形態では、写像関数ｆ（・）は、シンボルの対を他のシンボルの対に写像することができ、または、符号語の他の部分を異なる値に写像することができる。
【００６９】
上記では、本発明を十分に理解できるようにするために、説明を目的として特定の用語を使用した。しかしながら、本発明を実施するために特定の細部は必要ではないことが当業者には明らかであろう。本発明の特定の実施形態に関する上記説明は、例示及び説明のために提示されたものである。それらは、本発明を網羅することも本発明を開示した形態そのものに限定することも意図していない。上記の教示に照らして多くの修正及び変形が可能である。それらの実施形態は、本発明の原理及びその実用的応用を最も良く説明し、これによって、当業者が、意図する特定の用途に適するように種々の変更を加えつつ本発明及び種々の実施形態を最良に利用できるようにするために図示し及び説明された。本発明の範囲は、添付の特許請求の範囲及びその等価物によって画定されることが意図されている。
【図１】
2011514743.tif 000307
【図２】
2011514743.tif 000308
【図３Ａ】
2011514743.tif 000309
【図３Ｂ】
2011514743.tif 000310
【図４】
2011514743.tif 000311
【図５】
2011514743.tif 000312
2011514743.tif 000313
【図７Ａ】
2011514743.tif 000314
【図７Ｂ】
2011514743.tif 000315
【図８】
2011514743.tif 000316
【図９】
2011514743.tif 000317
【図１０】
2011514743.tif 000318
【図１１】
2011514743.tif 000319
【図１２】
2011514743.tif 000320
【図１３】
2011514743.tif 000321
【図１４】
2011514743.tif 000322
【図１５Ａ】
2011514743.tif 000323
【図１５Ｂ】
2011514743.tif 000324
【図１６】
2011514743.tif 000325
【図１７Ａ】
2011514743.tif 000326
【図１７Ｂ】
2011514743.tif 000327
【図１８】
2011514743.tif 000328
【図１９】
2011514743.tif 000329
【図２０】
2011514743.tif 000330
【図２１】
2011514743.tif 000331
【図２２】
2011514743.tif 000332
【図２３】
2011514743.tif 000333
【国際調査報告】
2011514743.tif 000334
2011514743.tif 000335