説明

前方エラー訂正(FEC)符号およびストリーミング

【課題】データ符号化器において、符号化されるデータであるソースシンボルと欠落したソースシンボルに関する情報を再生するのに使用可能なリペアシンボルとを含む符号化データを生成する方法を提供する。
【解決手段】ソースシンボルからリペアシンボルへの符号化を表現する生成行列を取得する。ソースシンボルの少なくともいくつかを読み取る。ソースシンボルの少なくともいくつかを、順序付けられた複数のソースシンボル内のソースシンボルの順番に対応する符号化セット内の順番で符号化セットの符号化シンボルとして含める。ソースシンボルの並べ替えセットを形成するため、1以上の並べ替え規則のセットに従ってソースシンボルを並べ替える。リペアシンボルのセットを形成するため、ソースシンボルの並べ替えセットに生成行列を作用させる。符号化データとリペアシンボルのセットとして符号化セットを出力する。

【発明の詳細な説明】
【発明の技術分野】
【0001】
関連出願の相互参照
本願は、参照によってその全体が組み込まれている2005年6月10日出願の米国仮出願第60/689,333号の利益を主張し、その非仮出願である。
【0002】
本発明は、全般的にはFEC符号に関し、具体的にはストリーミングアプリケーション用のFEC符号に関する。
【発明の技術背景】
【0003】
最近、伝送中にストリーミングメディアを保護するのにFEC符号を検討することが、一般的な実践になってきた。パケットネットワークを介して送信される時に(パケットネットワークの例には、インターネットと、3GPP、3GPP2、およびDVBなどのグループによって標準化されたものなどの無線ネットワークとが含まれる)、ソースストリームは、生成される時または使用可能にされる時にパケットに配置され、したがって、パケットは、ソースストリームが生成される順序またはソースストリームが受信機から使用可能にされる順序でソースストリームを搬送するのに使用される。これらのタイプのシナリオへのFEC符号の通常の応用では、FEC符号は、ソースストリームを含むオリジナルのソースパケットに追加のリペアパケットを追加するのに使用され、これらのリペアパケットは、ソースパケット消失が発生する時に、受信されたリペアパケットを使用して、失われたソースパケットに含まれるデータを回復できるという特性を有する。他の例では、部分的なパケット消失が発生することが可能である、すなわち、受信機が、パケットの他の部分を受信しながらそのパケットの諸部分を失う場合があり、したがって、これらの例では、完全にまたは部分的に受信されたリペアパケットを使用して、完全にまたは部分的に失われたソースパケットを回復することができる。もう1つの例では、他のタイプの破損が、送信されたデータに対して発生する可能性があり、たとえば、ビットの値が反転される場合があり、したがって、リペアパケットを使用して、そのような破損を訂正し、ソースパケットのできる限り正確な回復をもたらすことができる。他の例では、ソースストリームを、必ずしも離散的パケットで送信するのではなく、その代わりに、たとえば連続的ビットストリームとして送信することができる。
【0004】
ソースストリームの保護を実現するのに使用できるFEC符号の多数の例がある。リードソロモン符号は、通信システムでのエラーおよび消去訂正のための周知の符号である。たとえばパケットデータネットワークでの消去訂正について、リードソロモン符号の周知の効率的実施は、”L.Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols", Computer Communication Review, 27(2):24-36(April 1997)”(以下”Rizzo”)、および、”Bloemer,ET AL., "An XOR-Based Erasure-Resilient Coding Scheme", Technical Report TR-95-48, International Computer Science Institute, Berkeley, California (1995)”(以下”XOR−Reed−Solomon”)に記載のコーシー行列またはバンデルモンド行列を使用することである。FEC符号の他の例には、その全体が本明細書に組み込まれている米国特許第6307487号(以下では”LubyI”)および米国特許出願第2003/0058958号(以下では”ShokrollahiI”)に記載のものなどのLDPC符号、連鎖符号、およびマルチステージ連鎖符号が含まれる。
【0005】
リードソロモン符号の変形に関するFEC復号化処理の例が、”Rizzo”および”XOR−Reed−Solomon”に記載されている。これらの例では、復号化は、十分なソースデータパケットおよびリペアデータパケットが受信されたならば、適用される。復号化処理は、計算集中型である場合があり、使用可能なCPUリソースに応じて、ブロック内のメディアがまたがる時間の長さに対して、相対的に、完了にかなりの時間を要する場合がある。受信機は、メディアストリームの受信の始まりとそのメディアの再生との間に必要な遅延を計算する時に、復号化に必要なこの時間の長さを考慮に入れなければならない。復号化に起因するこの遅延は、特定のメディアストリームに関するユーザの要求と再生の始まりとの間の遅延としてユーザによって知覚される。したがって、この遅延を減らすことが望ましい。
【0006】
多くのアプリケーションで、パケットは、シンボルにさらに副分割され、このシンボルに、FEC処理が適用される。シンボルは、任意のサイズとすることができるが、しばしば、シンボルのサイズは、多くともパケットのサイズと等しい。以下では、我々は、符号化ブロックを含むシンボルを”ソースシンボル”と呼び、FEC処理中に生成されるシンボルを”符号シンボル”と呼ぶ。一部のFEC符号、特にリードソロモン符号について、符号化時間および復号化時間は、ソースブロックあたりの符号シンボルの個数が増えるにつれて、非実用的に増大する。したがって、実際には、ソースブロック当たりに生成できる符号シンボルの総数に対する上限、たとえば255個が、しばしば存在する。シンボルは、別々のパケットペイロードに配置されるので、これは、ソースブロックの符号化での最大長に対する実用的上限を設け、たとえば、パケットペイロードが多くとも1024バイトである場合に、符号化されたソースブロックは、多くとも255KB(キロバイト)であり、これは、もちろん、ソースブロック自体のサイズに関する上限でもある。
【0007】
ソースストリーミングレートについて行くのに十分に高速のソースブロックを復号化できること、FEC復号化によって導入される復号化待ち時間を最小化することができること、およびFEC復号化中の任意の時点に受信デバイスで使用可能なCPUの小さい割合だけを使用することなどの他の考慮事項が、問題である。
【0008】
したがって、改善された処理および装置を有することが望ましい。
【発明の概要】
【0009】
本発明の実施形態は、FEC符号化されたソースブロックからのパケットの受信と同時に、復号化に付随する計算の重要な部分を実行する方法を提示する。したがって、復号化遅延、すなわち、ソースブロックの最後のパケットの受信の後、回復されたソースブロックが使用可能になる前の遅延は、計算の残りの部分を実行するのに必要な時間まで減らされ、この計算の残りの部分は、一般に、復号化作業全体の小さい分数である。
【0010】
いくつかの実施形態で、符号化器からチャネルを介して受信されるシンボルからデータを復号化するデータ復号化器が使用され、ここで、受信されたデータには、消去が含まれる可能性があり、ソースシンボルおよびリペアシンボルが含まれ、この復号化器は、復号化において、生成行列すなわち、可逆である任意の正方行列を使用し、復号化器が、ソースシンボルおよびリペアシンボルの到着と同時に復号化動作を実行できるようになっており、少なくとも部分的に生成行列から導出される連立方程式を復号化器メモリ内で表すことと、すべてのソースシンボルを受信する前に、ソースシンボルが受信される時に、受信されたソースシンボルを連立方程式に代入することと、復号化器論理を使用して、リペアシンボルが到着する時に、連立法的式を解くのに使用されるリペア式を識別することと、復号化器論理を使用して、ソースシンボルが到着する時に、式のベクトル値を計算することと、リペアシンボルが復号化器に到着する時に連立方程式を上三角形式に変換することとを含む方法が、提供される。
【0011】
いくつかの実施形態で、利益を得るために2Dリードソロモン符号と他の関連する符号とをインターリーブする新規の方法が使用される。いくつかの実施形態は、FEC符号の大きいクラスの符号化構造を指定する、新規の一般的な簡潔な機構を使用することができる。
【0012】
諸実施形態は、ソースブロックのパケットの送信をスケジューリングする新規の方法をも提示する。この方法の利益の一部には、FECエンドツーエンド待ち時間の最小化、FEC受信機待ち時間の最小化、FEC符号化されるストリームのできる限り滑らかなレートでの伝送、ソースブロックのパケットで送信されるデータの時間にまたがるできる限り均一な拡散、およびFEC受信機での単純な論理要件が含まれる。
【0013】
諸実施形態は、ソースブロックをインターリーブする新規の方法をも提示する。これは、個々のソースブロック内での伝送における消失またはエラーを、インターリーブが使用されない場合よりはるかに長い時間期間にわたって拡散させることを可能にし、受信機によって知覚される復号化待ち時間を最小値まで減らしながら、ソースデータのオリジナルの送信順序をも維持することを可能にする。
【0014】
次の詳細な説明は、添付図面と一緒に、本発明の性質および利点のよりよい理解をもたらす。
【図面の簡単な説明】
【0015】
【図1】本発明の一実施形態による通信システムを示すブロック図である。
【図2】受信機遅延を示す図である。
【図3A】受信機遅延の成分を例示する図である。
【図3B】復号化中のFECに関するCPU使用率を例示する図である。
【図4】本発明の一実施形態に従って使用可能な復号化行列の例を示す図である。
【図5】本発明の一実施形態による復号化処理の一部を示すフローチャートである。
【図6】本発明の一実施形態による復号化処理の一部を示すもう1つのフローチャートである。
【図7】復号化ステップのうちの1つの、変形形態を示すフローチャートである。
【図8A】ソースブロックの処理の異なるフェーズを示す図である。
【図8B】連続するソースブロックの処理の異なるフェーズの間の関係を示す図である。
【図9】FEC送信機のソース初期処理を示すフローチャートである。
【図10】FEC送信機のソース中間処理を示すフローチャートである。
【図11】FEC送信機のソース最終処理を示すフローチャートである。
【図12】FEC送信機のソースリペア処理を示すフローチャートである。
【図13】FEC送信機に関するフローチャートである。
【発明を実施するための形態】
【0016】
本明細書で説明する実施形態は、復号化遅延を減らすためのFEC符号化されたソースブロックからのパケットの受信と同時の復号化など、ネットワークまたは類似物を介して受信されたデータの復号化を実行する新規の方法を提供する。以下では、本明細書で説明する処理および方法を連続ビットストリームネットワークなどの他のタイプの伝送ネットワークにどのように適用できるかを当業者が簡単に理解できることを認識して、データを搬送するネットワークを、本明細書での説明を単純にするためにパケットベースであると仮定する。以下では、本明細書で説明する処理および方法をビット反転などの他のタイプのデータ伝送破損にどのように適用できるかを当業者が簡単に理解できることを認識して、本明細書での説明を単純にするために、FEC符号が、失われたパケットまたはパケット内の失われた部分的データに対する保護をもたらすと仮定する。
【0017】
図1は、連鎖符号を使用する通信システム100のブロック図である。通信システム100内では、入力ファイル101または入力ストリーム105が、入力シンボル生成器110に供給される。入力シンボル生成器110は、入力ファイルまたは入力ストリームから1つまたは複数の入力シンボルのシーケンス(IS(0),IS(1),IS(2),...)を生成し、各入力シンボルは、値および位置を有する(図1では、括弧に囲まれた整数として示す)。入力シンボルの可能な値すなわち入力シンボルのアルファベットは、
通常、2個のシンボルのアルファベットであり、その結果、各入力シンボルは、入力ファイルのMビットについて符号化するようになる。Mの値は、一般に、通信システム100の用途によって決定されるが、汎用システムは、入力シンボル生成器110に関するシンボルサイズ入力を含むことができ、その結果、Mを、用途ごとに変更することができるようになる。入力シンボル生成器110の出力は、符号化器115に供給される。
【0018】
キー生成器120は、符号化器115によって生成される出力シンボルごとにキーを生成する。各キーは、LubyIまたはShokrollahiIに記載の方法のうちの1つ方法に従って、または、キーが、このキー生成器もしくは別のキー生成器のどちらによって生成されるのであれ、同一の入力ファイルについてまたは1つのストリーム内のデータの同一のブロックについて生成されるキーの大きい分数が一意であることを保証する任意の匹敵する方法に従って、生成することができる。たとえば、キー生成器120は、カウンタ125の出力、一意ストリーム識別器130、および/または乱数生成器135の出力の組合せを使用して、各キーを作ることができる。キー生成器120の出力は、符号化器115に供給される。他の例、たとえば一部のストリーミングアプリケーションでは、キーの組を、固定し、ストリーム内のデータのブロックごとにもう一度再利用することができる。通常の実施形態では、生成できるキーの個数は、入力ファイルまたはストリームのサイズまたは他の特性ではなく、キー生成器の分解能によって示される。たとえば、入力が、1万個以下程度のシンボルになると期待される場合に、キー分解能は、32ビットとすることができ、これは、40億個までの一意のキーを可能にする。これらの関連する数の結果の1つは、キーに従って符号化する符号化器を、入力の1万個のシンボルについて40億個の一意の出力シンボルを生成できるものとすることができることがである。現実的な問題として、ほとんどの通信システムは、400000個のシンボルのすべてではなくそのうちの1つだけを失い、したがって、40億個もの出力シンボルを生成する必要はなく、したがって、可能なキーの個数は、効果的に無制限として扱うことができ、繰り返される必要はなく、キーの2つの独立の選択が同一のキーをつかむ可能性は、ほとんどないほどに小さい。しかし、なんらかの理由でそうなる場合には、キー生成器の分解能を高めることができ、その結果、キーを使用する処理は、キーの終りのない供給があるかのように振る舞うことができるようになる。
【0019】
キー生成器120によって供給される各キーIから、符号化器115は、入力シンボル生成器によって供給される入力シンボルからの、値B(I)を有する出力シンボルを生成する。各出力シンボルの値は、そのキーと、本明細書で出力シンボルの”付随する入力シンボル”または単に出力シンボルの”付随物(associates)”と称する、入力シンボルのうちの1つまたは複数のある関数とに基づいて生成される。必ずではないが通常、Mは、入力シンボルおよび出力シンボルについて同一である、すなわち、これらの両方が、同一ビット数について符号化する。
【0020】
いくつかの実施形態で、入力シンボルの個数Kは、符号化器によって、付随物を選択するのに使用される。入力がストリームであり、Kがそのストリーム内の各ブロックの間で変化し得る場合など、Kが、前もっては知られない場合には、Kを、単に推定値とすることができる。値Kが、符号化器115によって、入力シンボルのストレージを割り振るのに使用される場合もある。
【0021】
符号化器115は、送信モジュール140に出力シンボルを供給する。送信モジュール140は、キー生成器120から各そのような出力シンボルのキーをも供給される。送信モジュール140は、出力シンボルを送信し、使用されるキーイング方法に応じて、送信モジュール140は、送信される出力シンボルのキーに関するあるデータをも、チャネル145を介して受信モジュール150に送信することができる。チャネル145は、消去チャネルであると仮定されるが、これは、通信システム100の正しい動作の要件ではない。モジュール140、145、および150は、送信モジュール140が、出力シンボルおよびそのキーに関するすべての必要なデータをチャネル145に送信するように適合され、受信モジュール150が、シンボルおよび潜在的にそのキーに関するいくつかのデータをチャネル145から受信するように適合される限り、任意の適切なハードウェア構成要素、ソフトウェア構成要素、物理媒体、またはその任意の組合せとすることができる。Kの値が、付随物を判定するのに使用される場合に、Kの値を、チャネル145を介して送信することができ、あるいは、符号化器115および復号化器155の合意によって前もってセットすることができる。
【0022】
チャネル145は、インターネットを介する経路、テレビジョン送信機からテレビジョン受信側への放送リンク、またはある地点から別の地点への電話接続などのリアルタイムチャネルとすることができ、あるいは、チャネル145は、CD−ROM、ディスクドライブ、ウェブサイト、または類似物などのストレージチャネルとすることができる。チャネル145は、ある人がパーソナルコンピュータから電話回線を介してインターネットサービスプロバイダ(ISP)に入力ファイルを送信し、その入力ファイルがウェブサーバに格納され、その後にインターネットを介して受信側に送信される時に形成されるチャネルなど、リアルタイムチャネルおよびストレージチャネルの組合せとすることさえできる。
【0023】
チャネル145が、パケットネットワークを含む場合に、通信システム100は、任意の複数のパケットの相対順序が、チャネル145を介する移動中に保存されると仮定することができない場合がある。したがって、出力シンボルのキーは、上で説明したキーイング方式のうちの1つまたは複数を使用して判定され、必ずしも出力シンボルが受信モジュール150を出る順序によって決定されるのではない。
【0024】
受信モジュール150は、出力シンボルを復号化器155に供給し、受信モジュール150が受信する、これらの出力シンボルのキーに関するすべてのデータが、キー再生器160に供給される。キー再生器160は、受け取った出力シンボルのキーを再生し、これらのキーを復号化器155に供給する。復号化器155は、キー再生器160によって供給されたキーを、対応する出力シンボルと一緒に使用して、入力シンボル(やはりIS(0),IS(1),IS(2),...)を回復する。復号化器155は、回復されたシンボルを入力ファイル再組立器165に供給し、入力ファイル再組立器165は、入力ファイル101のコピー170または入力ストリーム105のコピー175を生成する。
【0025】
メディアストリーミングアプリケーション
メディアストリーミングアプリケーションで使用される時に、ソースメディアストリームを形成するソースパケットは、時々、ソースブロックと呼ばれるグループに集められる。たとえば、ソースブロックを、固定された長さの時間にまたがるソースパケットのグループとすることができ、リードソロモン消去符号を、ソースブロックのオリジナルのソースパケットと一緒に受信機に送信されるリペアパケットを生成するために、これらのソースブロックに独立に適用することができる。
【0026】
送信機では、ソースストリームは、ソースパケットが到着する時にソースブロックに連続して区分され、その後、リペアパケットが、ソースブロックごとに生成され、送信される。特に生のまたは対話型のストリーミングアプリケーションについて、FEC符号の使用によって追加される総エンドツーエンド遅延を最化にすることが好ましく、したがって、FEC解決策の全体的設計が、ソースパケットが送信の前に送信機でできる限り短く遅延され、あるソースブロックのすべてのソースパケットおよびリペアパケットが、できる限り短い総遅延で送信されるものになっているならば、好ましい。また、FEC符号化されたストリームのレートが、できる限り滑らかである、すなわち、FEC符号化されたストリームレートにできる限り少ない変動性がある、または少なくともオリジナルのソースストリームに既に存在するどの変動性の増幅も存在しないならば、好ましい。というのは、これが、FEC符号化されたストリームの帯域幅使用量をより予測可能にし、ネットワークおよび他のおそらくは競合するストリームに対する影響を最小化するからである。また、あるソースブロックのパケット内で送信されるデータが、パケットがそのソースブロックについて送信される期間にわたってできる限り均一に拡散されることが好ましい。というのは、これが、バースト消失に対する最良の保護をもたらすからである。また、受信機のFEC論理が、できる限り単純である、すなわち、複数のソースブロックからのパケットの同時受信をできる限り回避するならば、好ましい。したがって、FEC送信機が、できる限り、あるソースブロックからのすべてのパケットを、後続ソースブロックからのパケットを送信する前に送信することが好ましい。
【0027】
受信機では、パケットが失われるか、エラー(たとえばCRC検査を使用して、検出し、破棄することができる)を伴って受信される場合に、十分なリペアパケットが受信済みであると仮定すると、それらのリペアパケットを使用して、失われたソースパケットを回復することができる。
【0028】
いくつかのアプリケーションで、パケットは、さらに、シンボルに副分割され、これらのシンボルに、FEC処理が適用される。いくつかのFEC符号、特にリードソロモン符号について、符号化時間および復号化時間は、ソースブロックあたりの符号シンボルの個数が増えるにつれて非現実的に増え、しばしば、ソースブロックあたりに生成できる符号シンボルの総数に対する上限がある。シンボルは、異なるパケットペイロードに配置されるので、これは、ソースブロックの符号化での最大長に対する実用的上限を設け、これは、もちろん、ソースブロック自体のサイズに対しても上限を設ける。
【0029】
多くのアプリケーションについて、保護が、長い時間期間にわたって提供されなければならないとき、またはメディアストリーミングレートが高いときには、最大ソースブロックサイズを超える、データに対する保護を提供することが有利でありえる。この場合に、最大ソースブロックサイズより短いソースブロックを使用し、その後、異なるソースブロックからのソースパケットをインターリーブすることによって、個々のソースブロックからのソースパケットがより長い時間期間にわたって拡散される解決策がもたらされる。
【0030】
しかし、もう1つの関心事は、ソースストリーミングレートについて行くのに十分に高速にソースブロックを復号化でき、FEC復号化によって導入される復号化待ち時間を最小化でき、FEC復号化中のどの時点においても受信するデバイスで使用可能なCPUの小さい分数だけを使用できることである。さらに、ソースパケットのオリジナルの送信順序を変更しないことが重要である。したがって、ソースパケットのオリジナルの送信順序を尊重し、各ソースブロックのFEC復号化を時間にわたってできる限り均等に拡散することを可能にし、FEC復号化待ち時間を最小化する、ソースブロックインターリービングを使用することが望ましい。本明細書で説明するさまざまな実施形態は、これらの利点のうちの1つまたは複数を実現する。
【0031】
用語
FEC符号
この説明では、符号化されるデータ(ソースデータ)が、等しい長さの”シンボル”に分解されており、シンボルは、任意の長さ(単一ビットまで)とすることができる。シンボルは、データネットワークを介してパケット内で搬送することができ、シンボルの総数は、各パケット内で明示的に搬送されるか、暗示される。いくつかの場合に、ソースパケットがシンボル長の倍数ではないことが可能であり、その場合に、パケット内の最後のシンボルを切り詰めることができる。この場合に、FEC符号において、この最後のシンボルは、ビットの固定パターン、たとえば0の値のビットによってパディングされると暗黙のうちに仮定され、その結果、これらのビットはパケット内で搬送されないが、受信機は、それでも、この最後の切り詰められたシンボルを完全なシンボルに充填することができるようになる。他の実施形態では、ビットの固定パターンをパケット内に配置することができ、これによって、効果的に、シンボルが、パケットの長さと等しい長さまでパディングされる。シンボルのサイズは、しばしば、ビット単位で測定され、シンボルは、Mビットのサイズを有し、シンボルは、2個のシンボルのアルファベットから選択される。非2進数字も企図されているが、2進ビットは、より一般的に使用されているので好ましい。
【0032】
本明細書でストリーミングについて検討されるFEC符号は、通常は、組織的FEC符号である、すなわち、ソースブロックのソースシンボルは、ソースブロックの符号化の一部として含められ、したがって、ソースシンボルが、送信される。次に、組織的FEC符号は、ソースシンボルのソースブロックから、ある個数のリペアシンボルを生成し、次に、ソースシンボルおよびリペアシンボルの組合せが、そのソースブロックについて送信される符号シンボルである。FEC符号の一部は、必要な個数のリペアシンボルを効率的に生成する能力を有する。そのような符号を、”情報付加的符号”および”ファウンテン符号”と称し、これらの符号の例には、”連鎖符号”および”マルチステージ連鎖符号”が含まれる。リードソロモン符号などの他のFEC符号は、実用的には、限られた個数のリペアシンボルを生成することしかできない。
【0033】
パケット内でシンボルを搬送する多数の他の方法があり、下の説明では、説明を単純にするためにこの例を使用するが、下の説明は、限定的または網羅的であることを意図されてはいない。下の説明の文脈では、用語”パケット”が、文字どおりにデータの単一の単位として送信されるものを意味することに制限されることは意図されていない。そうではなく、用語”パケット”は、データの単一の単位として送信されてもされなくてもよい、シンボルおよび部分的シンボルの論理グループ化を定義するというより広い概念を含むことが意図されている。
【0034】
シンボルの消失以外の形のデータの破損、たとえば、伝送中にその値が変化するか他の形で破損されるシンボルもあるが、下で説明される方法は、これらにも同等に適用される。したがって、下の説明では、しばしば、シンボルの消失を説明するが、この方法は、他のタイプの破損およびFECエラー訂正符号などのFEC消去符号を超えた他のタイプのFEC符号に同等に良好に適用される。
【0035】
線形変換
ある種の構成および例を示すために、環という数学的概念を利用する。当業者に周知の通り、環は、2つの演算すなわち加算および乗算が定義され、これらの演算が分配法則を満足するようになっている集合である。さらに、加算だけについて検討される集合は、アーベル群を形成する、すなわち、加算の結果は、被加数の順序付けと独立であり、加算の単位元0があり、要素ごとに、その要素との和が0になるもう1つの要素がある。他の要件は、乗算が単位元1を有し、1との任意の要素の乗算が、その要素の値を変更しないようになっていることである。一般的な環について、非0要素が逆数を有することは要求されず、乗算が可換であることも要求されない。しかし、これらの条件の両方が満足されるときに、その環を”体”と呼ぶ。この表記法は、代数の分野で標準的な表記法である。
【数1】

