(57)【要約】  通信チャネルを介した転送元から転送先までの転送のためのデータの符号化方法が提供される。当該方法は、入力シンボルの順列セットを演算して、線形の制約条件に基づいた入力シンボルから複数の冗長シンボルの生成を含む。当該方法は、また、線形の制約条件に基づいた、入力シンボルと冗長シンボルとを含むシンボルの合成セットからの複数の出力シンボルの生成を含む。ここで、線形の制約条件の少なくとも１つまたはその組み合わせは第１の有限体上に存在し、線形の制約条件の他の少なくとも１つまたはその組み合わせは異なる第２の有限体上に存在する。これにより、入力シンボルの順列セットは任意の個数の出力シンボルから所望の精度で再生できる。
2009527949.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一部が消去チャネルとして振舞う通信チャネル上を送信元から送信先まで転送されるデータを符号化する方法であって、
符号化されるデータを表す入力シンボルの順列セットを取得するステップと、
値の複数の体配列を選択するステップであって、体配列の各々は有限体配列から導出され、少なくとも２つの異なる有限体配列を表している、ステップと、
前記複数の体配列の少なくとも２つを表す係数行列を表すデータ構造を生成するステップであって、該少なくとも２つの体配列は互いに異なる有限体配列から導出される、ステップと、
入力シンボルの線形結合として出力シンボルを生成するステップであって、当該結合は係数行列を表す前記データ構造に従っている、ステップと、
生成された出力シンボルと前記データのための符号化とを使用するステップと、
を含むことを特徴とする方法。
【請求項２】
係数行列を表す前記データ構造はセル値の２次元配列であり、セル値の各々は１つの出力シンボルの生成における１つの入力シンボルの係数を表し、係数がゼロまたは所定基数を法としてゼロでない場合、関連する出力シンボルの値は関連する入力シンボルの値に依存する、ことを特徴とする請求項１に記載の方法。
【請求項３】
係数行列を表す前記データ構造は係数の値を指定するルールのセットであり、該ルールの１つは、係数がゼロまたは所定基数を法としてゼロでないことを示し、関連する出力シンボルの値は関連する入力シンボルの値に依存する、ことを特徴とする請求項１に記載の方法。
【請求項４】
入力シンボルの前記セットから生成された一意となる出力シンボルの数は、入力シンボルに対する固定値の任意のセットに対して、体配列のサイズと独立である、ことを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の体配列の少なくとも２つは互いに異なる有限体配列から導出され、少なくとも２つを表す係数行列を表すデータ構造の生成は、第１の有限体配列から導出される第１の体配列と第２の有限体配列から導出される第２の体配列とを使用する生成であり、前記第１の有限体配列と前記第２の有限体配列とは異なり、さらに、前記第１の有限体と前記第２の有限体の各々は、ＧＦ（２），ＧＦ（４），ＧＦ（１６），ＧＦ（２５６）から構成される体のセットから選択される、ことを特徴とする請求項１に記載の方法。
【請求項６】
前記第１の有限体配列はＧＦ（２）であり、前記第２の有限体配列はＧＦ（２５６）であることを特徴とする請求項５に記載の方法。
【請求項７】
前記第１の有限体配列はＧＦ（２）であり、前記第２の有限体配列はＧＦ（４）であることを特徴とする請求項５に記載の方法。
【請求項８】
前記第１の有限体配列はＧＦ（４）であり、前記第２の有限体配列はＧＦ（１６）であることを特徴とする請求項５に記載の方法。
【請求項９】
前記第１の有限体配列はＧＦ（１６）であり、前記第２の有限体配列はＧＦ（２５６）であることを特徴とする請求項５に記載の方法。
【請求項１０】
前記第１の有限体配列は前記第２の有限体配列より小さいことを特徴とする請求項５に記載の方法。
【請求項１１】
前記第１の有限体配列は前記第２の有限体配列より大きいことを特徴とする請求項５に記載の方法。
【請求項１２】
少なくとも一部が消去チャネルとして振舞う通信チャネル上を送信元から送信先まで転送されるデータを復号化する方法であって、
入力シンボルの順列セットから生成された複数の出力シンボルの少なくともいくつかを受信するステップであって、入力シンボルの前記順列セットは複数の出力シンボルに符号化されたものであり、出力シンボルの各々は１以上の入力シンボルの有限体から選択された係数による線形結合であり、少なくとも１つの係数は第１の有限体のメンバであり、他の少なくとも１つの係数は第２の有限体のメンバかつ前記第１の有限体のメンバではない、ステップと、
任意の所定数の出力シンボルの受信から入力シンボルの前記順列セットを所望の精度で再生するステップと、
を含むことを特徴とする方法。
【請求項１３】
入力シンボルの固定数の任意のセットについて、入力シンボルの前記セットから生成され得るユニークなシンボルの個数は、体配列のサイズと独立であることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記有限体は、前記第１の有限体配列と前記第２の有限体配列とが異なるようなものであり、前記第１の有限体および前記第２の有限体の各々は、ＧＦ（２），ＧＦ（４），ＧＦ（１６），ＧＦ（２５６）から構成される体のセットから選択されることを特徴とする請求項１２に記載の方法。
【請求項１５】
前記第１の有限体配列はＧＦ（２）であり、前記第２の有限体配列はＧＦ（２５６）であることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記第１の有限体配列はＧＦ（２）であり、前記第２の有限体配列はＧＦ（４）であることを特徴とする請求項１４に記載の方法。
【請求項１７】
前記第１の有限体配列はＧＦ（４）であり、前記第２の有限体配列はＧＦ（１６）であることを特徴とする請求項１４に記載の方法。
【請求項１８】
前記第１の有限体配列はＧＦ（１６）であり、前記第２の有限体配列はＧＦ（２５６）であることを特徴とする請求項１４に記載の方法。
【請求項１９】
前記第１の有限体配列は前記第２の有限体配列より小さいことを特徴とする請求項１４に記載の方法。
【請求項２０】
前記第１の有限体配列は前記第２の有限体配列より大きいことを特徴とする請求項１４に記載の方法。
【請求項２１】
少なくとも一部が消去チャネルとして振舞う通信チャネル上を送信元から送信先まで転送されるデータを符号化する方法であって、
符号化されるデータを表す入力シンボルの順列セットを取得するステップと、
値の複数の体配列を選択するステップであって、体配列の各々は有限体配列から導出され、少なくとも２つの異なる有限体配列を表している、ステップと、
前記複数の体配列の少なくとも２つを表す係数行列を表すデータ構造を生成するステップであって、該少なくとも２つの体配列は互いに異なる有限体配列から導出される、ステップと、
入力シンボルの前記順列セットから複数の冗長シンボルを生成するステップであって、冗長シンボルの各々は、有限体上の係数により１以上の入力シンボルと他の冗長シンボルとに対する線形制約のセットに基づいて生成される、ステップと、
入力シンボルの線形結合として出力シンボルを生成するステップであって、当該結合は係数行列を表す前記データ構造に従っている、ステップと、
入力シンボルと冗長シンボルとの混合セットから複数の出力シンボルを生成するステップであって、出力シンボルの各々は、入力シンボルと冗長シンボルとの前記混合セットの１以上の、有限体から選択された係数による線形結合として生成される、ステップと、
生成された出力シンボルと前記データのための符号化とを使用するステップと
を含むことを特徴とする方法。
【請求項２２】
入力シンボルの前記セットから生成され得る冗長シンボルの数は、入力シンボルの固定値の任意のセットについて、体配列サイズと独立であることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記有限体は、第１の有限体配列と第２の有限体配列とが異なり、該第１の有限体と該第２の有限体の各々は、ＧＦ（２），ＧＦ（４），ＧＦ（１６），ＧＦ（２５６）から構成される体のセットから選択されることを特徴とする請求項２１に記載の方法。
【請求項２４】
少なくとも一部が消去チャネルとして振舞う通信チャネル上を送信元から送信先まで転送されるデータを復号化する方法であって、
入力シンボルと冗長シンボルとの混合セットから生成された複数の出力シンボルの少なくともいくつかを受信するステップであって、出力シンボルの各々は入力シンボルと冗長シンボルとの前記混合セットの１以上の、有限体から選択された係数による線形結合として生成される、ステップと、
ここで、複数の冗長シンボルは、入力シンボルの順列セットから生成され、冗長シンボルの各々は、有限体上の係数により１以上の入力シンボルと他の冗長シンボルとに対する線形制約のセットに基づいて生成され、
ここで、少なくとも１つの係数は第１の有限体のメンバであり、他の少なくとも１つの係数は第２の有限体のメンバかつ前記第１の有限体のメンバではなく、
任意の所定数の出力シンボルの受信から入力シンボルの前記順列セットを所望の精度で再生するステップと、
を含むことを特徴とする方法。
【請求項２５】
入力シンボルの前記セットから生成された一意となる出力シンボルの数は、入力シンボルに対する固定値の任意のセットに対して、体配列のサイズと独立である、ことを特徴とする請求項２４に記載の方法。
【請求項２６】
前記第１の有限体配列はＧＦ（２）であることを特徴とする請求項２４に記載の方法。
【請求項２７】
前記第２の有限体配列はＧＦ（２５６）であることを特徴とする請求項２４に記載の方法。
【請求項２８】
前記第２の有限体配列はＧＦ（４）であることを特徴とする請求項２４に記載の方法。
【請求項２９】
前記第１の有限体配列はＧＦ（４）であることを特徴とする請求項２４に記載の方法。
【請求項３０】
前記第１の有限体配列はＧＦ（１６）であることを特徴とする請求項２４に記載の方法。
【請求項３１】
前記第２の有限体配列はＧＦ（１６）であることを特徴とする請求項２４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信システムにおけるデータの符号化及び復号化に関し、より詳細には通信データにおける誤りや切れ目を考慮したデータの符号化及び復号化に関するものである。”通信”は広義で使用され空間および／または時間を介した任意の形態のデジタルデータ転送を含むがこれに限定されない。
【背景技術】
【０００２】
（相互参照）
本願は２００６年２月２１日出願の米国仮特許出願番号６０／７７５，５２８の優先権を主張する非仮出願である。
【０００３】
以下の参考文献を本願明細書に引用し、すべての目的のために参照により組み込む。
【０００４】
ルビー（Luby）に対して発行された、”Information Additive Code Generator and Decoder for Communication Systems”というタイトルの米国特許第６，３０７，４８７号（以下、”ルビーＩ”）。
【０００５】
ルビー他に対して発行された、”Information Additive Group Code Generator and Decoder for Communication Systems”というタイトルの米国特許第６，３２０，５２０号（以下、”ルビーＩＩ”）。
【０００６】
ショクロラヒ（Shokrollahi）他に対して発行された、”Multi-Stage Code Generator and Decoder for Communication Systems”というタイトルの米国特許第７，０６８，７２９号（以下、”ショクロラヒＩ”）。
【０００７】
ショクロラヒ他に対して発行された、”Systematic Encoding and Decoding of Chain Reaction Codes”というタイトルの米国特許第６，９０９，３８３号（以下、”ショクロラヒＩＩ”）。
【０００８】
ショクロラヒ他に対して発行された、”Systems and Processes for Decoding Chain Reaction Codes through Inactivation”というタイトルの米国特許第６，８５６，２６３号（以下、”ショクロラヒＩＩＩ”）。
【０００９】
ショクロラヒにより２００４年１２月１日に出願された、”Protection of Data from Erasures Using Subsymbol Based Codes”というタイトルの米国特許公開第２００５／０２１９０７０Ａ１号（以下、”ショクロラヒＩＶ”）。
【００１０】
送り手と受け手との間で通信チャネルを介して行うファイルおよびストリームの転送は多くの文献の主題として取り上げられてきた。好ましくは、受け手は、送り手からチャネルを介して送信される正確なデータのコピーをあるレベルの確実性をもって受信することを望む。チャネルは完全な忠実度を有していない（物理的に実現可能な多くのシステムがそうである）ため、転送により消失するか歪められるデータを取り扱う方法に関心が生じる。受け手は、いつ破損データが誤ってデータ受信されたかの判断を常に行えるとは限らないので、通常、破損データ（誤り）に比較し欠落データ（消去）を取扱うのは容易である。多くの誤り訂正符号は、消去および／または誤りを訂正するために開発されてきた。一般的に、データが送信されているチャネルおよび送信されているデータの性質の不忠実度に関する何らかの情報に基づいて使用する特定の符号が選択される。たとえば、チャネルが長期間の不忠実度を有することが既知の場合、当該アプリケーションにはバースト誤り符号が最適であり得る。短くまれな誤りだけが予想される場合、簡単なパリティ符号が最善であり得る。
【００１１】
送信機および受信機が通信のために必要とされる演算能力および電力の全てを利用し、送受信装置間のチャネルが相対的にエラーフリーの通信を可能とするのに十分クリーンであるときに、データ転送は直接的に行なわれる。そして、チャネル環境が悪いか、または、送信機および／または受信機の能力が制限されている場合に、データ転送の問題は難しくなる。
【００１２】
１つのソリューションは、受信機が転送における消去および誤りを回復可能となるように、データを送信機で符号化する前方誤り訂正（ＦＥＣ）技術を活用する方法である。受信機から送信機へのリバースチャネルが利用可能な場合、受信機が送信機に誤りについての通信が可能であり、伝送プロセスを調整可能である。しかし、しばしばリバースチャネルは利用可能ではない。たとえば、送信機が多数の受信機に対して送信している場合、送信機はそれらの全ての受信機からのリバースチャネルを取り扱うことが不可能であり得る。他の例では、通信チャネルは記録媒体であり得、この場合、データの転送は時間に沿ってなされ、誰かが時間を遡れる時間旅行マシンを発明しない限り、このチャネルのリバースチャネルはありえない。その結果、通信プロトコルはしばしばリバースチャネルなしで設計されることを必要とし、そして、送信機はこれらのチャネル状況の全容無しに広く様々なチャネル状況を取扱わなければならないかもしれない。
【００１３】
受信機が携帯型または移動可能である低電力の小型デバイスであり高帯域でのデータ受信を必要とする場合、送信機と受信機との間のデータ転送の問題はより難しくなる。たとえば、無線ネットワークが、ファイルまたはストリームをブロードキャストまたはマルチキャストにより固定された送信機から多数あるいは不確定数の携帯型または移動可能な受信機に配信するよう設定され、受信機が演算能力、記憶容量、利用できる電力、アンテナサイズ、デバイスサイズおよびその他の設計制約条件において拘束される場合である。他の例では、受信機が記憶媒体からデータを取り出す記憶用途であり、オリジナルデータの復元に不忠実が現れる。このような受信機は、装置内のディスクドライブなどの記憶部自身にしばしば組み込まれており、演算能力および電力に大きな制約がある。
【００１４】
このようなシステムでは、リバースチャネルが少ないか皆無であり、記憶制限、計算サイクル制限、電力、移動可能性およびタイミングを含む考慮が必要である。個々の受信機の電源の予測不可能なオン／オフ、範囲の出入り、リンクエラーによるロス、移動、輻輳によるファイルまたはストリームパケットに対する優先度の一時的な引き下げの強制などがあり得る潜在的に多数の受信機にデータ配信するために必要な転送時間を最小化するよう設計することが望まれる。
【００１５】
パケット損失が発生し得るチャネルを介したデータ転送のために使用されるパケットプロトコルの場合、パケット網を通じて送信されるファイル、ストリームまたは他のデータブロックは、均等なサイズの入力シンボルに区切られ、入力シンボルと同一のサイズの符号化シンボルがＦＥＣ符号を使用して入力シンボルから生成され、符号化シンボルはパケットに配置され送信される。入力シンボルが実際にビットストリームに分解されるか否かに関わらず、入力シンボルの”サイズ”はビット単位で計測することができ、入力シンボルが２Ｍ個のシンボルのアルファベットから選択される場合、入力シンボルはＭビットのサイズを有する。この種のパケットベースの通信システムにおいて、パケットに基づいた消去ＦＥＣ符号化方法が適切である。ネットワーク内で消去が発生したにもかかわらず指定された受け手がオリジナルファイルの正確なコピーを回復可能な場合、高信頼なファイル転送と呼ぶことが出来る。ネットワーク内で消去が発生したにもかかわらず指定された受け手がタイムリーな方法でストリーム各部の正確なコピーを回復可能な場合、高信頼なストリーム転送と呼ぶことが出来る。また、ファイルまたはストリームの一部が回復可能でない、または、ストリーミングにおいてストリームの一部がただちに回復可能ではないという意味では、ファイル転送およびストリーム転送の双方についていくらかの信頼性があり得る。パケット損失は、しばしば、散発的な輻輳の発生によりルータのバッファリングメカニズムが処理限界に達し入力パケットが強制的にドロップされることにより生じる。そのため、転送中の消去発生に対する保護が多くの研究の主題とされてきた。
【００１６】
ビットを破壊し得るノイズの多いチャネル上でのデータ転送で使用されるプロトコルの場合、データ転送チャネル上で伝送されるデータのブロックは、等しいサイズの入力シンボルに区切られ、入力シンボルから等しいサイズの符号化シンボルが生成され、符号化シンボルがチャネル上に送信される。このようなノイズの多いチャネルでは、シンボルが実際にビットストリームに分解されるかどうかに関わらずシンボルのサイズは通常１ビットまたは数ビットである。このような通信システムでは、ビットストリーム指向の誤り訂正ＦＥＣ符号化スキームが適している。誤り（シンボル破壊、チャネルでの検出あるいは未検出）が発生したにもかかわらず指定された受け手がオリジナルファイルの正確なコピーを回復可能な場合、高信頼性なデータ転送と呼ぶことが出来る。また、回復の後、ブロックの一部が破壊されているという意味では、転送はいくらかの信頼性があり得る。シンボルはしばしば突発的ノイズ、周期的ノイズ、干渉、弱い信号、チャネル妨害、および他の様々な原因により破壊される。転送中のデータ破壊に対する保護は研究の主題とされてきた。
【００１７】
連鎖反応符号は、ファイルまたはストリームの一定の入力シンボルからの多数の出力シンボルの生成を可能にするＦＥＣ符号である。この符号は事前の固定転送レートを持たないことから、ときに、ファウンテン符号あるいはレートレス符号とも呼ばれる。連鎖反応符号は様々な利用があり、情報付加的方法によりおびただしい数の出力シンボルの生成を含み、情報重複的方法ではなく、ここで、後者は、入力シンボルを回復する前の受信器により受信された出力シンボルは、既に受信した情報と重複し、入力シンボルを回復するのに有用な情報を提供しない。連鎖反応符号の生成、使用、操作のための新規の技術が、例えば、ルビーＩ，ルビーＩＩ，ショクロラヒＩおよびショクロラヒＩＩに示されている。
【００１８】
連鎖反応符号化器により作成される出力シンボルの特性の１つとして、受信機は十分な出力シンボルを受信するとすぐにオリジナルファイルまたはオリジナルストリームのブロックを回復することが可能であるということがある。具体的には、高確率を有するオリジナルのＫ個の入力シンボルを回復するために、受信機はおよそＫ＋Ａ個の出力シンボルを必要とする。ここで、比Ａ／Ｋは”相対的受信オーバヘッド”と呼ばれる。相対的受信オーバヘッドは、入力シンボル数Ｋ、および、復号化器の信頼性に依存する。
【００１９】
また、多段階連鎖反応（”ＭＳＣＲ”）符号を使用することも公知であり、例えばショクラヒＩおよび／またはＩＩに記載されデジタルファウンテン社により開発された”Ｒａｐｔｏｒ”として商品名の符号がある。多段階連鎖反応符号は、たとえば、ソースファイルまたはソースストリームから入力シンボルを受信し、そこから中間シンボルを生成し、連鎖反応符号を用いた中間シンボルを符号化する符号化器により用いられる。より詳しくは、送信される入力シンボルの順列セットから複数の冗長シンボルが生成される。そして、入力シンボルおよび冗長シンボルを含むシンボルの混合セットから複数の出力シンボルが生成される。ここで、可能な出力シンボルの数はシンボルの混合セットのシンボルの数に比較し非常に大きい。また、少なくとも一つの出力シンボルは、シンボルの混合セットの１つのシンボルより多く全てのシンボル数よりは少ないシンボルから生成され、任意の所定数Ｎの出力シンボルから入力シンボルの順序集合が所望の精度まで再生できるように生成される。上述の組織的符号の符号化及び復号化の技術も既知であり、そこでは符号の可能な出力シンボルの中に入力シンボルが含まれる。これは、ショクロラヒＩＩに書かれたように、上述のステップの前に最初に入力シンボルに変換を適用することにより実現され、この改良されたプロセスにより、入力シンボルと等しい符号により生成された最初の出力シンボルとなる。誤りおよび消去符号の当業者は、ショクロラヒＩＩの技術が本明細書で提案される符号に直接的に適用されうることが明白であろう。
【００２０】
用途によっては、他のバリエーションの符号がより適切あるいはより好適であり得る。
【００２１】
上述のＭＳＣＲ符号および連鎖反応符号は、それらの符号化および復号化の複雑性の点で非常に効率的である。それらの効率性の理由のうちの１つは、実行される演算が、体ＧＦ（２）、すなわち、２つの体の元を加算する演算が単に論理ＸＯＲ演算であり、２つの体の元を乗算する演算が単に論理ＡＮＤ演算である１ビット上の単純な体上の線形演算であることである。概して、これらの演算は、同時に複数のビットに渡って、例えば、一度に３２ビットまたは一度に４バイトに渡って実行され、そのような演算は、全ての現在のＣＰＵプロセッサでネイティブサポートされる。その一方、消去ＦＥＣ符号として使用されるとき、演算がＧＦ（２）上であるので、受信機が全ての入力シンボルを復号化することができる可能性が、最初のＫ個を超えて受信されたそれぞれの追加的なシンボルに対して最大でおよそ半分低下することが判明し、ここで、Ｋは元の入力シンボルの数である。例えば、Ｋ＋Ａ個の符号化シンボルが受信される場合、回復プロセスがＫ個の元の入力シンボルを回復することに失敗する可能性は、少なくとも２−Ａである。より望ましい振る舞いであるのは、復号化の失敗の可能性がＡの関数としてより急速に小さくされることである。
【００２２】
より大きな体上で機能するその他の消去および誤り訂正ＦＥＣ符号、例えば、ＧＦ（４）上で、またはＧＦ（８）上で、またはＧＦ（２５６）上で、またはより一般的に任意のＬ＞１に対するＧＦ（２Ｌ）上で機能するリードソロモン符号、および、さらに、より大きな体上で機能するＬＤＰＣ符号が存在する。そのようなＦＥＣ符号の利点は、例えば、消去ＦＥＣ符号の場合、復号化の失敗の可能性が、Ａの関数として、ＧＦ（２）上のＦＥＣ符号よりもはるかに高速に減少することである。その一方、これらのＦＥＣ符号は、概して、符号化および復号化の複雑性の観点ではるかに非効率的であり、その主な理由のうちの１つは、より大きな体上の演算がはるかに複雑であり、および／または現在のＣＰＵによってネイティブサポートされないからであり、概して、複雑性は、体のサイズが増すにつれて増える。したがって、より大きな有限体上で機能するＦＥＣ符号は、ＧＦ（２）上で機能するＦＥＣ符号と比較してはるかに低速であるか、または非実用的であることが多い。
【発明の開示】
【発明が解決しようとする課題】
【００２３】
したがって、必要とされるのは、復号化の失敗の可能性が、元の入力シンボルを回復するために理想的なＦＥＣ符号によって必要とされる最小数を超えて受信されたシンボルの数の関数として非常に高速に減少する特性を有する、符号の符号化および復号化の複雑性の観点で極めて効率的な消去および誤り訂正ＦＥＣ符号である。
【課題を解決するための手段】
【００２４】
本発明の一実施形態によれば、通信チャネルを介した送信元から送信先への伝送のためにデータを符号化する方法が提供される。方法は、入力シンボルの順序付けられたセットに対して機能し、入力シンボルから０個以上の冗長シンボルを生成することができ、各冗長シンボルは、１つまたは複数の有限体から得られた係数を用いたいくつかの入力シンボルの一次結合に等しく、使用される有限体は、異なる入力シンボルの間で、および異なる冗長シンボルの間で異なる可能性がある。方法は、入力シンボルと、何らかの冗長シンボルが存在する場合には冗長シンボルとを含むシンボルの合成セットからの複数の出力シンボルの生成を含み、各出力シンボルは、合成された入力シンボルおよび冗長シンボルのうちの１つまたは複数から生成されることができ、各出力シンボルは、１つまたは複数の有限体から得られた係数を用いたいくつかの入力シンボルおよび冗長シンボルの一次結合として生成され、使用される有限体は、入力シンボルの順序付けられたセットが任意の所定の数の出力シンボルから所望の精度で再生されることができるように、異なる入力シンボルと冗長シンボルとの間で、異なる出力シンボルの間で、および出力シンボルと冗長シンボルとの間で異なる可能性がある。
【００２５】
また、方法は出力シンボルを生成するために使用されることができ、入力シンボルの決まったセットから生成されることができるあり得る出力シンボルの数は、入力シンボルの数よりもはるかに多い可能性がある。
【００２６】
本発明の別の実施形態によれば、方法は、通信チャネルを介して送信元から送信された出力シンボルの少なくとも一部を送信先で受信することを含み、チャネルを介した伝送は送信シンボルの一部の消去または破損をもたらす可能性があり、受信シンボルの一部は正しく受信されることが知られることができ、シンボルの破損の程度に関する情報も提供されることができる。方法は、いくつのシンボルが受信されるかと、受信シンボルの破損の知識とによって決まる所望の精度で、入力シンボルの順序付けられたセットを送信先で再生することを含む。
【００２７】
この実施形態は、出力シンボルの少なくとも一部を送信先で受信することも含むことができ、受信されることができるあり得る出力シンボルの数は、入力シンボルの数よりもはるかに多い可能性がある。
【００２８】
本発明の別の実施形態によれば、通信チャネルを介した送信元から送信先への伝送のためにデータを符号化する方法が提供される。方法は、入力シンボルの順序付けられたセットに対して機能し、入力シンボルから複数の冗長シンボルを生成することを含む。方法は、入力シンボルおよび冗長シンボルを含むシンボルの合成セットから複数の出力シンボルを生成することも含み、出力シンボルの生成において適用される演算は、小さな有限体（例えば、ＧＦ（２））上であり、入力シンボルの順序付けられたセットが任意の所定の数の出力シンボルから所望の精度で再生されることができるようなものである。複数の冗長シンボルは入力シンボルの順序付けられたセットから生成され、冗長シンボルを生成するための演算は、ＧＦ（２）ではない有限体（例えば、ＧＦ（２５６））上であるか、または２つ以上の有限体の混合上である（例えば、ＧＦ（２）上の一部の演算、ＧＦ（２５６）上の一部の演算）。
【００２９】
本発明のさらに別の実施形態によれば、通信チャネル上で送信元から送信されたデータを受信するためのシステムが、同様の技術を使用して提供される。システムは、通信チャネルを介して送信された出力シンボルを受信するための、通信チャネルに結合された受信モジュールを含み、各出力シンボルは、入力シンボルおよび冗長シンボルを含むシンボルの合成セット内の少なくとも１つのシンボルから生成され、出力シンボルの生成において適用される演算は、小さな有限体（例えば、ＧＦ（２））上であり、入力シンボルの順序付けられたセットが任意の所定の数の出力シンボルから所望の精度で再生されることができるようなものであり、入力シンボルは入力シンボルの順序付けられたセットからのものであり、冗長シンボルは入力シンボルから生成され、複数の冗長シンボルが入力シンボルの順序付けられたセットから生成され、冗長シンボルを生成するための演算は、ＧＦ（２）ではない有限体（例えば、ＧＦ（２５６））上であるか、または２つ以上の有限体の混合上である（例えば、ＧＦ（２）上の一部の演算、ＧＦ（２５６）上の一部の演算）。
【００３０】
本発明のさらに別の実施形態によれば、搬送波で具現化されるコンピュータデータ信号が提供される。
【００３１】
多くの利点が、本発明のやり方によって達成される。例えば、特定の実施形態において、チャネルを介した伝送のためのデータの符号化の計算量が削減される。別の特定の実施形態において、そのようなデータの復号化の計算量が削減される。さらに別の特定の実施形態において、復号化器の誤り確率が、符号化および復号化の計算量を少なく保ったまま小さくされる。実施形態に応じて、これらの利点のうちの１つまたは複数が達成されることができる。これらのおよびその他の利点が、本明細書を通じてより詳細に提供され、以下でより具体的に提供される。
【００３２】
本明細書において開示される発明の性質および利点のさらなる理解が、本明細書の残りの部分および添付の図面を参照することによって得られることができる。
【発明を実施するための最良の形態】
【００３３】
詳細な説明の後に３つの付録を示しており、付録Ａは、組織的インデックスＪ（Ｋ）の値の例を含み、付録Ｂ．１は、テーブルＶ０の値の例を含み、付録Ｂ．２は、テーブルＶ１の値の例を含んでいる。
【００３４】
本明細書において説明される発明は、１つまたは複数の有限体における演算に基づく符号化および復号化のための数学的演算を使用する。有限体は、四則演算が定義され、それらの演算に関して体を形成する有限の代数的構造である。それらの定理およびそれらの構築は当業者によく理解されている。
【００３５】
以下に続く説明において、我々は、乗算プロセスが、有限体の元と、符号化もしくは復号化されるべきデータを表すか、または符号化もしくは復号化されるべきデータから導出されるシンボルとの間で定義されることを必要とすることになる。３つの異なる種類のシンボルがこの説明において考慮され、入力シンボルは、受信機に伝達されるべき送信機に知られている情報を含み、冗長シンボルは、入力シンボルから導出されるシンボルを含み、出力シンボルは、送信機によって受信機に送信されるシンボルを含む。そのような乗算プロセスを定義するための多くの可能性のうち、我々は、２つの特定の可能性、すなわち、単純変換およびインターリーブ変換に焦点を置く。
【００３６】
＜単純変換＞
この場合、乗算プロセスは、有限体ＧＦ（２Ｍ）からの元と、長さＭビットのシンボルＳとの間で定義される。本明細書において使用される”シンボル”は、概してソースブロックよりも小さい１つのデータを指す。多くの場合、シンボルのサイズはビットで測られることができ、シンボルはＭビットのサイズを有し、シンボルは２Ｍ個のシンボルのアルファベットから選択される。パケットネットワークを介した情報の高信頼の伝送の応用において、各パケットが１つまたは複数のシンボルを含むように、例えば、シンボルのサイズはパケットサイズに等しい可能性があるか、またはシンボルのサイズはより小さい可能性がある。
【００３７】
単純変換の場合、シンボルＳは、ＧＦ（２Ｍ）の元と解釈され、乗算ａ＊Ｓは、体ＧＦ（２Ｍ）内の通常の乗算として定義される。シンボルに対して実行される演算は、シンボルの”単純変換”と呼ばれる。例示的な例として、体ＧＦ（４）を考える。ＧＦ（４）の元は、例えば、それらの元の２進展開によって２ビットで表されることができる。体ＧＦ（４）は４つの体の元００、０１、１０、１１を有し、加算はビット列の通常の排他的論理和であり、乗算は以下の表によって定義される。
2009527949.tif 000003
上記の乗算表によれば、１０＊０１の結果は、０１が体の乗算の単位元（恒等元と呼ばれることもある）であるので１０である。
【００３８】
＜インターリーブ変換＞
インターリーブ変換を示すために、我々は、環の数学的概念を使用する。当業者によく知られているように、環は、２つの演算、加算および乗算が、これらの演算が分配法則を満たすように定義されるセットである。さらに、加法だけを考えたセットがアーベル群を形成し、すなわち、加法の結果が加数の順番と無関係であり、加法に関する単位元０が存在し、各元に対して、それらの元の和が０であるような別の元が存在する。その他の要件は、乗算が単位元１を有し、したがって、任意の元と１との乗算がその元の値を変えないことである。通常の環に関して、我々は、任意の非ゼロの元が乗算の逆元を有することを要求せず、我々は、乗算が可換であることも要求しない。しかし、これらの条件が両方満足されるとき、我々は、その環を”体”と呼ぶ。この表記は、代数学の分野における標準的な表記である。
【００３９】
マッピング（シンボルに関する和）は、同じサイズのシンボルの対をそのサイズの別のシンボルにマッピングする、ハードウェア、ソフトウェア、データ記憶装置などで実装可能な論理構造である。我々は、□（□：○と＋を合成した記号を代替）によってこのマッピングを表記し、Ｓ□Ｔによってシンボルの対（Ｓ，Ｔ）に対するこのマッピングの像を表記する。そのようなマッピングの例は、ビット毎の排他的論理和（ＸＯＲ）である。
【００４０】
ここで使用される別の構造は、シンボルに対する特殊な種類のセットの”アクション”の構造である。Ａは、単位元を有し、あらゆる元に対してその元の加算の逆元を含む可換な加算演算”＋”を備えるセットであるものとする。そのようなセットは、通常、アーベル群とも呼ばれる。シンボルのセットに対するこの群の”アクション”は、群の元ｒおよびシンボルＳを含む対を別のシンボルにマッピングするマッピングである。我々はｒ＊Ｓによって像を表記し、このマッピングは群における加算を妨げず、すなわち、群Ａ内の元ａおよびｂのあらゆる対に対して、（ａ＋ｂ）＊Ｓ＝ａ＊Ｓ□ｂ＊Ｓである。Ａが環であり、アクションがＡにおける乗算をやはり妨げず（ここで、Ａにおける乗算の演算子は●である）、すなわち、（ａ●ｂ）＊Ｓ＝ａ＊（ｂ＊Ｓ）である場合、このアクションは、有限体の元とシンボルとの間の望ましい乗算プロセスである。この設定において、我々は、体がシンボルのセットに対して”機能する”と言う。このようにしてシンボルに対して実行される演算は”インターリーブ変換”と呼ばれる。
【００４１】
そのような乗算プロセスのあり余るほどの例が存在する。少数の例が以下で述べられる。例のこのリストは、例示的な目的でのみ述べられ、網羅的なリストとみなされるべきでなく、このリストは、本発明の範囲を限定すると解釈されるべきでもない。
【００４２】
加算が排他的論理和（ＸＯＲ）であり、乗算が論理演算ＡＮＤであるようにして、体の元０および１を有する体ＧＦ（２）は、１＊Ｓ＝Ｓおよび０＊Ｓ＝０を定義することによってシンボルのセットに対して機能し、ここで、Ｓは任意のシンボルを表し、０は全てゼロであるシンボルを表す。
【００４３】
体ＧＦ（４）は、以下のやり方で偶数のサイズのシンボルに対して機能することができる。そのようなシンボルＳに対して、我々はそのシンボルＳの前半と後半とをＳ［０］およびＳ［１］によってそれぞれ表し、したがって、Ｓ＝（Ｓ［０］，Ｓ［１］）はＳ［０］およびＳ［１］の連結である。そのとき、我々は、
2009527949.tif 000004
と定義する。
【００４４】
これが確かに妥当な演算であることは直ぐに確かめられることができる。体の乗算の表は、２ビットシンボルの場合、上で定義された演算に一致する演算を示すことが理解されることができる。
【００４５】
代替として、体ＧＦ（４）は、以下のやり方で偶数のサイズのシンボルに対して機能することができる。そのようなシンボルＳに対して、我々は、Ｓ内の偶数の位置のビットの連結をＳ［０］によって表し、同様に、我々は、Ｓ内の奇数の位置のビットの連結をＳ［１］によって表す（ここで、位置は、０から始まる番号を順番に振られる）。２つの等しい長さのビット列ＡおよびＢに関して、（Ａ｜Ｂ）が２倍の長さのビット列Ｃであるように定義されるものとし、ここで、Ｃの位置２＊ｉのビットはＡの位置ｉのビットであり、Ｃの位置２＊ｉ＋１のビットはＢの位置ｉ＋１のビットである。そのとき、我々は、
2009527949.tif 000005
と定義する。
【００４６】
これが確かに妥当な演算であることは直ぐに確かめられることができる。２ビットシンボルの場合、上で定義された全ての演算は同じであることが理解されることができる。
【００４７】
上述のインターリーブ変換は、体の元の２進数の長さがビットで表したシンボルの長さと一致するインターリーブ変換の特定の場合とみなされることができ、シンボルに対する体の元の演算は、有限体における乗算と同じである。
【００４８】
より一般的に、Ｋが度数ｄのＧＦ（２）の拡大体である場合、体の演算は、サイズがｄで割り切れるシンボルに対して定義されることができる。そのような演算は、Technical Report Number TR-95-048 of the International Computer Science Institute in Berkeley, 1995として発行された、ブローマー（Bloemer）、カルファン（Kalfane）、カーピンクシ（Karpinksi）、カープ（Karp）、ルビー（Luby）、およびズッカーマン（Zuckerman）による論文”An XOR-based erasure resilient coding scheme”に記載されている。このスキームは、体Ｋのいわゆる”正則表現”を２進数の成分を有するｄ×ｄマトリックスとして使用する。
【００４９】
これらの一般化のために、第１のインターリーブ変換は、長さｄ＊ｌビットの列であるＳをｄ個の等しいサイズの部分に分割し、第１の部分Ｓ［０］はＳの最初のｌビットであり、Ｓ［１］はＳの次のｌビットであり、Ｓ［ｄ−１］はＳの最後のｌビットである。変換は、Ｓのｄ個の部分に対して機能し、演算の結果を形成するために一緒に連結されるｄ個の部分を生成する。代替的に、第２のインターリーブ変換はＳをｄ個の等しいサイズの部分に分割し、第１の部分Ｓ［０］はＳ内の位置０から始まるＳのｄ個おきのビットの連結であり、第２の部分Ｓ［１］はＳ内の位置１から始まるＳのｄ個おきのビットの連結であり、ｄ番目の部分Ｓ［ｄ−１］はＳ内の位置Ｌ−１から始まるＳのｄ個おきのビットの連結である。この第２の変換は、（第１の変換と全く同じ）Ｓのｄ個の部分に対して機能し、演算の結果を形成するために一緒にインターリーブされるｄ個の部分を生成する。
【００５０】
第１のインターリーブ変換は、元の列Ｓの連続するビットを一緒にＸＯＲ演算することによって計算されることができ、これは、概してＣＰＵがそのような演算をネイティブサポートするソフトウェア実装のために有益であることに留意されたい。その一方、演算の結果の特定の位置のビットの値は元の列Ｓの長さに依存し、これは、ハードウェアの演算がシンボル長に応じて異なる必要があるので、人が、可変長シンボルをサポートするハードウェアで演算を実行したい場合には多少不利である。第２のインターリーブ変換は、元の列の連続しないビットを一緒にＸＯＲ演算することを含み、これは、概してＣＰＵがそのようなＸＯＲをネイティブな演算としてサポートしないソフトウェア実装に対しては多少不利であることに留意されたい。しかしながら、シンボルの有限体の元を直接処理するソフトウェア演算は、ソフトウェアでかなり効率的に実行されることができ、したがって、第２のインターリーブ変換のソフトウェア実装が可能である。さらに、第２のインターリーブ変換に関して、演算の結果の特定の位置のビットの値は元の列Ｓの長さに依存せず、これは、ハードウェアの演算がシンボル長に無関係であることができるので、人が、可変長シンボルをサポートするハードウェアで演算を実行したい場合に有益である。したがって、第２のインターリーブ変換は、第１のインターリーブ変換に優るいくつかの全体的な利点を確かに有する。
【００５１】
＜線形変換＞
”線形変換”の概念が、単純変換またはインターリーブ変換に関して定義されることができる。所与の整数ｍおよびｎに対して、演算によって引き起こされる線形変換は、特定の体の成分を有するマトリックスの空間を使用してｎ個のシンボルのベクトルをｍ個のシンボルのベクトルにマッピングする。体Ｆ上のマトリックスは成分の２次元の集合であり、マトリックスの成分はＦに属する。マトリックスがｍ行およびｎカラムを有する場合、通常、そのマトリックスはｍ×ｎマトリックスと呼ばれる。対（ｍ，ｎ）は、マトリックスの”型”と呼ばれる。同じ型のマトリックスは、基礎となる体または環の加算および減算を使用して加算および減算されることができる。型（ｍ，ｎ）のマトリックスは、よく知られているように、型（ｎ，ｋ）のマトリックスと乗算されることができる。演算中、Ｂが型（ｍ，ｎ）を有するマトリックスを表し、Ｂ［ｊ，ｋ］が位置（ｊ，ｋ）のＢの成分を表す場合、およびＳがシンボルＳ１、Ｓ２、．．．、Ｓｎを含む列ベクトルを表し、ＸがシンボルＸ１、Ｘ２、．．．、Ｘｍを含む列ベクトルを表す場合、変換は、
2009527949.tif 000006
のように表されることができる。
【００５２】
したがって、以下の関係が成り立つ。
【００５３】
１からｍまでの全てのｊに対して、
2009527949.tif 000007
ここで、”＊”は、単純変換またはインターリーブ変換のいずれかを表す。
【００５４】
上記の式は、以下のステップによって実行されることができる”単純変換プロセス”と呼ばれる、符号化器または復号化器においてＢおよびＳからＸを計算するためのプロセスを記述する。
【００５５】
１．ｊを１に設定し、Ｘｊを０に設定する。
【００５６】
２．１からｎまでのｋの値に対して、
2009527949.tif 000008
を行う。
【００５７】
３．ｊを１増やす。ｊがｍを超える場合は停止し、そうでなければステップ２に行く。
【００５８】
そのような線形変換は、様々な応用においてよくある。例えば、１つのデータまたはソースブロックを符号化するために線形符号を使用するとき、Ｓは符号化されるべきソースブロックのソースシンボルである可能性があり、ＸはＳの符号化されたバージョンである可能性があり、Ｂは符号の生成マトリックスである可能性がある。例えば、使用される符号が組織的であるその他の応用において、ＸはＳの符号化の冗長シンボルである可能性がある一方、Ｂはソースシンボルに対する冗長シンボルの依存性を示すマトリックスである可能性がある。
【００５９】
当業者に知られているように、汎用プロセッサ内で実行される命令のプロビジョンを通じてか、特に上述の演算を実行するように設計されたハードウェアを通じてか、またはそれら両方の組合せを通じてかのいずれかでそのような演算を実行するための方法が知られている。全ての場合で、要求される命令の数、要求されるハードウェアの量、ハードウェアのコスト、演算によって消費される電力、および／または演算を実行するために要求される時間の観点で、演算のコストは、より大きな有限体が使用されるとき、概してより大きくなる。具体的には、体ＧＦ（２）の場合、要求される演算は、汎用プロセッサ内で広く提供されるビット毎のＡＮＤおよびＸＯＲ演算と同等であり、単純で、高速で、必要とされる場合にハードウェアで実行するためのコストが安い。対称的に、ＧＦ（２）より大きな有限体を使用する演算は、汎用プロセッサで直接提供されることはほとんどなく、特殊なハードウェアか、または実行するためのいくつかのプロセッサ命令およびメモリ操作かのいずれかを必要とする。
【００６０】
＜多体消去および誤り訂正符号＞
多体消去および誤り訂正符号の多くの特定の実施形態が、一般化されたマトリックスの記述に言及することによって本明細書において説明される。このアプローチは、説明の道具として取り上げられるだけであり、本明細書において説明される実施形態を説明するための唯一のやり方を表すものではなく、このアプローチは、本発明の範囲を限定すると解釈されるべきでもない。一般化された記述において、元が１つまたは複数の有限体から得られるマトリックスが構築される。異なる元が、全ての体が組み込まれることができる単一の体が存在し、特定のそのような組み込みが選択されるという特性を有する異なる有限体から得られることができる。出力シンボルの一部もしくは全ては、以下でさらに示されるように、選択された特定の実施形態に応じて、入力シンボルもしくは冗長シンボルの一部と同一である可能性があるか、または入力シンボルおよび冗長シンボルと異なる可能性がある。
【００６１】
１対１の対応が、符号の入力シンボルと、マトリックスのカラムの一部との間で作成される。さらなる１対１の対応が、符号の冗長シンボルと、マトリックスの残りのカラムとの間で作成される。さらに、冗長シンボルの数に等しいマトリックスのいくつかの行が、スタティックな行として指定される。マトリックスの残りの行は、ダイナミックな行として指定される。１対１の対応が、マトリックスのダイナミックな行と、符号の出力シンボルとの間で作成される。この説明において、スタティックな行は、入力シンボルと冗長シンボルとの間で変化しないことを要求される制約を表し、スタティックな行は、入力シンボルおよびスタティックな行が分かっていれば冗長シンボルを構築するのに十分であるように入力シンボルと冗長シンボルとの間の関係を完全に定義する。ダイナミックな行は、チャネル上で実際に送信される出力シンボルを表す。多くの符号において、入力シンボルおよび／または冗長シンボル自体が送信され、これは、送信されるべき各入力および冗長シンボルに関するダイナミックな行を加えることによってこの記述において表され、前記ダイナミックな行は、要求される入力または冗長シンボルに対応するカラムに非ゼロの成分を有し、残りのカラムにゼロの成分を有する。一部の実施形態において、非ゼロの成分は単位元である。その他の実施形態において、この非ゼロの成分は単位元である必要はない。
【００６２】
上述の形態のマトリックスは、通信チャネルを介した送信元から送信先への伝送のためにデータを符号化する方法を決定するために使用されることができ、方法は、入力シンボルの順序付けられたセットから複数の冗長シンボルを生成することであって、各冗長シンボルが、有限体上の係数を用いた、入力シンボルおよびその他の冗長シンボルのうちの１つまたは複数に対する線形制約のセットに基づいて生成され、前記線形制約がマトリックスの記述のスタティックな行に対応する、複数の冗長シンボルを生成することと、入力シンボルおよび冗長シンボルの合成セットから複数の出力シンボルを生成することであって、各出力シンボルが、有限体から選択された係数を用いた、入力シンボルおよび冗長シンボルの合成セットのうちの１つまたは複数の一次結合として生成され、前記線形制約がマトリックスの記述のダイナミックな行に対応する、複数の出力シンボルを生成することと、複数の生成された出力シンボルの少なくとも一部を送信することとを含む。
【００６３】
逆に、上記のステップを含む方法は、スタティックな行が入力シンボルおよび冗長シンボルのうちの１つまたは複数に対する線形制約に対応し、ダイナミックな行が、出力シンボルを形成するために使用される入力シンボルおよび出力シンボルの一次結合に対応する上述の種類のマトリックスを用いて記述されることができる。実際には、上述の方法の実施形態は、説明されたマトリックスの明示的または暗黙的表現または構築を含まない可能性がある。
【００６４】
よく知られているように、マトリックスの全ての要素が体ＧＦ（２）から得られる場合、よく知られている誤り訂正および消去訂正符号の大きな分類は、このやり方で説明されることができる。例えば、例えば、www.inrialpes.frで入手可能な、INRIA Research Report RR-5225, June 2004として発行された、Ｖ．ロカ（Roca）およびＣ．ニューマン（Neumann）による”Design, Evaluation and Comparison of Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and LDGM Triangle, plus a Reed-Solomon Small Block FEC Codec”というタイトルの論文（以降、”ロカ”と呼ばれる）に記載の低密度パリティ検査（ＬＤＰＣ）符号を含むＬＤＰＣ符号の場合、一般化されたマトリックスは、パリティ検査マトリックスのあらゆる行をスタティックな行として指定し、上述のように各入力および冗長シンボルに関するさらなるダイナミックな行を加えることによってパリティ検査マトリックスから構築されることができる。別の例は、マトリックス内のスタティックな行の数がゼロであり、ダイナミックな行が標準形の連鎖反応マトリックスを含む、ルビーＩおよびルビーＩＩに記載のシングルステージ（１段）連鎖反応符号を使用する可能性がある。別の例はＭＳＣＲ符号の使用であり、その場合、ここでの一般化された記述は、そのような符号の標準形のマトリックス表示と同等である。
【００６５】
より大きな体上のその他の符号も、このようにして記述されることができる。例えば、入力シンボルがソースシンボルであり、一般化されたマトリックスがヴァンデルモンドマトリックスに等しく、全ての行がダイナミックであり、この場合、各成分が、少なくとも、存在する行およびカラムの総数と同じだけ多くの元をその乗法群に有する体、例えば、行およびカラムの総数が２５６未満であるときの有限体ＧＦ（２５６）からの有限体の元である、ヴァンデルモンドマトリックスから導出されるリードソロモン符号などのリードソロモン符号。別の例は、ヴァンデルモンドマトリックスから導出される、ＧＦ（２５６）などの有限体上の組織的リードソロモン符号であり、その場合、入力シンボルはソースシンボルであり、冗長シンボルはパリティシンボルであり、マトリックスは、ヴァンデルモンドマトリックスの組織的な形態内のパリティシンボルに対応する行であり、全てのそのような行はスタティックとみなされ、追加的なダイナミックな行が上述のように各ソースおよびパリティシンボルに関して追加され、その理由は、これらが正にチャネルを介して送信されるシンボルであるからである。
【００６６】
誤りおよび消去訂正符号の分野に精通した者によく知られているように、誤りおよび消去訂正の望ましい特性は、低い符号化の複雑性、低い復号化の複雑性、低い復号誤り確率、および低いエラーフロアを含む。符号の複雑性は、符号を符号化または復号化するために必要とされる計算リソースの目安である。低い複雑性は、符号化または復号化が、移動体端末、家庭用電化製品、記憶装置、または多くの符号化もしくは復号化演算を同時に処理する可能性があるデバイスなどのリソースを制限されたデバイスによって実行されるべきである応用において特に重要である。計算の複雑性は、部分的に、符号を符号化および復号化するために使用されるマトリックスの密度、ならびにマトリックスの要素が得られる有限体のサイズの関数である。概して、密なマトリックスはより高い複雑性をもたらし、このことは、疎なマトリックスに基づく符号の多くの設計、例えば、低密度パリティ検査符号および連鎖反応符号をもたらした。より大きな有限体もより高い複雑性をもたらし、そのことは、小さな体、最も一般的にはＧＦ（２）に基づく符号の多くの設計をもたらした。
【００６７】
この文脈における誤り確率は、完全に正常である復号化が不可能である確率である。所与の誤り訂正または消去訂正符号に対する誤り確率は、チャネル上で受信される情報、および復号化のために使用される特定のアルゴリズムによって変わる。消去訂正符号の場合、誤り確率は、入力シンボルの数よりも少ないシンボルが受信されるときはいつも１である。理想的な消去符号は、誤り確率が、受信されるシンボルの数が入力シンボルの数よりも多いか、または入力シンボルの数に等しいときはいつも０である特性を有する。その他の符号は、この場合に非ゼロの失敗の確率を有する。
【００６８】
理想的な消去符号、特にリードソロモン符号は、密なマトリックスを使用して構築されることができることが知られている。しかし、リードソロモン符号の場合、要求される体のサイズは、入力シンボルおよび冗長シンボルの数の和である符号サイズの関数であり、概して、この事実はマトリックスの密度と共に、特に符号サイズが大きくなるにつれて高い計算の複雑性をもたらす。さらに、低密度符号の場合、より大きな有限体が、（例えば、IEEE Communications Letters, volume 2, number 6, pages 165-167, 1998に掲載された、Ｍ．Ｃ．デービー（Davey）およびＤ．Ｊ．Ｃ．マッカイ（MacKay）による論文”Low Density Parity Check Codes over GF(q)”のように）誤り訂正符号に関する誤り確率を小さくし、消去符号に関する誤り確率を小さくするために使用されることができることが知られている。さらに、少数の高密度マトリックスの行またはカラムの低密度符号への導入が誤り確率を改善することができ、誤り確率と複雑性との間の折り合いを付けることができることが知られている［ＭＳＣＲ符号および連鎖反応符号］。しかし、全てのそのような符号の難点は、低い複雑性と低い誤り確率との間の重大なトレードオフが常に存在することである。
【００６９】
多くのＦＥＣ符号、すなわち、ＬＤＰＣ符号および連鎖反応符号およびＭＳＲＣ符号に関して、入力シンボルの数よりも多くの出力シンボルが受信されるにつれて、正常な復号化に関する誤り確率がある速度で急激に減少する。そのような符号のエラーフロアは、追加的な出力シンボルの受信が、受信出力シンボル数が入力シンボル数を初めて超えるときよりも大幅に遅い速度で誤り確率を小さくする誤り確率である。少数の高密度の行もしくはカラムの使用、および／またはマトリックスに対するより大きな有限体の使用が、より高い計算の複雑性を代償としてより低いエラーフロアをもたらすことができることが知られている。低い複雑性を有する多くの知られている誤りおよび消去訂正符号の難点は、エラーフロアが、望まれるよりも高いことである。
【００７０】
本明細書において、上述の難点の一部に対処する、誤り訂正および消去訂正符号の構築のための新規の方法が説明される。そのような符号の効率的な符号化および復号化のための方法が、例として本明細書において説明される特定の実施形態に関連して示される。
【００７１】
本明細書において説明される、２つ以上のあり得る体のセットからの、マトリックスの要素に対する体の選択は、より大きな体上の符号の低い誤り確率およびエラーフロアと共に小さな体上の符号の低い計算の複雑性を維持する符号の設計を可能にし、したがって、最新技術に優る重大な利点を示す。
【００７２】
以下でより詳細に説明される１つの好ましい実施形態において、大部分の行に関して成分がＧＦ（２）から選択され、残りの行に関して成分がＧＦ（２５６）から選択される。別の実施形態において、各行に関して、ちょうど１つの成分がＧＦ（２５６）から選択され、残りの要素がＧＦ（２）から選択される。
【００７３】
全ての元が同じ体から選択される当技術分野で知られている符号と比較して計算の複雑性と誤り確率およびエラーフロアとの間のトレードオフの改善をもたらす、２つ以上の体からの元の使用の多くのその他のあり得る実施形態が存在する。
【００７４】
本明細書で使用される用語”ファイル”は、１個以上のソースを格納し１以上の転送先にユニットとして配信される任意のデータを示している。したがって、文書、画像、およびファイルサーバまたはコンピュータ記憶装置からのファイルは、すべて、転送される”ファイル”の例である。ファイルは、既知のサイズ（例えばハードディスクに保存される１メガバイトの画像）でもよいし、未知のサイズ（例えばストリーミングソースの出力から取得されるファイル）でもよい。いずれの場合においても、ファイルは一連の入力シンボルであり、各々の入力シンボルはファイル内の位置および値を有する。
【００７５】
本明細書で使用される用語”ストリーム”は、１個以上のソースを格納もしくは生成された順番に各時点で特定のレートで１以上の転送先に配信される任意のデータを示している。ストリームは、固定レートまたは可変レートでありえる。したがって、ＭＰＥＧ映像ストリーム、ＡＭＲ音声ストリーム、遠隔装置の制御に使用されるデータストリームは全て転送される”ストリーム”の例である。各時点でのストリームのレート（速度）は、既知（例えば４メガビット／秒）でもよいし、未知（例えば各時点のレートが前もって分からない可変レートのストリーム）でもよい。いずれの場合においても、ストリームは一連の入力シンボルであり、各々の入力シンボルはストリーム内の位置および値を有する。
【００７６】
転送は、ファイルまたはストリームを配信するために１以上の送信機から１以上の受信機までチャネルを介してデータを送信する処理である。また、送信機を符号化器と称することもある。１台の送信機が完全なチャネルにより任意数の受信機に接続している場合、受信データは入力ファイルまたはストリームの正確なコピーであり、全てのデータが正しく受信される。ここでは、現実のチャネルの多くの場合と同様、チャネルが完全でないと仮定する。多くのチャネルの欠点の中で、重要な２つの欠点は、データ消去およびデータ消去の特殊例とみなすことが可能なデータ不完全性である。データ消去は、チャネルが消去またはデータがドロップした場合に発生する。データ不完全性は、いくつかのデータが素通りした後まで受信機がデータを受信し始めない場合、転送が終了する前に受信機がデータを受信するのを止めた場合、受信機が一部の送信データのみを受信することを選択する場合、および／または、受信機が断続的に停止し再度データを受信する場合に発生する。データ不完全性の例としては、移動衛星送信機が入力ファイルまたはストリームを示すデータを送信している場合、受信機が受信可能範囲内に入る前に転送を始めるかもしれない。一旦受信機が受信可能範囲内に入ると衛星が動いて受信可能範囲外に出るまでデータを受信することが出来、受信可能範囲に入ってきた他の衛星により送信されている同じ入力ファイルまたはストリームの受信を開始するために（データを受信していない間の期間に）衛星アンテナの向きを変えるかもしれない。本明細書を読むことにより明らかになるべきであるが、データ不完全性はデータ消去の特殊な場合であり、受信者はデータ不完全性（および受信者が同じ問題を有する）を、あたかも全期間にわたって受信者は受信範囲内に存在したが受信者がデータ受信を開始した点まで全データのチャネルを見失ったように取り扱うことが出来る。また、通信システム設計では良く知られているように、検出可能な誤りを、検出可能な誤りを有する全てのデータブロックあるいはシンボルを単に欠落させることにより消去と等価として考慮することが出来る。
【００７７】
いくつかの通信システムにおいて、受信者は、多数の送信者によってまたは並列に接続する１台の送信者により生成されるデータを受信する。たとえば、ダウンロードの速度を上げるために、受信者は、同時に同じファイルに関与するデータを送信する複数の送信機に接続するかもしれない。別の例では、マルチキャスト転送において、多数のマルチキャストデータストリームは、受信者が１以上のこれらのストリームに接続可能なように接続しているチャネルの帯域幅の集約転送速度を送信者と適合させるように送信されるかもしれない。この種の全ての場合において、懸念は、全ての送信データの確保は、受信者に独立な用途であるということである。すなわち、伝送速度が異なるストリームに対し非常に異なるときであっても、また、損失の任意のパターンがあるときであっても、複数のソースデータはストリーム間で冗長ではないということである。
【００７８】
一般に、通信チャネルは、データ転送のため送信機と受信機とを接続する。通信チャネルはリアルタイムチャネルでありえ、チャネルはデータを得るとすぐに送信機から受け側までデータを移動する。または、通信チャネルは、送信機から受け側までいくつかまたは全てのデータを通過途中に格納する格納チャネルであるかもしれない。後者の実施例は、ディスク記憶装置または他の記憶装置である。その例においては、データを生成するプログラムまたはデバイスを送信機として見る事が出来、記憶装置にデータを送信する。受信者は、記憶装置からデータを読み込むプログラムまたはデバイスである。送信機が記憶装置上へデータを得るために使用するメカニズム、記憶装置自体、受信者が記憶装置からデータを得るために使用するメカニズムは、集合としてチャネルを形成する。それらのメカニズムまたは記憶装置がデータを消去し得る可能性がある場合、それは通信チャネルのデータ消去とみなされるだろう。
【００７９】
送信者および受信者が、シンボルが消去され得る通信チャネルによって隔てられるとき、入力ファイルまたはストリームの正確なコピーを送信する代わりに、入力ファイルまたはストリームから生成され、消去の回復アシストするデータ（入力ファイルまたはストリームの全部または一部を含みうる）を送信しても良い。符号化器は、そのようなタスクを処理する回路、デバイス、モジュール、または符号セグメントである。１つの符号化器の動作を見る方法は符号化器が入力シンボルから出力シンボルを生成するということである。ここで、一連の入力シンボル値は入力ファイルまたはストリームのブロックを表す。各々の入力シンボルは、入力ファイルまたはストリームのブロックでの位置および値を有する。復号化器は、受信者により受信され、出力シンボルから入力シンボルを回復する回路、デバイス、モジュールまたはコードセグメントである。多段階符号化において、符号化器および復号化器は、各々が異なるタスクを実行するサブモジュールに更に分けられる。
【００８０】
多段階符号体系の実施例において、符号化器および復号化器はサブモジュールに更に分けられうる。そして、各々が異なるタスクを実行する。例えば、実施例によっては、符号化器は、本明細書においてスタティック符号化器およびダイナミック符号化器と称されるものを含む。本願明細書において使用しているように、”スタティック符号化器”は入力シンボルのセットから多数の冗長シンボルを生成する符号化器である。冗長シンボルの数は符号化の前に決定される。スタティック符号化している符号の例はリード−ソロモン符号、トルネード符号、ハミング符号、低密度パリティチェック（ＬＤＰＣ：Low Density Parity Check）符号、その他を含む。そして、本願明細書において、用語”スタティック復号化器”はスタティック符号化器によって符号化されたデータを復号化可能な復号化器を参照するために使用される。
【００８１】
本願明細書において使用しているように、”ダイナミック符号化器”は、入力シンボルおよび可能な冗長シンボルのセットから出力シンボルを生成する。好適な実施形態においては、可能な出力シンボルの数のオーダは入力シンボルの数より大きい。そして、生成される出力シンボル数は固定する必要はない符号化器である。ダイナミック符号化器の１つの実施例は、連鎖反応符号化器（例えばＬｕｂｙ  ＩおよびＬｕｂｙ  ＩＩに記載されている符号化器）である。本願明細書において、用語”ダイナミック復号化器”は、ダイナミック符号化器によって符号化されたデータを復号化可能な復号化器を参照するために使用される。
【００８２】
多体符号化の実施例は、いかなる特定の種類の入力シンボルに限定されることは無い。一般的に、入力シンボルの値は、ある自然数Ｍに対し２Ｍ個のシンボルのアルファベットから選択される。この種の場合、入力シンボルは、入力ファイルまたはストリームからデータの連続したＭビットにより表される。たとえば、Ｍの値は、アプリケーション、通信チャネルおよび／または出力シンボルのサイズに基づいて決定される。加えて、出力シンボルのサイズは、アプリケーション、チャネルおよび／または入力シンボルのサイズに基づいてしばしば決定される。場合によっては、出力シンボル値および入力シンボル値が同一サイズである場合（すなわち、同数ビットにより表現されるか同じアルファベットから選択される）、符号化処理は単純化されるかもしれない。この場合、出力シンボル値のサイズが制限される場合、入力シンボル値のサイズは制限される。たとえば、それは、制限されたサイズのパケットに出力シンボルを配置することを要求され場合である。受信機でキーを回復するために、出力シンボルに伴うキーについてのいくつかのデータが送信されることになっている場合、出力シンボルは、１つのパケットにおいて、キーについて出力シンボル値およびデータに対応するために好適には十分小さい。
【００８３】
一例として、入力ファイルが数メガバイトのファイルである場合、入力ファイルは、各々の入力シンボルを符号化している数千、何百または数バイトだけを有する、数千、数万または何十万もの入力シンボルに分解されるかもしれない。別の例としてパケットベースのインターネットチャネルのために、１０２４バイトのサイズのペイロードを有するパケットが適当かもしれない（１バイトは８ビットである）。この例では、各々のパケットが１個の出力シンボルおよび８バイトの補助情報を含む場合、８１２８ビット（（１０２４−８）＊８）の出力シンボルサイズが適当だろう。このように、入力シンボルサイズは、Ｍ＝（１０２４−８）＊８つまり８１２８ビットに選択される。別の例として、いくつかの衛星システムはＭＰＥＧパケット規格を使用する。ここで、各々のパケットのペイロードは１８８バイトを含む。この例において、各々のパケットが１個の出力シンボルおよび４バイトの補助情報を含む場合、１４７２ビット（（１８８−４）＊８）の出力シンボルサイズが適当だろう。このように、入力シンボルサイズは、Ｍ＝（１８８−４）＊８つまり１４７２ビットに選択される。汎用通信システムを使用している多段階符号化において、アプリケーション特有のパラメータ（例えば入力シンボルサイズ（すなわちＭ個の入力シンボルによって、符号化されるビット数）は、アプリケーションによって設定される変数であるかもしれない。
【００８４】
別の例として、可変サイズのソースパケットが使用されるストリームに対しては、各々のソースパケットが最高でも総サイズがソースパケットわずかに上回る入力シンボルの総数をカバーするように、小さなシンボルサイズが選択されうる。
【００８５】
各々の出力シンボルは、値を有する。下で考慮する好ましい実施例において、各々の出力シンボルは”キー”と呼ばれている識別子を結びつけられる。望ましくは、各々の出力シンボルのキーは、受け側がある出力シンボルと他の出力シンボルを区別できるために、受け側で容易に測定され得る。望ましくは、出力シンボルのキーは、他の全ての出力シンボルのキーとは異なる。従来技術においてキーイングにはさまざまな形式がある。たとえば、ルビーＩは、本明細書の実施例において使用され得るキーイングのさまざまな形式を記述している。
【００８６】
データ消去が予想される場合または転送の開始および終了に合わせて受信者が必ずしも受信の開始および終了をしていない場合に、多段階符号化は特に役立つ。後者は本明細書において、”データ不完全性”と呼ぶ。消去イベントとみなす事項において、多段階符号は、ルビーＩに記載されている連鎖反応符号化の利点の多くを共有する。特に、多段階符号はファウンテン符号またはレートレス符号であり得、この場合、入力シンボルより多くの区別される出力シンボルが固定値の入力シンボルのセットに対し生成され、任意の適切な数の区別される出力シンボルが入力シンボルの所望の精度での回復に使用され得る。多体多段階符号化が使われる場合、多段階符号化により生成される出力シンボルは情報付加的であるため、これらの状況は通信プロセスに悪影響を与えない。たとえば、１００個のパケットがデータ消去を引き起こす突然のノイズにより消去される場合、バースト後にさらなる１００個のパケットにより消去パケットのロスを置き換えることが出来る。送信機が送信を開始したときに受信機が同調していなかったことにより数１０００個のパケットがロスした場合に、受信機はただ単に転送の他の期間における数１０００パケットを取得すればよい。多体多段階符号化については、受信機はいかなるパケットの特定のセットにも制約されないので、ある送信機からいくつかのパケットを受信することができ、他の送信機に切替が可能であり、いくつかのパケットを失っても所与の転送の開始および終了をミスしても、入力ファイルおよびまたはストリームのブロックを再生することが出来る。受信機と送信機との間の協調を必要としない転送への参加および離脱の能力は、通信プロセスを単純化するのに役に立つ。
【００８７】
いくつかの実施形態では、多段階符号化を使用しているファイルまたはストリームの送信は、入力シンボルをストリームの入力ファイルまたはブロックから生成するか、形成するかまたは抽出することを含み、冗長シンボルを計算し、入力および冗長シンボルを１個以上の出力シンボルに符号化する。ここで、各々の出力シンボルは他の全ての出力シンボルと独立したキーに基づいて生成され、チャネルを介して１つ以上の受信者に出力シンボルを送信する。加えて、実施例によっては、多段階符号化を使用している入力ファイルまたはストリームのブロックのコピーの受信（および再構築）は、１以上のデータストリームからの出力シンボルのいくつかのセットまたはサブセットの受信、および、受信された出力シンボルの値及びキーからの入力シンボルの復号化を含む。
【００８８】
本明細書に記載されている適切なＦＥＣ消去符号化は、上述の問題点を克服するために用いられ、マルチメディア放送およびマルチキャストのシステム及びサービスに使用され得る。以後”多段階連鎖反応符号”と称するＦＥＣ消去符号は、この種のシステムおよびサービスの現在および将来の必要条件の多くを満たす特性を有する。
【００８９】
多体多段階連鎖反応符号のいくつかの基本特性は、任意のパケット損失状況、任意のサイズのソースファイルおよび任意の速度でのストリームの配信に対して、（ａ）個々の受信デバイス”ＲＤ”の受信オーバヘッドが最小化され、（ｂ）ソースファイルを任意数のＲＤに配信するための必要トータル転送時間を最小化でき、（ｃ）転送スケジュールの適切な選択について任意数のＲＤに対する配信ストリームの品質を、入力シンボル数に対する出力シンボル数が相対的に最大化される、ことである。ＲＤは、携帯デバイスでありえ、車両に埋め込まれるか、可搬型（すなわち、使用中に移動可能であるが通常は動いていない）か、または、場所に固定されているかもしれない。
【００９０】
復号化のために必要とされる作業メモリの量は少なく、かつ上述の特性を提供できる。そして、符号化および復号化に必要とされる計算の量は最小限である。本明細書において、シンプルかつ容易な多段階連鎖反応符号のいくつかのバリエーションを説明する。
【００９１】
多体多段階連鎖反応符号は、ファウンテン符号である。すなわち、必要に応じた数の符号化パケットをオンザフライで生成する。そして、各々は、ソースファイルまたはストリームのブロックを回復するのに等しく役立つ一意の符号化シンボルを含む。ＦＥＣ符号の他方式にかわりファウンテン符号を使用することには多くの利点がある。１つの利点は、パケット損失状況およびＲＤの有効性に関係なく、ファウンテン符号は、各々のＲＤがソースファイルまたはストリームのブロックを回復するために受信を必要とする符号化パケット数を最小化するということである。これは、厳しいパケット損失状況の下でさえあてはまり、移動機ＲＤが、たとえば、断続的に電源オンされる場合、あるいは、長いファイルダウンロードセッションにわたって利用できる。
【００９２】
他の利点は、転送が進行中である間、どれくらいの符号化パケットをオンザフライで生成するべきかについて決定でき、必要に応じて多くの符号化パケットを正確に生成する。これは、たとえばソースファイルかストリームのブロックを回復するのに十分な符号化パケットを受信したか否かを指示する応答がＲＤからある場合、役立つ。パケット損失状況が予想より厳しくない場合、転送は早く終了され得る。パケット損失状況が予想より厳しい場合、または、ＲＤが予想よりしばしば利用できない場合、転送はシームレスに延長され得る。
【００９３】
他の効果は、逆多重化の能力である。逆多重化により、ＲＤがソースファイルまたはストリームのブロックを回復するために独立した送信機で生成される符号化パケットを受信し組み合わせることが可能である。逆多重化の１つの利用は、異なる送信機から符号化パケットを受信することに関して以下に記載されている。
【００９４】
未来のパケット損失、ＲＤ有効性およびアプリケーション状況は、予測するのが難しく、予測不可能な状況の下で適切な動作が可能である柔軟なＦＥＣソリューションを選択することは重要である。多段階連鎖反応符号は、ＦＥＣ符号の他方式がマッチしない柔軟度を提供する。
【００９５】
多体多段階符号のさらなる利点は、符号の誤り確率およびエラーフロアが計算複雑度が同程度の既知の符号のものよりもより低いことである。同様に、多体多段階連鎖反応符号の計算複雑度は同程度の誤り確率および／またはエラーフロアを有する既知の符号のものよりも低い。
【００９６】
多体多段階連鎖反応符号の他の利点は、計算複雑度と誤り確率および／またはエラーフロアとの間の所望のバランスを達成するために、シンボルサイズや体サイズなどのパラメータをフレキシブルに選択可能なことである。本発明の態様は、次に図に関して記載されている。
【００９７】
＜システム概要＞
図１は、多段階符号化を使用する通信システム１００のブロック図である。通信システム１００において、入力ファイル１０１または入力ストリーム１０５は、入力シンボル生成器１１０に提供される。入力シンボル生成器１１０は入力されたファイルまたはストリームから１個以上の一連の入力シンボル（ＩＳ（０），ＩＳ（１），ＩＳ（２），．．．）を生成し、各入力シンボルは値および位置（図１の括弧内整数として示す）を有する。上述したように、入力シンボルの可能な値（すなわちアルファベット）は一般的に２Ｍ個のシンボルからなるアルファベットであり、各々の入力シンボルは入力ファイルまたはストリームのＭビットを符号化する。通常、Ｍの値は使用する通信システム１００により決定されるが、Ｍは用途により多様であるため汎用システムでは入力シンボル生成器１１０のためのシンボルサイズ入力を含むかもしれない。入力シンボル生成器１１０の出力は、符号化器１１５に提供される。
【００９８】
スタティックキー生成器１３０は、スタティックキーＳ０，Ｓ１．．．のストリームを生成する。通常、生成されるスタティックキーの数は制限されており特定実施形態の符号化器１１５に依存する。スタティックキーの生成は、以降で更に詳細に説明する。ダイナミックキー生成器１２０は、符号化器１１５により生成される各々の出力シンボルに対するダイナミックキーを生成する。各々のダイナミックキーは、同一の入力ファイルまたはストリームのブロックのダイナミックキーの大部分が一意（ユニーク）となるように生成される。たとえば、利用可能なキー生成器の実施形態がルビーＩに記載されている。ダイナミックキー生成器１２０およびスタティックキー生成器１３０の出力は、符号化器１１５に提供される。
【００９９】
ダイナミックキー生成器１２０によって提供された各々のキーＩから、符号化器１１５は、入力シンボル生成器により提供される入力シンボルから値Ｂ（Ｉ）の出力シンボルを生成する。符号化器１１５の動作については以下で更に詳細に説明する。各々の出力シンボルの値は、対応するキー、１個以上の入力シンボルの何らかの関数、おそらく入力シンボルから計算される冗長シンボルに基づいて生成される。ある特定の出力シンボルの源である入力シンボルおよび冗長シンボルの集合を、出力シンボルの”関連シンボル”または単にその”付随物（associates）”と呼ぶ。関数（”値関数”）および付随物の選択については、以降で更に詳細に記載されている処理に従って行われる。常にではないが、一般的にはＭは、入力シンボルおよび出力シンボルに対して同一である、すなわち、それら双方は同一ビット数に符号化する。
【０１００】
いくつかの実施形態では、符号化器１１５は付随物を選択するために入力シンボル数Ｋを使用する。入力がストリーミングファイルである場合のようにＫが前もって分からない場合には、Ｋは単に推定値であってもよい。また、値Ｋは、符号化器１１５により生成される入力シンボルおよび任意の中間シンボルの格納割り当てに、符号化器１１５により使用されるかもしれない。
【０１０１】
符号化器１１５は送信モジュール１４０に出力シンボルを提供する。また、送信モジュール１４０にはダイナミックキー生成器１２０から各々の出力シンボルのキーが提供される。送信モジュール１４０は出力シンボルを送信し、送信モジュール１４０は送信された出力シンボルのキーに関する何らかのデータを使用するキーイング方法に従いチャネル１４５を介して受信モジュール１５０に送信するかもしれない。チャネル１４５は消去チャネルであるとみなされるが、それは通信システム１００が適切に動作するための必要条件ではない。送信モジュール１４０がチャネル１４５に出力シンボルおよび対応するキーに関する必要データを送信するのに適合し、受信モジュール１５０がチャネル１４５からシンボルおよび対応するキーに関する何らかのデータを受信するのに適合してさえいれば、モジュール１４０、１４５および１５０は、適切なハードウェア構成要素、ソフトウェア構成要素、物理媒体またはそのいかなる組合せによっても実現可能である。Ｋの値は、付随物を決定するために用いられる場合、チャネル１４５を介して送信されるか、または、事前に符号化器１１５および復号化器１５５に対して予めセットしておいてもよい。
【０１０２】
上述したように、チャネル１４５はリアルタイムチャネル（例えば、インターネット、テレビ送信機からテレビ受信機への放送リンク、あるポイントから他のポイントへの電話接続）で有り得る他、チャネル１４５は格納チャネル（例えば、ＣＤ−ＲＯＭ、ディスク装置、ウェブサイト等）でも有り得る。さらに、チャネル１４５はリアルタイムチャネルおよび格納チャネルの組合せでも有り得、例えば、ある人がパソコンから電話回線を介してインターネットサービスプロバイダ（ＩＳＰ）まで入力ファイルを送信する際に形成されるチャネルのように、入力ファイルはウェブサーバに格納され、続いてインターネットを介して受け側に転送され得る。
【０１０３】
チャネル１４５が消去チャネルであると仮定されるので、システム１００において、受信モジュール１５０から出力される出力シンボルと送信モジュール１４０に入力される出力シンボルとは１対１の対応があると仮定することは出来ない。実際、チャネル１４５がパケット網を含む場合、２個以上のパケットの相対的順序がチャネル１４５を通過中に保存されることを仮定することさえ出来ないかもしれない。従って、出力シンボルのキーは上述の１以上のキーイング方法を利用して決定され、必ずしも受信モジュール１５０から出力される出力シンボルの順序で決定されるというわけではない。
【０１０４】
受信モジュール１５０は復号化器１５５に出力シンボルを提供し、受信モジュール１５０が受信するこれらの出力シンボルのキーに関する任意のデータはダイナミックキー再生器１６０に提供される。ダイナミックキー再生器１６０は、受信された出力シンボルのダイナミックキーを再生し、復号化器１５５にダイナミックキーを提供する。スタティックキー生成器１６３は、スタティックキーＳ０，Ｓ１．．．を再生し、復号化器１５５に提供する。スタティックキー生成器は、符号化および復号化プロセスの双方で使用する乱数生成器１３５にアクセスする。これは、この種のデバイスにより乱数が生成される場合、同一物理装置へのアクセスの形式でもよいし、同一の挙動となるように同一の乱数生成アルゴリズムへのアクセスの形式でもよい。復号化器１５５は、ダイナミックキー再生器１６０およびスタティックキー生成器１６３により提供される出力シンボルに対応するキーを使用し、入力シンボル（ＩＳ（０），ＩＳ（１），ＩＳ（２），．．．）を回復する。復号化器１５５は、入力ファイル１０１または入力ストリーム１０５のコピー１７０を生成する入力ファイル再構築器１６５に回復した入力シンボルを提供する。
【０１０５】
連鎖反応符号化器により生成された出力シンボルの１つの特性は、十分な出力シンボルを受信するとすぐに受信機がオリジナルファイルやオリジナルストリームのブロックを回復できることである。特に、高確率でオリジナルのＫ個の出力シンボルを回復するために、受信機はＫ＋Ａ個のおよそ出力シンボルが必要になる。比率Ａ／Ｋは”相対受信オーバヘッド”と呼ばれる。相対受信オーバヘッドは入力シンボルの数Ｋと復号化器の信頼性に依存する。ルビーＩ，ルビーＩＩおよびショクロラヒＩはこのような実施形態で利用可能なシステムおよび方法の教えを提供する。しかしながら、理解されるべきであるが、これらのシステムおよび方法は本発明に必要なものではなく、他の多くのバリエーション、修正物、代替物も使用されうる。
【０１０６】
＜符号化器＞
図２は、図１に示される符号化器１１５の一特定実施例のブロック図である。符号化器１１５は、スタティック符号化器２１０、ダイナミック符号化器２２０、および、冗長計算機２３０を備えている。スタティック符号化器２１０は、以下の入力を受信する。
【０１０７】
ａ）入力シンボル生成器１１０により提供され入力シンボルバッファ２０５に格納されたオリジナルの入力シンボルＩＳ（０），ＩＳ（１），ＩＳ（２），．．．，ＩＳ（Ｋ−１）
ｂ）オリジナルの入力シンボルの数Ｋ
ｃ）スタティックキー生成器１３０により提供されるスタティックキーＳ０，Ｓ１，．．．
ｄ）冗長シンボルの数Ｒ
スタティック符号化器２０５は、これらの入力を受信するとすぐに、後述するようにＲ個の冗長シンボルＲＥ（０），ＲＥ（１），．．．，ＲＥ（Ｒ−１）を計算する。常にではないが一般的に冗長シンボルは入力シンボルと同じサイズである。一特定実施例において、スタティック符号化器２１０により生成される冗長シンボルは、入力シンボルバッファ２０５に格納される。入力シンボルバッファ２０５は論理的なものでもよい。すなわち、ファイルまたはストリームのブロックは１つの場所に物理的に格納してもよいし、入力シンボルのシンボルバッファ２０５内の位置は、ただ単にオリジナルのファイルまたはストリームのブロック内のシンボルの位置の名称変更でもよい。
【０１０８】
ダイナミック符号化器は、入力シンボルおよび冗長シンボルを受信し下記に詳述されているように出力シンボルを生成する。冗長シンボルが入力シンボルバッファ２０５に格納される一実施例においては、ダイナミック符号化器２２０は入力シンボルバッファ２０５から入力シンボルおよび冗長シンボルを受信する。
【０１０９】
冗長計算機２３０は、入力シンボルの数Ｋから冗長シンボルの数Ｒを計算する。この計算は下記に詳述されている。
【０１１０】
＜スタティック符号化器の概要＞
スタティック符号化器２１０の一般動作は図３および図４に示される。図３は、スタティック符号化の方法一実施例の簡略フローチャートを例示している。ステップ３０５において、変数ｊ（どれだけ冗長シンボルが生成されたかについての情報を保持する）はゼロにセットされる。そして、ステップ３１０では、第１の冗長シンボルＲＥ（０）は少なくともいくつかの入力シンボルＩＳ（０），．．．，ＩＳ（Ｋ−１）の関数Ｆ０として計算される。それから、ステップ３１５で、変数ｊはインクリメントされる。次に、ステップ３２０で、冗長シンボルの全てが生成されたか（すなわち、ｊがＲ−１より大きいか？）どうかが検査される。もしＹｅｓの場合はフローは終了する。そうでなければ、フローは、ステップ３２５へ進む。ステップ３２５において、ＲＥ（ｊ）は入力シンボルＩＳ（０），．．．，ＩＳ（Ｋ−１）および以前に生成された冗長シンボルＲＥ（０），．．．，ＲＥ（ｊ−１）の関数Ｆｊとして計算される。ここで、Ｆｊは入力シンボルの何れかまたは冗長シンボルの何れかに依存する関数である必要はない。ステップ３１５、３２０および３２５はＲ個の冗長シンボルが計算されるまで繰り返される。
【０１１１】
再度図１および図２を参照すると、実施例によっては、スタティック符号化器２１０はスタティックキー生成器１３０から１個以上のスタティックキーＳ０，Ｓ１．．．を受信する。これらの実施例では、スタティック符号化器２１０は、いくつかまたは全部の関数Ｆ０，Ｆ１，．．．Ｆｊ−１を決定するためにスタティックキーを使用する。たとえば、スタティックキーＳ０は関数Ｆ０を決定するために利用可能であり、スタティックキーＳ１は関数Ｆ１を決定するために利用可能である。もしくは、１個以上のスタティックキーＳ０，Ｓ１，．．．を関数Ｆ０を決定するために利用可能であり、１個以上のスタティックキーＳ０，Ｓ１，．．．を関数Ｆ１を決定するために利用可能である。他の実施態様では、スタティックキーは必要でなく、スタティックキー生成器１３０は必要でない。
【０１１２】
次に図２および図３を参照すると、実施例によっては、スタティック符号化器２１０により生成される冗長シンボルは、入力シンボルバッファ２０５に格納されてもよい。図４は、スタティック符号化器２１０の一実施例の動作の簡略図である。特に、スタティック符号化器２１０は、入力シンボルバッファ２０５から受信した入力シンボルＩＳ（０），．．．，ＩＳ（Ｋ−１），ＲＥ（０），．．．，ＲＥ（ｊ−１）の関数Ｆｊとして、冗長シンボルＲＥ（ｊ）を生成する。そして、入力シンボルバッファ２０５の中に戻し格納する。関数Ｆ０，Ｆ１，．．．，ＦＲ−１の正確な形式は、特定の用途に依存する。常ではないが一般的には、関数Ｆ０，Ｆ１，．．．，ＦＲ−１は、関連するいくつかあるいは全ての引数の排他的論理和を含んでいる。上述の通り、これらの関数は実際に図１のスタティックキー生成器１３０により生成されるスタティックキーを使用するかもしれないし使用しないかもしれない。たとえば、後述する一特定実施例では、最初のいくつかの関数はハミング符号を実装し、スタティックキーＳ０，Ｓ１，．．．を全く使用しない。また、残りの関数は低密度パリティチェック符号を実装し、スタティックキーを明示的に利用する。
【０１１３】
＜多段階符号化器の概要＞
再度図２を参照すると、ダイナミック符号化器２２０は、入力シンボルＩＳ（０），．．．，ＩＳ（Ｋ−１）および冗長シンボルＲＥ（０），．．．，ＲＥ（Ｒ−１）および各々の出力シンボルのキーＩを受信する。この集合はオリジナルの入力シンボルおよび冗長シンボルを含んでおり、今後”ダイナミック入力シンボル”の集合と呼ぶ。図５はダイナミック符号化器の一実施例の簡略ブロック図であり、重みセレクタ５１０、アソシエータ５１５、値関数セレクタ５２０および計算機５２５を含む。図５に示すように、Ｋ＋Ｒ個のダイナミック入力シンボルはダイナミックシンボルバッファ５０５に格納される。実質的に、ダイナミック符号化器５００は図６に例示される動作を実行する。すなわち、選択された入力シンボルの何らかの値関数として出力シンボル値Ｂ（Ｉ）を生成する。
【０１１４】
図７は、スタティック符号化器の一特定実施例の簡略ブロック図である。スタティック符号化器６００は、パラメータ計算機６０５、低密度パリティチェック（ＬＤＰＣ）符号化器６１０および高密度パリティチェック（ＨＤＰＣ）符号化器６２０を備えている。ＬＤＰＣ符号化器６１０は、入力シンボルバッファ６２５からの入力シンボルＩＳ（０），．．．，ＩＳ（Ｋ−１）、入力シンボルの数Ｋ、および、パラメータＥを受信するように接続される。そして、ＬＤＰＣ符号化器６１０は、ＬＤＰＣ符号に従ってＥ個の冗長シンボルＬＤ（０），．．．，ＬＤ（Ｅ−１）を生成する。次に、ＨＤＰＣ符号化器６２０は、ＨＤＰＣ符号に従ってＤ個の冗長シンボルＨＡ（０），ＨＡ（１），．．．，ＨＡ（Ｄ−１）を生成するために、複数のＫ＋Ｅ個のシンボルＩＳ（０），．．．，ＩＳ（Ｋ−１），ＬＤ（０），．．．，ＬＤ（Ｅ−１）およびパラメータＤを受信するように接続される。
【０１１５】
図８は、図７に示されるスタティック符号化器を使用する一実施例の動作を例示する。
【０１１６】
図９は、パラメータ計算機（例えば図７のパラメータ計算機６０５）の一実施例の簡略フローチャートであり、ＨＤＰＣ符号がハミング符号の場合、上述のパラメータＤおよびＥを計算する。最初に、ステップ７０５で、パラメータＤは１に初期化される。そして、ステップ７１０で、２Ｄ−Ｄ−１がＫ未満かどうかが判定される。ＮＯの場合フローはステップ７３０へ進む。ＹＥＳの場合フローはステップ７２０へ進み、パラメータＤはインクリメントされる。それから、フローはステップ７１０へ進む。Ｄが決定されると、ステップ７３０で、Ｒ−Ｄ−１としてパラメータＥが算出される。
【０１１７】
図１０は本発明の一実施例に従うこのような符号化器の簡略フローチャートであり以下に説明する。最初に、ステップ８０５で、変数ｉはゼロに初期化される。変数ｉは、すでに生成される冗長シンボルの数の情報を得続ける。ステップ８１０において、数ｔは、Ｋ／２以上の最も少ない奇数の整数として算出される。ステップ８１５において、値Ｐ１，Ｐ２，．．．，Ｐｔは、Ｋ、ｔおよびスタティックキーＳｉに基づいて生成される。値Ｐ１，Ｐ２，．．．，Ｐｔは、冗長シンボルを生成するために用いる入力シンボルの位置を指示する。ある特定の実施例では、図５のアソシエータ５１５のようなアソシエータは、Ｐ１，Ｐ２，．．．，Ｐｔを生成するために用いる。特に、Ｗ（Ｉ）個の入力として値ｔは提供され、Ｋ＋Ｒ個の入力として値Ｋは提供される。そして、スタティックキーＳｉはキーＩの入力として提供される。ｔの多くの異なる値が類似した符号化効果を得る点に留意する必要がある。このように、この特定の選択は１つの例にすぎない。ステップ８２０において、ＲＥ（ｉ）の値は、値ＩＳ（Ｐ１），ＩＳ（Ｐ２），．．．，ＩＳ（Ｐｔ）のＸＯＲとして計算される。ステップ８２５において、変数ｉは次の冗長シンボルの計算を準備するために１だけインクリメントされる。そして、ステップ８３０で、全ての冗長シンボルが計算されたかどうかは判定される。そうでない場合には、フローはステップ８１５に戻る。
【０１１８】
図１１は、本発明による復号化器の簡略ブロック図を例示している図である。復号化器９００は、たとえば、図１の復号化器１５５を実装するために用いられる。
【０１１９】
復号化器９００は、ダイナミック復号化器９０５とスタティック復号化器９１０を備えている。ダイナミック復号化器９０５により回復される入力シンボルおよび冗長シンボルは、回復バッファ９１５に格納される。ダイナミック復号化終了後、スタティック復号化器９１０は、ダイナミック復号化器９０５により回復されない入力シンボルがあれば回復を試みる。特に、スタティック復号化器９１０は回復バッファ９１５からの入力シンボルと冗長シンボルを受信する。
【０１２０】
図１２は、本発明による復号化のための方法の簡略フローチャートを例示している図である。ステップ１００５において、Ｑ個の出力シンボルは、復号化器により受信される。Ｑの値は、入力シンボルの数および使用するある特定のダイナミック符号化器に依存する。Ｑの値は、また、復号化器が入力シンボルを回復できる所望の精度に依存する。たとえば、復号化器が高確率を有する入力シンボルの全てを回復できることが要求される場合、Ｑは入力シンボルの数より大きな数として選択される。特に、用途によっては、入力シンボルの数が大きいときに、Ｑは３％未満程度オリジナル入力シンボルの数より大きい。ほかの応用において、入力シンボルの数が少ないときに、Ｑは少なくとも１０％程度入力シンボルの数より大きい。具体的には、Ｑは入力シンボルの数Ｋに数Ａを加えた値として選ばれる。ここで、Ａは復号化器が高確率を有する入力シンボルの全てを再生させることができることを確保するために選ばれる。数Ａの決定は、下で更に詳細に記載されている。復号化器は入力シンボル（時々または常に）の全てを復号化することができないことを許容する場合、Ｑは、Ｋ＋Ａ未満でありえ、Ｋに等しくありえる、Ｋ未満でもありえる。明確に、全体の符号体系の１つの目的はしばしば可能な限り数Ｑを減少させることである、その一方で、所望の精度に関して復号プロセスの成功に関する良好な見込みに基づく保証を維持する。
【０１２１】
ステップ１０１０において、ダイナミック復号化器９０５は受信したＱ個出力シンボルから入力シンボルおよび冗長シンボルを再生する。ステップ１００５および１０１０が実質的に並行して実行されることができることは、よく理解されている。たとえば、ダイナミック復号化器９０５は、復号化器がＱ個の出力シンボルを受信する前に入力シンボルおよび冗長シンボルを再生させ始めることができる。
【０１２２】
ダイナミック復号化器９０５がＱ個の出力シンボルを処理したあと、入力シンボルが所望の精度に回復されたかどうかは判定される。所望の精度は、たとえば、全ての入力シンボルまたは全てより少ないいくつか、パーセンテージ、その他である。ＹＥＳの場合、フローは終わる。ＮＯの場合は、フローはステップ１０２０へ進む。ステップ１０２０において、スタティック復号化器９１０は、ダイナミック復号化器９０５が回復することができなかった入力シンボルの回復を試みる。スタティック符号化器９１０がダイナミック復号化器９０５により回復された入力シンボルおよび冗長シンボルを処理した後フローが終了する。
【０１２３】
図１３は、本発明による復号化のための方法の他の実施例を示している簡略フローチャートである。この実施例は、図１１に関して記載されたものと類似していて、共通のステップ１００５、１０１０、１０１５および１０２５を含む。しかし、ステップ１０２５の後、フローはステップ１０３０へ進む。そこにおいて、入力シンボルが所望の精度に回復されたかどうかは判定される。ＹＥＳの場合、フローは終了する。ＮＯの場合、フローはステップ１０３５へ進む。ステップ１０３５において、一つ以上の付加的な出力シンボルが受信される。それから、フローはステップ１０１０へ進行する。その結果、ダイナミック復号化器９０５および／またはスタティック復号化器９１０は残留する非回復の入力シンボルを回復することを試みることができる。
【０１２４】
図１４は、本発明による復号化のための方法のさらにもう一つの実施例を示している簡略フローチャートである。ステップ１０５５において、出力シンボルは復号化器により受信される。そして、ステップ１０６０で、ダイナミック復号化器９０５は受信された出力シンボルから入力シンボルおよび冗長シンボルを再生させる。それから、ステップ１０６５で、ダイナミック復号化が終了すべきかどうかが判定される。この判定は、処理した出力シンボルの数、回復した入力シンボルの数、付加的な入力シンボルが回復されている現在の速度、出力シンボルの処理に費やした時間は、その他の一つ以上に基づいて行われる。
【０１２５】
ステップ１０６５において、ダイナミック復号化を終了しないと決定される場合、フローはステップ１０５５へ進行する。しかし、ステップ１０６５において、ダイナミック復号化を終了すると決定される場合、フローはステップ１０７０へ進む。ステップ１０７０において、入力シンボルが所望の精度に回復されたかどうかが判定される。ＹＥＳである場合、フローは終了する。ＮＯの場合は、フローはステップ１０７５へ進む。ステップ１０７５において、スタティック復号化器９１０は、ダイナミック復号化器９０５が回復することができなかった入力シンボルの回復を試みる。スタティック符号化器９１０が、ダイナミック符号化器９０５によって回復された入力シンボルおよび冗長シンボルを処理した後、フローは終了する。
【０１２６】
図１５は、本発明によるダイナミック復号化器の一実施例を示す。ダイナミック復号化器１１００は、図５に示されるダイナミック符号化器５００と類似した構成要素を含む。復号化器１１００は、Ｌｕｂｙ  ＩおよびＬｕｂｙ  ＩＩに記載されている連鎖反応復号化器の実施例と類似している。ダイナミック復号化器１１００は、重みセレクタ５１０と、アソシエータ５１５と、値関数セレクタ５２０と、出力シンボルバッファ１１０５と、レデューサ１１１５と、再構築器１１２０と、再構築バッファ１１２５とを備える。
【０１２７】
図１６は、スタティック復号化器の一実施例の簡略ブロック図を示している。データが図７に関して記載されているスタティック符号化器などによって、符号化されるときに、この実施例を用いることができる。スタティック復号化器１２００は、ＬＤＰＣ復号化器１２０５とハミング復号化器１２１０を備えている。ＬＤＰＣ復号化器１２０５は回復バッファ１２１５から入力シンボルおよび冗長シンボルを受信する。そして、ダイナミック復号化器の復号ステップの後、回復バッファ１２１５の未回復のシンボルの回復を試みる。いくつかの実施形態では、回復バッファ１２１５は、回復バッファ１１２５（図１５）である。
【０１２８】
ＬＤＰＣ復号化器およびハミング復号化器の多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。１つの特定実施例において、ハミング復号化器は、ガウス消去アルゴリズムを使用して行う。ガウス消去アルゴリズムの多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。
【０１２９】
＜ＨＤＰＣ符号化のバリエーション＞
ここで、別の種類のＨＤＰＣ符号化が説明される。ＨＤＰＣ符号化のこの実施形態において、データの所与のセットから冗長シンボルを作成するための数学的演算は、有限体における演算に基づく。
【０１３０】
ＨＤＰＣ符号化のこの実施形態において、有限体の元が、冗長シンボルＨＤ［０］、．．．、ＨＤ［Ｄ−１］を得るために使用される。これらのシンボルは、上述のようにシンボルＩＳ［０］、．．．、ＩＳ［Ｋ−１］、ＬＤ［０］、．．．、ＬＤ［Ｅ−１］と有限体の元との間の乗算プロセスを定義することによって得られる。
【０１３１】
＜ＨＤＰＣ符号化＞
ＨＤＰＣ符号を使用するとき、符号は、有限体ＧＦ（２Ｍ）上の生成マトリックスによって記述される可能性がある。符号が組織的である（このことは好ましい実施形態に当てはまる）場合、生成マトリックスは、Ｋ＋Ｅ個の入力シンボルＩＳ［０］、．．．、ＩＳ［Ｋ−１］、ＬＤ［０］、．．．、ＬＤ［Ｅ−１］と冗長シンボルＨＤ［０］、．．．、ＨＤ［Ｄ−１］との間の関係のみを使用して記述されることができる。Ｇと呼ばれるこのマトリックスは、型がＤ×（Ｋ＋Ｅ）である。ＸがシンボルＨＤ［０］、．．．、ＨＤ［Ｄ−１］を含む列ベクトルを表し、ＳがシンボルＩＳ［０］、．．．、ＩＳ［Ｋ−１］、ＬＤ［０］、．．．、ＬＤ［Ｅ−１］を含む列ベクトルを表す場合、我々は、Ｘ−Ｇ◇Ｓ（◇：○と×を合成した記号を代替）を得る。マトリックスＧ、およびシンボルの効率的な計算のための様々な方法に関するより具体的な実施形態が以下で説明される。
【０１３２】
＜バリエーション＞
上述の多段階連鎖反応符号は組織的符号ではない。すなわち、ソースブロックのオリジナルソースシンボルの全てが必ずしも送信される符号化シンボルであるというわけではない。しかしながら、組織的ＦＥＣ符号は、ファイルダウンロードシステムまたはサービスに役立ち、ストリーミングシステムまたはサービスにとって非常に重要である。下記の実施に示すように、変更を加えられた符号は、組織的で、まだファウンテン符号および他の記載されている特性を維持するよう実行されることができる。
【０１３３】
それが多段階符号を使用した補足的なサービスのバラエティが設計者に容易である一つの理由は、それが送信機の中の関連性の無いソースファイルまたはストリームを復元するために多数の送信機から符号化シンボルを受信して組み合わせることができるということである。唯一の必要条件は、送信機がそれらが符号のパケットを符号化する際に送信する符号化シンボルを生成するためのキーと異なるセットを使用するということである。これを達成する方法は、この種の各々の送信機によって、異なる範囲のキー空間を使用するか、または、各々の送信機でランダムにキーを生成することを含む。
【０１３４】
例えば、この能力の用途として、ファイルダウンロードセッションからソースファイルを復元するのに十分な符号化パケットを受信せず、送信機から例えば、ＨＴＴＰセッションを経て）付加的な符号化符号が送信されるよう要求する多段階連鎖反応符号を許容するファイルダウンロードサービスに対する補足的なサービスの提供を考える。送信機はソースファイルから符号化シンボルを生成し（例えばＨＴＴＰを使用して）送信し、ソースファイルを回復するため、これらの全ての符号化シンボルはファイルダウンロードセッションから受信されるものと混合されうる。このアプローチを使用することによって、異なる送信機同士が送信機間の調整を必要とせずインクリメント式ソースファイル配信サービスを提供でき、その各々の受信機は各々のソースファイルを回復するための符号化パケットを最低限の数だけ受信すればよい。
【０１３５】
上述した多段階連鎖反応符号の復号化は、ソースシンボル数が少ない場合に比較的大きなオーバヘッドを要し、例えば、数１０００のソースシンボルに対して１００のオーダである。このような場合、ショクロラヒＩＩＩに開示されるような復号化器のような異なる復号化器が望ましい。下記のような実装により、ショクロラヒＩＩＩに開示された符号の特徴およびコンセプトを用いる本明細書で開示される符号のクラスに対して修正された復号化アルゴリズムがデザインされ得、復号化の効率性を維持したまま、少ないソースシンボル数に対して低い復号化誤り確率を提供することができる。
【０１３６】
＜多段階符号のさまざまな段階の実現例＞
＜ＦＥＣ方式定義＞
これらの技術を使用しているパケットは、ヘッダ情報（例えばソースブロック番号（ＳＢＮ）（パケットの範囲内の符号化シンボルが関係するソースブロックのための１６ビット整数識別子）および符号化シンボルＩＤ（ＥＳＩ）（パケット内の符号化シンボルに対する１６ビット整数識別子）を含んでいる４オクテットのＦＥＣペイロードＩＤ）により表されるかもしれない。ソースブロック番号および符号化シンボルＩＤの１つの適切な解釈は、以下のセクションＢにおいて定義される。ＦＥＣオブジェクト転送情報は、ＦＥＣ符号化ＩＤ、転送長（Ｆ）および以下で定義されるパラメータＴ、Ｚ、ＮおよびＡを含みうる。パラメータＴおよびＺは１６ビット符号なし整数である、ＮおよびＡは８ビット符号なし整数である。
【０１３７】
ＭＢＭＳ前方誤り訂正のＦＥＣ符号化方式は、下記のセクションにおいて定義される。それは２つの異なるＦＥＣペイロードＩＤフォーマット（１つはＦＥＣ転送元パケットのため、もう１つはＦＥＣ修復パケットのため）を定義する。しかし、非組織的符号のバリエーションもまた可能である。
【０１３８】
転送元ＦＥＣペイロードＩＤは、ソースブロック番号（ＳＢＮ）（パケット内の符号化シンボルに関係するソースブロックに対する１６ビット整数識別子）および符号化シンボルＩＤ（ＥＳＩ）（パケット内の符号化シンボルに対する１６ビット整数識別子）を含むかもしれない。その一方で、修復ＦＥＣペイロードＩＤは、ソースブロック番号（ＳＢＮ）（パケット内の修復シンボルに関係するソースブロックに対する１６ビット整数識別子）、符号化シンボルＩＤ（ＥＳＩ）（パケット内の修復シンボルに対する１６ビット整数識別子）およびソースブロック長（ＳＢＬ）（１６ビット：ソースブロック内のソースシンボルの数を表す）を含みうる。ソースブロック番号、符号化シンボルＩＤおよびソースブロック長の解釈は、以下で定義される。
【０１３９】
ＦＥＣオブジェクト転送情報は、ＦＥＣ符号化ＩＤ、最大ソースブロック長（シンボル単位）およびシンボルサイズ（バイト単位）を含みうる。シンボルサイズおよび最大ソースブロック長は、シンボルサイズ（Ｔ）（１６ビット：符号化シンボルのサイズを表す（バイト単位））および最大ソースブロック長（１６ビット：ソースブロックの最大長を表す（シンボル単位））の４オクテットフィールドを含み得る。
【０１４０】
下記のセクションでは、組織的多体ＭＳＣＲ前方誤り訂正符号の適用を指定する。多体ＭＳＣＲはファウンテン符号である。すなわち、符号化器はブロックのソースシンボルからオンザフライで必要なだけ多数のソースシンボルを生成することが出来る。復号化器は、ソースシンボルの数よりわずかに多いいかなる符号化シンボルのセットからもソースブロックを回復可能である。本明細書に記載されている符号は組織的符号であり、修復シンボルと同じ数だけオリジナルソースシンボルは受信機に送信機から変形されずに送信される。
【０１４１】
＜Ｂ．１  定義、記号および略号＞
＜Ｂ．１．１  定義＞
本明細書において以下の用語および定義を適用する。
【０１４２】
ソースブロック：ＭＳＣＲ符号化の目的で一緒に考慮されるＫ個のソースシンボルのブロック。
【０１４３】
ソースシンボル：符号化プロセスの間使用されるデータの最小単位。ソースブロック内の全てのソースシンボルは同一のサイズである。
【０１４４】
符号化シンボル：データパケットに含まれるシンボル。符号化シンボルは、ソースシンボルおよび修復シンボルを含む。ソースブロックから生成される修復シンボルは、ソースブロックのソースシンボルと同様に同一のサイズである。
【０１４５】
組織的符号：ソースブロックのため送信される符号化シンボルの一部としてソースシンボルが含まれる符号。
【０１４６】
修復シンボル：ソースブロックのため送信されるソースシンボルでない符号化シンボル。修復シンボルはソースシンボルに基づいて生成される。
【０１４７】
中間シンボル：逆の符号化プロセスを使用してソースシンボルから生成されるシンボル。修復シンボルは中間シンボルから直接生成される。符号化シンボルは中間シンボルを含まない。すなわち、中間シンボルはデータパケットに含まれない。
【０１４８】
シンボル：データの単位。バイトで表現されるサイズはシンボルサイズとして既知である。
【０１４９】
符号化シンボルグループ：一緒に送られる符号化シンボルグループ。すなわち、同一パケット内においてソースシンボルに対する関係が単一の符号化シンボルＩＤに由来するものである。
【０１５０】
符号化シンボルＩＤ：符号化シンボルグループのシンボルとソースシンボルの関係を定義する情報。
【０１５１】
符号化パケット：符号化シンボルを含むデータパケット。
【０１５２】
サブブロック：ソースブロックはサブブロックに分解され、それぞれは作業メモリ内において復号化されるために十分に小さい。Ｋ個のソースシンボルを含むソースブロックに対して、各々のサブブロックはＫ個のサブシンボルを含み、ソースブロックの各シンボルは各サブブロックの１個のサブシンボルから構成される。
【０１５３】
サブシンボル：シンボルの一部。各ソースシンボルは、ソースブロック内のサブブロックである多くのサブシンボルから構成される。
【０１５４】
ソースパケット：ソースシンボルを含むデータパケット。
【０１５５】
修復パケット：修復シンボルを含むデータパケット。
【０１５６】
＜Ｂ．１．２  記号＞
ｉ、ｊ、ｘ、ｈ、ａ、ｂ、ｄ、ｖ、ｍ：自然数を表す
ｃｅｉｌ（ｘ）：ｘ以上である最小の自然数を表す
ｃｈｏｏｓｅ（ｉ，ｊ）：繰り返しのないｉ個のオブジェクトの中からｊ個のオブジェクトを選択する方法の数を表す
ｆｌｏｏｒ（ｘ）：ｘ以下である最大の自然数を表す
ｉ％ｊ：ｉモジュロｊを表す
Ｘ＾Ｙ：等しい長さのビット列ＸおよびＹに対し、ＸとＹとのビット毎の排他論理和を表す
Ａ：シンボル配列パラメータを表し、シンボルおよびサブシンボルのサイズはＡの倍数に制限される
ＡＴ：Ａの転置行列を表す
Ａ−１：Ａの逆行列を表す
Ｋ：１個のソースブロック内にあるシンボルの数を表す
ＫＭＡＸ：１つのソースブロック内にあるソースシンボルの最大数を表し、８１９２に設定される（他の値も使用され得る）
Ｌ：１つのソースブロックに対する予め符号化されるシンボルの数を表す
Ｓ：１つのソースブロックに対するＬＤＰＣシンボルの数を表す
Ｈ：１つのソースブロックに対するハーフシンボルの数を表す
Ｃ：中間シンボル（Ｃ［０］，Ｃ［１］，Ｃ［２］，．．．，Ｃ［Ｌ−１］）の配列を表す
Ｃ’：ソースシンボル（Ｃ’［０］，Ｃ’［１］，Ｃ’［２］，．．．，Ｃ’［Ｋ−１］）の配列を表す
Ｘ：負でない整数値を表す
Ｖ０、Ｖ１：４バイト整数の２つの配列、Ｖ０［０］，Ｖ０［１］，．．．，Ｖ０［２５５］およびＶ１［０］，Ｖ１［１］，．．．，Ｖ１［２５５］を表す
Ｒａｎｄ［Ｘ、ｉ、ｍ］：擬似乱数生成器である
Ｄｅｇ［ｖ］：度数生成器である
ＬＴＥｎｃ［Ｋ、Ｃ、（ｄ、ａ、ｂ）］：ＬＴ符号化シンボル生成器である
Ｔｒｉｐ［Ｋ、Ｘ］：トリプル生成関数である
Ｇ：符号化シンボル群内のシンボルの数である
Ｎ：ソースブロック内のサブブロックの数である
Ｔ：シンボルサイズ（バイト）であり、ソースブロックがサブブロックに区切られているとき、Ｔ＝Ｔ’・Ｎである
Ｔ’：サブシンボルサイズ（バイト）であり、ソースブロックがサブブロックに区切られていないときＴ’は関連しない
Ｆ：ファイルダウンロードのときのファイルサイズ（バイト）である
Ｉ：サブブロックサイズ（バイト）である
Ｐ：ファイルダウンロードの場合、各パケットのペイロードサイズ（バイト）であり、ファイルダウンロード転送パラメータの推奨導出に使用される。ストリーミングの場合、各修復パケットのペイロードサイズ（バイト）であり、ストリーミング転送パラメータの推奨導出に使用される
Ｑ：Ｑ＝６５５２１、すなわち、Ｑは２１６未満の最大の素数である（２１６以外の他の値も使用され得る）
Ｚ：ファイルダウンロードのときのソースブロックの数である
Ｊ（Ｋ）：Ｋに関連する組織的インデックスである
Ｇ：任意の生成行列を表す
ＩＳ：Ｓ×Ｓの恒等行列を表す
０Ｓ×Ｈ：Ｓ×Ｈの零行列を表す
＜Ｂ．１．３  略号＞
本明細書において以下の略号を用いる。
【０１５７】
ＥＳＩ（Encoding Symbol ID）：符号化シンボルＩＤ
ＬＤＰＣ（Low Density Parity Check）：低密度パリティチェック
ＬＴ（Luby Transform）：ルビー変換
ＳＢＮ（Source Block Number）：ソースブロック番号
ＳＢＬ（Source Block Length）：ソースブロック長（シンボル単位）
＜Ｂ．２  概要＞
これら各々のアプリケーションに特定されるＭＳＣＲ前方誤り訂正符号は、ファイル配信およびストリーミングアプリケーションの双方に適用可能である。ＭＳＣＲ符号の態様は、本明細書のセクションＢ．３およびＢ．４で述べる。
【０１５８】
組織的ＭＳＣＲ符号の構成要素は、セクションＢ．５に記載されている基本的な符号化器である。第１に、中間シンボルについての知識がソースシンボルを復元するのに十分であるように、どのようにオリジナルソースシンボルから一組の中間シンボルの値を導き出すかが記述される。第２に、符号化器は、各々多数の中間シンボルの排他的論理和である修復シンボルを作成する。符号化シンボルは、ソースおよび修復シンボルの組合せである。中間シンボル従ってまたソースシンボルはいかなる十分に大きい符号化シンボル群からも回復可能となるように修復シンボルは生成される。
【０１５９】
本明細書は、組織的ＭＳＣＲ符号化器を定義する。多くの考えられる復号化アルゴリズムが利用可能である。効率的な復号化アルゴリズムは、セクションＢ．６において提供される。
【０１６０】
中間のおよび修復シンボルの組立の一部分は、セクションＢ．５に記載されている擬似乱数生成器に基づく。この生成器は、送信機および受信機の双方で利用できる５１２の乱数の固定セットに基づく。数のセットの実施例は、付録Ｂ．１およびＢ．２において提供される。
【０１６１】
最後に、ソースシンボルからの中間シンボルの組立は、”組織的インデックス”により支配される。組織的インデックスの値の実施例セットは、４個のソースシンボルからＫＭＡＸ＝８１９２個のソースシンボルまでのソースブロックサイズに対するものが付録Ａに示される。
【０１６２】
＜Ｂ．３  ファイルダウンロード＞
＜Ｂ．３．１  ソースブロック構築＞
＜Ｂ．３．１．１  全般＞
ＭＳＣＲ符号化器をソースファイルに適用するために、ファイルはＺ（≧１）個のブロック（ソースブロックとして知られる）として分解されうる。ＭＳＣＲ符号化器は、それぞれに各々のソースブロックに適用される。各々のソースブロックは一意な整数のソースブロック番号（ＳＢＮ）であり、第１のソースブロックのＳＢＮは０、第２は１などである。各々のソースブロックは各々のサイズがＴバイトのソースシンボルの数（Ｋ）に分割される。各々のソースシンボルは一意の整数の符号化シンボル識別子（ＥＳＩ）であり、ソースブロックの第１のソースシンボルのＥＳＩは０、第２は１などである。
【０１６３】
Ｋ個のソースシンボルを有する各々のソースブロックはＮ（≧１）個のサブブロックに分けられる。それは作業メモリにおいて復号化されるのに十分小さい。各々のサブブロックは、サイズＴ’のＫ個のサブシンボルに区分される。
【０１６４】
ファイルの各々のソースブロックの値に対してＫの値が必ずしも同一であるというわけではない点、および、ソースブロックの各々のサブブロックに対してＴ’が必ずしもの同一であるというわけではない点に注意する。しかしながら、ファイルの全てのソースブロックに対してシンボルサイズＴは同一であり、ソースブロックのあらゆるサブブロックに対してシンボル数Ｋは同一である。ファイルの、ソースブロックおよびサブブロックへの正確な分割は、後述のＢ．３．１．２に記載されている。
【０１６５】
図１７は二次元行列に配置されたソースブロックの例を示す。ここで、各々のエントリはＴ’バイトのサブシンボルであり、各々の列はサブブロックであり、各々の行はソースシンボルである。この例では、Ｔ’の値は、あらゆるサブブロックに対して同一である。各々のサブシンボルのエントリに示される数は、ソースブロック中でのオリジナルの順番を示している。たとえば、Ｋの番号をつけられたサブシンボルは、ソースブロックのＴ’・ＫからＴ’・（Ｋ＋１）−１個までのバイトを含む。そして、ソースシンボルｉは、各々のサブブロックからの第ｉのサブシンボルの連結であり、ｉ、Ｋ＋ｉ、２・Ｋ＋ｉ、．．．、（Ｎ−１）・Ｋ＋ｉの番号をつけられたソースブロックのサブシンボルに対応する。
【０１６６】
＜Ｂ．３．１．２  ソースブロックとサブブロック分割＞
ソースブロックおよびサブブロックの構築は、Ｆ、Ａ、Ｔ、Ｚ、Ｎの５個のパラメータおよび関数Ｐａｒｔｉｔｉｏｎ［］に基づいて決定される。５個のパラメータは次のように定義される。
【０１６７】
Ｆ：ファイルサイズ（バイト）である
Ａ：シンボル配列パラメータ（バイト）である
Ｔ：シンボルサイズ（バイト）であり、必ずＡの倍数となる
Ｚ：ソースブロックの数である
Ｎ：各ソースブロック内のサブブロックの数である
これらのパラメータは、ｃｅｉｌ（ｃｅｉｌ（Ｆ／Ｔ）／Ｚ）≦ＫＭＡＸとなるようにセットされる。これらのパラメータのいくつかの適正な導出例がセクションＢ．３．４において提供される。
【０１６８】
関数Ｐａｒｔｉｔｉｏｎ［］は一対の整数（Ｉ、Ｊ）を入力として４整数（ＩＬ、ＩＳ、ＪＬ、ＪＳ）を導出する。具体的には、Ｐａｒｔｉｔｉｏｎ［Ｉ、Ｊ］の値は、４整数のシーケンス（ＩＬ、ＩＳ、ＪＬ、ＪＳ）であり、ＩＬ＝ｃｅｉｌ（Ｉ／Ｊ）、ＩＳ＝Ｆｌｏｏｒ（Ｉ／Ｊ）、ＪＬ＝Ｉ−ＩＳ・Ｊ、ＪＳ＝Ｊ−ＪＬである。Ｐａｒｔｉｔｉｏｎ［］は、サイズＩのブロックをほぼ等しいＪのブロックに分割するパラメータを導出する。具体的には、長さＩＬのＪＬ個のブロックと長さＩＳのＪＳ個のブロックである。
【０１６９】
ソースファイルは、以下の通りにソースブロックおよびサブブロックに仕切られる。
【０１７０】
Ｋｔ＝ｃｅｉｌ（Ｆ／Ｔ）のとき
（ＫＬ、ＫＳ、ＺＬ、ＺＳ）＝Ｐａｒｔｉｔｉｏｎ［Ｋｔ，Ｚ］
（ＴＬ、ＴＳ、ＮＬ、ＮＳ）＝Ｐａｒｔｉｔｉｏｎ［Ｔ／Ａ，Ｎ］
それから、ファイルは、Ｚ＝ＺＬ＋ＺＳ個の隣接するソースブロックに仕切られ、最初のＺＬ個のソースブロックは各々ＫＬ・Ｔバイトであり、残りのＺＳ個のソースブロックは各々ＫＳ・Ｔバイトである。
【０１７１】
Ｋｔ・Ｔ＞Ｆのとき、符号化の目的で、最後のシンボルは最後がＫｔ・Ｔ−Ｆ個のゼロバイトでパディングされる。
【０１７２】
次に、各々のソースブロックはＮ＝ＮＬ＋ＮＳ個の隣接するサブブロックに仕切られ、最初のＮＬ個のサブブロックは各々ＴＬ・ＡのサイズのＫ個の隣接するサブシンボルを含み、残りのＮＳ個のサブブロックは各々ＴＳ・ＡのサイズのＫ個の隣接するサブシンボルを含む。シンボル配列パラメータＡは、サブシンボルが常にＡバイトの倍数であることを確保する。
【０１７３】
最後に、ソースブロックの第ｍ番目のシンボルは、各々Ｎ個のサブブロックから第ｍ番目のサブシンボルの連結を含む。
【０１７４】
＜Ｂ．３．２  符号化パケット構築＞
＜Ｂ．３．２．１  全般＞
各々の符号化パケットは、ソースブロック番号（ＳＢＮ）、符号化シンボルＩＤ（ＥＳＩ）、符号化シンボル、の情報を含む。各々のソースブロックは、他と独立してそれぞれに符号化される。ソースブロックはゼロから連続的に番号をつけられる。０からＫ−１の符号化シンボルＩＤ値によりソースシンボルを識別する。Ｋ以降の符号化シンボルＩＤは修復シンボルを識別する。
【０１７５】
＜Ｂ．３．２．２  符号化パケット構築＞
各々の符号化パケットは、好ましくは、ソースシンボル（ソースパケット）あるいは修復シンボル（修復パケット）のいずれかを含む。パケットは、同じソースブロックから任意数のシンボルを含むことができる。オブジェクトを符号化しているＦＥＣにパケットの最後のシンボルがパディングバイトを含む場合、これらのバイトはパケットに含まなくてもよい。そうでない場合、全シンボルが含まれる。
【０１７６】
各々のソースパケットにより転送される符号化シンボルＩＤ、Ｘは、そのパケットにおいて保持される最初のソースシンボルの符号化シンボルＩＤである。パケットの次のソースシンボルは順序付けられた符号化シンボルＩＤ、Ｘ＋１からＸ＋Ｇ−１を有し、ここで、Ｇはパケット内のシンボルの数である。
【０１７７】
同様に、修復パケットに格納された符号化シンボルＩＤ、Ｘは、修復パケットの最初の修復シンボルの符号化シンボルＩＤであり、パケットの次の修復シンボルは順序付けられた符号化シンボルＩＤ、Ｘ＋１からＸ＋Ｇ−１を有し、ここで、Ｇはパケット内のシンボルの数である。
【０１７８】
ここで、受信機が修復パケットの合計数を知ることは必要でない点に注意する。修復シンボルのＧ個の修復シンボルトリプル（ｄ［０］，ａ［０］，ｂ［０］），．．．，（ｄ［Ｇ−１］，ａ［Ｇ−１］，ｂ［Ｇ−１］）は、ＥＳＩ  Ｘを有する修復パケット内に配置され、以降のＢ．５．３．４において定義されるトリプル生成器を使用して計算される。
【０１７９】
各々のｉ＝０，．．．，Ｇ−１に対して、
（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）＝Ｔｒｉｐ［Ｋ，Ｘ＋ｉ］
ＥＳＩ  Ｘを有する修復パケットに配置されるＧ個の修復シンボルは、セクションＢ．５．３にて説明したように、中間シンボルＣおよびＬＴ符号化器ＬＴｅｎｃ［Ｋ，Ｃ，（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）］を用い修復シンボルトリプルに基づいて計算される。
【０１８０】
＜Ｂ．３．３  転送＞
このセクションは、ＭＳＣＲ符号化器／復号化器間の情報交換を記載し、ファイル配信のためのＭＳＣＲ前方誤り訂正を利用する任意の転送プロトコルが使用できる。
【０１８１】
ファイル送出のためのＭＳＣＲ符号化器および復号化器は、転送プロトコルから以下の情報を必要とする。バイト単位のファイルサイズ、Ｆ、シンボル配列パラメータ、Ａ、シンボルサイズ（Ｔ）（バイト単位でＡの倍数である）、ソースブロックの数、Ｚ、各々のソースブロックのサブブロックの数、Ｎ。ファイル配信のためのＭＳＣＲ符号化器は、加えて、符号化されるファイルがＦバイトであることを必要とする。
【０１８２】
ＭＳＣＲ符号化器は、各々のパケットのために、ＳＢＮ、ＥＳＩおよび符号化シンボルを含む符号化パケット情報を転送プロトコルに出力する。転送プロトコルは透過的にＭＳＣＲ復号化器にこの情報を伝える。
【０１８３】
＜Ｂ．３．４  パラメータの特定例の詳細＞
＜Ｂ．３．４．１  パラメータ導出アルゴリズム＞
このセクションは良好な結果をもたらす４つの転送パラメータＡ，Ｔ，ＺおよびＮの導出例を提供する。これらは以下の入力パラメータに基づいている。
【０１８４】
Ｆ：ファイルサイズ（バイト）
Ｗ：サブブロックサイズ目標（バイト）
Ｐ：最大のパケットペイロードサイズ（バイト）、Ａの倍数であると仮定される
Ａ：シンボル配列ファクタ（バイト）
ＫＭＡＸ：ソースブロック当たりのソースシンボルの最大数
ＫＭＩＮ：ソースブロック当たりのシンボルの最小目標数
ＧＭＡＸ：パケット当たりのシンボルの最大目標数
上記の入力に基づいて、転送パラメータＴ、ＺおよびＮは、以下の通りに算出される。
【０１８５】
Ｇ＝ｍｉｎ｛ｃｅｉｌ（Ｐ・ＫＭＩＮ／Ｆ），Ｐ／Ａ，ＧＭＡＸ｝−パケット当たりの平均シンボル数
Ｔ＝ｆｌｏｏｒ（Ｐ／（Ａ・Ｇ））・Ａ
Ｋｔ＝ｃｅｉｌ（Ｆ／Ｔ）−ファイル内の総シンボル数
Ｚ＝ｃｅｉｌ（Ｋｔ／ＫＭＡＸ）
Ｎ＝ｍｉｎ｛ｃｅｉｌ（ｃｅｉｌ（Ｋｔ／Ｚ）・Ｔ／Ｗ），Ｔ／Ａ｝
ＧおよびＮの値は上述のように導出され下限として考慮される。例えば、２の累乗に近似した数などに、これらの値を増やすことは、有利となり得る。特に、上記のアルゴリズムはシンボルサイズＴが最大パケットサイズＰを区分することを保証しない。そして、正確にＰのサイズのパケットが使用可能とはならない。その代わりに、Ｇは、Ｐ／Ａを区分する値として選択される場合、シンボルサイズＴはＰの因子である。そして、サイズＰのパケットが使うことができる。
【０１８６】
入力パラメータの適切な値は、Ｗ＝２５６ＫＢ  Ａ＝４  ＫＭＩＮ＝４  ＧＭＡＸ＝１、であり得る
＜Ｂ．３．４．２  例＞
上記のアルゴリズムは結果として図１８に示す転送パラメータをもたらす。そして、Ｗ、Ａ、ＫＭＩＮおよびＧＭＡＸに対する上述の値がＰ＝５１２とともに使用される。
【０１８７】
＜Ｂ．４  ストリーミング＞
＜Ｂ．４．１  ソースブロック構築＞
本明細書において定義したように、ソースブロックは転送プロトコルによって組み立てられる。そして、組織的ＭＳＣＲ前方誤り訂正符号を利用する。ソースブロックの組立および修復シンボルの組立に使われるシンボルサイズＴは転送プロトコルにより提供される。いかなるソースブロックについてもソースシンボルの数が最高でもＫＭＡＸであるために、パラメータＴがセットされるかもしれない。
【０１８８】
良好に動作するパラメータの例は、セクションＢ．４．４に示される。
【０１８９】
＜Ｂ．４．２  符号化パケット構築＞
Ｂ．４．３にて説明するように各々の修復パケットは、ＳＢＮ、ＥＳＩ、ＳＢＬおよび修復シンボルを含む。修復パケットの中で含まれる修復シンボルの数は、パケット長から計算される。修復パケットに入れられるＥＳＩ値および修復シンボルを生成するために用いる修復シンボルのトリプルは、セクションＢ．３．２．２にて説明したように、計算される。
【０１９０】
＜Ｂ．４．３  転送＞
このセクションは、ＭＳＣＲ符号化器／復号化器間の情報交換を記載し、ストリーミングのためのＭＳＣＲ前方誤り訂正を利用する任意の転送プロトコルが使用可能である。ストリーミングのためのＭＳＣＲ符号化器は、各々のソースブロックのための転送プロトコルから、シンボルサイズＴ（バイト）、ソースブロックのシンボル数Ｋ、ソースブロック番号（ＳＢＮ）、符号化されるソースシンボル（Ｋ・Ｔバイト）、の情報を使用するかもしれない。ＭＳＣＲ符号化器は、各々の修復パケットに対して、ＳＢＮ、ＥＳＩ、ＳＢＬおよび修復シンボルを含んでいる符号化パケット情報を転送プロトコルに出力する。転送プロトコルは透過的にＭＳＣＲ復号化器にこの情報を伝えるかもしれない。
【０１９１】
＜Ｂ．４．４  パラメータの選択＞
パラメータの選択について多くの方法が使用可能である。それらのいくつかを以下で詳細に説明する。
【０１９２】
＜Ｂ．４．４．１  パラメータ導出アルゴリズム＞
このセクションでは、以下の入力パラメータに基づく転送パラメータＴの導出について説明する。
【０１９３】
Ｂ：最大ソースブロックサイズ（バイト）
Ｐｍａｘ：パディングを含まないソースパケット情報サイズ（バイト）
Ｐｒ：パディングを含まないｘ番目のパーセントソースパケット情報サイズ（すなわち、パケットのｘ％となる最小数ｎはソースパケット情報サイズｎまたはそれ未満であることが期待される）
Ａ：シンボル配列ファクタ（バイト）
ＫＭＡＸ：ソースブロック当たりのソースシンボルの最大数
ＫＭＩＮ：ソースブロック当たりのシンボルの最小目標数
ＧＭＡＸ：修復パケット当たりのシンボルの最大目標数
これらの入力上の必要条件は、ｃｅｉｌ（Ｂ／Ｐ）≦ＫＭＡＸである。上記の入力に基づいて、転送パラメータＴは、以下の通りに算出される。
【０１９４】
Ｇ＝ｍｉｎ｛ｍａｘ｛ｃｅｉｌ（Ｐ・ＫＭＩＮ／Ｂ），ｆｌｏｏｒ（Ｐｘ／Ｐｍａｘ）｝，Ｐ／Ａ、ＧＭＡＸ｝−ＳＰＩ当たりのシンボル数
Ｔ＝ｆｌｏｏｒ（Ｐ／（Ａ・Ｇ））・Ａ
上で導出されるＴの値は、使用されるＴの実効値のガイドと思われなければならない。ＴをＰに分割することは有利でもあり得、または、フルサイズの修復シンボルが紛失したソースパケットの最後（ソースブロック内のソースシンボルの最大数ＫＭＡＸを超えない限り）にあるソースシンボルの一部を回復するために使用される場合、無駄を最小化するためにＴの値を小さく設定することは有利であり得る。さらに、Ｔの選択がソースパケットサイズの分布に依存するかもしれない。例えば、全てのソースパケットが同一サイズである場合、Ｔを、修復パケットＰ’の実際のペイロードサイズにすることは有利であり得る。ここで、Ｐ’はＴの倍数であり、ソースブロック内を占める各ソースパケットのバイト数に等しい（または、数バイトだけ大きい）。
【０１９５】
適切な入力パラメータの値は、Ａ＝１６，ＫＭＩＮ＝４，ＧＭＡＸ＝４，であり得る。
【０１９６】
＜Ｂ．４．４．２  例＞
Ａ、ＫＭＩＮおよびＧＭＡＸを上述の値と仮定しＰ＝１４２４を仮定した場合、上述のアルゴリズムは結果として図１９に示す転送パラメータをもたらす。
【０１９７】
＜Ｂ．５  組織的多体ＭＳＣＲ符号化器＞
＜Ｂ．５．１  符号化の概要＞
組織的ＭＳＣＲ符号化器は、Ｋ個のソースシンボルを含むソースブロックから修復シンボルを生成するために用いる。シンボルは、符号化および復号化プロセスの基本的なデータ単位である。各々のソースブロック（サブブロック）に対して、全てのシンボル（サブシンボル）は、同一サイズである。符号化および復号化のためのシンボル（サブシンボル）に実行される動作は、排他的論理和演算である。
【０１９８】
Ｃ’［０］，．．．，Ｃ’［Ｋ−１］はＫ個のソースシンボルを示す
Ｃ［０］，．．．，Ｃ［Ｌ−１］はＬ個の中間シンボルを示す
符号化の第一段階は、Ｋ個のソースシンボルから中間シンボルの数（Ｌ＞Ｋ）を生成することである。このステップにおいて、Ｋ個のソーストリプル（ｄ［０］，ａ［０］，ｂ［０］），．．．，（ｄ［Ｋ−１］，ａ［Ｋ−１］，ｂ［Ｋ−１］）はセクションＢ．５．４．４にて説明したＴｒｉｐ［］を使用して生成される。Ｋ個のソーストリプルはＫ個のソースシンボルと関連し、逆符号化プロセスを使用してソースシンボルからＬ個の中間シンボルＣ［０］，．．．，Ｃ［Ｌ−１］を決定するために用いる。この処理は、ＭＳＣＲ復号プロセスにより実現される。
【０１９９】
特定の”所与の符号化関係”は、Ｌ個の中間シンボルの中で保持しなければならない。セクションＢ．５．２は、これらの関係および中間シンボルがソースシンボルから生成される方法を記載する。
【０２００】
一旦中間シンボルが生成されると、修復シンボルは作成され、一つ以上の修復シンボルはグループとして単一のデータパケットに配置される。各々の修復シンボルグループは、符号化シンボルＩＤ（ＥＳＩ）および符号化シンボルの数（Ｇ）と関係している。ＥＳＩは、セクションＢ．５．４．４にて説明したＴｒｉｐ［］を再び使用して、各々の修復シンボルに対する３整数（ｄ、ａ、ｂ）のトリプルを生成するために用いられる。これは、セクションＢ．５．４に記載されている生成器を使用し、セクションＢ．３およびＢ．４にて説明したように実行される。各々の（ｄ，ａ，ｂ）−トリプルはセクションＢ．５．４．３．に記載されているＬＴＥｎｃ［Ｋ，Ｃ［０］，．．．，Ｃ［Ｌ−１］，（ｄ，ａ，ｂ）］生成器を使用して、中間シンボルから対応する修復シンボルを生成するために用いられる。
【０２０１】
＜Ｂ．５．２  符号化の第１段階：中間シンボル生成＞
＜Ｂ．５．２．１  全般＞
第１の符号化ステップは、ソースシンボルＣ’［０］，．．．，Ｃ’［Ｋ−１］からＬ個の中間シンボルＣ［０］，．．．，Ｃ［Ｌ−１］を生成する、前置（プリ）符号化ステップである。中間シンボルは、制約条件の２つのセットによって、唯一に定義される。
【０２０２】
１．中間シンボルは、ソースシンボルのトリプルの一組によって、ソースシンボルに関連する。ソースシンボルトリプルの生成はセクション５．２．２で定義され、セクションＢ．５．４．４にて説明したＴｒｉｐ［］生成器を使用する。
【０２０３】
２．一組の前置符号化関係は、中間シンボル自身の中で保持される。
【０２０４】
これらは、セクションＢ．５．２．３において定義される。Ｌ個の中間シンボルの生成は、セクション５．２．４において定義される。
【０２０５】
＜Ｂ．５．２．２  ソースシンボルのトリプル＞
Ｋ個のソースシンボルのそれぞれは、０＜ｉ＜Ｋに対するトリプル（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）に関係している。ソースシンボルトリプルは、セクションＢ．５．４．４で定義されるトリプル生成器を使用して決定される。
【０２０６】
０＜ｉ＜Ｋの各ｉについて、
（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）＝Ｔｒｉｐ［Ｋ，ｉ］
＜Ｂ．５．２．３  前置符号化関係＞
Ｌ個の中間シンボル間の前置符号化関係は、最初のＫ個の中間シンボルに関して最後のＬ−Ｋ個の中間シンボルを表すことにより定義される。
【０２０７】
最後のＬ−Ｋ個の中間シンボルＣ［Ｋ］，．．．，Ｃ［Ｌ−１］はＳ個のＬＤＰＣシンボルとＨ個のＨＤＰＣシンボルを含む。ＳおよびＨの値は、後述するようにＫから決定される。そのため、Ｌ＝Ｋ＋Ｓ＋Ｈである。
【０２０８】
Ｘ：  Ｘ・（Ｘ−１）≧２・Ｋとなる最小の自然数
Ｓ：  Ｓ≧ｃｅｉｌ（０．０１・Ｋ）＋Ｘとなる最小の素数整数
Ｈ：  （Ｈ、ｃｅｉｌ（Ｈ／２））＞＝Ｋ＋Ｓとなる最小の整数
Ｈ’＝ｃｅｉｌ（Ｈ／２）
Ｌ＝Ｋ＋Ｓ＋Ｈ
Ｃ［０］、．．．、Ｃ［Ｋ−１］  最初のＫ個の中間シンボルを示す
Ｃ［Ｋ］、．．．、Ｃ［Ｋ＋Ｓ−１］  Ｓ個のＬＤＰＣシンボルを示す（ゼロに初期化される）
Ｃ［Ｋ＋Ｓ］、．．．、Ｃ［Ｌ−１］  Ｈ個のＨＤＰＣシンボルを示す（ゼロに初期化される）
Ｓ  ＬＤＰＣシンボルは、以下の処理の最後でＣ［Ｋ］，．．．，Ｃ［Ｋ＋Ｓ−１］の値であるように定義される。
【０２０９】
ｉ＝０、．．．、Ｋ−１  について以下を実行
ａ＝１＋（ｆｌｏｏｒ（ｉ／Ｓ）％（Ｓ−１））
ｂ＝ｉ％Ｓ
Ｃ［Ｋ＋ｂ］＝Ｃ［Ｋ＋ｂ］＾Ｃ［ｉ］
ｂ＝（ｂ＋ａ）％Ｓ
Ｃ［Ｋ＋ｂ］＝Ｃ［Ｋ＋ｂ］＾Ｃ［ｉ］
ｂ＝（ｂ＋ａ）％Ｓ
Ｃ［Ｋ＋ｂ］＝Ｃ［Ｋ＋ｂ］＾Ｃ［ｉ］
Ｈ個のＨＤＰＣシンボルの構築のために、システムは体ＧＦ（２５６）を使用する。体は、体ＧＦ（２）上の既約多項式ｆ＝ｘ８＋ｘ４＋ｘ３＋ｘ２＋１に関して表されることができる。αは元ｘモジュロｆを表すものとする。当業者によく知られているように、元αは原始的であり、すなわち、２５５個のαの１乗はＧＦ（２５６）の２５５個の非ゼロの元に一致する。一実施形態において、システムは、Ｋ＋Ｓ個の整数ａ［０］、．．．、ａ［Ｋ＋Ｓ−１］を選択し、β［０］、．．．、β［Ｋ＋Ｓ−１］によって元αａ［０］、．．．、αａ［Ｋ＋Ｓ−１］を表す。さらに、我々は、Ｈ個のさらなる整数ｂ［０］、．．．、ｂ［Ｈ−１］を選択し、Γ［０］、．．．、Γ［Ｈ−１］によって元αｂ［０］、．．．、αｂ［Ｈ−１］を表す。本発明のさらなる好ましい実施形態は、これらの整数に関する特定の選択を規定する。しかし、これらの整数の多くの等価な選択が存在することに留意されたい。全ての正の整数ｉに対して、ｇ［ｉ］＝ｉ＾（ｆｌｏｏｒ（ｉ／２））とする。ｇ［ｉ］は、各要素が、単一のビット位置で前の要素と異なるグレイ系列であることに留意されたい。さらに、ｇ［ｊ，ｋ］が、要素がその要素の２進表現においてちょうどｋ個の非ゼロのビットを有するｇ［ｉ］の下位系列のｊ番目の要素（ｊ＝０、１、２、．．．）を表すものとする。当業者によく知られているように、系列ｇ［ｊ，ｋ］は、ｇ［ｊ，ｋ］およびｇ［ｊ＋１，ｋ］の２進表現がちょうど２つの位置で異なるという特性を有する。我々は、これらの位置をｐ［ｊ，ｋ，１］およびｐ［ｊ，ｋ，２］によって表す。
【０２１０】
ＨＤＰＣシンボルの値は、以下のプロセスの後のＣ［Ｋ＋Ｓ］、．．．、Ｃ［Ｌ−１］の値として定義される。
【０２１１】
我々は、シンボルＵを０と初期化する。このシンボルのサイズは、ソース、ＬＤＰＣ、およびＨＤＰＣシンボルの通常のサイズと同じである。
【０２１２】
次に、０からＫ＋Ｓ−２までの範囲を取る変数ｈに対して、我々は以下を実行する。変数Ｕが、Ｕ＝Ｕ＊β［ｈ］＾Ｃ［ｈ］と更新される。同時に、我々は、Ｃ［Ｋ＋Ｓ＋ｐ［ｊ，Ｈ’，１］］＝Ｃ［Ｋ＋Ｓ＋ｐ［ｊ，Ｈ’，１］］＾Ｕ、およびＣ［Ｋ＋Ｓ＋ｐ［ｊ，Ｈ’，２］］＝Ｃ［Ｋ＋Ｓ＋ｐ［ｊ，Ｈ’，２］］＾Ｕと設定する。
【０２１３】
さらなるステップにおいて、我々は、ＵをＵ＊β［Ｋ＋Ｓ−１］＾Ｃ［Ｋ＋Ｓ−１］に変換する。
【０２１４】
次に、０からＨ−１の範囲を取る変数ｈに対して、我々は、Ｃ［Ｋ＋Ｓ＋ｈ］＝Ｃ［Ｋ＋Ｓ＋ｈ］＾Γ［ｈ］＊Ｕと更新する。これは、ＨＤＰＣ符号化プロセスの記述を完了する。
【０２１５】
好ましい実施形態において、システムは、以下の整数、ａ［０］、．．．、ａ［Ｋ＋Ｓ−１］、およびｂ［０］、．．．、ｂ［Ｈ−１］：ａ［０］＝ａ［１］＝．．．＝ａ［Ｋ＋Ｓ−１］＝１およびｂ［０］＝１、ｂ［１］＝２、．．．ｂ［ｉ］＝ｉ＋１などを選択する。有利なことに、この好ましい実施形態において、ＨＤＰＣシンボルの構築は、シンボル間のビット毎の排他的ＯＲ演算と共に原始元αのアクションだけを用いて実行されることができる。上で与えられた既約多項式の選択は、αのアクションの非常に効率的な実行を可能にし、それによってＨＤＰＣ構築アルゴリズムの計算の複雑性を小さくする。当業者に明らかであろうように、上記の構築アルゴリズムは、多段階符号の復号化器内の要求される復号化演算を実行するように容易に適合されることができ、したがって、復号化器における計算の複雑性の上述の削減も実現することができる。
【０２１６】
＜Ｂ．５．２．４  中間シンボル＞
＜Ｂ．５．２．４．１  定義＞
所与のＫ個のソースシンボルＣ’［０］，Ｃ’［１］，．．．，Ｃ’［Ｋ−１］についてＬ個の中間シンボルＣ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］は以下を満たすように独自に定義されるシンボル値である。
【０２１７】
１．  ０＜ｉ＜Ｋの全てのｉについて、Ｋ個のソースシンボルＣ’［０］，Ｃ’［１］，．．．，Ｃ’［Ｋ−１］は、Ｋ個の制約条件、Ｃ’［ｉ］≡ＬＴＥｎｃ［Ｋ，（Ｃ［０］，．．．，Ｃ［Ｌ−１］），（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）］を満足する。
【０２１８】
２．  Ｌ個の中間シンボルＣ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］は、Ｂ．５．２．３で定義された前置符号化関係を満足する。
【０２１９】
＜Ｂ．５．２．４．２  中間シンボルの計算＞
このサブセクションは、Ｂ．５．２．４．１の制約条件を満たしているＬ中間シンボルＣ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］の算出方法を記載する。
【０２２０】
Ｋ個の入力シンボルからＮ個の出力シンボルを生成する符号のための生成行列ＧはＧＦ（２）の上のＮ×Ｋマトリックスである。ここで、各々の列は出力シンボルの１つに対応し、各々の行は入力シンボルの１つに対応し、ｉ番目となる出力シンボルは、ｉ列がゼロでないエントリを含む入力シンボルの合計に等しい。
【０２２１】
そして、Ｌ個の中間シンボルは、以下の通りに算出される。
【０２２２】
Ｃ：Ｌ個の中間シンボル（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］）の列ベクトルを示す。
【０２２３】
Ｄ：Ｓ＋Ｈ個のゼロシンボルを含む列ベクトルで、Ｋ個のソースシンボルＣ’［０］，Ｃ’［１］，．．．，Ｃ’［Ｋ−１］が続く。
【０２２４】
よって、上記の制約条件はＧＦ（２）の上のＬ×Ｌマトリックスと定義され、Ａは
Ａ・Ｃ＝Ｄ
となるようなものである。
【０２２５】
マトリックスＡは、以下の通りに構築され得る。
【０２２６】
ＧＬＤＰＣは、ＤＰＣシンボルのＳｘＫの生成行列である、そのため、
ＧＬＤＰＣ・（Ｃ［０］，．．．，Ｃ［Ｋ−１］）Ｔ＝（Ｃ［Ｋ］，．．．，Ｃ［Ｋ＋Ｓ−１］）Ｔ
ＧＨＤＰＣは、ハーフシンボルのＨ×（Ｋ＋Ｓ）の生成行列である、そのため、
ＧＨＤＰＣ×（Ｃ［０］，．．．，Ｃ［Ｓ＋Ｋ−１］）Ｔ＝（Ｃ［Ｋ＋Ｓ］，．．．，Ｃ［Ｋ＋Ｓ＋Ｈ−１］）Ｔ
ＩＳ：Ｓ×Ｓの恒等行列を表す
ＩＨ：Ｈ×Ｈの恒等行列を表す
０Ｓ×Ｈ：Ｓ×Ｈの零行列を表す
ＧＬＴ：ＬＴ符号化器により生成される符号化シンボルのＫ×Ｌの生成行列である。
【０２２７】
そのため、
ＧＬＴ・（Ｃ［０］，．．．，Ｃ［Ｌ−１］）Ｔ＝（Ｃ’［０］，Ｃ’［１］，．．．，Ｃ’［Ｋ−１］）Ｔ
すなわち、ＧＬＴｉ，ｊ＝１であり、Ｃ［ｉ］は排他的論理和されたシンボルを含むだけならば、
ＬＴＥｎｃ［Ｋ，（Ｃ［０］，．．．，Ｃ［Ｌ−１］），（ｄ［ｉ］，ａ［ｉ］，ｂ［ｉ］）］
となる。
【０２２８】
そして、
Ａの最初のＳ列は、ＧＬＤＰＣ｜ＩＳ｜ＺＳ×Ｈに等しい。
【０２２９】
Ａの次のＨ列は、ＧＨＤＰＣ｜ＩＨに等しい。
【０２３０】
Ａの残りのＫ列は、ＧＬＴに等しい。
【０２３１】
マトリックスＡは、図２０に示される。中間シンボルはそれから算出されることができる。
【０２３２】
Ｃ＝Ａ−１・Ｄ
いかなるＫにおいても行列Ａは最大ランクを有し、逆変換可能であるようにソーストリプルは生成される。この算出は、Ｌ個の中間シンボルＣ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］を作成するためにＭＳＣＲ復号プロセスをＫ個のソースシンボルＣ’［０］，Ｃ’［１］，．．．，Ｃ’［Ｋ−１］に適用することにより実現されうる。
【０２３３】
ソースシンボルから効率的に中間シンボルを生成するために、セクションＢ．６に記載されるような効率的な復号化器態様が用いられる。ソースシンボルトリプルは、そのアルゴリズムを使用しているソースシンボルの効率的な復号化を容易にするように設計されている。
【０２３４】
＜Ｂ．５．３  第２の符号化ステップ：連鎖反応符号化＞
第２の符号化ステップでは、セクションＢ．３．２．２およびＢ．４．２に従って生成されたトリプル（ｄ，ａ，ｂ）＝Ｔｒｉｐ［Ｋ，Ｘ］を使用して、セクションＢ．５．４において定義される生成器ＬＴＥｎｃ［Ｋ，（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］），（ｄ，ａ，ｂ）］をＬ個の中間シンボルＣ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］に適用することによってＥＳＩ  Ｘを有する修復シンボルを生成する。
【０２３５】
＜Ｂ．５．４  生成器＞
＜Ｂ．５．４．１  乱数生成器＞
乱数生成器Ｒａｎｄ［Ｘ，ｍ］は以下の通りに定義される。ここで、Ｘは非負整数であり、ｉは非負整数であり、ｍは自然数であり、そして、生成される値は０とｍ−１との間の整数である。Ｖ０およびＶ１の各々が２５６個のエントリの配列であるとする。ここで、各エントリは４バイトの符号なし整数である。乱数の適切な配列は付録Ｂ．１およびＢ．２で提供されるが、これは例示であり発明の範囲を限定すべきものではない。これらの仮定のもとで、Ｒａｎｄ［Ｘ，ｉ，ｍ］＝（Ｖ０［（Ｘ＋ｉ）％２５６］＾Ｖ１［（ｆｌｏｏｒ（Ｘ／２５６）＋ｉ）％２５６］）％ｍである。本明細書では、特に明示しない限り、”乱数”は”擬似乱数”および”本質的乱数”を含むものとする。
【０２３６】
＜Ｂ．５．４．２  度数生成器＞
度数生成器［ｖ］は以下の通りに定義される。ｖは少なくとも０であり２２０＝１０４８５７６より小さい整数である。
【０２３７】
図２１において、ｆ［ｊ−１］≦ｖ＜ｆ［ｊ］となるインデックスｊを探す。
【０２３８】
Ｄｅｇ［ｖ］＝ｄ［ｊ］
＜Ｂ．５．４．３  連鎖反応符号化シンボル生成器＞
符号化シンボル生成器ＬＴＥｎｃ［Ｋ，（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］），（ｄ，ａ，ｂ）］は、以下の入力をする。
【０２３９】
Ｋは、ソースブロック（サブブロック）に対するソースシンボル（またはサブシンボル）の数である。セクションＢ．５．２にて説明したように、ＬはＫから導出される。そして、Ｌ’はＬ以上の最小の素数とする。
【０２４０】
（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］）はセクションＢ．５．２にて説明したように、生成されるＬ個の中間シンボル（サブシンボル）である。
【０２４１】
（ｄ、ａ、ｂ）はセクションＢ．５．３．４で定義されたトリプル生成器使用して決定されるソーストリプルである。ここで、ｄは符号化シンボルの度数を示す整数であり、ａは１からＬ’−１に含まれる整数であり、ｂは０からＬ’−１に含まれる整数である。
【０２４２】
以下のアルゴリズムにより、符号化シンボル生成器は１つの符号化シンボルを出力として生成する。
【０２４３】
ｂ≧Ｌである間、ｂ＝（ｂ＋ａ）％Ｌ’を実行
ＬＴＥｎｃ［Ｋ，（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］），（ｄ，ａ，ｂ）］＝Ｃ［ｂ］
ｊ＝１，．．．，ｍｉｎ（ｄ−１，Ｌ−１）について以下を実行
ｂ＝（ｂ＋ａ）％Ｌ’
ｂ≧Ｌである間、ｂ＝（ｂ＋ａ）％Ｌ’を実行
ＬＴＥｎｃ［Ｋ，（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］），（ｄ，ａ，ｂ）］＝ＬＴＥｎｃ［Ｋ，（Ｃ［０］，Ｃ［１］，．．．，Ｃ［Ｌ−１］），（ｄ，ａ，ｂ）］＾Ｃ［ｂ］
＜Ｂ．５．４．４  トリプル生成器＞
トリプル生成器Ｔｒｉｐ［Ｋ，Ｘ］には次のものが入力される。
【０２４４】
Ｋ：ソースシンボル数
Ｘ：符号化シンボルＩＤ
そして、
ＬはセクションＢ．５．２で説明したようにＫに基づいて決定される
Ｌ’はＬ以上の最小の素数である
Ｑ＝６５５２１、２１６未満の最大の素数である
とする。
【０２４５】
Ｊ（Ｋ）は、Ｋと関係する組織的インデックスである。組織的インデックスは以下のプロセスにより選択される数であり、本明細書のマトリックスＡの構築の残りのプロセスは結果として逆変換可能なマトリックスＢになる。適切な組織的インデックスは付録Ａで提供されるが、これは例示であり発明の範囲を限定すべきものではない。
【０２４６】
トリプル生成器の出力はトリプル（ｄ、ａ、ｂ）であり、以下の通りに決定される。
【０２４７】
１．  Ａ＝（５３５９１＋Ｊ（Ｋ）・９９７）％Ｑ
２．  Ｂ＝１０２６７・（Ｊ（Ｋ）＋１）％Ｑ
３．  Ｙ＝（Ｂ＋Ｘ・Ａ）％Ｑ
４．  ｖ＝Ｒａｎｄ［Ｙ，０，２２０］
５．  ｄ＝Ｄｅｇ［ｖ］
６．  ａ＝１＋Ｒａｎｄ［ｙ，１，Ｌ’−１］
７．  ｂ＝Ｒａｎｄ［Ｙ，２，Ｌ’］
＜Ｂ．６  ＦＥＣ復号化の実装＞
＜Ｂ．６．１  全般＞
このセクションは、本明細書に記載されているＭＳＣＲ符号のための効率的な復号化アルゴリズムを記載する。各々がシンボルを符号化することを受信した注は、中間シンボルの間に均衡化の値と思われることができる。これらの連立方程式および中間シンボルの間の周知の予め符号化関係から、連立方程式を解くためのいかなるアルゴリズムも、中間シンボルおよびそれ故、ソースシンボルをうまく復号化できる。しかしながら、選択されるアルゴリズムは復号化の計算効率に大きな影響を及ぼす。
【０２４８】
＜Ｂ．６．２  ソースブロックの復号化＞
＜Ｂ．６．２．１  全般＞
復号化器は、復号化されるソースブロックの構造について既知であると仮定され、シンボルサイズＴおよびソースブロック内のシンボル数Ｋを含む。
【０２４９】
セクションＢ．５において説明されたアルゴリズムから、ＭＳＣＲ復号化器は、プリコーディングシンボルの総数Ｌ＝Ｋ＋Ｓ＋Ｈを計算することができ、それらが、復号化されるべきソースブロックからどのように生成されたかを判定することができる。この説明において、復号化されるべきソースブロックに関する受信符号化シンボルが復号化器に渡されると想定される。さらに、それぞれのそのような符号化シンボルに関して、排他的論理和が符号化シンボルに等しい中間シンボルの数およびセットが復号化器に渡されると想定される。ソースシンボルの場合、セクションＢ．５．２．２において説明されたソースシンボルトリプルが、各ソースシンボルを与えるために総和される中間シンボルの数およびセットを示す。
【０２５０】
Ｎ≧Ｋがソースブロックに関する受信された符号化シンボルの数であるものとし、Ｍ＝Ｓ＋Ｈ＋Ｎであるものとする。以下のＭ×ＬマトリックスＡは、復号化されるべきソースブロックに関して復号化器に渡された情報から導出されることができる。ＣがＬ個の中間シンボルの列ベクトルであるものとし、Ｄが受信機に知られている値を有するＭ個のシンボルの列ベクトルであるものとし、ここで、Ｍ個のシンボルのうちの最後のＳ＋Ｈ個は、ＬＤＰＣシンボルおよびＨＤＰＣシンボルに対応する値がゼロのシンボルであり（これらはＬＤＰＣシンボルおよびＨＤＰＣシンボルに関するチェックシンボルであり、ＬＤＰＣシンボルおよびＨＤＰＣシンボル自体ではない）、Ｍ個のシンボルのうちの残りのＮ個はソースブロックに関する受信符号化シンボルである。そのとき、Ａは、Ａ・Ｃ＝Ｄを満足するマトリックスであり、ここで・はＧ（２５６）上のマトリックスの乗算を表す。マトリックスＡは図２３に示されるようなブロック構造を有する。ブロック構造は、Ｎ行およびＬカラムを有するマトリックスＦと、Ｓ行およびＬ−Ｓ−Ｈカラムを有するマトリックスＥと、Ｓ×Ｓ恒等行列Ｉと、全てゼロであるＳ行およびＨカラムを有するマトリックスＯと、Ｈ行およびＬ−Ｈカラムを有するマトリックスＢと、Ｈ×Ｈ恒等行列Ｊとを含む。サブマトリックスＢはＧＦ（２５６）上で定義された成分を有する一方、マトリックスＥおよびＦは０／１成分、すなわち、ＧＦ（２）の成分を有する。マトリックスＦはダイナミックな符号化プロセスを定義し、マトリックスＥは上述のＬＤＰＣ符号化プロセスを定義し、マトリックスＢはＨＤＰＣ符号化プロセスを定義する。特に、符号化において、インデックスｊに対応する中間シンボルが、インデックスｉに対応する符号化シンボルに排他的ＯＲ演算される場合、Ｆ［ｉ，ｊ］＝１である。全てのその他のｉおよびｊに対して、Ｆ［ｉ，ｊ］＝０である。同様に、インデックスｊに対応する中間シンボルが、インデックスｉに対応するＬＤＰＣシンボルに排他的ＯＲ演算される場合、Ｅ［ｉ，ｊ］＝１である。最後に、インデックスｊに対応する中間シンボルに対するβのアクションの結果が、インデックスｉに対応するＨＤＰＣシンボルに排他的ＯＲ演算される場合、Ｂ［ｉ，ｊ］＝βである。
【０２５１】
ソースブロックを復号化することは、知られているＡおよびＤからＣを復号化することと等価である。ＣはＧＦ（２５６）上のＡの階数がＬであるときかつそのときに限って復号化されることができることは明らかである。Ｃが復号化されると、欠落したソースシンボルが、ソースシンボルトリプルを使用して、それぞれの欠落したソースシンボルを得るために排他的ＯＲ演算される中間シンボルの数およびセットを判定することによって得られることができる。
【０２５２】
Ｃの復号化における第１のステップは、復号化のスケジュールを作成することである。このステップにおいて、Ａは、Ｍ−Ｌ行を捨てた後に、（行演算と、行およびカラムの並べ替えとを使用する）ガウスの消去法を使用してＬ×Ｌ恒等行列に変換される。復号化のスケジュールは、ガウスの消去法のプロセス中の行演算と行およびカラムの並べ替えとの順序を含み、ＤではなくＡにのみ依存する。ＤからのＣの復号化は、復号化のスケジュールの作成と同時に行われることができるか、または復号化は、復号化のスケジュールに基づいて後で行われることができる。
【０２５３】
復号化のスケジュールとＣの復号化との間の対応は以下の通りである。最初にｃ［０］＝０、ｃ［１］＝１．．．、ｃ［Ｌ−１］＝Ｌ−１、およびｄ［０］＝０、ｄ［１］＝１．．．、ｄ［Ｍ−１］＝Ｍ−１とする。
【０２５４】
復号化のスケジュールにおいてＡの行ｉが行ｉ’に排他的ＯＲ演算される度に、そのとき、復号化のプロセスにおいて、シンボルＤ［ｄ［ｉ］］がシンボルＤ［ｄ［ｉ’］］に排他的ＯＲ演算される。我々はこの演算をＧＦ（２）行演算と呼ぶ。
【０２５５】
復号化のスケジュールにおいてＡの行ｉの（ＧＦ（２５６）内の何らかのαに関する）倍数αが行ｉ’に排他的ＯＲ演算される度に、そのとき、復号化のプロセスにおいて、シンボルα＊Ｄ［ｄ［ｉ］］がシンボルＤ［ｄ［ｉ’］］に排他的ＯＲ演算される。我々はこの演算をＧＦ（２５６）行演算と呼ぶ。ＧＦ（２）行演算は、元αが１であるＧＦ（２５６）行演算の特定の場合であることに留意されたい。
【０２５６】
復号化のスケジュールにおいて行ｉが行ｉ’と交換される度に、そのとき、復号化のプロセスにおいて、ｄ［ｉ］の値がｄ［ｉ’］の値と交換される。
【０２５７】
復号化のスケジュールにおいてカラムｊがカラムｊ’と交換される度に、そのとき、復号化のプロセスにおいて、ｃ［ｊ］の値がｃ［ｊ’］の値と交換される。
【０２５８】
この対応から、ソースブロックの復号化におけるシンボルの排他的ＯＲ演算の総数が、ガウスの消去法における行演算（交換ではない）の数に関連することは明らかである。Ａは、ガウスの消去法の後、および最後のＭ−Ｌ行を捨てた後、Ｌ×Ｌ恒等行列であるので、正常な符号化の終わりに、Ｌ個のシンボルＤ［ｄ［０］］、Ｄ［ｄ［１］］、．．．、Ｄ［ｄ［Ｌ−１］］はＬ個のシンボルＣ［ｃ［０］］、Ｃ［ｃ［１］］、．．．、Ｃ［ｃ［Ｌ−１］］の値であることは明らかである。
【０２５９】
ガウスの消去法が復号化のスケジュールを作成するために実行される順番は、復号化が成功か否かにいかなる影響も与えない。しかし、復号化の速度は、ガウスの消去法が実行される順番に大きく依存する。（さらに、Ａの疎な表現を保つことが極めて重要であるが、これはここでは説明されない）。ＧＦ（２５６）行演算よりもＧＦ（２）行演算を実行する方がより効率的であることも明らかである。したがって、ガウスの消去法を実行するとき、体ＧＦ（２）から得られた要素を有するマトリックスＡの行でピボット選択する方がよい。ＨＤＰＣシンボルに対応するマトリックスの行の消去をガウスの消去法のプロセスの終わりまで残すことも有利である。このセクションの残りの部分は、比較的効率的なガウスの消去法が実行される可能性がある順番を説明する。
【０２６０】
＜Ｂ．６．２．２  第１段階＞
図２３を参照して、我々はＸによって、図２４ａに示されるようにＦ、Ｅ、Ｉ、および０を含むマトリックスを表す。
【０２６１】
ガウスの消去法の第１段階において、マトリックスＸは、概念的にサブマトリックスに分割される。サブマトリックスのサイズは、０に初期化される非負の整数ｉおよびｕによってパラメータ化される。Ｘのサブマトリックスは以下である。
【０２６２】
（１）最初のｉ行と最初のｉカラムとの共通部分によって定義されるサブマトリックス。これは、この段階の各ステップの最後に恒等行列である。
【０２６３】
（２）最初のｉ行と、最初のｉカラムおよび最後のｕカラム以外の全てのカラムとの共通部分によって定義されるサブマトリックス。このサブマトリックスの全ての成分はゼロである。
【０２６４】
（３）最初のｉカラムと最初のｉ行以外の全ての行との共通部分によって定義されるサブマトリックス。このサブマトリックスの全ての成分はゼロである。
【０２６５】
（４）全ての行と、最後のｕカラムとの共通部分によって定義されるサブマトリックスＵ。
【０２６６】
（５）最初のｉカラムおよび最後のｕカラム以外の全てのカラムと、最初のｉ行以外の全ての行との共通部分によって形成されるサブマトリックスＶ。
【０２６７】
図２２はＸのサブマトリックスを示す。第１段階の初めは、Ｖ＝Ｘである。各ステップにおいて、Ｘの行が選択される。Ｖの構造によって定義される以下のグラフが、Ｘのどの行が選択されるかを決定することに使用される。Ｖと交わるカラムはグラフ内のノードであり、Ｖ内にちょうど２つの１を有する行は、２つの１の位置で２つのカラム（ノード）を接続するグラフのエッジである。このグラフの構成要素は、グラフ内のノード／エッジの各組の間に経路が存在するようなノード（カラム）およびエッジ（行）の最大のセットである。構成要素のサイズは、当該構成要素内のノード（カラム）の数である。グラフは、以下でＹによって表される。
【０２６８】
第１段階には最大Ｌステップが存在する。この段階は、Ｖが消えるか、またはゼロマトリックスになるかのいずれかのときに終了する。各ステップにおいて、Ｘの行が以下のように選択される。
【０２６９】
Ｖの全ての成分がゼロである場合、行は選択されず、第１段階が終了する。
【０２７０】
そうでない場合、ｒを、Ｘの少なくとも１つの行がＶ内にちょうどｒ個の１を有するような最小の整数とする。
ｒ＝１の場合、Ｖ内にちょうど１つの１を有する行を選択する。
ｒ＝２の場合、Ｙによって定義されたグラフ内の最大のサイズの構成要素の一部である、Ｖ内にちょうど２つの１を有する任意の行を選択する。
ｒ＞２の場合、Ｖ内にちょうどｒ個の１を有する全ての行の中で最小の初めの重みを有する、Ｖ内にちょうどｒ個の１を有するそのような行を選択する。
【０２７１】
このステップにおいて行が選択された後、Ｖと交わるＸの第１の行が選択された行と交換され、したがって、選択された行がＶと交わる第１の行である。Ｖと交わるカラムのうちのＸのカラムが、選択された行内のｒ個の１のうちの１つがＶの第１のカラムに現れるように、および残りのｒ−１個の１がＶの最後のカラムに現れるように並べ替えられる。そのとき、選択された行が、Ｖの第１のカラム内に１を有する、選択された行より下のＸの全てのその他の行に排他的ＯＲ演算される。換言すると、我々は、このステップにおいてＧＦ（２）行演算を実行する。最後に、ｉが１だけ増やされ、ｕがｒ−１だけ増やされ、これがステップを完了する。
【０２７２】
ｖはこの段階の終了時のマトリックスＶのカラムの数を表すものとする。ＶのカラムがＸの最後のｖ個のカラムに対応するようにマトリックスＢのカラムの順序を変えた後、マトリックスＸは図２４ｂで与えられる形態を有することになる。
【０２７３】
＜Ｂ．６．２．３  第２段階＞
我々は、マトリックスＵを、そのマトリックスＵがマトリックスＸの最後のｖ行をさらに含むように修正し、我々は、それに応じてｕをｕ＋ｖで置き換える。さらに、サブマトリックスＵは、図２５に示されるように最初のｉ行Ｕｕｐｐｅｒおよび残りのＮ＋Ｓ−ｉ行Ｕｌｏｗｅｒとに分割される。ガウスの消去法が、Ｕｌｏｗｅｒに対して第２段階で実行される。このステップの後、マトリックスＵｌｏｗｅｒは図２６で与えられる形態を有することになり、すなわち、行およびカラムの順番の変更の後、最初のｓ行と最初のｓカラムとの共通部分はＩと呼ばれる恒等行列であり、最後のｍ行はゼロであり、最初のｓ行と最後のｕ−ｓカラムとの共通部分はマトリックスＷを形成する。ｓ＋ｍはマトリックスＵｌｏｗｅｒの行の数Ｎ＋Ｓ−ｉに等しいことに留意されたい。ｓの値がｕである場合、次の段階はスキップされることができる。ｍの値がＨ−ｖよりも大きい場合、この場合、マトリックスＡの階数がＬ未満であるので復号化の誤りが返される。マトリックスＸの最後のｍ行が捨てられ、したがって、この段階の後、Ａは図２７で与えられる形態を有する。この図において、Ｂ１、．．．、Ｂ３は、それぞれＨ行を有し、ＧＦ（２５６）の成分を有するマトリックスである。次に、ＧＦ（２５６）行演算が、マトリックスＢ１およびＢ２をゼロ設定するためにそれらのマトリックスＢ１およびＢ２に対して実行される。これは２つのやり方のうちの１つで行われることができる。第１の方法において、Ａの最初のｉ行が、ＧＦ（２５６）行演算によってマトリックスＢ１をゼロ設定するために使用される。次に、Ａの次のｓ行が、マトリックスＢ２をゼロ設定するために使用される。第２の方法において、行ｉから行ｉ＋ｓ−１まで（行ｉおよび行ｉ＋ｓ−１を含む）が、ＧＦ（２）行演算によってＵｕｐｐｅｒの最初のｓカラムをゼロ設定するために使用され、次に、Ｘの最初のｉ＋ｓ行がＧＦ（２５６）行演算によってＢ１およびＢ２を両方ゼロ設定するために使用される。当業者に明らかであるように、ＨＤＰＣシンボルの構築のための上述の方法のアルゴリズムは、（第１の方法における）マトリックスＢ１または（第２の方法における）Ｂ１およびＢ２両方のゼロ設定のための同様のアルゴリズムをもたらす。このアルゴリズムは、マトリックスのカラム毎に１回と、Ｈの行毎に１回とだけシンボルに対するＧＦ（２５６）の元のアクションの計算を必要とする。したがって、上述の第２の方法は、マトリックスＢ１およびＢ２をゼロ設定するために全体的により少ない演算をもたらす。
【０２７４】
このステップの後、マトリックスＡは図２８で与えられる形態を有する。マトリックスＴは、Ｈ行およびｕ−ｓカラムを有する。ガウスの消去法が、マトリックスＴをＨ−ｕ＋ｓ行が後に続く恒等行列に変換するためにそのマトリックスＴに対して実行される。これが不可能である場合、すなわち、Ｔの階数がｕ−ｓより小さい場合、復号化の誤りが伝達される。この段階の終了時、マトリックスＡは、最後のＨ−ｕ＋ｓ行を捨てた後、図２９で与えられる形態を有する。この図において、Ｉはｓ×ｓ恒等行列を表し、Ｊはｕ−ｓ×ｕ−ｓ恒等行列を表す。
【０２７５】
＜Ｂ．６．２．４  第３段階＞
第２段階の後、ＡをＬ×Ｌ恒等行列に変換することを完了するためにゼロ設定される必要があるＡの部分は、Ｂ１およびＢ２をゼロ設定する第１の方法の後の場合にＷ、およびＵｕｐｐｅｒの全ｕカラムであるか、またはＢ１およびＢ２をゼロ設定する第２の方法の後の場合にＷ、およびＵｕｐｐｅｒの最後のｕ−ｓカラムである。前者の場合、マトリックスＷは概して小さなサイズであるので、そのＷは基本的なＧＦ（２）行演算を使用してゼロ設定されることができる。このステップの後、マトリックスＡは図３０で与えられる形態を有する。両方の場合とも、ゼロ設定されるべきマトリックスの残りの部分は、このとき長方形である。前者の場合、その残りの部分はｉ行およびｕカラムのサイズであり、後者の場合、その残りの部分はｉ＋ｓ行およびｕ−ｓカラムのサイズである。以下では、我々は、このマトリックスの行数に関してｉ’を使用し、カラム数に関してｕ’を使用し、マトリックスをＵ＾によって表す。
【０２７６】
概して、残りのサブマトリックスＵ＾の行数ｉ’は、カラム数ｕ’よりも大幅に大きい。効率的に☆をゼロ設定するために使用されることができるいくつかの方法が存在する。１つの方法において、以下の事前計算マトリックスＵ’が、我々がＩｕで表す、Ａの最後のｕ行およびカラムに基づいて計算され、Ｕ’はＵ＾をゼロ設定するために使用される。Ｉｕのｕ行は、ある整数ｚに対して、それぞれｚ行のｃｅｉｌ（ｕ／ｚ）個のグループに分割される。そのとき、ｚ行の各グループに関して、ｚ行の全ての非ゼロの組合せが計算され、２z−１行をもたらす（これは、Ｉｕ内に現れるハミング重み１の組合せが再計算される必要がないのでグループ毎に行の２z−ｚ−１回の排他的論理和によって行われることができる）。したがって、結果として得られる事前計算マトリックスＵ’は、ｃｅｉｌ（ｕ／ｚ）・２ｚ−１行およびｕカラムを有する。Ｕ’は形式上マトリックスＡの一部ではないが、Ｕｕｐｐｅｒをゼロ設定するために後で使用されることに留意されたい。好ましい実施形態において、ｚ＝８である。
【０２７７】
Ｕ＾のｉ’行のそれぞれに対して、この行のＵ＾サブマトリックス内のｚカラムの各グループについて、Ｕ＾内のｚカラムの成分のセットが全てゼロという訳ではない場合、ｚカラム内のパターンに一致する事前計算マトリックスＵ’の行がその行に排他的論理和演算され、それによって、Ｕ’の１行のその行への排他的論理和演算をコストとしてその行内のそれらのｚカラムをゼロ設定する。
【０２７８】
この段階の後、ＡはＬ×Ｌ恒等行列であり、完全な復号化のスケジュールが正常に形成されている。そのとき、知られている符号化シンボルを排他的ＯＲ演算することを含む対応する復号化が、復号化のスケジュールに基づいて中間シンボルを回復するために実行されることができる。
【０２７９】
全てのソースシンボルに関連するトリプルが、Ｂ．５．２．２に従って計算される。受信ソースシンボルに関するトリプルが、復号化において使用される。欠落したソースシンボルに関するトリプルが、どの中間シンボルが、欠落したソースシンボルを回復するために排他的ＯＲ演算される必要があるかを判定するために使用される。
【０２８０】
＜多体シングルステージ連鎖反応符号化器／復号化器＞
多体シングルステージ（ＭＦＳＳ）符号は、本明細書において開示または提案される有用な特性を有する。ＭＦＳＳ符号、符号化器、および復号化器の新規の構成が、本明細書において説明される。一実施形態において、データは送信元から送信先への伝送のために符号化され、各出力シンボルは、有限体から得られた係数を用いた入力シンボルのうちの１つまたは複数の一次結合として生成され、各出力シンボルに関して、
−ランダムプロセスに従って、出力シンボルの度数として知られる１以上の整数ｄを選択し、
−ランダムプロセスに従って、入力シンボルのサイズｄのセットを選択し、入力シンボルのこのセットは出力シンボルの近隣セットとして知られるべきであり、
−有限体のセットを、少なくとも１つの出力シンボルに関してこのセットが少なくとも２つの有限体を含むように選択し、
−出力シンボルの近隣セット内の各入力シンボルに関して、あり得る有限体の選択されたセットから有限体を選択し、
−出力シンボルの近隣セット内の各入力シンボルに関して、ランダムプロセスに従って、上で選択された有限体から非ゼロの元を選択する。
【０２８１】
出力シンボルの度数を選択するためのランダムプロセスは、度数が度数分布に従って選択されるルビーＩおよびルビーＩＩに記載のプロセスであってよい。各出力シンボルに関連付けるための入力シンボルを選択するためのランダムプロセスは、入力シンボルがランダムに、一様に選択されるルビーＩおよびルビーＩＩに記載のプロセスであってよい。本明細書において使用される”ランダム”は、”擬似ランダム”、”偏位ランダム”などを含む可能性がある。
【０２８２】
あり得る有限体のセットは、セット｛ＧＦ（２），ＧＦ（２５６）｝であってよい。
【０２８３】
有限体を選択するためのプロセスは、ｄ１未満の度数の出力シンボルに関して、体ＧＦ（２）が、出力シンボルの近隣セット内の全ての入力シンボルに対して選択され、ｄ１以上の度数の出力シンボルに関して、体ＧＦ（２５６）が、出力シンボルの近隣セットの数の少なくとも１つ、一部、または全てに対して選択され、ＧＦ（２）が、もしある場合には近隣セット内の残りの元に対して選択されるように、パラメータｄ１に基づくことができる。
【０２８４】
選択された体から有限体の元を選択するためのプロセスは、元が、体の非ゼロの元の中から一様に、ランダムに選択される単純なランダムプロセスであってよい。
【０２８５】
上述のようにＭＦＳＳ符号化器によって符号化されたデータを受信する復号化器は、上述の方法に従って符号のマトリックス表現を形成することであって、このマトリックスがスタティックな行を含まず、符号の各出力シンボルに関する１つのダイナミックな行を含む、形成することと、次に、このマトリックスの逆行列を発見するためにガウスの消去法を適用することと、ガウスの消去法のプロセスの各段階において最小の度数のピボット行が選択されることを保証することとによって、入力シンボルを再生するために出力シンボルを復号化する可能性がある。
【０２８６】
当業者に明らかであろうように、ルビーＩおよびルビーＩＩに記載の符号のよく知られている特性のうちの多くは上述の符号に同様に適用可能であり、特に、適切な度数分布の選択は、高い確率でガウスの消去法のプロセスが残りの度数が１の行を特定することができ、したがって、復号化プロセスがルビーＩおよびルビーＩＩに記載された連鎖反応プロセスとして働くことを保証することができる。
【０２８７】
このＭＦＳＳ符号は、当技術分野で知られている符号に優るいくつかのさらなる利点を有する。第１に、体ＧＦ（２５６）からの元を包含することは、任意の所与の受信出力シンボルが、前に受信された出力シンボルに対する追加情報ではない確率を大幅に小さくする。結果として、この符号の復号誤り確率は、従来の符号よりも大幅に小さくなる。例えば、場合によっては、ルビーＩおよびルビーＩＩに記載の符号の失敗の確率が改善される。
【０２８８】
大きな体に基づくその他の符号に優るこの符号の利点は、概して、小さな度数の出力シンボルがガウスの消去法のプロセスによって最初に処理され、結果として、ＧＦ（２５６）からの元の包含が、復号化のプロセスの後の方まで考慮される必要がないことである。ＧＦ（２５６）上の演算はＧＦ（２）上の演算と比べて比較的コストが高いので、これは、シンボルの多くまたは全てがＧＦ（２５６）またはその他の大きな有限体からの元を使用して構築される符号と比較して大幅に削減された計算の複雑性をもたらす。
【０２８９】
大きな体に基づくその他の符号に優るさらなる利点は、より大きな体を使用して生成されたそれらの出力シンボルに関して、近隣セットの１つの元だけがより大きな体から得られた係数を有し、その結果、シンボルと有限体の元との間の１つの演算だけがそれぞれのそのような出力シンボルに対して要求されることである。これは、小さい全体的な計算の複雑性をもたらす。
【０２９０】
内符号および外符号を使用して、２つの（またはそれより多い）符号化手順を使用して入力シンボルを符号化することは、より複雑な符号にしばしば見られる利点を提供する単純な符号スキームをもたらすことが知られている。内符号および外符号を使用する場合、ソースシンボルが、符号のうちの一方を使用して最初に符号化され、第１の符号化器の出力が、もう一方の符号によって符号化する符号化器に提供され、その結果が出力シンボルとして出力される。もちろん、ＭＦＳＳを使用することは、内符号／外符号の使用とは異なる。一例として、出力シンボルが入力符号の近隣セットから導出される。本明細書において説明される実施形態のうちの多くにおいて、各出力シンボルは入力シンボルの一次結合である。多段階符号を用いる場合、各出力シンボルは、入力シンボルならびに／または冗長シンボルおよび／もしくは中間シンボルの一次結合である可能性がある。
【０２９１】
＜密多体符号およびそのような符号のための符号化器／復号化器＞
上述の技術の変形形態において、符号のマトリックス表現は密なマトリックスである。よく知られているように、誤り訂正符号は、有限体上の密なランダムマトリックスから構築されることができる。例えば、スタティックな行が存在せず、それぞれのダイナミックな行がＧＦ（２ｑ）からの元を含み、各元がランダムに選択される一般化されたマトリックスが構築されることができる。そのとき、各出力シンボルが、ダイナミックな行のうちの１つに対応し、マトリックスのこの行の対応するカラムに非ゼロの元が存在する入力シンボルの一次結合として、一次結合プロセスにおいてこれらの元を係数として使用して生成される固定レート符号が構築されることができる。
【０２９２】
ＧＦ（２ｑ）から独立に、ランダムに選択された係数を用いたＫ行およびＫ＋Ａカラムのランダムに選択されたマトリックスがＫより小さい階数を有する確率は最大で２−ｑＡであることが当業者によく知られている。したがって、出力シンボルが、ＧＦ（２ｑ）からのランダムに選択された係数を使用して入力シンボルから独立に、ランダムに生成される、Ｋ個の入力シンボルおよびＫ／Ｒ個の出力シンボルを有する符号の復号誤り確率は、受信された符号化シンボルの数がＫ＋Ａである場合、最大で２−ｑＡである。
【０２９３】
ｑ＝１の場合、上述の符号は、全ての演算が体ＧＦ（２）内であり、したがって通常のＸＯＲ演算に対応するので、妥当な計算の複雑性の利点を有する。しかし、この場合、失敗の確率の下限２−Ａは、いったんＡ個の追加的なシンボルが受信されてしまうと、望ましい失敗の確率よりも大幅に高い。
【０２９４】
ｑ＝８の場合、上述の符号は、（受信されたＡ個の追加的なシンボルに対して２−８Ａで限界が与えられる）より低い失敗の確率の利点を有する。しかし、この場合、全ての演算は体ＧＦ（２５６）内であり、したがって、比較的計算のコストが高い。
【０２９５】
さらなる実施形態は、大きなｑの値を使用して達成可能な復号誤り確率に近い復号誤り確率が、小さなｑの値を用いて達成可能な計算の複雑性に近い計算の複雑性によって達成されることを可能にする。この実施形態において、出力シンボルは、ＧＦ（２ｐ）またはＧＦ（２ｑ）のいずれかから得られた係数を用いた入力シンボルの一次結合として生成され、ここで、ｐ＜ｑである。１つの特定の実施形態において、ちょうど（Ｋ−２ｐ／ｑ）／Ｒ個の出力シンボルが、ＧＦ（２ｐ）からの係数を使用して生成され、残りの２ｐ／（ｑＲ）個の出力シンボルが、ＧＦ（２ｑ）からの係数を使用して生成される。
【０２９６】
送信先において受信されたデータは、符号の受信された出力シンボルと入力シンボルとの間の線形関係を判定し、線形関係のこのセットを解いて入力シンボルを判定することによって復号化されることができる。
【０２９７】
この符号の復号誤り確率は、最大で、全ての係数が体ＧＦ（２ｐ）から選択される符号の復号誤り確率であり、より大きな体ＧＦ（２ｑ）からの係数を使用して生成されたシンボルの数に依存して大幅に小さい可能性がある。しかし、出力シンボルのほとんどはＧＦ（２ｐ）からの係数を使用して生成されるので、符号化の計算の複雑性は、全てのシンボルがＧＦ（２ｐ）からの係数を使用して生成される符号の計算の複雑性よりもほんのわずかに高いだけである。さらに、復号化の方法は、ＧＦ（２ｐ）からの係数を用いて生成されたシンボルが最初に処理され、したがって、復号化の演算の大部分が専らＧＦ（２ｐ）の演算を用いて実行されるように構成されることができる。結果として、同様に、復号化方法の計算の複雑性は、ＧＦ（２ｐ）のみを用いて構築された符号に関する計算の複雑性に近い。特定の好ましい実施形態において、ｐ＝１およびｑ＝８である。
【０２９８】
＜一部の多体符号の一部の特性＞
上述の例のほとんどにおいて、入力シンボルおよび出力シンボルは同数のビットを符号化し、各出力シンボルは１つのパケットに入れられる（パケットは、その全体が受信されるか、またはその全体が失われるかのいずれかである伝送単位である）。一部の実施形態において、通信システムは、各パケットがいくつかの出力シンボルを含むように修正される。そのとき、出力シンボルの値のサイズが、いくつかの要因に基づいて、ストリームのファイルまたはブロックの入力シンボルへの最初の分割における入力シンボルの値のサイズによって決定されたサイズに設定される。復号化のプロセスは、各パケットが受信されるときに出力シンボルがまとまって到着することを除いて基本的に変わらない。
【０２９９】
通常、入力シンボルサイズおよび出力シンボルサイズの設定は、出力シンボルが送信されるべきストリームおよび通信システムのファイルまたはブロックのサイズによって指示される。例えば、通信システムがデータのビットを定義されたサイズのパケットにグループ化するか、またはその他のやり方でビットをグループ化する場合、シンボルサイズの設計は、パケットまたはグループ化のサイズから始まる。そこから、設計者は、いくつの出力シンボルが１つのパケットまたはグループで搬送されるかを決定し、そのことが出力シンボルのサイズを決定する。簡単にするために、設計者は、出力シンボルサイズに等しい入力シンボルサイズを設定しがちであるが、入力データが異なる入力シンボルサイズをより都合よくする場合は、その異なる入力シンボルサイズが使用される可能性がある。
【０３００】
上述の符号化プロセスは、ストリームの元のファイルまたはブロックに基づいて、出力シンボルを含むパケットのストリームを生成する。ストリーム内の各出力シンボルが、全てのその他の出力シンボルと無関係に生成され、生成されることができる出力シンボルの数に対する下限または上限は存在しない。キーが各出力シンボルに関連付けられる。キー、およびストリームの入力ファイルまたはブロックの一部の内容が、出力シンボルの値を決定する。続けて生成された出力シンボルが連続したキーを有する必要はなく、一部の応用において、一連のキーをランダムに生成すること、または系列を擬似ランダムに生成することが好ましい。
【０３０１】
多段階復号化は、Ｋ個のサイズの等しい入力シンボルのブロックが、非常に高い確率で平均Ｋ＋Ａ個の出力シンボルから回復されることができ、ＡはＫと比較して小さいという特性を有する。例えば、上で最初に説明された好ましい実施形態において、Ｋ＝１００のとき、図３１は、生成された最初の１２０個の出力シンボルの中からランダムに選択されたＫ＋Ａ個の出力シンボルから復号化することに失敗する確率を示し、図３２の表は、生成された最初の１１０個の出力シンボルの中からランダムに選択されたＫ＋Ａ個の出力シンボルから復号化することに失敗する確率を示す。
【０３０２】
特定の出力シンボルがランダムまたは擬似ランダムな順番で生成され、搬送中の特定の出力シンボルの損失が概して当該シンボルの値に無関係であるので、入力ファイルまたはブロックを回復するために必要とされる出力シンボルの実際の数にはほんのわずかな変動しかない。多くの場合、Ｋ＋Ａ個の出力シンボルの特定の集合がブロックを復号化するのに十分でない場合、ブロックは、受信機が１つまたは複数の送信元からより多くの出力シンボルを受信することができる場合、まだ回復可能である。
【０３０３】
出力シンボルの数がＩの解像度により制限されるだけであるので、Ｋ＋Ａ個の出力シンボルがより適切に生成できる。たとえば、Ｉが３２ビット数である場合、４０億の異なる出力シンボルを生成でき、ファイルまたはストリームのブロックはＫ＝５０，０００個の入力シンボルを含みうる。ある用途では、４０億の出力シンボルのうちごく少数だけが生成され、送信され得る。そして、それは入力ファイルまたはストリームのブロックが可能な出力シンボルの非常に小さい割合で復元され、Ｋ個の出力シンボル（入力シンボルサイズは出力シンボルサイズと同様であると仮定する）よりわずかに多い入力ファイルによりブロックが復元される確率である。
【０３０４】
ある用途では、入力シンボルの全てを復号化することが出来ないこと、または入力シンボルの全てを復号化できるが出来比較的低い確率であることを許容することが出来るかもしれない。この種のアプリケーションにおいて、受信機は、Ｋ＋Ａ個の出力シンボルを受信した後に入力シンボルの全てを復号化することを試みるのを止めることができる。または、受信機は、Ｋ＋Ａ個未満の出力シンボルの受信の後で出力シンボルを受信するのを止めることができる。ある用途では、受信機は、Ｋ個以下の出力シンボルを受信しさえすることができるだけである。このように、本発明のいくつかの実施例で、所望の精度が全ての入力シンボルの完全回復である必要があるというわけではないと理解されることになっている。
【０３０５】
更に、不完全な回復が受け入れられるいくつかのアプリケーションでは、データは入力シンボルの全てが回復されることができるというわけでないように、あるいは、入力シンボル数より多い数の出力シンボルの受信を必要とする入力シンボルの完全な復元がされるように符号化される。この種の符号化は、通常、より計算能力を必要とせず、このように、符号化の計算能力を減少させる方法が許容されても良い。
【０３０６】
上述の図のさまざまな機能ブロックがハードウェアおよび／またはソフトウェアの組合せにより実現可能であることがよく理解されていることになっている。そして、特定の実装では、いくつかのブロックのいくつかあるいは全ての機能が合成されうる。同様に、また、本願明細書に記載されているさまざまな方法がハードウェアおよび／またはソフトウェアの組合せにより実現可能であることが理解されることになっている。
【０３０７】
前記説明は、例示的なものであり限定的なものではない。当業者は本開示を読むことにより本発明の多くのバリエーションが明らかになるであろう。本発明の範囲は、従って、上述の説明に関して決定されてはならず、その代わりに添付の請求の範囲およびその等価な範囲に関して決定されなければならない。
【０３０８】
＜付録Ａ．  組織的インデックスＪ（Ｋ）の値＞
Ｋの値それぞれについて、ソースシンボル・トリプルのセット（ｄ［０］，ａ［０］，ｂ［０］），．．．，（ｄ［Ｌ−１］，ａ［Ｌ−１］，ｂ［Ｌ−１］）がＬ個の中間シンボルが一意に規定されるような特性を有するように、組織的インデックスＪ（Ｋ）は設計されている。すなわち、セクションＢ．５．２．４．２のマトリックスＡは最大階数（フルランク）であり、かつ、逆変換可能な特性を有するように設計されている。以下は、４から８１９２の間にあるＫの値に対応する適切な組織的インデックスのリストであり、一例として提供されるものである。値の順序は、読書の順序と同じである。すなわち、第１行の最初の数値から第１行の最後の数値、そして、第２行の最初の数値に続き、以下同様である。
2009527949.tif 000009
2009527949.tif 000010
2009527949.tif 000011
2009527949.tif 000012
2009527949.tif 000013
2009527949.tif 000014
2009527949.tif 000015
2009527949.tif 000016
2009527949.tif 000017
2009527949.tif 000018
2009527949.tif 000019
2009527949.tif 000020
2009527949.tif 000021
2009527949.tif 000022
＜付録Ｂ．１  テーブルＶ０の値＞
これらの値は、上述の明細書のセクションＢ．５．４．１で説明したテーブルＶ０の値の例示的なセットを示している。各々の成分は１０進数表記の３２ビット整数である。値は、第１カラムの最上段から最下段、そして、第２カラムの最上段から最下段、以下同様に読まれる。
2009527949.tif 000023
＜付録Ｂ．２  テーブルＶ１の値＞
これらの値は、上述の明細書のセクションＢ．５．４．１で説明したテーブルＶ１の値の例示的なセットを示している。各々の成分は１０進数表記の３２ビット整数である。値は、第１カラムの最上段から最下段、そして、第２カラムの最上段から最下段、以下同様に読まれる。
2009527949.tif 000024
【図面の簡単な説明】
【０３０９】
【図１】本発明の一実施形態に係る通信システムのブロック図である。
【図２】本発明の一実施形態に係る符号化器のブロック図である。
【図３】本発明の一実施形態に係る冗長シンボルを生成する方法の簡略ブロック図である。
【図４】本発明の一実施形態に係るスタティック符号化器の基本演算の簡略ブロック図である。
【図５】本発明の一実施形態に係るダイナミック符号化器の簡略ブロック図である。
【図６】本発明の一実施形態に係るダイナミック符号化器の基本演算の簡略ブロック図である。
【図７】本発明の一実施形態に係るスタティック符号化器の簡略ブロック図である。
【図８】本発明の一実施形態に係るスタティック符号化器の基本演算の簡略ブロック図である。
【図９】スタティック符号化器の一特定実施形態に係る符号化パラメータを計算する方法の簡略図である。
【図１０】本発明の他の実施形態に係るスタティック符号化器の簡略フローチャートである。
【図１１】本発明の一実施形態に係る復号化器の簡略ブロック図である。
【図１２】本発明の一実施形態に係る復号化器の演算の簡略フローチャートである。
【図１３】本発明の他の実施形態に係る復号化器の演算の簡略フローチャートである。
【図１４】本発明のさらに他の実施形態に係る復号化器の演算の簡略フローチャートである。
【図１５】本発明の一実施形態に係るダイナミック復号化器の簡略ブロック図である。
【図１６】本発明の一実施形態に係るスタティック復号化器の簡略ブロック図である。
【図１７】サブシンボル写像からのソースシンボルを示す図である。
【図１８】様々なファイルサイズに対するファイルダウンロード・パラメータの可能な設定を示す図である。
【図１９】様々なソースブロックサイズに対するストリーミングパラメータの可能な設定を示す図である
【図２０】ソースシンボルと中間シンボルとの関係を表すマトリックスの形式を示す図である。
【図２１】度数生成器の度数分布を示す図である。
【図２２】復号化に使用可能なマトリックスＡの形式を示す図である。
【図２３】復号化に使用可能なマトリックスＡのブロック分解を示す図である。
【図２４ａ】復号化に使用可能なマトリックスＸのブロック分解を示す図である。
【図２４ｂ】復号化処理の第１段階のいくつかのステップの後のマトリックスＸのブロック分解を示す図である。
【図２５】いくつかの消去ステップの後のマトリックスＸのブロック分解を示す図である。
【図２６】さらなる消去ステップの後のＸサブマトリックスのブロック分解を示す図である。
【図２７】消去および削除ステップの後のマトリックスＡのブロック分解を示す図である。
【図２８】さらなる消去および削除ステップの後のマトリックスＡのブロック分解を示す図である。
【図２９】さらなる消去ステップの後のマトリックスＡのブロック分解を示す図である。
【図３０】更にさらなる消去ステップの後のマトリックスＡのブロック分解を示す図である。
【図３１】本発明の好適な実施形態に係る（１２０，１００）符号の符号失敗確率のテーブルを示す図である。
【図３２】本発明の好適な実施形態に係る（１１０，１００）符号の符号失敗確率のテーブルを示す図である。
【図１】
2009527949.tif 000025
【図２】
2009527949.tif 000026
【図３】
2009527949.tif 000027
【図４】
2009527949.tif 000028
【図５】
2009527949.tif 000029
【図６】
2009527949.tif 000030
【図７】
2009527949.tif 000031
【図８】
2009527949.tif 000032
【図９】
2009527949.tif 000033
【図１０】
2009527949.tif 000034
【図１１】
2009527949.tif 000035
【図１２】
2009527949.tif 000036
【図１３】
2009527949.tif 000037
【図１４】
2009527949.tif 000038
【図１５】
2009527949.tif 000039
【図１６】
2009527949.tif 000040
【図１７】
2009527949.tif 000041
【図１８】
2009527949.tif 000042
【図１９】
2009527949.tif 000043
【図２０】
2009527949.tif 000044
【図２１】
2009527949.tif 000045
【図２２】
2009527949.tif 000046
【図２３】
2009527949.tif 000047
【図２４ａ】
2009527949.tif 000048
【図２４ｂ】
2009527949.tif 000049
【図２５】
2009527949.tif 000050
【図２６】
2009527949.tif 000051
【図２７】
2009527949.tif 000052
【図２８】
2009527949.tif 000053
【図２９】
2009527949.tif 000054
【図３０】
2009527949.tif 000055
【図３１】
2009527949.tif 000056
【図３２】
2009527949.tif 000057
【国際調査報告】
2009527949.tif 000058