JP5027305B2 - 信頼できる通信を可能にするためのソース識別情報の生成および伝達 - Google Patents

Description

優先権
本出願は、２００７年９月１２日に出願された米国特許出願第６０／９７１，８８４号、および２００８年８月２９日に出願された米国特許出願第６１／０９３，２７７号の非仮出願の、米国特許法第１１９条（ｅ）項に基づく利益を主張する。これらの出願のすべては、すべての目的のために全文が参照により組み込まれる。

相互参照
以下の参考文献は、本明細書に含まれ、すべての目的のために参照により組み込まれる。

Lubyに発行された「Information Additive Code Generator and Decoder for Communication Systems」と題する米国特許第６，３０７，４８７号（以下「Luby I」）。

Lubyらの「File Download and Streaming System」と題する米国特許第７，４１８，６５１号（以下「Luby II」）。

Shokrollahiらに発行された「Multi Stage Code Generator and Decoder for Communication Systems」と題する米国特許第７，０６８，７２９号（以下「Shokrollahi I」）。

２００６年２月１６日に公開されたLubyらの「Method and Apparatus for Fast Encoding of Data Symbols According to Half-Weight Codes」と題する米国公開特許出願第２００６／００３６９３０号（以下「Luby III」）。

Shokrollahiらに発行された「Systems and Processes for Decoding Chain Reaction Codes Through Inactivation」と題する米国特許第６，８５６，２６３号（以下「Shokrollahi II」）。

２００７年１２月２７日に公開されたWatsonらの「Code Generator and Decoder for Communications Systems Operating Using Hybrid Codes to Allow for Multiple Efficient Users of the Communications Systems」と題する米国公開特許出願第２００７／０３００１２７号（以下「Watson」）。

２００７年７月２４日にJens Rasmussenらに発行された「System and Method for Reliably Communicating the Content of a Live Data Stream」と題する米国特許第７，２４９，２９１号（以下「Rasmussen」）。

本発明は、通信システム中でデータを符号化および復号することに関し、より詳細には、通信における誤りおよびギャップをなくすようにデータを符号化および復号する通信システムに関する。

通信チャネルを介した送信側と受信者との間のファイルおよびストリームの送信は、多くの文献の主題であった。好ましくは、受信者は、ある程度の確度でチャネルを介して送信側によって送信されたデータの正確なコピーを受信することを望む。チャネルが、物理的に最も実現可能なシステムを特徴づける完全な忠実度を有していない場合、１つの懸念は、送信中に損失または破損したデータをどのように処理するかということである。受信者は、送信されたデータがいつ破損したかを常に認識することができるわけではないので、損失したデータ（消去）は、破損したデータ（誤り）よりも、しばしば処理しやすい。

消去および／または誤りを訂正するために多数の誤り訂正コードが開発されてきた。一般に、使用される特定のコードは、データが送信されているチャネルの不忠実度と、送信されているデータの性質とに関する何らかの情報に基づいて選択される。たとえば、チャネルが長い周期の不忠実度を有することが知られている場合、バースト誤りコードがその適用例に最も適しているだろう。ごく短い、まれにしか起こらない誤りが予想される場合、単純なパリティーコードが最良であろう。

信頼できるデータ配信を行うための一般的に使用される別の技法は、データ再送信の使用である。たとえば、よく知られているＴＣＰ／ＩＰプロトコルは、損失または消失したパケットのパケット再送信を使用して、データの信頼できる配信を保証する。別の例は、ＴＣＰ／ＩＰの上に構築され、ＴＣＰ／ＩＰプロトコルの信頼性を使用して、信頼できるデータ配信を行うＨＴＴＰプロトコルである。受信機において損失または消失したパケットに対処する方法として、ＲＴＰプロトコルなどの他のプロトコルを、再送信を使用するように拡張することも提案されてきた。

ストリーミングアプリケーションの改善のために提案されてきた別の技法は、１つのチャネル中でストリームの初期データを受信機に送信し、次いで、第２のチャネル中で主データストリームを受信機に送信することに移行することである。たとえば、Rasmussenでは、そのような方法を提案している。別の例として、受信機がビデオまたはマルチメディアストリームのプレイアウトを迅速に開始するのに十分なデータを有するように、初期データをユニキャスト接続を介して受信機に送信することができ、次いで、受信機は、ストリームのさらなるデータを受信するように、マルチキャスト接続に切り替わることができる。

本明細書で使用する「通信」は、ある位置から別の位置に送信されるデータ、または、ある時点で記憶され、別の時点で使用されるデータなど、空間および／または時間を介したデータ送信を指す。チャネルは、送信側と受信機とを分離するチャネルである。空間的なチャネルは、送信側と受信機との間のワイヤ、ネットワーク、ファイバ、ワイヤレス媒体などとすることができる。時間的なチャネルは、データストレージデバイスとすることができる。実現可能なチャネルでは、送信側によって送信または記憶されたデータが、受信者によって受信または読み取られたときと異なる可能性がゼロでないことがしばしばあり、それらの差異は、チャネル中にもたらされる誤りに起因するものであろう。

送信機および受信機が、通信に必要な計算能力および電力のすべてを有しているとき、データ送信は簡単であり、送信機と受信機との間のチャネルは、比較的誤りのない通信を可能にするのに十分信頼できる。チャネルが劣悪な環境にあるとき、データ送信はより困難になるか、あるいは送信機および／または受信機が能力を制限される。いくつかの適用例では、連続的な誤りのない通信が、長い時間期間にわたって必要とされる。たとえば、デジタルテレビジョンシステムでは、送信が一度に何時間もの間、誤りなく受信されることが期待される。これらの場合、データ送信の問題は、比較的低いレベルの誤りの状態においてさえ困難である。

データ通信が困難である別のシナリオは、単一の送信が、大幅に異なるデータ損失状態を経験することがある複数の受信機に向けられている場合である。さらに、１つの所与の受信機が経験する状態は、大幅に異なるか、または時間がたつにつれて比較的一定になることがある。

データ損失（誤りおよび／または消去）の処理に対する１つの解決策は、受信機が送信消去および誤りを訂正することができるように送信機においてデータを符号化する、前方誤り訂正（ＦＥＣ）技法の使用である。実行可能な場合、受信機から送信機への逆方向チャネルは、受信機がこれらの誤りに関する情報を送信機に中継できるようにし、次いで、送信機は、それに応じてその送信プロセスを調整することができる。しかしながら、逆方向チャネルは、利用可能または実行可能でないか、あるいは限られた容量でしか利用可能でないことがある。たとえば、送信機が多数の受信機に送信している場合、送信機は、すべての受信機からの逆方向チャネルを維持することが不可能であろう。別の例では、通信チャネルはストレージ媒体とすることができる。

たとえば、データは年代順に送信されることがあり、因果律は、誤りが起こる前に誤りを修正することができる逆方向チャネルを妨げる。したがって、しばしば逆方向チャネルなしに、または限られた容量の逆方向チャネルで通信プロトコルを設計する必要があり、したがって、送信機は、それらのチャネル状態の事前知識なしに、大幅に異なるチャネル状態を処理しなければならない。一例は、逆方向通信が行われないか、あるいは行われるとしても、ごく限られているかまたは費用のかかる、ブロードキャストまたはマルチキャストチャネルがある。そのような状況が関係する別の例は、ＦＥＣを使用してデータを符号化して記憶し、次いでその後の時点で、場合によってはＦＥＣ復号を使用して、データを回復する、ストレージ適用例である。

別の解決策は、受信機がどのパケットが受信されないかを理解し、次いでそれらの消失したパケットを再送信するように要求を送信側に送信することに基づく再送信に基づく。消失したパケットの識別情報は、しばしば、パケット内で搬送されるシーケンス番号に基づく。そのようなプロトコルの例には、ＴＣＰ／ＩＰ、ＮＯＲＭ、再送信を用いたＲＴＰなどがある。

別の解決策は、ＦＥＣと再送信との組合せに基づく。この場合、ＦＥＣは事前に送信され、次いで、たとえば、受信機は、ＦＥＣ復号器によって回復できるものよりも多くを損失した場合のみ、元のソースパケットを回復するのに十分なパケットをＦＥＣ復号器に与えるために、パケットの再送信、または追加のＦＥＣパケットの送信を要求する。別の例として、ＦＥＣが最初に送信されず、消失したパケットがある場合のみ、受信機は、元のソースパケットを回復するために使用できるＦＥＣパケットとすることができる、追加のパケットを要求することになる。たとえば、これは、マルチキャストを介して元のソースストリームを送信する場合に注目すべき解決策になり、その場合、要求されたパケットはまた、同じストリームまたは異なるマルチキャストストリームのいずれかで送信される。たとえば、受信機によって損失するパケットの数が異なることがあり、その場合、要求されたパケットを送信している送信側は、たとえば、すべての受信機によって要求されたＦＥＣパケットの最大数を送信し、それにより、すべての受信機は、それらの個々のパケット損失パターンとは無関係に元のソースを回復できるようになる。

パケットを損失する可能性があるチャネルを介したデータトランスポートに使用されるパケットプロトコルの場合、パケットネットワークを介して送信すべきデータのファイル、ストリーム、または他のブロックを（すべて等しいサイズであるか、あるいはブロックサイズまたは他のファクタに応じてサイズが異なる）ソースシンボルに分割する。ＦＥＣコードを使用してソースシンボルから符号化シンボルを生成し、符号化シンボルをパケット中に配置し、送信する。シンボルが実際にビットストリームに分解されるか否かにかかわらず、シンボルの「サイズ」をビットで測定することができ、シンボルが２^Ｍ個のシンボルのアルファベットから選択されたとき、シンボルはＭビットのサイズを有する。そのようなパケットベースの通信システムでは、パケット指向消去ＦＥＣコーディング方式が好適であろう。

ファイル送信は、ネットワークを介して送信されたデータの消去および／または他の破損にもかかわらず、意図された受信者が元のファイルの正確なコピーを回復できる場合、信頼できると呼ばれる。ストリーム送信は、ネットワーク内の消去および／または破損にもかかわらず、意図された受信者がストリームの各部分の正確なコピーを適時に回復できる場合、信頼できると呼ばれる。ファイル送信とストリーム送信の両方は、むしろ、ファイルまたはストリームのいくつかの部分が回復可能でないか、または、ストリーミングの場合、ストリームのいくつかの部分が回復可能であるが、適時には回復可能でないという意味で、いくぶん信頼できるが、完全に信頼できるというわけではない。いくつかの制約条件に応じてできるだけ高い信頼性を提供することは、しばしば目的であり、制約の例としては、ストリーミング適用例のための適時の配信、または解決策が動作すると予想されるネットワーク状態のタイプがある。

パケット損失は、散発的な輻輳によりルータ中のバッファ機構がその容量に達し、着信パケットを削除してしまうために、しばしば発生する。パケット損失の他の原因には、弱い信号、断続的な信号、および雑音干渉があり、破損したパケットは廃棄される。トランスポート中の消去に対する保護は、多くの研究の主題であった。

単一の送信が２つ以上の受信機に向けられ、受信機によって経験する状態が大幅に異なるシステムでは、送信は、しばしば送信機と任意の受信機との間の状態のある組のために構成され、より悪い状態にある受信機は、送信を確実に受信することができない。

そのようなシナリオにおいて損失したパケットの優れた回復を行う消去コードが知られている。たとえば、リードソロモンコードがよく知られており、この目的に適合できる。しかしながら、リードソロモンコードの知られている欠点は、それらの計算の複雑さが比較的大きいことである。ＬＴ（商標）連鎖反応コードおよびＲａｐｔｏｒ（商標）マルチステージ連鎖反応（「ＭＳＣＲ」）コードを含む、連鎖反応コードは、損失したパケットの優れた回復を行い、異なるチャネル状態に大いに適合可能である。たとえば、連鎖反応コードの態様が記載されているLuby I、およびマルチステージ連鎖反応コードの態様が記載されているShokrollahi Iを参照されたい。本明細書では、「連鎖反応コード」という用語は、別段に規定がない限り、連鎖反応コードまたはマルチステージ連鎖反応コードを含むものと理解されたい。

再送信プロトコルも、損失したパケットを回復する良い方法であることが知られている。ＴＣＰ／ＩＰ、ＮＯＲＭ、ＵＤＰおよびＲＴＰベースの再送信プロトコルはすべて、そのような再送信プロトコルの例である。加えて、消去コードプロトコルと再送信プロトコルとの組合せを使用することは、損失したパケットを回復するのに極めて有用である。再送信プロトコルは、受信機が、受信機に送信されるべき特定のパケットまたはパケットの数を要求し、送信側が、それに応答して、特定のパケットまたはパケットの数を、その受信機に、または受信機のグループに送信することができるプロトコルを含む。

いくつかの通信システムは、同じストリーム中の他のソースパケットに対するソースパケットの位置またはシーケンスを識別するのに使用可能な情報を含む、ＲＴＰなど、トランスポートプロトコルを使用する。各パケットのシーケンス情報を提供することによって、受信機は、ネットワーク順序からはずれて受信されたパケットを検出し、訂正することができる。受信機はまた、パケットが損失したときを検出することができ、ＤＶＢ−ＩＰＩの技法（たとえば、Watson中の記述を参照されたい）など、アプリケーション層ＦＥＣ技法と組み合わせると、受信機は、損失したパケットを回復し、ネットワーク信頼性の欠陥を効果的にマスキングすることができる。ＤＶＢの詳細については、ＤＶＢ−ＩＰＩ規格の参考文献「DVB BlueBook A086r4 (03/07)/ETSI Technical Specification 102 034 v1.3.1」から知られている。また、ＤＶＢ−ＩＰＩ規格は、URL:http://www.dvb.org/technology/standards/a086r4.dTS102034.V1.3.1.pdfで入手可能である。

多くの展開された通信システムは、いかなる形式のタイミングまたはシーケンス情報をも含まないトランスポートレベルプロトコルを使用する。たとえば、ＩＰＴＶネットワークでは、「ローＵＤＰ」を介してＭＰＥＧ２トランスポートストリームパケットを配信することが慣例である。受信機にとって利用可能な唯一のシーケンス情報は、アクセスが難しいか、または信頼できず、概してトランスポートレベルで利用可能でないオーディオおよびビデオエレメンタリストリーム中に埋め込まれる。したがって、受信機が、パケットがネットワーク順序からはずれて受信されたときを認識できるようにするか、または消失したパケットを識別できるようにするローＵＤＰストリームを用いた、トランスポートレベルにおける固有の機構がない。アプリケーション層ＦＥＣ（「ＡＬ−ＦＥＣ」）など、よく知られている機構を使用して、損失したパケットを効率的に回復することができるが、ソースストリームパケット上にトランスポートレベルシーケンス情報がないので、そのような回復技法の直接の適用範囲が限定される。これらの同じ問題は、再送信解決策、および再送信とＡＬ−ＦＥＣ解決策との組合せに当てはまる。したがって、これは、いくつかの既存の手法の一般的な問題である。

いくつかの通信システムの別の問題は、部分同士が相互に関係することである。場合によっては、展開後に通信システムの信頼性を高めることが必要であるか、または望ましいことがある。しかしながら、ネットワーク信頼性の改善が必要であるが、ネットワーク中のすべての受信デバイスを一度に交換またはアップグレードすることは、一般に実行可能でないか、またはまったく実行可能でない。たとえば、ネットワーク信頼性の劣化、トラフィック負荷の増大、ネットワークの拡大および／または変更などにより、実際のネットワークパケット損失が最初の予定よりも大きくなること、またはサービス品質要件は、競合するサービスに合うように増加する必要があることが判明するであろうが、通信システムのすべてのノードに新しい受信機を一度に用意すること、または新しい受信機を徐々に分配し、新しい受信機が到着するまで、いくつかの受信局を使用不能にしておくことは、実際的でないであろう。

レガシーデバイスが、アップグレードされた受信機または新しい受信機によって使用される、ＡＬ−ＦＥＣまたは再送信、あるいはＡＬ−ＦＥＣと再送信との組合せなどのプロトコル拡張の影響を受けないように、同じトランスポートレベルプロトコルを使用してソースパケットを配信し続けることが必要である。さらに、レガシーデバイスに配信されるソースパケットがバースト損失を受けやすくならないように、同じソースパケットタイミング分配またはパケット間タイミングを維持することが必要である。いくつかの通信システムでは、リペアパケットを関連するソースパケットの直後に配信できるようにするために、ソースブロック内のソースパケットをより小さいパケット間ギャップで送信することがあるが、そのような技法は、バースト損失へのソースストリームの露出を増加させるので、レガシーデバイスのトランスポート有効性を劣化させることになる。

可能な最良のサービスを最小のコストで配信するために、通信システムは、競合するリソース制約を同時に均衡させなければならない。ネットワーク帯域幅は重要なリソース制約である。送信デバイスおよび受信デバイスは、信頼できるサービスをサポートする際にネットワーク帯域幅を効率的に使用できるようにする必要がある。受信デバイス上の利用可能なＣＰＵ処理は一般に厳しい制限であり、いかなるトランスポート信頼性拡張方法も、適当な量の計算労力しか必要としてはならないことを意味する。加えて、特にストリーミングメディアの場合、エンドユーザがシステム応答性の低減を知覚しないように、信頼できるトランスポート方法に関連する増分待ち時間を制限することもしばしば必要である。