【0036】
シンボルに作用する環または体の例は、豊富にある。少数の例に、下で言及する。この例のリストは、例示のみを意図されており、網羅的なリストと考えてはならず、本発明の範囲を限定するものと解釈してもならない。
【0037】
例として、0および1からなり、排他的論理和(XOR)である加算および論理演算ANDである乗算を有する体GF(2)は、1*S=Sおよび0*S=0を定義することによってシンボルの集合に作用し、ここで、Sは、任意のシンボルを表し、0は、完全に0からなるシンボルを表す。
【0038】
”線形変換”という概念およびこの処理の行列定式化は、シンボルの環の演算という概念を参照して定義することができる。所与の整数kおよびnについて、この演算によって導入される線形変換は、指定された環に含まれる要素を有する行列の空間を使用して、k個のシンボルのベクトルをn個のシンボルのベクトルに写像する。環R上の行列は、項目の2次元集合であり、各項目は、Rに属する。ある行列が、n行k列を有する場合に、その行列を、一般にn×k行列と称する。ペア(n,k)を、その行列の”フォーマット”と呼ぶ。同一のフォーマットの行列は、基礎になる体または環の加算および減算を使用して、加算し、減算することができる。フォーマット(n,k)の行列は、一般に知られている通り、フォーマット(k,m)の行列と乗算することができる。
【0039】
演算において、Mがそのようなn×k行列を表し、M[i,j]が、位置(i,j)のMの項目を表し、この行列がベクトル(S,S,...,S)をベクトル(E,E,...,E)に変換する場合に、式1に示された関係は、有効である。
【数2】

