(57)【要約】      （修正有）【課題】LT符号という名の無レート符号を使った低計算量のネットワーク再エンコード方法および装置を提供する。【解決手段】ネットワーク再エンコード装置が、ネットワークに接続された少なくとも一つの通信装置に送信されるべきエンコードされたシンボルをエンコードし直すために意図される。このネットワーク再エンコード装置は、送信される準備のできた生成された出力ノードを定義する新しいLT符号を作り出すために、LT符号シンボルによって定義される出力ノードであって、エンコードされたシンボルを表し、かつ、出力ノードがタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算の結果をそれぞれ表す出力ノードを、既知の値をもつ選ばれた入力ノードおよび／または出力ノードを組み合わせることによって再エンコードする。【選択図】図１
2010178332.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに接続された少なくとも一つの通信装置に送信されるべきエンコードされたシンボルをエンコードし直すネットワーク再エンコード方法であって、送信される準備のできた生成された出力ノードを定義する新しいLT符号シンボルを作り出すために、
LT符号シンボルによって定義される出力ノードであって、エンコードされたシンボルを表し、かつ、前記出力ノードがタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算（単数または複数）の結果をそれぞれ表す出力ノードを、
既知の値をもち部分デコードされたノードと呼ばれる選ばれた入力ノード（単数または複数）および／または出力ノード（単数または複数）を組み合わせることによって、再エンコードする段階を有しており、
前記組み合わせる段階の間に、前記部分デコードされたノードが互いの間のXORブール演算によって組み合わされ；
前記組み合わせる段階の間に、生成された出力ノードの次数の現在の分布の次数のうちで、第一の所定の基準分布の同じ次数との最高の差をもつ次数であって、この次数をもつ生成された出力ノードを作り出すことを許容する次数を判別することによって始め、次いで少なくとも一つの部分デコードされたノードを組み合わせることによってこの次数をもつ生成された出力ノードを作り出すことを特徴とする、方法。
【請求項２】
前記組み合わせる段階において、所定の発見的方法によってこの次数をもつ生成された出力ノードを作り出すことを許容する次数を判別することを特徴とする、請求項１記載の方法。
【請求項３】
前記生成された出力ノードを作り出したのち、前記入力ノードの現在の分布を第二の所定の基準分布と比較して、少なくとも一つの入力ノードが生成された出力ノードを作り出すためにあまりに多く使われたかどうかを判定し、もしそうであれば、この入力ノードが、前記生成された出力ノードにリンクされる諸入力ノードに組み合わされるときに前記生成された出力ノードの次数を不変のままにすることを許容するなら、前記入力ノードの前記現在の分布を正規化するために、前記生成された出力ノードにおける前記あまりに多く使われた入力ノードの少なくとも一つを、あまりにまれに使われた入力ノードによって置き換えることを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記生成された出力ノードが、前記あまりに多く使われた入力ノードを有し、2に等しい次数をもつ出力ノードと組み合わされることを特徴とする、請求項３記載の方法。
【請求項５】
前記組み合わせる段階において、送信される準備のできた前記生成された出力ノードを作り出したのち、前記生成された出力ノードの次数の前記現在の分布および前記入力ノードの前記現在の分布を更新することを特徴とする、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
前記組み合わせる段階において、前記発見的方法は、生成されるべきノードの次数が、デコードされた入力ノードおよび少なくとも一つの隣接ノードをもつ入力ノードを含むカバーされる入力ノードの数以下であることを検査することを含む、請求項２記載の方法。
【請求項７】
前記発見的方法がさらに、条件
【数１】
2010178332.tif 000029
が検証されるかどうかを検査することを含み、ここで、dは生成されるべき出力ノードの決定された次数であり、n(k)はdより小さい次数kの既知である部分デコードされたノードの数であることを特徴とする、請求項６記載の方法。
【請求項８】
ネットワークに接続された少なくとも一つの通信装置に送信されるべきエンコードされたシンボルをエンコードし直すネットワーク再エンコード装置であって、送信される準備のできた生成された出力ノードを定義する新しいLT符号シンボルを作り出すために、
LT符号シンボルによって定義される出力ノードであって、エンコードされたシンボルを表し、かつ、前記出力ノードがタナー・グラフにおいてタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算（単数または複数）の結果をそれぞれ表す出力ノードを、
既知の値をもち部分デコードされたノードと呼ばれる選ばれた入力ノード（単数または複数）および／または出力ノード（単数または複数）を組み合わせることによって、再エンコードするよう構成された再エンコード手段を有しており；
前記再エンコード手段は、前記部分デコードされたノードを互いの間のXORブール演算を実行することによって組み合わせるよう構成されており；
前記再エンコード手段は、生成された出力ノードの次数の現在の分布の次数のうちで、第一の所定の基準分布の同じ次数との最高の差をもつ次数であって、この次数をもつ生成された出力ノードを作り出すことを許容する次数を判別し、次いで少なくとも一つの部分デコードされたノードを組み合わせることによってこの次数をもつ生成された出力ノードを作り出すよう構成されている、
ことを特徴とする、ネットワーク再エンコード装置。
【請求項９】
前記再エンコード手段が、所定の発見的方法を適用することによってこの次数をもつ生成された出力ノードを作り出すことを許容する次数を判別するよう構成されていることを特徴とする、請求項８記載のネットワーク再エンコード装置。
【請求項１０】
前記再エンコード手段が、前記生成された出力ノードを作り出したのち、前記入力ノードの現在の分布を第二の所定の基準分布と比較して、少なくとも一つの入力ノードが生成された出力ノードを作り出すためにあまりに多く使われたかどうかを判定し、もしそうであれば、この入力ノードが、前記生成された出力ノードにリンクされる諸入力ノードに組み合わされるときに前記生成された出力ノードの次数を不変のままにすることを許容するなら、前記入力ノードの前記現在の分布を正規化するために、前記生成された出力ノードにおける前記あまりに多く使われた入力ノードの少なくとも一つを、あまりにまれに使われた入力ノードによって置き換えるよう構成されていることを特徴とする、請求項８または９に記載のネットワーク再エンコード装置。
【請求項１１】
前記再エンコード手段が、前記生成された出力ノードを、前記あまりに多く使われた入力ノードを有し、2に等しい次数をもつ出力ノードと組み合わせるよう構成されていることを特徴とする、請求項１０記載のネットワーク再エンコード装置。
【請求項１２】
前記再エンコード手段が、送信される準備のできた前記生成された出力ノードを作り出したのち、前記生成された出力ノードの次数の前記現在の分布および前記入力ノードの前記現在の分布を更新するよう構成されていることを特徴とする、請求項８ないし１１のうちいずれか一項記載のネットワーク再エンコード装置。
【請求項１３】
前記再エンコード手段が、生成されるべきノードの次数が、デコードされた入力ノードおよび少なくとも一つの隣接ノードをもつ入力ノードを含むカバーされる入力ノードの数以下であることを検査することを含む発見的方法を適用するよう構成されていることを特徴とする、請求項８ないし１２のうちいずれか一項記載のネットワーク再エンコード装置。
【請求項１４】
前記再エンコード手段が、条件
【数２】
2010178332.tif 000030
が検証されるかどうかを検査することをさらに含む発見的方法を適用するよう構成されており、ここで、dは生成されるべき出力ノードの決定された次数であり、n(k)はdより小さい次数kの既知である部分デコードされたノードの数であることを特徴とする、請求項１３記載のネットワーク再エンコード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シンボル・データ処理に、より詳細には、受信されたエンコードされたシンボルのデコードおよびネットワークに接続されている通信装置に送信されるべきシンボル・データのエンコードに関する。
【背景技術】
【０００２】
当業者に知られているように、通信装置間での伝送の間にデータが失われたり破損したりすることが起こりうる。この場合、受信機は送信機に、失われたまたは破損したデータを再び送信するよう要求してもよいし、あるいは最初からデータのコピーが二つ送信されてもよい。別の解決策は、送信されるべきデータを符号、より詳細には消失訂正符号（erasure  correcting  code）によってエンコードすることである。この場合、コンテンツの全データをデコードできるためにコンテンツの全データを受信し終わるのを待つことは必要でない。送り手によって送信されたデータ全部を再構築するために必要とされるのはコンテンツ・データの（十分な）一部分だけだからである。
【０００３】
エンコード方法のうちでも、「ネットワーク符号化（network  coding）」という名のエンコード方法はいくつかの利点をもたらす。このエンコード方法は非特許文献１によって提案されている。これは、たとえば無線および／またはインターネット・ネットワークにおいて使用されうる。ネットワーク符号化は、ネットワークの内部（または中間）ルーターが、データaおよびbを受け取ったときに、受け取ったデータaまたはbを単に転送する代わりに、c＝f(a,b)の型のデータの組み合わせを送ることを許容する。よって、いくつかのネットワークではルーティングは最大フローに達するのに十分強力ではないように見えても、ネットワーク符号化はネットワーク上での最大フロー（maximal  flow）に達することを許容する。しかし、これはルーターが受信したデータを送信する前に該データに対して計算を実行でき、最終的な各受信機が受け取るエンコードされたデータをデコードできることを必要とする。
【０００４】
最大フローに達することを許容する関数の組f(  )の計算はNP困難であることが証明されているので、いくつかの確率的な方式が提案されている。
【０００５】
たとえば、無レート式の（rateless）ランダム線形ネットワーク符号（RLNC:  random  linear  network  codes）を使う方式が非特許文献２によって提案されている。この方式はいくつかの利点がある：実装するのがかなり簡単で、完全に分散される（fully  distributed）ことができるのである。この方式によれば、ネットワークの各ルーターは、受け取ったデータ（入力）のランダムな線形結合をそのネットワークの他の諸ルーターに転送する。受信機は、係数の行列およびデータ（a  matrix  of  coefficient  and  data）をも受信し、それにより、この行列が可逆であればガウスの消去法またはガウス・ジョルダンの消去法を通じて受け取ったデータをデコードすることが許容される。
【０００６】
ネットワーク符号化は諸シンボルを独立して生成することを許容するので、シンボルの無限ストリームが生成できる。しかしながら、ランダム線形ネットワーク符号は、エンコードの際のみならずデコードの際にも複雑な計算を必要とする。さらに、RLNCはガロア体GF(2k)に対して作用するので、有限体上での演算を欠く汎用プロセッサ上でのエンコードおよびデコードには好適ではない。
【０００７】
ラプター符号（Raptor  codes）を使う別の方式が非特許文献３によって提案されている。この方式は、一対のエンコードされたシンボルをXORブール演算によって組み合わせることからなる再エンコード方法を導入する。だが、この方式もデコードの際にガウスの消去法を必要とし、したがって、ラプター・ネットワーク符号化はパフォーマンスおよび属性の面でのその利点を失ってしまう。
【０００８】
非特許文献４によって提案されたもう一つの方式もある。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】ルドルフ・アールスウェーデ（Rudolf  Ahlswede）ら、「ネットワーク情報フロー（Network  information  flow）」、IEEE  Transactions  On  Information  Theory  2000
【非特許文献２】T・ホー（Ho）ら、「マルチキャストのためのランダム線形ネットワーク符号化アプローチ（A  random  linear  network  coding  approach  to  multicast）」、IEEE  Transaction  On  Information  Theory  2000
【非特許文献３】N・トモス（Thomos）、P・フロサール（Frossard）、「ラプター・ネットワーク符号化を用いた協働的ビデオ・ストリーミング（Collaborative  video  streaming  with  Raptor  network  coding）」、ICME  2008
【非特許文献４】プドゥシェリ（Puducheri）・Sら、「消去リレー・チャネルのための符号化方式（Coding  Schemes  for  an  erasure  relay  channel）」、Proc.  IEEE  International  Symposium  on  Information  Theory,  ISIT、2007年6月24日、pp.666-670
【発明の概要】
【発明が解決しようとする課題】
【００１０】
よって、本発明の目的は、ルビー変換符号（Luby  Transform  codes）（またはLT符号）という名の無レート符号（rateless  codes）を使ったネットワーク再エンコード方法および装置を提案することである。その構造は、低計算量のエンコーダおよびデコーダの使用を許容する。
【００１１】
LT符号はマイケル・ルビー（Michael  Luby）によって２００２年IEEEコンピュータ科学基礎シンポジウム（IEEE  Symposium  on  Foundations  of  Computer  Science  2002）において提案されたパリティ符号であることが想起される。LT符号は入力ノードと出力ノードとの間の対応を確立するタナー・グラフによって表現できる。タナー・グラフの各出力ノードは、ネットワークから受信されたデコードされるべきエンコードされたシンボル（またはLT符号シンボル（あるいはまたLT符号語））であり、入力ノードと呼ばれる発見すべき一つまたは複数のエンコードされていない（またはデコードされた）シンボルに（エッジを通じて）リンクされており、これらの入力ノードの間のXORブール演算（単数または複数）の結果を表す。よって、通信装置（たとえばルーターまたはユーザー端末のような）のデコーダがエンコードされたシンボル（すなわちLT符号シンボル）をそれぞれのリンクを表すデータとともに受信するとき、これらのエンコードされたシンボルがデコードされなければならないタナー・グラフの出力ノードをなす。デコードはたとえば「信頼伝搬（BP:  belief-propagation）デコード法」によって行われ、このタナー・グラフの入力ノードをなすエンコードされていない（デコードされた）シンボルを生成する。ある出力ノードと諸入力ノードとの間のリンク（またはエッジ）の数はこの出力ノードの次数（degree）を定義する。よって、タナー・グラフの出力ノードの次数の分布を構築することが可能である。信頼伝搬デコード方法によってLT符号を効率的にデコードできるかどうかは、具体的な次数の分布に依拠する。この効率は、LT符号の次数の分布がいわゆる「堅牢ソリトン（robust  soliton）」分布であるので一層重要となる。
【課題を解決するための手段】
【００１２】
本発明は、ネットワークの少なくとも一つの通信装置に送信されるべきエンコードされたシンボル（またはデータ）をエンコードし直すために意図されたネットワーク再エンコード方法であって、送信される準備のできた生成された出力ノードを定義する新しいLT符号を作り出すために、LT符号シンボルによって定義される出力ノードを再エンコードする段階を有する方法を提供する。前記出力ノードは、エンコードされたシンボルを表し、かつ、前記出力ノードがタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算（単数または複数）の結果をそれぞれ表す。前記再エンコードする段階は、部分デコードされたノードと呼ばれる選ばれた入力ノード（単数または複数）および／または既知の値をもつ出力ノード（単数または複数）を組み合わせることによる。
【００１３】
本発明に基づく方法は、別個にまたは組み合わせて考慮される、特に以下のような追加的な特徴を含んでいてもよい。
−部分デコードされたノードをそれらの間のXORブール演算によって組み合わせてもよい。
−生成された出力ノードの次数の現在の分布の諸次数のうちで、第一の選ばれた基準分布と同じ次数での最高の差をもち、かつ、この次数をもつ生成された出力ノードを作り出すことを許容する次数を判別することによって始めてもよく、次いで、少なくとも一つの部分デコードされたノード（すなわち、内部的な再エンコード・ステップの途中で一時的に生成されるノード）を組み合わせることによってこの次数をもつ生成された出力ノードを作り出してもよい。
【００１４】
△選ばれた発見的方法によって、この次数をもつ生成された出力ノードを作り出すことを許容する次数を判別してもよい。
【００１５】
△前記生成された出力ノードを作り出したのち、前記入力ノードの現在の分布を第二の所定の基準分布と比較して、少なくとも一つの入力ノードが生成された諸出力ノードを作り出すためにあまりに多く使われたかどうかを判定してもよく、もしそうであれば、この入力ノードが、前記生成された出力ノードにリンクされる諸入力ノードに組み合わされるときに前記生成された出力ノードの次数を不変のままにすることを許容するなら、前記入力ノードの前記現在の分布を平準化するために、前記生成された出力ノード中に前記あまりに多く使われた入力ノードの少なくとも一つを、使用があまりに少なかった入力ノードによって置き換えてもよい。
【００１６】
・前記生成された出力ノードを、前記あまりに多く使われた入力ノードを有し、2に等しい次数をもつ出力ノードと組み合わせてもよい。
【００１７】
△送信される準備のできた前記生成された出力ノードを作り出したのち、生成された諸出力ノードの次数の現在の分布および諸入力ノードの現在の分布を更新してもよい。
【００１８】
△前記発見的方法は、生成されるべきノードの次数が、デコードされた入力ノードおよび少なくとも一つの隣接ノード（すなわち、タナー・グラフにおいてその入力ノードがリンクされている出力ノード）をもつ入力ノードを含むカバーされる入力ノードの数以下であることを検査してもよい。
【００１９】
・前記発見的方法がさらに、条件
【数１】
2010178332.tif 000003
が検証されるかどうかを検査することを含んでもよい。ここで、dは生成されるべき出力ノードの決定された次数であり、n(k)はdより小さい次数kの既知である部分デコードされたノードの数である。
【００２０】
本発明はまた、ネットワークの少なくとも一つの通信装置に送信されるべきエンコードされたシンボル（またはデータ）をエンコードし直すために意図されたネットワーク再エンコード装置であって、送信される準備のできた生成された出力ノードを定義する新しいLT符号シンボルを作り出すために、
LT符号シンボルによって定義される出力ノードであって、エンコードされたシンボルを表し、かつ、前記LT符号シンボルがタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算（単数または複数）の結果をそれぞれ表す出力ノードを、
既知の値をもち部分デコードされたノードと呼ばれる選ばれた入力ノード（単数または複数）および／または出力ノード（単数または複数）を組み合わせることによって、再エンコードするよう構成された再エンコード手段を有する、ネットワーク再エンコード装置をも提供する。
【００２１】
本発明に基づくネットワーク再エンコード装置は、別個にまたは組み合わせて考慮される、特に次のような追加的な特徴を含んでいてもよい。
−その再エンコード手段は、前記部分デコードされたノードを互いの間のXORブール演算を実行することによって組み合わせるよう構成されていてもよい。
−前記再エンコード手段は、生成された出力ノードの次数の現在の分布の次数のうちで、第一の所定の基準分布と同じ次数での最高の差をもつ次数であって、この次数をもつ生成された出力ノードを作り出すことを許容する次数を判別し、次いで少なくとも一つの部分デコードされたノードを組み合わせることによってこの次数をもつ生成された出力ノードを作り出すよう構成されていてもよい。
【００２２】
△その再エンコード手段は、選ばれた発見的方法を適用することによってこの次数をもつ生成された出力ノードを作り出すことを許容する次数を判別するよう構成されていてもよい。
【００２３】
△その再エンコード手段は、前記生成された出力ノードを作り出したのち、前記入力ノードの現在の分布を第二の所定の基準分布と比較して、少なくとも一つの入力ノードが生成された諸出力ノードを作り出すためにあまりに多く使われたかどうかを判定し、もしそうであれば、この入力ノードが、この生成された出力ノードにリンクされる諸入力ノードに組み合わされるときにこの生成された出力ノードの次数を不変のままにすることを許容するなら、前記入力ノードの前記現在の分布を平準化するために、前記生成された出力ノード中の前記あまりに多く使われた入力ノードの少なくとも一つを、使用があまりに少なかった入力ノードによって置き換えるよう構成されていてもよい。
【００２４】
・その再エンコード手段は、前記生成された出力ノードを、前記あまりに多く使われた入力ノードを有し、2に等しい次数をもつ出力ノードと組み合わせるよう構成されていてもよい。
【００２５】
・その再エンコード手段は、前記生成された出力ノードを、1に等しい次数をもつ二つのあまりに多く使われた入力ノードを有する出力ノードと組み合わせるよう構成されていてもよい。
【００２６】
△その再エンコード手段は、送信される準備のできた前記生成された出力ノードを作り出したのち、前記生成された出力ノードの次数の前記現在の分布および前記入力ノードの前記現在の分布を更新するよう構成されていてもよい。
【００２７】
△その再エンコード手段は、生成されるべきノードの次数が、デコードされた入力ノードおよび少なくとも一つの隣接ノードをもつ入力ノードを含むカバーされる入力ノードの数以下であることを検査することを含む発見的方法を適用するよう構成されていてもよい。
【００２８】
・その再エンコード手段が、条件
【数２】
2010178332.tif 000004
が検証されるかどうかを検査することをさらに含む発見的方法を適用するよう構成されていてもよい。ここで、dは生成されるべき出力ノードの決定された次数であり、n(k)はdより小さい次数kの既知である部分デコードされたノードの数である。
【００２９】
本発明はまた、ネットワークに接続されることのできる通信設備に備えることを意図されたデコーダであって、
−受信された出力ノードに選ばれたデコード方法を適用してそれぞれのリンクされた入力ノードを取得し、ここで、前記受信された出力ノードはエンコードされたシンボルを表し、かつ、前記出力ノードがタナー・グラフにおいてリンクされている、その値が発見されねばならないデコードされたシンボルを定義する入力ノード間のXORブール演算（単数または複数）の結果をそれぞれ表すLT符号シンボルによって定義され、
−前記入力ノードおよび前記出力ノードを、これらの入力ノードおよび出力ノードが同じタナー・グラフの他の出力ノードおよび入力ノードとの間にもつリンクの数を表す次数と対応付けて定義するデータを記憶する（つまり、選ばれた次数のノードへのランダム・アクセスを許容するインデックスを維持する）、
よう構成されたデコード手段を有するデコーダ、
をも提供する。
【００３０】
このデコーダはさらに、上に呈示した型の、そのデコード手段に結合されたネットワーク再エンコード装置を有していてもよい。
【００３１】
このデコーダはまたさらに、デコードされるべき出力ノードがあるときに、その出力ノードがそのデコード手段によって以前に受領されたかどうかを判定し、もしそうであれば、それが以前に受領されており（そして可能性としてはデコード段階において以前に取得されており）、タナー・グラフ中に再び挿入される必要がないことを伝達するメッセージを生成するよう構成された検出手段をも有していてもよい。
【００３２】
本発明の他の特徴および利点は、以下の詳細な明細および付属の図面を調べれば明白となるであろう。
【図面の簡単な説明】
【００３３】
【図１】ネットワークを通じて互いの間を接続された三つのユーザー通信装置であって、それぞれエンコーダと本発明に基づくデコーダの実施形態の例とを有するものを概略的かつ機能的に示す図である。
【図２】本発明に基づくデコーダのタナー・グラフを概略的に示す図である。
【図３】次数の堅牢ソリトン分布の例（黒）および生成された出力ノードの次数の実際の（または現在の）計算された分布の例（灰色）を示すグラフである。
【図４】入力ノードの一様分布の例（水平線）および生成された入力ノードの現在の（呈示されている）分布の例（黒）を示すグラフである。
【図５】次数4の生成された出力ノードを次数2の出力ノードを用いて洗練することを許容する方法サブステップを概略的に示す図である。
【発明を実施するための形態】
【００３４】
付属の図面は、本発明を完全にするのみならず、必要であればその定義にも寄与するはたらきをしうる。
【００３５】
本発明は、ネットワークを通じて互いの間を接続されている通信装置に低計算量のエンコーダおよびデコーダの使用を許容するために、LT符号シンボルをエンコードし直すことを意図された、ネットワーク再エンコード方法および対応するネットワーク再エンコード装置（D）を提供することをねらいとする。
【００３６】
以下の記述では、ネットワークは移動（またはセルラーまたはその他の電波）通信ネットワーク（CN:  communication  network）であり、該ネットワークにおいて通信装置（CEi:  communication  equipments）は互いの間でコンテンツを、少なくともブロードキャストまたはアドホック・モードにおいて送信できると考える。しかしながら、本発明はこの型のネットワークに限定されるものではない。実際、ネットワークは、特に通信装置が互いの間でピアツーピア（P2P:  peer--to-peer）モードで通信することを許容する場合、DSLネットワークまたは光ファイバー・ネットワークまたはその他のケーブル・ネットワークといった有線（または固定）型でもよい。
【００３７】
さらに、通信装置（CEi）は、互いの間で通信を確立できる限りいかなる型のものでもよい。よって、通信装置（CEi）は、通信モデム（または何らかの等価な通信手段）を有する限り、ルーター、固定パーソナル・コンピュータ、ラップトップ、コンテンツ受信機（たとえば家庭ゲートウェイまたはユーザーの家庭敷地内に位置するセットトップボックス（STB:  set-top  box））、携帯電話もしくはセルラー電話、固定電話または携帯情報端末（PDA:  personal  digital  assistant）であってもよい。
【００３８】
以下の記述では、通信装置（CEi）はユーザーに属し、携帯電話であると考える。図１では三つの携帯電話CE1ないしCE3（i＝1ないし3）のみが示されているが、移動体ネットワークでは、通例、ずっと多くの通信装置がエンコードされたコンテンツの少なくとも一部分を互いの間で交換できる。
【００３９】
図示した例では、各携帯電話CEiは古典的な型のエンコーダEDと本発明に基づくデコーダDCを有する。しかしながら、いくつかの通信装置CEi、特に最初にコンテンツを提供するものは、古典的な型のエンコーダECおよび可能性としては古典的な型のデコーダのみを有するのでもよく、その一方、他のいくつかの通信装置CEi、特にコンテンツを受信して転送するものは本発明に基づくデコーダDCまたは本発明に基づいて適応された古典的な型のデコーダおよび本発明に基づくネットワーク再エンコード装置Dのみを有するのでもよいことを注意しておくことが重要である。
【００４０】
ここで、「古典的な型のエンコーダ」とは、LT符号シンボルを生成するために、エンコードされていない（コンテンツ）データ（またはシンボル（コンテンツ）データ）をエンコードすることのできるエンコーダを意味する。さらに、「古典的な型のデコーダ」とは、古典的な型のエンコーダEDによってまたは本発明に基づくネットワーク再エンコード装置Dによって生成されたLT符号シンボルを、既知でかつ古典的なデコード方法によってデコードできるデコーダを意味する。「本発明に基づくデコーダ」とは、新しい型のデコーダ、すなわち、既知で古典的なデコード方法によってLT符号シンボルをデコードでき、当該デコーダがローカルに結合されているまたは当該デコーダが含む本発明に基づくネットワーク再エンコード装置Dの動作を簡略化するよう適応されたデコーダを意味する。以下の記述では、限定しない例として、デコード方法はいわゆる「信頼伝搬（BP）デコード方法」であると考える。しかしながら、本発明はこのデコード方法に限定されるものではない。
【００４１】
図のように、本発明に基づくネットワーク再エンコード装置Dは、その携帯電話CEiによって一つまたは複数の他の携帯電話CEiから以前に受信されたシンボルを再エンコードするために、関連付けられたデコーダDCに、特にその内部状態に（よってそのタナー・グラフおよび関連するデータに）アクセスするよう構成された再エンコード・モジュール（RM:  re-encoding  module）を有する。
【００４２】
先述したように、これらのLT符号はエンコードされたシンボルを表す。それらは、既知の値をもつ符号化されていないシンボル・データとのそれらのそれぞれのリンクを表す関連付けられたデータをもつデータのブロックにおいて送信される。
【００４３】
LT符号シンボルは、一つまたは複数のシンボル・データの値の組み合わせの結果、より詳細にはシンボル・データ間のXORブール演算（単数または複数）の結果である。換言すれば、ある出力ノードの諸リンクは、その出力ノードを作り出すためにXORブール演算（単数または複数）によって組み合わされた非エンコード・シンボルを指定する。
【００４４】
よって、通信装置CEiのデコーダDCがエンコードされたシンボル（すなわち、LT符号シンボル）をそれらのそれぞれのリンクを表すデータと一緒に受信するとき、該デコーダDCはこれらのエンコードされたシンボルを上記の関連付けられたデータを用いてデコードして、対応する非エンコード・シンボルを復元しなければならない。この目的のため、デコーダDCのデコード・モジュールDDMは、受信されたLT符号シンボル（またはエンコードされたシンボル）をタナー・グラフにフィードする。するとそれらのLT符号シンボルが出力ノードONを定義する。同時に、復元されるべき非エンコード・シンボルはタナー・グラフの入力ノードINを定義し、それらの入力ノードは関連付けられた出力ノードにリンクされる。
【００４５】
タナー・グラフの限定された例が図２に示されている。この例において、10個の出力ノードON（a‐j）が８個（A‐H）のグループのうちの一つまたは複数の入力ノードINにつながれている。より詳細には：
・出力ノードａは入力ノードＡ、Ｂ、Ｃにリンクされており、よって二つのXORブール演算によるそれらの組み合わせの結果である
【数３】
2010178332.tif 000005
・出力ノードｂは入力ノードＢにリンクされており、よってＢに等しい
・出力ノードｃは入力ノードＤ、Ｅにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数４】
2010178332.tif 000006
・出力ノードｄは入力ノードＡ、Ｆにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数５】
2010178332.tif 000007
・出力ノードｅは入力ノードＥ、Ｈにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数６】
2010178332.tif 000008
・出力ノードｆは入力ノードＦ、Ｇにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数７】
2010178332.tif 000009
・出力ノードｇは入力ノードＢ、Ｇにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数８】
2010178332.tif 000010
・出力ノードｈは入力ノードＤ、Ｅ、Ｆにリンクされており、よって二つのXORブール演算によるそれらの組み合わせの結果である
【数９】
2010178332.tif 000011
・出力ノードｉは入力ノードＧ、Ｈにリンクされており、よって一つのXORブール演算によるそれらの組み合わせの結果である
【数１０】
2010178332.tif 000012
・出力ノードｊは入力ノードＣにリンクされており、よってＣに等しい。
【００４６】
留意すべき重要なことは、ある出力ノードONと入力ノードINとの間のリンク（またはエッジ）の数がこの出力ノードONの次数を定義していることである。よって、上記の例では：
・ａの次数は３に等しく、
・ｂの次数は１に等しく、
・ｃの次数は２に等しく、
・ｄの次数は２に等しく、
・ｅの次数は２に等しく、
・ｆの次数は２に等しく、
・ｇの次数は２に等しく、
・ｈの次数は３に等しく、
・ｉの次数は２に等しく、
・ｊの次数は１に等しい。
【００４７】
定義により、以下の記述において：
・「入力ノード（input  node）」とは、タナー・グラフにおいてもとのデータを表すノードである。
・「デコードされた入力ノード（decoded  input  node）」とは、その値が知られている入力ノードである。これは決していかなるリンク（またはエッジ）ももたず、タナー・グラフの出力ノードONのうちには決して存在しない。デコードされていない入力ノード（non-decoded  input  node）は既知の値をもたず、再エンコードの際に使用されることはできない。
・「カバーされる入力ノード（covered  input  node）」とは、デコードされている入力ノードまたは少なくとも一つの隣接ノード（neighbor）（すなわち、タナー・グラフにおいてその入力ノードがリンクされている出力ノード）をもつ入力ノードである。
・「出力ノード（output  node）」とは、エンコードされたシンボルを表すノードである。これは受信されたものでもよいし、あるいはデコード・ステップから帰結したものでもよい。
・「部分デコードされたノード（partially  decoded  node）」（または「既知のノード（known  node）」）とは、デコードされた入力ノードまたは既知の値をもつ出力ノードである。
・「生成された出力ノード（generated  output  node）」とは、ネットワーク再エンコード装置Dによって生成され、一つまたは複数の通信装置CEiに送信される準備ができたノードである。
・「部分生成されたノード（partially  generated  node）」とは、内部的な再エンコード・ステップの間にネットワーク再エンコード装置Dによって一時的に生成されたノードである。
【００４８】
デコーダDCはタナー・グラフを、たとえばメモリのような記憶手段中に記憶する。
【００４９】
再エンコード・モジュールRMは、送信されるべく準備ができた生成された出力ノードを定義する新しいLT符号シンボルを作り出すために、選ばれた部分デコードされたノード（または既知のノード）を、すなわち既知の値をもつ入力ノード（単数または複数）および／または出力ノード（単数または複数）を組み合わせることによって出力ノードを再エンコードするよう構成されている。
【００５０】
これらの組み合わせは、好ましくは部分デコードされたノードの間のXORブール演算からなるが、たとえば有限体（GF(pq)）における線形結合であることもできる。ただし、これはすべてのエッジ（またはリンク）上で線形結合についての係数を記憶することを要求する。
【００５１】
本発明に基づくネットワーク再エンコード装置D（特にその再エンコード・モジュールRM）は好ましくは少なくとも部分的にソフトウェア・モジュールから構成される。だが、電子回路（単数または複数）またはハードウェア・モジュールまたはハードウェア・モジュールとソフトウェア・モジュールの組み合わせ（この場合、再エンコード装置Dはハードウェア・モジュールとソフトウェア・モジュールの間の連携動作を許容するソフトウェア・インターフェースをも有する）から構成されることもできる。ソフトウェア・モジュールのみから構成される場合には、通信装置CEiの（たとえばそのデコーダDC内の）メモリに、あるいはたとえばCD-ROMのような通信装置CEiによって読まれることができる任意のコンピュータ・ソフトウェア製品中に格納されることができる。
【００５２】
出力ノードONを再エンコードするために、再エンコード・モジュールRMはネットワーク再エンコード方法を実装する。この方法について、以下に述べる。
【００５３】
たとえば、本方法は、今までに生成された出力ノードONの次数の現在の（すなわち実際の）分布の次数djのうちで、第一の選ばれた基準分布の同じ次数と最高の差をもち、この次数をもつ生成された出力ノードを作り出すことを許容するものを判別することからなる第一のステップを有する。
【００５４】
この第一の選ばれた基準分布はいわゆる堅牢ソリトン分布であることができる。
【００５５】
これらの分布が離散集合上の分布であることを注意しておく。
【００５６】
生成された出力ノードの次数の堅牢ソリトン分布の例（黒）および生成された出力ノードの次数の実際の（すなわち現在の）分布の例（灰色）の両方が図３のグラフに示されている。
【００５７】
たとえば、再エンコード・モジュールRMはまず、各次数について、現在の分布と第一の選ばれた基準分布との間の差を計算しうる。次いで、その結果をソートできる。図３に示した例では、同じ次数での二つの分布の最高の差は４に等しい次数に、次いで２に等しい次数に、次いで１６に等しい次数に、次いで５に等しい次数に、などに現れることが見て取れる。
【００５８】
生成された出力ノードの次数の現在の分布は再エンコード・モジュールRMによって、それが以前に生成してたとえばメモリのような記憶手段中に記憶した出力ノードに関する情報から、計算されることができる。
【００５９】
現在の分布と第一の選ばれた基準分布との間の次数差の計算は、この現在の分布を第一の選ばれた基準分布に近づけるためには、現在の分布のどの次数が生成されるべき次の出力ノードのために優先的に使われなければならないかを判別することをねらいとする。実際、当業者には知られているように、LT符号のパフォーマンスはその分布に依存し、よって、そうしたパフォーマンスは、LT符号シンボルの現在の分布が堅牢ソリトン分布のような最適分布に近いよう維持されるときに最適になる。
【００６０】
よって、再エンコード・モジュールRMは、ひとたび現在の分布と第一の選ばれた基準分布の間の諸次数差を計算したら、その結果をソートして、現在の分布を向上させるための次数提案のリストを得ることができる。
【００６１】
次いで、次数の各提案djについて、次数djのノードを生成できるかどうかを検査することができる。この目的のためには、発見的方法（heuristic）が使用される。
【００６２】
たとえば、発見的方法は、生成されるべき出力ノードの次数dがカバーされる入力ノード（すなわち、デコードされた入力ノードおよび少なくとも一つの隣接ノードをもつ入力ノード）の数以下であることを検査することからなっていてもよい。この数の値は、デコーダDCによって常に最新（up-to-date）に保たれる。
【００６３】
よりよい結果を与えるために、この発見的方法は、以下に述べるような別の条件を用いて完成されてもよい。
【００６４】
次数rの出力ノードは、rより小さい次数d（d＜r）の出力ノードを生成するために使うことはできないので、再エンコード・モジュールRMは、条件
【数１１】
2010178332.tif 000013
が検証されるかどうかを検査してもよい。ここで、dは生成されるべき出力ノードの決定された次数であり、n(k)はdより小さな次数kの、既知である部分デコードされたノードの数である。換言すれば、次数dの出力ノードを生成するためにdより小さな次数k（k＜d）の部分デコードされたノードが十分にあるかどうかを検査しなければならない。
【００６５】
上記の発見的方法は、次数3の二つのノードがXORブール演算によって組み合わされるとき、これが次数6のノードを与えることは確かではないという事実は考慮していない。実際、第一のノード
【数１２】
2010178332.tif 000014
を第二のノード
【数１３】
2010178332.tif 000015
と組み合わせると、得られるのは次数4のノード
【数１４】
2010178332.tif 000016
である。
【００６６】
よって、再エンコード・モジュールRMは、衝突の期待される数を計算する、より複雑な発見的方法を使ってもよい。
【００６７】
LT符号シンボルのデコード過程の際、ひとたびエンコードされたシンボル（または入力ノード）がデコードされたら、そのシンボルがタナー・グラフの出力ノードとの間にもつすべてのリンク（またはエッジ）がこのタナー・グラフから除去される。したがって、ある入力ノードがデコードされている場合、その入力ノードはそれ以上別のノードには関わらず、いかなる衝突も生じることはない。
【００６８】
n0をデコードされた入力ノードの数とし、ncoveredをカバーされる入力ノードの数とし、ntotalを部分デコードされたノードの総数とする。これらの定義を用いると、次数k＞1のノードが次数Dsの生成されたノードに追加されるときの衝突の数は、パラメータ(k,Ds−n0,ncovered−n0)の超幾何分布（hyper-geometric）則に従い、その平均Cs+1は
Cs+1＝k×(Ds−n0)／(ncovered−n0)
によって与えられる。
【００６９】
したがって、ノードにs＋1番目のノードが追加された後での次数Ds+1は、
Ds+1＝Ds＋k−2×Cs+1
によって与えられる。ここで、D0＝n0とする（D0＝0と設定し、最終ステップにおいてn0を加えることも可能であるが、これはCs+1についての次の定義Cs+1＝k×(Ds／(ncovered−n0))を使うことを必要とする）。
【００７０】
次数dのノードが生成されることができるかどうかを検査するために、以下の二つのサブステップを実装してもよい。
【００７１】
第一のサブステップは、生成されるべきノードの次数dがカバーされる入力ノードの数以下であることを検査することからなる。
【００７２】
第二のサブステップは、希望まれる（または期待される）次数d以下の次数k（k≦d）のすべてのノードを加えて次数D（これは、すべての組み合わせの実行後に結果として得られる次数である）を計算することからなる。D≧dであれば、次数dのノードを生成することが可能であると推定できる。Dは、次数Lのノードを生成することが可能かどうかを検査することからなるアルゴリズムを用いて再帰的に計算できる。すべてのノードを「一発」で統合する（aggregate）のではなく、あるノードを入れることが現在の次数を増やしうる場合にのみそのノードを統合する。実際、ノードを一発で統合する場合、この統合の結果は、それらのノードのどれよりも小さな次数のノードとなることがありうる。（たとえば、
【数１５】
2010178332.tif 000017
である。）したがって、各反復工程において、以前の値およびノードが追加された場合の値のうちの最大のみを保持する。これは、次のようなルーチンによって行うことができる：
D＝0
For  k＝d  to  2
For  i＝1  to  n(k)［ここで、n(k)は次数kの既知のノードの数］
D＝max（D，D＋k−2*k*(D)/(ncovered−n0)）
EndFor
EndFor
Return  D＋n0≦L。
【００７３】
上記の発見的方法は、選ばれた目標を超えることを回避しつつ可能な衝突を考慮するために、その第二のサブステップを別のサブステップで置き換えることによって改善できる。
【００７４】
このもう一つの第二サブステップは、高い次数から低い次数の順に漸進的にノードを追加していくことからなる。その際、ノードが追加されるのは、その次数がLとDとの間の差以下である場合のみである。換言すれば、このノードは、生成されるべき再エンコードされたシンボルにおける残りのスペースを超えてはらなない。というのも、あまりに高い次数のエンコードされたシンボルを生成したくはないからである。したがって、たとえば次数6のノードを生成したい場合、次数5の二つのノードを加えることはできず、次数5の一つのノードと次数1の一つのノードを加えなければならない。これは、次のようなルーチンによって行うことができる：
D＝0
For  k＝d  to  2
For  i＝1  to  n(k)［ここで、n(k)は次数kの既知のノードの数］
D＝max（D，D＋k−2*Econflicts(k,D)）［ここで、Econflicts(k,D)はk*D/(ncovered−n0)に等しく、次数kのノードを次数Dの部分生成されたノードに加えるときに期待できる衝突の数に対応する。ただし、すべてのノードは、ncovered個のカバーされる入力ノードおよびn0個のデコードされた入力ノードをもつタナー・グラフにおいて取るものとする。k＝1については衝突がないので、次数Dのノードは、デコードされた入力ノードとの間にいかなるリンク（またはエッジ）ももってはならない。したがって、最後のステップでは、Econflicts(0,D)＝0として、常にn0を加えることになる。］
If  L≦D＋n0  Then  Return  TRUE
If  k＞L−D  Then  Break（for  i＝1  to  n(k)のループ）
EndFor
EndFor
Return  FALSE。
【００７５】
上記の発見的方法は、可能な衝突を考慮し、衝突を考慮する間に選ばれた目標を超えるのを避けるために、さらに改善されることができる。実際、L−Dより大きな次数k（k＞L−D）のノードを追加することができ、十分な衝突が起これば次数Lのノードをもつことができることを考えることが可能である。これは、次のようなルーチンによって行うことができる：
D＝0
For  k＝d  to  2
For  i＝1  to  n(k)［ここで、n(k)は次数kの既知のノードの数］
D＝max（D，D＋k−2*Econflicts(k,D)）
If  L≦D＋n0  Then  Return  TRUE
If  k−2*Econflicts(k,D)＞L−D  Then  Break（for  i＝1  to  n(k)のループ）
EndFor
EndFor
Return  FALSE。
【００７６】
発見的方法の選択は計算コストおよびLT符号のパフォーマンスに影響をもつことを注意しておくことも重要である。発見的方法が単純なほど計算コストは低くなり、パフォーマンスも低くなる。
【００７７】
使用される発見的方法（単数または複数）が、次数dの出力ノードが生成できることを示す場合、再エンコード・モジュールRMは、少なくとも一つの部分デコードされたノードを組み合わせてこの次数dをもつ生成された出力ノードを生成することによって、第一の方法ステップを完了する。そうでない場合には、再エンコード・モジュールRMは、次の次数提案を試し、満足させることのできる次数提案がみつかるまで続けられる。そのような次数提案がみつかるという状況は起こる。というのも、少なくとも、以前に受領されたノードの一つをコピーすることは可能だからである。よって、生成されるシンボルの最高の不足（deficit）をもつ次数をもつエンコードされたシンボルを生成しようとすることが有益である。
【００７８】
次数dのノードを生成するために、再エンコード・モジュールRMは次のように進行する。
【００７９】
再エンコード・モジュールRMは、次数dの部分デコードされた諸ノードから出発し、次数dのノードをもつまで部分デコードされたノードを追加していく。部分デコードされたノードを追加するたびに、以前の値に追加される部分デコードされたノードの値をXORしたものに等しい新しい結果的な値が得られる。次いで、再エンコード・モジュールRMは、追加される部分デコードされたノードに寄与する入力ノード（単数または複数）を、結果として得られるノードに寄与するノードのリストに加える。
【００８０】
このノード生成の間、再エンコード・モジュールRMは次数dの諸ノードで出発し、1に至るまで減少していく次数のノードをもって続く。実際、ちょうど期待される次数dにうまく到達するためには、生成されるノードを完成させるために、最初に最も大きな諸シンボルを使い、その後小さな諸シンボルを使うことが好ましい。よって、生成中のノードの次数を下げる組み合わせは決して許容しない。さらに、部分デコードされたノードを加えようとするのは、その次数が期待される次数dと生成中のノードの現在の次数との間の差以下である場合のみであることが好ましい。生成中のノードが期待される次数dをもつようになったらすぐ、再エンコード・モジュールRMは第一の方法ステップを停止する。
【００８１】
上記のノード生成は、次のようなルーチンによって行うことができる。そこで、Lは第一の方法ステップの第一の部分において決定された期待される次数、Gは部分生成されたノードである：
L＝第一の方法ステップの第一の部分の結果
G＝φ
For  k＝d  to  1
While  次数kの何らかのノードNが試されていない
and  k≦L−degreeOf(G)〔Gの次数〕  do
N＝次数Lのランダムなノードを選ぶ
If  degreeOf(G＋N)＞degreeOf(G)  then
G＝G＋N  （それらの値をXORし、入力ノードどうしを加え、二回存在する入力ノードは除去する）
EndIf
EndWhile
EndFor
Return  G。
【００８２】
留意すべき重要なことは、再エンコード・モジュールRMが起こりうる衝突発生を考慮する発見的方法を使うときは、生成中のノードの次数が一時的に低下することを許容するということである。これは、上記のノード生成機構の制約条件の一つを緩和することに相当する。しかしながら、それでも、部分デコードされたノードを追加するのは、その次数が期待される次数と生成中のノードの現在の次数との間の差以下である場合であり続ける。ノード生成のこの変更は、次のようなルーチンによって行うことができる：
L＝第一のステップの第一の部分の結果
G＝φ
For  k＝d  to  1
While  次数kの何らかのノードnが試されていない
and  k≦L−degreeOf(G)〔Gの次数〕  do
N＝次数Lのランダムなノードを選ぶ
G＝G＋L  （それらの値をXORし、入力ノードどうしを加え、二回存在する入力ノードは除去する）
EndWhile
EndFor
Return  G。
【００８３】
上記のノード生成機構は、部分デコードされたノードを追加するのは、その次数が期待される次数と生成中のノードの現在の次数との間の差以下である場合のみであるという制約条件を緩和することによって向上させてもよい。この変形では、衝突は相変わらず考慮に入れられる。たとえば、次数LのノードNが生成中であるとき、再エンコード・モジュールRMが次数Dの生成されたノードに次数dの部分デコードされたノードを加えようとしうるのは、L−D≧d−2Econflicts(d,D)である場合にのみである。ノード生成のこの変形は、最後に記載された発見的方法が使われる場合に、より有用である。これは、次のようなルーチンによって行うことができる：
L＝第一のステップの第一の部分の結果
G＝φ
For  k＝d  to  1
While  次数kの何らかのノードnが試されていない
and  k−2Econflicts(k,degreeOf(G)−iadded)≦L−degreeOf(G)
and  degreeOf(G)＜L  do
N＝次数Lのランダムなノードを選ぶ
G＝G＋N  （それらの値をXORし、入力ノードどうしを加え、二回存在する入力ノードは除去する）
EndWhile
EndFor
Return  G。
【００８４】
低次数（1、2または3のような）のノードがたくさんある場合、可能な最高の次数のノードを加えることによって開始するのではなく、低次数ノードのみを使って高次数ノードを構築することに決めることも可能である。この目的のため、たとえば、上記最後のルーチン中で、1から1までの（次数1のノードのみを使うため）、あるいは2から1までの（次数1および2のノードのみを使うため）または3から1までの（次数1、2、3のノードのみを使うため）「Forループ」を使うことができる。
【００８５】
また、たとえば、追加される（added）べき次数1のノードを、この次数1のランダム・ノードを選ぶのではなく、そのスコア（すなわち、第二の選ばれた基準分布との差）に依存して選ぶことも可能である。これは、次数1のノードを、第二の選ばれた基準分布から推定できるそのスコアに依存してソートすることを要求するのみである。
【００８６】
生成された出力ノードを、第一の方法ステップを用いて生成し終わったのち、この生成された出力ノードは、第二の方法ステップによって洗練されることができる。
【００８７】
この第二の方法ステップは、タナー・グラフの入力ノードの現在の分布を、それがたとえば一様分布のような最適分布（または第二の選ばれた基準分布）に近く維持されることができるために、正規化する（normalizing）ことからなっていてもよい。
【００８８】
この目的のため、再エンコード・モジュールRMは、入力ノードの現在分布を第二の選ばれた基準分布と比較して、生成された諸出力ノードを生成するためにあまりに多く使われた、かつ、生成される出力ノードにリンクされる諸入力ノードに組み合わされるときにその生成される出力ノードの次数を不変のままにすることを許容する少なくとも一つの入力ノードを判別してもよい。
【００８９】
入力ノードの現在の分布は、再エンコード・モジュールRMによって、それが以前に生成し、たとえばメモリのような記憶手段中に記憶している諸出力ノードに関する情報から計算されることができる。
【００９０】
図４のグラフには、入力ノードの一様分布の例（水平線）および生成された諸入力ノードの次数の現在の（呈示されている）分布の例（黒）の両方が示されている。一様入力ノード分布は、どの入力ノードも同じ回数使われる分布である。
【００９１】
図４に示される例では、入力ノードAまたはFを再び送ることは避け、その代わりに入力ノードCまたはEを送ることを優先させるべきであることが観察できる。
【００９２】
再エンコード・モジュールRMが少なくとも一つのあまりに多く使われた入力ノードを判別したとき、生成される出力ノード中のこれらのあまりに多く使われた入力ノード（自らが判別した）のうち少なくとも一つを、あまりにまれに使われた入力ノードで置き換えてもよい。入力ノードの現在の分布を正規化するためである。
【００９３】
あまりに多く使われた入力ノードを有し、2に等しい選ばれた次数をもつ出力ノードを使うことは有利である。実際、LT符号シンボルでは（十分長い場合には）2に等しい次数をもつ（エンコードされた）出力ノードが50%を超えることが想起される。よって、
【数１６】
2010178332.tif 000018
なので、部分生成されたノード
【数１７】
2010178332.tif 000019
と次数2の出力ノード
【数１８】
2010178332.tif 000020
があるとすると、生成された出力ノード
【数１９】
2010178332.tif 000021
を生成することが可能である。（入力ノードａ（ここではあまりに多く使われたと考えられている）は除去されており、入力ノードｅ（ここではあまりにまれに使われたと考えられている）に置き換えられている。）
図５には、次数4の生成された出力ノードδ
【数２０】
2010178332.tif 000022
を、次数2の出力ノードγ
【数２１】
2010178332.tif 000023
を用いて洗練することを許容する方法サブステップの例が示されている。
【００９４】
【数２２】
2010178332.tif 000024
なので、洗練された生成された出力ノードβはいまだ次数4であるが、あまりに多く使われた入力ノードAはあまりにまれに使われた入力ノードEによって置き換えられている。
【００９５】
【数２３】
2010178332.tif 000025
生成された出力ノードの洗練に進むために、再エンコード・モジュールRMは次のように進行しうる。生成された出力ノードに含まれる各入力ノードNについて、この入力ノードNを含む次数2のすべての出力ノードを探す。次いで、これらの出力ノードのうちで、洗練されるべき生成された出力ノードのスコアを最もよく向上させることができるものを探しうる。その向上が正であれば、組み合わせ（XOR）を実行する。次いで、洗練されるべき生成された出力ノードに含まれる別の入力ノードNに進み、この過程を繰り返すことができる。衝突が起こる場合（すなわち、洗練されるべき生成された出力ノードの次数が減少されうる場合）、組み合わせ（XOR）は実行しない。
【００９６】
留意すべき重要なことは、上記の衝突の場合に組み合わせが行われることを単に禁止する代わりに、次数1の二つの入力ノードで、一緒になって次数2の衝突する出力ノードよりもよいスコアをもたらすものがみつかる限りにおいて、組み合わせが実行されることを許容することも可能であるということである。これは、さらなる多様性を導入し、次数1のノードを組み合わせにおいてより頻繁に使うことを許容する。
【００９７】
送信されるべき準備ができた（洗練された）生成された出力ノードを生成し終わったのち、再エンコード・モジュールRMは、記憶手段中に記憶している、生成された出力ノードの次数の現在の分布およびタナー・グラフの入力ノードの現在の分布を表す情報を更新しうる。後続の再エンコードにおいてそれらの更新された分布を使うためである。入力ノードの分布の更新は、生成された出力ノードに含められる各入力ノードについて、一つの生起を追加することによって行うことができる。
【００９８】
生成された出力ノードの現実の次数が望まれた次数と異なり、生成される出力ノードの次数が第二の方法ステップの間に低下することが許容される場合には、現実に生成される次数を節約する代わりに、生成したかった（生成することを期待した）次数（すなわち、第一の方法ステップの第一の部分の間に決定された次数）を節約することも可能である。この動作は、前記発見的方法が十分精密である場合には不要である。
【００９９】
ネットワーク再エンコード装置Dのタスクを簡単にするために、デコーダDCの古典的デコード・モジュールDDMを適応させることが有利である。より詳細には、デコード・モジュールDDMは、受信されたLT符号シンボルをデコードし終わったとき、そのタナー・グラフを更新する。このタナー・グラフは、それぞれの次数に依存して出力および入力ノードを検索するために、ネットワーク再エンコード装置Dによって使われる。よって、デコーダDCのデコード・モジュールDMは好ましくは、入力ノードおよび出力ノードをタナー・グラフ中のそれぞれの次数と対応して定義するデータを記憶するよう修正される。そうしたデータは、ネットワーク再エンコード装置Dによって容易にアクセスできるよう、たとえばインデックスの形で記憶されてもよい。よって、デコード・モジュールDMは、インデックスのテーブルを維持し、再エンコード・モジュールRMが特定の次数のノードをランダムに選ぶことを、また各次数のどのくらい多くのノードがデコーダDCのタナー・グラフ中に存在しているかを知ることを許容する。
【０１００】
本発明に基づく修正されたデコード・モジュールDDMは、少なくとも部分的にはソフトウェア・モジュールから構成されるのが好ましいが、電子回路（単数または複数）またはハードウェア・モジュールまたはハードウェア・モジュールとソフトウェア・モジュールの組み合わせ（この場合、ハードウェア・モジュールとソフトウェア・モジュールの間の連携動作を許容するソフトウェア・インターフェースをも有する）から構成されることもできる。ソフトウェア・モジュールのみから構成される場合には、デコーダDCのメモリに、あるいはたとえばCD-ROMのような通信装置CEiによって読まれることができる任意のコンピュータ・ソフトウェア製品中に格納されることができる。
【０１０１】
さらに、デコーダDCは、ノード冗長性を検出することができ、よってネットワーク再エンコード装置Dのタスクを単純化するためにさらに修正されてもよい。実際、本発明に基づくネットワーク再エンコード方法によってノード冗長性は増加させられる。該方法はLT符号シンボルのより多くの冗長なブロックを生成する傾向があり、それはデコードの複雑さ（計算上のまたスペース上の）を増し、ネットワーク再エンコード装置D（これはデコーダのデータを使う）のパフォーマンスを低下させる。
【０１０２】
よって、本発明は、デコーダDCに検出モジュールDTMを追加することを提案する。検出モジュールDTMは、デコードされるべき出力ノードがあるときに、それがデコード・モジュールDDMによって以前に受領されているかどうかを判別し、そうである場合には、それが以前にデコードされておりデコーダのタナー・グラフに再び挿入される必要がないことを信号伝達するメッセージを生成するよう構成される。
【０１０３】
留意すべき重要なことは、検出モジュールDTMは、出力ノードが受領されるときに（それが以前に受領されてデコードされたかどうかを判定するために）、あるいはデコード中に（たとえば出力ノード
【数２４】
2010178332.tif 000026
が部分デコードされて別の出力ノード
【数２５】
2010178332.tif 000027
を生成するときに）使用されることができるということである。この最後の場合、検出器モジュールDTMはyがすでに知られているか否かを検査することができる。
【０１０４】
たとえば、検出モジュールDTMは迅速に、受領された出力ノードについてのキーを計算して、二分探索木（たとえばRB木（「Red  Black  trees（赤黒木）」――自己均衡二分木の一種））またはハッシュ・テーブルのような高速な読み取りおよび挿入アクセスをもつ記憶されているデータ構造を検索してもよい。もう一つのキーがすでに挿入されていることを見出せれば、同じ出力ノードがすでに受領されており再びデコードされる必要がないと結論できる。よって、受領された出力ノードがデコーダDCのタナー・グラフ中に挿入されるのではなく単に破棄されるよう、メッセージを生成する。
【０１０５】
出力ノードの大半は低い次数（2または3に等しい）をもち、次数2の二つの出力ノードが同じである確率は次数4の二つの出力ノードが同じである確率よりずっと高いので、冗長性検出を次数1、2または3の出力ノードに制約することが可能である。この場合、検出モジュールDTMは次数1、2または3の任意の出力ノードxについてのキーh(x)をh(x)＝h(x′)⇔x＝x′となるよう計算するために意図されたハッシュ方法を実装してもよい。このハッシュ方法は次のようなものであってよい。
【０１０６】
まず、検出モジュールDTMは、あるエンコードされたシンボル（または出力ノード）を合成するもとの諸シンボルを昇順にソートしてもよい（たとえばそれらのシンボルの識別子を考慮することによって）。次いで、キーh(x)＝s1＋s2・(L＋1)＋s3・(L＋1)2を計算してもよい。ここで、
【数２６】
2010178332.tif 000028
であり、s1＝ia＋1、s3＝ib＋1、s2＝ic＋1であり、Lはシンボル（またはLT符号シンボル）長、ixはシンボル（または入力ノード）xを特定する0からL−1までの間の値を取る整数である。シンボルが次数2であれば、単にs3＝0と置き、シンボルが次数1であれば、単にs3＝0かつs2＝0と置く。
【０１０７】
このハッシュ方法はキーh(x)を計算するために若干の（定数）加算および乗算しか必要としない。さらに、この計算されたキーは多くの記憶スペースを要求することもない。その長さは3log2(L＋1)に等しいことを示すことができる。さらに、冗長性検出方法に伴うコストは低い（たとえば、長さL＝65536の出力符号について、64ビット比較を含むことになるが、これは汎用プロセッサによって一般に提供されている）。
【０１０８】
本発明に基づく検出モジュールDTMは、少なくとも部分的にはソフトウェア・モジュールから構成されるのが好ましいが、電子回路（単数または複数）またはハードウェア・モジュールまたはハードウェア・モジュールとソフトウェア・モジュールの組み合わせ（この場合、ハードウェア・モジュールとソフトウェア・モジュールの間の連携動作を許容するソフトウェア・インターフェースをも有する）から構成されることもできる。ソフトウェア・モジュールのみから構成される場合には、通信装置CEiの（たとえばデコーダDC内の）メモリに、あるいはたとえばCD-ROMのような通信装置CEiによって読まれることができる任意のコンピュータ・ソフトウェア製品中に格納されることができる。
【０１０９】
本発明はいくつかの利点を提供する。特に：
・複雑さが低いネットワーク符号を生成することを許容する。
・ガウスの消去法の代わりに信頼伝搬デコードを使いしたがってガロア体（GF(2k)）代数の使用を回避しうるため、ランダム線形ネットワーク符号（RLNC）よりも計算の面でより効率的なネットワーク符号を生成することを許容するので、幅広い範囲の用途において使用できる。
【０１１０】
本発明は、ネットワーク再エンコード方法、ネットワーク再エンコード装置およびデコーダの、上に単に例として記載された諸実施形態に限定されるものではなく、付属の請求項の範囲内であると当業者によって考えられうるあらゆる代替的な実施形態をも包含するものである。
【符号の説明】
【０１１１】
CEi  通信装置
ED  エンコーダ
DC  デコーダ
D  ネットワーク再エンコード装置
RM  再エンコード・モジュール
DDM  デコード・モジュール
DTM  検出モジュール
CN  通信ネットワーク
【図１】
2010178332.tif 000031
【図２】
2010178332.tif 000032
【図３】
2010178332.tif 000033
【図４】
2010178332.tif 000034
【図５】
2010178332.tif 000035
【外国語明細書】
2010178332000001.pdf