本発明の一実施形態による、ソースストリームから、ソース識別データまたは情報と呼ばれる、ソース識別情報またはデータを生成する方法について説明する。本方法は、元のソースストリームに対して動作し、他のソースパケットに対するソースパケットの位置を識別するため、および損失または破損したソースパケットを識別するために受信デバイスによって使用される比較的コンパクトなソース識別情報またはデータを生成することができる。ソース識別情報またはデータの生成方法により、ソースパケット識別情報をコンパクトに表現することができるようになり、それにより、比較的少ない量のネットワーク帯域幅を使用してソースパケットのブロックのソース識別情報を配信することが可能になる。ソース識別情報を導出する計算負荷は小さい。

損失または破損したソースパケットの回復を可能にするために、ソース識別データを前方誤り訂正（「ＦＥＣ」）技法と組み合わせることができる。損失または破損したソースパケットの回復を可能にするために、ソース識別データを、再送信技法、およびＦＥＣ技法と再送信技法との組合せと組み合わせることもできる。ソース識別データはまた、いくつかの送信されたパケットが損失し、破損し、または再順序付けされたときでも、ソースパケットのシーケンスがどの順序で送信側から受信機に送信されるかをその受信機において識別する技法とともに使用できる。

本発明の別の実施形態では、ソースパケットの識別情報または相対位置を受信デバイスにおいて判断することができ、拡張によって、受信したソースパケットの不在を導出することができるように、ソース識別データの信頼できる配信を可能にする方法および装置が提供されるであろう。ソース識別の信頼できる配信を行うために、ソース識別を搬送するパケットを、バースト損失または周期的な損失パターンへの露出を最小限に抑える方法で送信することができる。ソース識別データがソースパケットの内容から導出されるので、２つ以上のソースパケットが同じソース識別データを共有することができ、これらの方法の変形形態は、受信機においてそのようなソース識別の衝突に対して保護することができる。

本発明の別の実施形態によれば、通信チャネルを介してデータを送信する方法であって、元の変更されていないソースストリームを送信するステップと、元の変更されていないソースストリーム中の損失または破損したパケットを効率的に回復するために使用できる追加のストリームとして、ＦＥＣリペアデータおよびソース識別データを送信するステップとを備える方法が提供される。

本発明の別の実施形態によれば、通信チャネルを介してデータを送信する方法であって、元の変更されていないソースストリームを送信するステップと、どのデータが受信データから消失または破損したかを識別し、再送信を要求するために使用できる追加のストリームとして、ソース識別データを送信するステップとを備える方法が提供される。本実施形態のさらなる拡張では、ソース識別情報を使用して、再送信されたデータをも識別する。本実施形態のさらなる拡張では、ソース識別情報を使用して、順序からはずれたデータ受信を識別し、再順序付けする。さらなる拡張では、ソース識別情報を使用して、ＦＥＣを用いて元の変更されていないソースストリーム中の損失または破損したデータを回復するとともに、どのデータが元のソースストリームから消失または破損したかを識別し、消失または破損したデータの再送信、または変更されていないソースストリーム中のデータを回復するために使用できる追加のリペアデータの送信を要求する。本実施形態のさらなる拡張では、元の変更されていないソースストリームとともに第１のリペアストリームを送信する。本実施形態のさらなる拡張では、再送信の要求に応答して第２のリペアストリームを送信する。本実施形態のさらなる拡張では、様々なストリームの１つまたは複数をキャッシュする。

本発明の別の実施形態によれば、ソース識別情報は、データの変更されていないソースストリーム内のどのデータブロックにソースパケットが関連付けられているのかを識別する。この場合、変更されていない各ソースパケットの一意の識別子を生成することができない、すなわち、ソース識別情報は、ソースパケットが関連付けられているデータブロックを識別するために使用できるが、ブロック内のソースパケットを互いと区別することができない。

本発明の別の実施形態によれば、通信チャネルを介して送信されるデータを受信する方法であって、（１）非ＦＥＣ対応受信機の場合、または、０個以上のＦＥＣ対応受信機の場合、元の変更されていないソースストリームを受信するステップと、（２）１つまたは複数のＦＥＣ対応受信機の場合、元の変更されていないソースストリーム、およびＦＥＣリペアデータとソース識別データとの追加のストリームの一部または全部を受信し、元のソースストリームから損失したパケットを効率的に回復するためにこれを使用するステップとを備える方法が提供される。

本発明の別の実施形態によれば、通信チャネルを介して送信されるデータを受信する方法であって、（１）非再送信対応受信機の場合、または、０個以上の再送信対応受信機の場合、元の変更されていないソースストリームを受信するステップと、（２）１つまたは複数の再送信対応受信機の場合、元の変更されていないソースストリーム、および再送信リペアデータとソース識別データとの追加のストリームの一部または全部を受信し、元のソースストリームから損失したパケットを効率的に回復するためにこれを使用するステップとを備える方法が提供される。

本発明の別の実施形態によれば、通信チャネルを介して送信されるデータを受信する方法であって、（１）非ＦＥＣおよび非再送信対応受信機の場合、または、０個以上のＦＥＣおよび再送信対応受信機の場合、元の変更されていないソースストリームを受信するステップと、（２）１つまたは複数のＦＥＣおよび再送信対応受信機の場合、元の変更されていないソースストリーム、ならびにＦＥＣおよび再送信リペアデータの追加のストリームの一部または全部、ならびにソース識別データを受信し、元のソースストリームから損失したパケットを効率的に回復するためにこれを使用するステップと、を備える方法が提供される。

本発明の別の実施形態によれば、通信チャネルを介して送信されるデータを受信する方法であって、（１）ＦＥＣ対応または再送信対応受信機の場合、受信されている特定のストリームが、関連する利用可能なＦＥＣリペアデータまたは再送信データを有するかどうかを判断するステップと、（２）ＦＥＣリペアデータまたは再送信データが利用可能な場合、必要に応じてＦＥＣおよび再送信リペアデータの追加のストリームの一部または全部、ならびにソース識別データを受信し、元のソースストリームから損失したパケットを効率的に回復するためにこれを使用するステップと、を備える方法が提供される。

本発明の別の実施形態によれば、通信チャネルを介してデータを送信する方法であって、元の変更されていないソースストリームを送信するステップと、元の変更されていないソースストリーム中の損失したパケットを効率的に回復するために使用できる関係するデータの追加のストリームを送信するステップとを備える方法が提供される。

本開示を検討すれば当業者には明らかであるように、本明細書で説明する方法は上記の多くの変形形態に当然拡張でき、ＦＥＣリペアデータの複数の層を送信すること、ソースストリームを１つのＩＰアドレスに、および追加のストリームを他のＩＰアドレスに送信すること、再送信データを受信機に個々に送信すること、同じ再送信データをブロードキャストまたはマルチキャストを介して複数の受信機に送信すること、ＦＥＣリペアデータと再送信データとの組合せを受信機に送信すること、ＦＥＣリペアデータを受信機の１つのセットに送信し、再送信を受信機の第２のセットに送信すること、同じＩＰアドレスであるが、パケット内で異なるポート番号を使用することによって区別されるＩＰアドレスにすべてのストリームを送信すること、ストリームのいくつかを受信機のいくつかの部分にのみ送信し、他の受信機に送信しないことなどを含む。

本明細書の残りの部分を参照すれば、本明細書で開示する実施形態の性質および利点をより良く理解することができる。

ＦＥＣリペア技法とともに使用する本明細書に記載のソース識別技法の１つまたは複数を生成し、使用することができる通信システムのブロック図。 レガシーセットトップボックスとＦＥＣ対応セットトップボックスの両方をサポートする通信システムのブロック図。 リペアが特定のストリームに利用可能か否かを判断するＦＥＣ対応受信機の状態図。 可能なＦＥＣ対応受信機の流れ図。 １つのソース識別データ方法の例を示す流れ図。 １つのソース識別データ方法の例を示すブロック図。 いくつかのソース識別データの構成の例を示すブロック図。 受信機がソース識別データを使用して、変更されていない受信したソースパケットの識別情報を計算する方法を示す流れ図。 いくつかのソース識別データの構成の例を示すブロック図。 ソース識別データの構成のいくつかのさらなる詳細の例を示すブロック図。 可能なソース識別データフォーマットの例を示すブロック図。 ソース識別データの構成中で隣接するソースブロックとのソースブロック境界および重複の例を示すブロック図。 別の可能なソース識別データフォーマットの例を示すブロック図。 ２つの同じパケットが同じ値にハッシュしている例を示すブロック図。 同じパケットを処理することができるシーケンスと位置との対応を示すブロック図。 同じでないパケットが同じ値にハッシュする例を示すブロック図。 ソース識別データをＦＥＣ保護する方法を示すブロック図。 変更されていないソースパケットからＦＥＣリペアシンボルを生成する方法を示すブロック図。 ＦＥＣリペアデータとソース識別データの両方を備えるパケットの可能なフォーマットを示すブロック図。 パケットで搬送されるソース識別データからのソース識別情報の可能な部分再構成を示すブロック図。 受信機がソース識別情報を使用して、受信したソースデータを処理する方法の例を示す流れ図。 ２つのソースブロックにわたる受信機における受信タイムアウト中の損失したパケットを示すブロック図。 ソースブロック中で早期に発生する受信機における受信タイムアウト中の損失したパケットを示すブロック図。 受信機における受信中のソースブロック内の遅延パケットを示すブロック図。 受信機における受信中のソースブロック間の遅延パケットを示すブロック図。 拡張ブロックを越える受信機における受信中の遅延パケットを示すブロック図。 図２３Ａおよび図２３Ｂの例とともに拡張ブロック内の受信機における重複パケット受信を示すブロック図。 図２３Ａおよび図２３Ｂの例とともに拡張ブロック内の受信機における重複パケット受信を示すブロック図。 拡張ブロックを越えた受信機における重複パケット受信を示すブロック図。 ＦＥＣリペアデータおよびソース識別データを用いたストリームの保護のいくつかの例示的な結果を示す表。 ＦＥＣリペアデータおよびソース識別データおよび再送信リペアデータを用いてストリームを保護する例を示すブロック図。

本明細書の残りの部分および添付の図面を参照すれば、本明細書で開示する本発明の性質および利点をさらに理解することができる。

本明細書で説明する様々な機能ブロックはハードウェアおよび／またはソフトウェアの組合せによって実装でき、特定の実装形態では、ブロックの一部の機能の一部または全部を組み合わせることができることを理解されたい。同様に、本明細書で説明する様々な方法はハードウェアおよび／またはソフトウェアの組合せによって実装できることも理解されたい。したがって、「次いでステップＸを実行する」のように記述される場合がある計算ステップを実施する場合、そのような記述は、典型的には通信プロセスの一部として、人間または手動による相互作用を伴わずに、それらのステップを実施する電子ハードウェアおよび／またはソフトウェアなどを含むことを理解されたい。

本明細書で説明するいくつかの実施形態では、符号化されるデータは「ソースブロック」にセグメント化され、各ブロックは、「ソースパケット」として知られるいくつかのデータのパケットを備え、ブロック中のソースパケットの数は、場合によってはブロック間で異なる。ソースブロックごとに、いくつかの「ＦＥＣリペア」パケットが符号器によって生成され、その数は、同じく場合によってはブロック間で異なる。「ソースパケット」および「ＦＥＣリペア」、（または「リペア」）パケットは、ソースパケットと、ソースパケットの数と同数またはそれ以上のリペアパケットとの組合せを受信する受信機が、すべてのソースパケットを回復する０ではないある確率を有するという特徴を有する。

ソース識別データのタイプおよび使用法
本明細書のいくつかの実施形態では、ソース識別データは、他のソースシンボルに対する（以下より一般的にソースデータ単位と呼ぶ、パケットまたは他の搬送単位で送信できる）ソースシンボルの位置、ならびに損失したソースシンボルの位置を受信デバイスにおいて識別することができるデータを指すことがある。本明細書で使用するソースシンボルマップまたはソースシステムマップ（いずれも「ＳＳＭ」と呼ぶことがある）は、ソース識別データまたは情報の一形式である。本開示では、ソースシンボルマップおよびソースシステムマップはソース識別データと互換的に使用される。本明細書のいくつかの実施形態では、ソース識別データは、受信パケットと損失したパケットの両方の位置を備える、他のパケットに対するパケットのストリーム中の送信パケットの位置を受信デバイスにおいて識別することができるデータを指すことがある。本明細書のいくつかの実施形態では、ソース識別データは、受信機から再送信を要求されたパケットまたはシンボルまたは他のデータ単位を識別するために送信側で使用されるデータを指すことがある。ソース識別データは、ソースおよびリペアのシンボルまたはパケットの組合せから損失したシンボルまたはパケットまたは他のデータ単位を回復するために受信機において使用できる。ソース識別データは、再送信を要求するために、どのシンボルまたはパケットまたは他のデータ単位が損失しているかを識別するために使用できる。ソース識別データはまた、他のパケットまたはシンボルに対する、パケットまたはシンボルの元の送信順序を受信機において判断するために使用できる。ソース識別データは、単一パーツとして考えるか、サブパーツに分割するか、またはストリームと考えることができるが、ソース識別データの単一パーツ、サブパーツ、またはストリームは、ソースデータ単位の全部または一部を識別するために使用でき、たとえば、ソース識別データの一部はソースブロック内のソースデータ単位を識別するために使用できる。当業者なら認識されるように、本明細書では列挙しないが、本明細書で開示する方法およびプロセスを使用して容易に推測できる、ソース識別データの多くの他の可能な使用法がある。ソース識別データの可能な様々なタイプおよび使用法は以下を含むが、これらに限定されない。

（１）知られているソースデータ単位の識別ラベルを判断する方法−ソース識別データから知られている各ソースデータ単位の短い識別ラベルを判断する能力。１つの例示的な使用法は、受信機が、受信したソースデータ単位のラベルを送信側に送信して、それにより受信されなかったラベルに関連するソースデータ単位を送信側から受信機に送信できるようにすることである。この方法の変形態では、可能なソースデータ単位、たとえば、特定のソースブロックに属するソースデータ単位、または指定の時間期間内に送信されたソースデータ単位の制限されたセットの識別データを判断することができる。

（２）すべてのソースデータ単位の識別データを判断する方法−ソース識別データから、ソースデータ単位が知られているか知られていないかにかかわらずすべてのソースデータ単位の短い識別ラベルを判断する能力。１つの例示的な使用法は、受信機が、消失したソースデータ単位のラベルを送信側に送信して、それにより受信したラベルに関連するソースデータ単位を送信側から受信機に送信できるようにすることである。この方法の変形態では、可能なソースデータ単位、たとえば、特定のソースブロックに属するソースデータ単位、または指定の時間期間内に送信されたソースデータ単位の制限されたセットの識別データを判断することができる。

（３）配置判断方法−ソースデータ単位のすべての順序付けに関して、知られているソースデータ単位と知られていないソースデータ単位の両方に対して各ソースデータ単位の位置を判断する能力であり、この順序付けは、ソース識別データによって判断されるが、データ単位の送信順序と異なっていても、あるいはストリームまたはファイル内のソースデータ単位の順序と異なっていてもよい。１つの例示的な使用法は、送信側および受信機がこの情報を使用して、ＦＥＣ符号化およびＦＥＣ復号のために、ソースブロック内のどこにソースデータ単位を配置すべきかを判断できるようにすることである。この方法の変形態では、可能なソースデータ単位、たとえば、特定のソースブロックに属するソースデータ単位、または指定の時間期間内に送信されたソースデータ単位の制限されたセットの位置を判断することができる。

（４）シーケンシング判断方法−ソースデータ単位のすべての（ファイル中のソースデータ単位の順序、またはオーディオビデオストリーム中のデータの順序などの）送信順序シーケンスまたは他のソース判断順序シーケンスに関して、知られているソースデータ単位と知られていないソースデータ単位の両方に対して各ソースデータ単位の位置をソース識別データから判断する能力。１つの例示的な使用法は、受信機がこの順序付けを使用して、データ単位をどんな順序でアプリケーションに送出すべきか、たとえば、データ単位をどんな順序でファイルに書き込むべきか、または媒体ストリームのデータ単位をどんな順序でメディアプレーヤに送信すべきかを判断できるようにすることである。この方法の変形態では、可能なソースデータ単位、たとえば、特定のソースブロックに属するソースデータ単位、または指定の時間期間内に送信されたソースデータ単位の制限されたセットの位置を判断することができる。

配置判断方法をＦＥＣ方法とともに使用するとき、ソースブロック内でのソースシンボルの順序付けは、配置判断方法からの位置に従うことができ、この場合、ソース識別方法は、ＦＥＣ符号化および復号の方法の動作の仕方と相互作用する。一方、シーケンシング判断方法をＦＥＣ方法とともに使用するとき、ソースブロック内でのソースシンボルの順序付けはシーケンシングに従うことができ、シーケンシングは一般にシーケンシング判断方法によって規定されないので、この場合、ソース識別方法は、ＦＥＣ符号化および復号の方法の動作の仕方とはほとんど無関係とすることができる。場合によっては、配置判断方法とシーケンシング判断方法との組合せであるソース識別方法を使用することができ、たとえば、何らかの最初のソース識別データが存在することができ、この最初のソース識別データを使用してソースブロック内のソースシンボルの位置を判断し、次いでＦＥＣ復号を実施して位置に従ってソースシンボルを回復し、その場合、そのソースブロックの一部である何らかの追加のソース識別データが存在することができ、この追加のソース識別データを使用して、回復されたソースシンボルのシーケンシングを判断して、アプリケーションに送出する。