【0040】
そのような線形変換は、さまざまなアプリケーションで平凡である。たとえば、ソースブロックを符号化するのに線形FEC符号を使用する時に、Sを、符号化されるソースブロックのソースシンボルとすることができ、Eを、ソースブロックについて送信される、Sから生成された符号シンボルとすることができ、Mを、FEC符号に関する生成行列とすることができる。他のアプリケーションでは、たとえば、組織的FEC符号が使用される場合に、Eを、Sから生成されたリペアシンボルとすることができ、Mを、ソースシンボルに対するリペアシンボルの依存性を記述する行列とすることができる。もう1つのアプリケーションでは、Sを、変換の後に受け取られる符号シンボルのベクトルとすることができ、Eは、完全に未知または部分的に未知のいずれかであるソースシンボルの集合に対応することができ、Mは、EとSとの間の関係を記述することができる。これらの例には、消去にもかかわらずまたはエラーにもかかわらずリードソロモン符号を復号化する場合が含まれる。後者は、Shokrollahi他の米国特許第6631172号、名称”Efficient List Decoding of Reed-Solomon Codes for Message Recovery in the Presence of High Noise Levels”に記載されている。
【0041】
組織的リードソロモン符号の行列定式化は、ソースシンボルおよびリペアシンボルの中で成り立つ連列方程式の組を表す。具体的に言うと、各式は、リペアシンボルの場合にはソースシンボルの線形組合せとして、ソースシンボルの場合には恒等式として、符号シンボルを表す。したがって、ソースシンボルおよびリペアシンボルと正確に同一の個数の式がある。
【0042】
本明細書で説明する方法および処理は、リードソロモン符号または他のFEC消去符号もしくはFECエラー訂正符号の他の定式化に同等に適用される。
【0043】
ストリーミング
ソースストリームのFEC保護をもたらすために、ソースストリームを、1つまたは複数の論理ストリームの組合せとすることができ、その例は、オーディオRTPストリームおよびビデオRTPストリームの組合せ、MIKEYストリームおよびRTPストリームの組合せ、複数のビデオストリームの組合せ、ならびに制御RTCPトラフィックおよびRTPストリームの組合せである。ソースストリームが、たとえばソースビットストリーム、ソースシンボルストリーム、またはソースパケットストリームである、あるフォーマットでFEC送信機に到着する時に、FEC送信機は、そのストリームをソースブロックにバッファリングし、ソースブロックからリペアストリームを生成することができる。FEC送信機は、ソースストリームおよびリペアストリームをスケジューリングし、たとえばパケットネットワークを介して送信されるパケット内で、送信する。FEC符号化されたストリームは、組み合わされたソースストリームおよびリペアストリームである。FEC受信機は、FEC符号化されたストリームを受信し、このFEC符号化されたストリームは、たとえば消失またはビット反転に起因して、破損されている場合がある。FEC受信機は、ソースストリームのオリジナルのソースブロックを再構成することを試み、その受信機でオリジナルソースストリームをスケジューリングし、使用可能にする。
【0044】
ストリーミングアプリケーションについて、ソースストリームを保護するのにFEC符号をどのように使用するかの設計に対する入力である複数のキーパラメータと、通常は最適化することが重要な複数のキーメトリックとがある。
【0045】
設計における2つのキー入力パラメータは、保護期間および保護量である。あるソースブロックの送信機保護期間とは、ソースブロックから生成されたシンボルがその間に送信される時間の持続時間である。あるソースブロックの保護量とは、そのソースブロック内のソースシンボルの個数の分数またはパーセンテージとして表される、そのソースブロックに関して送信されるFECリペアシンボルの個数である。たとえば、保護期間が2秒であり、保護量が20%であり、ソースブロックに10000個のソースシンボルがある場合に、そのソースブロックに関する10000個のソースシンボルおよび2000個のリペアシンボルが、2秒の時間のウィンドウにまたがって拡散されて送信される。
【0046】
ソースブロックあたりの保護期間と保護量との両方を、ソースブロックごとに変更することができる。たとえば、ソースブロックが、ソースストリーム内のある種のソースパケットの間にまたがらないことが好ましい時、たとえば、第1パケットがMPEG2ビデオストリーム内のグループオブピクチャ(GOP)の最後のパケットであり、第2の連続するパケットが、次のGOPの最初のパケットである時に、ソースブロックを、第1パケットの後、第2パケットの前に打ち切ることができ、この打切りは、これが保護期間の終りの前に発生する場合であっても行うことができる。これによって、FEC保護ブロックをビデオ符号ブロックと整列させることが可能になり、これは、ビデオバッファリングおよびFECバッファリングに起因する受信機待ち時間を最小化できるという利点を含む、多数の利点を有することができる。他のアプリケーションでは、さまざまな理由から、各連続するソースブロックについて同一の保護期間および/または同一のソースブロックサイズを必ず維持することが有利である可能性がある。下の説明の多くでは、説明を単純にするために、保護期間と保護量との両方が、各連続するソースブロックについて同一であると仮定する。これが限定的ではないことは、この開示を読んだ後に当業者に明白であろう。というのは、この開示を読んだならば、保護量または保護期間のいずれかあるいはその両方がソースブロックごとに変化する場合およびソースブロックサイズがソースブロックごとに変化する場合にも、本明細書で説明される処理および方法がどのように適用されるかを簡単に判定できるからである。
【0047】
後続の議論の一部を単純にするために、オリジナルストリームのソースシンボルが、安定したレートでFEC符号化を実行しなければならないFEC送信機に到着し、そのFEC送信機が、まずソースシンボルを受信機で使用可能にしたならば、そこからソースシンボルが受け取られる第1ソースブロックに、ソースシンボル消失がなく、各後続ソースブロックで、符号シンボル消失が、多くとも成功のFEC復号化を可能にするために可能な最大値であると仮定して、後続ソースシンボルが、同一の安定したレートでFEC受信機によって使用可能にされるとしばしば仮定する。この単純にする仮定は、この後で説明する処理および方法の動作または設計に固有ではなく、いかなる形でもこれらの処理をこの仮定に限定することは意図されておらず、単に、この処理および方法の特性の説明の一部を単純にするための道具として導入されるものである。たとえば、可変レートストリームについて、対応する条件は、ソースシンボルが、FEC送信機に到着するのと同一のレートまたはそれと同一に近いレートでFEC受信機によって使用可能にされることである。
【0048】
最小化することが重要ないくつかのキーメトリックには、FEC送信機待ち時間が含まれ、このFEC送信機待ち時間は、FEC送信機によって導入される待ち時間である。FEC送信機待ち時間の最小化は、生のビデオストリームなど一部のアプリケーション、またはビデオ会議などの対話型アプリケーションに望ましい。FEC送信機待ち時間を最小化するのを助ける全体設計の一態様は、FEC送信機が、ソースシンボルがそのFEC送信機に到着するのと同一の順序でソースシンボルを送信することである。FEC送信機待ち時間を最小化する他の設計態様は、後に説明する。
【0049】
もう1つの重要なメトリックが、FEC受信機待ち時間である。図2に示されているように、これは、受信機がストリームに参加するかストリームを要求し、そのストリームからの符号シンボルの受信を初めて開始する時と、そのFEC受信機がそのストリームからのソースシンボルを初めて使用可能にする時との間の時間である。一般に、FEC受信機待ち時間を最小化することが望ましい。というのは、これが、FEC受信機によって復号化され、渡される前にシンボルを記憶するための、その受信機でのメモリ要件を最小化し、また、ストリームに参加する時と、たとえばビデオストリームの再生のために、そのストリームが始めて使用可能になり始める時との間の時間の長さを最小化するからである。FEC受信機待ち時間を最小化する1つの重要な態様は、FEC送信機がソースシンボルのオリジナルの送信順序を維持することであるが、下で説明するように、FEC受信機待ち時間に対する大きい影響を有する多数の他の重要な設計態様がある。
【0050】
FEC受信機待ち時間は、通常は複数の成分を含む。シーケンシャルソースブロックに区分されたストリームのこれらの成分の例を、図3Aおよび3Bに示す。図3Aには、保護期間あたり単一のソースブロックが示されており、この例は、受信機がソースブロックの始めにストリームに参加する場合を示す。この例でのFEC受信機待ち時間の2つの成分は、保護期間および復号化待ち時間である。受信機保護待ち時間は、その間にFEC受信機がソースブロックからの受信符号シンボルをバッファリングしている時間である。送信機保護期間および受信機保護期間は、送信機と受信機との間のチャネルが、各ビット、バイト、シンボル、またはパケットが送信機から受信機まで移動するのに要する時間に関して変動を全く有しない場合に、同一であることに留意されたい。したがって、実際には、送信機保護期間は、配送におけるネットワークタイミング変動に起因して、同一のソースブロックに関して受信機保護期間と異なる場合がある。
【0051】
本明細書での例示を単純にするために、以下では、送信機保護期間および受信機保護期間が各ソースブロックについて同一であると仮定し、用語”保護期間”を、送信機保護期間および受信機保護期間について同義に使用する、すなわち、ネットワーク配送時間が、すべてのデータについて同一であると仮定するが、当業者が、この開示を読んだ後に、ネットワーク配送変動に起因する送信機保護期間と受信機保護期間との差を考慮に入れるために、本明細書に記載の方法および装置に対して必要な変更を行うことができることに留意されたい。
【0052】
FEC受信機待ち時間の保護期間成分は、不可避である。というのは、最初のソースブロックにソースシンボルの消失が全くない場合であっても、それでも、後続ソースブロックに符号シンボルの消失がある時にすべての後続ソースシンボルの滑らかなソースシンボル配送を保証するために、ソースシンボルを少なくとも保護期間の間に使用可能にするために遅延しなければならないからである。保護期間中に、ソースブロックのFEC復号化の一部、ほとんど、またはすべてを、符号シンボルの受信と同時に行っているものとすることができる。保護期間の終りに、ソースブロックの最初のソースシンボルがFEC受信機から使用可能になる前に行われる、追加のFEC復号化がある場合があり、この時間期間は、図3Aでは、復号化待ち時間としてラベルを付けられている。さらに、最初のソースシンボルが使用可能になった後であっても、ソースブロックの第2のおよび後続のソースシンボルが使用可能になる前に行われる、追加のFEC復号化がある場合がある。図を単純にするために、この追加のFEC復号化は、図3Aには示されておらず、この例では、最初のソースシンボルの後のすべてのソースシンボルを十分に速いレートで復号化するのに十分な使用可能なCPUリソースがあると仮定する。
【0053】
図3Bに、図3Aに示された例に対応するものとすることができる、2つの潜在的なFEC復号化CPU利用度曲線を示す。図3Bに示された2つの曲線の一方では、FEC復号化に使用されるCPU利用度が、各時点で同一である、すなわち、CPU利用度は、均等に分散されている。これは、望ましいCPU利用度曲線である。というのは、これによって、各時点で同一量のCPUリソースが予測可能に使用され、総CPUリソースのうちの同一量がソースブロック全体を復号化するのに必要になると仮定して、最大CPUリソースが最小化されるからである。図3Bに示された2つの曲線の他方では、FEC復号化に使用されるCPU利用度が、各時点で同一ではなく、具体的には、ソースブロックの符号シンボルの受信の終りに向かっておよびその直後のCPU利用度は、他の時点よりかなり高い。これは、望ましいCPU利用度曲線ではない。というのは、CPUリソース使用が、ある時点で急上昇し、この時点が、ビデオプレイヤなどの他の処理もCPUに要求を行う時点である可能性があり、したがって、たとえばビデオストリームの再生におけるグリッチを引き起こす可能性が高まるからである。したがって、ストリームの保護に関するFEC解決策の設計は、FEC符号化器が経時的にできる限り滑らかに均一にCPUを使用する解決策を提供することである。例として、設計判断基準を、符号シンボル消失のワーストケースパターンの下でのFEC復号化処理の任意の時点での最大CPU利用度が、ある閾値未満であり、たとえば、多くともCPUの10%を使用することとすることができる。
【0054】
受信機が、たまたまソースブロックの途中でストリームに参加するときには、ソースパケットのオリジナルの送信順序がFEC送信機によって維持される限り、FEC受信機待ち時間を、保護期間と、最初の部分的ソースブロックからのソースシンボルの消失がない時の復号化待ち時間との合計ほどに短くすることができる。したがって、FEC送信機が、ソースシンボルのオリジナルの送信順序を維持することが望ましい。
【0055】
FECストリーミング解決策は、FECエンドツーエンド待ち時間を最小化するのにも使用することができ、このFECエンドツーエンド待ち時間は、ソースパケットがFEC符号化が適用される前に送信機でストリーミングの準備ができた時とソースパケットがFEC復号化が適用された後に受信機で再生に使用可能になる時との間のFECの使用によって導入されるワーストケース総待ち時間である。
【0056】
FECストリーミング解決策は、FECが使用される時の送信レートの変動を最小化するのに使用することもできる。これの1つの利益は、パケットネットワーク内で、ストリームの送信レートのピークがネットワーク内の制限された容量を有する点での他のトラフィックのピークと一致する時の輻輳またはバッファオーバーフローに起因して、変動する送信レートを有するストリームが、よりパケット消失を受けやすいことである。最低限でも、FEC符号化されたストリームのレートの変動は、オリジナルのソースストリームのレートの変動より悪くなってはならず、好ましくは、より多くのFEC保護がオリジナルのソースストリームに適用されるにつれて、FEC符号化されたストリームのレートの変動が、より少なくなる。特殊な事例として、オリジナルストリームが、一定のレートで送信される場合に、FEC符号化されたストリームも、できる限り一定に近いレートで送信されなければならない。
【0057】
FECストリーミング解決策は、FEC受信機でできる限り単純な論理を実現しなければならない。これは、多くの文脈で重要である。というのは、FEC受信機が、制限された計算リソース機能、メモリリソース機能、および他のリソース機能を有するデバイスに組み込まれる場合があるからである。さらに、いくつかの場合に、伝送でのシンボルのかなりの消失または破損がある場合があり、したがって、FEC受信機が、条件が改善される時にストリーム内のどこから受信が継続しつつかるのかを理解するためのコンテキストがほとんどまたは全くない、破滅的な消失または破損のシナリオから回復しなければならない場合がある。したがって、FEC受信機論理が単純であり、堅牢であるほど、FEC受信機は、FEC符号化されたストリームの受信からのソースストリームのソースシンボルの回復およびこれをもう一度使用可能にすることを、よりすばやく信頼できる形で開始できるようになる。
【0058】
FECストリーミング解決策の総合的な望ましい特徴の一部を、次のように要約することができる。
【0059】
1.FEC送信機は、ソースストリングのオリジナルの送信順序を維持しなければならない。
【0060】
2.FEC復号化器は、CPU利用度をできる限り滑らかに拡散させなければならない。
【0061】
3.FEC受信機は、FEC符号化されたストリームの受信の始まりと、そのソースストリームの最初のデータがFEC復号化の後に使用可能にされる時との間の遅延と定義されるFEC受信機待ち時間を最小化しなければならない。
【0062】
4.FEC送信機/受信機は、FECエンドツーエンド待ち時間すなわち、FEC送信機待ち時間およびFEC受信機待ち時間を含む、FECを使用することによって導入される総待ち時間を最小化しなければならない。
【0063】
5.FEC符号化されたストリーム(そのストリームについて送信されるすべてのデータを含む)の送信レートは、できる限り滑らかでなければならず、少なくともオリジナルのソースストリームと同程度に滑らかでなければならない。
【0064】
次のセクションでは、これらの特徴の一部またはすべてを有する方法および装置を説明する。
【0065】
インクリメンタル復号化
このセクションでは、ソースブロックについて受信された符号シンボルから、そのソースブロックの失われたソースシンボルを回復するインクリメンタルFEC復号化処理を説明する。この説明では、組織的FEC符号が使用されると仮定し、ソースシンボルのソースブロックから生成されるシンボルは、リペアシンボルと呼ばれ、用語”符号シンボル”は、ソースシンボルまたはリペアシンボルのいずれかであるシンボルを指すのに使用される。
【0066】
この処理は、符号シンボルの受信と同時に、線形式のリストを更新し、このリストでは、式の個数が、受信された符号シンボルの個数であり、個数変数が、ソースシンボルの個数である。各式は、受信された符号シンボルのうちの1つに対応する。処理の始めには、符号シンボルがまだ受信されていないという事実をまねて、式の個数は0である。
【0067】
ソースシンボルおよびリペアシンボルの受信と同時に復号化動作を部分的に完了する技法を説明する。この技法は、バンデルモンド行列またはコーシー行列に基づく組織的リードソロモン符号に関して説明されるが、行列に関して記述されるどの線形変換にも同等に適用することができる。
【0068】
バンデルモンド行列またはコーシー行列に基づく(n,k)リードソロモン符号は、次のように動作する。
【0069】
GF(2)上のn×k生成行列Mが、下の式2を満足するように構成され、ここで、Eは、符号シンボルを含む大きさnの列ベクトルであり、Sは、ソースシンボルを含む大きさkの列ベクトルである。組織的符号について、さらに、Mの最初のk個の行が、恒等行列を形成すると仮定する。
【0070】
E=M*S (式2)
基本的な演算は、基礎の体GF(2)の要素にまたがるものである。たとえば、q=8の場合に、体の各要素を、データの単一バイトとして表すことができる。多くの場合に、”Rizzo”に記載されているように、符号化と復号化との両方が、次のように体要素をグループ化することが効率的である。ソースブロックが、k*T個の体要素を含み、Tが、正の整数であるものとする。すると、ソースブロックの体要素を、それぞれがT個の体要素のk個のグループに区分することができ、各グループを、ソースシンボルであると考えることができる。次に、記載されているように(たとえば、”Rizzo”)、同一の行列ベクトル乗算演算が、k個のソースシンボルにまたがってソースシンボルのT個の位置のそれぞれに適用されて、FEC符号化中にn個の符号シンボルが生成され、したがって、T個の位置のそれぞれについて、適用すべき演算のシーケンスを1回だけ計算することが可能になる。同様に、FEC復号化中に、復号化演算のシーケンスを1回計算し、受信した符号シンボルにまたがって符号シンボルのT個の位置のそれぞれに適用して、オリジナルのk個のソースシンボルを回復することができる。
【0071】
オリジナルのk個のソースシンボルを回復するためには、符号シンボルのうちの少なくともk個を受信しなければならない(同一サイズのシンボルと、オリジナルシンボルに関する追加情報が使用可能でないこととを仮定して)。行列M’は、復号化に使用されるk個の受信された符号シンボルに対応するMのk個の行から形成され、列ベクトルE’は、復号化に使用されるk個の受信された符号シンボルを含む。すると、復号化は、式3によって記述されるE’およびM’に基づいてSを解くことを含む。
【0072】
E’=M’*S (式3)
リードソロモン符号について、Mの構成は、M’が必ず可逆になるようになっており、これは、任意のk個の符号シンボルの受信からの復号化を可能にする(他のFEC符号および線形変換について、Sについて解くためにk個を超える符号シンボルを受信する必要があることがありえる)。Sについて式3を解くためのFEC復号化計算の量は、受信されたソースシンボルのすべてが、E’に含まれるk個の符号シンボルの中にある場合に最小化される。
【0073】
式3に基づいてSについて解くのに必要な計算は、大部分、次のように符号シンボルの到着と同時に実行することができる。
【0074】
mが、受信されたソースシンボルの個数であるものとする。すると、ここでは組織的線形変換を説明しているので、M’の最初のm個の行は、それぞれ単一の項目を含む。E’およびSとM’の行および列とを、最初のm個の行および列が受信されたソースシンボルに対応するように置換することができ、その後、M’の左上のm×m部分行列は、恒等行列であり、M’の右上のm×(k−m)部分行列は、零行列である。したがって、M’は、図4に示されたフォーマットを有し、ここで、Imは、m×m恒等行列であり、0は、m×(k−m)のすべての0の行列であり、Aは、(k−m)×m行列であり、Bは、(k−m)×(k−m)行列である。M’の上側のm個の行は、Im|0と記述され、M’の下側の(k−m)個の行は、A|Bと記述され、今や、次の式4〜5が得られ、ここで、Eは、Eの最初のm個の項目(受信されたソースシンボル)であり、Eは、Eの最後の(k−m)個の項目(受信されたリペアシンボル)であり、Sは、Sの最初のm個の項目(受信されたソースシンボル)であり、Sは、Sの最後の(k−m)個の項目(それについて解かなければならない未知のソースシンボル)である。
【0075】
=(Im|0)*S=S (式4)
=(A|B)*S=A*S+B*S (式5)
したがって
B*S=E−A*E (式6)
であり、したがって、
=B−1*(E−A*E) (式7)
である。
【0076】
同時復号化を使用する実施形態は、ソースシンボルが到着する時にA*Eを計算できるという事実に頼る。行列Aは、正確にk個の行を有するように行列M’が選択されるので、消去されたソースシンボルと同一個数の行を有する。
【0077】
図5、6、および7に示され、下で説明される復号化方法の実施形態の説明について、受信されるソースブロックのすべてのソースシンボルが、そのソースブロックのいずれかのリペアシンボルが受信される前に受信され、さらに、すべての符号シンボルが、増加するインデックスの順序で受信され、ソースシンボルが、1からkまでのインデックスを付けられ、リペアシンボルが、k+1からnまでのインデックスを付けられると仮定する。しかし、符号シンボルの消去の量およびパターンは、FEC復号化器に既知ではなく、したがって、A’*Eが計算され、ここで、A’は、m個の受信されたソースシンボルに対応するMの列と交差するMの最後のn−k個の行に対応する。
【0078】
図5には、ソースシンボルが到着する時に使用できる処理が示されている。変数mは、ステップ505で0に初期化されて、ソースシンボルがまだ到着していないことを示し、n−k個のシンボルのベクトルrも、ステップ505ですべて0のシンボルに初期化される。ステップ510で、テストを行って、別のソースシンボルがあるかどうかを調べ、さらなるソースシンボルがない場合には、ソースシンボルの受信は、ステップ520に示されているように、図6で説明する処理に進む。別のソースシンボルがある場合には、ステップ530で、シンボル値eおよびインデックスjを用いてそのソースシンボルを受け取る。ステップ540で、受け取ったソースシンボルの個数mを1つインクリメントし、ベクトルCOLを更新して、m番目の受け取られたソースシンボルのインデックスを記憶する。ステップ550で、ベクトルM[k+1,...,n:j]と受け取られたシンボル値eとの積を加算することによって、シンボルのベクトルrを更新し、ここで、M[k+1,...,n:j]は、Mの列jの最後のn−k個の行に対応する。したがって、この処理が、最終的に図5のステップ520に達する時に、リペアシンボルベクトルrは、A’*Eと等しい。
【0079】
図6には、リペアシンボルが到着する時に使用できる処理が示されている。変数rは、ステップ605で0に初期化されて、リペアシンボルがまだ到着していないことを示す。ステップ610では、検査を行って、到着した符号シンボルの総数すなわちm個のソースシンボルおよびr個のリペアシンボルが、ソースブロック内のソースシンボルの総数kと等しいかどうかを調べる。k個の符号シンボルが到着している場合には、復号化が可能であり、この処理は、図6のステップ620に示されているように、図7に進む。k個より少ない符号シンボルが到着している場合には、この処理は、図6のステップ630に進み、別のリペアシンボルの受信について検査する。追加のリペアシンボルがない場合には、ステップ640に示されているように、復号化は可能ではない。別のリペアシンボルがある場合には、ステップ650で、シンボル値eおよびインデックスjを用いてそのリペアシンボルを受け取る。ステップ660で、受け取られたリペアシンボルの個数rを1つインクリメントし、ベクトルROWを更新して、r番目の受け取られたリペアシンボルのインデックスを記憶する。ステップ670で、シンボルベクトルeのr番目の項目にe−r[j−k]をセットし、ここで、r[j−k]は、A’*Eのインデックスjを有するリペアシンボルに対応するシンボル値を格納し、したがって、この処理が最終的に図6のステップ620に達する時に、シンボル値ベクトルeは、E−A*Eと等しい。
【0080】
図7では、B−1*e=B−1*(E−A*E)=Sを計算する、すなわち、受信されていないソースシンボルについて解く、この処理の最後のステップを説明する。図7のステップ705から760では、行列Bを決定する。ステップ705で、i、j、およびsrcの値を、すべて0に初期化し、iは、k個のソースシンボルを通ってインデクシングするのに使用され、jは、これまでに欠けているソースシンボルの個数を記憶するのに使用され、srcは、受信したソースシンボルのインデックスの配列へのインデックスである。また、COL[m+1]に0をセットして、後続の論理を単純化し、COLは、図5に示されているように計算される、m個の受信されたソースシンボルのインデックスの配列である。ステップ710で、iの値を1つインクリメントし、ステップ720で、復号化処理は、すべてのソースシンボルが検討されたかどうかの検査を含み、そうでない場合には、この処理は、ステップ730に継続し、ステップ730では、この処理は、iが受信されたソースシンボルのインデックスである、すなわち、i=COL[src]であるかどうかを検査する。iが受信されたソースシンボルのインデックスである場合には、ステップ750で、このソースシンボルをスキップするが、iが欠けているソースシンボルのインデックスである場合には、ステップ740で、このインデックスを、欠けているソースシンボル値のベクトルMISSに保存する。k個のソースシンボルのすべてを、それが欠けているかどうかを調べるために検査し、そのインデックスをベクトルMISSに適当に追加した後に、ステップ760で、この処理は、受信したリペアシンボルのベクトルROWによってインデクシングされるMのr個の行と欠けているソースシンボルのベクトルMISSによってインデクシングされるr個の列との交差として行列Bを形成する。ステップ770で、Bの逆行列B−1を計算し、ステップ780で、欠けているソースシンボルをB−1*eとして計算し、この点で、ステップ790に示されているように、復号化が完了する。
【0081】
上の処理の多数の変形形態がある。たとえば、この開示を読んだ後には、ソースパケットおよびリペアパケットが任意の順序で到着するようにするためにこの処理を変更することが、単純であるに違いない。当業者は、この開示を読んだ後に、本明細書で教示される方法の多数の他の変形形態を識別できるに違いない。上の処理のいくつかの追加の変形形態および機能強化を、下で説明する。
【0082】
説明したばかりの処理では、シンボルの潜在的により大きいn−kベクトルであるr=A’*Eを計算する。消去の個数および受信されたリペアシンボルの位置がわかったならば、rの要素をA*Eから破棄することができる。その結果、この手法は、不必要な計算を実行する可能性を許す(rの計算されるシンボルを破棄できるので)。しかし、この不必要な計算は、それ以外の形でプロセッサがFEC計算によって占有されない可能性がある時間の間に行われる。計算全体の量を、復号化に使用されるk個のシンボルの受信の後にすべての処理が開始される伝統的な復号化のワーストケース未満に保つことができることは、明白であるに違いない。
【0083】
上で説明した処理では、シンボルのベクトルrは、シンボルが到着する間に記憶されることに留意されたい。リペアシンボルの総サイズと等しい量のメモリが、このために必要である。Aを形成するA’の行が識別される時に、このメモリを再利用することができる。特定のリペアシンボルが受信されないことを識別することが可能である場合には、rのその項目に対応するメモリを解放することができる。十分なリペアシンボル(すなわち、欠けているソースシンボルの個数と等しい個数のリペアシンボル)が受信されるや否や、Aを形成するA’の行を識別することができ、受信されるさらなるリペアシンボルのすべてを破棄することができる。
【0084】
n−k個のシンボルと等しい量のメモリが、rの記憶のために割り振られる。ワーストケースでは、k個のシンボルのためのさらなる量のメモリも、ソースシンボルが到着する時にソースシンボルを記憶するために必要である、すなわち、総メモリ必要量は、シンボルn個分である。
【0085】
さらなる変形形態では、図7に示されたB−1*(E−A*E)の計算を、2つのサブステップに分割することができ、その第1サブステップは、リペアシンボルが到着する時に実行される。これは、式6に従って動作するのではなく、式8に従って、行ごとに、リペアシンボルが到着する時に動作するようにするために復号化器を再構成することに頼る。
【0086】
*S=B*(E−A*E) (式8)
式8では、Bは、上三角の形であり、Bは、下三角の形である。到着する各リぺアシンボル(すなわち、Eの要素)を用いて、これらの行列のそれぞれの追加の行を、Bの逆行列のガウス消去処理のステップを実行することによって計算することができる。
【0087】
さらに、B*(E−A*E)の値も、リペアシンボルが到着する時に計算することができる。このフェーズでは、各連続するリペアシンボルが、B*(E−A*E)の付随する項目の値を計算するために、最後のリペアシンボルより多くの作業を必要とするので、リペアシンボルが到着する時間にまたがって、作業負荷が均一には拡散されないことに留意することが重要である。
【0088】
したがって、十分なリペアシンボルが到着した後に実行すべき残りの作業は、系(式8)を解くことであり、これは、後退代入によって行うことができる。
【0089】
リペアパケットの先行送信
リペアパケットがソースパケットの前に送信される場合に、上の処理に対するある種の変形形態を作ることができる。この手法は、ソースパケットがリペアパケットの後に送信される場合にはソースパケットをバッファリングしなければならないので、FEC送信機で追加の遅延を注入するというコストを有する。
【0090】
しかし、この手法には複数の利点がある。よい受信状態でソースブロックの途中でストリームに参加する受信機は、より大量のソースデータを受信し、したがって、FEC受信機待ち時間が減る。失われたリペアパケットの位置は、既知であり、したがって、これらのシンボルに対応する(E−A*E)の要素の計算を回避することができる。受信されたリペアシンボルの個数がrである場合に、k−r個のソースシンボルが受信されたならば、(E−A*E)の行を破棄することができ、その後に受信されるソースシンボルに付随する計算を減らすことができる。その結果、復号化を、合計k個のシンボルのためのメモリだけを使用して完了することができる。
【0091】
2D符号に関する改善されたインターリービング
2次元符号とは、シンボルが2次元格子に配置され、独立の消去訂正符号が各行のシンボルおよび各列のシンボルに適用される符号である。使用可能な計算リソースおよび他のリソースに応じて、復号化手順を反復することができ、これによって、符号のエラー訂正能力が潜在的に高まる。この形では、たとえばリードソロモン符号またはXOR符号など、任意のエラー訂正符号を適用することができる。この説明では、消去符号に関してこのクラスの符号を提示するが、エラー訂正符号および消去訂正符号の当業者に明らかである通り、同一の手法を、エラー訂正符号に簡単に適用することができる。
【0092】
周知の通り、2次元符号の性能は、符号シンボルをオリジナルの順序以外の順序で送信することによって改善することができる。しかし、これは、FEC符号をサポートしない受信機に関して複雑さを追加し、送信機と受信機との間の消失が少ない場合に、ファイルの受信に必要な時間を増やす。移動端末の場合に、この追加の受信時間は、追加の電力消費を意味し、これが電池寿命を減らす。
【0093】
代替の手法は、2次元符号を適用する前に、ソースシンボルのオリジナル順序に非自明な置換を適用することである。ソースシンボルは、オリジナルの順序で送信され、FECをサポートしない受信機の複雑さが減り、消失が少ない場合の受信時間が減る。リペアシンボルは、生成された順序またはある他の順序のいずれかで、ソースシンボルの前に、ソースシンボルの間に散在して、またはソースシンボルの後に送信される。
【0094】
この手法では、送信機と受信機との両方が、適用された置換を知っている。これは、送信機と受信機との両方に既知の明確に定義された組織的な形で置換を導出することによって達成することができる。たとえば、特定の擬似乱数生成処理を、送信機と受信機との両方で定義し、置換を生成するのに使用することができる。もう1つの例は、次の処理によって置換を定義することであるはずである。
【0095】
kが、ソースシンボルの個数であり、k’が、k以上の最小の素数であるものとする。k未満の2つの整数aおよびbを選択する。次に、ソースシンボルが、最初に0,...,k−1という番号を与えられる場合に、新しい順序付けは、次のように定義される。
【0096】
1)すべてのソースシンボルが新しい順序付けに追加されている場合には、停止する
2)b<kである場合には、新しい順序付けの次のソースシンボルは、シンボルbである
3)b=(b+a) mod k’
4)(1)に進む
上の方法の不利益は、選択される置換に依存して、オリジナルのシンボル送信順序付けで隣接する2つのシンボルが2次元符号で同一行または同一列に現れることが、可能なままであることである。これは、2つの隣接するシンボルの消失が、単一の行内または単一の列内に集中するので、バースト消失に対する符号の脆弱性に対する悪影響を有する。
【0097】
さらなる変形形態では、隣接するシンボルを絶対に同一行または同一列に写像しない置換が選択される。ソースブロックが正方形である場合に、そのような置換は、たとえば、数0,...,k=kの2つの置換σおよびσを選択することによって定義することができ、ここで、kおよびkは、それぞれ2次元ソースブロックの行および列の個数である。次に、s[i,j]が、ソースブロック内の位置(i,j)のシンボルを表し、s’[i,j]が、置換されたソースブロック内の位置(i,j)のシンボルを表すものとする。次に、
s’[i,j]=s[(σ(j)+σ(i))%k,j] (式9)
を定義する。
【0098】
次に、2次元符号を、置換されたソースブロックに適用する。ソースシンボルは、オリジナルの順序で送信される。次に、リペアシンボルを、任意の順序で送信することができる。有利なことに、同一行または同一列の符号からのリペアシンボルは、絶対に連続しては送信されない。
【0099】
一般化された符号
このセクションでは、多次元符号の一般化されたクラスを導入する。この一般化されたクラスの符号に関する符号化処理および復号化処理は、実施の複雑さにおいて、2次元符号の特定の事例とほぼ同等である。前と同様に、この説明は、消去訂正符号に関して提示されるが、本明細書で提示される技法を、エラー訂正符号にも適用できることを理解されたい。
【0100】
この一般化されたクラスの符号は、ソースシンボルごとに1列、リペアシンボルごとに1列を有する2進行列に関して定義することができる。この行列の各行は、次のように、別個の消去訂正符号を表す。これらの別個の消去符号を、本明細書ではコンポーネント消去符号と称し、符号全体をコンパウンド符号と称する。上で説明したものなどの2次元符号の場合に、コンポーネント消去符号は、個々の行および列の符号であり、コンパウンド符号は、コンポーネント符号の組合せから形成される2次元符号である。一般化された事例について、行ごとに、コンポーネント消去訂正符号は、2つの条件が存在する場合に構成される。
【0101】
第1の条件は、コンポーネント符号のソースシンボルが、その列が特定の行に”1”を有するコンパウンド符号のソースシンボルと、その列が特定の行に”1”を有し、コンパウンド符号リペアシンボルの列が行列内の下側インデックスの1つの行に”1”を有するコンパウンド符号のリペアシンボルとを含むことである。これらのシンボルを、コンパウンド符号のソースシンボル全体から区別するために、”コンポーネント符号ソースシンボル”と呼ぶ。
【0102】
第2の条件は、コンポーネント符号リペアシンボルが、その列が特定の行に”1”を有し、その列が下側インデックスの行に”1”を全く有しないコンパウンド符号リペアシンボルを含むことである。これらのシンボルを、コンパウンド符号のリペアシンボル全体から区別するために、”コンポーネント符号リペアシンボル”と呼ぶ。
【0103】
よって或るコンパウンド符号リペアシンボルの値は、リペアシンボルに対応する列の中で“1”を伴う第1行に対応するコンポーネント消去符号によって決定される。このリペアシンボルは、行列の後続行内にコンポーネント符号ソースシンボルとして現れる可能性がある。
【0104】
本明細書で提示する一般化では、2Dリードソロモン符号は、k+k個の行および(k*k)+k*(n−k)+k*(n−k)個の列を有する行列に関して説明される。最初のk個の行は、通常の2次元表現の行にまたがるリードソロモン符号に対応する。残りのk個の行は、通常の2次元表現の列にまたがるリードソロモン符号に対応する。ここで、(n−k)は、2Dリードソロモン符号の列ごとに生成されるリペアシンボルの個数であり、(n−k)は、2Dリードソロモン符号の行ごとに生成されるリペアシンボルの個数である。
【0105】
明らかに、任意の多次元リードソロモン符号を、この形で表現することができる。
【0106】
追加の符号を、異なる行列構成を使用して構成することができる。たとえば、低密度パリティチェック(LDPC)符号の一般クラスは、XOR消去符号に基づくこのクラスの符号の例を提供する。本明細書で提示する一般化は、これらの符号を定義する行列を、他の消去符号、たとえばリードソロモン符号を使用して適用することを可能にする。この一般化では、リードソロモンがXOR演算の代わりに使用されるので、複数のリペアシンボルを、行列の行ごとに生成することができる。
【0107】
最後に、連鎖符号(たとえば、Luby Iおよび他の文献に記載の連鎖符号)およびマルチステージ連鎖符号(たとえば、ShokrollahiIおよび他の文献に記載の連鎖符号)をこの一般化に適用して、ファウンテン符号の特性を有する新しい符号を生成することもできる。
【0108】
この一般化を適用するためには、符号を記述する行列が、FEC符号化器とFEC復号化器との両方に既知でなければならない。特定の符号の場合に、行列の構造を、FEC符号化器とFEC復号化器との両方に前もって供給することができ、正確な符号を記述する特定のパラメータだけを、通信チャネルを介して供給することができる。
【0109】
本明細書で説明するクラスの符号は、2次元符号に使用されるアルゴリズムの一般化である共通の復号化アルゴリズムによって復号化することができる。受信機は、通信チャネルからできる限り多数のソースシンボルおよびリペアシンボルを集め、その後、次の処理を繰り返す。
【0110】
a)行列の行ごとに、その行について未知のままであるシンボル(コンポーネント符号ソースシンボルおよびコンポーネント符号リペアシンボル)の個数を計算し、
b)未知のシンボルの個数がコンポーネント符号リペアシンボル(すなわち、元々はその行のコンポーネント符号によって生成されたリペアシンボル)の個数以下である行ごとに、未知のコンポーネント符号ソースシンボルの値を決定するために行復号化動作を試みる。この復号化動作が成功であり、いずれかのコンポーネント符号リペアシンボルが未知のままである場合には、未知のコンポーネント符号リペアシンボルの値を決定するために符号化動作を実行し、
c)なんらかの動作がステップ(b)で実行され、いくつかのソースシンボルが未知のままである場合には、ステップ(a)に戻る。そうでない場合には、停止する。
【0111】
上の処理は、例としてのみ説明されたものである。さらなる最適化を、たとえばさらなる復号化動作で支援する可能性を有しないコンポーネント符号リペアシンボルの計算を避けるために、適用することができる。これらの動作は、ハードウェア、ソフトウェアなどによって実施される、受信機の復号化器部分によって実行することができる。
【0112】
最後に、上で注記したように、上の一般化された符号構成は、リードソロモン符号に制限されず、任意の消去符号を適用して、各行の行リペアシンボルを構成することができる。明らかに、XOR演算が使用される場合に、結果は、上で言及した符号を含む、LDPC符号の周知のクラスである。
【0113】
FEC送信
このセクションでは、FEC送信機がパケット(ソースパケットとリペアパケットとの両方)の送信を刻時する方法おおよび処理を説明する。ここでは、単一のソースブロックに関するパケットの送信に集中するが、これらの処理および方法が、ソースブロックに区分されるソースストリームにシームレスに適用されるように設計されていることに留意されたい。
【0114】
kが、ソースブロック内のソースシンボルの個数であるものとし、Tが、ソースブロックの保護期間であるものとし、pが、分数として表される保護量であるものとし、したがって、p・k個のリペアシンボルが、ソースブロックについて送信される。k、T、およびpの値は、各ソースブロックが形成されつつある時にFEC送信機によって動的に決定することができ、したがって、あるソースブロックのkおよびTの値は、そのソースブロックのソースシンボルのほとんどまたはすべてがFEC送信機に到着した時にFEC送信機だけに既知である場合があり、pの値は、ソースブロックのソースシンボルのすべてがFEC送信機に到着した後に決定することができる。また、FEC送信機は、異なるソースブロックのシンボルサイズを変更することができる。したがって、特定のソースブロックのこれらのパラメータの多数またはすべてが、そのソースブロックのデータを十分に受け取ったFEC受信機に既知になる可能性がある。
【0115】
FECエンドツーエンド待ち時間に関する懸念がない場合には、次のFEC基本送信機が、しばしば、適切である。
【0116】
FEC基本送信機:たとえばT秒の期間にわたって、ソースブロックのソースシンボルが到着する時に、これらのソースシンボルをバッファリングする。次に、たとえばT’秒の期間にわたって、そのソースブロックのp・k個のリペアシンボルを生成する。次に、後続のT秒にわたって均等に拡散してソースシンボルおよびリペアシンボルを送信する。
【0117】
このFEC基本送信機は、次の特性を有する。
【0118】
1.保護期間はTであり、これは、FEC送信機でソースシンボルを受け取る時間と同一である。
【0119】
2.ソースブロックについて送信されるシンボルは、経時的に均等に拡散される。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がシンボルの伝送中にいつ発生するかに依存しないことを意味し、これは望ましい特性である。
【0120】
3.このFEC送信機は、シンボルの全体的な送信レートの変動を導入しない。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合に、すべてのシンボルの送信レートは、やはり一定であり、このFEC送信機でのソースシンボルのオリジナルの到着レートが可変である場合に、少なくともソースブロックあたりのシンボルの一定の送信レートが、変動を減衰させる。これは、望ましい特性である。
【0121】
4.FEC受信機待ち時間は、T程度に少ないものとすることができる。これは、(1+p)・k個のシンボルの最小限のバッファリング(すべてのソースブロックがk個のソースシンボルを含むと仮定して)を意味し、これは、可能な最小限であり、したがって望ましい。
【0122】
5.ソースブロックのシンボルは、インターリーブされない。これは、FEC受信機の論理を単純にし、したがって望ましい。
【0123】
このFEC基本送信機が有する1つの望ましくない特性は、FECエンドツーエンド待ち時間が、2・T+T’であり、これがかなり大きくなる可能性があることである。対話型アプリケーションまたはライブ・アプリケーションに関して、FECエンドツーエンド待ち時間を最小化することが非常に望ましく、したがって、これらのアプリケーションに関して、次のFEC送信機を説明し、検討する。
【0124】
FEC送信機A:たとえばR秒の期間にわたって、ソースシンボルが到着する時にそれらのソースシンボルを送信する。受信および次のソースブロックのソースシンボルの送信にまたがって均等に拡散して、リペアシンボルを送信する。
【0125】
FEC送信機Aは、次の特性を有する。
【0126】
1.保護期間Tは、2・Rである(次のソースブロックも、R秒の期間にわたって受け取られるソースシンボルを含むと仮定して)。
【0127】
2.ソースブロックについて送信されるシンボルは、ソースシンボル到着が経時的に均等に拡散している場合であっても、経時的に均等に拡散はされない。これは、後続ソースシンボル送信の間の平均時間がk/Rであるが、後続リペアシンボル送信の間の平均時間がp・k/Rであるからである。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がシンボルの伝送中にいつ発生するかに依存することを意味する。これは、停止がいつ発生するかと独立に所与の停止持続時間に耐えるために保護量を設計している場合に、ソースシンボル伝送またはリペアシンボル伝送のレートのうちのより大きい方に非最適に基づく保護の量を提供しなければならないことを意味する。これは、ある種のアプリケーションで望ましくない特性である。
【0128】
3.ソースストリーム全体のシンボルの全体的な送信レートは、ソースシンボルの送信レートから大きくは変動しない。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合には、すべてのシンボルの送信レートは一定であり、ソースシンボルのオリジナルの送信レートが可変である場合には、リペアパケットが均等に拡散されて送信されるので、オリジナルソースストリームの変動性が、多少減衰される。これは、望ましい特性である。
【0129】
4.FEC受信機待ち時間は、少なくともT=2・Rであり、これは、たとえば対話型アプリケーションなど、いくつかのアプリケーションでは望ましくない。というのは、オリジナルソースブロックの持続時間が、Rに過ぎないからである。これは、少なくとも(2+p)・k個のシンボルのバッファリングが必要である(すべてのソースブロックがk個のソースシンボルを含むと仮定して)ことを意味する。これは、可能な最低限である(1+p)・kよりはるかに大きく、したがって、これは、いくつかのアプリケーションで望ましくない。
【0130】
5.あるソースブロックのリペアシンボルが、次のソースブロックからのソースシンボルとインターリーブされる。これは、複数のソースブロックのシンボルを同時に記憶し、保存することを必要とするので、FEC受信機論理を潜在的に必要であるものより複雑にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを多少難しくする。
【0131】
したがって、全体的なFEC送信機Aは、混合された品質を有し、ある種のアプリケーションでは好ましくない場合がある。
【0132】
FEC送信機B:たとえばR秒の期間にわたって、ソースシンボルが到着する時にそれらのソースシンボルを送信する。ソースシンボル到着の平均レートで均等に拡散してリペアシンボルを送信し、したがって、リペアシンボルは、p・R秒にわたって均等に拡散される。
【0133】
FEC送信機Bは、次の特性を有する。
【0134】
1.保護期間Tは、(1+p)・Rである。
【0135】
2.ソースブロックについて送信されるシンボルは、ソースシンボル到着が経時的に均等に拡散されている場合には、経時的に均等に拡散される。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がソースブロックのシンボルの伝送内でいつ発生するかに依存しないことを意味し、これは、望ましい特性である。
【0136】
3.ソースストリーム全体のシンボルの全体的な送信レートの変動が、導入される。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合であっても、リペアシンボルの伝送が後続ソースブロックのシンボルの送信と部分的にオーバーラップするだけなので、シンボルの全体的な送信レートは、非常に可変であり、変動が多い。これは、ある種のアプリケーションで望ましい特性ではない。
【0137】
4.FEC受信機待ち時間は、少なくともT=(1+p)・Rであり、これは、いくつかのアプリケーションで望ましくない。というのは、オリジナルソースブロックの持続時間が、Rに過ぎないからである。これは、少なくとも(1+2・p)・k個のシンボルのバッファリングが必要である(すべてのソースブロックがk個のソースシンボルを含むと仮定して)ことを意味する。これは、可能な最低限である(1+p)・kよりはるかに大きい。
【0138】
5.あるソースブロックのリペアシンボルが、次のソースブロック(および、pの値に依存して、おそらくは後続ソースブロックも)からのソースシンボルとインターリーブされる。これは、複数のソースブロックのシンボルを同時に記憶し、保存することを必要とするので、FEC受信機論理を潜在的に必要であるものより複雑にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを多少難しくする。
【0139】
したがって、全体的なFEC送信機Bは、混合された品質を有し、ある種のアプリケーションでは好ましくない場合がある。戦略AおよびBは、FEC符号化器が、最後のソースシンボルが受信された後にリペアシンボルを作るのにかなりの時間を要する場合があることを考慮に入れておらず、実用的なFEC送信機では、これが考慮に入れられる必要があることに留意されたい。しかし、FEC符号化時間を考慮に入れるために戦略を変更することが、その望ましくない特性のいずれをも改善しないことに留意されたい。
【0140】
いくつかの条件で好ましい実施形態は、下で説明するFEC送信機Cになるはずである。
【0141】
FEC送信機C:あるソースブロックを形成するソースシンボルが、R=T秒の期間にわたって到着し、Tは、保護期間である。u=p/(1+p)であるものとし、T’≧u・Tであるものとし、ここで、T’−u・Tは、あるソースブロックの最後のソースシンボルの受け取りの後に、FEC符号化器がそのソースブロックの最初のリペアシンボルを生成し、下で規定する送信レートでそのソースブロックの後続リペアシンボルの生成を継続できるのに十分な時間である。tが、FEC送信機での現在時刻であるものとする。
【0142】
1.ソースブロックがこのFEC送信機によって開始される時に、tをt=0に初期化する。
【0143】
2.現在時刻tが、区間0≦t≦Tに含まれる間に、ソースシンボルが現在時刻tに受け取られるたびに、そのソースシンボルを、時刻T’+t/(1+p)に送信されるようにスケジューリングする。
【0144】
3.ソースブロックが時刻Tに完了した時に、k個のソースシンボルが受け取られていると仮定する。そのソースブロックのp・k個のリペアシンボルを、時間区間T’+T/(1+p)からT’+Tまで(長さu・Tの区間である)にわたって均等に送信されるようにスケジューリングする。
【0145】
FEC送信機Cは、次の特性を有する。
【0146】
1.保護期間Tは、その間にソースブロックのソースシンボルが到着する時間期間と同一の持続時間である。
【0147】
2.ソースシンボルの全体的な送信レートの変動は、時間において倍率1/(1+p)だけ圧縮されるが、同一の大きさのままになる。これは、保護量が増えるにつれて、FEC符号化されたストリームによって使用される帯域幅の量が増え、したがって、より多くの帯域幅を使用する時には、ストリーミングレートの変動の大きさを減らすことがより望ましいはずなので、いくつかのアプリケーションで完全に望ましくはない可能性がある。これは、固定持続時間のバースト消失に対して提供される保護のレベルが、消失がいつ発生するかに依存する可能性があることをも意味し、これは、望ましくない場合がある。しかし、特殊な事例として、ソースシンボルのオリジナルの送信レートが一定である場合に、FEC符号化されたストリームの送信レートも一定であり、したがって、固定持続時間のバースト消失に関して提供される保護のレベルは、消失がいつ発生するかに依存しない。
【0148】
3.FECエンドツーエンド待ち時間は、FEC符号化待ち時間およびFEC復号化待ち時間が0に接近するので、T’+u・T程度に短くすることができる。
【0149】
4.FEC受信機待ち時間は、FEC復号化待ち時間が0に接近するので、T程度に短くすることができる。これは、(1+p)・k個のシンボルのバッファリングだけが必要である(すべてのソースブロックがk個のソースシンボルを含むと仮定して)ことを意味する。これは、可能な最小限の量であり、したがって、これは望ましい。
【0150】
5.あるソースブロックのリペアシンボルは、次のソースブロックからのソースシンボルとインターリーブされない、すなわち、あるソースブロックのすべてのシンボルが、後続ソースブロックのシンボルが送信される前に送信される。これは、本質的に1つのソースブロックのシンボルだけを同時に記憶し、保存することを必要とするので、FEC受信機の論理を単純にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを簡単にする。
【0151】
6.FEC送信機は、最後のソースシンボルの到着と最初のリペアシンボルの送信との間にT’−u・Tの時間遅れがあるので(T’は、FEC符号化器の能力に基づいて適当に調整できるパラメータである)、FEC符号化器が、最後のソースシンボルが受け取られた後にリペアシンボルを作るのかなりの長さの時間を要する可能性があることを考慮に入れる。
【0152】
したがって、全体的なFEC送信機Cは、上のリストの特性2で説明したように、FEC送信機Cが、ソースシンボルの送信レートの変動のオリジナルの大きさを維持することを除いて、説明したそれぞれの形において望ましい。
【0153】
下で説明するFEC送信機Dは、FEC送信機Cに関して上でリストした望ましい特性のすべてを維持するが、ソースシンボルの送信レートの変動の大きさを減衰させるという有益な結果をも維持する。したがって、FEC送信機Dは、複数の利点を有し、いくつかの場合に好ましい実施形態であるものとすることができる。
【0154】
FEC送信機D:あるソースブロックを形成するソースシンボルが、T秒の期間にわたって到着し、Tは、保護期間である。u=p/(1+p)であるものとし、T’≧u・Tであるものとし、ここで、T’−u・Tは、あるソースブロックの最後のソースシンボルの受け取りの後に、FEC符号化器がそのソースブロックの最初のリペアシンボルを生成し、下で規定する送信レートでそのソースブロックの後続リペアシンボルの生成を継続できるのに十分な時間である。tが、FEC送信機での現在時刻であるものとする。この処理の各時点で、Bが、そのソースブロックについて受け取られたソースシンボルの個数であるものとし、Sが、FEC送信機によってこれまでに送信されたソースシンボルの個数であるものとする。
【数3】

