【手続補正書】
【提出日】平成19年9月25日(2007.9.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
出力記号の１群を生成する方法であって、１群は１つ以上の出力記号であり、各出力記号は出力アルファベットから選択され、入力アルファベットからそれぞれ選択される順列の複数の入力記号を含む入力ファイルが、このような群の１セットから回復可能であるような該群であり、該方法は、
該群のキーＩを得るステップであって、該キーがキーアルファベットから選択され、該キーアルファベットにおける可能なキーの数が該入力ファイルにおける入力記号の数よりもずっと大きい、ステップと、
Ｉの所定の関数にしたがって、該群のリストＡＬ（Ｉ）を計算するステップであって、ＡＬ（Ｉ）は、該群に関連付けられたＷ（Ｉ）個の関連付けられた入力記号を示し、重みＷは、少なくとも２つの値の間で変化する正の整数であり、Ｉの少なくとも１つの値に対して１より大きい、ステップと、
ＡＬ（Ｉ）によって示される該関連付けられた入力記号の所定の関数から、該群における各出力記号の出力記号値を生成するステップと、
を含む方法。
【請求項２】
前記キーＩを得るステップが、ランダム関数または擬似ランダム関数にしたがってキーＩを計算するステップを含む、請求項１に記載の方法。
【請求項３】
前記計算するステップが、Ｉのランダム関数または擬似ランダム関数にしたがってＷ（Ｉ）を計算するステップを含む、請求項１に記載の方法。
【請求項４】
前記計算するステップが、Ｉのランダム関数または擬似ランダム関数にしたがってＡＬ（Ｉ）を計算するステップを含む、請求項１に記載の方法。
【請求項５】
前記計算するステップが、前記群における出力記号の数Ｇ（Ｉ）を計算するステップを含み、該数Ｇ（Ｉ）が正の整数であり、該数Ｇ（Ｉ）がＩのランダム関数または擬似ランダム関数にしたがって計算される、請求項１に記載の方法。
【請求項６】
前記計算するステップが、
Ｉの所定の関数および確率分布にしたがって、重みＷ（Ｉ）を計算するステップであって、該確率分布が少なくとも２つの正の整数上にあり、そのうちの少なくとも１つが１より大きい、ステップと、
リストＡＬ（Ｉ）のリストエントリを計算するステップと、
Ｗ（Ｉ）個のリストエントリが計算されるまで、リストＡＬ（Ｉ）のリストエントリを計算するステップを繰り返すステップと、
を含む、請求項１に記載の方法。
【請求項７】
前記Ｗ（Ｉ）を計算するステップが、Ｗが前記キーアルファベット上の所定の分布を近似するようなＷ（Ｉ）を決定するステップを含む、請求項６に記載の方法。
【請求項８】
前記所定の分布が一様分布である、請求項７に記載の方法。
【請求項９】
前記所定の分布がつり鐘曲線分布である、請求項７に記載の方法。
【請求項１０】
前記所定の分布は、Ｗ＝１が１／Ｋの確率を有し、ここで、Ｋが前記入力ファイルにおける入力記号の数であり、そしてＷ＝ｉがｉ＝２，．．．，Ｋに対して１／ｉ（ｉ−１）の確率を有する、請求項７に記載の方法。
【請求項１１】
前記ＡＬ（Ｉ）によって示される関連付けられた入力記号の前記所定の関数が、リード−ソロモン符号によって決定される、請求項１に記載の方法。
【請求項１２】
前記入力アルファベットおよび前記出力アルファベットが同じアルファベットである、請求項１に記載の方法。
【請求項１３】
前記入力アルファベットが２Mi個の記号を含み、各入力記号がＭｉビットを符号化し、前記出力アルファベットが２Mo個の記号を含み、各出力記号の群がＭをビットを符号化する、請求項１に記載の方法。
【請求項１４】
各後続キーＩがその先行キーよりも１大きい、請求項１に記載の方法。
【請求項１５】
出力記号の複数の群を符号化する方法であって、各群は請求項１に記載され、該方法は、
生成されるべき該出力記号の群の各々に対するキーＩを生成するステップと、
および
該生成された出力記号の群の各々をデータイレーズチャネルを介して送信されるべき出力シーケンスとして出力するステップと、
をさらに含む方法。
【請求項１６】
各キーＩが他の選択されるキーとは独立に選択される、請求項１５に記載の方法。
【請求項１７】
前記ＡＬ（Ｉ）を計算するステップが、
前記入力ファイルにおける入力記号の数Ｋを少なくとも近似的に識別し、かつ重みＷ（Ｉ）を識別するステップと、
Ｋより大きいかまたはＫに等しい最小素数Ｐを決定するステップと、
ＰがＫより大きい場合、Ｐ−Ｋ個のパディング入力記号で該入力ファイルを少なくとも論理的にパディングするステップと、
１≦Ｘ＜Ｐである第１の整数Ｘ、および０≦Ｙ＜Ｐである第２の整数Ｙを生成するステップと、
１〜Ｗ（Ｉ）の各Ｊに対して、ＡＬ（Ｉ）における第Ｊ番目のエントリを（（Ｙ＋（Ｊ−１）・Ｘ）  ｍｏｄ  Ｐ）に設定するステップと、
を含む、請求項１に記載の方法。
【請求項１８】
前記各Ｊに対してＡＬ（Ｉ）における第Ｊ番目のエントリを設定するステップが、
配列Ｖにおける第１のエントリＶ［Ｊ＝０］をＹに設定するステップと、
１〜Ｗ（Ｊ）−１の各Ｊに対して、該配列Ｖにおける第Ｊ番目のエントリＶ［Ｊ］を（（Ｖ［Ｊ−１］＋Ｘ）  ｍｏｄ  Ｐ）に設定するステップと、
該配列Ｖを該リストＡＬ（Ｉ）として使用するステップと、
を含む、請求項１７に記載の方法。
【請求項１９】
ソースから目的地にパケット通信チャネルを介してデータを送信する方法であって、該方法が、
ａ）送信されるべき該データを入力記号の順列セットとして構成するステップであって、各入力記号は、入力アルファベットから選択され、該データにおける位置を有する、ステップと、
ｂ）出力記号の複数の群を生成するステップであって、各出力記号が出力アルファベットから選択され、該複数の群の各群が、以下のステップによって生成され、該ステップは、
キーアルファベットから、生成される該群のキーＩを選択するステップと、
Ｉの関数として重みＷ（Ｉ）を決定するステップであって、ここで、重みＷは、少なくとも２つの値の間および該キーアルファベット上で変化する正の整数であり、該キーアルファベットにおける少なくともいくつかのキーに対しては０より大きい、ステップと、
Ｉの関数にしたがってＷ（Ｉ）個の該入力記号を選択し、したがって、該群に関連付けられるＷ（Ｉ）個の入力記号のリストＡＬ（Ｉ）を形成するステップと、
該群における出力記号の数Ｇ（Ｉ）を決定するステップと、
該関連付けられるＷ（Ｉ）個の入力記号の所定の値関数から該群における各出力記号の値Ｂ（Ｉ）を計算するステップとを含む、ステップと、
ｃ）該複数の群のうちの少なくとも１つの出力記号の群のうちの少なくとも１つを、複数のパケットの各々にパケット化するステップと、
ｄ）該複数のパケットを該パケット通信チャネルを介して送信するステップと、
ｅ）該複数のパケットのうちの少なくともいくつかを該目的地で受信するステップと、
ｆ）該複数の受信されたパケットから該データを復号化するステップと、
を含む方法。
【請求項２０】
前記データを復号化するステップが、
１）受信された出力記号の各群を処理するステップであって、
ａ）該群の前記キーＩを決定するステップと、
ｂ）該群の前記重みＷ（Ｉ）を決定するステップと、
ｃ）該群の前記Ｗ（Ｉ）個の関連付けられた入力記号を決定するステップとを含む、ステップと、
２）任意の入力記号を復号化するのに十分な情報が受信されたかどうかを決定するステップと、
３）該受信された情報から復号化され得る入力記号を復号化するステップと、
を含む、請求項１９に記載の方法。
【請求項２１】
前記キーＩを決定するステップが、前記パケット通信チャネルを介して受信されたパケットにおいて供給されたデータから該キーＩを少なくとも部分的に決定するステップを含む、請求項２０に記載の方法。
【請求項２２】
前記データを復号化するステップが、
１）受信された出力記号の各群を処理するステップであって、
ａ）該受信された群の前記重みＷ（Ｉ）を決定するステップと、
ｂ）該受信された群の前記Ｗ（Ｉ）個の関連付けられた入力記号を決定するステップと、
ｃ）出力記号の群のテーブルにおける群の出力記号の値Ｂ（Ｉ）を、該受信された群に対する該重みＷ（Ｉ）および前記Ｗ（Ｉ）個の関連付けの位置とともに格納するステップとを含む、ステップと、
２）出力記号のさらなる群を受信し、それらをステップ１）およびそのサブステップにしたがって処理するステップと、
３）たかだか群サイズの重みを有し、使い古された出力記号の群として表記されていない出力記号の各群、ＧＯＳ１、に対して、以下のステップ、
ａ）ＧＯＳ１に対応する入力記号の位置に対して入力記号を計算するステップと、
ｂ）該出力記号の群のテーブルにおける接続された出力記号の群を識別するステップであって、接続された出力記号の群は、ステップ３）ａ）において処理された少なくとも１つの入力記号の関数である出力記号の群である、ステップと、
ｃ）ステップ３）ａ）において処理された該入力記号に独立になるように該接続された出力記号の群を再計算するステップと、
ｄ）ステップ３）ａ）において処理された該入力記号の独立性を反映するようにステップ３）ｃ）において再計算された該出力記号の群の重みを決定するステップと、
ｅ）ＧＯＳ１を使い古した出力記号として表記するステップと、を実行するステップと、
４）前記入力記号の順列セットが前記目的地で回復されるまで、該ステップ１）からステップ３）を繰り返すステップと、
を含む、請求項１９に記載の方法。
【請求項２３】
前記表記するステップが、前記使い古した出力記号にゼロの重みを割り当てるステップである、請求項２２に記載の方法。
【請求項２４】
前記表記するステップが、前記出力記号の群のテーブルから前記使い古した出力記号の群を除去するステップを含む、請求項２２に記載の方法。
【請求項２５】
前記パケット化するステップが、複数の出力記号の群のうちの少なくとも１つの群から少なくとも１つの出力記号の群を各パケットにパケット化するステップであり、該方法が、パケット内の出力記号の１群の位置を該出力記号の群のキーの一部として使用するステップをさらに含む、請求項１９に記載の方法。
【請求項２６】
前記計算するステップが、前記群における出力記号の数Ｇ（Ｉ）を計算するステップを含み、該Ｇ（Ｉ）は、正の整数であり、Ｉのすべての値に対して同じ正の整数である、請求項１に記載の方法。
【請求項２７】
出力記号のグループを生成する方法であって、グループは１個以上の出力記号であり、出力記号の各々は出力アルファベットから選択され、該グループは、各々が入力アルファベットから選択される順列の複数の入力記号を含む入力ファイルがこのようなグループのセットから回復可能であるようなものであり、該方法は、
所与のグループに対して、該グループに関連付けられるＷ個の関連付け入力記号を指示するリストＡＬを決定するステップであって、Ｗは正の整数であり、少なくとも２つのグループは各々のＷ個の関連付けに対して異なる値を有し、少なくとも１つのグループに対してＷは２以上であり、可能なグループの個数は入力ファイル内の入力記号の個数よりずっと多い、ステップと、
ＡＬにより指示されるＷ個の関連付け入力記号の所定の関数から、前記グループ内の各々の出力記号の出力記号値を生成するステップと、
を含むことを特徴とする方法。
【請求項２８】
さらに、
所与のグループに関連付けられたキーＩからＷを計算するステップと、
キーＩからＡＬを計算するステップと、
を含むことを特徴とする請求項２７に記載の方法。
【請求項２９】
前記Ｗを計算するステップと前記ＡＬを計算するステップとは、確率分布を使用することを特徴とする請求項２８に記載の方法。
【請求項３０】
入力ファイルの情報コンテンツを送信する方法であって、該入力ファイルは、各々が入力アルファベットから選択される順列の複数の入力記号であり、該入力ファイルは、各々が出力アルファベットから選択される出力記号のセットから回復可能なものであり、該方法は、
出力記号の複数のグループを生成するステップであって、グループは１以上の出力記号であり、前記複数のグループの各々のグループは、
ａ）前記グループに関連付けられたＷ個の関連付け入力記号を指示するリストＡＬを決定するステップであって、Ｗは正の整数であり、少なくとも２つのグループは各々のＷ個の関連付けに対して異なる値を有し、少なくとも１つのグループに対してＷは２以上であり、可能なグループの個数は入力ファイル内の入力記号の個数よりずっと多い、ステップと、
ｂ）ＡＬにより指示されるＷ個の関連付け入力記号の所定の関数から、前記グループ内の各々の出力記号の出力記号値を生成するステップと、
により生成される、ステップと、
生成された複数のグループを送信するステップと、
を含むことを特徴とする方法。
【請求項３１】
前記複数のグループを生成するステップは、複数のソースの各々において、独立した複数個のグループを生成するステップであり、該複数個のグループは、前記複数のソースの各々のソースが、該複数のソースの他のソースで生成されたリストの参照を必要とすること無く、ある独立ソースが他のソースの情報出力と完全に重複すること無く、関連付け入力シンボルのリストを決定するという点で独立であることを特徴とする請求項３０に記載の方法。
【請求項３２】
さらに、
あるチャネルにより提供される情報コンテンツが、他のチャネルの情報コンテンツと完全に重複すること無く、複数のチャネルにわたって複数のグループを配信するステップを含むことを特徴とする請求項３０に記載の方法。
【請求項３３】
前記決定するステップは、
キーアルファベットから、生成されるグループに対するキーＩを選択するステップであって、該キーアルファベットは入力記号の順列のセットに含まれる入力記号の個数よりもずっと多い個数を含む、ステップと、
Ｉの関数として重みＷ（Ｉ）を決定するステップと、
Ｉの関数に従って入力記号のＷ（Ｉ）を選択ステップであって、それにより前記グループに関連付けられたＷ（Ｉ）個の入力記号のリストＡＬ（Ｉ）を形成する、ステップと、
前記グループ内の出力記号の個数Ｇ（Ｉ）を決定するステップと、
関連付けられたＷ（Ｉ）個の入力記号の所定の値関数から、前記グループのＧ（Ｉ）個の出力記号の各々の値Ｂ（Ｉ）を計算するステップと、
を含むことを特徴とする請求項３０に記載の方法。
【請求項３４】
前記複数のグループを生成するステップは、複数のソースの各々において、独立した複数個のグループを生成するステップであり、該複数個のグループは、前記複数のソースの各々のソースが、該複数のソースの他のソースで生成されたキーの参照を必要とすること無く、ある独立ソースが他のソースの情報出力と完全に重複すること無く、キーを選択するという点で独立であることを特徴とする請求項３３に記載の方法。
【請求項３５】
さらに、
あるチャネルにより提供される情報コンテンツが、他のチャネルの情報コンテンツと完全に重複すること無く、複数のチャネルにわたって複数のグループを配信するステップを含むことを特徴とする請求項３３に記載の方法。
【請求項３６】
複数のチャネルを介してソースからデータを送信する方法であって、該方法は、
ａ）順列の入力記号のセットとして送信されるデータを編成するステップと、
ｂ）複数のチャネルの各々に対して出力記号の複数のグループを生成するステップであって、該複数のグループの各々のグループは、
１）キーアルファベットから、生成されるグループに対するキーＩを選択するステップであって、該キーアルファベットは入力記号の順列のセットに含まれる入力記号の個数よりもずっと多い個数を含む、ステップと、
２）Ｉの関数として重みＷ（Ｉ）を決定するステップであって、重みＷは、少なくとも２つの正の整数値をとり、前記キーアルファベットに含まれる少なくともいくつかのキーに対して１より大きい値をとる、ステップと、
３）Ｉの関数に従って入力記号のＷ（Ｉ）を選択するステップであって、それにより前記グループに関連付けられたＷ（Ｉ）個の入力記号のリストＡＬ（Ｉ）を形成する、ステップと、
４）前記グループの出力記号の個数Ｇ（Ｉ）を決定するステップと、
５）関連付けられたＷ（Ｉ）個の入力記号の所定の値関数から、前記グループのＧ（Ｉ）個の出力記号の各々の値Ｂ（Ｉ）を計算するステップと、
により生成される、ステップと、
ｃ）前記複数のグループの少なくとも１つを複数のパケットの各々にパケット化するステップと、
ｄ）前記複数のチャネルにわたって前記複数のパケットを送信するステップであって、該複数のチャネルの少なくとも２つは、キーＩに対して互いに異なる値として生成されたグループを含むパケットを運ぶ、ステップと、
を含むことを特徴とする方法。
【請求項３７】
前記ソースは、自ソースのキーＩに対する値を生成する単一のソースを含み、前記複数のチャネルの任意の２つから受信されるグループが完全な重複とはならないように、前記複数のチャネルにわたって結果のグループを配信する、ことを特徴とする請求項３６に記載の方法。
【請求項３８】
前記複数のチャネルの任意の２つから受信されるグループが完全な重複とはならないように、キーＩに対する前記値は、前記複数のチャネルの各々に対して独立に選択されることを特徴とする請求項３６に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
図８ａにおいて示すプロセスの１つの変形例を図８ｂに示す。そこで、出力記号の各群が処理されるステップ８５０、８５２、８５５および８６０を実行する代わりに、図８ｂのステップ８５１、８５３、８５６および８６１に示すように、Ｒ’の値が後の処理のために実行スケジュールに格納される。保留された実行処理の例を、ステップ８７０、８７５、８８０および８８５により示されるステップを含む図８ｃに示す。この変形例において、図６に示すフローチャートは、ステップ６０５においてＥをゼロに初期化することによって改変される。実行スケジュールの保留された処理は、受信した記号がファイル全体を復号するのに十分であるとデコーダが判定した後、例えば、すべての入力記号が回復可能であると分かった後のステップ６４０にて行われ得る。いくつかの場合において、特に入力記号が大きい場合、スケジュールの実行は、入力ファイルまたはその部分が受信器側で必要となるまで保留され得る。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１３７
【補正方法】変更
【補正の内容】
【０１３７】
図１６〜１９は、図１５において記載するプロセスの実行例の１スナップショットを示す。この例において、群サイズは、すべての群に対して２であり、出力記号の４個の群（１６０３０、１６０３５、１６０４０、１６０４５）は、図１６において矢印つきの線で示す関連付け（１６０００、１６００５、１６０１０、１６０１５、１６０２０、１６０２５）とともに受信されている。まず、キー２３および値（Ａ，Ｄ）、キー１５９および値（ＲＳ＿１（Ａ，Ｅ，Ｆ），ＲＳ＿２（Ａ，Ｅ，Ｆ））、キー３３および値（Ｂ，Ｃ）、ならびにキー８３５および値（ＲＳ＿１（Ｃ，Ｆ，Ｇ，Ｈ），ＲＳ＿２（Ｃ，Ｆ，Ｇ，Ｈ））を有する出力記号の群（第１および第３の出力記号の群は、重み２を有し、その値関数が識別関数であり、第２および第４の群は、それぞれ重み３および重み４を有し、その値関数がリード−ソロモン値関数である）が、図１７に示すようにＧＯＳＤＳ５０５に受信および格納される。ＧＯＳＤＳ５０５における行番号は、図１８に示すように、出力記号の重みに対応する行においてＲＯＷ＿ＬＩＳＴ中に格納される。重み２の出力記号の群は、ＧＯＳＤＳ５０５の行０および行２にある。このように、ＲＯＷ＿ＬＩＳＴ（０）は、重みＷＴ＿ＶＡＬ（０）＝２を有する出力記号の群に対応し、図１８に示すように、行番号０および２を含む。同様に、ＷＴ＿ＶＡＬ（１）＝３であり、かつＲＯＷ＿ＬＩＳＴ（１）は１を含み、ＷＴ＿ＶＡＬ（２）＝４であり、かつＲＯＷ＿ＬＩＳＴ（２）は３を含む。
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2001189665.tif 000001
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2001189665.tif 000002
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図８ｃ
【補正方法】変更
【補正の内容】
【図８ｃ】
2001189665.tif 000003