配置判断方法を再送信方法とともに使用するとき、受信機によって再送信を要求されたソースパケットをそれらの位置によって識別することができ、たとえば、受信機は、送信側に再送信を要求されたソースパケットの位置を送信することができる。これらの場合、シーケンシング順序は位置順序と異なってよいので、送信側は、シーケンス順序に従って再送信パケットを送信し、受信機は、損失していないソースパケットの受信の元の順序と再送信されたソースパケットの受信の順序とに基づいてシーケンシングを判断することができる。シーケンシング判断方法を再送信方法とともに使用するとき、受信機によって再送信を要求されたソースパケットをそれらのシーケンシングによって識別することができ、たとえば、受信機は、送信側に再送信を要求されたソースパケットのシーケンス番号を送信することができる。場合によっては、配置判断方法とシーケンシング判断方法との組合せであるソース識別方法を使用することができ、たとえば、何らかの最初のソース識別データが存在することができ、この最初のソース識別データを使用して、ソースパケットの元の送信中に送信されたソースブロック内の位置を判断し、その場合、再送信中に送信された何らかの追加のソース識別データが存在することができ、この追加のソース識別データを使用して、そのソースパケットのシーケンシングを判断して、アプリケーションに送出する（たとえば、再送信されたソースパケットのシーケンス番号）。

当業者なら認識されるように、上記には多くの変形態が存在する。たとえば、ソース識別方法をＦＥＣ方法と再送信方法との組合せとともに使用することができ、その場合、再送信の要求は、特定のソースパケットに対して、特定のリペアパケットに対して、または特定のリペアパケットに対してではなくリペアパケットの指定された数に対してのものとすることができる。

ソース識別方法をＦＥＣ方法とともに使用する例
図１は、ＦＥＣリペア方法とともに使用する本明細書に記載のソース識別技法を生成し、使用することができる通信システムのブロック図である。

通信システム１００では、入力ストリームまたはファイル１１０がソース識別情報生成器１２０に供給される。ソース識別情報生成器１２０は、パケットまたはシンボルのストリーム内でのソースパケットまたはシンボルの相対位置に関する情報を含むソース識別データを生成する。すべてのソースシンボルまたはパケットは、一般に通信システム１００を使用することによって決定される同じサイズを有することができ、あるいはシンボルサイズまたはパケットサイズは、使用ごとに異なるまたはストリーム内で異なることができる。ソース識別データの生成はソースシンボルサイズまたはパケットサイズとは無関係とすることができる。

入力ストリームまたはファイル１１０はＦＥＣ符号器１３０に供給できる。いくつかの実施形態では、ＦＥＣ符号器１３０はシステマティックＦＥＣ符号化を実施し、このシステマティックＦＥＣ符号化は、入力ソースシンボルおよびそれらの位置の１つまたは複数に基づいてＦＥＣリペアシンボルを生成し、多くの場合、送信のためにこれらのＦＥＣリペアシンボルをリペアパケット中に配置する。

通信チャネルを介した送信のために使用される入力ストリームまたはファイル１１０から構築されたソースパケットが存在することができ、これらのソースパケットの構築はソースシンボルサイズとは無関係とすることができることに注目すべきである。ソースパケットとソースシンボルとの間に１対１の写像があっても、なくてもよい。ソースパケットは可変長であっても、なくてもよい。

入力ストリームまたはファイル１１０からのソースパケット、ソース識別情報生成器１２０からのソース識別データ、およびＦＥＣ符号器１３０からのＦＥＣリペアシンボルは、送信モジュール１４０に供給される。送信モジュール１４０は、ソース識別データおよびＦＥＣリペアシンボルをパケットでチャネル１４５に送信することができ、これらのソース識別データおよびＦＥＣリペアシンボルは、このプロセス中にパケット中で組み合わせても、組み合わせなくてもよい。これらのパケットはソースパケットとともにチャネル１４５を介して送信される。

チャネル１４５は消去チャネルであってよいが、それは通信システム１００が適切に動作するための要件ではない。一般に、元のソースパケットは、他のパケットから論理的に別個のデータストリームとして送信される。論理的に別個のデータストリームの例には、異なるマルチキャストグループによって送信されるストリーム、または異なるポートに送信されるストリームがあるが、これらに限定されない。チャネル１４５に送信されたデータストリームは、受信モジュール１５０および１５５が受信することができる。受信モジュール１５０はＦＥＣ復号器と協働するものであるが、受信モジュール１５５は、ＦＥＣ復号を含まないことがあるレガシーデバイスである。通信システム１００は、レガシー受信モジュール１５５が、ソースパケットのみを受信するように、あるいはパケットの組合せを受信するがソースパケット以外のパケットをフィルタ処理するように設計できることに留意されたい。

レガシー受信モジュール１５５は、チャネル１４５からのソースパケットを認識し処理できるようにすることが可能である。リペアパケットまたはソース識別データが到着した場合、それらは論理的に別個のストリーム上にあることができ、レガシー受信モジュール１５５はそれらを無視する（黙って廃棄する）ことができる。受信ストリーム１８５はレガシー受信モジュール１５５から作り出される。

受信モジュール１５０は、ソースパケットからソース識別データ、リペアシンボルを論理的に区別することができる。ソースパケットおよびソース識別データは、ソース識別情報解釈器１６０に供給され、このソース識別情報解釈器１６０から、ソースパケットで搬送されたソースシンボルを識別するソースシンボルＩＤを識別することができる。受信したソースシンボル値とそれらの位置との間の関係を与えるソース識別データは、ＦＥＣ復号器１７０に送信される。

さらに、ＦＥＣ復号器１７０はまた、ＦＥＣリペアシンボルおよびソースパケットを入力として受け取り、その両方は受信モジュール１５０から供給される。ＦＥＣ復号器１７０は、もしあれば、消失したソースパケットを回復しようと試みる。受信したソースパケットは、必要ならばＦＥＣ復号器１７０から回復された消失したソースパケットと再統合されて、回復されたストリームまたはファイル１８０を作り出す。回復された入力ストリームまたはファイル１８０として送信されるソースパケットは、入力ストリーム１１０から送信された元の順序とまったく同じにまたは近似して送信できる。

通信システム１００には多数の変形態が存在する。たとえば、ＦＥＣ符号器１３０を使用しないか、あるいはＦＥＣ符号器１３０の代わりに、損失または消失したパケットの再送信の要求を受信し、ソース識別データに基づいてそれらのパケットを再送信するレトランスミッタ送信側モジュールを使用することができる。別の例として、ＦＥＣ復号器１７０を使用せず、あるいはＦＥＣ復号器１７０の代わりに、ソース識別データに基づいてどのパケットまたはシンボルが損失または消失しているかを判断し、それらの消失したパケットまたはシンボルを求める要求を送信し、再送信されたパケットまたはシンボルを受信するとそれらを適切な順序に配置し、回復されたストリーム１８０として渡すレトランスミッタ受信機モジュールを使用することができる。別の例として、ＦＥＣ符号器１３０およびＦＥＣ復号器１７０を使用せず、代わりにＦＥＣ復号器１７０の代わりにパケット再順序付け器を使用して、誤って順序付けされた受信ソースパケットをソース識別情報に基づいて再順序付けすることができる。別の例として、ＦＥＣ符号器１３０およびＦＥＣ復号器１７０を、ＦＥＣリペアと再送信ロジックおよび方法の両方の処理を備えるように拡張することができる。別の例として、ソース識別データのある部分を受信機に直接送信し、ソース識別データの他の部分をＦＥＣ回復プロセスの一部として回復することができる。

通信システム１００は、ストリーム、ファイル、または他のタイプのデータを配信するために使用できる。

シームレスアップグレードパス
通信システムの完全なアップグレードに長時間かかるのには様々な理由がある。たとえば、より旧式のデバイスが、計算リソースまたはメモリの制限により、アップグレードされたシステムをサポートする機能を有しない場合である。別の例として、一部のデバイスがアップグレードできない特性で設計されており、したがって、そのデバイスを、すでにアップグレードがインストールされた新しいデバイスと交換したときにしか、アップグレードが行えない。他の場合には、理論的にはアップグレードが可能であっても、実際には、アップグレードソフトウェアを何百万個ものデバイスにリモートでインストールし、アップグレードが正しく動作していることを確認し、ならびにインストール中の問題を解決するなどの費用のために、多数のデバイスをアップグレードするにはあまりに費用がかかるか危険なことがある。さらに、設置された多数のデバイスが存在し、システムが再び稼動する前にすべてのデバイスをアップグレードする必要がある場合には、数千、数万、さらには何百万個もの受信機を用いたＩＰＴＶサービスの大規模な運用展開の場合のように、完全にアップグレードするのに数日または数カ月かかることがあるように、アップグレード中にシステムをシャットダウンすることは実際には不可能なことがある。

そのような場合、シームレスアップグレードパスが大いに望ましいが、達成するのは、しばしば困難である。

以前にＦＥＣを使用していなかったシステム内のストリーミングデータのＦＥＣ保護の展開に関して、よく知られている潜在的なシームレスアップグレードパスが存在する。これを行う方法は、元のソースストリームが送信され、次いではるかに高品質のストリームプレイアウトをサポートするためにアップグレードされた受信機が使用することができる論理的に別個のストリーム中で追加のＦＥＣリペアデータが送信され、同時に、アップグレードされていないより旧式の受信機が、単にＦＥＣリペアデータを無視し、データの元のソースストリームを使用して依然として従来通り動作することができるように、ＦＥＣのアプリケーションを設計することである。このシームレスアップグレードパスの実現可能性が、ストリーミングアプリケーションにはシステマティックＦＥＣコードが好ましい主な理由の１つである。システマティックＦＥＣコードは、元のソースデータがＦＥＣ符号化データの一部として含まれ、送信されるという性質を有し、この文脈では、生成され、送信される追加のＦＥＣデータはＦＥＣリペアデータと呼ばれる。

このシームレスアップグレードパスに対する障害は、ＦＥＣリペアデータと、ＦＥＣリペアデータが生成される元のソースデータストリームとの間の関連付けを受信機において判断する必要があることである。特に、多くのＦＥＣ方式では、元のソースデータストリームを備えるソースシンボルまたはパケットをソースシンボル識別子またはパケット識別子によって識別および／または順序付けすることができ、ＦＥＣ復号器は、ソースシンボル識別子またはパケット識別子を使用して、受信ＦＥＣリペアデータから消失または損失したソースデータを回復することができる。しかしながら、多くのストリーミングシステムでは、そのようなソースシンボルまたはパケット識別子は、含まれないか、部分的にのみ含まれるか、完全には信頼できないか、または元のソースストリーム中でアクセスするのが困難である。ソースパケット識別子および／またはシーケンサとして使用できる各ソースパケットにおいてシーケンス情報をネイティブに含むＲＴＰなどのトランスポートプロトコルが存在するが、多数の展開された通信システムはこれらのプロトコルを使用せず、したがってタイミングまたはシーケンス情報は、元のソースパケット中に含まれないか、またはトランスポート層においてアクセスできない。一例として、ＩＰＴＶ展開は、しばしば、ＭＰＥＧ２ ＴＳ単位を搬送するＵＤＰパケットを使用し、これらの展開では、識別子は、しばしば、トランスポートレベルにおいて容易にアクセスしたりまたは利用したりできない。さらに、元のソースストリーム中のシンボルまたはパケットに識別データを追加することは、様々な理由で不可能である。これらの理由の中には、元のソースストリームが何らかの形で変更されると、既存の展開されたデバイスが動作しなくなること、あるいは既存の通信プロトコルが様々な他の理由で変更されないことが望まれるか、または変更することが不可能なことがある。これらの状況では、上述の単純なシームレスアップグレードパスは不可能であり、他の方法およびプロセスが必要になる。

これらのシステムにおいてレガシーデバイスとの互換性を維持するために、およびパケットまたはシンボルまたはデータシーケンシングまたは識別情報をネイティブに含まない通信システムの使用を可能にするために、本明細書で導入する方法は、論理的に別個のストリーム中でソースパケットシーケンスまたは識別子情報を送信し、それにより、能力のある受信機が、この情報をＦＥＣリペアデータとともに収集し、消去または損失または消失または破損したソースパケットまたはシンボルを回復することができるようにする方法を開示する。一実施形態において概説したソース識別データは、この情報を捕捉し、表現することができる。いくつかの実施形態では、この識別子またはシーケンス情報は、ＦＥＣリペアデータが送信されるチャネルのうちの１つで送信されるが、これは絶対に必要なわけではない。

図２に、ＦＥＣ方法をサポートするデバイスとサポートしないデバイスの混合を使用している通信システム２００のシームレスアップグレードパスの一例を示す。ヘッドエンドデバイス２１０は、元のソースデータを備える元のプログラムと、ＦＥＣリペアデータおよびソース識別データを備えるプログラムのリペアの両方を生成し、コアネットワーク２２０に送信する。コアネットワーク２２０は、元のプログラムをアクセスネットワーク２３０（１）、２３０（２）に送信し、ＦＥＣをサポートしないレガシーセットトップボックス（ＳＴＢ）２４０（１）、２４０（２）が存在するアクセスネットワーク２３０（１）にはリペアプログラムを送信せず、ＦＥＣ方法をサポートするＳＴＢ２５０（１）、２５０（２）が存在するアクセスネットワーク２３０（２）にはリペアプログラムを送信する。通信システム２００には多くの変形形態が存在し、レガシーＳＴＢ２４０（１）はリペアプログラムを受信するが、元のプログラムのみを使用する変形形態、コアネットワークとアクセスネットワークとの間の区別がない変形形態、元のプログラムおよびリペアプログラムが１つの論理ストリームとして送信される変形形態、ＦＥＣ方法の代わりにまたはＦＥＣ方法と組み合わせて再送信方法をサポートする変形形態、セットトップボックスが他のタイプの受信デバイスである変形形態、ある受信デバイスはソース識別データ方法をサポートせず、ある受信デバイスはソース識別データ方法をＦＥＣ方法とともにサポートし、別の受信デバイスはソース識別方法を再送信方法とともにサポートし、別の受信デバイスはソース識別方法を再送信方法とＦＥＣ方法の両方とともにサポートし、別の受信デバイスはソース識別方法をデータ再順序付け方法とともにサポートする変形形態、複数の送信デバイスが存在する変形形態、プログラムのリペアの送信および／または生成デバイスが元のプログラムの送信および／または生成デバイスとは論理的または物理的に異なる変形形態、送信デバイスが少なくとも時々受信デバイスとなるかまたはその逆の変形形態、ＦＥＣ方法または再送信方法以外の理由により、たとえばデータ再順序付け方法をサポートするためにソース識別データ方法をサポートする変形形態がある。

ソース識別方法と（ＦＥＣ方法および再送信方法など）関連する回復方法とをサポートする通信システムは、そのような方法をサポートしない通信システムと比較してシグナリングおよびデータ配信に関して、できる限り相違が少ないことが望ましい。たとえば、特定のストリームがソース識別方法および関連する方法をサポートするかどうかを示すために特殊なプレシグナリングが必要とされない場合、プレシグナリングは、たとえば電子的プログラムガイドまたはその均等物を含むことができることが望ましい。たとえば、様々な理由で、あるデータストリームは、ソース識別方法と関連する回復方法とをサポートすることができるが、他のストリームは、ソース識別方法と関連する回復方法とを同時にまたは異なる時点においてサポートすることができない。たとえば、最初はどのストリームもソース識別方法をサポートしないが、時間がたつにつれてますます多くのストリームがソース識別方法をサポートするようになり、最終的にすべてのストリームがソース識別方法をサポートすることができるようになる場合である。ストリームがソース識別方法をサポートするかしないかをシグナリングする必要がないこと、たとえば、電子的プログラムガイド中に記載された各ストリームがソース識別方法をサポートするかどうかをガイド中に含める必要がないことが大いに望ましいことがある。

図３に、ソース識別方法とＦＥＣ方法とをサポートする受信デバイスでロジックとして使用され、特定のストリームがソース識別方法とＦＥＣ方法とを使用するかどうかを示すためにプレシグナリングが必要とされない、起こりうる状態図３００の一例を示す。状態図３００では、受信機は、ストリームに最初に合流するときレガシー状態３１０で始動する、すなわち、受信機は、最初、送信中のストリームがソース識別方法とＦＥＣ方法とを使用していないと仮定する。とはいえ、レガシー状態３１０で、受信機は、現在のストリームのパケットの受信を継続的に監視し、ソース識別データ（またはＦＥＣリペアデータ）を受信すると、受信機は状態図のＳＩ非同期状態３２０に移行する。若干の時間が経った後、たとえば、１００ｍｓ後、最初のソース識別データ（またはＦＥＣリペアデータ）が、ソース識別方法とＦＥＣ方法とを使用するストリーム用の受信機に到着し、これにより、ＳＩ非同期状態３２０に移行するのに若干の待ち時間が生じる。受信機がＳＩ非同期状態３２０になると、受信機は、入手可能ならばＦＥＣリペアデータと、ソース識別データの両方を継続的に受信し、受信機は、これらのデータを使用して識別情報を解釈し、および／または受信したおよび消失したソースパケットもしくはシンボルの相対的な順序付けを判断しようと試みる。受信機が現在のソース識別データを解釈することができる場合、受信機はＳＩ同期状態３３０に移行する。ＳＩ同期状態３３０にある間、受信機は、ソース識別データの解釈を使用して、受信および消失したソースパケットまたはシンボルの相対的な順序付けを識別および／または判断し、今度はこれを使用して、受信したＦＥＣリペアデータを使用してデータの元のソースストリームの一部を回復することができる。受信機がＳＩ同期状態３１０にあり、現在のソース識別データをもはや解釈することができなくなると、現在のソース識別データが再び解釈できるようになるまで、受信機はＳＩ非同期状態３２０に移行する。ＳＩ同期状態３１０とＳＩ非同期状態３２０との間を移行する際の待ち時間の量は、ソースデータがソースブロックに編成され、ソース識別データがソースブロックごとに編成される場合、保護期間、すなわち、ストリームからデータのソースブロック上で受信するのにかかる時間期間の程度とすることができる。