【0155】
これらのステップに続いて、すべてのソースシンボルが、時刻Tまでに受け取られており、したがってソースブロックにk=B個のソースシンボルがある。この点で、この処理は、現在時刻tが時間の区間T<t≦T’+T/(1+p)に含まれる間に、残りのB−S個の未送信のソースシンボルをその区間にわたって均等に拡散して送信する。次に、この処理は、現在時刻tが時間の区間T/(1+p)<t≦T’+Tに含まれる間に、p・k個のリペアシンボルをその区間にわたって均等に拡散して送信する。
【0156】
FEC送信機Dは、FEC送信機Cの望ましい特性を有し、さらに、FEC送信機Cの特性2は、FEC送信機Dについて、ソースストリーム全体のシンボルの全体的な送信レートの変動が減衰されるという点で、次に示すものに改善される。具体的に言うと、ソースストリームの変動は、T’が増えるにつれてより大きく減衰され、一般に、T’は、保護量が増えるにつれて増える。
【0157】
これは、保護量が増えるにつれて、FEC符号化されたストリームによって使用される帯域幅の量が増え、したがって、より多くの帯域幅を使用する時に、ストリーミングレートの変動を減らすことがさらに望ましいので、望ましい。また、これは、変動が減衰する時に、固定持続時間のバースト停止がある時の消失に対して提供される保護のレベルが、停止がいつ発生するかにより弱く依存するので望ましく、これは、望ましい特性である。特殊な事例として、オリジナルのソースストリームが一定レートである場合に、FEC符号化されたストリームも一定レートである。全体的なFEC送信機Dは、他の送信機より望ましいものである可能性があり、したがって、多くの条件について好ましい。
【0158】
FEC送信機Dの多数の可能な変形形態があり、その一部は、本明細書で説明され、他の変形形態は、この開示を読んだ後に当業者に明白になるであろう。
【0159】
たとえば、ステップ3bには、yの計算があるが、類似する結果をもたらす正確な計算の代わりの単純な近似を含むこの計算を実行する多数の可能な方法がある。もう1つの例として、ステップ3cでは、条件y≧1に基づいて別のソースシンボルをいつ送信すべきかに関する判断を、変更することができ、たとえば、条件y≧0またはある定数αについてy≧αに置換することができる。そのような変形形態は、類似する結果をもたらす。変形形態のもう1つの例として、次のソースシンボルまたはリペアシンボルを個別に送信するのではなく、シンボルのグループを、各パケット内で一緒に受け取りまたは送信することができ、各パケット内で受け取られまたは送信されるグループのサイズは、パケットごとに変更することができる。この場合に、受け取られたシンボルを説明する手順、および次のソースシンボルまたはリペアシンボルをいつ送信すべきかに関する手順は、単純な形で簡単に変更することができる。
【0160】
もう1つの変形形態の例として、シンボルではなくビットが送信され、受信される、すなわち、潜在的に、一時にシンボル全体ではなくシンボルの諸部分が送信され、受信されるものとすることができ、シンボルを送信する手順およびシンボルを受信する手順は、たとえばシンボルではなくビット単位でまたは可変サイズパケットの単位でのデータの送信および受信に対処するように簡単に変更することができる。
【0161】
FEC送信機Dの1つの可能な変形形態が、下で説明し、図8A、8B、9、10、11、12、および13に示すFEC送信機Eである。FEC送信機Eは、FEC送信機Dに類似し、具体的には、Tは、保護期間の持続時間であり、ソースブロックの持続時間であり、u=p/(1+p)であり、T’≧u・Tは、送信機が現在のソースブロックのソースシンボルの受け取りを開始する時と、送信機が現在のソースブロックのソースシンボルの送信を開始する時との間の時間の持続時間である。FEC送信機Eは、現在のソースブロックの処理を、4つの処理すなわち、図8Aに示されているように、ソース初期処理、ソース中間処理、ソース最終処理、およびリペア送信処理に分解する。この4つの処理のそれぞれの相対的な時間区間および持続時間は、図8Aで、それぞれ”時間区間”と示された列および”継続時間”と示された列に示されている。時間区間は、現在のソースブロックが開始される時刻に対して相対的に表され、したがって、t=0は、現在のソースブロックが開始される時刻に対応する。したがって、図8Aに示されているように、ソース初期処理は、時刻t=0に開始され、時刻t=T’に終了し、したがって、持続時間T’を有する。同様に、ソース中間処理は、時刻t=T’に開始され、時刻t=Tに終了し、したがって、持続時間T−T’を有し、ソース最終処理は、時刻t=Tに開始され、時刻t=T’+T/(1+p)に終了し、したがって、持続時間T’−u・Tを有し、リペア送信処理は、時刻t=T’+T/(1+p)に開始され、時刻t=T’+Tに終了し、したがって、持続時間u・Tを有する。
【0162】
図8Bに示されているように、異なるソースブロックに関する4つの処理が、オーバーラップしていることに留意されたい。たとえば、現在のソースブロックのソース初期処理は、まず、前のソースブロックのソース最終処理と同時であり、その後に、前のソースブロックのリペア送信処理と同時である。もう1つの例として、現在のソースブロックのソース最終処理および現在のソースブロックのリペア送信処理は、次のソースブロックのソース初期処理と同時である。
【0163】
図8Bに示されているように、各時点で、ソースシンボルが、正確に1つのソースブロックだけについて受け取られており、符号シンボルが、正確に1つのソースブロックだけについて送信されている。たとえば、現在のソースブロックのソース初期処理中には、符号シンボルが、前のソースブロックについて送信されており、ソースシンボルが、現在のソースブロックについて受け取られている。もう1つの例として、現在のソースブロックのソース中間処理中には、ソースシンボルが、現在のソースブロックについて受け取られており、符号シンボルが、現在のソースブロックについて送信されている。
【0164】
FEC送信機Eは、次の特性を有する。(a)ソースシンボルが、T秒の間にソースブロックごとに受け取られ、(b)符号シンボルが、T秒の間にソースブロックごとに送信され、(c)あるソースブロックのソースシンボルの受け取りの始めとそのソースブロックのソースシンボルの送信の始めとの間にT’の時間持続時間があり、(d)現在のソースブロックのすべてのソースシンボルが、次のソースブロックのソースシンボルが受け取られる前に受け取られ、(e)現在のソースブロックのすべての符号シンボルが、次のソースブロックの符号シンボルが送信される前に送信される。したがって、FEC送信機Eは、ソースブロックのインターリービングを全く有しない。
【0165】
図9に、FEC送信機Eのソース初期処理を示す。図9のステップ905で、現在のソースブロックが始まり、したがって、現在のソースブロックの、受け取られたソースシンボルの個数Bと送信されたソースシンボルの個数Sとの両方を0に初期化し、現在時刻tに0をセットし、現在のソースブロックのソースシンボルをバッファリングするのに使用されるBUFFERを、空になるように初期化する。ステップ910で、検査を行って、現在時刻tがT’以上であるかどうかを調べ、そうである場合には、この処理は、ステップ920で図10のソース中間処理に進む。ステップ910でのテストの実施が、一般に、十分に頻繁に行われ、その結果、そのテストが真である時にtがT’に非常に近くなることを意味することに留意されたい。同一のコメントが、FEC送信機Eのすべての処理で2つの時刻の間で不等比較が行われる、下で説明するすべてのさらなるステップにあてはまる。ステップ910で、tがT’未満である場合には、ステップ930で検査を行って、次のソースシンボルが到着しているかどうかを調べる。次のソースシンボルが到着していない場合には、この処理はステップ910にループバックするが、次のソースシンボルが到着している場合には、ステップ940で、受け取られたソースシンボルの個数Bをインクリメントし、受け取られたソースシンボルをBUFFERに追加し、その後、処理はステップ910にループバックする。
【0166】
図10に、FEC送信機Eのソース中間処理を示す。図10のステップ1005で、TLASTの値を現在時刻t(T’以上であるが、図9のステップ910でのテストの精度に依存して、T’に非常に近い)に初期化し、TNEXTをTLAST+T’/((1+p)・B)に初期化する。TNEXTは、次のソースシンボルが送信をスケジューリングされる時刻である。ステップ1010で、検査を行って、現在時刻tがT以上であるかどうかを調べ、そうである場合には、この処理はステップ1020に進み、ステップ1020は、現在のソースブロックのソースシンボルの受け取りが完了したことを示し、したがって、BUFFERは、ソースブロックのソースシンボルのすべてを含み、処理は、ステップ1020で図11に示されたソース最終処理に進む。ステップ1010でtがT未満の場合には、ステップ1040で、検査を行って、tがTNEXT以上であるかどうかを調べる。ステップ1040でのテストが真である場合には、次のソースシンボルを送信すべき時であり、したがって、処理はステップ1080に進む。ステップ1080では、まだ送信されていない最初に受け取られたソースシンボルを送信し、送信されたソースシンボルの個数Sを1つインクリメントし、TLASTを現在時刻に更新し、TNEXTをTLAST+(T’−u・TLAST)/(B−S)に更新し、その後、処理はステップ1010にループバックする。ステップ1040でのテストが偽である場合には、ステップ1050で検査を行って、ソースシンボルが到着したかどうかを調べる。ソースシンボルが到着していない場合には、処理は、ステップ1010にループバックするが、ソースシンボルが到着している場合には、処理はステップ1060に継続する。ステップ1060では、到着したソースシンボルをBUFFERの末尾に追加し、Bの値を1つインクリメントし、TNEXTを、ソースシンボルの受け取りに基づいてTLAST+(T’−u・TLAST)/(B−S)に更新し、その後、処理はステップ1010に即座にループバックする。
【0167】
図11に、FEC送信機Eのソース最終処理を示す。図11のステップ1105で、TLASTの値を現在時刻t(T以上であるが、図10のステップ1010でのテストの精度に依存して、Tに非常に近い)に初期化し、TNEXTをTLAST+(T’−u・T)/(B−S)に初期化する。TNEXTは、次のソースシンボルが送信をスケジューリングされる時刻である。ステップ1110で、検査を行って、現在時刻tがT’+T/(1+p)と等しいかどうかを調べ、そうである場合には、処理はステップ1120に進み、ステップ1120は、現在のソースブロックのソースシンボルの送信が完了したことを示し、処理は、ステップ1120で図12に示されたリペア送信処理に進む。ステップ1110でtがT’+T/(1+p)と等しくない場合には、ステップ1130で、検査を行って、tがTNEXTと等しいかどうかを調べる。ステップ1130のテストが真である場合には、次のソースシンボルを送信すべき時であり、したがって、処理はステップ1140に進む。ステップ1140では、まだ送信されていない最初に受け取られたソースシンボルを送信し、送信されたソースシンボルの個数Sを1つインクリメントし、TLASTを現在時刻tに更新し、TNEXTをTLAST+(T’+T/(1+p)−TLAST)/(B−S)に更新し、その後、処理はステップ1110にループバックする。ステップ1130でのテストが偽である場合には、処理はステップ1110に即座にループバックする。
【0168】
図12に、FEC送信機Eのソースリペア処理を示す。図12のステップ1205で、TLASTの値を現在時刻t(T’+T/(1+p)以上であるが、図11のステップ1110でのテストの精度に依存して、T’+T/(1+p)に非常に近い)に初期化し、TDELTAにT/((1+p)・B)をセットし、TNEXTをTLAST+TDELTAに初期化し、ここで、TDELTAは、各リペアシンボルの間の時間増分であり、TNEXTは、次のリペアシンボルが送信をスケジューリングされる時刻である。ステップ1210で、検査を行って、現在時刻tがT’+T以上であるかどうかを調べ、そうである場合には、処理はステップ1220に進み、ステップ1220は、現在のソースブロックのリペアシンボルの送信が完了したことを示し、したがって、現在のソースブロックが完了し、したがって、BUFFERを、後続ソースブロックに再利用することができる。ステップ1210でtがT’+T未満である場合には、ステップ1230で検査を行って、tがTNEXT以上であるかどうかを調べる。ステップ1230のテストが真である場合には、次のリペアシンボルを送信すべき時であり、したがって、処理はステップ1240に進む。ステップ1240では、BUFFERに格納されたソースブロックに基づいて、ソースブロックについて新しいリペアシンボルを生成し、送信し、TLASTをTNEXTに更新し、TNEXTをTLAST+TDELTAに更新し、その後、処理はステップ1210にループバックする。ステップ1230でのテストが偽の場合には、処理はステップ1210に即座にループバックする。
【0169】
FEC送信機Eについて説明した処理と同時に発生する他の処理および計算がある場合がある。たとえば、リペアシンボルの生成に備えて4つの処理のうちの1つまたは複数と同時に発生するBUFFERの前処理がある可能性があり、前処理されたBUFFERは、リペア処理のステップ1240でリペアシンボルを生成するための基礎として使用することができる。同一のまたは類似する結果を達成する他の同等の処理がある可能性もあり、たとえば、リペアシンボルを、リペア処理のステップ1240で説明したように送信される直前に生成するのではなく、送信される時の前に生成することができる。
【0170】
ソースブロックインターリービング
一部のFEC符号は、任意の実用的サイズのソースブロックにまたがって効率的に符号化することができ、任意のサイズのシンボルを効率的に扱うことができる。しかし、他のFEC符号は、より大きいソースブロックを孤立的に扱うことを難しくする、実用的制限を有する。これは、ストリーミングレートがより高い時および/またはシンボルを必ずより短くしなければならない(たとえば、シンボルを搬送する、より短いパケットの使用のゆえに)時および/またはより長い保護期間が使用される時に、特に心配の種である。
【0171】
例として、リードソロモン符号は、256個を超える要素を有する有限体を扱う時に非実用的になる可能性があり、256個の要素の有限体を扱うことは、ソースブロックあたりの符号シンボルの個数を257個までに制限する。この場合に、この問題に対する解決策の1つは、ソースブロックをインターリーブすること、すなわち、異なるソースブロックからのシンボルを混合された順序で送信することである。したがって、全体的には、前のセクションで説明したように、ソースブロックの間のインターリービングを全く有しないことが望ましいが、一部のFEC符号に関しては、複数のソースブロックと、ソースブロックあたりのシンボルの個数とを使用するためにインターリービングを可能にすると同時に、あるソースブロックのオリジナルのストリーミング時間より長い、そのソースブロックの保護期間を可能にすることが、有用である。このセクションでは、ソースブロックをインターリーブするFEC送信機のいくつかの好ましい実施形態を提供する。
【0172】
いくつかの場合に、FEC送信機が異なるソースブロックからのシンボルの送信をインターリーブすることを可能にし、その結果、各ソースブロックのシンボルを、そのソースブロックのストリーミング時間より長い保護期間にまたがって拡散できるようにすることに関する利益がある場合がある。これを行う理由の1つは、時間依存消失(たとえば、バースト的消失)に対するよりよい保護がもたらされること、すなわち、ソースブロックに関する保護期間が長くなるにつれて、固定持続時間のバースト消失に対する保護をもたらすのに、より少ない保護量が必要になることである。あるソースブロックのオリジナルのストリーミング時間を、t秒とすることができ、そのソースブロックの所望の保護期間を、p秒とすることができ、ここで、p>tである。インターリービングを使用するFEC送信機の他の望ましい特性には、(1)ソースパケットがそのオリジナルの順序で送信され、(2)各後続ソースブロックの最後の符号シンボルが受信される時刻が、経時的にできる限り均一に拡散されることが含まれる。
【0173】
第1のインターリービングの特性(ソースパケットがオリジナルの順序で送信される)は、受信機のタイプごとにFEC送信機で導入される待ち時間を最小化し、また、FECの使用が、非FEC受信機の大きい追加の待ち時間を引き起こさない。これは、受信機がストリームに同調する時にFEC受信機で導入される待ち時間をも最小化する、すなわち、FEC受信機が最初にパケットを受信し始める時とそのFEC受信機がそれらを安全に使用可能にし始めることができる時との間の遅延を最小化する。
【0174】
第2のインターリービングの特性(各後続ソースブロックの最後の符号シンボルが受信される時刻が、経時的にできる限り均一に拡散される)は、CPUのより滑らかな使用をもたらす。最後の符号シンボルが、あるソースブロックについて受信される時刻は、そのソースブロックを復号化するためのすべての情報がFEC復号化器から使用可能になる時刻であり、これは、通常、FEC復号化器が規定された復号化待ち時間バジェット内で復号化を終了するために最も激しく働かなければならないワーストケース消失条件の下の時である。したがって、ソースブロックの最後の符号シンボルの受信を均一に拡散することによって、FEC復号化に関するCPUのより滑らかな使用が可能になる。
【0175】
この説明では、多数の例で、FEC送信機がパケットでシンボルを伝送すると仮定し、各パケットは、異なる個数のシンボルを含むことができる。下の説明を単純にするために、オリジナルソースストリームでのソースパケット順序が、0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17などであると仮定し、ここで、この値は、パケットのインデックスを示す。
【0176】
任意の時点にアクティブなs個のソースブロックがあり、ソースブロックあたりk個のソースパケットがあるものとする(この単純化された説明では、すべてのソースパケットが同一の長さであると仮定する)。下のFEC送信機は、ソースブロックがソースパケットからどのように形成されるかと、ソースパケットが送信される順序とを説明するものである。あるソースブロックのリペアパケットは、そのソースブロックのソースパケットの前に、後に、またはそれと混合されてのいずれかで送信することができ、本明細書で説明するように、異なる戦略には利点がある。
【0177】
FEC送信機F:送信パターンは、各n=s・k個のパケットを繰り返し、ここで、nは、保護期間内のソースパケットの個数である。したがって、これは、それぞれがk個のソースパケットのs個のソースブロックに区分された、保護期間内のn個のソースパケットと考えることができる。ソースパケットの送信順序は、そのオリジナルの送信順序である。i=0,...,s−1について、i番目のソースブロックは、ソースパケットi,s+i,2s+i,...,(k−1)・s+iを含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、各ソースブロックの最初のリペアパケットは、各ソースブロックの第2のリペアパケットが送信される前に送信される。それぞれ6個のソースパケットの3つのソースブロックを有する例(したがって、保護期間は、持続時間においてソースパケット18個分である)は、次の通りである。
【0178】
ソースブロック0は、ソースパケット0、3、6、9、12、15を含み、
ソースブロック1は、ソースパケット1、4、7、10、13、16を含み、
ソースブロック2は、ソースパケット2、5、8、11、14、17を含む。
【0179】
FEC送信機Fは、第1のインターリービングの特性を満足するが、第2のインターリービングの特性を満足しない。第1のインターリービングの特性が満足されるのは、単に、ソースパケットの送信順序がオリジナルの送信順序であるからである。FEC送信機Fが、第2のインターリービングの特性を満足しない理由を知るために、連続するソースパケット0、1、2が、それぞれソースブロック0、1、2からのパケットであり、したがって、この3つのソースブロックの復号化時間が、連続するパケットにまたがる、すなわち、ソースブロックのこのインターリービングに関する復号化時間が、繰り返すパターン”1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0...”であることに留意されたい。このパターンでは、各項目が、パケットの受信を示し、1は、その項目がソースブロックのうちの1つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、バースト的であり、均一に拡散してはおらず、したがって、この例から、FEC送信機Fが、上の第2のインターリービングの特性を満足しないことがわかる。
【0180】
FEC送信機G:送信パターンは、各n=s・k個のパケットを繰り返し、ここで、nは、保護期間内のソースパケットの個数である。したがって、これは、それぞれがk個のソースパケットのs個のソースブロックに区分された、保護期間内のn個のソースパケットと考えることができる。ソースパケットの送信順序は、0,k,2k,...,(s−1)・k,1,k+1,2k+1,...,(s−1)・k+1,...,k−1,2k−1,3k−1,...,s・k−1である。i=0,...,s−1について、i番目のソースブロックは、ソースパケットk・i,k・i+1,k・i+2,...,k・i+k−1を含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、各ソースブロックの最初のリペアパケットは、各ソースブロックの第2のリペアパケットが送信される前に送信される。それぞれ6個のソースパケットの3つのソースブロックを有する例(したがって、保護期間は、持続時間においてソースパケット18個分である)は、次の通りである。
【0181】
ソースブロック0は、ソースパケット0、1、2、3、4、5を含み、
ソースブロック1は、ソースパケット6、7、8、9、10、11を含み、
ソースブロック2は、ソースパケット12、13、14、15、16、17を含む。
【0182】
ソースパケットの送信順序は、次の通りである。0、6、12、1、7、13、2、8、14、3、9、15、4、10、16、5、11、17。
【0183】
FEC送信機Gは、第1のインターリービングの特性を満足しないが、第2のインターリービングの特性を満足する。第1のインターリービングの特性が満足されないのは、単に、ソースパケットの送信順序がオリジナルの送信順序ではないからである。FEC送信機Gが、第2のインターリービングの特性を満足する理由を知るために、3つのソースブロックの復号化時間が、これらのパケットにまたがって均一に拡散される、すなわち、ソースブロックのこのインターリービングの復号化時間が、繰り返しパターン1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0...であることに留意されたい。このパターンでは、各項目が、パケットの受信を示し、1は、その項目がソースブロックのうちの1つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、均一に拡散されており、したがって、この例から、FEC送信機Gが、上の第2のインターリービングの特性を満足することがわかる。
【0184】
第1のインターリービングの特性と第2のインターリービングの特性との両方を同時に満足するインターリーブFEC送信機の次の実施形態について、個々のソースブロックごとに、前のセクションで説明した単一ソースブロックFEC送信機の好ましい実施形態が、ソースブロックごとにいつシンボルを送信するかを決定するのに使用されると仮定する。
【0185】
FEC送信機H:ソースパケットの送信順序は、そのオリジナルの送信順序である。このFEC送信機を説明するために、ソースパケットは、概念上、s個の列を有する行列の行に順次配置され、i=0,...,s−1について、列iは、i,s+i,2s+i,...,(k−1)・s+i modulo nのいずれかと合同であるインデックスを有するソースパケットを含む。
【0186】
ソースブロックは、1列の中のソースパケットの連続するシーケンスから形成される。列iの最初のソースブロックは、インデックスiを有するソースパケットから始まる。列i内の各後続のソースブロックは、インデックスfloor(k・i/s)・s+i mod nを有するソースパケットから始まり、したがって、列i内の最初のソースブロックを除くすべてのソースブロックが、k個のソースパケットを含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、列i内の所与のソースブロックのすべてのリペアパケットは、列i内の後続ソースブロックのリペアパケットの前に送信される。それぞれ6個のソースパケットの3つのソースブロックを有する例(したがって、保護期間は、持続時間においてソースパケット18個分である)は、次の通りである。
【0187】
上で説明した行列は、
100
000
010
000
001
000
である。
【0188】
したがって、列0の第1のソースブロックは、ソースパケット0、3、6、9、12、15を含み、列1の第1のソースブロックは、ソースパケット1、4を含み、列1の第2のソースブロックは、ソースパケット7、10、13、16、19、22を含み、列2の第1のソースブロックは、ソースパケット2、5、8、11を含み、列2の第2のソースブロックは、ソースパケット14、17、20、23、26、29を含む、などである。
【0189】
FEC送信機Hは、第1のインターリービングの特性と第2のインターリービングの特性との両方を満足する。第1のインターリービングの特性が満足されるのは、単に、ソースパケットの送信順序がオリジナルの送信順序であるからである。FEC送信機Hが、第2のインターリービングの特性を満足する理由を知るために、ソースブロックのこのインターリービングの復号化時間が、繰り返しパターン”1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0”であることに留意されたい。このパターンでは、各項目が、ソースパケットの受信を示し、1は、その項目がソースブロックのうちの1つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、できる限り均一に拡散されており、したがって、この例から、FEC送信機Fが、上の第2のインターリービングの特性を満足することがわかる。
【0190】
上の特性(1)および(2)を満足し、この開示を読んだ後に見つけることができる、FEC送信機Hの多数の変形形態がある。たとえば、上で説明したFEC送信機Hは、ストリーム内のソースパケットのすべてが同一のサイズである時およびソースパケットのストリーミングレートが一定である時に、良好に働く。下で説明するFEC送信機Iは、ソースパケットが可変長である時および/またはソースパケットのストリーミングレートが一定でない時に良好に働く、FEC送信機Hの変形形態である。
【0191】
FEC送信機I:所望の保護期間がt秒であり、任意の時点にs個のアクティブなソースブロックがあるものとする。この処理を、図13を参照して説明する。図13のステップ1305で、z=t/sに、あるソースブロックの終りと別のソースブロックの始めとの間の秒単位の時間増分をセットし、バイトカウンタB,B,...,Bs−1のすべてを0に初期化する。ステップ1310で、変数iを0に初期化し、現在時刻を0に初期化し、変数iは、どのソースブロックが次に終了するかを記憶するのに使用され、現在時刻は、ソースブロックがいつ終了するかを記憶するのに使用される。ステップ1314で、現在時刻を、FEC送信機のクロックを使用して、ステップ1310で最初に0にセットされた時から経過した時間の長さに従ってインクリメントして、更新する。ステップ1318で、検査を行って、現在時刻がz未満であるかどうかを調べ、これが真である場合には、処理は、ステップ1320に継続して、次のソースパケットが使用可能であるかどうかを調べる。使用可能なソースパケットがない場合には、処理はステップ1314に戻るが、使用可能な次のソースパケットがある場合には、ステップ1330で、次のソースパケットを受け入れ、Xは、バイト単位のそのソースパケットのサイズである。ステップ1340で、Bが最小になるインデックスjを計算する。ステップ1350で、受け入れたばかりのソースパケットをソースブロックjに追加し、ステップ1360で、Bの値をこのソースパケットのサイズXだけインクリメントし、処理は、ステップ1314に戻る。そうではなく、ステップ1318で、現在時刻が少なくともzである場合には、ステップ1370で、zの値をt/sだけインクリメントし、ステップ1380で、iの値を、1つインクリメントし、アクティブなソースブロックの個数sを法とする剰余をとり、ステップ1390で、インデックスiを有する現在のソースブロックを終了し、インデックスiを有する新しいソースブロックを開始し、その後、処理はステップ1314に戻る。
【0192】
この処理がどのように働くかの例として、t=6秒かつs=3であり、したがって、t/s=2であるものとする。最初の2秒のうちに受け取られるソースパケットが、次の通りであるものとする。
【0193】
サイズが500バイトのソースパケット0
サイズが750バイトのソースパケット1
サイズが400バイトのソースパケット2
サイズが490バイトのソースパケット3
サイズが700バイトのソースパケット4
また、同一の極小値を有する複数のバイトカウンタがある場合に、最小のインデックスを有するバイトカウンタを、最小であると考えるものとする。すると、ソースパケット0は、ソースブロック0に追加され、B=500であり、ソースパケット1は、ソースブロック1に追加され、B=750であり、ソースパケット2は、ソースブロック2に追加され、B=400であり、ソースパケット3は、ソースブロック2に追加され、B=890であり、ソースパケット4は、ソースブロック0に追加され、B=1200である。
【0194】
同一の例を継続すると、現在時刻が2秒に達する時に、ソースブロック1は、終了し、サイズ750バイトのソースパケット1だけを含み、新しいソースブロック1が、開始される。次が、後続の2秒に送信機に到着するソースパケットのシーケンスを記述するものとする。
【0195】
サイズが500バイトのソースパケット5
サイズが380バイトのソースパケット6
サイズが400バイトのソースパケット7
サイズが600バイトのソースパケット8
サイズが700バイトのソースパケット9
サイズが400バイトのソースパケット10
サイズが350バイトのソースパケット11
サイズが800バイトのソースパケット12
サイズが200バイトのソースパケット13
サイズが500バイトのソースパケット14
この時点で、ソースブロック2は、終了し、合計2770バイトのソースパケットすなわち、ソースパケット2、3、6、9、12を含み、新しいソースブロック2が、開始される。次のソースパケットのシーケンスが、後続の2秒に送信機に到着するものとする。
【0196】
サイズが350バイトのソースパケット15
サイズが500バイトのソースパケット16
サイズが450バイトのソースパケット17
サイズが800バイトのソースパケット18
サイズが650バイトのソースパケット19
サイズが400バイトのソースパケット20
サイズが600バイトのソースパケット21
サイズが350バイトのソースパケット22
サイズが200バイトのソースパケット23
サイズが600バイトのソースパケット24
この時点で、ソースブロック0は、終了し、合計4150バイトのソースパケットすなわち、ソースパケット0、4、7、10、13、14、17、20、および21を含み、新しいソースブロック0が、開始される。
【0197】
FEC送信機Iは、各列に割り振られるソースパケットのバイトの総数が、各時点でできる限り等しくなり、ソースブロックの復号化時間が、z=t/sの区間で経時的に等しく拡散されるという特性を有する。ソースパケットレートが一定であり、ソースパケットサイズがすべて同一である場合に、FEC送信機Iが、本質的にFEC送信機Hと同一の解決策をもたらすことに留意されたい。たとえば、上の例で、それぞれ2秒の6つのソースパケットがあり、ソースパケットのすべてがサイズにおいて1000バイトである場合に、FEC送信機Iは、次の行列を作る。
【0198】
000
010
000
001
000
100
000
010
000
001
000
100
この例では、各ソースブロック内のソースパケットの個数が6であり、インターリービングパターンが、上のFEC送信機Hに関するインターリービングの例の単純なシフトであることに留意されたい。
【0199】
本発明を、例示的実施形態に関して説明してきたが、当業者は、多数の変更が可能であることを認めるであろう。たとえば、本明細書で説明した処理は、ハードウェア構成要素、ソフトウェア構成要素、および/またはその任意の組合せを使用して実施することができる。したがって、本発明を、例示的実施形態に関して説明したが、本発明が、添付の特許請求の範囲の範囲に含まれるすべての修正形態および同等物を含むことが意図されていることを了解されたい。

