連鎖的暗号化反応の系統的記号化および復号化
【課題】すべての種類のデータをチェイン・リアクションコードを用いてデータを符号化し復号する。
【解決手段】データをチェイン・リアクションコードとして符号化する方法は、入力データから入力記号の集合を生成する段階を含む。その後、各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される1つまたは複数の非システマティック出力記号が、入力記号の集合から生成される。この符号化プロセスの結果として、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれていない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の集合の任意の部分集合を回復することができる。
【解決手段】データをチェイン・リアクションコードとして符号化する方法は、入力データから入力記号の集合を生成する段階を含む。その後、各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される1つまたは複数の非システマティック出力記号が、入力記号の集合から生成される。この符号化プロセスの結果として、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれていない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の集合の任意の部分集合を回復することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2002年10月5日に出願され、参照としてすべての目的について本明細書に全体的に組み入れられる“Systematic Encoding and Decoding of Chain Reaction Codes”という名称の米国特許仮出願第60/319,597号の利益を主張する。
【０００２】
本発明は、すべての種類のデータを符号化し復号するシステムおよび方法に関し、特に、チェイン・リアクションコードを用いてデータを符号化し復号するシステムおよび方法に関する。
【背景技術】
【０００３】
通信チャネル上での送信側と受信側との間のデータの伝送は多数の文献の主題となっている。常にそうであるとは限らないが、受信側は送信側によってチャネル上で送信されたデータの正確なコピーをある程度確実に受信することを望むことが好ましい。チャネルが（物理的に実現可能なほとんどすべてのシステムをカバーする）完全な忠実度を有さない場合、送信時に紛失するかまたは歪曲されたデータをどのように対処するかという問題がある。受信側は、破壊されたデータが誤って受信されたデータであることが常に分かるわけではないので、失われたデータ（消失）に対処するのは破壊されたデータ（誤り）に対処するよりも容易であることが多い。消失および／または誤りを訂正するために多くの誤り訂正符号が開発されている。通常、使用される特定の符号は、データが送信されているチャネルのIDおよび送信されているデータの性質に関するある情報に基づいて選択される。たとえば、チャネルが長い非忠実度期間を有することが分かっている場合、その用途にはバースト誤り符号が最適である。短くまれな誤りのみが予想される場合、簡単なパリティ符号が最適である。
【０００４】
符号を選択する際の他の問題は、伝送に使用されるプロトコルである。インタネットの場合、データ転送にパケット・プロトコルが使用される。このプロトコルはインタネット・プロトコルまたは略して「IP」と呼ばれる。データのファイルまたはその他のブロックは、IPネットワーク上で送信される際、等しいサイズの入力記号に区分され、入力された記号は連続したパケットに入れられる。入力記号の「サイズ」は、入力記号が実際にビット・ストリームに分解されるかどうかにかかわらずビット単位で測定され、入力記号は、2M個の記号のアルファベットから選択される際にはMビットのサイズを有する。このようなパケットによる通信システムでは、パケット対応符号化方式が適している。
【０００５】
伝送は、予定された受信側がネットワークにおいて消失が起こった場合でも元のファイルの正確なコピーを回復するのを可能にする場合に信頼できる送信と呼ばれる。インタネット上では、散発的な輻輳によってルータのバッファリング機構がその能力の限界に達し、着信パケットを捨てざるを得なくなるために、パケット・ロスが起こることが多い。転送時の消失に対する保護は多くの研究の主題となっている。
【０００６】
Transport Control Packet（「TCP」）は、肯定応答機構を有する一般に使用されているポイント・ツー・ポイント・パケット制御方式である。TCPを用いた場合、送信側は指示されたパケットを送信し、受信側は各パケットの受信に対して肯定応答する。パケットが紛失した場合、送信側に肯定応答が送信されず、送信側はパケットを送信し直す。TCPなどのプロトコルでは、肯定応答パラダイムは、致命的な障害を起こさずにパケットを消失させる。というのは、肯定応答がないことに応答するか、または受信側からの明示的な要求に応答して紛失したパケットを再送することができるからである。
【０００７】
肯定応答によるプロトコルは一般に、多数の用途に適しており、実際、現在のインタネット上で広く使用されているが、非効率的であり、場合によっては、Luby Iに記載されているようなある種の用途ではまったく実現不能である。
【０００８】
この伝送上の問題を解決するために提案されている1つの解決策は、肯定応答によるプロトコルの使用を避け、その代わりに、リード・ソロモン符号、トルネード符号、チェイン・リアクションコードなどの順方向誤り訂正（Forward Error-Correction（FEC））符号を用いて信頼性を高めることである。基本的な考えは、コンテントを構成する入力記号のみの代わりにコンテントから生成された出力記号を送信することである。リード・ソロモン符号やトルネード符号のような従来の消失訂正符号は、一定の長さのコンテントについて一定数の出力記号を生成する。たとえば、K個の入力記号について、N個の出力記号を生成することができる。このN個の出力記号は、K個の元の入力記号およびN-K個の冗長記号を含んでよい。記憶装置に支障がなければ、サーバは、各コンテントの出力記号の集合を一度だけ算出し、カルーセル・プロトコルを用いて出力記号を送信することができる。
【０００９】
ある種のFEC符号に伴う1つの問題は、これらの符号では過度の計算力またはメモリを使用する必要があることである。他の問題は、符号化プロセスの前に出力記号の数を決定しなければならないことである。このため、パケットの紛失率の推定値が高すぎる場合には非効率な結果をもたらす可能性があり、パケットの紛失率の推定値が低すぎた場合には障害が発生する恐れがある。
【００１０】
従来のFEC符号では、生成できる可能な出力記号の数は、コンテントが区分される入力記号の数と同程度である。常にそうであるとは限らないが、通常、これらの出力記号のほとんどまたはすべては、送信段階の前の前処理段階で生成される。これらの出力記号は、長さが元のコンテントに等しいかまたは元のコンテントよりもわずかに長い出力記号の任意の部分集合からすべての入力記号を再生できるという特性を有する。
【００１１】
“Information Additive Code Generator and Decoder for Communication Systems”という名称の米国特許第6,307,487号（以下では“Luby I”と呼ぶ）および“Multi-Stage Code Generator and Decoder for Communications Systems”という名称の米国特許出願第10/032,156号（以下では“Raptor”と呼ぶ）に記載された「チェイン・リアクションコード化」は、上記の問題に対処する異なる形態の転送誤り制御に相当する。チェイン・リアクションコードでは、生成できる一群の可能な出力記号は、入力記号の数よりも一桁多く、必要に応じ送信段階と並行して一群の可能な出力記号からランダム出力記号を高速に生成することができる。チェイン・リアクションコードは、長さが元のコンテントよりもわずかに長いランダムに生成された出力記号の集合の任意の部分集合からコンテントのすべての入力記号を再生できるという特性を有する。
【００１２】
様々なチェイン・リアクションコードの他の説明は、2000年9月22日に出願され、“On Demand Encoding With a Window”と題する米国特許出願第09/668,452号や、2000年10月18日に出願され“Generating High Weight Output symbols Using a Basis”という名称の米国特許出願第09/691,735号に記載されている。
【００１３】
チェイン・リアクションコード化システムのいくつかの態様は、エンコーダおよびデコーダから成る。データは、ブロックまたはストリームの形でエンコーダに与えることができ、エンコーダは、ブロックまたはストリームから出力記号を高速に生成することができる。いくつかの態様、たとえば、Raptorに記載されている態様では、静的エンコーダを用いてオフラインでデータを前符号化することができ、複数の元のデータ記号および静的出力記号から出力記号を生成することができる。
【００１４】
チェイン・リアクションコード化システムのいくつかの態様では、符号化および復号プロセスは重みテーブルに依存する。重みテーブルは、ソース記号の集合に関する確率分布を表している。すなわち、1からソース記号の数までの間の任意の数Wについて、重みテーブルは固有の確率P(W)を示す。P(W)は、Wの実質的に多数の値について0である可能性があり、その場合、P(W)が0でない重みWのみを含むことが望ましい。
【００１５】
チェイン・リアクションコード化システムのいくつかの態様では、出力記号は以下のように生成される。すなわち、あらゆる出力記号について、鍵がランダムに生成される。この鍵に基づいて、重みテーブルから重みWが算出される。次いで、W個のソース記号のランダムな部分集合が選択される。この場合、出力記号は、これらのソース記号のXORである。これらのソース記号を以下では出力記号の近傍またはアソシエートと呼ぶ。この基本方式の様々な修正態様および拡張態様が可能であり、それらは上述の特許および特許出願で考察されている。
【００１６】
出力記号は、生成された後、予定された受信側に鍵、または鍵をどのように生成するかを示す信号と一緒に送信することができる。いくつかの態様では、たとえば、2001年2月22日に出願された“Scheduling of multiple files for serving on a server”という名称の米国特許出願第09/792,364号に記載されたように、多数の出力記号が1つの送信パケットを構成することができる。
【００１７】
ある用途では、まずソース記号を送信し、次いで出力記号を送信することによって送信を継続することが好ましい場合がある。このような符号化システムを以下ではシステマティック符号化システムと呼ぶ。受信側では、受信器はできるだけ多くの元の入力記号を受信し、受信されなかった入力記号を1つまたは複数の出力記号で置き換え、それらを用いて、失われた入力記号を回復することを試みることができる。出力記号の送信は、プロアクティブに、受信側の明白な要求なしに行うことも、リアクティブに、すなわち、受信側による明示的な要求に応答して行うこともできる。たとえば、紛失がないか、または非常に少ない量の紛失が予想される用途では、まず元の入力記号を送信し、消失が起こった場合に追加的な出力記号を送信すると有利である場合がある。このようにして、紛失が起こらない場合には復号を行う必要はない。他の用途として、ライブ・ビデオ・ストリームを1つまたは複数の受信側に送信する場合を考える。ある程度の紛失が予想される場合、ライブ送信の性質上、受信側は、所定の時間以下の時間の間にのみデータの特定の部分をバッファすることができる。この時間の後に受信される記号の数がデータを完全に再構成するのに十分な数でない場合、ある用途では、データの、それまでに受信されている部分をビデオ・プレーヤに転送すると有利である。ある用途では、適切なソース符号化方法を用いた場合に、ビデオ・プレーヤが品質を落としてデータを再生できる場合がある。一般に、場合によっては部分的に回復されたデータを利用できる用途では、システマティック符号化システムを使用すると有利である場合がある。
【００１８】
システマティック符号化システムを生成する、Luby IまたはRaptorに記載されたチェイン・リアクションコード化システムの態様の簡単な修正態様は、一般に非効率的な結果をもたらす。たとえば、チェイン・リアクションコード化システムにおいて、最初に送信された記号が元の記号を含む場合、元のデータを回復できるようにするために、元の記号と同程度のいくつかの純粋な出力記号を受信することが必要になる場合がある。言い換えれば、元の記号の受信は復号プロセスの最小限の助けにしかならず、したがって、復号プロセスは、受信される他の記号に完全に依存する必要がある。このため、不必要に高い受信オーバヘッドが生じる。
【００１９】
したがって、効率的な符号化アルゴリズムおよび復号アルゴリズムを有し、かつチェイン・リアクションコード化システムと同程度の受信オーバヘッドを有する、チェイン・リアクションコード化システムの体系的な形態が必要である。
【発明の開示】
【００２０】
発明の概要
本発明は、体系的なチェイン・リアクションコード化プロセスおよび復号プロセスを用いてデータを符号化し復号するシステムおよび方法を提供する。これらは、多数の用途、たとえば、データがより高速に、より確実に、かつより少ない計算費用で伝達されるデータ通信システムに用いることができる。
【００２１】
本発明の一態様では、データをチェイン・リアクションコードとして符号化する方法が提供される。まず、データから入力記号の集合が生成される。その後、各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される1つまたは複数の非システマティック出力記号が、入力記号の集合から生成される。この符号化プロセスの結果として、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の集合の任意の部分集合を回復することができる。
【００２２】
本発明の他の態様および特徴は、以下の図面および詳細な説明を検討することによってよりよく理解されよう。
【００２３】
説明を明確にするため、かつ説明の都合上、最初の図面において識別される特徴および構成要素は、以後の図面でもその参照符号を保持する。
【００２４】
例示的な態様の詳細な説明
I．非システマティック・チェイン・リアクション・エンコーダおよびデコーダ
図1Aおよび1Bは、それぞれ、Luby IおよびRaptorに記載された非システマティック・チェイン・リアクション・エンコーダ130およびデコーダ170の例示的な態様を示している。Luby IおよびRaptorではこのように呼ばれていないが、これらの態様を、本明細書では、以下に示すシステマティック・エンコーダおよびデコーダとその構造および動作を区別するために「非システマティック」と呼ぶ。
【００２５】
次に図1Aを参照すると、非システマティック・エンコーダ130は、記号IS(0), IS(1), ...および鍵発生器120によって生成された鍵I0, I1, ...を入力として受け入れる。入力記号の数は、事前に分かっていてもいなくてもよい。いくつかの態様では、非システマティック・エンコーダ130は、各鍵Iごとに出力記号を生成する。図1Aでは、出力は鍵I0, I1, ...に対応するB(I0), B(I1), ...として示されている。生成される出力記号の数は、場合によっては無制限である。鍵発生器120は、鍵を生成する乱数発生器にアクセスすることができる。または、鍵Iを他の何らかの機構によって生成することができる。エンコーダ130は、たとえばRaptorに記載された静的エンコーダおよび動的エンコーダを含んでよい。エンコーダ130は、静的エンコーダを記述するのに用いられる他の鍵発生器にアクセスすることができる。
【００２６】
Luby IおよびRaptorに示されている、入力記号から出力記号を得る様々な方法がある。このような符号化方法のある例示的な態様を図2に示す。この態様は、元の入力記号からの出力記号270の生成を表している。元の入力記号は210(a)〜210(f)として示されている。いくつかの態様では、符号化プロセスの第1の段階は、Raptorに記載されているように静的符号化である。この段階は、220(a)〜220(f)および260(a)〜260(c)として示されているソース記号を生成することができる。いくつかの態様では、静的符号化はシステマティックであってよく、したがって、ソース記号220(a)〜220(f)の値は210(a)〜210(f)の値に等しい。いくつかの態様では静的符号化は行われず、その場合、入力記号はソース記号に一致する。ソース記号は、データ記号が利用可能になってときにオフラインで生成してもオンラインで生成してもよい。
【００２７】
ソース記号が作成された後、ソース記号から出力記号を生成することができる。いくつかの態様では、出力記号の値は、いくつかのソース記号の値のXORである。各出力記号について、鍵発生器120は鍵を生成し、この鍵によって、重みテーブル250から出力記号の重みが求められる。重みWが求められた後、W個のランダム・ソース記号または擬似ランダム・ソース記号が選択され、出力記号の値がこれらのソース記号の値のXORとして算出される。たとえば、図2では、出力記号270の重みは3に等しく、その値は、ソース記号220(a)、220(d)、および260(b)のXORとして求められる。出力記号の重みを本文書では出力記号の次数と呼ぶこともある。ソース記号Sが出力記号Oの値に寄与する場合、SとOを近傍と呼ぶ。たとえば、図2に示されている状況では、出力記号270はソース記号220(a)、220(b)、および220(d)の各々の近傍である。
【００２８】
図1Bのチェイン・リアクション・デコーダの様々な態様がLuby IおよびRaptorに詳しく記載されている。いくつかの態様では、十分な出力記号が収集された直後に復号プロセスが開始する。いくつかの態様では、収集される出力信号の数は、元の入力記号の数よりもわずかに多い。他の態様では、復号プロセスを開始するのに必要な収集される出力信号の数は、元の入力記号の数よりもずっと少ない。
【００２９】
いくつかの態様では、受信された出力信号ごとに、鍵発生器160が記号の対応する鍵を算出し、その鍵から近傍のソース記号を求める。
【００３０】
チェイン・リアクション復号の復号プロセスの態様の1つの可能な説明は、図3に例示されている対応する復号グラフに関して与えることができる。このグラフは、ノードの2つの集合、すなわち、それぞれソース記号および受信出力記号に対応するソース・ノードおよび出力ノードから成る。ソース・ノードはソース記号に対応し、同様に出力ノードは出力記号に対応する。出力ノードは、ソース・ノードに対応するソース記号が出力ノードに対応する出力記号の近傍である場合ソース・ノードに連結されている。この場合、この出力ノードおよびソース・ノードを近傍と呼ぶ。
【００３１】
いくつかの態様では、復号は、次数1の出力ノードO1を識別することによって開始する。次いで、O1の固有の近傍が回復され、復号グラフから除去され、プロセスは、次数1の他の出力ノードO2を識別することによって継続する。たとえば、図3に示されている状況では、O1は、330(a)として示されている出力ノードであってよい。固有の近傍320(b)を復号グラフから除去すると、次数1の他の出力ノード、すなわち330(c)が得られる。このプロセスは、すべてのソース・ノードが回復されるか、または次数1の出力ノードがなくなるまで継続する。
【００３２】
たとえば、図3の状況では、出力ノードの以下のシーケンスを選択して対応するソース・ノードを回復することができる。
【表１】
この例では復号が成功する。
【００３３】
いくつかの態様では、このグラフの解釈を用いて、Luby IまたはRaptorに示されているように、復号に必要な実際の計算のスケジュールをセットアップすることができる。さらに、上述の理想的なデコーダを、上述の特許および特許出願に記載されているように、必要なリソースを減らし、復号プロセスの速度を高めるように様々な点で変更することができる。
【００３４】
いくつかの態様では、デコーダは、対応する入力ノードを回復するのに用いられた出力ノードのシーケンスを出力することができる。たとえば、上記の場合、デコーダは、出力ノード330(a)、330(c)、220(h)、330(d)、330(i)、330(b)、330(j)、330(e)、330(f)、および330(g)に対応する指数を出力することができる。
【００３５】
以下では復号行列と呼ぶ、復号グラフの行列表現、この行列に関する復号アルゴリズムの解釈を考えると有利な場合がある。本発明のいくつかの態様では、復号グラフに対応する復号行列は、出力ノードと同じ数の行と、ソース・ノードと同じ数の列を有し、項目0または1を有する。j番目のソース・ノードがk番目の出力ノードの近傍である場合、復号行列の位置（k,j）には1がある。
【００３６】
図4は、図3の復号グラフの復号行列を示している。当業者に既知のように、復号問題は、復号行列によって与えられる数式の系を解くことに関して表すことができる。Mが復号に対応する復号行列を示し、出力記号の値のベクトルがbで示され、K個のソース・ノードがある場合、未知のソース記号値x1, x2, ..., xKは以下の行列式を満たす。
M・x = b
上式で、xが列ベクトル（x1, x2, .,,, xK）である。チェイン・リアクション復号は、結果として得られる行列が低次三角行列であり、すなわち、行列内の、主対角線の上方の値が0であるようなMの行および列の置換がある場合に成功する。たとえば、行に対して置換（3→2、8→3、2→5、10→6、5→7、6→8、7→9）を行い、列に対して置換（2→1、5→2、8→3、9→4、1→5、3→7、7→8、4→9）を行うことによって、低次三角行列が生成される。行列に関して言えば、このことは、P・M・Qが低次三角行列になるようにチェイン・リアクション復号アルゴリズムが行列PおよびQを生成することを意味する。当業者に知られているように、一次方程式の系を解く様々な方法がある。たとえば、ガウス消去アルゴリズムを使用することが可能である。
【００３７】
復号の行列図は、例示のためにのみ与えられており、制限的なものではない。特に、デコーダの実際の動作は、Luby I、Raptor、および上述の特許出願に記載されているように、前記の考察とは実質的に異なることがある。
【００３８】
いくつかの態様では、Raptorに記載されているように多段チェイン・リアクションコード化システムを使用する場合、使用される特定の静的符号化によって与えられるソース記号間の関係を表す二次グラフによって増補することができる。たとえば、低密度パリティ・チェック符号を静的符号化プロセスに使用する場合、この符号中のチェック記号の数に等しい数の出力ノードを復号グラフに追加し、これらの出力ノードの値を0に設定することができ、ソース・ノードとチェック・ノードとの間の低密度パリティ・チェック符号のグラフによって復号グラフを増補することができ、復号グラフをこの新しいグラフで置き換えることができる。低密度パリティ・チェック符号の選択は、本出願にとって重要ではない。一般に、任意の種類の静的符号化について、対応するパリティ・チェック行列は、復号グラフを増補できる2部グラフを定める。この新しいグラフを以下では修正復号グラフと呼ぶ。
【００３９】
図5は、修正復号グラフを得る手順の例示的な態様である。ソース・ノードは510(a)〜510(f)として示され、出力ノードは520(a)〜520(g)として示され、チェック・ノードは530(a)〜520(d)として示されている。ソース・ノードはソース記号に対応する。出力ノードとソース・ノードとの間のグラフは、出力ノードの近傍構成によって与えられる復号グラフである。チェック・ノードとソース・ノードとの間のグラフは、各ソース・ノード間の関係を表している。たとえば、ノード530(a)は、ソース・ノード510(a)、510(b)、510(e)、および510(f)に対応するソース記号の値のXORが0であることを示している。
【００４０】
修正復号グラフは、ソース・ノードと同じ数の列を有し、出力ノードとチェック・ノードの総計値と同じ数の行を有する、0と1から成る修正復号行列に対応する。これに対応して、修正復号行列は、1つの集合が出力ノードに対応し、1つの集合がチェック・ノードに対応する行の2つの集合から成る。L個の出力ノード、C個のチェック・ノード、およびK個のソース・ノードがある場合、修正復号行列を、L個の行およびK個の列から成る部分行列MOと、C個の行およびK個の列から成る行列MCとに分解することができる。x1, ..., xKがソース記号の未知のベクトルを示し、b1, ..., bLが受信された出力記号の既知の値を示す場合、デコーダのタスクは、MO・x = bおよびMC・x = 0によって与えられる数式の系を解くことであってよい。数式の結合系は、図6に与えられている系である。
【００４１】
チェイン・リアクション・デコーダのいくつかの態様では、非活動化デコーダと呼ばれる異なるデコーダを使用することができる。このデコーダは、”Systems and Process for Decoding a Chain Reaction Code through Inactivation”という名称を有し、参照として本明細書に組み入れられる、同一出願人による同時係属中の米国特許出願第10/459,370号に詳しく記載されており、「非活動化デコーダ」と呼ばれる。
【００４２】
II．システマティック・チェイン・リアクション・エンコーダおよびデコーダならびに動作方法
図7Aは、本発明によるシステマティック・チェイン・リアクションコードを用いてデータを符号化する例示的な方法を示している。本明細書では、語「出力記号」はチェイン・リアクションコードを指し、その例がLuby IおよびRaptorに記載されている。したがって、システマティック出力記号および非システマティック出力記号は、特定の種類のチェイン・リアクションコードであり、システマティック出力記号は送信される入力記号を含み、非システマティック出力記号は、1つまたは複数の入力記号の関数である出力記号を含む。
【００４３】
図7Aの方法は、インタネットを通じたパスや、テレビジョン送信機からテレビジョン受信機までのブロードキャスト・リンクや、ある点から別の点までの電話接続のようなリアルタイム・チャネルなどを介して送信されるデータの符号化のような様々な用途に使用することができ、または通信チャネルは、複数のCD-ROM、ディスク・ドライブ、ウェブ・サイトのような格納チャネルであってもよい。通信チャネルは、場合によっては、ある人が電話回線上でパーソナル・コンピュータからインタネット・サービス・プロバイダ（ISP）に入力ファイルを送信するときに形成されるチャネルのような、リアルタイム・チャネルと格納チャネルとの組合せであってもよく、入力チャネルは、ウェブ・サーバ上に格納され、その後インタネット上で受信側に送信される。
【００４４】
次に図7Aを参照すると、符号化プロセスは702から始まり、入力データの集合が受信され、その入力データから入力記号の集合が生成される。このプロセスの例示的な態様はLuby IおよびRaptorに記載されている。ただし、本発明による他の態様では他の技術を使用することができる。本文献および本明細書で参照されるかまたは参照として本明細書に組み入れられる文献に記載されているように、入力データは、組全体が演繹的に分かるわけではないライブ・データを含め、任意のフォーマットおよび種類のデータであってよい。
【００４５】
次に、入力記号から1つまたは複数の非システマティック式が生成される。このプロセスの特定の態様では、最初入力記号から中間入力記号が生成される（704）。その後、中間入力記号から1つまたは複数の非システマティック出力記号が生成される（706）。本発明による他の態様では、706のプロセスを省略することができ、入力記号から非システマティック出力記号が生成される。これらのプロセスを以下に詳しく示す。
【００４６】
以下に詳しく説明するように、入力記号は、入力データ用の入力記号発生器によって与えられる。上述のように、入力データは、ビデオ捕捉モジュールなどの二次装置からリアルタイムに得られるデータであってよく、また、たとえば、二次用途によって形成されるファイルまたはバッファに入力データが存在するときは、静的データであってよい。本発明の他の用途では、たとえば、ネットワーク・カードなどの二次装置またはアプリケーションからデータを受信し、それを、入力記号発生器によってさらに処理できるように格納装置に格納することによって、リアルタイム方法と静的方法の組合せによってデータを取得することができる。
【００４７】
図7Bは、本発明によるシステマティック・チェイン・リアクションコードを復号する例示的な方法を示している。最初712で、入力記号の第1の部分集合が取得される。このアプリケーションは通常、このプロセスをどのように実現するかを決定する。たとえば、通信システムに用いると、このプロセスは、通信チャネルを介して送信されるチェイン・リアクションコードの入力記号を受信することによって実行される。上述のように、本発明の特定の態様では、通信チャネルはリアルタイム・チャネルであってよく、また、格納チャネル、それらの組合せであってもよい。さらに以下に示す特定の態様では、入力記号の取得は、システマティック出力記号を含む入力記号を受信側に送信することによって行われる。チャネル・ロスが予想されるため、送信される入力記号（すなわち、システマティック出力記号）のいくらかは紛失してもよい。したがって、入力記号の元の集合の部分集合のみを受信側によって取得することができる。
【００４８】
次に714で、1つまたは複数の非システマティック出力記号が取得される。通常、非システマティック出力記号の取得は入力記号と同じ方式に従う。ただし、他の態様では他の手段を使用してよい。
【００４９】
方法は716に進み、取得されなかった1つまたは複数の入力記号が回復される。このプロセスの特定の態様では、失われた入力記号を、非システマティック出力記号、または非システマティック出力記号と取得された入力記号の組合せから回復することができる。
【００５０】
716の回復プロセスは、失われた入力記号のうちの1つ、いくつか、またはすべてを回復するのに用いることができる。所望の数の失われた入力記号が回復された後、それらを、取得された入力記号に付加し、入力記号の元の集合、したがって元のデータのコピーを再形成することができる。
【００５１】
図7Cは、本発明の一態様によるシステマティック符号化および復号を使用する例示的な通信システム700のブロック図である。通信システム700では、入力ファイル721または入力ストリーム725が入力記号発生器726に与えられる。入力記号発生器726は、各々が値および位置（図7では括弧内の整数として示されている）を有する1つまたは複数の入力記号（IS(0), IS(1), IS(2), ...）のシーケンスを入力ファイルまたはストリームから生成する。上述のように、入力記号の可能な値、すなわち、そのアルファベットは通常2M個の記号のアルファベットであり、したがって、各入力記号は入力ファイルのMビットを構成する。Mの値は一般に、通信システム700を用いることによって決定されるが、汎用システムは、用途に応じてMを変えることができるように入力記号発生器726の記号サイズ入力を含んでよい。入力記号発生器726の出力は、システマティック・エンコーダ728に与えられる。
【００５２】
非システマティック鍵発生器727は、エンコーダ728に与えられる入力記号に対応する鍵I0, I1, I2, ...を生成し、これらの非システマティック鍵は、エンコーダ728から出力された非システマティック出力記号B(I0), B(I1), B(I2), ...の値を算出するのに用いられる。各非システマティック鍵I0, I1, I2, ...は、同じ入力ファイルの鍵の大部分が固有の鍵になるように生成される。一態様では、非システマティック鍵発生器727は、上記の図1Aに示されLuby IおよびRaptorに記載されている鍵発生器120を含んでいる。ただし、他の態様では、非システマティック鍵を生成するように動作できる他の種類の装置を使用してよい。
【００５３】
システマティック鍵発生器730は、エンコーダ728に与えられる入力記号に対応し、以下に詳しく説明するように、受信されなかった1つまたは複数の入力記号を回復するのに用いられるシステマティック鍵C0, C1, C2, ...を生成する。システマティック鍵発生器730は、乱数発生器735によって生成された乱数を用いて鍵を生成する。システマティック鍵の生成については以下に詳しく説明する。非システマティック鍵発生器727およびシステマティック鍵発生器730の出力はエンコーダ728に与えられる。
【００５４】
非システマティック鍵発生器727によって非システマティック鍵Iが与えられるたびに、エンコーダ728は、入力記号発生器から与えられた入力記号から、値B(I)を有する非システマティック出力記号を生成する。生成される非システマティック出力記号は、Luby Iに記載されている出力記号（単一段符号化／復号）であっても、Raptorに記載されている出力記号（多段符号化／復号）であってもよい。例示的なシステマティック・エンコーダ728の動作については以下に詳しく説明する。各出力記号の値は、その鍵および1つまたは複数の入力記号のある関数に基づいて生成される。
【００５５】
いくつかの態様では、入力記号の数Kは、アソシエートを選択するためにシステマティック・エンコーダ728によって使用される。入力がストリーミング・ファイルである場合のようにKが既知でない場合、Kは単なる推定値であってよい。値Kはまた、入力記号およびシステマティック・エンコーダ728によって生成された中心記号の記憶域を割り当てるためにシステマティック・エンコーダ728によって使用される。
【００５６】
システマティック・エンコーダ728は、入力記号IS(0), IS(1), ...をシステマティック鍵C0, C1, ..., CK-1またはシステマティック鍵を再生するにはどうするか関する指示と一緒に送信モジュール740に転送する。送信された記号IS(0), IS(1), ...を本明細書では「システマティック出力記号」と呼ぶ。システマティック・エンコーダ728は、入力記号を送信モジュールに転送する前に、他の出力記号を生成するための入力記号のコピーを作成することができる。
【００５７】
システマティック・エンコーダ728はまた、非システマティック出力記号B(I0), B(I1), B(I2), ...を送信モジュール740に与える。送信モジュール740には、非システマティック鍵発生器727からそのような各出力記号ごとの非システマティック鍵（I0, I1, I2, ...）も与えられる。送信モジュール740は、システマティック出力記号および非システマティック出力記号を送信し、かつ使用される鍵生成方法に応じて、送信される出力記号の鍵に関するあるデータをチャネル745上で受信モジュール750に送信することもできる。チャネル745は消失チャネルと仮定されるが、通信システム700を適切に動作させるための要件ではない。モジュール740、745、および750は、送信モジュール740が出力記号およびその鍵に関する任意の必要なデータをチャネル745に送信するようになっており、受信器モジュール750が記号および場合によってはその鍵に関するある種のデータをチャネル745から受信するようになっているかぎり、任意の適切なハードウェア構成要素、ソフトウェア構成要素、物理媒体、またはそれらの組合せであってよい。Kの値は、アソシエートを判定するのに用いる場合にはチャネル745上で送信することができ、また、エンコーダ728とデコーダ755との合意によって事前に送信しておいてもよい。
【００５８】
上述のように、チャネル745は、インタネットを通じたパスや、テレビジョン送信機からテレビジョン受信機までのブロードキャスト・リンクや、ある点から別の点までの電話接続のようなリアルタイム・チャネルであってよく、また、チャネル745は、CD-ROM、ディスク・ドライブ、ウェブ・サイトのような格納チャネルであってもよい。チャネル745は、場合によっては、ある人が電話回線上でパーソナル・コンピュータからインタネット・サービス・プロバイダ（ISP）に入力ファイルを送信するときに形成されるチャネルのような、リアルタイム・チャネルと格納チャネルとの組合せであってもよく、入力チャネルは、ウェブ・サーバ上に格納され、その後インタネット上で受信側に送信される。
【００５９】
受信モジュール750は、それがデコーダ755に供給するチャネル745から非システマティック出力記号および／またはシステマティック出力記号を受信する。受信された出力記号の鍵に対応するデータは非システマティック鍵再生器760およびシステマティック鍵再生器780に与えられる。図7に示されている態様では、IS(x), IS(y), ..., IS(z)によって示されるシステマティック出力記号の集合が非システマティック出力記号の集合B(Ia), B(Ib), B(Ic), ...と一緒に受信される。他の態様では、受信モジュール750は、システマティック出力記号のみ、またはシステマティック出力記号と非システマティック出力記号の組合せを受信することができる。
【００６０】
非システマティック鍵再生器760は、受信された非システマティック出力記号の非システマティック鍵を再生し、これらの鍵をシステマティック・デコーダ755に与える。一態様では、非システマティック鍵再生器760は、上記の図1Bに示されLuby IおよびRaptorに記載されている鍵再生器160を含んでいる。ただし、他の態様では、非システマティック鍵を再生するように動作できる他の種類の装置を使用してよい。システマティック鍵再生器180は、システマティック鍵C0, C1, ...を再生し、それらをシステマティック・デコーダ755に与える。システマティック鍵再生器780は、システマティック鍵の再生を容易にするシステマティック鍵発生器730とのある共用情報にアクセスすることができる。または、システマティック鍵再生器780は、チャネル745を通じて送信された追加的な情報に基づいて鍵を再生することができる。いくつかの態様では、システマティック鍵再生器780は、システマティック鍵を生成するのに用いることのできるのと同じ乱数発生器735にアクセスすることができる。これは、乱数がある物理的装置上で生成される場合にこの物理的装置へのアクセスの形であっても、同一の振る舞いを実現するように乱数を生成するのと同じアルゴリズムへのアクセスの形であってもよい。
【００６１】
デコーダ755は、非システマティック鍵再生器760およびシステマティック鍵発生器780から与えられた非システマティック鍵を対応する出力記号と一緒に用いて、入力記号（この場合もIS(0), IS(1), IS(2), ...）を回復する。回復された入力記号は入力ファイルリアセンブラ765に転送される。システマティック・デコーダ755は、残りの入力記号を回復する前に、受信されたシステマティック出力記号IS(x), IS(y), ..., IS(z)を直接入力ファイル・リアセンブラ765に転送することができる。特に、すべての入力記号が受信された場合、デコーダは、それ以上の計算なしに、受信されたデータを入力ファイル・リアセンブラ765に転送することを選択することができる。入力ファイル・リアセンブラ765は、入力ファイル721または入力ストリーム725のコピー770を生成する。
【００６２】
以下に、システマティック・エンコーダ728およびデコーダ755の動作について詳しく説明する。本発明のいくつかの態様では、これらのユニットは、上述のようにチェイン・リアクションコード化および復号を使用することができる。
【００６３】
図8Aは、本発明の特定の態様におけるシステマティック・エンコーダ728の動作を示している。まず、システマティック・エンコーダ728は、図7の入力記号発生器726から入力記号IS(0), IS(1), ,,,, IS(K-1)を受信する。入力記号は、符号化の開始時にその全体が分かっても、部分的にのみ分かってもよい。
【００６４】
この態様では、システマティック・エンコーダ728は、生成された非システマティック出力記号と同じ数の非システマティック鍵I0, I1, ...を生成する非システマティック鍵発生器727にアクセスすることができる。さらに、システマティック鍵発生器730は、入力記号と同じ数のシステマティック鍵C0, C1, ...CK-1を生成する。システマティック・エンコーダ728は、元の入力記号を送信モジュール750に渡し、これらの記号はシステマティック出力記号として送信される。システマティック・エンコーダ728は、非システマティック鍵発生器727によって生成された各鍵I0, I1, ...ごとに非システマティック出力記号B(I0), B(I1), ...を生成するように動作する。システマティック鍵発生器730の動作について以下に詳しく説明する。
【００６５】
システマティック鍵発生器730およびシステマティック鍵発生器780（図7）は、システマティック鍵再生器780が首尾よくシステマティック鍵発生器730と同じ鍵を生成できるようにある種の共用情報にアクセスすることができる。いくつかの態様では、この共用情報は、システマティック鍵再生器780に送信することができる。他の態様では、システマティック鍵は、符号の他のパラメータ、たとえば入力記号の数や重みテーブルの確定的関数であってよい。
【００６６】
いくつかの態様では、システマティック鍵は、入力記号の数のいくつかまたはすべての関連する値について事前に算出しておくことができる。いくつかの態様では、システマティック鍵を入力記号の異なるいくつかの集合に再使用してよい。他の態様では、システマティック鍵発生器730とシステマティック鍵発生器780とのある種の共用情報を用いて、あらゆる入力ブロックについてシステマティック鍵を再計算することができる。
【００６７】
図8Bは、本発明の特定の態様におけるシステマティック・デコーダ755の動作を示している。システマティック・デコーダ755は、それぞれIS(x), IS(y), ..., IS(z)およびB(Ia), B(Ib), ...として示されているシステマティック出力記号を受信モジュール750から受信する。特定の態様では、システマティック・デコーダ755は、システマティック鍵再生器780および非システマティック鍵再生器760にアクセスすることができる。システマティック・チェイン・リアクション・デコーダの出力は、初期入力記号の集合IS(0), IS(1), ..., IS(K-1)である。
【００６８】
図9Aは、システマティック・エンコーダ728を詳しく示している。システマティック・エンコーダ728は、チェイン・リアクション・デコーダ910およびチェイン・リアクション・エンコーダ920を含んでいる。さらに、システマティック・エンコーダ728は、メモリ装置（図示せず）にアクセスし、中間記号S(0), S(1), ..., S(K-1)を格納することができる。
【００６９】
チェイン・リアクション・デコーダ910は、入力記号IS(0), IS(1), ..., IS(K-1)およびシステマティック鍵C0, C1, ..., CK-1を受信すると、たとえば、本明細書に組み入れられている特許および特許出願に記載されているチェイン・リアクションコード化符号の復号方法を用いて、中間入力記号の集合S(0), S(1), ..., S(K-1)を算出する。本発明のいくつかの態様では、中間入力記号をメモリまたはディスク上に格納することができる。他の態様では、中間入力記号を、利用可能になってときにチェイン・リアクション・エンコーダ920に転送することができる。
【００７０】
チェイン・リアクション・エンコーダ920は、チェイン・リアクション・デコーダ910によって生成された中間入力記号を、非システマティック鍵再生器727によって生成された非システマティック鍵I0, I1, I2, ...と一緒に用いて非システマティック出力記号B(I0), B(I1), ...を生成する。いくつかの態様では、この符号化プロセスは、Luby IまたはRaptorに記載されている入力記号符号化プロセスを用いて、本発明の中間入力記号がLuby Iの入力記号として使用される修正を施して実現することができる。特定の態様では、非システマティック出力記号は、入力記号IS(0), IS(1), ..., IS(K-1)の後で送信モジュール140に供給される。しかし、このことは本発明の機能にとって重要ではない。さらに、送信モジュール740からの送信順序も変えることができる。
【００７１】
図9Bは、チェイン・リアクション・デコーダ930およびチェイン・リアクション・エンコーダ940を含むシステマティック・デコーダ755の例示的な態様である。システマティック・デコーダへの入力は、いくつかが受信されたシステマティック出力記号IS(x), IS(y), IS(z), ...を含み、いくつかが受信された非システマティック出力記号B(Ia), B(Ib), ...を含む受信された出力記号を含む。いくつかの態様では、デコーダは、受信されたシステマティック記号をメモリ装置にコピーし、それらを入力ファイル・リアセンブラ765に直接転送することができる。
【００７２】
チェイン・リアクション・デコーダ930は、記号IS(x), IS(y), ..., IS(z), B(Ia), B(Ib), ...、システマティック鍵再生器780によって生成されたシステマティック鍵Cx, Cy, ...Cz、非システマティック鍵再生器760によって生成された非システマティック鍵Ia, Ib, ...を用いて中間入力記号S(0), S(1), ..., S(K-1)を生成する。システマティック鍵Cx, Cy, ..., Czは、受信された入力記号IS(x), IS(y), ..., IS(z)に相当する。いくつかの態様では、回復された中間記号は、チェイン・リアクション・エンコーダ440に渡す前に二次記憶域に格納しておくことができる。他の態様では、これらの中間記号を直接チェイン・リアクション・エンコーダ940に渡すことができる。
【００７３】
チェイン・リアクション・エンコーダ940は、中間入力記号、および消失したシステマティック出力記号IS(u), IS(v), ..., IS(w)に対応するシステマティック鍵Cu, Cv, ..., Cwを用いて、失われた元の入力記号IS(u), IS(v), ..., IS(w)を出力する。例示的な態様として、各初期鍵Cu, Cv, ..., Cwについて、デコーダは、重みWおよび中間入力記号S(0), ..., S(K-1)のうちのW個の記号を識別し、各出力記号の値をXORし、システマティック鍵Cu, Cv, ..., Cwに対応する消失した入力記号IS(u), IS(v), ..., IS(w)を得る。チェイン・リアクション・エンコーダ940によって使用される計算リソースの量は、一態様では、消失するシステマティック出力記号の数に比例する。たとえば、すべての出力記号が受信された場合、デコーダは計算を実行せず、受信された記号を入力ファイル・リアセンブラ765に転送する。
【００７４】
特定の態様では、静的符号化を用いる場合、チェイン・リアクション・エンコーダ940とチェイン・リアクション・デコーダ910は、同じ重みテーブルにアクセスし、同じ静的符号化／復号を使用する。同様に、チェイン・リアクション・エンコーダ920とチェイン・リアクション・デコーダ930は、同じ重みテーブルにアクセスし、同じ静的符号化／復号を使用することができる。
【００７５】
システマティック鍵を算出する方法
本発明の特定の態様では、システマティック鍵は、記号送信の前にシステマティック鍵発生器730によって算出され、記号受信後にシステマティック鍵再生器780によって再計算される。システマティック鍵は、中間入力記号S(0), S(1), ... S(K-1)を得るために、チェイン・リアクション・デコーダ910およびエンコーダ930によって使用される。
【００７６】
本発明の特定の態様では、システマティック鍵は、K個の記号の固有の効率的なチェイン・リアクション復号が、これらの鍵によって生成されたK個の出力記号のみを用いて可能になるように算出される。ここで、復号は、Luby I、Raptor、もしくはInactivation Decodingに記載された復号方法のいずれか、またはたとえばInactivation Decodingに記載されたガウス消去アルゴリズムに基づくより一般的な復号方法のいずれかであってよい。
【００７７】
図10は、システマティック鍵生成プロセスの例示的な態様である。システマティック鍵発生器への1つの入力は、入力記号IS(0), IS(1), ..., IS(K-1)の数Kであってよい。システマティック鍵生成は、変数jを0に等しく設定することによって始まる。アルゴリズムの間、K個の列を持つ行列Mは、最初0個の列を有し、アルゴリズムが進行するにつれて行を追加することによって更新される。jのあらゆる異なる値について、アルゴリズムは、1020で異なる鍵D(j)を生成する。この鍵は、Luby IまたはRaptorに記載されている方法によって生成することができ、図1に示されている乱数発生器135を使用することができる。次に1030で、鍵D(j)を用いて行列Mのj番目の行の項目が算出される。このような計算の1つの可能な態様では、チェイン・リアクションコード化プロセスにおいて鍵D(j)が使用される。この場合、鍵D(j)は、重みテーブルを用いて、重みWおよび値0, 1, ..., K-1のうちのW個の値を識別する。鍵D(j)は次いで、Mのj番目の行の位置mに、mが、生成されたランダム値または擬似ランダム値の一方である場合に1を設定し、j番目の行の他の値を0に設定する。
【００７８】
1040で、現在構成されている行列Mが、整数2法として掛け算および足し算が実行される0および1から成る集合を指すバイナリ・フィールドGF(2)上で線形に独立したK個の行を有するかどうかが判定される。1040のこのプロセスは、様々な方法で実行することができる。たとえば、バイナリ・フィールドGF(2)上のガウス消去を用いてこれをチェックすることができる。しかし、当業者に既知の他の多数の方法がある。たとえば、非活動化復号の教示を行列Mに適用する場合、Mは、Mに適用される非活動化デコーダがうまく動作する場合にのみK個の線形に独立した行を含む。
【００７９】
1040の試験が肯定的であり、Mの行r(0), r(1), ..., r(K-1)が線形に独立していることが分かった場合、システマティック鍵C0, C1, ..., CK-1は鍵D(r(0)), ..., D(r(K-1))に設定され、これらの鍵が出力される。1040の試験が否定的である場合、1060でカウンタjが増分され、1020から計算が繰り返される。
【００８０】
当業者によって、システマティック鍵を生成する他の同等のまたは実質的に同様の方法を構想することができる。たとえば、アルゴリズムの実行中に鍵D(j)を一度に1つずつ生成するのではなく、L個のそのような鍵の集合を事前に生成しておき、アルゴリズムの段階jでこの一群の鍵から鍵D(j)を取り出すことができる。ここで、Lは入力記号の数の関数であってよい。
【００８１】
システマティック鍵を生成する第2の方法が図11に例示されている。この方法では、このアルゴリズムへの入力は、K個の入力記号と、通常K以上である数Lとから成る。いくつかの態様では、Lは、Luby IまたはRaptorに記載されているように、復号が成功することを高い確率で保証するために収集すべき出力記号の数であってよい。
【００８２】
1110で、L個の鍵D(0), ..., D(L-1)が生成される。このプロセスは、乱数発生器735を用いることによって行うことができる。他の態様では、これらの鍵を再使用可能な鍵の一定のリストから生成することができる。このプロセスは、鍵がどのように生成されたかを示すこともできる。たとえば、乱数発生器を使用する場合、発生器のシードを、将来システマティック鍵再生器によって使用できるように記録することができる。
【００８３】
鍵D(0), D(1), ..., D(L-1)を用いて、上記に説明し図5に例示されているように修正復号グラフが1120でセットアップされる。このプロセスは、符号の特定の重みテーブルの知識を使用すると共に、Raptorに記載されているように、使用される静的符号化の知識を使用することができる。
【００８４】
1130で、すでに示されている方法のいずれかを用いて修正復号グラフが復号される。復号の副産物として、入力ノードの回復をトリガする出力ノードの指数r(0), r(1), ..., r(K-1)が記録される。1140で、システマティック鍵がC0=D(r(0)), ..., CK=D(r(K-1))として出力される。
【００８５】
図12は、システマティック鍵を算出する第3の方法を示している。図11の方法と同様に、1210で鍵D(0), ..., D(L-1)が生成され、これらの鍵、および場合によっては重みテーブルを用いて復号グラフがセットアップされる。次に、1230で、集合Sが空集合として初期設定される。集合Sは、入力ノードの値を回復するためにチェイン・リアクション復号プロセスで使用される出力記号の指数を含む。1240で、次数1の出力ノードを識別することによってチェイン・リアクション復号プロセスが復号グラフに適用される。この出力ノードの指数は、この集合の上述の役割に従って集合Sに追加される。1250で、集合Sがすでに正しい数の要素を有しているかどうかについての試験が行われる。正しい数の要素を有していない場合、アルゴリズムは1240に戻り、次数1の他の入力ノードが選択され、復号プロセスが継続される。SのサイズがKである場合、1260で、Sの要素が最小の要素からソートされてソート済み要素S0, ..., SK-1が得られ、システマティック鍵がC0=D(S0), ..., CK-1=D(SK-1)として算出される。
【００８６】
図13は、本発明によるシステマティック鍵を算出する第4の方法を示している。この方法では、入力Kおよび鍵の集合に対して、鍵の所与の集合から元のK個の記号を復号できるかどうかを判定できる復号アルゴリズムが利用可能であると仮定される。このようなアルゴリズムの例は、Luby I、Raptor、またはInactivation Decodingに記載されたデコーダによって与えられる。
【００８７】
1310では、L個の鍵D(0), ..., D(L-1)が生成される。上記の説明と同様に、このプロセスは、乱数発生器735を用いることによって行うことができ、または一定の再使用可能な鍵から鍵を生成することができる。1315で、デコーダを用いて、鍵の集合D(0), ..., D(L-1)からK個の記号を復号することが可能かどうかが判定される。復号が成功しない場合、鍵の所与の集合はシステマティック鍵を部分集合として含んでおらず、アルゴリズムは1325でアボートする。他の場合には、3つの集合は1330で初期設定される。これらの集合をそれぞれ、Systematic（システマティック）、Non_Systematic（非システマティック）、およびUnvisited（未アクセス）と呼ぶ。アルゴリズムの終了時に、集合Systematicは、システマティック鍵の集合を含む。最初、1330で、SystematicおよびNon_Systematicは空の集合に初期設定され、一方、Unvisitedはすべての元の鍵D(0), ..., D(L-1)を含む。プロセス1335から1360で、集合Unvisitedから鍵が取り出され、集合SystematicおよびUnvisitedに含まれる鍵に対して復号が試みられる。試みが成功した場合、選択された鍵Cはシステマティック鍵の集合に属していない。これに対して、復号が成功しなかった場合、鍵はシステマティック鍵の集合に属している。未アクセス鍵の取出しおよび復号（1335）、復号が成功したかどうかの試験（1340）、ならびにその後行われる、デコーダの結果に基づく集合SystematicまたはNon_Systematicへの選択された鍵の追加（1345および1350）から成るこの手順は、集合Systematicが元の入力記号の数Kよりも少ない入力記号を有するかぎり繰り返される。
【００８８】
図14は、本発明によるシステマティック記号および非システマティック記号を有するチェイン・リアクションコードを復号する方法を示している。1410で、受信された非システマティック出力記号B(Ia), B(Ib), ...に対応する非システマティックIa, Ib, ...を用いて、受信された非システマティック出力記号と同じ数の行および入力記号と同じ数の列を有する行列Bが生成される。各鍵ごとに、チェイン・リアクションコードを符号化する場合と同じ機構を用いて、重みW、および鍵に対応する出力記号が生成される入力記号の指数の集合J1, J2, ..., JWが生成される。次いで、行列Bの対応する行で、J1, J2, ..., JWに対応する位置が1に設定され、一方、その行の他の位置が0に設定される。この手順は、受信された非システマティック記号に対応するすべての鍵が無くなるまで繰り返される。
【００８９】
次に1420で、同様の手順が適用され、システマティック鍵C0, C1, ..., CK-1から得た入力記号と同じ数の行および列を有する正方行列Cが作成される。このプロセスでは、Aと呼ばれる行列Cの逆数も算出される。Aの逆数の計算は、当業者に知られているように様々な方法で行うことができる。たとえば、ガウス消去アルゴリズムを用いてAを算出することができる。他の態様では、ある形態のチェイン・リアクション復号を利用してこの段階を実行することができる。このことは、本開示の以下の例に示す。
【００９０】
1430で、バイナリ・フィールドGF(2)上で行列BおよびAの積が算出され、行列Hが得られる。次に1440で、指数の2つの集合EおよびRが求められる。Eは受信されなかったシステマティック記号の指数の集合であり、一方、Rは受信されたシステマティック記号の指数の集合である。たとえば、指数0, 1, 2, ..., 10を有する11個の入力記号があると仮定する。送信後に、指数0, 3, 9, 10に対応するシステマティック記号が受信された場合、R={0, 3, 9, 10}になり、一方E={1, 2, 4, 5, 6, 7, 8}になる。次いで、1430でBとAの積として算出された行列Hが2つの部分行列HEおよびHRに細分される。HEは、受信されなかったシステマティック記号の指数に対応するHの列を取り出すことによって得られたHの部分行列であり、HRは、受信されたシステマティック記号の指数に対応するHの部分行列である。上記の例では、HEは、Hの列1, 2, 3, 4, 5, 6, 7および8によって形成されるHの部分行列である。
【００９１】
1450で、行列HRに、受信されたシステマティック記号IS(x), IS(y), ..., IS(z)で形成されるベクトルが掛け算される。たとえば、上記の場合、HRにシステマティック記号0, 3, 9, 10（この順序で）の値が掛け算される。実際の掛け算は、当業者に既知のように様々な方法で行うことができる。この掛け算の結果は、以下ではベクトルyと呼ばれ、将来使用できるように格納することができる。1460で、受信された非システマティック出力記号を用いてベクトルbがセットアップされる。L個のそのような記号がある場合、ベクトルb内の項目の数はLである。この段階は単なる論理的な段階であってよい。言い換えれば、この段階では計算は必要とされない。次に、ベクトルyに格納されている前の掛け算の結果は、構成要素ごとにベクトルbの項目とXORされ、すなわち、受信された各非システマティック出力記号は、ベクトルyの対応する記号とXORされる。この演算の結果は、受信された非システマティック記号の代わりに格納することも、異なる位置に格納することもできる。
【００９２】
このXORが求められた後、消失したシステマティック記号に対応する行列HEを用いて一次方程式の系がセットアップされる。ここで、系HE*x=y+bの解xは、消失したシステマティック記号の値に相当する。この場合も、このプロセスは、様々な方法で行うことができ、たとえば、ガウス消去や、Luby I、Raptor、またはInactivation Decodingに開示されたチェイン・リアクション復号の変形形態のいずれかを用いて行うことができる。
【００９３】
復号についてのこの行列図は、例示のためのみのものであり、制限的なものではない。本開示を検討すれば、当業者には復号手順の多数の変形態様が明らかになろう。
【００９４】
III．例示的なシステマティック符号化および復号
次に、図15〜17を参照して、システマティック・チェイン・リアクションコード化システムのいくつかの態様の動作のいくつかの局面の簡単な例を示す。与えられるすべての例において、重みテーブルの効果は、所与の記号の鍵を仮定した場合の所与の記号の近傍のリストに関して暗黙的に述べられるに過ぎない。
【００９５】
システマティック鍵の計算
図15Aは、システマティック鍵C0, C1, ..., C8を得るのに用いられる復号グラフを表している。たとえば図11の1110の演算によって12個の鍵D(0), D(1), ..., D(11)がすでに生成されていると仮定される。図15Aのグラフは、鍵D(0), ..., D(11)を用いた、1520(a), ..., 1520(i)として示されている入力ノードと1530(a), ..., 1530(l)として示されている出力ノードとの修正復号グラフを表している。次に、このグラフにチェイン・リアクション復号を適用して、チェイン・リアクション復号の実行時に入力ノードの回復をトリガする出力ノードの鍵としてシステマティック鍵が得られる。
【００９６】
動作時には、ノード1530(a)を用いて入力ノード1520(b)を回復することができる。したがって、この場合、第1のシステマティック鍵C0は、生成された鍵のうちの第1の鍵、すなわち、D(0)に等しい。入力ノード1520(b)が回復すると、出力ノード1530(c)は次数1のノードになり、したがって、ノード1520(e)の回復をトリガする。このような動作を継続することによって、図15Aで明るい灰色に示されているノードを用いて入力ノードを回復できることが分かる。入力ノードを回復するのに用いられる出力ノードのシーケンスは、1530(a), 1530(b), 1530(c), 1530(d), 1530(e), 1530(f), 1530(g), 1530(h), 1530(j)に等しい。その結果、システマティック鍵のシーケンスを図15Bに示されているように選択することができる。
【００９７】
図示のチェイン・リアクション復号の回復プロセスが概念的なものに過ぎないことに留意されたい。特に、この特定の例ではXOR演算は実行されない。
【００９８】
システマティック符号化
図9Aに概略的に示されているように、システマティック・チェイン・リアクション・エンコーダは、チェイン・リアクション・デコーダ910およびチェイン・リアクション・エンコーダ920から成っている。したがって、システマティック・チェイン・リアクションコード化の演算は2つの部分に分割される。この2つの部分はそれぞれ、図16Aおよび図16Bに例示されている。
【００９９】
図16Bは、チェイン・リアクション・デコーダ910の動作を例示している。入力記号はIS(0), ..., IS(8)として示されている。鍵C0, C1, ..., C8を用いて入力記号と中間入力記号S(0), ..., S(8)との間の図形上の依存性がセットアップされる。たとえば、鍵C0は、IS(0)がS(1)の値に等しいことを示し、一方、鍵C4は、S(2)、 S(5)、およびS(7)の値のSORに等しいことを示している。ここで、チェイン・リアクション復号を適用して値S(0), S(1), ..., S(8)を得ることができる。これらの値を得るためのスケジュールは、図7でシステマティック鍵発生器730からチェイン・リアクション・デコーダ910に転送しておくことができる。これは、このスケジュールが鍵C0, C1, ..., C8を得るようにセットアップされているからである。システマティック鍵発生器の動作とは異なり、この段階では、個々の記号の値のXORを使用してよい。
【０１００】
図16Aの例では、スケジュールはまずS(1)の値を生成し、それによって、IS(1)の値を用いてS(4)の値を生成することができる。これによって、S(0)、S(7)などの値の回復がトリガされる。
【０１０１】
図16Bは、最初の11個の非システマティック出力記号O(0), ..., O(10)の生成を示すことによって図9Aのチェイン・リアクション・エンコーダ920の動作を例示している。（図示の出力記号O(i)は前述の出力記号B(Ii)を指す）。前述のように、システマティック・エンコーダの出力は、システマティック出力記号IS(0), ..., IS(8)と、その後に続く出力記号O(0), ..., O(10), ...とから成っている。この特定の順序は例示的なものであり、本発明による他の態様では他の順序を使用することができる。
【０１０２】
システマティック復号
図17Aおよび17Bは、システマティック・チェイン・リアクション復号のプロセスの態様を例示している。受信されたシステマティック出力記号がIS(6)およびIS(7)であり、一方、受信された非システマティック出力記号がO(0)、O(3)、O(4)、O(6)、O(7)、O(8)、O(9)、およびO(10)であると仮定する。デコーダのタスクは、失われたシステマティック出力記号の値、すなわち、値IS(0)、IS(2)、IS(3)、IS(4)、IS(5)、およびIS(8)を算出することである。図17Aは、図9Bにおけるチェイン・リアクション・デコーダ930およびチェイン・リアクション・エンコーダ940を1つのデコーダとして組み合わせるにはどうしたらよいかの例を示している。いくつかの用途では、このような組合せによって計算を節約することができる。
【０１０３】
受信されたシステマティック出力記号に対応する鍵C1、C6、およびC7、ならびに受信された非システマティック出力記号に対応する鍵を用いて、受信された出力記号と中間入力記号S(0), ..., S(8)とのグラフがセットアップされる。出力記号と、XORされると出力記号の値を与えるすべての中間入力記号との間に接続線が描かれる。個々の接続は、図16Aおよび16Bに示されている接続と同じである。受信された出力記号の特定の順序は、復号グラフを表すように選択された順序に等しくなくてよい。
【０１０４】
このグラフは、消失したシステマティック出力記号に対応するノードの他のレイヤによって拡張される。このグラフは、入力記号IS(0)、IS(2)、IS(3)、IS(4)、IS(5)、およびIS(8)が、それらがXORとなる中間入力記号に点線を介して接続される図17Aの上部に対応する。この場合も、これらの接続は、図17Aにおける対応する接続に対して検証することができる。
【０１０５】
この特定の例における復号プロセスは、下方のグラフにチェイン・リアクション復号を適用することによって始めることができる。1つの中間記号が回復されるたびに、その値を、図の上部における受信されなかった元の記号のうちのこの記号のすべての近傍の値とXORすることができる。最初、これらの記号の値を0に設定することができる。
【０１０６】
たとえば、出力記号O(4)を用いてS(3)の値を回復することができる。次いで、S(3)の値をIS(5)の現在の値にXORすることができる。この段階の後で、IS(5)の値はS(3)の値に等しくなる。S(3)を回復すると、出力ノードO(10)の次数は0に下がる。この出力ノードは中間記号S(6)の値を回復する。この値はIS(5)の現在の値にXORされ、したがって、この段階の後IS(5)の値が回復される。このプロセスは、受信されなかったすべてのシステマティック入力記号が回復されるまで継続することができる。
【０１０７】
図17Bは、失われた出力記号を回復するプロセスを示している。回復された記号は長方形に囲まれている。回復されたシステマティック出力記号は灰色の長方形に囲まれている。この図における各縁部のラベルは、回復に使用される記号を表している。
【０１０８】
たとえば、記号O(4)は、S(3)を回復するのに用いられる。記号O(10)はS(6)を回復するのに用いられる。S(3)およびS(6)はS(5)を回復するのに用いられる。S(6)を回復すると（O(9)を用いて）S(8)の回復がトリガされると共に、（受信されたシステマティック出力記号IS(7)を用いて）S(0)の回復がトリガされる。S(8)を回復するとIS(3)の回復がトリガされる。S(0)を回復すると、（IS(1)を用いて）S(4)の回復がトリガされる。一方、S(8)を回復すると、O(0)を用いて、S(1)の回復がトリガされ、S(1)はS(4)と一緒にIS(2)を回復する。さらに、S(1)を回復するとIS(0)が回復される。なぜなら、これらの値が同一であるからである。O(8)およびS(4)の回復された値を用いて、S(5)の値が得られる。これによって、IS(8)の値が回復される。というのは、IS(8)が、S(5)、S(4)、およびS(0)のXORであり、すべてのこれらの値がこの段階で既知であるからである。IS(6)およびS(4)を用いて、S(7)の値が得られる。これによって、O(7)の値を用いてS(2)の値が回復される。S(2)は、S(7)と一緒に、最後の残りの入力記号、すなわちIS(4)の値を回復する。
【０１０９】
上記の説明は、例示および説明のために与えられている。この説明は、網羅的なものでも、本発明を開示された厳密な形態に制限するものでもなく、上記の教示を考慮して多数の修正態様および変形態様が可能であることは自明である。上述の態様は、本発明の原則およびその実際的な適用を最もうまく説明し、それによって、当業者が、様々な態様、および考えられる特定の用途に適した様々な修正態様で本発明を最もうまく利用することができるように選択されている。本発明の範囲は特許請求の範囲によって定義されるものである。
【０１１０】
参照として本明細書に組み入れられる文書
“Information Additive Code Generator and Decoder for Communication Sysmtes”という名称のMichel G. Lubyの米国特許第6,307,487号（本明細書ではLuby Iと呼ぶ）
2001年2月22日に出願され、“Scheduling of Multiple Files for Serving on a Server”という名称を有する米国特許出願第09/792,364号
2001年12月21日に出願され、“Multi-Stage Code Generator and Decoder for Communication Systems”という名称を有する米国特許出願第10/032,156号（本明細書では「Raptor」と呼ぶ）
2003年6月10日に出願され、“Systems and Processes for Decoding Chain Reaction Codes through Inactivation”という名称を有する米国特許出願第10/459,370号（本明細書では「Inactivation Decoding」と呼ぶ）
【図面の簡単な説明】
【０１１１】
【図１Ａ】非システマティックチェイン・リアクション・エンコーダの例示的な態様を示す図である。
【図１Ｂ】非システマティックチェイン・リアクション・デコーダの例示的な態様を示す図である。
【図２】チェイン・リアクション復号プロセスに用いられる元の入力記号からの出力記号の生成を示す図である。
【図３】チェイン・リアクション復号プロセスに用いられる例示的な復号グラフを示す図である。
【図４】図3に示されている復号プロセスの復号行列を示す図である。
【図５】チェイン・リアクション復号プロセスに用いられる修正復号グラフを得る例示的な手順を示す図である。
【図６】チェイン・リアクション復号プロセスに用いられる修正復号式を示す図である。
【図７Ａ】本発明によるシステマティック・チェイン・リアクションコードを用いてデータを符号化する例示的な方法を示す図である。
【図７Ｂ】本発明によるシステマティック・チェイン・リアクションコードを復号する例示的な方法を示す図である。
【図７Ｃ】本発明の一態様によるシステマティック符号化および復号を用いた通信システムのブロック図である。
【図８Ａ】本発明の一態様によるシステマティック・エンコーダの動作を示す図である。
【図８Ｂ】本発明による一態様によるシステマティック・デコーダの動作を示す図である。
【図９Ａ】本発明によるシステマティック・エンコーダの一態様を示す図である。
【図９Ｂ】本発明によるシステマティック・デコーダの一態様を示す図である。
【図１０】本発明によるシステマティック鍵を生成する一方法を示す図である。
【図１１】本発明によるシステマティック鍵を生成する第2の方法を示す図である
【図１２】本発明によるシステマティック鍵を生成する第3の方法を示す図である。
【図１３】本発明によるシステマティック鍵を生成する第4の方法を示す図である。
【図１４】本発明によるシステマティック記号および非システマティック記号を有するチェイン・リアクションコードを復号する方法を示す図である。
【図１５Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１５Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１６Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１６Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１７Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１７Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2002年10月5日に出願され、参照としてすべての目的について本明細書に全体的に組み入れられる“Systematic Encoding and Decoding of Chain Reaction Codes”という名称の米国特許仮出願第60/319,597号の利益を主張する。
【０００２】
本発明は、すべての種類のデータを符号化し復号するシステムおよび方法に関し、特に、チェイン・リアクションコードを用いてデータを符号化し復号するシステムおよび方法に関する。
【背景技術】
【０００３】
通信チャネル上での送信側と受信側との間のデータの伝送は多数の文献の主題となっている。常にそうであるとは限らないが、受信側は送信側によってチャネル上で送信されたデータの正確なコピーをある程度確実に受信することを望むことが好ましい。チャネルが（物理的に実現可能なほとんどすべてのシステムをカバーする）完全な忠実度を有さない場合、送信時に紛失するかまたは歪曲されたデータをどのように対処するかという問題がある。受信側は、破壊されたデータが誤って受信されたデータであることが常に分かるわけではないので、失われたデータ（消失）に対処するのは破壊されたデータ（誤り）に対処するよりも容易であることが多い。消失および／または誤りを訂正するために多くの誤り訂正符号が開発されている。通常、使用される特定の符号は、データが送信されているチャネルのIDおよび送信されているデータの性質に関するある情報に基づいて選択される。たとえば、チャネルが長い非忠実度期間を有することが分かっている場合、その用途にはバースト誤り符号が最適である。短くまれな誤りのみが予想される場合、簡単なパリティ符号が最適である。
【０００４】
符号を選択する際の他の問題は、伝送に使用されるプロトコルである。インタネットの場合、データ転送にパケット・プロトコルが使用される。このプロトコルはインタネット・プロトコルまたは略して「IP」と呼ばれる。データのファイルまたはその他のブロックは、IPネットワーク上で送信される際、等しいサイズの入力記号に区分され、入力された記号は連続したパケットに入れられる。入力記号の「サイズ」は、入力記号が実際にビット・ストリームに分解されるかどうかにかかわらずビット単位で測定され、入力記号は、2M個の記号のアルファベットから選択される際にはMビットのサイズを有する。このようなパケットによる通信システムでは、パケット対応符号化方式が適している。
【０００５】
伝送は、予定された受信側がネットワークにおいて消失が起こった場合でも元のファイルの正確なコピーを回復するのを可能にする場合に信頼できる送信と呼ばれる。インタネット上では、散発的な輻輳によってルータのバッファリング機構がその能力の限界に達し、着信パケットを捨てざるを得なくなるために、パケット・ロスが起こることが多い。転送時の消失に対する保護は多くの研究の主題となっている。
【０００６】
Transport Control Packet（「TCP」）は、肯定応答機構を有する一般に使用されているポイント・ツー・ポイント・パケット制御方式である。TCPを用いた場合、送信側は指示されたパケットを送信し、受信側は各パケットの受信に対して肯定応答する。パケットが紛失した場合、送信側に肯定応答が送信されず、送信側はパケットを送信し直す。TCPなどのプロトコルでは、肯定応答パラダイムは、致命的な障害を起こさずにパケットを消失させる。というのは、肯定応答がないことに応答するか、または受信側からの明示的な要求に応答して紛失したパケットを再送することができるからである。
【０００７】
肯定応答によるプロトコルは一般に、多数の用途に適しており、実際、現在のインタネット上で広く使用されているが、非効率的であり、場合によっては、Luby Iに記載されているようなある種の用途ではまったく実現不能である。
【０００８】
この伝送上の問題を解決するために提案されている1つの解決策は、肯定応答によるプロトコルの使用を避け、その代わりに、リード・ソロモン符号、トルネード符号、チェイン・リアクションコードなどの順方向誤り訂正（Forward Error-Correction（FEC））符号を用いて信頼性を高めることである。基本的な考えは、コンテントを構成する入力記号のみの代わりにコンテントから生成された出力記号を送信することである。リード・ソロモン符号やトルネード符号のような従来の消失訂正符号は、一定の長さのコンテントについて一定数の出力記号を生成する。たとえば、K個の入力記号について、N個の出力記号を生成することができる。このN個の出力記号は、K個の元の入力記号およびN-K個の冗長記号を含んでよい。記憶装置に支障がなければ、サーバは、各コンテントの出力記号の集合を一度だけ算出し、カルーセル・プロトコルを用いて出力記号を送信することができる。
【０００９】
ある種のFEC符号に伴う1つの問題は、これらの符号では過度の計算力またはメモリを使用する必要があることである。他の問題は、符号化プロセスの前に出力記号の数を決定しなければならないことである。このため、パケットの紛失率の推定値が高すぎる場合には非効率な結果をもたらす可能性があり、パケットの紛失率の推定値が低すぎた場合には障害が発生する恐れがある。
【００１０】
従来のFEC符号では、生成できる可能な出力記号の数は、コンテントが区分される入力記号の数と同程度である。常にそうであるとは限らないが、通常、これらの出力記号のほとんどまたはすべては、送信段階の前の前処理段階で生成される。これらの出力記号は、長さが元のコンテントに等しいかまたは元のコンテントよりもわずかに長い出力記号の任意の部分集合からすべての入力記号を再生できるという特性を有する。
【００１１】
“Information Additive Code Generator and Decoder for Communication Systems”という名称の米国特許第6,307,487号（以下では“Luby I”と呼ぶ）および“Multi-Stage Code Generator and Decoder for Communications Systems”という名称の米国特許出願第10/032,156号（以下では“Raptor”と呼ぶ）に記載された「チェイン・リアクションコード化」は、上記の問題に対処する異なる形態の転送誤り制御に相当する。チェイン・リアクションコードでは、生成できる一群の可能な出力記号は、入力記号の数よりも一桁多く、必要に応じ送信段階と並行して一群の可能な出力記号からランダム出力記号を高速に生成することができる。チェイン・リアクションコードは、長さが元のコンテントよりもわずかに長いランダムに生成された出力記号の集合の任意の部分集合からコンテントのすべての入力記号を再生できるという特性を有する。
【００１２】
様々なチェイン・リアクションコードの他の説明は、2000年9月22日に出願され、“On Demand Encoding With a Window”と題する米国特許出願第09/668,452号や、2000年10月18日に出願され“Generating High Weight Output symbols Using a Basis”という名称の米国特許出願第09/691,735号に記載されている。
【００１３】
チェイン・リアクションコード化システムのいくつかの態様は、エンコーダおよびデコーダから成る。データは、ブロックまたはストリームの形でエンコーダに与えることができ、エンコーダは、ブロックまたはストリームから出力記号を高速に生成することができる。いくつかの態様、たとえば、Raptorに記載されている態様では、静的エンコーダを用いてオフラインでデータを前符号化することができ、複数の元のデータ記号および静的出力記号から出力記号を生成することができる。
【００１４】
チェイン・リアクションコード化システムのいくつかの態様では、符号化および復号プロセスは重みテーブルに依存する。重みテーブルは、ソース記号の集合に関する確率分布を表している。すなわち、1からソース記号の数までの間の任意の数Wについて、重みテーブルは固有の確率P(W)を示す。P(W)は、Wの実質的に多数の値について0である可能性があり、その場合、P(W)が0でない重みWのみを含むことが望ましい。
【００１５】
チェイン・リアクションコード化システムのいくつかの態様では、出力記号は以下のように生成される。すなわち、あらゆる出力記号について、鍵がランダムに生成される。この鍵に基づいて、重みテーブルから重みWが算出される。次いで、W個のソース記号のランダムな部分集合が選択される。この場合、出力記号は、これらのソース記号のXORである。これらのソース記号を以下では出力記号の近傍またはアソシエートと呼ぶ。この基本方式の様々な修正態様および拡張態様が可能であり、それらは上述の特許および特許出願で考察されている。
【００１６】
出力記号は、生成された後、予定された受信側に鍵、または鍵をどのように生成するかを示す信号と一緒に送信することができる。いくつかの態様では、たとえば、2001年2月22日に出願された“Scheduling of multiple files for serving on a server”という名称の米国特許出願第09/792,364号に記載されたように、多数の出力記号が1つの送信パケットを構成することができる。
【００１７】
ある用途では、まずソース記号を送信し、次いで出力記号を送信することによって送信を継続することが好ましい場合がある。このような符号化システムを以下ではシステマティック符号化システムと呼ぶ。受信側では、受信器はできるだけ多くの元の入力記号を受信し、受信されなかった入力記号を1つまたは複数の出力記号で置き換え、それらを用いて、失われた入力記号を回復することを試みることができる。出力記号の送信は、プロアクティブに、受信側の明白な要求なしに行うことも、リアクティブに、すなわち、受信側による明示的な要求に応答して行うこともできる。たとえば、紛失がないか、または非常に少ない量の紛失が予想される用途では、まず元の入力記号を送信し、消失が起こった場合に追加的な出力記号を送信すると有利である場合がある。このようにして、紛失が起こらない場合には復号を行う必要はない。他の用途として、ライブ・ビデオ・ストリームを1つまたは複数の受信側に送信する場合を考える。ある程度の紛失が予想される場合、ライブ送信の性質上、受信側は、所定の時間以下の時間の間にのみデータの特定の部分をバッファすることができる。この時間の後に受信される記号の数がデータを完全に再構成するのに十分な数でない場合、ある用途では、データの、それまでに受信されている部分をビデオ・プレーヤに転送すると有利である。ある用途では、適切なソース符号化方法を用いた場合に、ビデオ・プレーヤが品質を落としてデータを再生できる場合がある。一般に、場合によっては部分的に回復されたデータを利用できる用途では、システマティック符号化システムを使用すると有利である場合がある。
【００１８】
システマティック符号化システムを生成する、Luby IまたはRaptorに記載されたチェイン・リアクションコード化システムの態様の簡単な修正態様は、一般に非効率的な結果をもたらす。たとえば、チェイン・リアクションコード化システムにおいて、最初に送信された記号が元の記号を含む場合、元のデータを回復できるようにするために、元の記号と同程度のいくつかの純粋な出力記号を受信することが必要になる場合がある。言い換えれば、元の記号の受信は復号プロセスの最小限の助けにしかならず、したがって、復号プロセスは、受信される他の記号に完全に依存する必要がある。このため、不必要に高い受信オーバヘッドが生じる。
【００１９】
したがって、効率的な符号化アルゴリズムおよび復号アルゴリズムを有し、かつチェイン・リアクションコード化システムと同程度の受信オーバヘッドを有する、チェイン・リアクションコード化システムの体系的な形態が必要である。
【発明の開示】
【００２０】
発明の概要
本発明は、体系的なチェイン・リアクションコード化プロセスおよび復号プロセスを用いてデータを符号化し復号するシステムおよび方法を提供する。これらは、多数の用途、たとえば、データがより高速に、より確実に、かつより少ない計算費用で伝達されるデータ通信システムに用いることができる。
【００２１】
本発明の一態様では、データをチェイン・リアクションコードとして符号化する方法が提供される。まず、データから入力記号の集合が生成される。その後、各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される1つまたは複数の非システマティック出力記号が、入力記号の集合から生成される。この符号化プロセスの結果として、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の集合の任意の部分集合を回復することができる。
【００２２】
本発明の他の態様および特徴は、以下の図面および詳細な説明を検討することによってよりよく理解されよう。
【００２３】
説明を明確にするため、かつ説明の都合上、最初の図面において識別される特徴および構成要素は、以後の図面でもその参照符号を保持する。
【００２４】
例示的な態様の詳細な説明
I．非システマティック・チェイン・リアクション・エンコーダおよびデコーダ
図1Aおよび1Bは、それぞれ、Luby IおよびRaptorに記載された非システマティック・チェイン・リアクション・エンコーダ130およびデコーダ170の例示的な態様を示している。Luby IおよびRaptorではこのように呼ばれていないが、これらの態様を、本明細書では、以下に示すシステマティック・エンコーダおよびデコーダとその構造および動作を区別するために「非システマティック」と呼ぶ。
【００２５】
次に図1Aを参照すると、非システマティック・エンコーダ130は、記号IS(0), IS(1), ...および鍵発生器120によって生成された鍵I0, I1, ...を入力として受け入れる。入力記号の数は、事前に分かっていてもいなくてもよい。いくつかの態様では、非システマティック・エンコーダ130は、各鍵Iごとに出力記号を生成する。図1Aでは、出力は鍵I0, I1, ...に対応するB(I0), B(I1), ...として示されている。生成される出力記号の数は、場合によっては無制限である。鍵発生器120は、鍵を生成する乱数発生器にアクセスすることができる。または、鍵Iを他の何らかの機構によって生成することができる。エンコーダ130は、たとえばRaptorに記載された静的エンコーダおよび動的エンコーダを含んでよい。エンコーダ130は、静的エンコーダを記述するのに用いられる他の鍵発生器にアクセスすることができる。
【００２６】
Luby IおよびRaptorに示されている、入力記号から出力記号を得る様々な方法がある。このような符号化方法のある例示的な態様を図2に示す。この態様は、元の入力記号からの出力記号270の生成を表している。元の入力記号は210(a)〜210(f)として示されている。いくつかの態様では、符号化プロセスの第1の段階は、Raptorに記載されているように静的符号化である。この段階は、220(a)〜220(f)および260(a)〜260(c)として示されているソース記号を生成することができる。いくつかの態様では、静的符号化はシステマティックであってよく、したがって、ソース記号220(a)〜220(f)の値は210(a)〜210(f)の値に等しい。いくつかの態様では静的符号化は行われず、その場合、入力記号はソース記号に一致する。ソース記号は、データ記号が利用可能になってときにオフラインで生成してもオンラインで生成してもよい。
【００２７】
ソース記号が作成された後、ソース記号から出力記号を生成することができる。いくつかの態様では、出力記号の値は、いくつかのソース記号の値のXORである。各出力記号について、鍵発生器120は鍵を生成し、この鍵によって、重みテーブル250から出力記号の重みが求められる。重みWが求められた後、W個のランダム・ソース記号または擬似ランダム・ソース記号が選択され、出力記号の値がこれらのソース記号の値のXORとして算出される。たとえば、図2では、出力記号270の重みは3に等しく、その値は、ソース記号220(a)、220(d)、および260(b)のXORとして求められる。出力記号の重みを本文書では出力記号の次数と呼ぶこともある。ソース記号Sが出力記号Oの値に寄与する場合、SとOを近傍と呼ぶ。たとえば、図2に示されている状況では、出力記号270はソース記号220(a)、220(b)、および220(d)の各々の近傍である。
【００２８】
図1Bのチェイン・リアクション・デコーダの様々な態様がLuby IおよびRaptorに詳しく記載されている。いくつかの態様では、十分な出力記号が収集された直後に復号プロセスが開始する。いくつかの態様では、収集される出力信号の数は、元の入力記号の数よりもわずかに多い。他の態様では、復号プロセスを開始するのに必要な収集される出力信号の数は、元の入力記号の数よりもずっと少ない。
【００２９】
いくつかの態様では、受信された出力信号ごとに、鍵発生器160が記号の対応する鍵を算出し、その鍵から近傍のソース記号を求める。
【００３０】
チェイン・リアクション復号の復号プロセスの態様の1つの可能な説明は、図3に例示されている対応する復号グラフに関して与えることができる。このグラフは、ノードの2つの集合、すなわち、それぞれソース記号および受信出力記号に対応するソース・ノードおよび出力ノードから成る。ソース・ノードはソース記号に対応し、同様に出力ノードは出力記号に対応する。出力ノードは、ソース・ノードに対応するソース記号が出力ノードに対応する出力記号の近傍である場合ソース・ノードに連結されている。この場合、この出力ノードおよびソース・ノードを近傍と呼ぶ。
【００３１】
いくつかの態様では、復号は、次数1の出力ノードO1を識別することによって開始する。次いで、O1の固有の近傍が回復され、復号グラフから除去され、プロセスは、次数1の他の出力ノードO2を識別することによって継続する。たとえば、図3に示されている状況では、O1は、330(a)として示されている出力ノードであってよい。固有の近傍320(b)を復号グラフから除去すると、次数1の他の出力ノード、すなわち330(c)が得られる。このプロセスは、すべてのソース・ノードが回復されるか、または次数1の出力ノードがなくなるまで継続する。
【００３２】
たとえば、図3の状況では、出力ノードの以下のシーケンスを選択して対応するソース・ノードを回復することができる。
【表１】
この例では復号が成功する。
【００３３】
いくつかの態様では、このグラフの解釈を用いて、Luby IまたはRaptorに示されているように、復号に必要な実際の計算のスケジュールをセットアップすることができる。さらに、上述の理想的なデコーダを、上述の特許および特許出願に記載されているように、必要なリソースを減らし、復号プロセスの速度を高めるように様々な点で変更することができる。
【００３４】
いくつかの態様では、デコーダは、対応する入力ノードを回復するのに用いられた出力ノードのシーケンスを出力することができる。たとえば、上記の場合、デコーダは、出力ノード330(a)、330(c)、220(h)、330(d)、330(i)、330(b)、330(j)、330(e)、330(f)、および330(g)に対応する指数を出力することができる。
【００３５】
以下では復号行列と呼ぶ、復号グラフの行列表現、この行列に関する復号アルゴリズムの解釈を考えると有利な場合がある。本発明のいくつかの態様では、復号グラフに対応する復号行列は、出力ノードと同じ数の行と、ソース・ノードと同じ数の列を有し、項目0または1を有する。j番目のソース・ノードがk番目の出力ノードの近傍である場合、復号行列の位置（k,j）には1がある。
【００３６】
図4は、図3の復号グラフの復号行列を示している。当業者に既知のように、復号問題は、復号行列によって与えられる数式の系を解くことに関して表すことができる。Mが復号に対応する復号行列を示し、出力記号の値のベクトルがbで示され、K個のソース・ノードがある場合、未知のソース記号値x1, x2, ..., xKは以下の行列式を満たす。
M・x = b
上式で、xが列ベクトル（x1, x2, .,,, xK）である。チェイン・リアクション復号は、結果として得られる行列が低次三角行列であり、すなわち、行列内の、主対角線の上方の値が0であるようなMの行および列の置換がある場合に成功する。たとえば、行に対して置換（3→2、8→3、2→5、10→6、5→7、6→8、7→9）を行い、列に対して置換（2→1、5→2、8→3、9→4、1→5、3→7、7→8、4→9）を行うことによって、低次三角行列が生成される。行列に関して言えば、このことは、P・M・Qが低次三角行列になるようにチェイン・リアクション復号アルゴリズムが行列PおよびQを生成することを意味する。当業者に知られているように、一次方程式の系を解く様々な方法がある。たとえば、ガウス消去アルゴリズムを使用することが可能である。
【００３７】
復号の行列図は、例示のためにのみ与えられており、制限的なものではない。特に、デコーダの実際の動作は、Luby I、Raptor、および上述の特許出願に記載されているように、前記の考察とは実質的に異なることがある。
【００３８】
いくつかの態様では、Raptorに記載されているように多段チェイン・リアクションコード化システムを使用する場合、使用される特定の静的符号化によって与えられるソース記号間の関係を表す二次グラフによって増補することができる。たとえば、低密度パリティ・チェック符号を静的符号化プロセスに使用する場合、この符号中のチェック記号の数に等しい数の出力ノードを復号グラフに追加し、これらの出力ノードの値を0に設定することができ、ソース・ノードとチェック・ノードとの間の低密度パリティ・チェック符号のグラフによって復号グラフを増補することができ、復号グラフをこの新しいグラフで置き換えることができる。低密度パリティ・チェック符号の選択は、本出願にとって重要ではない。一般に、任意の種類の静的符号化について、対応するパリティ・チェック行列は、復号グラフを増補できる2部グラフを定める。この新しいグラフを以下では修正復号グラフと呼ぶ。
【００３９】
図5は、修正復号グラフを得る手順の例示的な態様である。ソース・ノードは510(a)〜510(f)として示され、出力ノードは520(a)〜520(g)として示され、チェック・ノードは530(a)〜520(d)として示されている。ソース・ノードはソース記号に対応する。出力ノードとソース・ノードとの間のグラフは、出力ノードの近傍構成によって与えられる復号グラフである。チェック・ノードとソース・ノードとの間のグラフは、各ソース・ノード間の関係を表している。たとえば、ノード530(a)は、ソース・ノード510(a)、510(b)、510(e)、および510(f)に対応するソース記号の値のXORが0であることを示している。
【００４０】
修正復号グラフは、ソース・ノードと同じ数の列を有し、出力ノードとチェック・ノードの総計値と同じ数の行を有する、0と1から成る修正復号行列に対応する。これに対応して、修正復号行列は、1つの集合が出力ノードに対応し、1つの集合がチェック・ノードに対応する行の2つの集合から成る。L個の出力ノード、C個のチェック・ノード、およびK個のソース・ノードがある場合、修正復号行列を、L個の行およびK個の列から成る部分行列MOと、C個の行およびK個の列から成る行列MCとに分解することができる。x1, ..., xKがソース記号の未知のベクトルを示し、b1, ..., bLが受信された出力記号の既知の値を示す場合、デコーダのタスクは、MO・x = bおよびMC・x = 0によって与えられる数式の系を解くことであってよい。数式の結合系は、図6に与えられている系である。
【００４１】
チェイン・リアクション・デコーダのいくつかの態様では、非活動化デコーダと呼ばれる異なるデコーダを使用することができる。このデコーダは、”Systems and Process for Decoding a Chain Reaction Code through Inactivation”という名称を有し、参照として本明細書に組み入れられる、同一出願人による同時係属中の米国特許出願第10/459,370号に詳しく記載されており、「非活動化デコーダ」と呼ばれる。
【００４２】
II．システマティック・チェイン・リアクション・エンコーダおよびデコーダならびに動作方法
図7Aは、本発明によるシステマティック・チェイン・リアクションコードを用いてデータを符号化する例示的な方法を示している。本明細書では、語「出力記号」はチェイン・リアクションコードを指し、その例がLuby IおよびRaptorに記載されている。したがって、システマティック出力記号および非システマティック出力記号は、特定の種類のチェイン・リアクションコードであり、システマティック出力記号は送信される入力記号を含み、非システマティック出力記号は、1つまたは複数の入力記号の関数である出力記号を含む。
【００４３】
図7Aの方法は、インタネットを通じたパスや、テレビジョン送信機からテレビジョン受信機までのブロードキャスト・リンクや、ある点から別の点までの電話接続のようなリアルタイム・チャネルなどを介して送信されるデータの符号化のような様々な用途に使用することができ、または通信チャネルは、複数のCD-ROM、ディスク・ドライブ、ウェブ・サイトのような格納チャネルであってもよい。通信チャネルは、場合によっては、ある人が電話回線上でパーソナル・コンピュータからインタネット・サービス・プロバイダ（ISP）に入力ファイルを送信するときに形成されるチャネルのような、リアルタイム・チャネルと格納チャネルとの組合せであってもよく、入力チャネルは、ウェブ・サーバ上に格納され、その後インタネット上で受信側に送信される。
【００４４】
次に図7Aを参照すると、符号化プロセスは702から始まり、入力データの集合が受信され、その入力データから入力記号の集合が生成される。このプロセスの例示的な態様はLuby IおよびRaptorに記載されている。ただし、本発明による他の態様では他の技術を使用することができる。本文献および本明細書で参照されるかまたは参照として本明細書に組み入れられる文献に記載されているように、入力データは、組全体が演繹的に分かるわけではないライブ・データを含め、任意のフォーマットおよび種類のデータであってよい。
【００４５】
次に、入力記号から1つまたは複数の非システマティック式が生成される。このプロセスの特定の態様では、最初入力記号から中間入力記号が生成される（704）。その後、中間入力記号から1つまたは複数の非システマティック出力記号が生成される（706）。本発明による他の態様では、706のプロセスを省略することができ、入力記号から非システマティック出力記号が生成される。これらのプロセスを以下に詳しく示す。
【００４６】
以下に詳しく説明するように、入力記号は、入力データ用の入力記号発生器によって与えられる。上述のように、入力データは、ビデオ捕捉モジュールなどの二次装置からリアルタイムに得られるデータであってよく、また、たとえば、二次用途によって形成されるファイルまたはバッファに入力データが存在するときは、静的データであってよい。本発明の他の用途では、たとえば、ネットワーク・カードなどの二次装置またはアプリケーションからデータを受信し、それを、入力記号発生器によってさらに処理できるように格納装置に格納することによって、リアルタイム方法と静的方法の組合せによってデータを取得することができる。
【００４７】
図7Bは、本発明によるシステマティック・チェイン・リアクションコードを復号する例示的な方法を示している。最初712で、入力記号の第1の部分集合が取得される。このアプリケーションは通常、このプロセスをどのように実現するかを決定する。たとえば、通信システムに用いると、このプロセスは、通信チャネルを介して送信されるチェイン・リアクションコードの入力記号を受信することによって実行される。上述のように、本発明の特定の態様では、通信チャネルはリアルタイム・チャネルであってよく、また、格納チャネル、それらの組合せであってもよい。さらに以下に示す特定の態様では、入力記号の取得は、システマティック出力記号を含む入力記号を受信側に送信することによって行われる。チャネル・ロスが予想されるため、送信される入力記号（すなわち、システマティック出力記号）のいくらかは紛失してもよい。したがって、入力記号の元の集合の部分集合のみを受信側によって取得することができる。
【００４８】
次に714で、1つまたは複数の非システマティック出力記号が取得される。通常、非システマティック出力記号の取得は入力記号と同じ方式に従う。ただし、他の態様では他の手段を使用してよい。
【００４９】
方法は716に進み、取得されなかった1つまたは複数の入力記号が回復される。このプロセスの特定の態様では、失われた入力記号を、非システマティック出力記号、または非システマティック出力記号と取得された入力記号の組合せから回復することができる。
【００５０】
716の回復プロセスは、失われた入力記号のうちの1つ、いくつか、またはすべてを回復するのに用いることができる。所望の数の失われた入力記号が回復された後、それらを、取得された入力記号に付加し、入力記号の元の集合、したがって元のデータのコピーを再形成することができる。
【００５１】
図7Cは、本発明の一態様によるシステマティック符号化および復号を使用する例示的な通信システム700のブロック図である。通信システム700では、入力ファイル721または入力ストリーム725が入力記号発生器726に与えられる。入力記号発生器726は、各々が値および位置（図7では括弧内の整数として示されている）を有する1つまたは複数の入力記号（IS(0), IS(1), IS(2), ...）のシーケンスを入力ファイルまたはストリームから生成する。上述のように、入力記号の可能な値、すなわち、そのアルファベットは通常2M個の記号のアルファベットであり、したがって、各入力記号は入力ファイルのMビットを構成する。Mの値は一般に、通信システム700を用いることによって決定されるが、汎用システムは、用途に応じてMを変えることができるように入力記号発生器726の記号サイズ入力を含んでよい。入力記号発生器726の出力は、システマティック・エンコーダ728に与えられる。
【００５２】
非システマティック鍵発生器727は、エンコーダ728に与えられる入力記号に対応する鍵I0, I1, I2, ...を生成し、これらの非システマティック鍵は、エンコーダ728から出力された非システマティック出力記号B(I0), B(I1), B(I2), ...の値を算出するのに用いられる。各非システマティック鍵I0, I1, I2, ...は、同じ入力ファイルの鍵の大部分が固有の鍵になるように生成される。一態様では、非システマティック鍵発生器727は、上記の図1Aに示されLuby IおよびRaptorに記載されている鍵発生器120を含んでいる。ただし、他の態様では、非システマティック鍵を生成するように動作できる他の種類の装置を使用してよい。
【００５３】
システマティック鍵発生器730は、エンコーダ728に与えられる入力記号に対応し、以下に詳しく説明するように、受信されなかった1つまたは複数の入力記号を回復するのに用いられるシステマティック鍵C0, C1, C2, ...を生成する。システマティック鍵発生器730は、乱数発生器735によって生成された乱数を用いて鍵を生成する。システマティック鍵の生成については以下に詳しく説明する。非システマティック鍵発生器727およびシステマティック鍵発生器730の出力はエンコーダ728に与えられる。
【００５４】
非システマティック鍵発生器727によって非システマティック鍵Iが与えられるたびに、エンコーダ728は、入力記号発生器から与えられた入力記号から、値B(I)を有する非システマティック出力記号を生成する。生成される非システマティック出力記号は、Luby Iに記載されている出力記号（単一段符号化／復号）であっても、Raptorに記載されている出力記号（多段符号化／復号）であってもよい。例示的なシステマティック・エンコーダ728の動作については以下に詳しく説明する。各出力記号の値は、その鍵および1つまたは複数の入力記号のある関数に基づいて生成される。
【００５５】
いくつかの態様では、入力記号の数Kは、アソシエートを選択するためにシステマティック・エンコーダ728によって使用される。入力がストリーミング・ファイルである場合のようにKが既知でない場合、Kは単なる推定値であってよい。値Kはまた、入力記号およびシステマティック・エンコーダ728によって生成された中心記号の記憶域を割り当てるためにシステマティック・エンコーダ728によって使用される。
【００５６】
システマティック・エンコーダ728は、入力記号IS(0), IS(1), ...をシステマティック鍵C0, C1, ..., CK-1またはシステマティック鍵を再生するにはどうするか関する指示と一緒に送信モジュール740に転送する。送信された記号IS(0), IS(1), ...を本明細書では「システマティック出力記号」と呼ぶ。システマティック・エンコーダ728は、入力記号を送信モジュールに転送する前に、他の出力記号を生成するための入力記号のコピーを作成することができる。
【００５７】
システマティック・エンコーダ728はまた、非システマティック出力記号B(I0), B(I1), B(I2), ...を送信モジュール740に与える。送信モジュール740には、非システマティック鍵発生器727からそのような各出力記号ごとの非システマティック鍵（I0, I1, I2, ...）も与えられる。送信モジュール740は、システマティック出力記号および非システマティック出力記号を送信し、かつ使用される鍵生成方法に応じて、送信される出力記号の鍵に関するあるデータをチャネル745上で受信モジュール750に送信することもできる。チャネル745は消失チャネルと仮定されるが、通信システム700を適切に動作させるための要件ではない。モジュール740、745、および750は、送信モジュール740が出力記号およびその鍵に関する任意の必要なデータをチャネル745に送信するようになっており、受信器モジュール750が記号および場合によってはその鍵に関するある種のデータをチャネル745から受信するようになっているかぎり、任意の適切なハードウェア構成要素、ソフトウェア構成要素、物理媒体、またはそれらの組合せであってよい。Kの値は、アソシエートを判定するのに用いる場合にはチャネル745上で送信することができ、また、エンコーダ728とデコーダ755との合意によって事前に送信しておいてもよい。
【００５８】
上述のように、チャネル745は、インタネットを通じたパスや、テレビジョン送信機からテレビジョン受信機までのブロードキャスト・リンクや、ある点から別の点までの電話接続のようなリアルタイム・チャネルであってよく、また、チャネル745は、CD-ROM、ディスク・ドライブ、ウェブ・サイトのような格納チャネルであってもよい。チャネル745は、場合によっては、ある人が電話回線上でパーソナル・コンピュータからインタネット・サービス・プロバイダ（ISP）に入力ファイルを送信するときに形成されるチャネルのような、リアルタイム・チャネルと格納チャネルとの組合せであってもよく、入力チャネルは、ウェブ・サーバ上に格納され、その後インタネット上で受信側に送信される。
【００５９】
受信モジュール750は、それがデコーダ755に供給するチャネル745から非システマティック出力記号および／またはシステマティック出力記号を受信する。受信された出力記号の鍵に対応するデータは非システマティック鍵再生器760およびシステマティック鍵再生器780に与えられる。図7に示されている態様では、IS(x), IS(y), ..., IS(z)によって示されるシステマティック出力記号の集合が非システマティック出力記号の集合B(Ia), B(Ib), B(Ic), ...と一緒に受信される。他の態様では、受信モジュール750は、システマティック出力記号のみ、またはシステマティック出力記号と非システマティック出力記号の組合せを受信することができる。
【００６０】
非システマティック鍵再生器760は、受信された非システマティック出力記号の非システマティック鍵を再生し、これらの鍵をシステマティック・デコーダ755に与える。一態様では、非システマティック鍵再生器760は、上記の図1Bに示されLuby IおよびRaptorに記載されている鍵再生器160を含んでいる。ただし、他の態様では、非システマティック鍵を再生するように動作できる他の種類の装置を使用してよい。システマティック鍵再生器180は、システマティック鍵C0, C1, ...を再生し、それらをシステマティック・デコーダ755に与える。システマティック鍵再生器780は、システマティック鍵の再生を容易にするシステマティック鍵発生器730とのある共用情報にアクセスすることができる。または、システマティック鍵再生器780は、チャネル745を通じて送信された追加的な情報に基づいて鍵を再生することができる。いくつかの態様では、システマティック鍵再生器780は、システマティック鍵を生成するのに用いることのできるのと同じ乱数発生器735にアクセスすることができる。これは、乱数がある物理的装置上で生成される場合にこの物理的装置へのアクセスの形であっても、同一の振る舞いを実現するように乱数を生成するのと同じアルゴリズムへのアクセスの形であってもよい。
【００６１】
デコーダ755は、非システマティック鍵再生器760およびシステマティック鍵発生器780から与えられた非システマティック鍵を対応する出力記号と一緒に用いて、入力記号（この場合もIS(0), IS(1), IS(2), ...）を回復する。回復された入力記号は入力ファイルリアセンブラ765に転送される。システマティック・デコーダ755は、残りの入力記号を回復する前に、受信されたシステマティック出力記号IS(x), IS(y), ..., IS(z)を直接入力ファイル・リアセンブラ765に転送することができる。特に、すべての入力記号が受信された場合、デコーダは、それ以上の計算なしに、受信されたデータを入力ファイル・リアセンブラ765に転送することを選択することができる。入力ファイル・リアセンブラ765は、入力ファイル721または入力ストリーム725のコピー770を生成する。
【００６２】
以下に、システマティック・エンコーダ728およびデコーダ755の動作について詳しく説明する。本発明のいくつかの態様では、これらのユニットは、上述のようにチェイン・リアクションコード化および復号を使用することができる。
【００６３】
図8Aは、本発明の特定の態様におけるシステマティック・エンコーダ728の動作を示している。まず、システマティック・エンコーダ728は、図7の入力記号発生器726から入力記号IS(0), IS(1), ,,,, IS(K-1)を受信する。入力記号は、符号化の開始時にその全体が分かっても、部分的にのみ分かってもよい。
【００６４】
この態様では、システマティック・エンコーダ728は、生成された非システマティック出力記号と同じ数の非システマティック鍵I0, I1, ...を生成する非システマティック鍵発生器727にアクセスすることができる。さらに、システマティック鍵発生器730は、入力記号と同じ数のシステマティック鍵C0, C1, ...CK-1を生成する。システマティック・エンコーダ728は、元の入力記号を送信モジュール750に渡し、これらの記号はシステマティック出力記号として送信される。システマティック・エンコーダ728は、非システマティック鍵発生器727によって生成された各鍵I0, I1, ...ごとに非システマティック出力記号B(I0), B(I1), ...を生成するように動作する。システマティック鍵発生器730の動作について以下に詳しく説明する。
【００６５】
システマティック鍵発生器730およびシステマティック鍵発生器780（図7）は、システマティック鍵再生器780が首尾よくシステマティック鍵発生器730と同じ鍵を生成できるようにある種の共用情報にアクセスすることができる。いくつかの態様では、この共用情報は、システマティック鍵再生器780に送信することができる。他の態様では、システマティック鍵は、符号の他のパラメータ、たとえば入力記号の数や重みテーブルの確定的関数であってよい。
【００６６】
いくつかの態様では、システマティック鍵は、入力記号の数のいくつかまたはすべての関連する値について事前に算出しておくことができる。いくつかの態様では、システマティック鍵を入力記号の異なるいくつかの集合に再使用してよい。他の態様では、システマティック鍵発生器730とシステマティック鍵発生器780とのある種の共用情報を用いて、あらゆる入力ブロックについてシステマティック鍵を再計算することができる。
【００６７】
図8Bは、本発明の特定の態様におけるシステマティック・デコーダ755の動作を示している。システマティック・デコーダ755は、それぞれIS(x), IS(y), ..., IS(z)およびB(Ia), B(Ib), ...として示されているシステマティック出力記号を受信モジュール750から受信する。特定の態様では、システマティック・デコーダ755は、システマティック鍵再生器780および非システマティック鍵再生器760にアクセスすることができる。システマティック・チェイン・リアクション・デコーダの出力は、初期入力記号の集合IS(0), IS(1), ..., IS(K-1)である。
【００６８】
図9Aは、システマティック・エンコーダ728を詳しく示している。システマティック・エンコーダ728は、チェイン・リアクション・デコーダ910およびチェイン・リアクション・エンコーダ920を含んでいる。さらに、システマティック・エンコーダ728は、メモリ装置（図示せず）にアクセスし、中間記号S(0), S(1), ..., S(K-1)を格納することができる。
【００６９】
チェイン・リアクション・デコーダ910は、入力記号IS(0), IS(1), ..., IS(K-1)およびシステマティック鍵C0, C1, ..., CK-1を受信すると、たとえば、本明細書に組み入れられている特許および特許出願に記載されているチェイン・リアクションコード化符号の復号方法を用いて、中間入力記号の集合S(0), S(1), ..., S(K-1)を算出する。本発明のいくつかの態様では、中間入力記号をメモリまたはディスク上に格納することができる。他の態様では、中間入力記号を、利用可能になってときにチェイン・リアクション・エンコーダ920に転送することができる。
【００７０】
チェイン・リアクション・エンコーダ920は、チェイン・リアクション・デコーダ910によって生成された中間入力記号を、非システマティック鍵再生器727によって生成された非システマティック鍵I0, I1, I2, ...と一緒に用いて非システマティック出力記号B(I0), B(I1), ...を生成する。いくつかの態様では、この符号化プロセスは、Luby IまたはRaptorに記載されている入力記号符号化プロセスを用いて、本発明の中間入力記号がLuby Iの入力記号として使用される修正を施して実現することができる。特定の態様では、非システマティック出力記号は、入力記号IS(0), IS(1), ..., IS(K-1)の後で送信モジュール140に供給される。しかし、このことは本発明の機能にとって重要ではない。さらに、送信モジュール740からの送信順序も変えることができる。
【００７１】
図9Bは、チェイン・リアクション・デコーダ930およびチェイン・リアクション・エンコーダ940を含むシステマティック・デコーダ755の例示的な態様である。システマティック・デコーダへの入力は、いくつかが受信されたシステマティック出力記号IS(x), IS(y), IS(z), ...を含み、いくつかが受信された非システマティック出力記号B(Ia), B(Ib), ...を含む受信された出力記号を含む。いくつかの態様では、デコーダは、受信されたシステマティック記号をメモリ装置にコピーし、それらを入力ファイル・リアセンブラ765に直接転送することができる。
【００７２】
チェイン・リアクション・デコーダ930は、記号IS(x), IS(y), ..., IS(z), B(Ia), B(Ib), ...、システマティック鍵再生器780によって生成されたシステマティック鍵Cx, Cy, ...Cz、非システマティック鍵再生器760によって生成された非システマティック鍵Ia, Ib, ...を用いて中間入力記号S(0), S(1), ..., S(K-1)を生成する。システマティック鍵Cx, Cy, ..., Czは、受信された入力記号IS(x), IS(y), ..., IS(z)に相当する。いくつかの態様では、回復された中間記号は、チェイン・リアクション・エンコーダ440に渡す前に二次記憶域に格納しておくことができる。他の態様では、これらの中間記号を直接チェイン・リアクション・エンコーダ940に渡すことができる。
【００７３】
チェイン・リアクション・エンコーダ940は、中間入力記号、および消失したシステマティック出力記号IS(u), IS(v), ..., IS(w)に対応するシステマティック鍵Cu, Cv, ..., Cwを用いて、失われた元の入力記号IS(u), IS(v), ..., IS(w)を出力する。例示的な態様として、各初期鍵Cu, Cv, ..., Cwについて、デコーダは、重みWおよび中間入力記号S(0), ..., S(K-1)のうちのW個の記号を識別し、各出力記号の値をXORし、システマティック鍵Cu, Cv, ..., Cwに対応する消失した入力記号IS(u), IS(v), ..., IS(w)を得る。チェイン・リアクション・エンコーダ940によって使用される計算リソースの量は、一態様では、消失するシステマティック出力記号の数に比例する。たとえば、すべての出力記号が受信された場合、デコーダは計算を実行せず、受信された記号を入力ファイル・リアセンブラ765に転送する。
【００７４】
特定の態様では、静的符号化を用いる場合、チェイン・リアクション・エンコーダ940とチェイン・リアクション・デコーダ910は、同じ重みテーブルにアクセスし、同じ静的符号化／復号を使用する。同様に、チェイン・リアクション・エンコーダ920とチェイン・リアクション・デコーダ930は、同じ重みテーブルにアクセスし、同じ静的符号化／復号を使用することができる。
【００７５】
システマティック鍵を算出する方法
本発明の特定の態様では、システマティック鍵は、記号送信の前にシステマティック鍵発生器730によって算出され、記号受信後にシステマティック鍵再生器780によって再計算される。システマティック鍵は、中間入力記号S(0), S(1), ... S(K-1)を得るために、チェイン・リアクション・デコーダ910およびエンコーダ930によって使用される。
【００７６】
本発明の特定の態様では、システマティック鍵は、K個の記号の固有の効率的なチェイン・リアクション復号が、これらの鍵によって生成されたK個の出力記号のみを用いて可能になるように算出される。ここで、復号は、Luby I、Raptor、もしくはInactivation Decodingに記載された復号方法のいずれか、またはたとえばInactivation Decodingに記載されたガウス消去アルゴリズムに基づくより一般的な復号方法のいずれかであってよい。
【００７７】
図10は、システマティック鍵生成プロセスの例示的な態様である。システマティック鍵発生器への1つの入力は、入力記号IS(0), IS(1), ..., IS(K-1)の数Kであってよい。システマティック鍵生成は、変数jを0に等しく設定することによって始まる。アルゴリズムの間、K個の列を持つ行列Mは、最初0個の列を有し、アルゴリズムが進行するにつれて行を追加することによって更新される。jのあらゆる異なる値について、アルゴリズムは、1020で異なる鍵D(j)を生成する。この鍵は、Luby IまたはRaptorに記載されている方法によって生成することができ、図1に示されている乱数発生器135を使用することができる。次に1030で、鍵D(j)を用いて行列Mのj番目の行の項目が算出される。このような計算の1つの可能な態様では、チェイン・リアクションコード化プロセスにおいて鍵D(j)が使用される。この場合、鍵D(j)は、重みテーブルを用いて、重みWおよび値0, 1, ..., K-1のうちのW個の値を識別する。鍵D(j)は次いで、Mのj番目の行の位置mに、mが、生成されたランダム値または擬似ランダム値の一方である場合に1を設定し、j番目の行の他の値を0に設定する。
【００７８】
1040で、現在構成されている行列Mが、整数2法として掛け算および足し算が実行される0および1から成る集合を指すバイナリ・フィールドGF(2)上で線形に独立したK個の行を有するかどうかが判定される。1040のこのプロセスは、様々な方法で実行することができる。たとえば、バイナリ・フィールドGF(2)上のガウス消去を用いてこれをチェックすることができる。しかし、当業者に既知の他の多数の方法がある。たとえば、非活動化復号の教示を行列Mに適用する場合、Mは、Mに適用される非活動化デコーダがうまく動作する場合にのみK個の線形に独立した行を含む。
【００７９】
1040の試験が肯定的であり、Mの行r(0), r(1), ..., r(K-1)が線形に独立していることが分かった場合、システマティック鍵C0, C1, ..., CK-1は鍵D(r(0)), ..., D(r(K-1))に設定され、これらの鍵が出力される。1040の試験が否定的である場合、1060でカウンタjが増分され、1020から計算が繰り返される。
【００８０】
当業者によって、システマティック鍵を生成する他の同等のまたは実質的に同様の方法を構想することができる。たとえば、アルゴリズムの実行中に鍵D(j)を一度に1つずつ生成するのではなく、L個のそのような鍵の集合を事前に生成しておき、アルゴリズムの段階jでこの一群の鍵から鍵D(j)を取り出すことができる。ここで、Lは入力記号の数の関数であってよい。
【００８１】
システマティック鍵を生成する第2の方法が図11に例示されている。この方法では、このアルゴリズムへの入力は、K個の入力記号と、通常K以上である数Lとから成る。いくつかの態様では、Lは、Luby IまたはRaptorに記載されているように、復号が成功することを高い確率で保証するために収集すべき出力記号の数であってよい。
【００８２】
1110で、L個の鍵D(0), ..., D(L-1)が生成される。このプロセスは、乱数発生器735を用いることによって行うことができる。他の態様では、これらの鍵を再使用可能な鍵の一定のリストから生成することができる。このプロセスは、鍵がどのように生成されたかを示すこともできる。たとえば、乱数発生器を使用する場合、発生器のシードを、将来システマティック鍵再生器によって使用できるように記録することができる。
【００８３】
鍵D(0), D(1), ..., D(L-1)を用いて、上記に説明し図5に例示されているように修正復号グラフが1120でセットアップされる。このプロセスは、符号の特定の重みテーブルの知識を使用すると共に、Raptorに記載されているように、使用される静的符号化の知識を使用することができる。
【００８４】
1130で、すでに示されている方法のいずれかを用いて修正復号グラフが復号される。復号の副産物として、入力ノードの回復をトリガする出力ノードの指数r(0), r(1), ..., r(K-1)が記録される。1140で、システマティック鍵がC0=D(r(0)), ..., CK=D(r(K-1))として出力される。
【００８５】
図12は、システマティック鍵を算出する第3の方法を示している。図11の方法と同様に、1210で鍵D(0), ..., D(L-1)が生成され、これらの鍵、および場合によっては重みテーブルを用いて復号グラフがセットアップされる。次に、1230で、集合Sが空集合として初期設定される。集合Sは、入力ノードの値を回復するためにチェイン・リアクション復号プロセスで使用される出力記号の指数を含む。1240で、次数1の出力ノードを識別することによってチェイン・リアクション復号プロセスが復号グラフに適用される。この出力ノードの指数は、この集合の上述の役割に従って集合Sに追加される。1250で、集合Sがすでに正しい数の要素を有しているかどうかについての試験が行われる。正しい数の要素を有していない場合、アルゴリズムは1240に戻り、次数1の他の入力ノードが選択され、復号プロセスが継続される。SのサイズがKである場合、1260で、Sの要素が最小の要素からソートされてソート済み要素S0, ..., SK-1が得られ、システマティック鍵がC0=D(S0), ..., CK-1=D(SK-1)として算出される。
【００８６】
図13は、本発明によるシステマティック鍵を算出する第4の方法を示している。この方法では、入力Kおよび鍵の集合に対して、鍵の所与の集合から元のK個の記号を復号できるかどうかを判定できる復号アルゴリズムが利用可能であると仮定される。このようなアルゴリズムの例は、Luby I、Raptor、またはInactivation Decodingに記載されたデコーダによって与えられる。
【００８７】
1310では、L個の鍵D(0), ..., D(L-1)が生成される。上記の説明と同様に、このプロセスは、乱数発生器735を用いることによって行うことができ、または一定の再使用可能な鍵から鍵を生成することができる。1315で、デコーダを用いて、鍵の集合D(0), ..., D(L-1)からK個の記号を復号することが可能かどうかが判定される。復号が成功しない場合、鍵の所与の集合はシステマティック鍵を部分集合として含んでおらず、アルゴリズムは1325でアボートする。他の場合には、3つの集合は1330で初期設定される。これらの集合をそれぞれ、Systematic（システマティック）、Non_Systematic（非システマティック）、およびUnvisited（未アクセス）と呼ぶ。アルゴリズムの終了時に、集合Systematicは、システマティック鍵の集合を含む。最初、1330で、SystematicおよびNon_Systematicは空の集合に初期設定され、一方、Unvisitedはすべての元の鍵D(0), ..., D(L-1)を含む。プロセス1335から1360で、集合Unvisitedから鍵が取り出され、集合SystematicおよびUnvisitedに含まれる鍵に対して復号が試みられる。試みが成功した場合、選択された鍵Cはシステマティック鍵の集合に属していない。これに対して、復号が成功しなかった場合、鍵はシステマティック鍵の集合に属している。未アクセス鍵の取出しおよび復号（1335）、復号が成功したかどうかの試験（1340）、ならびにその後行われる、デコーダの結果に基づく集合SystematicまたはNon_Systematicへの選択された鍵の追加（1345および1350）から成るこの手順は、集合Systematicが元の入力記号の数Kよりも少ない入力記号を有するかぎり繰り返される。
【００８８】
図14は、本発明によるシステマティック記号および非システマティック記号を有するチェイン・リアクションコードを復号する方法を示している。1410で、受信された非システマティック出力記号B(Ia), B(Ib), ...に対応する非システマティックIa, Ib, ...を用いて、受信された非システマティック出力記号と同じ数の行および入力記号と同じ数の列を有する行列Bが生成される。各鍵ごとに、チェイン・リアクションコードを符号化する場合と同じ機構を用いて、重みW、および鍵に対応する出力記号が生成される入力記号の指数の集合J1, J2, ..., JWが生成される。次いで、行列Bの対応する行で、J1, J2, ..., JWに対応する位置が1に設定され、一方、その行の他の位置が0に設定される。この手順は、受信された非システマティック記号に対応するすべての鍵が無くなるまで繰り返される。
【００８９】
次に1420で、同様の手順が適用され、システマティック鍵C0, C1, ..., CK-1から得た入力記号と同じ数の行および列を有する正方行列Cが作成される。このプロセスでは、Aと呼ばれる行列Cの逆数も算出される。Aの逆数の計算は、当業者に知られているように様々な方法で行うことができる。たとえば、ガウス消去アルゴリズムを用いてAを算出することができる。他の態様では、ある形態のチェイン・リアクション復号を利用してこの段階を実行することができる。このことは、本開示の以下の例に示す。
【００９０】
1430で、バイナリ・フィールドGF(2)上で行列BおよびAの積が算出され、行列Hが得られる。次に1440で、指数の2つの集合EおよびRが求められる。Eは受信されなかったシステマティック記号の指数の集合であり、一方、Rは受信されたシステマティック記号の指数の集合である。たとえば、指数0, 1, 2, ..., 10を有する11個の入力記号があると仮定する。送信後に、指数0, 3, 9, 10に対応するシステマティック記号が受信された場合、R={0, 3, 9, 10}になり、一方E={1, 2, 4, 5, 6, 7, 8}になる。次いで、1430でBとAの積として算出された行列Hが2つの部分行列HEおよびHRに細分される。HEは、受信されなかったシステマティック記号の指数に対応するHの列を取り出すことによって得られたHの部分行列であり、HRは、受信されたシステマティック記号の指数に対応するHの部分行列である。上記の例では、HEは、Hの列1, 2, 3, 4, 5, 6, 7および8によって形成されるHの部分行列である。
【００９１】
1450で、行列HRに、受信されたシステマティック記号IS(x), IS(y), ..., IS(z)で形成されるベクトルが掛け算される。たとえば、上記の場合、HRにシステマティック記号0, 3, 9, 10（この順序で）の値が掛け算される。実際の掛け算は、当業者に既知のように様々な方法で行うことができる。この掛け算の結果は、以下ではベクトルyと呼ばれ、将来使用できるように格納することができる。1460で、受信された非システマティック出力記号を用いてベクトルbがセットアップされる。L個のそのような記号がある場合、ベクトルb内の項目の数はLである。この段階は単なる論理的な段階であってよい。言い換えれば、この段階では計算は必要とされない。次に、ベクトルyに格納されている前の掛け算の結果は、構成要素ごとにベクトルbの項目とXORされ、すなわち、受信された各非システマティック出力記号は、ベクトルyの対応する記号とXORされる。この演算の結果は、受信された非システマティック記号の代わりに格納することも、異なる位置に格納することもできる。
【００９２】
このXORが求められた後、消失したシステマティック記号に対応する行列HEを用いて一次方程式の系がセットアップされる。ここで、系HE*x=y+bの解xは、消失したシステマティック記号の値に相当する。この場合も、このプロセスは、様々な方法で行うことができ、たとえば、ガウス消去や、Luby I、Raptor、またはInactivation Decodingに開示されたチェイン・リアクション復号の変形形態のいずれかを用いて行うことができる。
【００９３】
復号についてのこの行列図は、例示のためのみのものであり、制限的なものではない。本開示を検討すれば、当業者には復号手順の多数の変形態様が明らかになろう。
【００９４】
III．例示的なシステマティック符号化および復号
次に、図15〜17を参照して、システマティック・チェイン・リアクションコード化システムのいくつかの態様の動作のいくつかの局面の簡単な例を示す。与えられるすべての例において、重みテーブルの効果は、所与の記号の鍵を仮定した場合の所与の記号の近傍のリストに関して暗黙的に述べられるに過ぎない。
【００９５】
システマティック鍵の計算
図15Aは、システマティック鍵C0, C1, ..., C8を得るのに用いられる復号グラフを表している。たとえば図11の1110の演算によって12個の鍵D(0), D(1), ..., D(11)がすでに生成されていると仮定される。図15Aのグラフは、鍵D(0), ..., D(11)を用いた、1520(a), ..., 1520(i)として示されている入力ノードと1530(a), ..., 1530(l)として示されている出力ノードとの修正復号グラフを表している。次に、このグラフにチェイン・リアクション復号を適用して、チェイン・リアクション復号の実行時に入力ノードの回復をトリガする出力ノードの鍵としてシステマティック鍵が得られる。
【００９６】
動作時には、ノード1530(a)を用いて入力ノード1520(b)を回復することができる。したがって、この場合、第1のシステマティック鍵C0は、生成された鍵のうちの第1の鍵、すなわち、D(0)に等しい。入力ノード1520(b)が回復すると、出力ノード1530(c)は次数1のノードになり、したがって、ノード1520(e)の回復をトリガする。このような動作を継続することによって、図15Aで明るい灰色に示されているノードを用いて入力ノードを回復できることが分かる。入力ノードを回復するのに用いられる出力ノードのシーケンスは、1530(a), 1530(b), 1530(c), 1530(d), 1530(e), 1530(f), 1530(g), 1530(h), 1530(j)に等しい。その結果、システマティック鍵のシーケンスを図15Bに示されているように選択することができる。
【００９７】
図示のチェイン・リアクション復号の回復プロセスが概念的なものに過ぎないことに留意されたい。特に、この特定の例ではXOR演算は実行されない。
【００９８】
システマティック符号化
図9Aに概略的に示されているように、システマティック・チェイン・リアクション・エンコーダは、チェイン・リアクション・デコーダ910およびチェイン・リアクション・エンコーダ920から成っている。したがって、システマティック・チェイン・リアクションコード化の演算は2つの部分に分割される。この2つの部分はそれぞれ、図16Aおよび図16Bに例示されている。
【００９９】
図16Bは、チェイン・リアクション・デコーダ910の動作を例示している。入力記号はIS(0), ..., IS(8)として示されている。鍵C0, C1, ..., C8を用いて入力記号と中間入力記号S(0), ..., S(8)との間の図形上の依存性がセットアップされる。たとえば、鍵C0は、IS(0)がS(1)の値に等しいことを示し、一方、鍵C4は、S(2)、 S(5)、およびS(7)の値のSORに等しいことを示している。ここで、チェイン・リアクション復号を適用して値S(0), S(1), ..., S(8)を得ることができる。これらの値を得るためのスケジュールは、図7でシステマティック鍵発生器730からチェイン・リアクション・デコーダ910に転送しておくことができる。これは、このスケジュールが鍵C0, C1, ..., C8を得るようにセットアップされているからである。システマティック鍵発生器の動作とは異なり、この段階では、個々の記号の値のXORを使用してよい。
【０１００】
図16Aの例では、スケジュールはまずS(1)の値を生成し、それによって、IS(1)の値を用いてS(4)の値を生成することができる。これによって、S(0)、S(7)などの値の回復がトリガされる。
【０１０１】
図16Bは、最初の11個の非システマティック出力記号O(0), ..., O(10)の生成を示すことによって図9Aのチェイン・リアクション・エンコーダ920の動作を例示している。（図示の出力記号O(i)は前述の出力記号B(Ii)を指す）。前述のように、システマティック・エンコーダの出力は、システマティック出力記号IS(0), ..., IS(8)と、その後に続く出力記号O(0), ..., O(10), ...とから成っている。この特定の順序は例示的なものであり、本発明による他の態様では他の順序を使用することができる。
【０１０２】
システマティック復号
図17Aおよび17Bは、システマティック・チェイン・リアクション復号のプロセスの態様を例示している。受信されたシステマティック出力記号がIS(6)およびIS(7)であり、一方、受信された非システマティック出力記号がO(0)、O(3)、O(4)、O(6)、O(7)、O(8)、O(9)、およびO(10)であると仮定する。デコーダのタスクは、失われたシステマティック出力記号の値、すなわち、値IS(0)、IS(2)、IS(3)、IS(4)、IS(5)、およびIS(8)を算出することである。図17Aは、図9Bにおけるチェイン・リアクション・デコーダ930およびチェイン・リアクション・エンコーダ940を1つのデコーダとして組み合わせるにはどうしたらよいかの例を示している。いくつかの用途では、このような組合せによって計算を節約することができる。
【０１０３】
受信されたシステマティック出力記号に対応する鍵C1、C6、およびC7、ならびに受信された非システマティック出力記号に対応する鍵を用いて、受信された出力記号と中間入力記号S(0), ..., S(8)とのグラフがセットアップされる。出力記号と、XORされると出力記号の値を与えるすべての中間入力記号との間に接続線が描かれる。個々の接続は、図16Aおよび16Bに示されている接続と同じである。受信された出力記号の特定の順序は、復号グラフを表すように選択された順序に等しくなくてよい。
【０１０４】
このグラフは、消失したシステマティック出力記号に対応するノードの他のレイヤによって拡張される。このグラフは、入力記号IS(0)、IS(2)、IS(3)、IS(4)、IS(5)、およびIS(8)が、それらがXORとなる中間入力記号に点線を介して接続される図17Aの上部に対応する。この場合も、これらの接続は、図17Aにおける対応する接続に対して検証することができる。
【０１０５】
この特定の例における復号プロセスは、下方のグラフにチェイン・リアクション復号を適用することによって始めることができる。1つの中間記号が回復されるたびに、その値を、図の上部における受信されなかった元の記号のうちのこの記号のすべての近傍の値とXORすることができる。最初、これらの記号の値を0に設定することができる。
【０１０６】
たとえば、出力記号O(4)を用いてS(3)の値を回復することができる。次いで、S(3)の値をIS(5)の現在の値にXORすることができる。この段階の後で、IS(5)の値はS(3)の値に等しくなる。S(3)を回復すると、出力ノードO(10)の次数は0に下がる。この出力ノードは中間記号S(6)の値を回復する。この値はIS(5)の現在の値にXORされ、したがって、この段階の後IS(5)の値が回復される。このプロセスは、受信されなかったすべてのシステマティック入力記号が回復されるまで継続することができる。
【０１０７】
図17Bは、失われた出力記号を回復するプロセスを示している。回復された記号は長方形に囲まれている。回復されたシステマティック出力記号は灰色の長方形に囲まれている。この図における各縁部のラベルは、回復に使用される記号を表している。
【０１０８】
たとえば、記号O(4)は、S(3)を回復するのに用いられる。記号O(10)はS(6)を回復するのに用いられる。S(3)およびS(6)はS(5)を回復するのに用いられる。S(6)を回復すると（O(9)を用いて）S(8)の回復がトリガされると共に、（受信されたシステマティック出力記号IS(7)を用いて）S(0)の回復がトリガされる。S(8)を回復するとIS(3)の回復がトリガされる。S(0)を回復すると、（IS(1)を用いて）S(4)の回復がトリガされる。一方、S(8)を回復すると、O(0)を用いて、S(1)の回復がトリガされ、S(1)はS(4)と一緒にIS(2)を回復する。さらに、S(1)を回復するとIS(0)が回復される。なぜなら、これらの値が同一であるからである。O(8)およびS(4)の回復された値を用いて、S(5)の値が得られる。これによって、IS(8)の値が回復される。というのは、IS(8)が、S(5)、S(4)、およびS(0)のXORであり、すべてのこれらの値がこの段階で既知であるからである。IS(6)およびS(4)を用いて、S(7)の値が得られる。これによって、O(7)の値を用いてS(2)の値が回復される。S(2)は、S(7)と一緒に、最後の残りの入力記号、すなわちIS(4)の値を回復する。
【０１０９】
上記の説明は、例示および説明のために与えられている。この説明は、網羅的なものでも、本発明を開示された厳密な形態に制限するものでもなく、上記の教示を考慮して多数の修正態様および変形態様が可能であることは自明である。上述の態様は、本発明の原則およびその実際的な適用を最もうまく説明し、それによって、当業者が、様々な態様、および考えられる特定の用途に適した様々な修正態様で本発明を最もうまく利用することができるように選択されている。本発明の範囲は特許請求の範囲によって定義されるものである。
【０１１０】
参照として本明細書に組み入れられる文書
“Information Additive Code Generator and Decoder for Communication Sysmtes”という名称のMichel G. Lubyの米国特許第6,307,487号（本明細書ではLuby Iと呼ぶ）
2001年2月22日に出願され、“Scheduling of Multiple Files for Serving on a Server”という名称を有する米国特許出願第09/792,364号
2001年12月21日に出願され、“Multi-Stage Code Generator and Decoder for Communication Systems”という名称を有する米国特許出願第10/032,156号（本明細書では「Raptor」と呼ぶ）
2003年6月10日に出願され、“Systems and Processes for Decoding Chain Reaction Codes through Inactivation”という名称を有する米国特許出願第10/459,370号（本明細書では「Inactivation Decoding」と呼ぶ）
【図面の簡単な説明】
【０１１１】
【図１Ａ】非システマティックチェイン・リアクション・エンコーダの例示的な態様を示す図である。
【図１Ｂ】非システマティックチェイン・リアクション・デコーダの例示的な態様を示す図である。
【図２】チェイン・リアクション復号プロセスに用いられる元の入力記号からの出力記号の生成を示す図である。
【図３】チェイン・リアクション復号プロセスに用いられる例示的な復号グラフを示す図である。
【図４】図3に示されている復号プロセスの復号行列を示す図である。
【図５】チェイン・リアクション復号プロセスに用いられる修正復号グラフを得る例示的な手順を示す図である。
【図６】チェイン・リアクション復号プロセスに用いられる修正復号式を示す図である。
【図７Ａ】本発明によるシステマティック・チェイン・リアクションコードを用いてデータを符号化する例示的な方法を示す図である。
【図７Ｂ】本発明によるシステマティック・チェイン・リアクションコードを復号する例示的な方法を示す図である。
【図７Ｃ】本発明の一態様によるシステマティック符号化および復号を用いた通信システムのブロック図である。
【図８Ａ】本発明の一態様によるシステマティック・エンコーダの動作を示す図である。
【図８Ｂ】本発明による一態様によるシステマティック・デコーダの動作を示す図である。
【図９Ａ】本発明によるシステマティック・エンコーダの一態様を示す図である。
【図９Ｂ】本発明によるシステマティック・デコーダの一態様を示す図である。
【図１０】本発明によるシステマティック鍵を生成する一方法を示す図である。
【図１１】本発明によるシステマティック鍵を生成する第2の方法を示す図である
【図１２】本発明によるシステマティック鍵を生成する第3の方法を示す図である。
【図１３】本発明によるシステマティック鍵を生成する第4の方法を示す図である。
【図１４】本発明によるシステマティック記号および非システマティック記号を有するチェイン・リアクションコードを復号する方法を示す図である。
【図１５Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１５Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１６Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１６Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１７Ａ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【図１７Ｂ】本発明の例示的な態様における符号化プロセスおよび復号プロセスを示す図である。
【特許請求の範囲】
【請求項１】
以下の段階を含む、データを、システマティック出力記号および非システマティック出力記号を有するチェイン・リアクションコードに符号化する方法であって、
入力記号の集合の任意の一部は、(i)所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の一部に含まれていない入力記号と（b）1つ以上の非システマティック出力記号との組合せから回復可能である方法：
システマティック出力記号を含む入力記号の集合をデータから生成する段階；および
1つ以上の非システマティック出力記号を、入力記号の集合から生成する段階であって、1つ以上の非システマティック出力記号のそれぞれが、非システマティック出力記号のアルファベットから選択され、各非システマティック出力記号は、1つ以上の入力記号の関数として生成される段階。
【請求項２】
1つ以上の非システマティック出力記号を生成する段階は、
入力記号の集合から複数の中間入力記号を生成する段階と、
複数の中間入力記号を1つ以上の非システマティック出力記号に暗号化する段階とを含み、1つ以上の中間入力記号は1つの非システマティック出力記号に符号化される、請求項1記載の方法。
【請求項３】
複数の中間入力記号を生成する段階は、
複数の入力記号用のシステマティック鍵を算出する段階と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成する段階とを含む、請求項2記載の方法。
【請求項４】
複数の入力記号のシステマティック鍵を算出する段階は、K個の列およびJ個の列を有する行列を作成する段階を含み、Kは入力記号の数に相当し、該方法は、
（i）Jを0に初期設定する段階と、
（ii）鍵D(j)をJの関数として算出する段階と、
（iii）J番目の行の行項目を鍵D(J)の関数として算出する段階と、
（iv）行列の各行が線形に独立しているかどうかを判定する段階とを含み、
行列の行が線形に独立していない場合、JがJ+1に増分され、（ii）〜（iii）が繰り返され、行列の行が線形に独立している場合、システマティック鍵が線形に独立した行として算出される、請求項3記載の方法。
【請求項５】
（ii）鍵D(J)を算出する段階は、乱数発生器を用いて鍵D(J)をJの関数として算出する段階を含む、請求項4記載の方法。
【請求項６】
行の項目は0または1の値を含む、請求項4記載の方法。
【請求項７】
複数の入力記号のシステマティック鍵を算出する段階は、
（i）L個の固有の鍵D(0)〜D(L-1)を算出する段階であって、Lが定義済みの数である段階と、
（ii）K個の列およびL個の行を有する修正復号行列を作成する段階であって、Kが入力記号の数に相当し、0とL-1の間のjの任意の値について、J番目の行に沿って行の項目が鍵D(j)の関数として算出される段階と、
（iii）修正復号行列によって表される一次方程式の集合を解く段階であって、システマティック鍵が一次方程式の解の関数として算出される段階とを含む、請求項3記載の方法。
【請求項８】
システマティック出力記号および非システマティック出力記号を通信チャネル上で送信する段階をさらに含む、請求項1記載の方法。
【請求項９】
入力記号の集合の第1の部分集合を含む1つまたは複数のシステマティック出力記号を受信する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を受信する段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とをさらに含む、請求項8記載の方法。
【請求項１０】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の残りの部分集合を含む複数の入力記号として符号化する段階とを含む、請求項9記載の方法。
【請求項１１】
1つまたは複数の非システマティック出力記号と1つまたは複数のシステマティック出力記号との組合せを複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項10記載の方法。
【請求項１２】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
受信されなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
受信されなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項10記載の方法。
【請求項１３】
システマティック出力記号および非システマティック出力記号を有するチェイン・リアクションコードを、求められているデータを含む入力記号の集合として復号する方法であって、
1つまたは複数のシステマティック出力記号を含む入力記号の集合の第1の部分集合を与える段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を与える段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とをさらに含む方法。
【請求項１４】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する段階とを含む、請求項13記載の方法。
【請求項１５】
1つまたは複数の非システマティック出力記号を複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項14記載の方法。
【請求項１６】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
受信されなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項13記載の方法。
【請求項１７】
通信チャネルに沿って送信される伝送によってシステマティック出力記号および非システマティック出力記号を受信する段階をさらに含む、請求項13記載の方法。
【請求項１８】
チェイン・リアクションコードを用いてデータを処理する方法であって、
システマティック出力記号を含む入力記号の集合をデータから生成する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を、入力記号の集合から生成する段階と、
入力記号の集合のうちの、1つまたは複数のシステマティック出力記号を含む第1の部分集合を受信する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を受信する段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とを含む方法。
【請求項１９】
1つまたは複数の非システマティック出力記号を生成する段階は、
入力記号の集合から複数の中間入力記号を生成する段階と、
複数の中間入力記号を1つまたは複数の非システマティック出力記号として符号化する段階であって、1つまたは複数の中間入力記号が1つの非システマティック出力記号として符号化される段階とを含む、請求項18記載の方法。
【請求項２０】
複数の中間入力記号を生成する段階は、
複数の入力記号のシステマティック鍵を算出する段階と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成する段階とを含む、請求項19記載の方法。
【請求項２１】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する段階とを含む、請求項18記載の方法。
【請求項２２】
1つまたは複数の非システマティック出力記号と1つまたは複数の受信されたシステマティック出力記号との組合せを複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項 21記載の方法。
【請求項２３】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
与えられなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項18記載の方法。
【請求項２４】
通信チャネルに沿って送信される伝送によってシステマティック出力記号および非システマティック出力記号を受信する段階をさらに含む、請求項18記載の方法。
【請求項２５】
入力記号の集合の第1の部分集合を受信する段階は、入力記号の集合の第1の部分集合を含む伝送を受信する段階を含み、1つまたは複数の非システマティック出力記号を受信する段階は、1つまたは複数の非システマティック出力記号を含む伝送を受信する段階を含む、請求項18記載の方法。
【請求項２６】
入力データの集合を、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードとして符号化するように構成されたエンコーダであって、
入力データの集合を受信するように結合され、これに応答して1つまたは複数の入力記号を出力するように動作できる入力記号発生器と、
各入力記号に対応するシステマティック鍵を生成するように動作できるシステマティック鍵発生器と、
1つまたは複数の非システマティック鍵を生成するように動作できる非システマティック鍵発生器と、
1つまたは複数の入力記号、システマティック鍵、および非システマティック鍵を受信し、それに応答して、1つまたは複数の非システマティック鍵および1つまたは複数の入力記号を出力するように結合され、出力される入力記号がシステマティック出力記号を含むシステマティック・エンコーダとを含むエンコーダ。
【請求項２７】
システマティック・エンコーダは、
1つまたは複数の入力記号および1つまたは複数の入力記号に対応するシステマティック鍵を受信するように結合され、この受信に応答して1つまたは複数の中間入力記号を生成するように動作できるチェイン・リアクション・デコーダと、
1つまたは複数の中間入力記号および1つまたは複数の非システマティック鍵を受信するように結合され、この受信に応答して1つまたは複数の非システマティック出力記号を生成するように動作できるチェイン・リアクション・エンコーダとを含む、請求項26記載のエンコーダ。
【請求項２８】
1つまたは複数の入力記号および1つまたは複数の出力記号を受信するように結合され、入力記号および非システマティック出力記号を送信するように動作できる送信モジュールをさらに含み、送信される入力記号はシステマティック出力記号を含む、請求項27記載のエンコーダ。
【請求項２９】
1つまたは複数の非システマティック出力記号および1つまたは複数のシステマティック出力記号を含むチェイン・リアクションコードの集合を復号するように構成されたデコーダであって、
取得された各非システマティック出力記号ごとに非システマティック鍵の集合を生成するように構成された非システマティック鍵発生器と、
1つまたは複数のシステマティック鍵を再生するように構成されたシステマティック鍵発生器と、
1つまたは複数のシステマティック出力記号、1つまたは複数のシステマティック出力記号、システマティック鍵、および非システマティック鍵を受信し、それに応答して1つまたは複数の入力記号を出力するように結合されたシステマティック・デコーダとを含むデコーダ。
【請求項３０】
システマティック鍵再生器は、システマティック鍵の第1の集合およびシステマティック鍵の第2の集合を再生するように構成され、システマティック鍵の第1の集合の各システマティック鍵は、取得されたシステマティック出力記号に相当し、システマティック鍵の第2の集合の各システマティック鍵は、失われたシステマティック出力記号に相当する、請求項29記載のデコーダ。
【請求項３１】
システマティック・エンコーダは、
受信されたシステマティック出力記号、非システマティック鍵の集合、およびシステマティック鍵の第1および第2の集合を受信し、それに応答して中間入力記号の対応する集合を生成するように結合されたチェイン・リアクションコード化・デコーダと、
中間入力記号およびシステマティック鍵の第2の集合を受信し、それに応答して、失われたシステマティック出力記号のコピーを生成するように構成されたチェイン・リアクション・エンコーダとを含み、
受信されなかったシステマティック出力記号のコピーと組み合わされて受信されたシステマティック出力記号は、元のデータの集合を含む送信された入力記号の完全な集合を含む、請求項30記載のデコーダ。
【請求項３２】
コンピュータ可読媒体上に格納され、データを、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードとして符号化するコンピュータ・プログラム製品であって、
システマティック出力記号を含む入力記号の集合をデータから生成することを求める命令符号と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を、入力記号の集合から生成することを求める命令符号とを含み、
入力記号の集合任意の部分集合は、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれていない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復可能であるコンピュータ・プログラム製品。
【請求項３３】
1つまたは複数の非システマティック出力記号を生成することを求める命令符号は、
入力記号の集合から複数の中間入力記号を生成することを求める命令符号とを含み、1つまたは複数の中間入力記号が1つの非システマティック出力記号として符号化される、請求項32記載のコンピュータ・プログラム製品。
【請求項３４】
複数の中間入力記号を生成することを求める命令符号は、
複数の入力記号のシステマティック鍵を算出することを求める命令符号と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成することを求める命令符号とを含む、請求項33記載のコンピュータ・プログラム製品。
【請求項３５】
コンピュータ可読媒体上に格納され、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードを、求められているデータを含む入力記号の集合として復号するコンピュータ・プログラム製品であって、
1つまたは複数のシステマティック出力記号を含む入力記号の集合の第1の部分集合を与えることを求める命令符号と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を与えることを求める命令符号と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復することを求める命令符号とを含むコンピュータ・プログラム製品。
【請求項３６】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復することを求める命令符号は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号することを求める命令符号と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化することを求める命令符号であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する命令符号とを含む、請求項35記載のコンピュータ・プログラム製品。
【請求項３７】
1つまたは複数の非システマティック出力記号と1つまたは複数の受信されたシステマティック出力記号との組合せを複数の中間入力記号として復号することを求める命令符号は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出することを求める命令符号と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出することを求める命令符号と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成することを求める命令符号とを含む、請求項36記載のコンピュータ・プログラム製品。
【請求項３８】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化することを求める命令符号は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出することを求める命令符号と、
与えられなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成することを求める命令符号とを含む、請求項36記載のコンピュータ・プログラム製品。
【請求項１】
以下の段階を含む、データを、システマティック出力記号および非システマティック出力記号を有するチェイン・リアクションコードに符号化する方法であって、
入力記号の集合の任意の一部は、(i)所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の一部に含まれていない入力記号と（b）1つ以上の非システマティック出力記号との組合せから回復可能である方法：
システマティック出力記号を含む入力記号の集合をデータから生成する段階；および
1つ以上の非システマティック出力記号を、入力記号の集合から生成する段階であって、1つ以上の非システマティック出力記号のそれぞれが、非システマティック出力記号のアルファベットから選択され、各非システマティック出力記号は、1つ以上の入力記号の関数として生成される段階。
【請求項２】
1つ以上の非システマティック出力記号を生成する段階は、
入力記号の集合から複数の中間入力記号を生成する段階と、
複数の中間入力記号を1つ以上の非システマティック出力記号に暗号化する段階とを含み、1つ以上の中間入力記号は1つの非システマティック出力記号に符号化される、請求項1記載の方法。
【請求項３】
複数の中間入力記号を生成する段階は、
複数の入力記号用のシステマティック鍵を算出する段階と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成する段階とを含む、請求項2記載の方法。
【請求項４】
複数の入力記号のシステマティック鍵を算出する段階は、K個の列およびJ個の列を有する行列を作成する段階を含み、Kは入力記号の数に相当し、該方法は、
（i）Jを0に初期設定する段階と、
（ii）鍵D(j)をJの関数として算出する段階と、
（iii）J番目の行の行項目を鍵D(J)の関数として算出する段階と、
（iv）行列の各行が線形に独立しているかどうかを判定する段階とを含み、
行列の行が線形に独立していない場合、JがJ+1に増分され、（ii）〜（iii）が繰り返され、行列の行が線形に独立している場合、システマティック鍵が線形に独立した行として算出される、請求項3記載の方法。
【請求項５】
（ii）鍵D(J)を算出する段階は、乱数発生器を用いて鍵D(J)をJの関数として算出する段階を含む、請求項4記載の方法。
【請求項６】
行の項目は0または1の値を含む、請求項4記載の方法。
【請求項７】
複数の入力記号のシステマティック鍵を算出する段階は、
（i）L個の固有の鍵D(0)〜D(L-1)を算出する段階であって、Lが定義済みの数である段階と、
（ii）K個の列およびL個の行を有する修正復号行列を作成する段階であって、Kが入力記号の数に相当し、0とL-1の間のjの任意の値について、J番目の行に沿って行の項目が鍵D(j)の関数として算出される段階と、
（iii）修正復号行列によって表される一次方程式の集合を解く段階であって、システマティック鍵が一次方程式の解の関数として算出される段階とを含む、請求項3記載の方法。
【請求項８】
システマティック出力記号および非システマティック出力記号を通信チャネル上で送信する段階をさらに含む、請求項1記載の方法。
【請求項９】
入力記号の集合の第1の部分集合を含む1つまたは複数のシステマティック出力記号を受信する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を受信する段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とをさらに含む、請求項8記載の方法。
【請求項１０】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の残りの部分集合を含む複数の入力記号として符号化する段階とを含む、請求項9記載の方法。
【請求項１１】
1つまたは複数の非システマティック出力記号と1つまたは複数のシステマティック出力記号との組合せを複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項10記載の方法。
【請求項１２】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
受信されなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
受信されなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項10記載の方法。
【請求項１３】
システマティック出力記号および非システマティック出力記号を有するチェイン・リアクションコードを、求められているデータを含む入力記号の集合として復号する方法であって、
1つまたは複数のシステマティック出力記号を含む入力記号の集合の第1の部分集合を与える段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を与える段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とをさらに含む方法。
【請求項１４】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する段階とを含む、請求項13記載の方法。
【請求項１５】
1つまたは複数の非システマティック出力記号を複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項14記載の方法。
【請求項１６】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
受信されなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項13記載の方法。
【請求項１７】
通信チャネルに沿って送信される伝送によってシステマティック出力記号および非システマティック出力記号を受信する段階をさらに含む、請求項13記載の方法。
【請求項１８】
チェイン・リアクションコードを用いてデータを処理する方法であって、
システマティック出力記号を含む入力記号の集合をデータから生成する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を、入力記号の集合から生成する段階と、
入力記号の集合のうちの、1つまたは複数のシステマティック出力記号を含む第1の部分集合を受信する段階と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を受信する段階と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復する段階とを含む方法。
【請求項１９】
1つまたは複数の非システマティック出力記号を生成する段階は、
入力記号の集合から複数の中間入力記号を生成する段階と、
複数の中間入力記号を1つまたは複数の非システマティック出力記号として符号化する段階であって、1つまたは複数の中間入力記号が1つの非システマティック出力記号として符号化される段階とを含む、請求項18記載の方法。
【請求項２０】
複数の中間入力記号を生成する段階は、
複数の入力記号のシステマティック鍵を算出する段階と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成する段階とを含む、請求項19記載の方法。
【請求項２１】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復する段階は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号する段階と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する段階とを含む、請求項18記載の方法。
【請求項２２】
1つまたは複数の非システマティック出力記号と1つまたは複数の受信されたシステマティック出力記号との組合せを複数の中間入力記号として復号する段階は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出する段階と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出する段階と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成する段階とを含む、請求項 21記載の方法。
【請求項２３】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化する段階は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出する段階と、
与えられなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成する段階とを含む、請求項18記載の方法。
【請求項２４】
通信チャネルに沿って送信される伝送によってシステマティック出力記号および非システマティック出力記号を受信する段階をさらに含む、請求項18記載の方法。
【請求項２５】
入力記号の集合の第1の部分集合を受信する段階は、入力記号の集合の第1の部分集合を含む伝送を受信する段階を含み、1つまたは複数の非システマティック出力記号を受信する段階は、1つまたは複数の非システマティック出力記号を含む伝送を受信する段階を含む、請求項18記載の方法。
【請求項２６】
入力データの集合を、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードとして符号化するように構成されたエンコーダであって、
入力データの集合を受信するように結合され、これに応答して1つまたは複数の入力記号を出力するように動作できる入力記号発生器と、
各入力記号に対応するシステマティック鍵を生成するように動作できるシステマティック鍵発生器と、
1つまたは複数の非システマティック鍵を生成するように動作できる非システマティック鍵発生器と、
1つまたは複数の入力記号、システマティック鍵、および非システマティック鍵を受信し、それに応答して、1つまたは複数の非システマティック鍵および1つまたは複数の入力記号を出力するように結合され、出力される入力記号がシステマティック出力記号を含むシステマティック・エンコーダとを含むエンコーダ。
【請求項２７】
システマティック・エンコーダは、
1つまたは複数の入力記号および1つまたは複数の入力記号に対応するシステマティック鍵を受信するように結合され、この受信に応答して1つまたは複数の中間入力記号を生成するように動作できるチェイン・リアクション・デコーダと、
1つまたは複数の中間入力記号および1つまたは複数の非システマティック鍵を受信するように結合され、この受信に応答して1つまたは複数の非システマティック出力記号を生成するように動作できるチェイン・リアクション・エンコーダとを含む、請求項26記載のエンコーダ。
【請求項２８】
1つまたは複数の入力記号および1つまたは複数の出力記号を受信するように結合され、入力記号および非システマティック出力記号を送信するように動作できる送信モジュールをさらに含み、送信される入力記号はシステマティック出力記号を含む、請求項27記載のエンコーダ。
【請求項２９】
1つまたは複数の非システマティック出力記号および1つまたは複数のシステマティック出力記号を含むチェイン・リアクションコードの集合を復号するように構成されたデコーダであって、
取得された各非システマティック出力記号ごとに非システマティック鍵の集合を生成するように構成された非システマティック鍵発生器と、
1つまたは複数のシステマティック鍵を再生するように構成されたシステマティック鍵発生器と、
1つまたは複数のシステマティック出力記号、1つまたは複数のシステマティック出力記号、システマティック鍵、および非システマティック鍵を受信し、それに応答して1つまたは複数の入力記号を出力するように結合されたシステマティック・デコーダとを含むデコーダ。
【請求項３０】
システマティック鍵再生器は、システマティック鍵の第1の集合およびシステマティック鍵の第2の集合を再生するように構成され、システマティック鍵の第1の集合の各システマティック鍵は、取得されたシステマティック出力記号に相当し、システマティック鍵の第2の集合の各システマティック鍵は、失われたシステマティック出力記号に相当する、請求項29記載のデコーダ。
【請求項３１】
システマティック・エンコーダは、
受信されたシステマティック出力記号、非システマティック鍵の集合、およびシステマティック鍵の第1および第2の集合を受信し、それに応答して中間入力記号の対応する集合を生成するように結合されたチェイン・リアクションコード化・デコーダと、
中間入力記号およびシステマティック鍵の第2の集合を受信し、それに応答して、失われたシステマティック出力記号のコピーを生成するように構成されたチェイン・リアクション・エンコーダとを含み、
受信されなかったシステマティック出力記号のコピーと組み合わされて受信されたシステマティック出力記号は、元のデータの集合を含む送信された入力記号の完全な集合を含む、請求項30記載のデコーダ。
【請求項３２】
コンピュータ可読媒体上に格納され、データを、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードとして符号化するコンピュータ・プログラム製品であって、
システマティック出力記号を含む入力記号の集合をデータから生成することを求める命令符号と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を、入力記号の集合から生成することを求める命令符号とを含み、
入力記号の集合任意の部分集合は、（i）所定数の非システマティック出力記号、または（ii）（a）回復すべき入力記号の部分集合に含まれていない入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復可能であるコンピュータ・プログラム製品。
【請求項３３】
1つまたは複数の非システマティック出力記号を生成することを求める命令符号は、
入力記号の集合から複数の中間入力記号を生成することを求める命令符号とを含み、1つまたは複数の中間入力記号が1つの非システマティック出力記号として符号化される、請求項32記載のコンピュータ・プログラム製品。
【請求項３４】
複数の中間入力記号を生成することを求める命令符号は、
複数の入力記号のシステマティック鍵を算出することを求める命令符号と、
複数の入力記号および対応するシステマティック鍵から複数の中間入力記号を生成することを求める命令符号とを含む、請求項33記載のコンピュータ・プログラム製品。
【請求項３５】
コンピュータ可読媒体上に格納され、システマティック出力記号および非システマティック出力記号を含むチェイン・リアクションコードを、求められているデータを含む入力記号の集合として復号するコンピュータ・プログラム製品であって、
1つまたは複数のシステマティック出力記号を含む入力記号の集合の第1の部分集合を与えることを求める命令符号と、
各非システマティック出力記号が、非システマティック出力記号のアルファベットから選択され、1つまたは複数の入力記号の関数として生成される、1つまたは複数の非システマティック出力記号を与えることを求める命令符号と、
入力記号の第1の集合に含まれていない1つまたは複数の入力記号を含む入力記号の集合の残りの部分集合を、
（i）所定数の非システマティック出力記号、または
（ii）（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから回復することを求める命令符号とを含むコンピュータ・プログラム製品。
【請求項３６】
（a）第1の部分集合から得た1つまたは複数の入力記号と（b）1つまたは複数の非システマティック出力記号との組合せから入力記号の残りの部分集合を回復することを求める命令符号は、
1つまたは複数の受信された非システマティック出力記号と1つまたは複数の受信されたシステマティック入力記号との組合せを複数の中間入力記号として復号することを求める命令符号と、
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化することを求める命令符号であって、入力記号の第1の部分集合と残りの部分集合が集合的に入力記号の集合を形成する命令符号とを含む、請求項35記載のコンピュータ・プログラム製品。
【請求項３７】
1つまたは複数の非システマティック出力記号と1つまたは複数の受信されたシステマティック出力記号との組合せを複数の中間入力記号として復号することを求める命令符号は、
受信されたシステマティック出力記号に対応するシステマティック鍵を算出することを求める命令符号と、
受信された非システマティック出力記号に対応する非システマティック鍵を算出することを求める命令符号と、
システマティック鍵、非システマティック鍵、受信された非システマティック出力記号、および受信されたシステマティック出力記号から複数の中間入力記号を生成することを求める命令符号とを含む、請求項36記載のコンピュータ・プログラム製品。
【請求項３８】
複数の中間入力記号を、入力記号の残りの部分集合を含む1つまたは複数の入力記号として符号化することを求める命令符号は、
与えられなかったシステマティック出力記号のシステマティック鍵を算出することを求める命令符号と、
与えられなかったシステマティック出力記号および中間入力記号に対応するシステマティック鍵から入力記号の残りの部分集合を生成することを求める命令符号とを含む、請求項36記載のコンピュータ・プログラム製品。
【図１Ａ】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６Ａ】
【図１６Ｂ】
【図１７Ａ】
【図１７Ｂ】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６Ａ】
【図１６Ｂ】
【図１７Ａ】
【図１７Ｂ】
【公開番号】特開２０１０−２３９６２５（Ｐ２０１０−２３９６２５Ａ）
【公開日】平成２２年１０月２１日（２０１０．１０．２１）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１０８２９４（Ｐ２０１０−１０８２９４）
【出願日】平成２２年５月１０日（２０１０．５．１０）
【分割の表示】特願２００４−５４３０６７（Ｐ２００４−５４３０６７）の分割
【原出願日】平成１５年１０月１日（２００３．１０．１）
【出願人】（５０１１１４８４４）デジタル ファウンテン， インコーポレイテッド (25)
【Ｆターム（参考）】
【公開日】平成２２年１０月２１日（２０１０．１０．２１）
【国際特許分類】
【出願番号】特願２０１０−１０８２９４（Ｐ２０１０−１０８２９４）
【出願日】平成２２年５月１０日（２０１０．５．１０）
【分割の表示】特願２００４−５４３０６７（Ｐ２００４−５４３０６７）の分割
【原出願日】平成１５年１０月１日（２００３．１０．１）
【出願人】（５０１１１４８４４）デジタル ファウンテン， インコーポレイテッド (25)
【Ｆターム（参考）】
[ Back to top ]