状態図３００には多くの変形態が存在する。たとえば、ＦＥＣ方法の代わりにまたはＦＥＣ方法とともに再送信方法を使用することができる。別の例として、ＦＥＣ方法の代わりに再順序付け方法を使用することができる。別の例として、たとえば、ＦＥＣリペアまたは再送信方法が使用中であるかどうか、またはどんなタイプのＦＥＣコードが使用されているか、またはどんなタイプの再送信方法がストリームに対して使用中であるかを示すために、ソース識別データに加えて他のデータを搬送することができる。

図４に、ソース識別方法とＦＥＣ方法とをサポートする受信デバイス内で使用されるプロセスフローチャートの一例を与える。ステップ４２０において、プロセスはパケットの受信を監視し、パケットを受信すると、プロセスはステップ４３０に移動する。ステップ４３０において、プロセスは、ＳＩ同期状態が現在の状態である（図３のＳＩ同期３３０にあることに対応する）かどうかを確認する。ステップ４３０においてＳＩ同期が現在の状態である場合、プロセスはステップ４４０に移動する。ステップ４４０において、プロセスは、ソース識別データに基づいて受信パケットを適切なソースブロックに関連付け、プロセスはステップ４５０に進む。ステップ４５０において、プロセスは、現在のソースブロックをＦＥＣ復号すべき時刻であるかどうかを確認し、ＦＥＣ復号すべき時刻ではない場合、プロセスはステップ４２０に戻ってさらなるパケットを受信するが、ＦＥＣ復号すべき時刻である場合、プロセスはステップ４６０に移動し、受信したソースおよびリペアパケットと、リペアパケットをソースパケットに関係づける関連するソース識別データとを使用して、現在のソースブロックをＦＥＣ復号し、次いでステップ４７０において、現在のソースブロックを（たとえば、受信デバイス上のメディアプレーヤに）出力し、次のソースブロックが現在のソースブロックになり、処理はステップ４２０に続く。ステップ４３０においてＳＩ同期が現在の状態ではない場合、プロセスはステップ４８０に移動する。ステップ４８０において、受信パケットがソースパケットである場合は、それを（たとえばメディアプレーヤデバイスに）出力し、他の場合は廃棄し、処理はステップ４２０に戻る。

図４には詳細の多くを示していない。たとえば、図４には、ソースおよびリペアパケットとパケットの順序との間の関連付けを判断するために使用され、ステップ４３０においてＳＩ同期状態の状態を判断するために使用されるソース識別データの受信を示していない。図４に示すプロセスには多くの変形態が存在する。たとえば、ステップ４２０において、複数のパケットを受信し、その後ステップ４３０に進むことができる。

パケットとシンボルとの間の関係
前方消去訂正コードは、しばしば、固定のアルファベットから選択されたシンボルに作用する。たとえば、サイズ２^Ｍのアルファベットからシンボルを選択することができ、その場合、シンボルとＭ個の２進数字の文字列との間には明白な対応がある。以下、そのようなシンボルはＭビットのサイズを有すると呼ぶ。データは、しばしば、パケットの形態で通信チャネルを介して送信される。場合によっては、シンボルとパケットとの間に１対１の対応がある。たとえばLuby IIに記載のものを含む、他の場合には、パケットがシンボルよりも大きく、１つのパケットがいくつかのシンボルを備えることがある。さらに、シンボルおよびパケットは、ビット順序を除いて同じデータを備え、配置が異なり、またはパケット内に明示的に含まれないＦＥＣシンボルの中に、追加の情報、たとえばパケット長の２進表現を入れることができる。同様に、データ、たとえば、使用されないフィールドまたはあらゆるパケット中で同じ値を有するフィールドを備えるために、あるいは他の方法で回復できるために、ＦＥＣコードによって保護する必要がないデータは、ＦＥＣシンボル中に存在しないパケット中に存在することができる。

再送信方法はシンボルに基づくこともでき、シンボルは、バイトまたは何らかの大きいデータ単位とすることができる。たとえば、受信機は、ファイルまたは送信すべきデータストリームに、ある一定のバイト範囲を要求することができる。

ソースブロックとシンボルとの間の関係
多くの前方誤り訂正コードは、ソースブロックとして知られるソースシンボルの個別の集合に作用する。たとえば、ソースブロックは、ファイルのすべてのソースシンボル、またはストリーミングサービス時における特定のフラグメントのすべてのソースシンボルを備えることができる。

各ソースシンボルには、そのソースシンボルが属するソースブロック内で一意の識別情報が与えられる。この識別情報は、多くの場合、ソースパケットデータの一部ではないが、しばしば、ＦＥＣ復号プロセスのために使用される１つの情報である。

再送信方法はソースブロックに基づくこともでき、再順序付け方法はソースブロックに基づくこともできる。たとえば、ソースブロックは、受信機メモリに都合よく収まるサイズとすることができ、たとえば、そのサイズは、メモリに入れられる、またはメモリからディスクに書き込まれるデータブロックを識別するために都合がよいことがある。別の例として、ソースブロックは、特定の時間期間にわたって送信されるデータ量に対応するサイズとすることができ、たとえば、そのサイズは、データがどのソースブロックに属するかに基づいて、１つの時間期間中に送信されるデータを別の時間期間中に送信されるデータと区別するために都合がよいことがある。

本明細書で説明する方法の実施形態の多くでは、ソースブロックを使用する。ソースブロックは本方法の必須要素ではなく、ソースブロックを使用しない方法の変形態が存在することが当業者には認識されよう。

受信機
受信機がＦＥＣリペアデータを利用するために、受信機は、しばしば、ソース識別データを取得することができる必要があり、このソース識別データは、ＦＥＣリペアデータと同じチャネルに配信されても、配信されなくてもよい。通常、送信側および受信機は、ソース識別データを表現するのに同じプロトコルを使用しなければならない。そのようなプロトコルの一例を特定の実施形態で与える。受信機は、ソース識別データを使用して、ソースブロック内での受信ソースパケットの位置、ならびに消失したパケットの位置を識別する。次いでＦＥＣリペアデータを使用して、可能ならば、これらの消失したパケットを回復する。

アップグレードプロセス中、レガシー受信機は、受信した場合、ソース識別情報とＦＥＣリペアデータの両方を無視することができる。レガシー受信機は、アップグレード前のようにソースパケットを受信し、アップグレードされるまでアップグレード前のレベルで動作し続ける。

ソース識別方法
ソース識別データを表現し、搬送する多くの方法がある。一般に、帯域幅オーバーヘッド、ＣＰＵ負荷、およびサービス品質（ＱｏＳ）の間でトレードオフがある。

ソース識別方法の使用は、送信すべきすべてのソースシンボルまたはソースパケットまたは他のソースデータ単位の間、たとえば、ファイルまたはストリーム用に送信すべきすべてのソースデータの間を区別、識別または順序付ける能力を含む。他の場合には、（たとえば、送信順序の、または小さい時間ウィンドウ内で送信される）他のソースデータ単位のごく近傍にあるソースデータ単位が、たとえばデータストリーム用に区別、識別、または順序付けされるべきであり、再順序付け、区別、または識別の量が、送信側と受信機との間を動いているソースデータの最大数を超えるだけでよいように、ソース識別方法を適用することができる。これらの場合、実施の方法については本開示内で後述するように、ソースデータ単位を複数のソースブロックまたはそれらの均等物に分割するソース識別方法が適切であることがある。ソース識別方法によって使用されるソースブロック構造は、使用する場合、ＦＥＣまたは再送信方法によって使用されるソースブロック構造に一致しても、一致しなくてもよい。

以下で説明するソース識別方法の多くは、それらの説明でハッシュ関数を使用する。ハッシュ関数の役目の１つは、別個の長い文字列が別個のより短い文字列に写像されるように、長い文字列をはるかに短い文字列に写像することである。等価的に、ハッシュ関数は値を値に写像することができる。本明細書で説明する方法のために使用できる多数の可能なハッシュ関数があり、たとえば「Pairwise Independence and Derandomization」、Mike LubyおよびAvi Wigderson、Foundations and Trends in Theoretical Computer Science、第１巻、第４号、２００５年、Print ISSN 1551-305X、Online ISSN 1551-3068と題する刊行物に記載されているハッシュ関数（以下「ハッシュ関数」）を使用することができる。ハッシュ関数のリストを表現する多くの方法が存在し、そのうちのいくつかは「ハッシュ関数」に記載されており、たとえば、特定の入力についてどのようにハッシュ関数を計算するかを決定するビットシーケンスを表現するもの、またはハッシュ関数族からハッシュ関数の小リストを選択し、このリストへのインデックスでハッシュ関数を表現するものがある。可能なハッシュ関数族の一例は、正の整数（ａ，ｂ）によって記述でき、ａとｂは、０と正の整数値Ｐとの間の値の範囲にあり、対（ａ，ｂ）によって決定されるハッシュ関数は入力Ｘを（ａ＊Ｘ＋ｂ） ｍｏｄｕｌｏ Ｐに写像する。この例では、１対の値（ａ，ｂ）を使用して、Ｐが固定であるかまたは（ａ，ｂ）によって決定される場合は（ａ，ｂ）によって決定される、あるいは代替的に、Ｐが（ａ，ｂ）によって決定されない場合は３つ組（ａ，ｂ，Ｐ）によって決定される、ハッシュ関数の選択を示すことができる。ハッシュ関数の範囲内の値の数は素数に制限されず、値の数が任意の正の数とすることができる本明細書に記載の方法と同様のよく知られているハッシュ方法がある。この同じハッシュ関数族（または任意のハッシュ関数族）から選択されたハッシュ関数を示す別の方法は、値の３つ組の所定のリスト（ａ_１，ｂ_１，Ｐ_１）、（ａ_２，ｂ_２，Ｐ_２）、．．．、（ａ_ｉ，ｂ_ｉ，Ｐ_ｉ）に関するものであり、インデックスｊを使用して、（ａ_ｊ，ｂ_ｊ，Ｐ_ｊ）によって決定されるハッシュ関数の選択を示すことができる。

第１のソース識別方法の説明を以下に述べる。送信すべきソースデータを備えるＫ個の異なるソースデータ単位（たとえばソースパケットまたはシンボル）があると仮定する。すべてのＫ個のソースデータ単位が異なる値を有すると仮定する。Ｋ個のソースデータ単位をＫ個のＬビットベクトル（ｖ（０），ｖ（１），．．．，ｖ（ｋ−１））に写像するハッシュ関数をＨとする。Ｈがランダムなハッシュ関数である場合、Ｋ個のＬビットベクトルのうちの２つが同じ値に写像する確率は約Ｋ＾２／（２＾（Ｌ＋１））であり、ただし「＾」は指数関数である。したがって、Ｋ個のＬビットベクトルが少なくとも１−ｅｐｓの確率で異なるようにするためには、Ｌの値は約２＊ｌｏｇ（Ｋ）＋ｌｏｇ（１／ｅｐｓ）でなければならず、ただしｌｏｇは、２を底とする対数演算子である。第１の例として、Ｋ＝１０００＝１ｅ３およびｅｐｓ＝１ｅ−６である場合、Ｌは、約４０ビットすなわち５バイトでなければならず、ただし「１ｅ３」は１０＾３＝１０００の科学的指数表現である。第２の例として、Ｋ＝１ｅ６およびｅｐｓ＝１ｅ−１２である場合、Ｌは約８０ビットすなわち１０バイトでなければならない。送信側と受信機が同じハッシュ関数Ｈを計算することができると仮定すれば、ソース識別データは、単に、ソースデータ単位の順序で連結された、Ｋ個のＬビットベクトルの連結とすることができる。送信側は、ハッシュ関数Ｈをソースデータ単位の各々に適用してＫ個のＬビットベクトルを生成することによって、Ｋ個のソースデータ単位からソース識別データを計算することができる。ソースデータ単位を受信すると、受信機は、Ｈをソースデータ単位に適用して、対応するＬビットベクトル値を計算し、次いで受信機は、ソース識別データから、Ｋ個のソースデータ単位の間で受信したソースデータ単位を区別、識別、および順序付けすることができ、すなわち、これが、シーケンシング判断方法の一例である。上記の第１の例では、ソース識別データはサイズが５，０００バイトであり、上記の第２の例では、ソース識別データはサイズが１０，０００，０００バイトである。これらは両方とも、いくつかの適用例ではサイズが法外に大きくなることがある。ソース識別データのいくつかの使用法、たとえばいくつかの再送信方法では、受信機においてソースデータ単位を識別し、要求するのには、はるかに短いソース識別データで十分なことがある。たとえば、ＮＡＣＫベースの再送信方法では、受信機に伝達されるソース識別データは、ハッシュ関数Ｈの記述とすることができ、受信機は、受信した各ソースデータ単位に対してハッシュ関数Ｈを計算し、受信したソースデータ単位が写像されたＬビットベクトルを送信側に送信することができる。この場合、送信側は、どのＬビットベクトルが受信されたかに基づいて受信機によってどのソースデータ単位が受信されていないかを判断することができ、すなわち、これが、知られているソースデータ単位の識別ラベル判断方法の一例である。したがって、送信側および受信機がどのハッシュ関数Ｈを使用するかをあらかじめ決めていると仮定すると、受信機に明示的に伝達されるソース識別データの量を０にすることさえ可能である。しかしながら、この場合、消失したソースデータ単位の再送信を要求するために、ソースデータ単位ラベルの形態のかなりのデータ量を受信機から送信側に伝達することができる。

上記のソース識別方法の変形態では、送信側が、ハッシュ関数族から新しいハッシュ関数Ｈを繰り返し選択し、ハッシュ関数ＨがＫ個のソースデータ単位を異なるベクトルに写像するまで、ＨをＫ個のソースデータ単位に適用する。Ｈが、少なくとも１／２の確率でＫ個のソースデータ単位を異なるベクトルに写像するのには、Ｌ＝２＊ｌｏｇ（Ｋ）で十分であることに留意されたい。したがって、ｌｏｇ（１／ｅｐｓ）ランダムハッシュ関数のリストから、少なくとも１−ｅｐｓの確率でＫ個のソースデータ単位を異なるベクトルに写像する少なくとも１つのハッシュ関数が存在する。この場合、ソース識別データは、送信側によって選択されたハッシュ関数Ｈのインデックスと、Ｋの値と、Ｋ個のＬビットベクトルとの連結とすることができる。受信機は、ソース識別データを使用して、使用すべきハッシュ関数ＨのインデックスとＫの値とを決定し、次いでソースデータ単位を受信すると、Ｈをそのソースデータ単位に適用して、Ｋ個のソースデータ単位の間でソースデータ単位を区別、識別、または順序付けするＬビットベクトルを決定することができ、すなわち、これが、シーケンシング判断方法の一例である。Ｋ＝１，０００の場合、ソース識別データは、ハッシュ関数と、Ｋの値と、１，０００個の２０ビットベクトル、すなわち約２５００バイトとを識別するために２０ビットになり、Ｋ＝１，０００，０００の場合、ソース識別データは、ハッシュ関数と、Ｋの値と、１，０００，０００個の４０ビットベクトル、すなわち約５，０００，０００バイトとを識別するために４０ビットになる。

ソース識別データ方法の第３の変形態について以下に述べる。送信側は、ソース識別データを次のように計算することができる。たとえば上述の第１または第２のソース識別データ方法を使用して、Ｋ個のソースデータ単位をＫ個の異なるＬビットベクトルｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）に写像する第１のハッシュ関数Ｈを選択する。集合Ｓ_１＝｛０，１，．．．，Ｋ−１｝とする。異なる変形態では、Ｓ_１のサイズはＫよりも大きくても小さくてもよいが、いくつかの実施形態では、Ｓ_１のサイズとしてＫを選ぶのがよいことに留意されたい。ＬビットベクトルをＳ_１に写像するハッシュ関数Ｈ_１を選択する。ｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）をＳ_１に写像するＨ_１を使用する。Ｈ_１に関してｕ（ｊ）がｕ（ｉ）と同じ値に写像するようなｊがない場合、ベクトルｕ（ｉ）はＨ_１に関して一意に写像すると言われ、他の場合、ｕ（ｉ）はＨ_１に関して衝突を起こすと言われる。Ｈ_１に関してしきい値数未満のｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）が一意に写像する場合、新しいハッシュ関数Ｈ_１を選択し、Ｈ_１に関して一意に写像するｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）の数が少なくともしきい値数になるまで上記のプロセスを繰り返す。任意のｉについて、ｕ（ｉ）が、ランダムに一様に選択されたハッシュ関数Ｈ_１に関して一意に写像する確率は約１／ｅであり（ただし、ｅ＝２．７１８２８１８２８４５９０４５）、したがって、Ｋ／ｅはしきい値数の妥当な選択肢であるが、Ｋの値に応じて他のしきい値数が適切となり、たとえば、Ｋが０に近づくにつれて、しきい値数がＫに近づくかまたは達することに留意されたい。適切なＨ_１を決定した後、ＫビットベクトルＶ_１をＫ個の０ビットに初期化する。Ｈ_１に関してｕ（ｉ）が位置ｊに一意に写像するようなｉが存在するあらゆる位置ｊについて、Ｖ_１の第ｊビットを１に設定する。