【特許請求の範囲】
【請求項1】
符号化器からチャネルを介して受信される受信シンボルからデータを復号化するデータ復号化器における復号化の方法であって、該受信データは消去が含まれ得かつソースシンボルおよびリペアシンボルが含まれ、また、該復号化器は復号化に可逆である任意の正方行列である生成行列を使用しており、それにより該復号化器はソースシンボルおよびリペアシンボルの到着と同時に復号化動作を実行可能であり、該方法は、
少なくとも一部が前記生成行列から導出される連立方程式を復号化メモリ内で表現するステップと、
全てのソースシンボルを受信する前に、ソースシンボルが受信されると当該受信されたソースシンボルを前記連立方程式に代入するステップと、
リペアシンボルが到着すると、復号化ロジックを使用して前記連立方程式を解くのに使用されるリペア式を識別するステップと、
ソースシンボルが到着すると、復号化ロジックを使用して式のベクトル値を計算するステップと、
リペアシンボルが前記復号化器に到着すると、前記連立方程式を上三角形式に変換するステップと、
を含むことを特徴とする方法。
【請求項2】
符号の前記リペアシンボルは前記ソースシンボルより前に前記復号化器で受信され、復号化動作はインプレーンで実行されることを特徴とする請求項1に記載の方法。
【請求項3】
2次元リードソロモン符号が作用される前に、符号化器においてソースシンボルに対する置換が作用されることを特徴とする請求項1に記載の方法。
【請求項4】
前記置換は、ランダムまたは擬似ランダムであることを特徴とする請求項3に記載の方法。
【請求項5】
前記置換は、元の順番において隣接するシンボルが前記符号の同一行または同一列に出現しないようなものであることを特徴とする請求項3に記載の方法。
【請求項6】
前記置換は、2つの置換σおよびσにより導出され、kを前記コードの行または列の個数としたとき、前記ソースブロック内の位置(i,j)のシンボルs[i,j]の写像である前記2つの置換により置換されたソースブロック内の位置(i,j)のシンボルs’[i,j]が、s’[i,j]=s[(σ(j)+σ(i))%k,j]を満たすようなものであることを特徴とする請求項5に記載の方法。
【請求項7】
前記生成行列は、該生成行列の行単位で生成された2以上のリペアシンボルにより増大する符号の生成行列であることを特徴とする請求項1に記載の方法。
【請求項8】
前記生成行列は、正則LDGM符号、非正則LDGM符号、正則LDGM階段符号、非正則LDGM階段符号、正則LDGM三角符号、非正則LDGM三角符号、正則Copper符号、非正則Copper符号、または、ファウンテン符号の生成行列であることを特徴とする請求項1に記載の方法。
【請求項9】
前記生成行列は、エラー訂正符号の生成行列であることを特徴とする請求項1に記載の方法。
【請求項10】
前記生成行列は、エラー訂正符号および消去符号の生成行列であることを特徴とする請求項1に記載の方法。
【請求項11】
チャネルを介して送信されるデータを符号化するデータ符号化器において、符号化されるデータであるソースシンボルと欠落したソースシンボルに関する情報を再生するのに使用可能なリペアシンボルとを含む符号化データを生成する方法であって、前記ソースシンボルは順序付けられた複数のソースシンボルとして符号化され、該方法は、
前記ソースシンボルから前記リペアシンボルへの符号化を表現する生成行列を取得するステップと、
前記ソースシンボルの少なくともいくつかを読み取るステップと、
前記ソースシンボルの少なくともいくつかを、前記順序付けられた複数のソースシンボル内のソースシンボルの順番に対応する符号化セット内の順番で符号化セットの符号化シンボルとして含めるステップと、
ソースシンボルの並べ替えセットを形成するため、1以上の並べ替え規則のセットに従って前記ソースシンボルを並べ替えるステップと、
リペアシンボルのセットを形成するため、前記ソースシンボルの並べ替えセットに前記生成行列を作用させるステップと、
前記符号化データと前記リペアシンボルのセットとして符号化セットを出力するステップと、
を含むことを特徴とする方法。
【請求項12】
出力する前記ステップは、読み取る前記ステップ、並べ替える前記ステップ、および、作用させる前記ステップが完了した後にのみ実行されることを特徴とする請求項11に記載の方法。
【請求項13】
前記符号化セットを出力する前記ステップは、作用させる前記ステップが完了する前に実行されることを特徴とする請求項11に記載の方法。
【請求項14】
前記並べ替え規則は、前記符号化器に既知でありデータ復号化器において決定可能な擬似ランダムシーケンスに従って並べ替えることを含むことを特徴とする請求項11に記載の方法。
【請求項15】
ソースシンボルの前記並べ替えセットは、物理的に並べ替えられたシンボルのセットであることを特徴とする請求項11に記載の方法。
【請求項16】
ソースシンボルの前記並べ替えセットは、論理的に並べ替えられたシンボルのセットであり、並べ替えられる前のメモリに格納されたシンボルはメモリ位置の変更のために移動またはコピーをする必要が無いことを特徴とする請求項11に記載の方法。
【請求項17】
作用させる前記ステップにおいて前記ソースシンボルが元の順番以外の順番となるように前記生成行列を作用させることにより、ソースシンボルの前記並べ替えセットは並べ替えられることを特徴とする請求項11に記載の方法。

【図1】
image rotate

【図2】
image rotate

【図3A】
image rotate

【図3B】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate


【公開番号】特開2012−249303(P2012−249303A)
【公開日】平成24年12月13日(2012.12.13)
【国際特許分類】
【外国語出願】
【出願番号】特願2012−154721(P2012−154721)
【出願日】平成24年7月10日(2012.7.10)
【分割の表示】特願2008−516031(P2008−516031)の分割
【原出願日】平成18年6月12日(2006.6.12)
【出願人】(501114844)デジタル ファウンテン, インコーポレイテッド (25)
【Fターム(参考)】