(57)【特許請求の範囲】
【請求項１】
データをコード化するための方法であって、
前記データの１つ以上の順列を生成することと、
前記１つ以上の順列の各々に関連したウェイトを決定することと、
前記関連したウェイトに基づいた各順列からの１つ以上のコードパケットを計算することであって、ここで、前記ウェイトの各々は、前記１つ以上のコードパケットの各々を計算するのに使用される前記関連した順列の数を示し、前記計算することは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算することを含む、計算することと、
前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化することと、
を含む方法。
【請求項２】
さらに、ネットワークによって前記コードパケットストリームを伝送することを含む請求項１に記載の方法。
【請求項３】
前記計算することは、（Ｎ−ｋ）コードパケットの総和を生成するために前記１つ以上コードパケットを計算することを含み、前記データは、ｋデータパケットを含み、前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む請求項１に記載の方法。
【請求項４】
前記多重化することは、前記コードパケットストリームを生成するために前記ｋデータパケットとともに前記（Ｎ−ｋ）コードパケットを多重化することを含む請求項３に記載の方法。
【請求項５】
前記計算することは、
【数１】
0005474558.tif 000016
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算することを含み、ＣJは、Ｊ番目のコードパケットを表し、なお、Ｊ＝０，１，…Ｌであり、ＷJは、コードパケットＣJのウェイトを表し、ＰJは、コードパケットＣJの順列行列を表し、行列Ｇ（ＣJ，ＷJ）は、（ＣJ×ｋ）行列である、請求項１に記載の方法。
【請求項６】
前記生成することは、前記データの前記１つ以上の順列の各々を任意に生成することを含む請求項１に記載の方法。
【請求項７】
データをコード化するための装置であって、
前記データの１つ以上の順列を生成するように構成された順列ロジックと、
前記１つ以上の順列の各々に関連したウェイトを決定するように構成されたウェイトロジックと、
前記関連したウェイトに基づく各順序から１つ以上のコードパケットを計算するように構成された処理ロジックであって、前記ウェイトの各々は、前記１つ以上のコードパケットの各々を計算するのに使用される前記関連した順列の数を示し、前記処理ロジックは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成される、処理ロジックと、
前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化するように構成されたマルチプレクサと、
を含む装置。
【請求項８】
前記処理ロジックは、（Ｎ−ｋ）コードパケットの総和を生成するために前記１つ以上のコードパケットを計算するように構成され、前記データは、ｋデータパケットを含み、前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む請求項７に記載の装置。
【請求項９】
前記マルチプレクサは、前記コードパケットストリームを生成するために、前記ｋデータとともに前記（Ｎ−ｋ）コードパケットを多重化するように構成される請求項８に記載の装置。
【請求項１０】
前記処理ロジックは、
【数２】
0005474558.tif 000017
として表された低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するように構成され、ＣJは、Ｊ番目のコードパケットを表し、なお、Ｊ＝０，１，…Ｌであり、ＷJは、コードパケットＣJのウェイトを表し、ＰJは、コードパケットＣJの順列行列を表し、行列Ｇ（ＣJ，ＷJ）は、（ＣJ×ｋ）行列である、請求項７に記載の装置。
【請求項１１】
前記順列ロジックは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された請求項７に記載の装置。
【請求項１２】
データをコード化する装置であって、
前記データの１つ以上の順列を生成するための手段と、
前記１つ以上の順列の各々と関連したウェイトを決定するための手段と、
前記関連したウェイトに基づいた各順列から１つ以上のコードパケットを計算するための手段であって、前記ウェイトの各々は、前記１つ以上のコードパケットの各々を計算するのに使用される前記関連した順列の数を示し、前記計算するための手段は、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するための手段を含む、計算するための手段と、
前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化するための手段と、
を含む装置。
【請求項１３】
さらに、ネットワークによって前記コードパケットストリームを伝送するための手段を含む請求項１２の装置。
【請求項１４】
前記計算するための手段は、（Ｎ−ｋ）コードパケットの総和を生成するための前記１つ以上のコードパケットを計算するための手段を含み、前記データは、ｋデータパケットを含み、前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む請求項１２の装置。
【請求項１５】
前記多重化するための手段は、前記コードパケットストリームを生成するために前記ｋデータとともに前記（Ｎ−ｋ）コードパケットを多重化するための手段を含む請求項１４に記載の装置。
【請求項１６】
前記計算するための手段は、
【数３】
0005474558.tif 000018
として表される低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するための手段を含み、ＣJは、Ｊ番目のコードパケットを表し、なお、Ｊ＝０，１，…Ｌであり、ＷJは、コードパケットＣJのウェイトを表し、ＰJは、コードパケットＣJの順列行列を表し、行列Ｇ（ＣJ，ＷJ）は、（ＣJ×ｋ）行列である、請求項１２に記載の装置。
【請求項１７】
前記生成するための手段は、前記データの前記１つ以上の各々を任意に生成するための手段を含む請求項１２に記載の装置。
【請求項１８】
コンピュータにデータの１つ以上の順列を生成させるための第１のコードのセットと、
前記コンピュータに前記１つ以上の順列の各々に関連したウェイトを決定させるための第２のコードのセットと、
前記コンピュータに前記関連したウェイトに基づいて各順列から１つ以上のコードパケットを計算させるための第３のコードのセットであって、前記ウェイトの各々は、前記１つ以上のコードパケットの各々を計算するのに使用される前記関連した順列の数を示し、前記第３のコードのセットは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成される、第３のコードのセットと、
前記コンピュータに前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化させるための第４のコードのセットと、
を記憶するコンピュータ可読記憶媒体。
【請求項１９】
さらに、前記コンピュータにネットワークによって前記コードパケットストリームを伝送させるための第５のコードのセットを記憶する請求項１８のコンピュータ可読記憶媒体。
【請求項２０】
前記第３のコードのセットは、前記コンピュータに（Ｎ−ｋ）コードパケットの総和を計算させるように構成され、前記データは、ｋデータパケットを含み、前記コードパケットストリームは、Ｎコード化された総和を含む請求項１８のコンピュータ可読記憶媒体。
【請求項２１】
前記第４のコードのセットは、前記コードパケットストリームを生成するために前記ｋデータとともに前記（Ｎ−ｋ）コードパケットを多重化するように構成される請求項２０のコンピュータ可読記憶媒体。
【請求項２２】
前記第３のコードのセットは、
【数４】
0005474558.tif 000019
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成され、ＣJは、Ｊ番目のコードパケットを表し、なお、Ｊ＝０，１，…Ｌであり、ＷJは、コードパケットＣJのウェイトを表し、ＰJは、コードパケットＣJの順列行列を表し、行列Ｇ（ＣJ，ＷJ）は、（ＣJ×ｋ）行列である、請求項１８のコンピュータ可読記憶媒体。
【請求項２３】
前記第１のコードセットは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された請求項１８のコンピュータ可読記憶媒体。
【請求項２４】
データをコード化するための方法を実行するように構成された少なくとも１つのプロセッサであって、
前記データの１つ以上の順列を生成するための第１のモジュールと、
前記１つ以上の順列の各々と関連するウェイトを決定するための第２のモジュールと、
前記関連したウェイトに基づく各順列から１つ以上のコードパケットを計算するための第３のモジュールであって、前記ウェイトの各々は、前記１つ以上のコードパケットの各々を計算するのに使用される前記関連した順列の数を示し、前記第３のモジュールは、前記順列および前記ウェイトを示す低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するように構成される、第３のモジュールと、
前記データおよび前記１以上のコードパケットをコードパケットストリームに多重化するための第４のモジュールと、
を含む少なくとも１つのプロセッサ。
【請求項２５】
さらに、ネットワークによって前記コードパケットを伝送するための第５のモジュールを含む請求項２４に記載の少なくとも１つのプロセッサ。
【請求項２６】
前記第３のモジュールは、（Ｎ−ｋ）コードパケットの総和を計算するように構成され、前記データは、ｋデータパケットを含み、前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む請求項２４に記載の少なくとも１つのプロセッサ。
【請求項２７】
前記第４のモジュールは、前記コードパケットストリームを生成するために前記ｋデータとともに前記（Ｎ−ｋ）コードパケットを多重化するように構成される請求項２６に記載の少なくとも１つのプロセッサ。
【請求項２８】
前記第３のモジュールは、
【数５】
0005474558.tif 000020
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成され、ＣJは、Ｊ番目のコードパケットを表し、なお、Ｊ＝０，１，…Ｌであり、ＷJは、コードパケットＣJのウェイトを表し、ＰJは、コードパケットＣJの順列行列を表し、行列Ｇ（ＣJ，ＷJ）は、（ＣJ×ｋ）行列である、請求項２４の少なくとも１つのプロセッサ。
【請求項２９】
前記第１のモジュールは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された請求項２４の少なくとも１つのプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
３５Ｕ．Ｓ．Ｃ§１１９に基づく優先権の主張
本出願は、２００６年１１月１３日に出願された「APPARATUS AND METHODS FOR ERASURE RECOVERY USING A PARALLEL CONCATENATED LOW DENSITY GENERATOR MATRIX CODE」という名称の仮特許出願第６０／８６５，６２６号に基づく優先権を主張し、本譲受人に譲渡され、ここで参照により本明細書に明示的に組み込まれている。
【０００２】
本出願は、一般に、データネットワークの動作に関連し、より具体的には、通信ネットワークにおいてデータを符号化するための方法および装置に関する。
【背景技術】
【０００３】
典型的な無線の転送システムにおいて、コンテントは、マルチキャスト伝送チャネルによって携帯機器に転送される。コンテントは、パケットが転送チャネルによって転送されるときに生じることがあるパケット損失を克服するためにコード化されるコードパケットの形をとっている。送信機における符号器は、オリジナルデータパケットを取得し、１つ以上の装置に伝送されるコードパケットを生成する。ノイズまたは他の劣化している伝送の影響によって、コードパケットのサブセット（subset）は任意の特定の装置において受信される。受信されたコートパケットは、オリジナルデータパケットを回復するために復号化される。
【０００４】
典型的には、配信サーバは、データパケットによってメッセージのコード化を実行する符号器を有している。符号器は、データパケット（ｄ）を取得し、コードパケット（Ｃ）を生成する。コードパケットは、損失の大きい転送チャネルによって送信され、コードパケット（Ｃ）のあるサブセット（Ｃ’）は、装置によって受信される。装置における復号器は、オリジナルデータパケットｄを回復するために受信されたコードパケット（Ｃ’）を使用する。
【０００５】
メッセージのコード化のゴールは、マルチキャスト無線ネットワークによって多くのモバイル装置に効率的および確実にコンテントを転送することである。しかしながら、モバイル装置は、一般的に、それらのＣＰＵ容量、使用可能なメモリ量、バッテリ容量、およびそれらのファイルシステムの速度に限定される。これらの制約は、そのような環境で使用するために適しているコード化のタイプに厳しい制限を課する。
【０００６】
パケット削除を克服するために使用される典型的なコード化の構成は、リード・ソロモンコード（Reed-Solomon）およびラプター（Raptor）コードを含む。ｋデータパケットを回復するために、復号器がｋコードパケットを正確に受信する必要があるという意味で、リード・ソロコモンコードは、最適なコードである。しかしながら、動作を復号化する計算の要求は、非常に高いことがある。また、復号器のメモリ要求も非常に高く、モバイル装置上で実施することを非常に困難にしている。
【０００７】
ラプターコードは、ネットワークにおいてパケット削除を克服するために設計されている。コードは、データパケットの９９％以上を回復するために設計された内部のＬＴコード、および残りを回復するために設計された外部のコードから構成されている。ラプター復号器に要求される計算の容量は、リード・ソロモン復号器よりはるかに少ない。しかしながら、ラプターコードは、すべてのデータパケットを回復するために必要とされるコードパケットの数の面で、リード・ソロモンほど効率的ではない。例えば、ラプター復号器は、高い確率でｋデータパケットを回復するために、約１．１＊ｋコードパケットを受信する必要がある。
【０００８】
ラプターコードは、レートレス（rateless）のコードである。すなわち、符号器は、多くの（潜在的に無限大）の数のコードパケットを生成することができ、復号器は、約１．１＊ｋコードパケットが受信される限り、すべてのデータパケットを回復することができる。しかしながら、ほとんどのシステムにおいて、無限の数のコードパケットを生成することが必要（または可能）ではないであろう。例えば、典型的な配信システムは、クリップについての転送デッドラインを有しており、配信セーバは、そのデッドラインが経過した後、クリップに関連したコードパケットを伝送することを止めなければならない。
【０００９】
ラプターコード化に関連した他の問題は、それがコードの連続する連結であることである。最初に、内部コードを復号化しなければならない。これらの復号化されたパケットは、次に、外部復号器に送られる。これらの２つのステップは、順に実行されなければならない、また、これは実行するのに時間がかかる。ラプターコード化に関する他の問題は、復号化の動作を実行するために、モバイル装置で典型的に得られるより多くのメモリを取得することである。
【００１０】
したがって、無線環境において使用される低計算、メモリおよびオーバーヘッドの要求を有するコード化の構成を提供するために動作するシステムを有していることが望ましいだろう。
【発明の概要】
【００１１】
１つ以上の態様において、通信システムにおいてデータをコード化するために動作する方法および装置を含むコード化システムが提供される。１つの態様において、コード化システムは、単一の復号化ステージを使用して復号化を可能にする低密度ジェネレータデータ（low density generator matrix）（ＬＤＧＭ）を使用して符号化し、それによってメモリを保存し、計算の複雑さを最小化する。
【００１２】
１つの態様において、データをコード化する方法が提供される。方法は、データの１つ以上の順列を生成することと、各順列に関連するウェイトを決定することと、関連するウェイトに基づく各順列から１つ以上のコードパケットを計算することと、データおよび１つ以上のコードパケットをコードパケットストリームに多重化することと、を含む。
【００１３】
１つの態様において、データをコード化する装置が提供される。装置は、データの１つ以上の順列を生成するように構成された順列ロジックと、各順列に関連してウェイトを決定するように構成されたウェイトロジックと、を含む。装置は、さらに関連したウェイトに基づいた各順列からの１つ以上のコードパケットを計算するために構成された処理ロジックと、データおよび１つ以上のコードパケットをコードパケットストリームに多重化するように構成されたマルチプレクサと、を含む。
【００１４】
１つ態様において、データをコード化する装置が提供される。装置は、データの１つ以上の順列を生成するための手段と、各順列と関連するウェイトを決定するための手段と、を含む。装置は、さらに関連したウェイトに基づいた各順列から１つ以上のコードパケットを計算するための手段、データおよび１つ以上のコードパケットをコードパケットストリームに多重化するための手段と、を含む。
【００１５】
１つの態様において、コンピュータ可読媒体を含むコンピュータプログラムプロダクトが提供される。コンピュータ可読媒体は、コンピュータにデータの１つ以上の順列を生成させる第１のコードのセットと、コンピュータに各順列に関連するウェイトを決定させる第２のコードのセットと、コンピュータに関連したウェイトに基づいて各順列から１つ以上のコードパケットを計算させる第３のコードのセットと、コンピュータにデータおよび１つ以上のコードパケットをコードパケットストリームに多重化させる第４のコードのセットと、を含む。
【００１６】
１つの態様において、データをコードかするための方法を実行するように構成された少なくとも１つのプロセッサが提供される。少なくとも１つのプロセッサは、データの１つ以上の順列を生成するための第１のモジュールと、各順列に関連するウェイトを決定するための第２のモジュールと、関連するウェイトに基づいて各順列から１つ以上のコードパケットを計算するための第３のモジュールと、データおよび１つ以上のコードパケットをコードパケットストリームに多重化するための第４のモジュールと、を含む。
【００１７】
態様の他の態様は、以下の図面の簡単な説明、発明を実施するための形態、特許請求の範囲の調査の後に明らかになるだろう。
【図面の簡単な説明】
【００１８】
本明細書で説明される先の態様は、添付の図面とともに用いられるときに、次の記述の参照により、より直ちに明らかになるだろ、ここで、
【図１】図１は、コード化システムの１つの態様を含むネットワークを示す。
【図２】図２は、コード化システムの態様において使用されるコード化ロジックを示す。
【図３】図３は、コード化システムの提要において使用されるＬＤＧＭの構成を図示するグラフィカル表示を示す。
【図４】図４は、コード化システムの態様におけるコード化データについての符号器の機能的な図を示す。
【図５】図５は、コード化システムの態様において使用されるコードパケットジェネレータを示す。
【図６】図６は、コード化システムの態様において使用される方法を示す。
【図７】図７は、コード化システムの態様において使用されるコード化ロジックを示す。
【発明を実施するための形態】
【００１９】
１つ以上の態様において、通信システムにおいて、データをコード化するために動作するコード化システムが提供される。１つの態様において、コード化システムは、単一の復号化ステージを使用して復号化を可能にする低密度ジェネレータ行列を使用してデータを符号化し、それにより、メモリを保存し、計算の複雑さを最小化する。例えば、システムは、無線通信ネットワークによる通信についてのデータを符号化するのに適切している。システムは、無線ネットワーク環境においての使用について特に適しているが、任意のネットワーク環境において使用されることがあり、通信ネットワーク、インターネットなどの公衆ネットワーク、バーチャルプライベートネットワーク（virtual private network）（ＶＰＸ）などのプライベートネットワーク、ローカルエリアネットワーク、ワイドエリアネットワーク、長距離ネットワーク、または、任意のタイプのデータネットワークを含むが、限定されない。
【００２０】
図１は、コード化システムの１つの態様を含むネットワーク１００を示す。ネットワーク１００は、データネットワーク１０６を使用する装置１０４と通信するサーバ１０２を含む。１つの態様において、サーバ１０２は、任意のタイプの通信リンク１０８を使用して、ネットワーク１０６と通信するために動作する。ネットワーク１０６は、任意のタイプの有線および／または無線ネットワークであることがある。ネットワーク１０６は、任意の適切のタイプの無線通信リンク１１０を使用して、装置１０４と通信する。サーバ１０２は、コンテントおよび／またはサービスを装置１０４に伝送するために動作する。１つの装置が示されているが、システムは、任意の数またはタイプの装置とともに使用することについて適している。
【００２１】
１つの態様において、サーバ１０２は、ネットワーク１０６による伝送についてのデータを受信するために動作し、コードパケットストリーム１１４を生成するためにこのデータを符号化するコード化ロジック１１２を含む。１つの態様において、コード化ロジック１１２は、生成されたコードパケットが受信する装置よって効率的に復号化できるように並列のＬＤＧＭコード化を使用してデータを符号化する。例えば、復号化処理は、メモリではなく、また、計算上高価ではない。
【００２２】
１つの態様において、コードパケットストリーム１１４において、コードパケットのそれぞれは、そのパケットを符号化するために使用される符号化する構成を完全に説明するために動作するパケットヘッダおよび／または他のパラメータを含む。パケットヘッダがコード化の構成が使用されたことを完全に説明するので、システムは、それらが受信されたコードパケットを処理するために受信する装置を更新することなく、新しいコード化の構成が使用されることがあるため、スケーラブル（scalable）である。
【００２３】
コードパケットがコード化ロジック１１２によって生成された後、コードパケットストリーム１１４は、パス１１６によって示されるようにネットワーク１０６によって装置１０４に伝送される。装置１０４がコードパケットストリーム１１６を受信したとき、伝送されたデータを取得するためのコードパケットストリームを復号化するためにその復号器１１８を使用する。１つの態様において、装置１０４は、パケットヘッダが受信されたコードパケットを復号化するために必要な全ての情報を提供するため、使用される符号化する構成に関する特別な知識を必要としない。他の１つ態様では、装置１０４は、使用されるコード化する構成を認識しており、その知識に基づいて受信されたパケットストリームを復号化するために動作する。
【００２４】
したがって、コード化システムの態様は、柔軟に、計測可能なようにネットワークによる伝送についてのデータを符号化するために動作する。ネットワーク１００がコード化システムのただ１つの実行を説明し、他の実行が態様の範囲内で可能であることが注目されるべきである。
【００２５】
図２は、コード化システムの態様において使用されるコード化ロジック２００を示す。例えば、コード化ロジック２００は、図１に示されるコード化ロジック１１２として使用されることが適している。コード化ロジック２２０は、マルチプレクサ（ＭＵＸ）２０２、符号器２０４、および制御ロジック２０６を含む。
【００２６】
制御ロジック２０６は、ＣＰＵ、プロセッサ、ゲートアレイ、ハードウェアロジック、メモリ要素、バーチャルマシン、ソフトウェア、および／または「Ｎ」コードパケットを含むコードパケットストリーム（Ｃ）２１０を形成するために、データパケット（ｄＫ）がコード化されることを可能にする符号器２０４およびＭＵＸ２０２の動作を制御するために構成されたハードウェアおよびソフトウェアの任意の組み合わせを含む。１つの態様において、制御ロジック２０６は、Ｎ−ｘコードパケット２０８を形成するために入力データパケットｄＫの順列を識別する順列制御シグナル２１２を提供するために動作する。例えば、１つの態様において、ｘはｋと等しい、しかし、ｘは他の選択された値に設定されることがある。したがって、多かれ少なかれＭＵＸ２０２への入力についてのコードパケットを生成することは可能であり、これは、さらにコードパケットストリーム２１０において多かれ少なかれデータパケットを含むことが可能であることを意味する。制御ロジック２０６は、さらに、Ｎ−ｘコードパケット２０８を生成するために、データパケットの順列をウェイトするために使用されるウェイトを識別するウェイト制御シグナル２１４を提供するために動作する。さらなる順列およびウェイトの詳細な説明は、この本文の他のセクションにおいて提供される。
【００２７】
１つの態様において、符号器２０４は、ＣＰＵ、プロセッサ、ゲートアレイ、ハードウェアロジック、メモリ容量、バーチャルマシン、ソフトウェア、および／またはハードウェアおよびソフトウェアの任意の組み合わせを含む。１つの態様において、符号器２０４は、Ｎ−ｘコードパケット２０８を生成するための順列制御シグナル２０２およびウェイト制御シグナル２１４に基づいて受信されたデータパケットｄＫを符号化するために動作する。Ｎ−ｘコードパケット２０８は、ＭＵＸ２０２への入力である。１つの態様において、ＭＵＸ２０２は、多重化された出力を生成するための多重の入力を多重化するために動作可能な任意の適したハードウェアおよび／またはソフトウェア含む。１つの態様において、ＭＵＸ２０２は、データパケットｄｋ、Ｎ−ｘコードパケット２０８およびＭＵＸ制御シグナル２１６を受信する。ＭＵＸ制御シグナル２１６は、ＭＵＸ２０２がどのようにコードパケットストリーム２１０を生成するためにデータパケットｄｋとともにＮ−ｘコードパケット２０８を多重化するか示す。
【００２８】
動作中、制御ロジック２０６は、順列制御シグナル２１２、ウェイト制御シグナル２１４、およびＭＵＸ制御シグナル２１６を生成するために動作する。データパケットｄｋは、コード化のために受信される。データパケットｄｋは、ＭＵＸ２０２および符号器２０４への入力である。符号器２０４は、ＭＵＸ２０２への入力であるＮ−ｘコードパケット２０８を生成するための順列制御シグナル２１２およびウェイト制御２１４を使用して並列ＬＤＧＭコード化メカニズムに基づいてデータパケットを符号化するために動作する。ＭＵＸ２０２は、コードパケットストリーム２１０を生成するためにＭＵＸ制御シグナル２１６に基づいてデータパケットｄＫとともにＮ−ｘコードパケットを多重化するために動作する。例えば、ＭＵＸ２０２は、コードパケットストリーム２１０を生成するためにデータパケットｄＫとともにＮ−ｘコードパケットを平等に配信してもよい。したがって、システムは、ネットワークによる伝送についてデータをコードパケットストリームに符号化するために動作する並列ＬＤＧＭコード化メカニズムを提供する。コードパケットストリーム２１０は、単一ステージ復号器(single stage decoder)を使用して受信デバイスにおいて迅速に且つ効率的に復号されることができ、その結果、メモリ使用および計算の複雑さが最小化される。
【００２９】
符号器の動作
下記は、コード化システムの態様の動作の詳細な説明である。
【００３０】
図３において、コード化システムの態様において使用されるＬＤＧＭコードの構成のコードの説明をするグラフィカル表示を示す。例えば、ＬＤＧＭコード３００は、図２に示されるコード化システムにおいて使用されることに適している。図３において、ｋデータパケットコードは、３０２で一般に示しされた円として表される。ＬＤＧＭコード３００は、レッグ（Ｌ＋１）の並列な連結を提供する、ここでレッグは長方形によって表され、３０４で一般に示しされる。
【００３１】
ここで、レッグ３０６を参照すると、このレッグは、ｋデータパケット３０２を任意に順序し、この動作は、π１として表される。このレッグ３０６は、ウェイトＷ１の各々にＣ１コードパケットを生成する。同様に、レッグ３０８の順列動作は、πＬとして表され、このレッグは、ＷＬの各々にＣＬコードパケットを生成する。レッグπ０がＷ０＝１およびデータパケットの数に等しい（つまり、コード化ロジック２００のｘと等しい）Ｃ０に基づいて動作することが注目されるべきである。レッグ１からＬによって生成されたコードパケットは、符号器２０８の（Ｎ−ｘ）コードパケットを含むことがさらに注目されるべきである。
【００３２】
ウェイトＷＪのＣＪコードパケットを生成するレッグＪの一般的なケースを検討する。レッグＪは、πＪによって表されるｋデータパケットを任意に順列する。レッグＪによって生成された第１のコードパケットは、順列されたデータパケットのセットから第１のＷＪエントリを使用する。第２のコードパケットは、順列されたデータパケットのセットから次のＷＪエントリを使用し、以下同様。行列形式において、レッグＪによって生成されたコードパケットは、
【数１】
0005474558.tif 000002
【００３３】
として表すことができ、ここでＤは、ｋデータシンボルを表すベクターであり、ＰＪは、順列行列（ｋ×ｋ）である。行列Ｇ（ＣＪ、ＷＪ）は、段階構造を用いる（ＣＪ×ｋ）行列である。Ｇ（ＣＪ、ＷＪ）の第１の列は、１に等しいエントリ１からＷＪおよび、０に等しいエントリの残りを有している。Ｇ（ＣＪ、ＷＪ）の第２の列には、１に等しいエントリＷＪ＋１から２＊ＷＪ、０に等しいエントリの残りを有しており、以下同様。
【００３４】
全コードの生じるジェネレータ行列は、
【数２】
0005474558.tif 000003
【００３５】
として表すことができ、コードシンボルＣは、ＧおよびデータシンボルＤの積である。
【００３６】
したがって、１つの態様において、システムは、ｋデータパケットおよび（Ｎ−ｘ）コードパケットの組み合わせを含むＮのコード化されたパケットを生成するために動作する。Ｎのコード化されたパケットは、０からＬに番号付けられた（Ｌ＋１）レッグによって生成される。第１のレッグは、順列行列Ｐ０およびＧ（Ｃ０、Ｗ０）を使用する。システマティック（systematic）コードのケースにおいて、Ｐ０は、恒等行列であり、Ｃ０がｋ、Ｗ０が１である。したがって、第０レッグは、ウェイト１の各々のｋコードパケットを生成する。
【００３７】
例として、ｋ＝４およびＮ＝８であるシステマティックコードを検討する。レッグの数が３（Ｌ＝３）と、および（Ｃ、Ｗ）値がテーブルにおいて下記に示される通りと想定されるであろう。
【数３】
0005474558.tif 000004
【００３８】
Ｇ（Ｃ１、Ｗ１）行列は、下記に示される。
【数４】
0005474558.tif 000005
【００３９】
Ｇ（Ｃ２、Ｗ２）行列は、下記に示される。
【数５】
0005474558.tif 000006
【００４０】
コードのジェネレータ行列Ｇの例は、下記に示しされる。
【数６】
0005474558.tif 000007
【００４１】
一般に、行列Ｇは、疎行列であり、すなわち、コードは、低密度ジェネレータ行列コードである。
【００４２】
図４は、コード化システムの態様におけるコード化データについてのコード化ロジック２００の機能的な図を示す。コード化ロジック２００は、一般に４０２で示される（Ｌ＋１）レッグを含む、ここで各レッグは、データパケット４０４を受信するように、コードパケット（Ｃ）４０６を生成するように動作するコードパケットジェネレータを含む。各ジェネレータは、コードパケット４０６を生成するためにデータパケット４０４の順列（Ｐ）および選択されたウェイト（Ｗ）使用する。例えば、ジェネレータ４１２は、コードパケットＣ１を形成するために第１のデータパケット４０４の順列（Ｐ１）および第１のウェイト（Ｗ１）のセットを使用する。例えば、数Ｃ１は、１からコードパケットの任意の選択された数までの値の中で変動してもよい。同様に、他のジェネレータは、選択された順列および関連したウェイトを使用してコードパケットを形成する。
【００４３】
１つの態様において、ジェネレータは、それらが順列制御シグナル４０８に基づいて使用するであろう順列を決定するために動作する。例えば、順列制御シグナル４０８は、図２に示される制御ロジック２０６によって提供される。順列制御シグナル４０８は、各ジェネレータがコードパケットを生成するために使用するであろうデータパケットの順列を説明し、および／または、選択する。例えば、１つの態様において、各レッグは、任意の数を含み、ジェネレータは、異なるシードで初期化され、そして、各レッグについて任意に順列を決定する。他の１つの態様において、比較的ｋにとって重要である数ｐが選択され、初期シードａ０がさらに選択される。そして、ａ１＝（ａ０＋Ｐ）モジュロｋ、ａ２＝（ａ１＋ｐ）モジュロｋ、以下同様。この場合において、各レッグは、ｐおよびａ０について異なる値を選択する。
【００４４】
さらに、ウェイト制御シグナル４１０は、各ジェネレータがコードパケットの希望の数を生成するデータパケットの関連する順列をウェイトするために使用するであろうウェイトを説明し、および／または選択する制御ロジック２０６によってジェネレータにさらに提供される。例えば、１つの態様において、ウェイトは、前もって固定される。他の１つの態様において、ウェイトは、データパケットのセットがコード化される必要があるごとに、決定される。
【００４５】
１つの態様において、順列制御シグナル４０８およびウェイト制御シグナル４１０は、予め定義された順列およびウェイトを選択するために動作し、および／または各レッグによって使用されることになっている順列およびウェイトを生成するために使用される。したがって、コード化ロジック２００の動作は、ジェネレータ４０２によって生成された全てのコードパケットの総和（すなわち、Ｃ０＋Ｃ１＋Ｃ２＋Ｃ３＋…＋ＣＬ）を表すコードパケットを生成する。
【００４６】
１つの態様において、各コードパケットは、それを生成させたレッグに関する情報を含む。例えば、各コードパケットは、そのコードパケットを生成するために使用される順列およびウェイトに関する情報を含む。他の１つの態様において、レッグの全ての構造は、任意の受信する装置が受信されたコードパケットを処理することができるように、前もって知るようになっていることがある。
【００４７】
図５は、コード化システムの態様において使用されるコードパケットジェネレータ５００を示す。例えば、ジェネレータ５００は、図４に示される各レッグ４０２において使用することに適している。ジェネレータ５００は、処理ロジック５０２、ウェイトロジック５０４、順列ロジック５０６を含み、すべてデータバス５０８と連結される。
【００４８】
順列ロジック５０６は、ＣＰＵ、プロセッサ、ゲートアレイ、ハードウェアロジック、メモリ要素、バーチャルマシン、ソフトウェア、および／またはハードウェアおよびソフトウェアの任意の組み合わせを含む。順列ロジック５０６は、データパケット５１０を受信するため、順列制御シグナル５１２に基づくデータ順列を生成するために動作する。
【００４９】
１つの態様において、ウェイトロジック５０４は、コードパケットを形成するデータ順列をウェイトするために使用されることになっている値の多くを含む。例えば、コードパケットを形成するために、データ順列において各データアイテムは、関連したウェイトを与えられる。そして、ウェイトされたデータは、コードパケットを形成するために組み合わせられる。１つの態様において、ウェイト制御シグナル５１４は、コードパケットを生成するための各データ順序変更とともに使用されることになっているウェイトを決定するために使用される。
【００５０】
処理ロジック５０２は、ＣＰＵ、プロセッサ、ゲートアレイ、ハードウェアロジック、メモリ要素、バーチャルマシン、ソフトウェア、および／または、ハードウェアおよびソフトウェアの任意の組み合わせを含む。１つの態様において、処理ロジック５０２は、コードパケット５１６を生成するためにウェイトされたデータ順列を組み合わせるために動作する。例えば、ウェイトされたデータ値は、排他的論理和（exclusive OR function）（ＸＯＲ）を使用して、処理ロジック５０２によって組み合わせられる。
【００５１】
１つの態様において、コード化システムは、少なくとも１のプロセッサ、例えば、処理ロジック５０２におけるプロセッサによって実行されたとき、本明細書で説明された機能を提供するコンピュータ可読媒体に記憶された１つ以上のプログラム命令（「命令」）または「コード」のセットを含む。例えば、コードのセットは、フロッピー（登録商標）ディスク、ＣＤＲＯＭ、メモリカード、ＦＬＡＳＨメモリ装置、ＲＡＭ、ＲＯＭ、または処理ロジック５０２と接続するメモリ装置またはコンピュータ可読媒体の他のタイプなどのコンピュータ可読媒体から処理ロジック５０２にロードされることがある。他の１つの態様において、コードのセットは、外部の装置またはネットワークリソースから処理ロジック５０２にダウンロードされることがある。コードのセットは、実行されたとき、本明細書で説明されるようにコード化システムの態様を提供する。
【００５２】
図６は、コード化システムの態様において使用される方法６００を示す。明確にすると、方法６００は、図２に示されるコード化ロジック２００および図５に示しされるジェネレータ５００を参照して本明細書で説明される。例えば、１つの態様において、制御ロジック２０６は、下記に説明される機能を実行するためにコード化ロジック２００を制御するために１つ以上のコードのセットを実行する。
【００５３】
ブロック６０２において、各レッグについてのウェイトの符号器が決定される。１つの態様において、符号器２０４の各レッグについてウェイトロジック５０４は、ウェイト制御シグナル５１４に基づいてウェイトを決定する。例えば、ウェイトは、コードシンボルを形成するために、どのようにしてデータの順列のデータ要素が組み合わせられるか説明する。
【００５４】
ブロック６０４において、符号器の各レッグについてのデータの順列が決定される。１つの態様において、符号器２０４の各レッグについての順列ロジック５０６は、順列制御シグナル５１２に基づいてデータの順列を決定する。例えば、データの順列は、受信されたデータ値５１０から選択されたデータ項目の任意の部分を含む。
【００５５】
ブロック６０６において、データ値は、受信される。１つの態様において、コード化ロジック２００は、コード化についてのデータｄｋを受信するために動作する。
【００５６】
ブロック６０８において、Ｎ−ｘコードパケットは、生成される。例えば、符号器２０４は、ｄｋデータ値を符号化およびＮ−ｘコードパケット２０８を生成するために動作する。１つの態様において、Ｎ−ｘコードパケットは、上記で説明されたコード化にしたがって形成される。例えば、符号器２０４の各レッグは、関連したウェイトでウェイトされる関連するデータ順列を有し、結果は、コードパケットの選択された数を形成するために、処理ロジック５０２によって組み合わせられる。符号器２０４のレッグによって生成されたコードパケットの総和は、Ｎ−ｘコードパケットを形成する。
【００５７】
ブロック６１０において、データおよびＮ−ｘコードパケットは、コードパケットストリームに多重化される。例えば、ＭＵＸ２０２は、データおよびＮ−ｘコードパケット２０８を受信するために動作し、コードパケットストリーム２１０を形成するためにそれらをともに多重化する。
【００５８】
ブロック６１２において、コードパケットストリームは、１以上の受信装置に伝送される。例えば、コードパケットストリーム２１０は、図１に示しされた装置１０４にネットワークによって伝送される。
【００５９】
ブロック６１４において、テストは、コード化スキームのいずれかの調整の実行が必要かどうかを決定するために実行される。１つの態様において、制御ロジック２０６は、いずれかの調整が必要かどうかを決定するために動作する。現在のコード化スキームに調整がない場合、そのとき、方法は、伝送についてのデータのコード化を持続するためにブロック６０６に進む。コード化スキームの調整がある場合、そのとき、方法は、新しい順序変更および／またはウェイトが決定されることがあるブロック６０２に進む。
【００６０】
したがって、方法６００は、コード化システムの態様を提供するために動作する。方法６００がただ１つの実行を表し、他の実行が態様の範囲内で可能であることが注目されるべきである。
【００６１】
コード設計
次の記述は、コード化システムにおいて使用されるＬＤＧＭの設計を説明する。
【００６２】
下記に説明される設計はただ１つの実行であって、他の実行はコード化システムの態様によって提供されることがある。
【００６３】
各レッグについてのレッグＬの数および（Ｃｉ，Ｗｉ）の値は、コードの性能を決定する。１つの態様において、選択されたＬＧＤＭコードは、次の制約、
【数７】
0005474558.tif 000008
【００６４】
に適合する、ここで、各レッグＬｉ、１からＬ、において、
【数８】
0005474558.tif 000009
【００６５】
特定のコード化において、ウェイトｗ[Ｗ＞１]であるコードパケットの端数は、Ωｗによって示される。そして、ウェイトｗのコードパケットの数は、［（Ｎ−ｘ）＊Ωｗ］である。これらのパケットを生成するために使用されることができるレッグの数は、
【数９】
0005474558.tif 000010
【００６６】
である。
【００６７】
［（Ｎ−ｘ）＊Ωｗ］コードパケットは、そして、これらのＬｗレッグを横切って一様に分散される。したがって、Ｌおよび（Ｃｉ、Ｗｉ）値を決定する代わりに、コードの程度分散が決定される。この程度分散はコードパケットのウェイトおよび各特定のウェイトについてのコードパケットの少数を指定する。
【００６８】
図７は、コード化システムの態様において使用されるコード化ロジック７００を示す。例えば、コード化ロジック７００は、図１に示したコード化ロジック１１２として使用されることに適している。１つの態様において、コード化ロジック７００は、本明細書で説明されるようにコード化システムの態様を提供するように構成された１以上のモジュールを含む少なくとも１つのプロセッサによって実行される。例えば、各モジュールは、ハードウェア、ソフトウェア、またはそれらの任意の組み合わせを含む。
【００６９】
コード化ロジック７００は、順列ロジック５０６を含む１つの態様において、１つ以上の順列を生成するための手段（７０２）を有する第１のモジュールを含む。コード化ロジック７００は、さらに、ウェイトロジック５０４を含む態様において、ウェイトを決定するために手段（７０４）を有する第２のモジュールを含む。コード化ロジック７００は、さらに、処理ロジック５０２を含む１つの態様において、１つ以上のコードパケットを計算するための手段（７０６）を有する第３のモジュールを含む。コード化ロジック７００は、さらに、ＭＵＸ２０２を含む１つの態様において、コードパケットストリームを形成するためにデータおよび１つ以上のコードパケットを多重化するための手段（７０８）を有する第４のモジュールを含む。
【００７０】
本明細書に含まれた態様と関連して説明された様々な実例となるロジック、ロジカルブロック、モジュール、およびサーキット（circuit）は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）または他のプログラミング可能なロジックデバイス、ディスクリートゲートまたはトランジスタロジック、ディスクリートハードウェア構成要素、または、本明細書で説明された機能を実行するように設計されたそれらの任意の組み合わせ、とともに実装され、実行されることがある。汎用プロセッサは、マイクロプロセッサであることがあるが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または、定常マシンであることがある。プロセッサは、計算デバイスの組み合わせ、例えば、ＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰのコアと接続された１つ以上のマイクロプロセッサ、または他の任意のそのような構成として実施されることもある。機能、そのようなものを実行するためのユニットまたはモジュール
本明細書に含まれる態様と関連して説明された方法またはアルゴリズムのステップは、ハードウェア、プロセッサによって実行されたソフトウェアモジュール、または２つの組み合わせに直接実施されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または、当業者において知られている記憶媒体の形式に存在してもよい。典型的な記憶媒体は、記憶媒体からプロセッサが情報を読み、記憶媒体に情報を書き込むことができるようなプロセッサにつながれる。代替として、記憶装置は、プロセッサと一体的であることがある。プロセッサおよび記憶装置は、ＡＳＩＣに存在してもよい。ＡＳＩＣは、ユーザの端末に存在してもよい。代替として、プロセッサおよび記憶媒体は、ユーザ端末において、ディスクリート要素として存在してもよい。
【００７１】
示された態様の説明は、当業者が本発明を作成、または使用することを可能にするために提供される。これらの態様の様々な変更は、当業者に容易に明白かもしれない、ここで定義された総括的な法則は、発明の主旨または範囲から外れずに、他の態様に、例えば、インスタントメッセージサービスあるいは任意の一般的な無線データ通信アプリケーション中で適用されることがある。したがって、本発明は、ここで示された態様に限定することを意図されていないが、ここに示しされた法則と特徴と一致する最も広い範囲を与えられる。「典型的」という語は、ここで「見本、例、または実例として役立つ」ことを意味するために排他的にしようされる。本明細書で「典型的」として説明されている任意の態様は、他の態様に対して好まれる、または、有利であると解釈される必要はない。
【００７２】
それゆえに、ここでコード化システムの態様が説明され、記述された一方で、それの主旨または本質的な特徴から外れずに、様々な変更を行うことができることが認識されるだろう。したがって、ここの開示および記述は、説明するために意図されるが、次の特許請求の範囲である発明の範囲を限定すること意図するものではない。
以下に本件出願当初の特許請求の範囲に記載された発明を付記する。
［１］データをコード化するための方法であって、前記データの１つ以上の順列を生成することと、各順列に関連したウェイトの決定することと、前記関連したウェイトに基づいた各順列からの１つ以上のコードパケットを計算することと、前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化することと、を含む方法。
［２］さらに、ネットワークによって前記コードパケットストリームを伝送することを含む［１］に記載の方法。
［３］前記計算することは、（Ｎ−ｘ）コードパケットの総和を生成するために前記１つ以上コードパケットを計算することを含む［１］に記載の方法。
［４］前記多重化することは、前記コードパケットストリームを生成するためにｋデータパケットとともに前記（Ｎ−ｘ）コードパケットを多重化することを含み、ここで前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む［３］に記載の方法。［５］前記計算することは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算することを含む［１］に記載の方法。
［６］前記計算することは、
【数１０】
0005474558.tif 000011
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算することを含む［１］に記載の方法。
［７］前記生成することは、前記データの前記１つ以上の順列の各々を任意に生成することを含む［１］に記載の方法。
［８］データをコード化するための装置であって、前記データの１つ以上の順列を生成するように構成された順列ロジックと、各順列に関連したウェイトを決定するように構成されたウェイトロジックと、前記関連したウェイトに基づく各順序から１つ以上のコードパケットを計算するように構成された処理ロジックと、前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化するように構成されたマルチプレクサと、を含む装置。
［９］前記処理ロジックは、（Ｎ−ｘ）コードパケットの総和を生成するために前記１つ以上のコードパケットを計算するように構成された［８］に記載の装置。
［１０］前記マルチプレクサは、前記コードパケットストリームを生成するために、ｋデータとともに前記（Ｎ−ｘ）コードパケットを多重化するように構成され、ここで前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む［９］に記載の装置。
［１１］前記処理ロジックは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成された［８］に記載の装置。
［１２］前記処理ロジックは、
【数１１】
0005474558.tif 000012
として表された低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するように構成された［８］に記載の装置。
［１３］前記順列ロジックは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された［８］に記載の装置。
［１４］データをコード化する装置であって、前記データの１つ以上の順列を生成するための手段と、各順列と関連したウェイトを決定するための手段と、
前記関連したウェイトに基づいた各順列から１つ以上のコードパケットを計算するための手段と、前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化するための手段と、を含む装置。
［１５］さらに、ネットワークによって前記コードパケットストリームを伝送するための手段を含む［１４］の装置。
［１６］  前記計算するための手段は、（Ｎ−ｘ）コードパケットの総和を生成するための前記１つ以上のコードパケットを計算するための手段を含む［１４］の装置。
［１７］  前記多重化するための手段は、前記コードパケットストリームを生成するためにｋデータとともに前記（Ｎ−ｘ）コードパケットを多重化するための手段を含む、ここで前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む［１６］に記載の装置。
［１８］前記計算するための手段は、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するための手段を含む［１４］に記載の装置。
［１９］前記計算するための手段は、
【数１２】
0005474558.tif 000013
として表される低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するための手段を含む［１４］に記載の装置。
［２０］前記生成するための手段は、前記データの前記１つ以上の各々を任意に生成するための手段を含む［１４］に記載の装置。
［２１］コンピュータにデータの１つ以上の順列を生成させるための第１のコードのセットと、前記コンピュータに各順列に関連したウェイトを決定させるための第２のコードのセットと、前記コンピュータに前記関連したウェイトに基づいて各順列から１つ以上のコードパケットを計算させるための第３のコードのセットと、前記コンピュータに前記データおよび前記１つ以上のコードパケットをコードパケットストリームに多重化させるための第４のコードのセットと、を有するコンピュータ可読媒体を含むコンピュータプログラムプロダクト。
［２２］さらに、前記コンピュータにネットワークによって前記コードパケットストリームを伝送させるために第５のコードのセットを含む［２１］のコンピュータ可読媒体。
［２３］前記第３のコードのセットは、前記コンピュータに（Ｎ−ｘ）コードパケットの総和を計算するように構成された［２１］のコンピュータ可読媒体。
［２４］前記第４のコードのセットは、前記コードパケットストリームを生成するためにｋデータとともに前記（Ｎ−ｘ）コードパケットを多重化するように構成され、ここで前記コードパケットストリームは、Ｎコード化された総和を含む［２３］のコンピュータ可読媒体。
［２５］前記第３のコードのセットは、前記順列および前記ウェイトを示す低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成された［２１］のコンピュータ可読媒体。
［２６］前記第３のコードのセットは、
【数１３】
0005474558.tif 000014
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成された［２１］のコンピュータ可読媒体。
［２７］前記第１のコードセットは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された［２１］のコンピュータ可読媒体。
［２８］データをコード化するための方法を実行するように構成された少なくとも１つのプロセッサであって、前記データの１つ以上の順列を生成するための第１のモジュールと、
各順列と関連するウェイトを決定するための第２のモジュールと、前記関連したウェイトに基づく各順列から１つ以上のコードパケットを計算するための第３のモジュールと、前記データおよび前記１以上のコードパケットをコードパケットストリームに多重化するための第４のモジュールと、を含む少なくとも１つのプロセッサ。
［２９］さらに、ネットワークによって前記コードパケットを伝送するための第５のモジュールを含む［２８］に記載の少なくとも１つのプロセッサ。
［３０］前記第３のモジュールは、（Ｎ−ｘ）コードパケットの総和を計算するように構成された［２８］に記載の少なくとも１つのプロセッサ。
［３１］前記第４のモジュールは、前記コードパケットストリームを生成するためにｋデータとともに前記（Ｎ−ｘ）コードパケットを多重化するように構成され、ここで前記コードパケットストリームは、Ｎコード化されたパケットの総和を含む［３０］に記載の少なくとも１つのプロセッサ。
［３２］前記第３のモジュールは、前記順列および前記ウェイトを示す低密度ジェネレータを使用して前記１つ以上のコードパケットを計算するように構成された［２８］に記載の少なくとも１つのプロセッサ。
［３３］前記第３のモジュールは、
【数１４】
0005474558.tif 000015
として表される低密度ジェネレータ行列を使用して前記１つ以上のコードパケットを計算するように構成された［２８］の少なくとも１つのプロセッサ。
［３４］前記第１のモジュールは、前記データの前記１つ以上の順列の各々を任意に生成するように構成された［２８］の少なくとも１つのプロセッサ。
【図１】
0005474558.tif 000021
【図２】
0005474558.tif 000022
【図３】
0005474558.tif 000023
【図４】
0005474558.tif 000024
【図５】
0005474558.tif 000025
【図６】
0005474558.tif 000026
【図７】
0005474558.tif 000027