Ｈ_１に関して衝突を起こすＫ個のベクトルからのＫ_１ベクトルをｕ_１（１）、．．．、ｕ_１（Ｋ_１）とする。集合Ｓ_２＝｛０，．．．，Ｋ_１−１｝とし、ＬビットベクトルをＳ_２に写像するハッシュ関数Ｈ_２を選択する。ｕ_１（１）、．．．、ｕ_１（Ｋ_１）をＳ_２に写像するＨ_２を使用する。Ｈ_２に関してしきい値数未満のｕ_１（１）、．．．、ｕ_１（Ｋ_１）が一意に写像する場合、新しいハッシュ関数Ｈ_２を選択し、Ｈ_２に関して一意に写像するｕ_１（１），…，ｕ_１（Ｋ_１）の数が少なくともしきい値数になるまで上記のプロセスを繰り返し、ただし、しきい値はＫ_１に依存する。ＫビットベクトルＶ_２をＫ個の０ビットに初期化する。Ｈ_２に関してｕ（ｉ）が位置ｊに一意に写像するようなｉが存在するあらゆる位置ｊについて、Ｖ_２の第ｊビットを１に設定する。

ｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）のすべてがハッシュ関数に関して一意に写像するようになるまで、追加のハッシュ関数Ｈ_３、．．．、Ｈ_ｈを用いて上記のプロセスを繰り返すことができる。特に、Ｈ_ｈは、ｕ_ｈ−１（１）、ｕ_ｈ−１（２）、．．．、ｕ_ｈ−１（Ｋ_ｈ）を一意に写像し、ただしｕ_ｈ−１（１）、ｕ_ｈ−１（２）、．．．、ｕ_ｈ−１（Ｋ_ｈ）は、Ｈ_１、…、Ｈ_ｈ−１に関して衝突を起こすＫ個のベクトルからのＫ_ｈ個のベクトルである。

図５Ａに、ソース識別データ方法の第３の変形態のステップの概略を示す。Ｋ個のソースパケット（５０１）を異なるベクトルｕ（１）、ｕ（２）、．．．、ｕ（Ｋ）に写像するハッシュ関数Ｈを選択する（５０２）。次に、前のハッシュ関数によってまだ一意に写像されていないＫ個のベクトルのサブセットに作用するハッシュ関数を選択する（５０３）（第１のハッシュ関数に対して、このサブセットはＫ個のベクトルのフルセットである）。次いで選択されたハッシュ関数を使用して、Ｋ個のベクトルのサブセットをハッシュする（５０４）。このハッシング中、作用されたパケットのインデックス、ハッシュ関数および得られた値、ならびに潜在的な衝突を表す情報を記録する（５０６）。一実施形態では、このデータはビットベクトル中に記録される。次に、ハッシュ関数の出力を分析して、衝突が発生したかどうかを判断することができる（５０５）。衝突がある場合、異なるハッシュ関数を用いて上記のプロセスを繰り返す。衝突が存在しない場合、記録情報（５０６）を使用してソースシンボルマップを形成することができる（５０７）。

ソース識別データまたは等価的にソースシンボルマップは、ハッシュ関数Ｈのインデックスと、Ｋの値と、追加のハッシュ関数の数ｈと、ハッシュ関数Ｈ_１、．．．、Ｈ_ｈのインデックスと、Ｋ_１、．．．、Ｋ_ｈ−１の値と、ビットベクトルＶ_１、．．．、Ｖ_ｈとの連結とすることができる。ソースデータ単位の位置は次のように求めることができる。ソースデータ単位にハッシュ関数Ｈを適用して、Ｌビットラベルｕを生成する。Ｈ_ｉに関してｕが一意に写像されるような最初のｉが存在するまでｕにＨ_１、．．．、Ｈ_ｈを連続的に適用し、Ｈ_ｉがｕを写像する位置をｊとする。ソースデータ単位の位置は、１に設定されたＶ_１、．．．、Ｖ_ｉ−１中のビットの総数＋最初のｊ個のビット内で１に設定されたＶ_ｉ中のビット数である。ソースデータ単位の順序付けおよびそれらの位置を判断するための本方法は、配置判断方法を可能にするソース識別方法の一例であり、すなわち、ソースデータ単位の位置はソース識別データに基づいて判断されるが、その位置は必ずしもソースデータ単位の送信位置ではない。Ｋ＝１０００であり、しきい値数Ｋ／ｅを使用する場合、ソース識別データは、ハッシュ関数を識別するために必要とされるビットと、Ｋ、Ｋ_１、Ｋ_２、．．．、Ｋ_ｈ−１の値と、後続の２７００ビット、すなわち約３５０バイトとである。Ｋ＝１，０００，０００の場合、ソース識別データは約３４０，０００バイトである。当業者なら認識されるように、可能なこの変形態には多くの代替形態および最適化形態が存在し、たとえば、値Ｋ_１、．．．、Ｋ_ｈ−１のシーケンスが異なるように選択し、しきい値数が異なるように選択し、ビットベクトルＶ_１、．．．、Ｖ_ｈをエントリ当たり複数ビットまたはエントリ当たり可変ビット数とし、ビットのすべてが１に設定されることが常に当てはまるなどとすれば、最後のベクトルＶ_ｈを省略することができる。

図５Ｂは、先ほど説明したソース識別データ方法の第３の変形態の図である。図５Ｂの例では、ソース識別データが生成されるべき８つのデータ単位（５１０（１）、．．．、５１０（８））がある。８つのデータ単位（５１０）の内容を８つのＬビットハッシュ値の組（５２０）にハッシュする第１のハッシュ関数Ｈを選択し、ただし、Ｈは、８つのデータ単位（５１０）の内容が異なれば８つのＬビットハッシュ値（５２０）も異なるように選択し、この例では、８つのＬビットハッシュ値（５２０）はそれぞれＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、ＧおよびＨと示されている。２つ以上の候補ハッシュ関数を選択した後に、すべてソースデータ単位を一意のハッシュ値に写像する適切なハッシュ関数Ｈを選択することができることに留意されたい。また、ある実施形態では、この最初のハッシュ関数を適用することをスキップし、以下で概説するプロセスは、ハッシュ値（５２０）ではなくソースデータ単位（５１０）に直接作用することによって処理できることに留意されたい。

図５Ｂを参照すると、Ｌビットハッシュ値（５２０）の各々を０〜７の間の範囲にあるハッシュ値に写像する第２のハッシュ関数Ｈ_１を選択し、ただし、Ｈ_１によって定義される写像は、ハッシュ値（５２０）からハッシュ値（５３０）への矢印によって示されている。２つ以上の候補ハッシュ関数を選択した後に、十分な数のハッシュ値（５２０）が一意のハッシュ値（５３０）に写像するように適切なハッシュ関数Ｈ_１を選択することができ、この例では、しきい値数は、ハッシュ値（５２０）の少なくとも４つが一意のハッシュ値（５３０）に写像するようにできることに留意されたい。ビットベクトルＶ_１（５４０）では、ビットｊの値１は、ハッシュ値ｊ（５３０）に写像する一意のハッシュ値（５２０）が存在することを示し、ビットｊの値０は、０個または２個以上のハッシュ値（５２０）がハッシュ値ｊ（５３０）に写像することを示す。この例では、Ｖ_１の第１のビットは、どのハッシュ値（５２０）もＨ_１の値０（５３０）に写像しないので０に設定され、Ｖ_１の第２のビットは、ハッシュ値ＢおよびＣ（５２０）が両方ともＨ_１の値１（５３０）に写像するので０に設定され、Ｖ_１の第３のビットは、どのハッシュ値（５２０）もＨ_１の値２（５３０）に写像しないので０に設定され、Ｖ_１の第４のビットは、ハッシュ値Ａ（５２０）がＨ_１の値３（５３０）に一意に写像するので１に設定され、Ｖ_１の第５のビットは、ハッシュ値Ｇ（５２０）がＨ_１の値４（５３０）に一意に写像するので１に設定され、Ｖ_１の第６のビットは、ハッシュ値Ｄ（５２０）がＨ_１の値５（５３０）に一意に写像するので１に設定され、Ｖ_１の第７のビットは、ハッシュ値ＥおよびＨ（５２０）が両方ともＨ_１の値６（５３０）に写像するので０に設定され、Ｖ_１の第８のビットは、ハッシュ値Ｆ（５２０）がＨ_１の値７（５３０）に一意に写像するので１に設定される。この例では、ハッシュ値Ｂ、Ｃ、ＥおよびＨ（５２０）が一意の値に写像しないので、これらの４つのハッシュ値（５２０）は、別のハッシュ関数Ｈ_２を用いて４つの値０〜３（５５０）に写像されることになり、衝突ビットベクトルＶ_２（５６０）が得られる。この例では、ハッシュ値ＥおよびＨ（５２０）はＨ_２によって一意に写像されるが、ハッシュ値ＢおよびＣ（５２０）はＨ_２写像で衝突するので、２つのハッシュ値ＢおよびＣ（５２０）は別のハッシュ関数Ｈ_３によって２つの値０〜１（５７０）に写像されることになり、衝突ビットベクトルＶ_３（５８０）が得られ、この例では、残りのすべての値がＨ_３によって一意に写像されるので、Ｈ_３が、ソース識別データを完成するために必要とされる最後のハッシュ関数である。この例におけるソース識別データは、値ｈ＝３と、値Ｋ＝８、Ｋ_１＝４、Ｋ_２＝２と、ハッシュ関数Ｈ、Ｈ_１、Ｈ_２、Ｈ_３の表現と、ビットベクトルＶ_１、Ｖ_２、Ｖ_３とを備える。

図５Ｂに示す例では、衝突ビットベクトルＶ_１、Ｖ_２、およびＶ_３のすぐ左のインデックスは、このソース識別データによってそのように判断されたソースデータ単位の位置を示し、すなわち、位置０はシーケンス番号０のパケットに対応し、位置１はシーケンス番号６のパケットに対応し、位置２はシーケンス番号３のパケットに対応し、位置３はシーケンス番号５のパケットに対応し、位置４はシーケンス番号７のパケットに対応し、位置５はシーケンス番号４のパケットに対応し、位置６はシーケンス番号２のパケットに対応し、位置７はシーケンス番号１のパケットに対応する。このソース識別データから、クライアントは、８つのソースパケットのうちの受信したまたは消失したソースパケットの位置を容易に計算することができる。したがって、たとえば、これらの位置を使用して、ＦＥＣ符号化および復号のためにソースブロック内でソースパケットを順序付けすることができるので、ソースデータ単位のＦＥＣ符号化および復号にはソース識別データで十分である。別の例として、受信機は、受信したすべてのソースデータ単位の位置を計算し、この計算から、消失したソースデータ単位の位置を判断することができる。受信機は、どのソースデータ単位が要求されているかを位置によって識別することによって、消失したソースデータ単位を求める要求を送信し、送信側は、それに応答して、要求された位置に基づいてどのソースデータ単位を送信すべきかを判断することができる。この第３の変形態は、配置判断方法を可能にするソース識別方法の一例である。

第４の変形態として、第３の変形態に関して上述したＫ個のソースデータ単位のシーケンシング（たとえば、それらのシーケンシングは、元のソースデータの順序に、または別の例としてソースデータの送信順序に対応する）と、それらの対応する位置との間の対応を含むように第３の変形態のソース識別データを増強することができる。たとえば、追加のシーケンシングデータは、Ｋ個のシーケンス番号の順序付きリストＳＥＱ＝＜ｓｅｑ_０，ｓｅｑ_１，．．．，ｓｅｑ_Ｋ−１＞を備えることができ、ただし、ｓｅｑ_ｊは、位置ｊを有するデータ単位のシーケンス番号である。したがって、この追加のシーケンシングデータは、位置とシーケンスの対応を備えることができる。

この第４の変形態に関するソース識別データの一例を図６Ａに示し、これは図５Ｂに示す例の増強である。図５Ｂの例では、Ｋ＝８およびｈ＝３である。図６Ａに示すように、ｈ値は３であり（６１０）、Ｋ値はＫ＝８、Ｋ_１＝４、Ｋ_２＝２であり（６２０）、４つのハッシュ関数は、Ｈ、Ｈ_１、Ｈ_２、Ｈ_３であり（６３０）、サイズがそれぞれ８、４および２のビットベクトルＶ_１、Ｖ_２、Ｖ_３は連結されて示され（６４０）、Ｋ＝８のシーケンス番号を備える追加のシーケンシングデータが（６５０）に示されている。この場合、ハッシュ関数に従って位置０に写像されるソースデータ単位は、シーケンス番号０のソースデータ単位であり、位置１に写像されるソースデータ単位はシーケンス番号６を有し、位置２に写像されるソースデータ単位はシーケンス番号３を有し、位置３に写像されるソースデータ単位はシーケンス番号５を有し、位置４に写像されるソースデータ単位はシーケンス番号７を有し、位置５に写像されるソースデータ単位はシーケンス番号４を有し、位置６に写像されるソースデータ単位はシーケンス番号２を有し、位置７に写像されるソースデータ単位はシーケンス番号１を有する。

この第４の変形態では、Ｋ個のソースデータ単位の順序を区別、識別、および判断するのにはこのソース識別データで十分であり、すなわち、これが、シーケンシング判断方法を可能にするソース識別方法の一例である。この第４の変形態に関するソース識別データの追加のサイズは、第３の変形態におけるソース識別データのサイズを超える、Ｋ＊ｌｏｇ（Ｋ）である。たとえば、Ｋ＝１，０００の場合、第３の変形態のソース識別データのサイズを超える追加のソース識別データのサイズは、１２５０バイトになり、Ｋ＝１，０００，０００の場合、追加のサイズは２，５００，０００バイトになる。この第４の変形態のいくつかの実装形態では、第３の変形態に対応するソース識別データの部分を受信機に送信し、それによって受信機はソースデータ単位の位置を判断できるようになり、これを使用してソースブロックをＦＥＣ復号することが可能になり（ただし、ソースブロック内でのソースデータ単位の順序付けはそれらの位置に従う）、ソースデータ単位のシーケンシングを判断することを可能にするソース識別データの追加の部分は、ＦＥＣ復号方法を使用して回復できるソースブロック内に含められる。たとえば、図６Ａおよび図６Ｂを参照すると、ｈ値（６１０）、Ｋ値（６２０）、ハッシュ関数の記述（６３０）、およびビットベクトル（６４０）は、ソースブロック中のソースデータ単位の位置を判断するために受信機に伝達されるソース識別データを備えることができる。このソース識別データは、ソースシンボルマップの形式とすることができる（６０１）。ソースシンボルマップ中に含まれる情報をパースして（６０２）、位置とシーケンスの対応を含まないことを除いて図６Ａ中に概略を示したデータを抽出することができる（６５０）。（これは、６０３にも示されている。）次いで、いくつかのハッシュ計算および衝突解消を含む、配置判断方法において、受信したソースデータ単位に対して、ソースシンボルマップを使用することができる（６０５）。一実施形態では、受信したソースデータ単位はソースパケットの形式とすることができる（６０４）。受信したシンボルを確認し、配置情報に関連付け（６０６）、その後ＦＥＣ復号器に供給することができる（６０７）。位置とシーケンスの対応データ（６５０）は、ＦＥＣ復号の後に利用可能なソースブロック中に含まれるソース識別データを備えることができ、これを使用して、回復されたソースデータ単位のシーケンシングを判断する（６０８）。図７に、いくつかのソースデータ単位（５１０（１〜８））を備えるソースブロック中に含まれる、位置とシーケンスの対応データ（６５０）の一例を示す。図７では、位置とシーケンスの対応データ（６５０）は、ソースブロック中に含まれるソースデータ単位（５１０（１〜８））の終端に付加されており、ソースブロック中のソースデータ単位の順序は位置情報によって判断される。

別の変形態として、ソース識別データはさらに、各ソースデータ単位のサイズを含むように増強できる。すべてのソースデータ単位が同じまたはほぼ同じサイズである場合、一般にこの変形態は使用されない。この変形態では、可変サイズソースデータ単位の位置をより正確に判断することができる。

図８Ａは、図５Ｂの例と同様であるソース識別データの別の実施形態の一例である。図５Ｂに示す例と図８Ａに示す例との間の１つの差異は、図８Ａのビットベクトルは１ビットのみではなく２ビットの情報を含むことである。この余剰データを使用して、所与のレベルでのハッシュ演算のために衝突またはその欠如についてのさらなる詳細を伝達することができる。たとえば、図８Ａでは、「１１」は、ハッシュ値のいずれもビットベクトル中の特定の場所に写像されなかったことを示すのに使用され、「００」は、ビットベクトル中の特定の場所が一意のソースパケットに写像することを示すのに使用され、「１０」は、２つ以上のソースパケットが特定の場所に写像することを示すのに使用されている。当業者ならば、このような情報を伝達するために他の同様の方式が使用できることを認識されよう。

図８Ｂに、データ構造にフォーマット化されたソース識別情報の一例を示す（８１０）。この場合、データ構造は様々な方法で使用できる。ソース識別情報には多数の可能なフォーマットがあることを当業者なら認識されよう。ソース識別情報を編成するために使用されるいかなるデータ構造でも、任意選択でＦＥＣ保護し次いで受信機に送信できる各パケット中に挿入するか、または複数のパケットにわたって拡散させることができる。

図８Ｂに示すデータ構造（８１０）の実施形態では、図示されたフィールドの各々の近似サイズは、フィールドの下にバイト単位で記載している。フィールドのサイズは、データ構造の異なる実施形態間で違ってもよい。図８Ｂにおいて、Ｇはパケット当たりのシンボル数を表す。Ｇが０に等しい場合、これは可変長パケットが存在することを示す。Ｈは、ソース識別情報を生成するのに使用されるモジュロハッシュ試行の数を表す。Ｆは、初期ハッシュ関数インデックスである。Ｃｈｅｃｋは、ソースブロックのチェックサムである。Ｂは、ハッシュ位置マップのビット割当てである。Ｌは、ハッシングの各繰返しのハッシュ衝突ベクトル長である。図８Ｂでは、Ｌは、最初の２つのレベルでは各２バイトであり、それ以降は各１バイトである。Ｖは、実際のハッシュ衝突ベクトルを格納する。Ｍは、ハッシュ位置マップを格納する。図８Ｂでは、各値はＢビットを占める。Ｂ１は、Ｇ＝０のみに対して適用可能な任意選択のフィールドである。Ｂ１は、可変パケットシンボル数のビット割当てを格納する。Ｍ１は、Ｇ＝０のみに対して適用可能な別の任意選択のフィールドである。Ｍ１は、パケット中のシンボルの数を格納する。

図８Ｂには、図８Ａからのデータを使用しているこの概略的フォーマットの一例（８２０）も示している。

受信機がソース識別データを使用する方法
プロトコルは、ハッシュされるパケット｛Ｋ，Ｋ_１，．．．，Ｋ_ｎ｝、衝突ベクトル｛Ｖ，Ｖ_１，．．．，Ｖ_ｎ｝、およびハッシュ関数｛Ｈ，Ｈ_１，．．．，Ｈ_ｎ｝の数を送信側と受信機との間で伝達し、ただし、Ｈ_ｎでは衝突が生じない、すなわちＶ_ｎはすべて０である。さらに、すべてのＫ個のソースパケットの位置と、ベクトル｛Ｖ，Ｖ_１，．．．，Ｖ_ｎ｝内のそれらの対応するハッシュ位置との間の対応、ならびに各ソースパケット中のシンボル数も伝達する。

受信機はどのようにして受信ソースデータのシーケンス番号を判断することができるかの一例として、受信機は、図５Ｂに示した例に記載の５番目のソースデータ単位（５１０（５））を受信すると仮定する。受信機は、このソースデータ単位にＨを適用して、ハッシュ値Ｅ（５２０）を得る。受信機は、Ｅ（５２０）にＨ_１を適用して、６（５３０）を得る。位置６のＶ_１は０（５４０）に等しいので、受信機は、何らかの他のハッシュ値（５２０）に対してＨ_１に関するＥ（５２０）の衝突が存在すると判断し、したがってＥ（５２０）にＨ_２を適用して、３（５５０）を得る。位置３のＶ_２は１（５６０）に等しいので、受信機は、Ｅ（５２０）がＨ_２に関して一意に写像すると判断する。受信機は、Ｖ_１中の１の数を計数し、この計数値を、Ｖ_２の位置３までだが位置３を含まないＶ_２中の１の数に加算することによってハッシュ関数によって決定されるこのソースデータ単位の位置を判断することができ、それは５に等しく、したがって５番目のソースデータ単位の位置は５である。図６Ａを参照すると、受信機は、位置とシーケンスの対応（６５０）の位置５を見ることによって５番目のソースデータ単位のシーケンス番号を判断することができ、それは４に等しく、したがって５番目のデータ単位のシーケンス番号は４である。受信したソースデータ単位ごとに同様のプロセスを使用することによって、受信機は、受信した各ソースデータ単位のシーケンス番号を判断することができ、シーケンス番号は０で始まりＫ−１に至るまで連続しているので、これにより、受信機は消失したすべてのソースデータ単位のシーケンス番号を判断することができる。

１つの潜在的な困難は、ソース識別データを使用してソースデータ全体ではなくその一部を識別するときの特定のソースブロックの識別である。というのも、ソースパケット自体がその情報を含まず、ソースブロック境界の判断および通信のための既存の同期プロトコルが存在しない場合があるからである。１つの可能な解決策は、当該のソースブロックよりも広範囲のソースパケットにわたって上記のソース識別通信プロトコルを使用すること、すなわち、生成されるソース識別データが前および次のソースブロックと重複できるようにすることである。図９にこの解決策の一例を示している。関連するソースパケットの全範囲内でのその相対位置に関してソースブロック境界をシグナリングし、伝達することができる。重複の範囲が広くなるほど、このプロトコルは、余分の帯域幅オーバーヘッドならびにＣＰＵ負荷の犠牲を伴うが、より頑強になる。

図１０に、図８Ｂに示した例と同様であるが、ソース識別データの構造が、基準からのオフセットを表す新規フィールド「Ｏ」を含むように変更された一実施形態の一例を示す。基準からのオフセットは、図９に示すように、ソースブロック間の生成されるソース識別データの重複の量を決定する。このオフセットを使用して、他の隣接するソースブロックとの、ソースブロックの開始と終了の両方におけるソースデータ単位の重複をそれぞれ決定することができる。このソース識別データによってカバーされるソースブロック内のソースデータ単位のシーケンシングおよび配置を決定することに関しては、このオフセット範囲内で受信された（隣接するソースブロックを下回る）どんなパケットでも廃棄することができる。（これらの廃棄されるパケットが属している隣接ソースブロックをカバーする他のソース識別データにより、これらのパケットをこれらの他の隣接ソースブロック内でどのようにシーケンシングまたは配置するかの判断を処理することができる。）
別の潜在的な問題は、単一のソースブロック内の２つ以上のソースパケットが同じである場合があることである。これらの同じパケットは、パケットに適用するハッシュ関数とは無関係に常にハッシュ衝突を受ける。ハッシュ位置マップでは、両方のパケットシーケンスは同じハッシュ位置に写像する。これは図１１Ａに示されている。

どのソースパケットが同じであるかを示し、その情報を受信デバイスに伝達する方法を考案することができる。したがって本方法は、受信機は、まったく互いに異なるソースパケットを処理するだけであるという問題を軽減し、その場合、上述のプロトコルを適用することができる。我々の通信の目的では、同じパケットに起因する衝突は、これらの２つのパケットは同じであり、ハッシュ関数において他のいかなる異なるパケットとも衝突しないと仮定しているので、衝突ビットベクトル中でマークしていない。同じ出力値は、同じソースパケットの存在を暗示する。そのような方法の一例が以下である。位置とシーケンスの対応を使用する代わりに、たとえば、図６Ａに示す（６５０）のように、シーケンスと位置の対応を使用する。その場合、各同じパケットは、そのシーケンス番号とは無関係に同じ位置に写像し、各同じパケットについて、シーケンスと位置のマップは、それが写像するのと同じ位置をそのシーケンス番号に記載することができる。たとえば、図１１Ｂに示すように９つのソースデータ単位（１１１０）が存在し、それとともに、図５Ｂに示すハッシュ値と同じハッシュ値（５２０）である、図示のＨからの対応するハッシュ値（１１２０）が存在すると仮定する。これらのハッシュ値（１１２０）によって決定される配置は、図５Ｂに示す配置と同じであると仮定する。さらに、シーケンスと配置の対応（１１３０）は、シーケンス番号４および８をもつ同じソースデータ単位が、両方とも位置５のソースデータ単位に写像されることを示す。この方法を使用するときは、シーケンス中のソースデータ単位の数と、ソース識別データの一部としての一意のソースデータ単位の数の両方を、たとえば、図１１Ｂの例では９と８を示すことが有用であろう。

別の潜在的な問題は、あらゆる利用可能なハッシュ関数をパケットに適用した後でも、異なるパケットがやはり衝突する場合がまれにあるということである。これは、限定されたハッシュ関数選択プールによって、または衝突を解決するために割り振られた時間量の不十分さによって起こる可能性がある。これらの場合、最後の衝突ビットベクトルは、「最後の衝突」用にマークされた１つまたは複数のビットを有する。受信機は、単に、ハッシュ衝突を解決することができないパケットを廃棄する。図１２に、この潜在的な解決策を示す。

ソースデータを識別するためにソースシステムマップを使用すると、多くの利点が提供される。たとえば、ソースシステムマップは、最高２、３百までの範囲にあるＫのいくつかの値に関して説明した実施形態のいくつかでの各ソースパケットについて追加の約４〜１２ビットのデータを必要とするだけなので、サイズについてはかなり効率的である。また、複数のハッシュ関数はＣＰＵ負荷を低減するのに役立つ。最初に低複雑度ハッシュ関数を作用させ、次いで、はるかに少ないパケットに対してより高い複雑度のハッシュ関数を後で作用させる。別の利点は、ハッシュ衝突を解決するための追加の方法が必要でないことである。また、ソースシステムマップは、ハッシュ関数の設計または置換に対して柔軟である。

ソース識別データの信頼できる送信
ネットワーク構成に応じて、ソース識別データは、単一チャネル中でＦＥＣリペアデータと組み合わせるか、または単独で送信できる。この情報は、パケット回復および／または再順序付けプロセスにおいて重要な場合があるので、ソース識別データに前方消去訂正技法を適用することが好ましい。ソース識別データに適用するＦＥＣは、元のソースストリーム上のＦＥＣコードといかなる関連ももつ必要がないことに留意されたい。ＦＥＣは、同じＦＥＣコードであっても、なくてもよく、システマティックであっても、なくてもよい。さらに、これらのソース識別データパケット（およびそれらのＦＥＣリペア部分）の送信を拡散させることは、送信がバースト消去に対しより弾力的になるので、有益な場合がある。別の技法は、可能ならば、帯域幅オーバーヘッドをさらに低減するために、ソース識別データの全部または一部を、元のソースストリームから生成されたＦＥＣリペアデータと組み合わせることである。ソース識別データを元のデータのＦＥＣリペアデータとともに使用しない場合、ソース識別データをＦＥＣ保護することがやはり好ましいことがある。

一実施形態では、ソースシンボルマップは、（連鎖反応コードを使用して生成されたデータなどの）ＦＥＣデータとともに送信できる。その結果、受信機は、２つのストリーム、すなわち、変更されていないソースデータをもつ１つのストリームと、元のストリーム用のＦＥＣデータ（連鎖反応リペアデータ）およびソースシンボルマップデータをもつ第２のストリームとを受信することができる。ソースシンボルマップデータはまた、それ自体のＦＥＣデータを有することもできる。

図１３に、ソースシンボルマップからＦＥＣリペアデータを生成する方法の一例を示す。図１３では、まずソースシンボルマップをいくつかのフラグメントに分解し（１３１０）、次いで適切なＦＥＣ保護方式への入力として使用する（１３２０）。ＦＥＣ保護方式は一組のリペアデータを生成し（１３３０）、次いで元のソースシンボルマップとともに送信することができる。一実施形態では、Ｊ個のソースシンボルマップフラグメントがある場合、ソースシンボルマップフラグメントには、０からＪ−１の範囲にあるシーケンス番号を割り当て、リペアデータを、Ｊから始まりＪから上に進むシーケンス番号に割り当てるように、シーケンス番号をソースシンボルマップ（１３１０）のフラグメントとリペアデータ（１３３０）とに付与する。

図１４は、ソースパケットからリペアシンボルが生成されている図である。一実施形態では、リペアシンボルは、連鎖反応コードを使用して生成される。図１４に示すように、ソースパケットは、複数のソースシンボルを含み、ソースパケットはそれぞれ、異なる数のシンボルを含むことができる。

図１５に、一実施形態におけるリペアパケット情報の構造を示し、このリペアパケットはＦＥＣデータとソース識別データの両方を含む。図１５に示す実施形態では、ソース識別データはソースシンボルマップの形式である。図１５では、Ｒは、パケット中のＦＥＣリペアシンボルの数を表す。まれな場合では、パケット中にリペアシンボルがない場合、Ｒが０であることがある。ＳＢＮは、このパケットによって保護されるソースブロック番号を表す。図１５に示す実施例では、ＳＢＮは０〜４０９５の範囲にある。ＰＰは、ＦＥＣ方式によって与えられる保護期間である。図１５に示す実施形態では、ＰＰは１０ｍｓを単位とする。ＳＢＮとＰＰは両方とも、ストリームの同期を拡張するために使用できる。ＥＳＩは、パケット中の第１のＦＥＣリペアシンボルの符号化シンボルＩＤである。Ｋは、ソースブロック中のソースシンボルの数である。Ｊは、ＳＳＭフラグメントシーケンス番号である。Ｘは、元のＳＳＭフラグメントの数である。同じパケット内で連続するＦＥＣリペアシンボルは、連続する符号化シンボルＩＤを有する。ＳＳＭフラグメントは、元のソース識別データ、または元のソース識別データフラグメント用のＦＥＣリペアデータのいずれかを備えることができる。

図１６に、図１５に示すデータ構造からのフィールドを使用してどのようにソースシステムマップを再構成することができるかを示す１つの例示的な実施形態を示す。図１６では、一実施形態における元のソースデータを保護するＦＥＣリペアパケット中でどんなＳＳＭデータを搬送することができるかを示すために、リペアパケットからのフィールドＪ、Ｘ、およびＳＳＭフラグメント（１６１０）を拡張している。

図１７は、受信機がソースシステムマップを使用して、受信機が受信したソースシンボルに適用する方法を示す流れ図である。受信したソースパケット（１７１０）にＳＳＭ情報を適用する（１７２０）。受信機がソースパケットの一意の位置を識別することができない場合、または何らかの理由でプロセスが不正な結果を出力する場合（１７３０）、たとえば、ソースパケットがこのソースブロックの位置またはシーケンス番号の有効な範囲内にない場合、このソースブロックからソースパケットを廃棄することができる（１７４０）。対応付けに成功した場合、ソースシンボル位置および／またはシーケンシングをソースシンボルマップから抽出し（１７５０）、ソースシンボルに関連付けることができる。次いで、ソースシンボルを連鎖反応復号器などのＦＥＣ復号器に渡して（１７６０）、ソースブロックの回復などのさらなる処理を行うことができる。

伝送誤り処理
多くの実施形態では、符号器から復号器に送信されるデータストリームは、ネットワークを介して一連のパケット中で送信される。多くのそのようなネットワークでは、パケットの送信中に発生し得る多数の潜在的な誤りが存在する。送信中に、パケットは損失し、パケット配信は遅延になり、パケットは重複する可能性があり、復号器は、異なる時刻において同じパケットを受信する可能性がある。いくつかの実施形態では、復号器は、時間制約を受け、ある時間期間の後に所与のソースブロックの復号をタイムアウトさせることがある。しかし、関連するソースブロックがすでにタイムアウトした後に、ネットワークの性質のせいでパケットが受信機に配信されることがある。以下は、受信機が様々なパケット誤りを扱うことができる方法のいくつかの例である。以下の例のいずれも、受信機によって様々な誤りを処理することができる方法の網羅的なリストを与えるものではない。

図１８に、損失したパケットが２つのブロックにわたるパケット受信タイムアウトを示す。間違ったブロックにソースパケットが関連付けられる可能性がある場合、両方のブロックをアプリケーションにフラッシュすることができる。本明細書で使用するフラッシングは、当該のブロックを復号するための試行をしないでソースパケットがそのまま戻されることを意味することができる。代替的に、フラッシングは、ソースパケットを単に廃棄することを意味することができる。ブロックＮ＋２に対して作用すれば、通常の受信および復号に戻る。時々、タイムアウトは、３つ以上のブロックにわたる損失したパケットに関連することがある。そのような場合、中間のソースパケットを一時的ブロック中に格納し、次いで最終的にアプリケーションにフラッシュすることができる。

図１９に、ソースブロック中の早期での早期バースト損失を示す。ブロックＮに属するパケットはアプリケーションにフラッシュされる。ブロックＮ＋１に対して作用すれば、通常の受信および復号を続けることができる。

図２０および図２１に、同じブロック内でまたは拡張ブロック内で受信された遅延パケットを示す。どちらの状況でも、遅延パケットは、特殊な処理なしでブロックＮ内において正しく識別できる。ソースブロックＮおよびＮの後のソースブロックについて、受信および復号動作が通常通り進む。

図２２に、拡張ブロックを越える遅延パケットを示す。ブロックＮは通常通り復号される。ブロックＮ＋１については、遅延パケットに対してなされ得ることに関して３つの可能なシナリオがある。第１の可能性は、遅延パケットが不正であるとみなされることである。たとえば、パケットは、ＳＳＭ中に含まれる任意のパケットＩＤに正しくハッシュすることができない場合がある。この場合、パケットは廃棄され、ブロックＮ＋１が通常通り復号される。第２の可能性は、遅延パケットには、ブロックＮ＋１上のＳＳＭに従ってパケットＩＤが割り当てられるが、この割り当てられたパケットＩＤが、ブロックＮ＋１について受信された別のパケットのＩＤと一致することである。このシナリオでは、ブロックＮ＋１を復号する試行は行われず、ブロックＮ＋１はアプリケーションにフラッシュされる。第３の可能性は、遅延パケットには、ブロックＮ＋１上のＳＳＭに従ってパケットＩＤが割り当てられ、ブロックＮ＋１中の他のどんなパケットもこのパケットＩＤをとらないことである。このシナリオでは、ブロックＮ＋１に対する復号の試行が行われ、回復されたブロックのチェックサムに依拠してこの復号の試行が無効化される。この無効化により、ブロックＮ＋１について受信したソースパケットのみがアプリケーションに戻される。

図２３Ａ／図２３Ｂに、拡張ブロック内で受信された重複パケットを示す。どちらの状況でも、重複パケットは、ブロックＮ内において正しく識別できる。受信および復号動作が、通常通り容易に進むことができる。

図２４に、拡張ブロックを越えて受信された重複パケットを示す。ブロックＮは通常通り復号される。ブロックＮ＋１については、重複パケットに対してなされ得ることに関して３つの可能なシナリオがある。第１の可能性は、重複パケットが不正であるとみなされることである。たとえば、パケットは、ＳＳＭ中に含まれる任意のパケットＩＤに正しくハッシュすることができない場合がある。この場合、パケットは廃棄され、ブロックＮ＋１が通常通り復号される。第２の可能性は、重複パケットには、ブロックＮ＋１上のＳＳＭに従ってパケットＩＤが割り当てられるが、この割り当てられたパケットＩＤが、ブロックＮ＋１について受信された別のパケットのＩＤと一致することである。このシナリオでは、ブロックＮ＋１を復号する試行は行われず、ブロックＮ＋１はアプリケーションにフラッシュされる。第３の可能性は、重複パケットには、ブロックＮ＋１上のＳＳＭに従ってパケットＩＤが割り当てられ、ブロックＮ＋１中の他のどんなパケットもこのパケットＩＤをとらないことである。このシナリオでは、ブロックＮ＋１に対する復号の試行が行われ、回復されたブロックのチェックサムに依拠してこの復号の試行が無効化される。この無効化により、ブロックＮ＋１について受信したソースパケットのみがアプリケーションに戻される。

事例研究
以下は、多種多様なシステムについて説明した方法の特徴を示すいくつかの事例研究である。これらは、ＦＥＣコードを使用してＦＥＣリペアパケットを追加して元のストリームを保護し、各ＳＳＭがデータストリーム全体のうちの小部分をカバーするストリーミング適用例の事例研究である。これらの事例研究のすべてにおいて、
各ソースデータパケットは、７つのＭＰＥＧ−２ ＴＳ単位を搬送し、各ＭＰＥＧ−２ ＴＳ単位は１８８バイトである。

各ソースパケットが１シンボルとなるように、シンボルサイズを１３２０バイトに選択する。各リペアパケットは、１つのＦＥＣリペアシンボルと、ＳＳＭの全部または一部などの他のデータとを搬送する。

ＳＳＭは、各ＦＥＣリペアパケット中で全体的に搬送されるか、ＦＥＣリペアパケット内で部分的に搬送されるかのいずれかである。

各ＳＳＭは、ＦＥＣ保護を適用すべきデータの１つのソースブロックをカバーし、各ＳＳＭは、隣接するソースブロックからのパケットをフィルタ除去するためにそれらのソースブロックに関する何らかの重複情報を搬送する。

各場合において、ネットワークを介してパケットを送信するときのパケットのフラグメンテーションを避けるために、最大パケットサイズは１５００バイトであることが望ましい。

各場合において、Ｐ_ＳＳＭおよびＰ_ＦＥＣという２つの値が導出される。Ｐ_ＳＳＭは、ＳＳＭデータを回復するために十分なパケットがソースブロックに関して到着しない確率であり、一方、Ｐ_ＦＥＣは、理想的なＦＥＣコードを仮定しているソースブロックを回復するために十分なパケットがソースブロックに関して到着しない確率である。これらの確率は、各事例について述べる損失状態の下に、ランダムなおよび独立したパケット損失を仮定して計算される。

事例研究１
ソースデータストリームレートは４Ｍｂｐｓである。

ＳＳＭカバレージ期間（＝保護期間）：１２５ｍｓ
損失状態：０．１％
導出されたパラメータ：
１ソースブロック中のパケット数＝４８
リペアパケットの数＝３
ＳＳＭについての考察：
ＳＳＭ用に使用されるパケット数（各端部上で５パケットが重複）＝５８
ハッシュ関数の数＝５
ハッシュ衝突ベクトル割当て＝約２０バイト
ハッシュ位置マップ割当て≦５８バイト
ＳＳＭ長は１００バイト未満なので、ＳＳＭ全体を各ＦＥＣリペアパケット中で搬送することができる。

失敗率：

事例研究２
ソースデータストリームレートは４Ｍｂｐｓである。

ＳＳＭカバレージ期間（＝保護期間）：２５０ｍｓ
損失状態：０．７％
導出されたパラメータ：
１ソースブロック中のパケット数＝９５
リペアパケットの数＝９
ＳＳＭについての考察：
ＳＳＭ用に使用されるパケット数（各端部上で１０パケットが重複）＝１１５
ハッシュ関数の数＝５
ハッシュ衝突ベクトル割当て＝約４０バイト
ハッシュ位置マップ割当て＝約１１４バイト
全ＳＳＭ長＝約１６８バイト
ＳＳＭは、２つのセグメントに分割する
ＦＥＣ保護を使用して、別の９−２＝７個のリペアＳＳＭセグメントを生成する
各ＦＥＣリペアパケットは、１つのＳＳＭセグメントを搬送する
失敗率：

事例研究３
ソースデータストリームレートは６Ｍｂｐｓである。

ＳＳＭカバレージ期間（＝保護期間）：５００ｍｓ
損失状態：０．７％
導出されたパラメータ：
１ソースブロック中のパケット数＝２８５
リペアパケットの数＝２５
ＳＳＭについての考察：
ＳＳＭ用に使用されるパケット数（各端部上で３０パケットが重複）＝３４５
ハッシュ関数の数＝７
ハッシュ衝突ベクトル割当て＝約１２０バイト
ハッシュ位置マップ割当て＝約４００バイト
全ＳＳＭ長＝約５３８バイト
ＳＳＭは、５つのセグメントに分割する
ＦＥＣ保護を使用して、別の２５−５＝２０個のリペアＳＳＭセグメントを生成する
各ＦＥＣリペアパケットは、１つのＳＳＭセグメントを搬送する
失敗率：

図２５は、０．７％未満の損失状態下での様々な保護期間および保護量に対する４Ｍｂｐｓストリームの失敗率チャートである。このデータから引き出すことのできる結論は、不完全なＳＳＭによる復号失敗の確率は、ＦＥＣ受信シンボルの数が不十分なことによる復号失敗の確率よりもはるかに小さいということである。

複数のストリーム／再送信の実施形態
図２６に、ストリームの混合を使用してデータをセットトップボックスに送信する通信システム２６００の一例を示す。ヘッドエンドデバイス２６１０は、ソースストリーム中に元のソースデータを備える元のプログラムと、ＦＥＣリペアデータおよび／またはソース識別データを備えることができるプログラム用の２つの別個のリペアストリームとをネットワーク２６２０に送信する。ネットワーク２６２０は、元のプログラムを中間サーバ２６３０に送信する。この中間サーバ２６３０は、ソースストリームとリペアストリームのうちの１つとをネットワーク２６５０に送信する。ネットワーク２６５０は、ネットワーク２６２０と同じネットワークとすることができるが、異なるネットワークとすることもできる。いずれの場合も、ネットワーク２６５０は次いで、ソースストリームと１つのリペアストリームとを１つまたは複数のＳＴＢ２６４０に送信する。ＳＴＢのいずれかによって受信されたデータが、ソースデータを生成するのに不十分である場合、ＳＴＢは再送信ストリームを要求することができる。この要求は中間サーバ２６３０に送信され、この中間サーバ２６３０は、再送信の要求に応答して、第１のリペアストリームとは異なる第２のリペアストリームを送信することができる。いくつかの実施形態では、第２のリペアストリームからのパケットは中間サーバ上でキャッシュされる。いくつかの実施形態では、中間サーバ２６３０は、ＳＴＢにまだ送信されていないリペアデータをキャッシュした。いくつかの実施形態では、中間サーバ２６３０は、ソースストリームの保護期間に基づいてリペアデータをキャッシュする。いくつかの実施形態では、ソースまたはリペアストリームのキャッシングは、システム／ネットワーク中の他の場所で行うことができる。いくつかの実施形態では、ＳＴＢは、再送信要求中に、リペアパケットの特定の数など、リペアデータの特定の量を要求することができる。いくつかの実施形態では、ＳＴＢは、ＳＴＢが受信したソース識別データに基づいてリペアデータ（ソースデータまたはＦＥＣリペアデータ）を要求することができる。いくつかの実施形態では、最初にソースデータおよび／またはリペアデータを受信したＳＴＢは、中間サーバにキャッシュされているデータを（１つまたは複数の）ユニキャストストリーム中で第１に受信し、次いで中間サーバは、ＳＴＢに送信された（１つまたは複数の）ストリームを、（１つまたは複数の）マルチキャストストリームに遷移する。通信システム２６００には多くの変形形態が存在し、ソースストリームおよびリペアストリームが１つの論理ストリームとして送信される変形形態、セットトップボックスが他のタイプの受信デバイスである変形形態、ある受信デバイスはソース識別データ方法をサポートせず、ある受信デバイスはソース識別データ方法をＦＥＣ方法とともにサポートし、別の受信デバイスはソース識別方法を再送信方法とともにサポートし、別の受信デバイスはソース識別方法を再送信方法とＦＥＣ方法の両方とともにサポートし、別の受信デバイスはソース識別方法をデータ再順序付け方法とともにサポートする変形形態、複数の送信デバイスが存在する変形形態、プログラムのリペアの送信および／または生成デバイスが元のプログラムの送信および／または生成デバイスとは論理的または物理的に異なる変形形態、送信デバイスが少なくとも時々受信デバイスとなるかまたはその逆の変形形態、ＦＥＣ方法または再送信方法以外の理由により、たとえばデータ再順序付け方法をサポートするためにソース識別データ方法をサポートする変形形態がある。

ＤＶＢ−Ｔ／ＤＶＢ−Ｈ実施形態
ソースデータを含むデータストリームとは別個のデータストリーム中で送信されるソース識別データは、様々なシステムに適用できる。たとえば、付録Ａは、ＦＥＣ保護およびソース識別データが、ＤＶＢ−Ｔブロードキャストネットワークなどのネットワーク上で搬送される第１のデータストリーム上で送信でき、一方、元のソースデータは、同じネットワーク上で送信される第２のデータストリーム上で送信できるシステムを開示している。付録Ａは、すべての目的のために本開示に組み込まれる。他の実施形態では、ＦＥＣ保護およびソース識別データは、ＤＶＢ−Ｈブロードキャストネットワークなどのネットワーク上で搬送される第１のデータストリーム上で送信でき、一方、元のソースデータは、ＤＶＢ−Ｔネットワークなどの別のネットワーク上で送信される第２のデータストリーム上で送信できる。

ＤＶＢ−Ｔネットワークおよび設定は、定位置受信機に送信するように設計されているが、ＤＶＢ−Ｔネットワークの使用を他のタイプの受信機、たとえば、より劣悪な位置にあるモバイル受信機または定位置受信機に拡張することには大きい利点があることに留意されたい。これらのタイプの新しい受信機では、既存のＤＶＢ−Ｔネットワーク上に存在する誤り状態は、しばしば、高品質ストリーミングビデオなどの関連する適用例をサポートするにはあまりに厄介である。本開示で説明する方法を使用することにより、これらのネットワークの使用をこれらの新しい受信機に拡張して、通常ならばあまりに厄介でサポートできない適用例をサポートできるようになる。ネットワークアップグレードを適用することはこれらの方法には必要とされず、これらの新しい受信機をサポートするために既存の受信機をアップグレードすべきという要件も存在しない。ネットワーク状態が、新しい受信機にとって既存の受信機よりもはるかに悪い場合であっても、既存の受信機と同じ品質でビデオストリームを回復し、プレイアウトするために、新しい受信機は、本開示で説明する方法を使用することによって、元のデータストリームに関連するソース識別データおよびＦＥＣリペアデータを受信することに加えて、元の変更されていないデータストリームを受信できるようになる。

本開示を検討すれば当業者には明らかなように、本明細書に記載の方法は、それぞれのコードに関連する手順に従ってデータを独立して処理する場合よりも大きい誤り訂正を与える仕方で２つ以上の送信コードからのデータを組み合わせることができるという性質を受信機において維持しながら、異なるＦＥＣコードをサポートするようにもちろん拡張できる。

上記の記述は、例示および説明のために提示した。上記の記述は、網羅的なものでも、本発明を開示した正確な形態に限定するものでもなく、上記の教示に照らして明らかに多くの修正および変更が可能である。説明した実施形態は、本発明の原理およびその実際的な適用を最も良く説明し、それにより他の当業者が、企図される特定の使用に適した様々な実施形態において様々な修正を加えて本発明を最も良く利用できるようにするために選択したものである。本発明の範囲は、本明細書に添付の特許請求の範囲によって定義されるものである。
以下に本件出願当初の特許請求の範囲に記載された発明を付記する。
［１］ ソースデータのソース識別データを生成し、送信するための方法であって、前記ソースデータがＫ個のソースデータ単位に分割されており、Ｋが１よりも大きく、前記ソース識別データが、他のソースデータ単位に対するソースデータ単位の位置を識別するため、および損失または破損したソースデータ単位を識別するために使用でき、前記方法が、
前記Ｋ個のソースデータ単位からソース識別データを生成することと、
前記ソースデータ単位のセットを備える第１のデータストリームを受信機に送信することと、
前記ソース識別データを備える第２のデータストリームを前記受信機に送信することと、
を備える方法。
［２］ 前記ソース識別データが、前記第１および第２のデータストリームの受信者が、前記ソース識別データを生成するために使用される前記Ｋ個のソースデータ単位の識別ラベルを判断できるようにする［１］に記載の方法。
［３］ 前記ソース識別データが、前記第１および第２のデータストリームの受信者が、任意のソースデータ単位の識別ラベルを判断できるようにする［１］に記載の方法。
［４］ 前記ソース識別データが、前記第１および第２のデータストリームの受信者が、すべての前記ソースデータ単位の順序付けに関して所与のソースデータ単位の位置を判断できるようにする［１］に記載の方法。
［５］ 前記ソース識別データが、前記第１および第２のデータストリームの受信者が、すべての前記ソースデータ単位のソース判断順序シーケンスに関して所与のソースデータ単位の位置を判断できるようにする［１］に記載の方法。
［６］ 前記第２のデータストリームが前記ソースデータ単位のリペアデータをさらに備える［１］に記載の方法。
［７］ 前記第２のデータストリームが前記ソース識別データのリペアデータをさらに備える［１］に記載の方法。
［８］ 前記第１のデータストリームがＤＶＢ−Ｔを介して送信され、前記第２のデータストリームがＤＶＢ−Ｈを介して送信される［１］に記載の方法。
［９］ 前記受信機から追加のデータの要求を受信することと、
前記受信機に第３のデータストリームを送信することと、
をさらに備える［１］に記載の方法。
［１０］ 前記第３のデータストリームがソースデータ単位の第２のセットを備える［９］に記載の方法。
［１１］ 前記第３のデータストリームが前記ソースデータ単位のリペアデータを備える［９］に記載の方法。
［１２］ 前記Ｋ個のソースデータ単位からソース識別データを生成することが、
前記Ｋ個のソースデータ単位の各々から順序集合Ｓを作成するステップと、
ｉ）Ｓの各メンバにハッシュ関数Ｈ _ｉ を適用するステップであって、Ｈ _ｉ が、Ｓの前記メンバを可能なＬ個のハッシュ出力の１つに写像し、Ｈ _ｉ が、Ｓの前記メンバの少なくともＸ個を一意のハッシュ出力に写像する、適用するステップと、
ｉｉ）前記Ｌ個のハッシュ出力に対応するベクトルを作成するステップであって、前記ベクトルが、前記Ｌ個のハッシュ出力のどれが衝突を経験するか、および前記Ｌ個のハッシュ出力のどれがＳのメンバに一意に写像するかを示す、作成するステップと、
ｉｉｉ）一意のハッシュ出力に写像しないＳの要素を備える集合Ｓ _ｉ を作成するステップと、
ｉｖ）Ｓ _ｉ が空集合になるまで、または最大回数の繰返しが実行し終わるまでステップｉ〜ｉｉｉを繰り返すステップであって、ステップｉ〜ｉｉｉの繰返しごとにＳ _ｉ がＳとして使用され、繰返しごとにＨ _ｉ が、ステップｉ〜ｉｉｉの前の繰返し中に使用された前記ハッシュ関数とは異なるハッシュ関数であり、繰返しごとにＬおよびＸの値が変化することができる、繰り返すステップと、
ステップｉ〜ｉｉｉの各繰返し中に作成された前記ベクトルからソース識別データを生成するステップと、
を備える［１］に記載の方法。
［１３］ 前記ベクトルが、Ｓの一意に写像された各メンバのＳ中の所在をさらに示し、前記方法が、
ステップｉ〜ｉｉｉの各繰返し中に作成された前記ベクトルによって示されるようにＳの前記一意に写像されたメンバの前記所在から位置とシーケンスとの対応を生成すること、
をさらに備える［１２］に記載の方法。
［１４］ ［１］に記載の方法を実行するためのコードを備えるコンピュータ可読媒体。
［１５］ プロセッサと、前記プロセッサに結合された［１４］に記載のコンピュータ可読媒体とを備える送信機。
［１６］ ソース識別データを受信し、前記ソース識別データをソースデータに関連付けるための方法であって、前記ソースデータがＫ個のソースデータ単位に分割されており、Ｋが１よりも大きく、前記ソース識別データが、他のソースデータ単位に対するソースデータ単位の位置を識別するため、および損失または破損したソースデータ単位を識別するために使用でき、前記方法が、
第１のデータストリームから複数のソースデータ単位を受信することと、
第２のデータストリームからソース識別データを受信することと、
前記ソース識別データを前記複数のソースデータ単位に関連付けることと、
を備える方法。
［１７］ 前記受信された複数のソースデータ単位の識別ラベルを判断することをさらに備える［１６］に記載の方法。
［１８］ 前記受信された複数のソースデータ単位のメンバではないソースデータ単位の識別ラベルを判断することをさらに備える、［１６］に記載の方法。
［１９］ すべての前記ソースデータ単位の順序付けに関して前記複数のソースデータ単位中のソースデータ単位の位置を判断することをさらに備える［１６］に記載の方法。
［２０］ すべての前記ソースデータ単位のソース判断順序シーケンスに関して前記複数のソースデータ単位中のソースデータ単位の位置を判断することをさらに備える［１６］に記載の方法。
［２１］ 前記第２のデータストリームから前記複数のソースデータ単位のリペアデータを受信することをさらに備える［１６］に記載の方法。
［２２］ 前記第２のデータストリームから前記ソース識別データのリペアデータを受信することをさらに備える［１６］に記載の方法。
［２３］ 前記第１のデータストリームがＤＶＢ−Ｔを介して受信され、前記第２のデータストリームがＤＶＢ−Ｈを介して受信される［１６］に記載の方法。
［２４］ 前記Ｋ個のソースデータ単位のいずれかが受信されなかったかどうかを判断するために、前記ソース識別データおよび前記複数のソースデータ単位を分析することと、
前記Ｋ個のソースデータ単位のいずれかが受信されなかった場合、追加のデータを要求することと、
をさらに備える［１６］に記載の方法。
［２５］ 第３のデータストリームから前記追加のデータを受信することをさらに備える［２４］に記載の方法。
［２６］ 前記ソース識別データを前記複数のソースデータ単位に関連付けることが、
前記複数のソースデータ単位の各々から集合Ｓを作成するステップと、
ｉ）Ｓのメンバの各々に関連付けられるハッシュされた出力を得るために、Ｓの各メンバにハッシュ関数Ｈ _ｉ を適用するステップであって、Ｈ _ｉ がＳの前記メンバの各々を可能なＬ個のハッシュ出力の１つに写像する、適用するステップと、
ｉｉ）前記ハッシュされた出力のどれが前記ハッシュされた出力に関連付けられた前記ソースデータ単位を一意に識別するかを判断するステップと、
ｉｉｉ）ハッシュされた出力がソースデータ単位を一意に識別すると判断された場合、Ｓから前記一意に識別されたソースデータ単位を除去し、前記ソース識別データからの識別データの適切なセットを前記一意に識別されたソースデータ単位に関連付けるステップと、
ｉｖ）前記ハッシュされた出力の１つが一意でないと判断された場合、Ｓが空集合になるまで、または最大回数の繰返しが実行し終わるまでステップｉ〜ｉｉｉを繰り返すステップであって、繰返しごとにＨ _ｉ が、Ｌの潜在的に異なる値を用いたステップｉ〜ｉｉｉの前の繰返し中に使用された前記ハッシュ関数とは異なるハッシュ関数である、繰り返すステップと、
を備える、［１６］に記載の方法。
［２７］ ステップｉ〜ｉｖの繰返しごとに適用される前記Ｈ _ｉ が前記ソース識別データから判断される［２６］に記載の方法。
［２８］ 前記ハッシュされた出力のどれが前記ハッシュされた出力に関連付けられた前記ソースデータ単位を一意に識別するかを判断するステップが、
各ハッシュされた出力を前記ソース識別データからのベクトルと比較することであって、前記ベクトルが前記可能なＬ個のハッシュ出力に対応し、前記ベクトルが、前記Ｌ個のハッシュ出力のどれが衝突を経験するか、および前記Ｌ個のハッシュ出力のどれがＳのメンバに一意に写像するかを示す、比較することを備える［２６］に記載の方法。
［２９］ 前記ソース識別データが位置とシーケンスとの対応を含み、前記ソース識別データからの識別データの適切なセットを前記一意に識別されたソースデータ単位に関連付けることが、前記位置とシーケンスとの対応からの所在情報を前記一意に識別されたソースデータ単位に関連付けることを備える［２８］に記載の方法。
［３０］ ソースデータ単位が前記ソース識別データからの識別データの適切なセットに関連付けられる場合、前記ソースデータ単位を復号器に渡すことをさらに備える［２６］に記載の方法。
［３１］ ソースデータ単位が前記ソース識別データからの識別データの適切なセットに関連付けられない場合、前記ソースデータ単位を廃棄することをさらに備える［２６］に記載の方法。
［３２］ ［１６］に記載の方法を実行するためのコードを備えるコンピュータ可読媒体。
［３３］ プロセッサと、前記プロセッサに結合された［３２］に記載のコンピュータ可読媒体とを備える受信機。

Claims (33)

1. ソースデータのソース識別データを生成し、送信するための方法であって、前記ソースデータが１よりも大きいＫ個のソースデータ単位に分割され、前記ソース識別データが他のソースデータ単位に対して相対的な当該ソースデータ単位の位置を特定し、損失または破損したソースデータ単位を特定するために使用することができる当該送信するための方法において、
   前記Ｋ個のソースデータ単位から前記ソース識別データを生成することと、
   第１のデータストリームを受信機に送信することであって、この第１のデータストリームが前記ソースデータ単位のセットから構成され、また、この第１のデータストリームが前記ソース識別データを有していないところの、当該第１のデータストリームを受信機に送信することと、
   第２のデータストリームを前記受信機に送信することであって、当該第２のデータストリームが前記ソース識別データで構成され、当該ソース識別データが前記第１のデータストリームで送信される前記ソースデータ単位のセットとは区別され、また、前記第１のデータストリームで送信される前記ソースデータ単位のセット内において、当該ソース識別データが当該ソースデータ単位を特定するに利用されるところの、前記第２のデータストリームを前記受信機に送信することと、
   を備える方法。
2. 前記ソース識別データが前記第１および第２のデータストリームの受信側に対して、前記ソース識別データを生成するに使用される前記Ｋ個のソースデータ単位の識別ラベルを判断可能とする請求項１に記載の方法。
3. 前記ソース識別データが前記第１および第２のデータストリームの受信側に対して任意のソースデータ単位の識別ラベルを判断可能とする請求項１に記載の方法。
4. 前記ソース識別データが前記第１および第２のデータストリームの受信側に対してすべての前記ソースデータ単位の順序付けに関して任意のソースデータ単位の位置を判断可能とする請求項１に記載の方法。
5. 前記ソース識別データが前記第１および第２のデータストリームの受信側に対してすべての前記ソースデータ単位のソース判断順序シーケンスに関して任意のソースデータ単位の位置を判断可能とする請求項１に記載の方法。
6. 前記第２のデータストリームが前記ソースデータ単位のリペアデータをさらに備える請求項１に記載の方法。
7. 前記第２のデータストリームが前記ソース識別データのリペアデータをさらに備える請求項１に記載の方法。
8. 前記第１のデータストリームがＤＶＢ−Ｔを介して送信され、前記第２のデータストリームがＤＶＢ−Ｈを介して送信される請求項１に記載の方法。
9. 前記受信機から追加のデータの要求を受信することと、
   前記受信機に第３のデータストリームを送信することと、
   をさらに備える請求項１に記載の方法。
10. 前記第３のデータストリームがソースデータ単位の第２のセットを備える請求項９に記載の方法。
11. 前記第３のデータストリームが前記ソースデータ単位のリペアデータを備える請求項９に記載の方法。
12. 前記Ｋ個のソースデータ単位からソース識別データを生成することが、
    前記Ｋ個のソースデータ単位の各々から順序集合Ｓを作成するステップと、
    ｉ）前記順序集合Ｓの各メンバにハッシュ関数Ｈｉを適用するステップであって、前記ハッシュ関数Ｈｉが前記順序集合Ｓの前記メンバを可能なＬ個のハッシュ出力の１つに写像し、前記ハッシュ関数Ｈｉが前記順序集合Ｓの前記メンバの少なくともＸ個を一意のハッシュ出力に写像するところの適用するステップと、
    ｉｉ）前記Ｌ個のハッシュ出力に対応するベクトルを作成するステップであって、前記ベクトルが、前記Ｌ個のハッシュ出力のどれが衝突を経験するか、および前記Ｌ個のハッシュ出力のどれが前記順序集合Ｓのメンバに独自に（一意に）写像するかを示すところの作成するステップと、
    ｉｉｉ）一意のハッシュ出力に写像しない前記順序集合Ｓの要素から構成される集合Ｓｉを作成するステップと、
    ｉｖ）前記集合Ｓｉが空集合になるまで、または最大回数の繰返しが実行し終わるまでステップｉ〜ｉｉｉを繰り返すステップであって、ステップｉ〜ｉｉｉの繰返しごとに前記集合Ｓｉが前記順序集合Ｓとして使用され、繰返しごとに前記ハッシュ関数Ｈｉが、ステップｉ〜ｉｉｉの前の繰返し中に使用された前記ハッシュ関数とは異なるハッシュ関数であり、繰返しごとにＬおよびＸの値が変化することができる、繰り返すステップと、
    ステップｉ〜ｉｉｉの各繰返し中に作成された前記ベクトルからソース識別データを生成するステップと
    を備える、請求項１に記載の方法。
13. 前記ベクトルが、Ｓの一意に写像された各メンバのＳ中の所在をさらに示し、前記方法が、
    ステップｉ〜ｉｉｉの各繰返し中に作成された前記ベクトルによって示されるようにＳの前記独自（一意）に写像されたメンバの前記所在から位置とシーケンスとの対応を生成すること、
    をさらに備える請求項１２に記載の方法。
14. コンピュータによって請求項１に記載の方法を実行するためのコードを備えるコンピュータ可読記憶媒体。
15. プロセッサを備えた前記コンピュータと、前記プロセッサに結合された請求項１４に記載のコンピュータ可読記憶媒体とを備える送信機。
16. ソース識別データを受信し、前記ソース識別データをソースデータに関連付ける方法であって、前記ソースデータが１よりも大きいＫ個のソースデータ単位に分割され、前記ソース識別データが他のソースデータ単位に対して相対的なソースデータ単位の位置を特定し、損失または破損したソースデータ単位を特定するために使用することができる当該方法において、
    第１のデータストリームから複数のソースデータ単位を受信することであって、この第１のデータストリームが前記ソース識別データを有していないところの、当該複数のソースデータ単位を受信することと、
    第２のデータストリームからソース識別データを受信することであって、当該第２のデータストリームが前記第１データストリームから区別されている当該ソース識別データを受信することと、
    前記第２のデータストリームからのパケットセットから得られる前記ソース識別データを前記第２のデータストリームからの前記パケットセットから区別される前記複数のソースデータ単位に関連付けることであって、当該ソース識別データが前記多数のソースデータ単位におけるソースデータ単位を特定するに利用することができるところの、前記複数のソースデータ単位に関連付けることと、
    を備える方法。
17. 前記受信された複数のソースデータ単位の識別ラベルを判断すること
    をさらに備える請求項１６に記載の方法。
18. 前記受信された複数のソースデータ単位のメンバではない任意のソースデータ単位に対する識別ラベルを判断すること
    をさらに備える、請求項１６に記載の方法。
19. すべての前記ソースデータ単位の順序付けに関して前記複数のソースデータ単位中のソースデータ単位の位置を判断すること、
    をさらに備える、請求項１６に記載の方法。
20. すべての前記ソースデータ単位のソース判断順序シーケンスに関して前記複数のソースデータ単位中のソースデータ単位の位置を判断すること、
    をさらに備える、請求項１６に記載の方法。
21. 前記第２のデータストリームから前記複数のソースデータ単位のリペアデータを受信すること
    をさらに備える、請求項１６に記載の方法。
22. 前記第２のデータストリームから前記ソース識別データのリペアデータを受信することをさらに備える、請求項１６に記載の方法。
23. 前記第１のデータストリームがＤＶＢ−Ｔを介して受信され、前記第２のデータストリームがＤＶＢ−Ｈを介して受信される請求項１６に記載の方法。
24. 前記Ｋ個のソースデータ単位のいずれかが受信されなかったかどうかを判断するために、前記ソース識別データおよび前記複数のソースデータ単位を分析することと、
    前記Ｋ個のソースデータ単位のいずれかが受信されなかった場合、追加のデータを要求することと
    をさらに備える請求項１６に記載の方法。
25. 第３のデータストリームから前記追加のデータを受信すること
    をさらに備える、請求項２４に記載の方法。
26. 前記ソース識別データを前記複数のソースデータ単位に関連付けることが、
    前記複数のソースデータ単位の各々から集合Ｓを作成するステップと、
    ｉ）前記集合Ｓのメンバの各々に関連付けられるハッシュされた出力を得るために、前記集合Ｓの各メンバにハッシュ関数Ｈｉを適用するステップであって、前記ハッシュ関数Ｈｉが前記集合Ｓの前記メンバの各々を可能なＬ個のハッシュ出力の１つに写像するところの適用するステップと、
    ｉｉ）前記ハッシュされた出力のどれが前記ハッシュされた出力に関連付けられた前記ソースデータ単位を一意に識別するかを判断するステップと、
    ｉｉｉ）ハッシュされた出力がソースデータ単位を一意に識別すると判断された場合、前記集合Ｓから前記一意に識別されたソースデータ単位を除去し、前記ソース識別データからの識別データの適切なセットを前記一意に識別されたソースデータ単位に関連付けるステップと、
    ｉｖ） 前記ハッシュされた出力の１つが一意でないと判断された場合、前記集合Ｓが空集合になるまで、または最大回数の繰返しが実行し終わるまでステップｉ〜ｉｉｉを繰り返すステップであって、繰返しごとに前記ハッシュ関数Ｈｉが、Ｌの潜在的に異なる値を用いたステップｉ〜ｉｉｉの前の繰返し中に使用された前記ハッシュ関数とは異なるハッシュ関数である、繰り返すステップと
    を備える、請求項１６に記載の方法。
27. ステップｉ〜ｉｖの繰返しごとに適用される前記ハッシュ関数Ｈｉが前記ソース識別データから判断される、請求項２６に記載の方法。
28. 前記ハッシュされた出力のどれが前記ハッシュされた出力に関連付けられた前記ソースデータ単位を一意に識別するかを判断するステップが、
    各ハッシュされた出力を前記ソース識別データからのベクトルと比較することであって、前記ベクトルが前記可能なＬ個のハッシュ出力に対応し、前記ベクトルが、前記Ｌ個のハッシュ出力のどれが衝突を経験するか、および前記Ｌ個のハッシュ出力のどれがＳのメンバに一意に写像するかを示すところの比較すること、
    を備える請求項２６に記載の方法。
29. 前記ソース識別データが位置とシーケンスとの対応を含み、前記ソース識別データからの識別データの適切なセットを前記一意に識別されたソースデータ単位に関連付けることが、前記位置とシーケンスとの対応からの所在情報を前記一意に識別されたソースデータ単位に関連付けることを備える請求項２８に記載の方法。
30. ソースデータ単位が前記ソース識別データからの識別データの適切なセットに関連付けられる場合、前記ソースデータ単位を復号器に渡すこと、
    をさらに備える、請求項２６に記載の方法。
31. ソースデータ単位が前記ソース識別データからの識別データの適切なセットに関連付けられない場合、前記ソースデータ単位を廃棄すること、
    をさらに備える請求項２６に記載の方法。
32. 請求項１６に記載の方法を実行するためのコードを備えるコンピュータ可読記憶媒体。
33. プロセッサと、前記プロセッサに結合された請求項３２に記載のコンピュータ可読記憶媒体とを備える受信機。

Images