(57)【要約】  符号化器からチャネルを介して受信される受信シンボルからデータを復号化するデータ復号化器であって、受信データには、消去が含まれ得かつソースシンボルおよびリペアシンボルが含まれ、復号化器は、復号化において可逆である任意の正方行列である生成行列を使用し、復号化器は、ソースシンボルおよびリペアシンボルの到着と同時に復号化動作を実行できるようになっており、データ復号化の方法は、少なくとも部分的に生成行列から導出される連立方程式を復号化メモリ内で表現し、すべてのソースシンボルを受信する前に、ソースシンボルが受信されると受信されたソースシンボルを連立方程式に代入し、復号化ロジックを使用して、リペアシンボルが到着すると連立方程式を解くのに使用されるリペア式を識別し、復号化ロジックを使用して、ソースシンボルが到着すると式のベクトル値を計算し、リペアシンボルが復号化器に到着すると連立方程式を上三角形式に変換することを含む。新規の方法は、ＦＥＣ符号の大きいクラスの符号化構造のインターリーブおよび指定、パケットの送信のスケジューリング、および類似物に使用することができる。
2008546361.tif 000002
【特許請求の範囲】
【請求項１】
符号化器からチャネルを介して受信される受信シンボルからデータを復号化するデータ復号化器における復号化の方法であって、該受信データは消去が含まれ得かつソースシンボルおよびリペアシンボルが含まれ、また、該復号化器は復号化に可逆である任意の正方行列である生成行列を使用しており、それにより該復号化器はソースシンボルおよびリペアシンボルの到着と同時に復号化動作を実行可能であり、該方法は、
少なくとも一部が前記生成行列から導出される連立方程式を復号化メモリ内で表現するステップと、
全てのソースシンボルを受信する前に、ソースシンボルが受信されると当該受信されたソースシンボルを前記連立方程式に代入するステップと、
リペアシンボルが到着すると、復号化ロジックを使用して前記連立方程式を解くのに使用されるリペア式を識別するステップと、
ソースシンボルが到着すると、復号化ロジックを使用して式のベクトル値を計算するステップと、
リペアシンボルが前記復号化器に到着すると、前記連立方程式を上三角形式に変換するステップと、
を含むことを特徴とする方法。
【請求項２】
符号の前記リペアシンボルは前記ソースシンボルより前に前記復号化器で受信され、復号化動作はインプレーンで実行されることを特徴とする請求項１に記載の方法。
【請求項３】
２次元リードソロモン符号が作用される前に、符号化器においてソースシンボルに対する置換が作用されることを特徴とする請求項１に記載の方法。
【請求項４】
前記置換は、ランダムまたは擬似ランダムであることを特徴とする請求項３に記載の方法。
【請求項５】
前記置換は、元の順番において隣接するシンボルが前記符号の同一行または同一列に出現しないようなものであることを特徴とする請求項３に記載の方法。
【請求項６】
前記置換は、２つの置換σ１およびσ２により導出され、ｋを前記コードの行または列の個数としたとき、前記ソースブロック内の位置（ｉ，ｊ）のシンボルｓ［ｉ，ｊ］の写像である前記２つの置換により置換されたソースブロック内の位置（ｉ，ｊ）のシンボルｓ’［ｉ，ｊ］が、ｓ’［ｉ，ｊ］＝ｓ［（σ１（ｊ）＋σ２（ｉ））％ｋ，ｊ］を満たすようなものであることを特徴とする請求項５に記載の方法。
【請求項７】
前記生成行列は、該生成行列の行単位で生成された２以上のリペアシンボルにより増大する符号の生成行列であることを特徴とする請求項１に記載の方法。
【請求項８】
前記生成行列は、正則ＬＤＧＭ符号、非正則ＬＤＧＭ符号、正則ＬＤＧＭ階段符号、非正則ＬＤＧＭ階段符号、正則ＬＤＧＭ三角符号、非正則ＬＤＧＭ三角符号、正則Ｃｏｐｐｅｒ符号、非正則Ｃｏｐｐｅｒ符号、または、ファウンテン符号の生成行列であることを特徴とする請求項１に記載の方法。
【請求項９】
前記生成行列は、エラー訂正符号の生成行列であることを特徴とする請求項１に記載の方法。
【請求項１０】
前記生成行列は、エラー訂正符号および消去符号の生成行列であることを特徴とする請求項１に記載の方法。
【請求項１１】
チャネルを介して送信されるデータを符号化するデータ符号化器において、符号化されるデータであるソースシンボルと欠落したソースシンボルに関する情報を再生するのに使用可能なリペアシンボルとを含む符号化データを生成する方法であって、前記ソースシンボルは順序付けられた複数のソースシンボルとして符号化され、該方法は、
前記ソースシンボルから前記リペアシンボルへの符号化を表現しする生成行列を取得するステップと、
前記ソースシンボルの少なくともいくつかを読み取るステップと、
前記ソースシンボルの少なくともいくつかを、前記順序付けられた複数のソースシンボル内のソースシンボルの順番に対応する符号化セット内の順番で符号化セットの符号化シンボルとして含めるステップと、
ソースシンボルの並べ替えセットを形成するため、１以上の並べ替え規則のセットに従って前記ソースシンボルを並べ替えるステップと、
リペアシンボルのセットを形成するため、前記ソースシンボルの並べ替えセットに前記生成行列を作用させるステップと、
前記符号化データと前記リペアシンボルのセットとして符号化セットを出力するステップと、
を含むことを特徴とする方法。
【請求項１２】
出力する前記ステップは、読み取る前記ステップ、並べ替える前記ステップ、および、作用させる前記ステップが完了した後にのみ実行されることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記符号化セットを出力する前記ステップは、作用させる前記ステップが完了する前に実行されることを特徴とする請求項１１に記載の方法。
【請求項１４】
前記並べ替え規則は、前記符号化器に既知でありデータ復号化器において決定可能な擬似ランダムシーケンスに従って並べ替えることを含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
ソースシンボルの前記並べ替えセットは、物理的に並べ替えられたシンボルのセットであることを特徴とする請求項１１に記載の方法。
【請求項１６】
ソースシンボルの前記並べ替えセットは、論理的に並べ替えられたシンボルのセットであり、並べ替えられる前のメモリに格納されたシンボルはメモリ位置の変更のために移動またはコピーをする必要が無いことを特徴とする請求項１１に記載の方法。
【請求項１７】
作用させる前記ステップにおいて前記ソースシンボルが元の順番以外の順番となるように前記生成行列を作用させることにより、ソースシンボルの前記並べ替えセットは並べ替えられることを特徴とする請求項１１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にはＦＥＣ符号に関し、具体的にはストリーミングアプリケーション用のＦＥＣ符号に関する。
【背景技術】
【０００２】
最近、伝送中にストリーミングメディアを保護するのにＦＥＣ符号を検討することが、一般的な実践になってきた。パケットネットワークを介して送信される時に（パケットネットワークの例には、インターネットと、３ＧＰＰ、３ＧＰＰ２、およびＤＶＢなどのグループによって標準化されたものなどの無線ネットワークとが含まれる）、ソースストリームは、生成される時または使用可能にされる時にパケットに配置され、したがって、パケットは、ソースストリームが生成される順序またはソースストリームが受信機から使用可能にされる順序でソースストリームを搬送するのに使用される。これらのタイプのシナリオへのＦＥＣ符号の通常の応用では、ＦＥＣ符号は、ソースストリームを含むオリジナルのソースパケットに追加のリペアパケットを追加するのに使用され、これらのリペアパケットは、ソースパケット消失が発生する時に、受信されたリペアパケットを使用して、失われたソースパケットに含まれるデータを回復できるという特性を有する。他の例では、部分的なパケット消失が発生することが可能である、すなわち、受信機が、パケットの他の部分を受信しながらそのパケットの諸部分を失う場合があり、したがって、これらの例では、完全にまたは部分的に受信されたリペアパケットを使用して、完全にまたは部分的に失われたソースパケットを回復することができる。もう１つの例では、他のタイプの破損が、送信されたデータに対して発生する可能性があり、たとえば、ビットの値が反転される場合があり、したがって、リペアパケットを使用して、そのような破損を訂正し、ソースパケットのできる限り正確な回復をもたらすことができる。他の例では、ソースストリームを、必ずしも離散的パケットで送信するのではなく、その代わりに、たとえば連続的ビットストリームとして送信することができる。
【０００３】
ソースストリームの保護を実現するのに使用できるＦＥＣ符号の多数の例がある。リードソロモン符号は、通信システムでのエラーおよび消去訂正のための周知の符号である。たとえばパケットデータネットワークでの消去訂正について、リードソロモン符号の周知の効率的実施は、”L.Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols", Computer Communication Review, 27(2):24-36(April 1997)”(以下”Ｒｉｚｚｏ”)、および、”Bloemer,ET AL., "An XOR-Based Erasure-Resilient Coding Scheme", Technical Report TR-95-48, International Computer Science Institute, Berkeley, California (1995)”（以下”ＸＯＲ−Ｒｅｅｄ−Ｓｏｌｏｍｏｎ”）に記載のコーシー行列またはバンデルモンド行列を使用することである。ＦＥＣ符号の他の例には、その全体が本明細書に組み込まれている米国特許第６３０７４８７号（以下では”ＬｕｂｙＩ”）および米国特許出願第２００３／００５８９５８号（以下では”ＳｈｏｋｒｏｌｌａｈｉＩ”）に記載のものなどのＬＤＰＣ符号、連鎖符号、およびマルチステージ連鎖符号が含まれる。
【０００４】
リードソロモン符号の変形に関するＦＥＣ復号化処理の例が、”Ｒｉｚｚｏ”および”ＸＯＲ−Ｒｅｅｄ−Ｓｏｌｏｍｏｎ”に記載されている。これらの例では、復号化は、十分なソースデータパケットおよびリペアデータパケットが受信されたならば、適用される。復号化処理は、計算集中型である場合があり、使用可能なＣＰＵリソースに応じて、ブロック内のメディアがまたがる時間の長さに対して、相対的に、完了にかなりの時間を要する場合がある。受信機は、メディアストリームの受信の始まりとそのメディアの再生との間に必要な遅延を計算する時に、復号化に必要なこの時間の長さを考慮に入れなければならない。復号化に起因するこの遅延は、特定のメディアストリームに関するユーザの要求と再生の始まりとの間の遅延としてユーザによって知覚される。したがって、この遅延を減らすことが望ましい。
【０００５】
多くのアプリケーションで、パケットは、シンボルにさらに副分割され、このシンボルに、ＦＥＣ処理が適用される。シンボルは、任意のサイズとすることができるが、しばしば、シンボルのサイズは、多くともパケットのサイズと等しい。以下では、我々は、符号化ブロックを含むシンボルを”ソースシンボル”と呼び、ＦＥＣ処理中に生成されるシンボルを”符号シンボル”と呼ぶ。一部のＦＥＣ符号、特にリードソロモン符号について、符号化時間および復号化時間は、ソースブロックあたりの符号シンボルの個数が増えるにつれて、非実用的に増大する。したがって、実際には、ソースブロック当たりに生成できる符号シンボルの総数に対する上限、たとえば２５５個が、しばしば存在する。シンボルは、別々のパケットペイロードに配置されるので、これは、ソースブロックの符号化での最大長に対する実用的上限を設け、たとえば、パケットペイロードが多くとも１０２４バイトである場合に、符号化されたソースブロックは、多くとも２５５ＫＢ（キロバイト）であり、これは、もちろん、ソースブロック自体のサイズに関する上限でもある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ソースストリーミングレートについて行くのに十分に高速のソースブロックを復号化できること、ＦＥＣ復号化によって導入される復号化待ち時間を最小化することができること、およびＦＥＣ復号化中の任意の時点に受信デバイスで使用可能なＣＰＵの小さい割合だけを使用することなどの他の考慮事項が、問題である。
【０００７】
したがって、改善された処理および装置を有することが望ましい。
【課題を解決するための手段】
【０００８】
本発明の実施形態は、ＦＥＣ符号化されたソースブロックからのパケットの受信と同時に、復号化に付随する計算の重要な部分を実行する方法を提示する。したがって、復号化遅延、すなわち、ソースブロックの最後のパケットの受信の後、回復されたソースブロックが使用可能になる前の遅延は、計算の残りの部分を実行するのに必要な時間まで減らされ、この計算の残りの部分は、一般に、復号化作業全体の小さい分数である。
【０００９】
いくつかの実施形態で、符号化器からチャネルを介して受信されるシンボルからデータを復号化するデータ復号化器が使用され、ここで、受信されたデータには、消去が含まれる可能性があり、ソースシンボルおよびリペアシンボルが含まれ、この復号化器は、復号化において、生成行列すなわち、可逆である任意の正方行列を使用し、復号化器が、ソースシンボルおよびリペアシンボルの到着と同時に復号化動作を実行できるようになっており、少なくとも部分的に生成行列から導出される連立方程式を復号化器メモリ内で表すことと、すべてのソースシンボルを受信する前に、ソースシンボルが受信される時に、受信されたソースシンボルを連立方程式に代入することと、復号化器論理を使用して、リペアシンボルが到着する時に、連立法的式を解くのに使用されるリペア式を識別することと、復号化器論理を使用して、ソースシンボルが到着する時に、式のベクトル値を計算することと、リペアシンボルが復号化器に到着する時に連立方程式を上三角形式に変換することとを含む方法が、提供される。
【００１０】
いくつかの実施形態で、利益を得るために２Ｄリードソロモン符号と他の関連する符号とをインターリーブする新規の方法が使用される。いくつかの実施形態は、ＦＥＣ符号の大きいクラスの符号化構造を指定する、新規の一般的な簡潔な機構を使用することができる。
【００１１】
諸実施形態は、ソースブロックのパケットの送信をスケジューリングする新規の方法をも提示する。この方法の利益の一部には、ＦＥＣエンドツーエンド待ち時間の最小化、ＦＥＣ受信機待ち時間の最小化、ＦＥＣ符号化されるストリームのできる限り滑らかなレートでの伝送、ソースブロックのパケットで送信されるデータの時間にまたがるできる限り均一な拡散、およびＦＥＣ受信機での単純な論理要件が含まれる。
【００１２】
諸実施形態は、ソースブロックをインターリーブする新規の方法をも提示する。これは、個々のソースブロック内での伝送における消失またはエラーを、インターリーブが使用されない場合よりはるかに長い時間期間にわたって拡散させることを可能にし、受信機によって知覚される復号化待ち時間を最小値まで減らしながら、ソースデータのオリジナルの送信順序をも維持することを可能にする。
【００１３】
次の詳細な説明は、添付図面と一緒に、本発明の性質および利点のよりよい理解をもたらす。
【発明を実施するための最良の形態】
【００１４】
本明細書で説明する実施形態は、復号化遅延を減らすためのＦＥＣ符号化されたソースブロックからのパケットの受信と同時の復号化など、ネットワークまたは類似物を介して受信されたデータの復号化を実行する新規の方法を提供する。以下では、本明細書で説明する処理および方法を連続ビットストリームネットワークなどの他のタイプの伝送ネットワークにどのように適用できるかを当業者が簡単に理解できることを認識して、データを搬送するネットワークを、本明細書での説明を単純にするためにパケットベースであると仮定する。以下では、本明細書で説明する処理および方法をビット反転などの他のタイプのデータ伝送破損にどのように適用できるかを当業者が簡単に理解できることを認識して、本明細書での説明を単純にするために、ＦＥＣ符号が、失われたパケットまたはパケット内の失われた部分的データに対する保護をもたらすと仮定する。
【００１５】
図１は、連鎖符号を使用する通信システム１００のブロック図である。通信システム１００内では、入力ファイル１０１または入力ストリーム１０５が、入力シンボル生成器１１０に供給される。入力シンボル生成器１１０は、入力ファイルまたは入力ストリームから１つまたは複数の入力シンボルのシーケンス（ＩＳ（０），ＩＳ（１），ＩＳ（２），．．．）を生成し、各入力シンボルは、値および位置を有する（図１では、括弧に囲まれた整数として示す）。入力シンボルの可能な値すなわち入力シンボルのアルファベットは、通常、２Ｍ個のシンボルのアルファベットであり、その結果、各入力シンボルは、入力ファイルのＭビットについて符号化するようになる。Ｍの値は、一般に、通信システム１００の用途によって決定されるが、汎用システムは、入力シンボル生成器１１０に関するシンボルサイズ入力を含むことができ、その結果、Ｍを、用途ごとに変更することができるようになる。入力シンボル生成器１１０の出力は、符号化器１１５に供給される。
【００１６】
キー生成器１２０は、符号化器１１５によって生成される出力シンボルごとにキーを生成する。各キーは、ＬｕｂｙＩまたはＳｈｏｋｒｏｌｌａｈｉＩに記載の方法のうちの１つ方法に従って、または、キーが、このキー生成器もしくは別のキー生成器のどちらによって生成されるのであれ、同一の入力ファイルについてまたは１つのストリーム内のデータの同一のブロックについて生成されるキーの大きい分数が一意であることを保証する任意の匹敵する方法に従って、生成することができる。たとえば、キー生成器１２０は、カウンタ１２５の出力、一意ストリーム識別器１３０、および／または乱数生成器１３５の出力の組合せを使用して、各キーを作ることができる。キー生成器１２０の出力は、符号化器１１５に供給される。他の例、たとえば一部のストリーミングアプリケーションでは、キーの組を、固定し、ストリーム内のデータのブロックごとにもう一度再利用することができる。通常の実施形態では、生成できるキーの個数は、入力ファイルまたはストリームのサイズまたは他の特性ではなく、キー生成器の分解能によって示される。たとえば、入力が、１万個以下程度のシンボルになると期待される場合に、キー分解能は、３２ビットとすることができ、これは、４０億個までの一意のキーを可能にする。これらの関連する数の結果の１つは、キーに従って符号化する符号化器を、入力の１万個のシンボルについて４０億個の一意の出力シンボルを生成できるものとすることができることがである。現実的な問題として、ほとんどの通信システムは、４０００００個のシンボルのすべてではなくそのうちの１つだけを失い、したがって、４０億個もの出力シンボルを生成する必要はなく、したがって、可能なキーの個数は、効果的に無制限として扱うことができ、繰り返される必要はなく、キーの２つの独立の選択が同一のキーをつかむ可能性は、ほとんどないほどに小さい。しかし、なんらかの理由でそうなる場合には、キー生成器の分解能を高めることができ、その結果、キーを使用する処理は、キーの終りのない供給があるかのように振る舞うことができるようになる。
【００１７】
キー生成器１２０によって供給される各キーＩから、符号化器１１５は、入力シンボル生成器によって供給される入力シンボルからの、値Ｂ（Ｉ）を有する出力シンボルを生成する。各出力シンボルの値は、そのキーと、本明細書で出力シンボルの”付随する入力シンボル”または単に出力シンボルの”付随物(associates)”と称する、入力シンボルのうちの１つまたは複数のある関数とに基づいて生成される。必ずではないが通常、Ｍは、入力シンボルおよび出力シンボルについて同一である、すなわち、これらの両方が、同一ビット数について符号化する。
【００１８】
いくつかの実施形態で、入力シンボルの個数Ｋは、符号化器によって、付随物を選択するのに使用される。入力がストリームであり、Ｋがそのストリーム内の各ブロックの間で変化し得る場合など、Ｋが、前もっては知られない場合には、Ｋを、単に推定値とすることができる。値Ｋが、符号化器１１５によって、入力シンボルのストレージを割り振るのに使用される場合もある。
【００１９】
符号化器１１５は、送信モジュール１４０に出力シンボルを供給する。送信モジュール１４０は、キー生成器１２０から各そのような出力シンボルのキーをも供給される。送信モジュール１４０は、出力シンボルを送信し、使用されるキーイング方法に応じて、送信モジュール１４０は、送信される出力シンボルのキーに関するあるデータをも、チャネル１４５を介して受信モジュール１５０に送信することができる。チャネル１４５は、消去チャネルであると仮定されるが、これは、通信システム１００の正しい動作の要件ではない。モジュール１４０、１４５、および１５０は、送信モジュール１４０が、出力シンボルおよびそのキーに関するすべての必要なデータをチャネル１４５に送信するように適合され、受信モジュール１５０が、シンボルおよび潜在的にそのキーに関するいくつかのデータをチャネル１４５から受信するように適合される限り、任意の適切なハードウェア構成要素、ソフトウェア構成要素、物理媒体、またはその任意の組合せとすることができる。Ｋの値が、付随物を判定するのに使用される場合に、Ｋの値を、チャネル１４５を介して送信することができ、あるいは、符号化器１１５および復号化器１５５の合意によって前もってセットすることができる。
【００２０】
チャネル１４５は、インターネットを介する経路、テレビジョン送信機からテレビジョン受信側への放送リンク、またはある地点から別の地点への電話接続などのリアルタイムチャネルとすることができ、あるいは、チャネル１４５は、ＣＤ−ＲＯＭ、ディスクドライブ、ウェブサイト、または類似物などのストレージチャネルとすることができる。チャネル１４５は、ある人がパーソナルコンピュータから電話回線を介してインターネットサービスプロバイダ（ＩＳＰ）に入力ファイルを送信し、その入力ファイルがウェブサーバに格納され、その後にインターネットを介して受信側に送信される時に形成されるチャネルなど、リアルタイムチャネルおよびストレージチャネルの組合せとすることさえできる。
【００２１】
チャネル１４５が、パケットネットワークを含む場合に、通信システム１００は、任意の複数のパケットの相対順序が、チャネル１４５を介する移動中に保存されると仮定することができない場合がある。したがって、出力シンボルのキーは、上で説明したキーイング方式のうちの１つまたは複数を使用して判定され、必ずしも出力シンボルが受信モジュール１５０を出る順序によって決定されるのではない。
【００２２】
受信モジュール１５０は、出力シンボルを復号化器１５５に供給し、受信モジュール１５０が受信する、これらの出力シンボルのキーに関するすべてのデータが、キー再生器１６０に供給される。キー再生器１６０は、受け取った出力シンボルのキーを再生し、これらのキーを復号化器１５５に供給する。復号化器１５５は、キー再生器１６０によって供給されたキーを、対応する出力シンボルと一緒に使用して、入力シンボル（やはりＩＳ（０），ＩＳ（１），ＩＳ（２），．．．）を回復する。復号化器１５５は、回復されたシンボルを入力ファイル再組立器１６５に供給し、入力ファイル再組立器１６５は、入力ファイル１０１のコピー１７０または入力ストリーム１０５のコピー１７５を生成する。
【００２３】
メディアストリーミングアプリケーション
メディアストリーミングアプリケーションで使用される時に、ソースメディアストリームを形成するソースパケットは、時々、ソースブロックと呼ばれるグループに集められる。たとえば、ソースブロックを、固定された長さの時間にまたがるソースパケットのグループとすることができ、リードソロモン消去符号を、ソースブロックのオリジナルのソースパケットと一緒に受信機に送信されるリペアパケットを生成するために、これらのソースブロックに独立に適用することができる。
【００２４】
送信機では、ソースストリームは、ソースパケットが到着する時にソースブロックに連続して区分され、その後、リペアパケットが、ソースブロックごとに生成され、送信される。特に生のまたは対話型のストリーミングアプリケーションについて、ＦＥＣ符号の使用によって追加される総エンドツーエンド遅延を最化にすることが好ましく、したがって、ＦＥＣ解決策の全体的設計が、ソースパケットが送信の前に送信機でできる限り短く遅延され、あるソースブロックのすべてのソースパケットおよびリペアパケットが、できる限り短い総遅延で送信されるるものになっているならば、好ましい。また、ＦＥＣ符号化されたストリームのレートが、できる限り滑らかである、すなわち、ＦＥＣ符号化されたストリームレートにできる限り少ない変動性がある、または少なくともオリジナルのソースストリームに既に存在するどの変動性の増幅も存在しないならば、好ましい。というのは、これが、ＦＥＣ符号化されたストリームの帯域幅使用量をより予測可能にし、ネットワークおよび他のおそらくは競合するストリームに対する影響を最小化するからである。また、あるソースブロックのパケット内で送信されるデータが、パケットがそのソースブロックについて送信される期間にわたってできる限り均一に拡散されることが好ましい。というのは、これが、バースト消失に対する最良の保護をもたらすからである。また、受信機のＦＥＣ論理が、できる限り単純である、すなわち、複数のソースブロックからのパケットの同時受信をできる限り回避するならば、好ましい。したがって、ＦＥＣ送信機が、できる限り、あるソースブロックからのすべてのパケットを、後続ソースブロックからのパケットを送信する前に送信することが好ましい。
【００２５】
受信機では、パケットが失われるか、エラー（たとえばＣＲＣ検査を使用して、検出し、破棄することができる）を伴って受信される場合に、十分なリペアパケットが受信済みであると仮定すると、それらのリペアパケットを使用して、失われたソースパケットを回復することができる。
【００２６】
いくつかのアプリケーションで、パケットは、さらに、シンボルに副分割され、これらのシンボルに、ＦＥＣ処理が適用される。いくつかのＦＥＣ符号、特にリードソロモン符号について、符号化時間および復号化時間は、ソースブロックあたりの符号シンボルの個数が増えるにつれて非現実的に増え、しばしば、ソースブロックあたりに生成できる符号シンボルの総数に対する上限がある。シンボルは、異なるパケットペイロードに配置されるので、これは、ソースブロックの符号化での最大長に対する実用的上限を設け、これは、もちろん、ソースブロック自体のサイズに対しても上限を設ける。
【００２７】
多くのアプリケーションについて、保護が、長い時間期間にわたって提供されなければならないとき、またはメディアストリーミングレートが高いときには、最大ソースブロックサイズを超える、データに対する保護を提供することが有利でありえる。この場合に、最大ソースブロックサイズより短いソースブロックを使用し、その後、異なるソースブロックからのソースパケットをインターリーブすることによって、個々のソースブロックからのソースパケットがより長い時間期間にわたって拡散される解決策がもたらされる。
【００２８】
しかし、もう１つの関心事は、ソースストリーミングレートについて行くのに十分に高速にソースブロックを復号化でき、ＦＥＣ復号化によって導入される復号化待ち時間を最小化でき、ＦＥＣ復号化中のどの時点においても受信するデバイスで使用可能なＣＰＵの小さい分数だけを使用できることである。さらに、ソースパケットのオリジナルの送信順序を変更しないことが重要である。したがって、ソースパケットのオリジナルの送信順序を尊重し、各ソースブロックのＦＥＣ復号化を時間にわたってできる限り均等に拡散することを可能にし、ＦＥＣ復号化待ち時間を最小化する、ソースブロックインターリービングを使用することが望ましい。本明細書で説明するさまざまな実施形態は、これらの利点のうちの１つまたは複数を実現する。
【００２９】
用語
ＦＥＣ符号
この説明では、符号化されるデータ（ソースデータ）が、等しい長さの”シンボル”に分解されており、シンボルは、任意の長さ（単一ビットまで）とすることができる。シンボルは、データネットワークを介してパケット内で搬送することができ、シンボルの総数は、各パケット内で明示的に搬送されるか、暗示される。いくつかの場合に、ソースパケットがシンボル長の倍数ではないことが可能であり、その場合に、パケット内の最後のシンボルを切り詰めることができる。この場合に、ＦＥＣ符号において、この最後のシンボルは、ビットの固定パターン、たとえば０の値のビットによってパディングされると暗黙のうちに仮定され、その結果、これらのビットはパケット内で搬送されないが、受信機は、それでも、この最後の切り詰められたシンボルを完全なシンボルに充填することができるようになる。他の実施形態では、ビットの固定パターンをパケット内に配置することができ、これによって、効果的に、シンボルが、パケットの長さと等しい長さまでパディングされる。シンボルのサイズは、しばしば、ビット単位で測定され、シンボルは、Ｍビットのサイズを有し、シンボルは、２Ｍ個のシンボルのアルファベットから選択される。非２進数字も企図されているが、２進ビットは、より一般的に使用されているので好ましい。
【００３０】
本明細書でストリーミングについて検討されるＦＥＣ符号は、通常は、組織的ＦＥＣ符号である、すなわち、ソースブロックのソースシンボルは、ソースブロックの符号化の一部として含められ、したがって、ソースシンボルが、送信される。次に、組織的ＦＥＣ符号は、ソースシンボルのソースブロックから、ある個数のリペアシンボルを生成し、次に、ソースシンボルおよびリペアシンボルの組合せが、そのソースブロックについて送信される符号シンボルである。ＦＥＣ符号の一部は、必要な個数のリペアシンボルを効率的に生成する能力を有する。そのような符号を、”情報付加的符号”および”ファウンテン符号”と称し、これらの符号の例には、”連鎖符号”および”マルチステージ連鎖符号”が含まれる。リードソロモン符号などの他のＦＥＣ符号は、実用的には、限られた個数のリペアシンボルを生成することしかできない。
【００３１】
パケット内でシンボルを搬送する多数の他の方法があり、下の説明では、説明を単純にするためにこの例を使用するが、下の説明は、限定的または網羅的であることを意図されてはいない。下の説明の文脈では、用語”パケット”が、文字どおりにデータの単一の単位として送信されるものを意味することに制限されることは意図されていない。そうではなく、用語”パケット”は、データの単一の単位として送信されてもされなくてもよい、シンボルおよび部分的シンボルの論理グループ化を定義するというより広い概念を含むことが意図されている。
【００３２】
シンボルの消失以外の形のデータの破損、たとえば、伝送中にその値が変化するか他の形で破損されるシンボルもあるが、下で説明される方法は、これらにも同等に適用される。したがって、下の説明では、しばしば、シンボルの消失を説明するが、この方法は、他のタイプの破損およびＦＥＣエラー訂正符号などのＦＥＣ消去符号を超えた他のタイプのＦＥＣ符号に同等に良好に適用される。
【００３３】
線形変換
ある種の構成および例を示すために、環という数学的概念を利用する。当業者に周知の通り、環は、２つの演算すなわち加算および乗算が定義され、これらの演算が分配法則を満足するようになっている集合である。さらに、加算だけについて検討される集合は、アーベル群を形成する、すなわち、加算の結果は、被加数の順序付けと独立であり、加算の単位元０があり、要素ごとに、その要素との和が０になるもう１つの要素がある。他の要件は、乗算が単位元１を有し、１との任意の要素の乗算が、その要素の値を変更しないようになっていることである。一般的な環について、非０要素が逆数を有することは要求されず、乗算が可換であることも要求されない。しかし、これらの条件の両方が満足されるときに、その環を”体”と呼ぶ。この表記法は、代数の分野で標準的な表記法である。
【００３４】
写像は、同一サイズのシンボルのペアをそのサイズの別のシンボルに写像する、ハードウェア、ソフトウェア、データストレージなどで実施可能な論理構成である。我々は、
2008546361.tif 000003
によってこの写像を表し、シンボルのペア（Ｓ，Ｔ）に対するこの写像の像を
2008546361.tif 000004
によって表す。そのような写像の例が、ビット単位の排他的論理和（ＸＯＲ）である。
【００３５】
本明細書で使用されるもう１つの概念が、シンボルに対する特殊なタイプの集合の”アクション(action)”という概念である。Ａが、単位元を有し、すべての要素についてその反数を含む、可換加算演算（”＋”）を備えた集合であるものとする。そのような集合を、一般に、アーベル群とも呼ぶ。シンボルの集合に対するこの群の”アクション”は、群要素ｒおよびシンボルＳからなる対を別のシンボルに写像する写像である。この像を、ｒ＊Ｓによって表す。この写像が、この群においてすなわち、群Ａの要素ａおよびｂのすべてのペアについて、加算を尊重する場合に、
2008546361.tif 000005
が得られる。Ａが環であり、アクションが、Ａでの乗算をも尊重する場合に（Ａでの乗算演算子は、”・”である、すなわち（ａ・ｂ）＊Ｓ＝ａ＊（ｂ＊Ｓ）である）、このアクションを、”演算”と呼ぶ。
【００３６】
シンボルに作用する環または体の例は、豊富にある。少数の例に、下で言及する。この例のリストは、例示のみを意図されており、網羅的なリストと考えてはならず、本発明の範囲を限定するものと解釈してもならない。
【００３７】
例として、０および１からなり、排他的論理和（ＸＯＲ）である加算および論理演算ＡＮＤである乗算を有する体ＧＦ（２）は、１＊Ｓ＝Ｓおよび０＊Ｓ＝０を定義することによってシンボルの集合に作用し、ここで、Ｓは、任意のシンボルを表し、０は、完全に０からなるシンボルを表す。
【００３８】
”線形変換”という概念およびこの処理の行列定式化は、シンボルの環の演算という概念を参照して定義することができる。所与の整数ｋおよびｎについて、この演算によって導入される線形変換は、指定された環に含まれる要素を有する行列の空間を使用して、ｋ個のシンボルのベクトルをｎ個のシンボルのベクトルに写像する。環Ｒ上の行列は、項目の２次元集合であり、各項目は、Ｒに属する。ある行列が、ｎ行ｋ列を有する場合に、その行列を、一般にｎ×ｋ行列と称する。ペア（ｎ，ｋ）を、その行列の”フォーマット”と呼ぶ。同一のフォーマットの行列は、基礎になる体または環の加算および減算を使用して、加算し、減算することができる。フォーマット（ｎ，ｋ）の行列は、一般に知られている通り、フォーマット（ｋ，ｍ）の行列と乗算することができる。
【００３９】
演算において、Ｍがそのようなｎ×ｋ行列を表し、Ｍ［ｉ，ｊ］が、位置（ｉ，ｊ）のＭの項目を表し、この行列がベクトル（Ｓ１，Ｓ２，．．．，Ｓｋ）をベクトル（Ｅ１，Ｅ２，．．．，Ｅｎ）に変換する場合に、式１に示された関係は、有効である。
【００４０】
１からｎまでのすべてのｉについて、
2008546361.tif 000006
（式１）
Ｓが、Ｓ１，Ｓ２，．．．，Ｓｋを含む列ベクトルを表し、Ｅが、シンボルＥ１，Ｅ２，．．．，Ｅｎの列ベクトルを表す場合に、Ｅ＝Ｍ＊Ｓである。
【００４１】
そのような線形変換は、さまざまなアプリケーションで平凡である。たとえば、ソースブロックを符号化するのに線形ＦＥＣ符号を使用する時に、Ｓを、符号化されるソースブロックのソースシンボルとすることができ、Ｅを、ソースブロックについて送信される、Ｓから生成された符号シンボルとすることができ、Ｍを、ＦＥＣ符号に関する生成行列とすることができる。他のアプリケーションでは、たとえば、組織的ＦＥＣ符号が使用される場合に、Ｅを、Ｓから生成されたリペアシンボルとすることができ、Ｍを、ソースシンボルに対するリペアシンボルの依存性を記述する行列とすることができる。もう１つのアプリケーションでは、Ｓを、変換の後に受け取られる符号シンボルのベクトルとすることができ、Ｅは、完全に未知または部分的に未知のいずれかであるソースシンボルの集合に対応することができ、Ｍは、ＥとＳとの間の関係を記述することができる。これらの例には、消去にもかかわらずまたはエラーにもかかわらずリードソロモン符号を復号化する場合が含まれる。後者は、Ｓｈｏｋｒｏｌｌａｈｉ他の米国特許第６６３１１７２号、名称”Efficient List Decoding of Reed-Solomon Codes for Message Recovery in the Presence of High Noise Levels”に記載されている。
【００４２】
組織的リードソロモン符号の行列定式化は、ソースシンボルおよびリペアシンボルの中で成り立つ連列方程式の組を表す。具体的に言うと、各式は、リペアシンボルの場合にはソースシンボルの線形組合せとして、ソースシンボルの場合には恒等式として、符号シンボルを表す。したがって、ソースシンボルおよびリペアシンボルと正確に同一の個数の式がある。
【００４３】
本明細書で説明する方法および処理は、リードソロモン符号または他のＦＥＣ消去符号もしくはＦＥＣエラー訂正符号の他の定式化に同等に適用される。
【００４４】
ストリーミング
ソースストリームのＦＥＣ保護をもたらすために、ソースストリームを、１つまたは複数の論理ストリームの組合せとすることができ、その例は、オーディオＲＴＰストリームおよびビデオＲＴＰストリームの組合せ、ＭＩＫＥＹストリームおよびＲＴＰストリームの組合せ、複数のビデオストリームの組合せ、ならびに制御ＲＴＣＰトラフィックおよびＲＴＰストリームの組合せである。ソースストリームが、たとえばソースビットストリーム、ソースシンボルストリーム、またはソースパケットストリームである、あるフォーマットでＦＥＣ送信機に到着する時に、ＦＥＣ送信機は、そのストリームをソースブロックにバッファリングし、ソースブロックからリペアストリームを生成することができる。ＦＥＣ送信機は、ソースストリームおよびリペアストリームをスケジューリングし、たとえばパケットネットワークを介して送信されるパケット内で、送信する。ＦＥＣ符号化されたストリームは、組み合わされたソースストリームおよびリペアストリームである。ＦＥＣ受信機は、ＦＥＣ符号化されたストリームを受信し、このＦＥＣ符号化されたストリームは、たとえば消失またはビット反転に起因して、破損されている場合がある。ＦＥＣ受信機は、ソースストリームのオリジナルのソースブロックを再構成することを試み、その受信機でオリジナルソースストリームをスケジューリングし、使用可能にする。
【００４５】
ストリーミングアプリケーションについて、ソースストリームを保護するのにＦＥＣ符号をどのように使用するかの設計に対する入力である複数のキーパラメータと、通常は最適化することが重要な複数のキーメトリックとがある。
【００４６】
設計における２つのキー入力パラメータは、保護期間および保護量である。あるソースブロックの送信機保護期間とは、ソースブロックから生成されたシンボルがその間に送信される時間の持続時間である。あるソースブロックの保護量とは、そのソースブロック内のソースシンボルの個数の分数またはパーセンテージとして表される、そのソースブロックに関して送信されるＦＥＣリペアシンボルの個数である。たとえば、保護期間が２秒であり、保護量が２０％であり、ソースブロックに１００００個のソースシンボルがある場合に、そのソースブロックに関する１００００個のソースシンボルおよび２０００個のリペアシンボルが、２秒の時間のウィンドウにまたがって拡散されて送信される。
【００４７】
ソースブロックあたりの保護期間と保護量との両方を、ソースブロックごとに変更することができる。たとえば、ソースブロックが、ソースストリーム内のある種のソースパケットの間にまたがらないことが好ましい時、たとえば、第１パケットがＭＰＥＧ２ビデオストリーム内のグループオブピクチャ（ＧＯＰ）の最後のパケットであり、第２の連続するパケットが、次のＧＯＰの最初のパケットである時に、ソースブロックを、第１パケットの後、第２パケットの前に打ち切ることができ、この打切りは、これが保護期間の終りの前に発生する場合であっても行うことができる。これによって、ＦＥＣ保護ブロックをビデオ符号ブロックと整列させることが可能になり、これは、ビデオバッファリングおよびＦＥＣバッファリングに起因する受信機待ち時間を最小化できるという利点を含む、多数の利点を有することができる。他のアプリケーションでは、さまざまな理由から、各連続するソースブロックについて同一の保護期間および／または同一のソースブロックサイズを必ず維持することが有利である可能性がある。下の説明の多くでは、説明を単純にするために、保護期間と保護量との両方が、各連続するソースブロックについて同一であると仮定する。これが限定的ではないことは、この開示を読んだ後に当業者に明白であろう。というのは、この開示を読んだならば、保護量または保護期間のいずれかあるいはその両方がソースブロックごとに変化する場合およびソースブロックサイズがソースブロックごとに変化する場合にも、本明細書で説明される処理および方法がどのように適用されるかを簡単に判定できるからである。
【００４８】
後続の議論の一部を単純にするために、オリジナルストリームのソースシンボルが、安定したレートでＦＥＣ符号化を実行しなければならないＦＥＣ送信機に到着し、そのＦＥＣ送信機が、まずソースシンボルを受信機で使用可能にしたならば、そこからソースシンボルが受け取られる第１ソースブロックに、ソースシンボル消失がなく、各後続ソースブロックで、符号シンボル消失が、多くとも成功のＦＥＣ復号化を可能にするために可能な最大値であると仮定して、後続ソースシンボルが、同一の安定したレートでＦＥＣ受信機によって使用可能にされるとしばしば仮定する。この単純にする仮定は、この後で説明する処理および方法の動作または設計に固有ではなく、いかなる形でもこれらの処理をこの仮定に限定することは意図されておらず、単に、この処理および方法の特性の説明の一部を単純にするための道具として導入されるものである。たとえば、可変レートストリームについて、対応する条件は、ソースシンボルが、ＦＥＣ送信機に到着するのと同一のレートまたはそれと同一に近いレートでＦＥＣ受信機によって使用可能にされることである。
【００４９】
最小化することが重要ないくつかのキーメトリックには、ＦＥＣ送信機待ち時間が含まれ、このＦＥＣ送信機待ち時間は、ＦＥＣ送信機によって導入される待ち時間である。ＦＥＣ送信機待ち時間の最小化は、生のビデオストリームなど一部のアプリケーション、またはビデオ会議などの対話型アプリケーションに望ましい。ＦＥＣ送信機待ち時間を最小化するのを助ける全体設計の一態様は、ＦＥＣ送信機が、ソースシンボルがそのＦＥＣ送信機に到着するのと同一の順序でソースシンボルを送信することである。ＦＥＣ送信機待ち時間を最小化する他の設計態様は、後に説明する。
【００５０】
もう１つの重要なメトリックが、ＦＥＣ受信機待ち時間である。図２に示されているように、これは、受信機がストリームに参加するかストリームを要求し、そのストリームからの符号シンボルの受信を初めて開始する時と、そのＦＥＣ受信機がそのストリームからのソースシンボルを初めて使用可能にする時との間の時間である。一般に、ＦＥＣ受信機待ち時間を最小化することが望ましい。というのは、これが、ＦＥＣ受信機によって復号化され、渡される前にシンボルを記憶するための、その受信機でのメモリ要件を最小化し、また、ストリームに参加する時と、たとえばビデオストリームの再生のために、そのストリームが始めて使用可能になり始める時との間の時間の長さを最小化するからである。ＦＥＣ受信機待ち時間を最小化する１つの重要な態様は、ＦＥＣ送信機がソースシンボルのオリジナルの送信順序を維持することであるが、下で説明するように、ＦＥＣ受信機待ち時間に対する大きい影響を有する多数の他の重要な設計態様がある。
【００５１】
ＦＥＣ受信機待ち時間は、通常は複数の成分を含む。シーケンシャルソースブロックに区分されたストリームのこれらの成分の例を、図３Ａおよび３Ｂに示す。図３Ａには、保護期間あたり単一のソースブロックが示されており、この例は、受信機がソースブロックの始めにストリームに参加する場合を示す。この例でのＦＥＣ受信機待ち時間の２つの成分は、保護期間および復号化待ち時間である。受信機保護待ち時間は、その間にＦＥＣ受信機がソースブロックからの受信符号シンボルをバッファリングしている時間である。送信機保護期間および受信機保護期間は、送信機と受信機との間のチャネルが、各ビット、バイト、シンボル、またはパケットが送信機から受信機まで移動するのに要する時間に関して変動を全く有しない場合に、同一であることに留意されたい。したがって、実際には、送信機保護期間は、配送におけるネットワークタイミング変動に起因して、同一のソースブロックに関して受信機保護期間と異なる場合がある。
【００５２】
本明細書での例示を単純にするために、以下では、送信機保護期間および受信機保護期間が各ソースブロックについて同一であると仮定し、用語”保護期間”を、送信機保護期間および受信機保護期間について同義に使用する、すなわち、ネットワーク配送時間が、すべてのデータについて同一であると仮定するが、当業者が、この開示を読んだ後に、ネットワーク配送変動に起因する送信機保護期間と受信機保護期間との差を考慮に入れるために、本明細書に記載の方法および装置に対して必要な変更を行うことができることに留意されたい。
【００５３】
ＦＥＣ受信機待ち時間の保護期間成分は、不可避である。というのは、最初のソースブロックにソースシンボルの消失が全くない場合であっても、それでも、後続ソースブロックに符号シンボルの消失がある時にすべての後続ソースシンボルの滑らかなソースシンボル配送を保証するために、ソースシンボルを少なくとも保護期間の間に使用可能にするために遅延しなければならないからである。保護期間中に、ソースブロックのＦＥＣ復号化の一部、ほとんど、またはすべてを、符号シンボルの受信と同時に行っているものとすることができる。保護期間の終りに、ソースブロックの最初のソースシンボルがＦＥＣ受信機から使用可能になる前に行われる、追加のＦＥＣ復号化がある場合があり、この時間期間は、図３Ａでは、復号化待ち時間としてラベルを付けられている。さらに、最初のソースシンボルが使用可能になった後であっても、ソースブロックの第２のおよび後続のソースシンボルが使用可能になる前に行われる、追加のＦＥＣ復号化がある場合がある。図を単純にするために、この追加のＦＥＣ復号化は、図３Ａには示されておらず、この例では、最初のソースシンボルの後のすべてのソースシンボルを十分に速いレートで復号化するのに十分な使用可能なＣＰＵリソースがあると仮定する。
【００５４】
図３Ｂに、図３Ａに示された例に対応するものとすることができる、２つの潜在的なＦＥＣ復号化ＣＰＵ利用度曲線を示す。図３Ｂに示された２つの曲線の一方では、ＦＥＣ復号化に使用されるＣＰＵ利用度が、各時点で同一である、すなわち、ＣＰＵ利用度は、均等に分散されている。これは、望ましいＣＰＵ利用度曲線である。というのは、これによって、各時点で同一量のＣＰＵリソースが予測可能に使用され、総ＣＰＵリソースのうちの同一量がソースブロック全体を復号化するのに必要になると仮定して、最大ＣＰＵリソースが最小化されるからである。図３Ｂに示された２つの曲線の他方では、ＦＥＣ復号化に使用されるＣＰＵ利用度が、各時点で同一ではなく、具体的には、ソースブロックの符号シンボルの受信の終りに向かっておよびその直後のＣＰＵ利用度は、他の時点よりかなり高い。これは、望ましいＣＰＵ利用度曲線ではない。というのは、ＣＰＵリソース使用が、ある時点で急上昇し、この時点が、ビデオプレイヤなどの他の処理もＣＰＵに要求を行う時点である可能性があり、したがって、たとえばビデオストリームの再生におけるグリッチを引き起こす可能性が高まるからである。したがって、ストリームの保護に関するＦＥＣ解決策の設計は、ＦＥＣ符号化器が経時的にできる限り滑らかに均一にＣＰＵを使用する解決策を提供することである。例として、設計判断基準を、符号シンボル消失のワーストケースパターンの下でのＦＥＣ復号化処理の任意の時点での最大ＣＰＵ利用度が、ある閾値未満であり、たとえば、多くともＣＰＵの１０％を使用することとすることができる。
【００５５】
受信機が、たまたまソースブロックの途中でストリームに参加するときには、ソースパケットのオリジナルの送信順序がＦＥＣ送信機によって維持される限り、ＦＥＣ受信機待ち時間を、保護期間と、最初の部分的ソースブロックからのソースシンボルの消失がない時の復号化待ち時間との合計ほどに短くすることができる。したがって、ＦＥＣ送信機が、ソースシンボルのオリジナルの送信順序を維持することが望ましい。
【００５６】
ＦＥＣストリーミング解決策は、ＦＥＣエンドツーエンド待ち時間を最小化するのにも使用することができ、このＦＥＣエンドツーエンド待ち時間は、ソースパケットがＦＥＣ符号化が適用される前に送信機でストリーミングの準備ができた時とソースパケットがＦＥＣ復号化が適用された後に受信機で再生に使用可能になる時との間のＦＥＣの使用によって導入されるワーストケース総待ち時間である。
【００５７】
ＦＥＣストリーミング解決策は、ＦＥＣが使用される時の送信レートの変動を最小化するのに使用することもできる。これの１つの利益は、パケットネットワーク内で、ストリームの送信レートのピークがネットワーク内の制限された容量を有する点での他のトラフィックのピークと一致する時の輻輳またはバッファオーバーフローに起因して、変動する送信レートを有するストリームが、よりパケット消失を受けやすいことである。最低限でも、ＦＥＣ符号化されたストリームのレートの変動は、オリジナルのソースストリームのレートの変動より悪くなってはならず、好ましくは、より多くのＦＥＣ保護がオリジナルのソースストリームに適用されるにつれて、ＦＥＣ符号化されたストリームのレートの変動が、より少なくなる。特殊な事例として、オリジナルストリームが、一定のレートで送信される場合に、ＦＥＣ符号化されたストリームも、できる限り一定に近いレートで送信されなければならない。
【００５８】
ＦＥＣストリーミング解決策は、ＦＥＣ受信機でできる限り単純な論理を実現しなければならない。これは、多くの文脈で重要である。というのは、ＦＥＣ受信機が、制限された計算リソース機能、メモリリソース機能、および他のリソース機能を有するデバイスに組み込まれる場合があるからである。さらに、いくつかの場合に、伝送でのシンボルのかなりの消失または破損がある場合があり、したがって、ＦＥＣ受信機が、条件が改善される時にストリーム内のどこから受信が継続しつつかるのかを理解するためのコンテキストがほとんどまたは全くない、破滅的な消失または破損のシナリオから回復しなければならない場合がある。したがって、ＦＥＣ受信機論理が単純であり、堅牢であるほど、ＦＥＣ受信機は、ＦＥＣ符号化されたストリームの受信からのソースストリームのソースシンボルの回復およびこれをもう一度使用可能にすることを、よりすばやく信頼できる形で開始できるようになる。
【００５９】
ＦＥＣストリーミング解決策の総合的な望ましい特徴の一部を、次のように要約することができる。
【００６０】
１．ＦＥＣ送信機は、ソースストリングのオリジナルの送信順序を維持しなければならない。
【００６１】
２．ＦＥＣ復号化器は、ＣＰＵ利用度をできる限り滑らかに拡散させなければならない。
【００６２】
３．ＦＥＣ受信機は、ＦＥＣ符号化されたストリームの受信の始まりと、そのソースストリームの最初のデータがＦＥＣ復号化の後に使用可能にされる時との間の遅延と定義されるＦＥＣ受信機待ち時間を最小化しなければならない。
【００６３】
４．ＦＥＣ送信機／受信機は、ＦＥＣエンドツーエンド待ち時間すなわち、ＦＥＣ送信機待ち時間およびＦＥＣ受信機待ち時間を含む、ＦＥＣを使用することによって導入される総待ち時間を最小化しなければならない。
【００６４】
５．ＦＥＣ符号化されたストリーム（そのストリームについて送信されるすべてのデータを含む）の送信レートは、できる限り滑らかでなければならず、少なくともオリジナルのソースストリームと同程度に滑らかでなければならない。
【００６５】
次のセクションでは、これらの特徴の一部またはすべてを有する方法および装置を説明する。
【００６６】
インクリメンタル復号化
このセクションでは、ソースブロックについて受信された符号シンボルから、そのソースブロックの失われたソースシンボルを回復するインクリメンタルＦＥＣ復号化処理を説明する。この説明では、組織的ＦＥＣ符号が使用されると仮定し、ソースシンボルのソースブロックから生成されるシンボルは、リペアシンボルと呼ばれ、用語”符号シンボル”は、ソースシンボルまたはリペアシンボルのいずれかであるシンボルを指すのに使用される。
【００６７】
この処理は、符号シンボルの受信と同時に、線形式のリストを更新し、このリストでは、式の個数が、受信された符号シンボルの個数であり、個数変数が、ソースシンボルの個数である。各式は、受信された符号シンボルのうちの１つに対応する。処理の始めには、符号シンボルがまだ受信されていないという事実をまねて、式の個数は０である。
【００６８】
ソースシンボルおよびリペアシンボルの受信と同時に復号化動作を部分的に完了する技法を説明する。この技法は、バンデルモンド行列またはコーシー行列に基づく組織的リードソロモン符号に関して説明されるが、行列に関して記述されるどの線形変換にも同等に適用することができる。
【００６９】
バンデルモンド行列またはコーシー行列に基づく（ｎ，ｋ）リードソロモン符号は、次のように動作する。
【００７０】
ＧＦ（２ｑ）上のｎ×ｋ生成行列Ｍが、下の式２を満足するように構成され、ここで、Ｅは、符号シンボルを含む大きさｎの列ベクトルであり、Ｓは、ソースシンボルを含む大きさｋの列ベクトルである。組織的符号について、さらに、Ｍの最初のｋ個の行が、恒等行列を形成すると仮定する。
【００７１】
Ｅ＝Ｍ＊Ｓ      （式２）
基本的な演算は、基礎の体ＧＦ（２ｑ）の要素にまたがるものである。たとえば、ｑ＝８の場合に、体の各要素を、データの単一バイトとして表すことができる。多くの場合に、”Ｒｉｚｚｏ”に記載されているように、符号化と復号化との両方が、次のように体要素をグループ化することが効率的である。ソースブロックが、ｋ＊Ｔ個の体要素を含み、Ｔが、正の整数であるものとする。すると、ソースブロックの体要素を、それぞれがＴ個の体要素のｋ個のグループに区分することができ、各グループを、ソースシンボルであると考えることができる。次に、記載されているように（たとえば、”Ｒｉｚｚｏ”）、同一の行列ベクトル乗算演算が、ｋ個のソースシンボルにまたがってソースシンボルのＴ個の位置のそれぞれに適用されて、ＦＥＣ符号化中にｎ個の符号シンボルが生成され、したがって、Ｔ個の位置のそれぞれについて、適用すべき演算のシーケンスを１回だけ計算することが可能になる。同様に、ＦＥＣ復号化中に、復号化演算のシーケンスを１回計算し、受信した符号シンボルにまたがって符号シンボルのＴ個の位置のそれぞれに適用して、オリジナルのｋ個のソースシンボルを回復することができる。
【００７２】
オリジナルのｋ個のソースシンボルを回復するためには、符号シンボルのうちの少なくともｋ個を受信しなければならない（同一サイズのシンボルと、オリジナルシンボルに関する追加情報が使用可能でないこととを仮定して）。行列Ｍ’は、復号化に使用されるｋ個の受信された符号シンボルに対応するＭのｋ個の行から形成され、列ベクトルＥ’は、復号化に使用されるｋ個の受信された符号シンボルを含む。すると、復号化は、式３によって記述されるＥ’およびＭ’に基づいてＳを解くことを含む。
【００７３】
Ｅ’＝Ｍ’＊Ｓ      （式３）
リードソロモン符号について、Ｍの構成は、Ｍ’が必ず可逆になるようになっており、これは、任意のｋ個の符号シンボルの受信からの復号化を可能にする（他のＦＥＣ符号および線形変換について、Ｓについて解くためにｋ個を超える符号シンボルを受信する必要があることがありえる）。Ｓについて式３を解くためのＦＥＣ復号化計算の量は、受信されたソースシンボルのすべてが、Ｅ’に含まれるｋ個の符号シンボルの中にある場合に最小化される。
【００７４】
式３に基づいてＳについて解くのに必要な計算は、大部分、次のように符号シンボルの到着と同時に実行することができる。
【００７５】
ｍが、受信されたソースシンボルの個数であるものとする。すると、ここでは組織的線形変換を説明しているので、Ｍ’の最初のｍ個の行は、それぞれ単一の項目を含む。Ｅ’およびＳとＭ’の行および列とを、最初のｍ個の行および列が受信されたソースシンボルに対応するように置換することができ、その後、Ｍ’の左上のｍ×ｍ部分行列は、恒等行列であり、Ｍ’の右上のｍ×（ｋ−ｍ）部分行列は、零行列である。したがって、Ｍ’は、図４に示されたフォーマットを有し、ここで、Ｉｍは、ｍ×ｍ恒等行列であり、０は、ｍ×（ｋ−ｍ）のすべての０の行列であり、Ａは、（ｋ−ｍ）×ｍ行列であり、Ｂは、（ｋ−ｍ）×（ｋ−ｍ）行列である。Ｍ’の上側のｍ個の行は、Ｉｍ｜０と記述され、Ｍ’の下側の（ｋ−ｍ）個の行は、Ａ｜Ｂと記述され、今や、次の式４〜５が得られ、ここで、Ｅ１は、Ｅの最初のｍ個の項目（受信されたソースシンボル）であり、Ｅ２は、Ｅの最後の（ｋ−ｍ）個の項目（受信されたリペアシンボル）であり、Ｓ１は、Ｓの最初のｍ個の項目（受信されたソースシンボル）であり、Ｓ２は、Ｓの最後の（ｋ−ｍ）個の項目（それについて解かなければならない未知のソースシンボル）である。
【００７６】
Ｅ１＝（Ｉｍ｜０）＊Ｓ＝Ｓ１      （式４）
Ｅ２＝（Ａ｜Ｂ）＊Ｓ＝Ａ＊Ｓ１＋Ｂ＊Ｓ２      （式５）
したがって
Ｂ＊Ｓ２＝Ｅ２−Ａ＊Ｅ１      （式６）
であり、したがって、
Ｓ２＝Ｂ−１＊（Ｅ２−Ａ＊Ｅ１）      （式７）
である。
【００７７】
同時復号化を使用する実施形態は、ソースシンボルが到着する時にＡ＊Ｅ１を計算できるという事実に頼る。行列Ａは、正確にｋ個の行を有するように行列Ｍ’が選択されるので、消去されたソースシンボルと同一個数の行を有する。
【００７８】
図５、６、および７に示され、下で説明される復号化方法の実施形態の説明について、受信されるソースブロックのすべてのソースシンボルが、そのソースブロックのいずれかのリペアシンボルが受信される前に受信され、さらに、すべての符号シンボルが、増加するインデックスの順序で受信され、ソースシンボルが、１からｋまでのインデックスを付けられ、リペアシンボルが、ｋ＋１からｎまでのインデックスを付けられると仮定する。しかし、符号シンボルの消去の量およびパターンは、ＦＥＣ復号化器に既知ではなく、したがって、Ａ’＊Ｅ１が計算され、ここで、Ａ’は、ｍ個の受信されたソースシンボルに対応するＭの列と交差するＭの最後のｎ−ｋ個の行に対応する。
【００７９】
図５には、ソースシンボルが到着する時に使用できる処理が示されている。変数ｍは、ステップ５０５で０に初期化されて、ソースシンボルがまだ到着していないことを示し、ｎ−ｋ個のシンボルのベクトルｒも、ステップ５０５ですべて０のシンボルに初期化される。ステップ５１０で、テストを行って、別のソースシンボルがあるかどうかを調べ、さらなるソースシンボルがない場合には、ソースシンボルの受信は、ステップ５２０に示されているように、図６で説明する処理に進む。別のソースシンボルがある場合には、ステップ５３０で、シンボル値ｅおよびインデックスｊを用いてそのソースシンボルを受け取る。ステップ５４０で、受け取ったソースシンボルの個数ｍを１つインクリメントし、ベクトルＣＯＬを更新して、ｍ番目の受け取られたソースシンボルのインデックスを記憶する。ステップ５５０で、ベクトルＭ［ｋ＋１，．．．，ｎ：ｊ］と受け取られたシンボル値ｅとの積を加算することによって、シンボルのベクトルｒを更新し、ここで、Ｍ［ｋ＋１，．．．，ｎ：ｊ］は、Ｍの列ｊの最後のｎ−ｋ個の行に対応する。したがって、この処理が、最終的に図５のステップ５２０に達する時に、リペアシンボルベクトルｒは、Ａ’＊Ｅ１と等しい。
【００８０】
図６には、リペアシンボルが到着する時に使用できる処理が示されている。変数ｒは、ステップ６０５で０に初期化されて、リペアシンボルがまだ到着していないことを示す。ステップ６１０では、検査を行って、到着した符号シンボルの総数すなわちｍ個のソースシンボルおよびｒ個のリペアシンボルが、ソースブロック内のソースシンボルの総数ｋと等しいかどうかを調べる。ｋ個の符号シンボルが到着している場合には、復号化が可能であり、この処理は、図６のステップ６２０に示されているように、図７に進む。ｋ個より少ない符号シンボルが到着している場合には、この処理は、図６のステップ６３０に進み、別のリペアシンボルの受信について検査する。追加のリペアシンボルがない場合には、ステップ６４０に示されているように、復号化は可能ではない。別のリペアシンボルがある場合には、ステップ６５０で、シンボル値ｅおよびインデックスｊを用いてそのリペアシンボルを受け取る。ステップ６６０で、受け取られたリペアシンボルの個数ｒを１つインクリメントし、ベクトルＲＯＷを更新して、ｒ番目の受け取られたリペアシンボルのインデックスを記憶する。ステップ６７０で、シンボルベクトルｅのｒ番目の項目にｅ−ｒ［ｊ−ｋ］をセットし、ここで、ｒ［ｊ−ｋ］は、Ａ’＊Ｅ１のインデックスｊを有するリペアシンボルに対応するシンボル値を格納し、したがって、この処理が最終的に図６のステップ６２０に達する時に、シンボル値ベクトルｅは、Ｅ２−Ａ＊Ｅ１と等しい。
【００８１】
図７では、Ｂ−１＊ｅ＝Ｂ−１＊（Ｅ２−Ａ＊Ｅ１）＝Ｓ２を計算する、すなわち、受信されていないソースシンボルについて解く、この処理の最後のステップを説明する。図７のステップ７０５から７６０では、行列Ｂを決定する。ステップ７０５で、ｉ、ｊ、およびｓｒｃの値を、すべて０に初期化し、ｉは、ｋ個のソースシンボルを通ってインデクシングするのに使用され、ｊは、これまでに欠けているソースシンボルの個数を記憶するのに使用され、ｓｒｃは、受信したソースシンボルのインデックスの配列へのインデックスである。また、ＣＯＬ［ｍ＋１］に０をセットして、後続の論理を単純化し、ＣＯＬは、図５に示されているように計算される、ｍ個の受信されたソースシンボルのインデックスの配列である。ステップ７１０で、ｉの値を１つインクリメントし、ステップ７２０で、復号化処理は、すべてのソースシンボルが検討されたかどうかの検査を含み、そうでない場合には、この処理は、ステップ７３０に継続し、ステップ７３０では、この処理は、ｉが受信されたソースシンボルのインデックスである、すなわち、ｉ＝ＣＯＬ［ｓｒｃ］であるかどうかを検査する。ｉが受信されたソースシンボルのインデックスである場合には、ステップ７５０で、このソースシンボルをスキップするが、ｉが欠けているソースシンボルのインデックスである場合には、ステップ７４０で、このインデックスを、欠けているソースシンボル値のベクトルＭＩＳＳに保存する。ｋ個のソースシンボルのすべてを、それが欠けているかどうかを調べるために検査し、そのインデックスをベクトルＭＩＳＳに適当に追加した後に、ステップ７６０で、この処理は、受信したリペアシンボルのベクトルＲＯＷによってインデクシングされるＭのｒ個の行と欠けているソースシンボルのベクトルＭＩＳＳによってインデクシングされるｒ個の列との交差として行列Ｂを形成する。ステップ７７０で、Ｂの逆行列Ｂ−１を計算し、ステップ７８０で、欠けているソースシンボルをＢ−１＊ｅとして計算し、この点で、ステップ７９０に示されているように、復号化が完了する。
【００８２】
上の処理の多数の変形形態がある。たとえば、この開示を読んだ後には、ソースパケットおよびリペアパケットが任意の順序で到着するようにするためにこの処理を変更することが、単純であるに違いない。当業者は、この開示を読んだ後に、本明細書で教示される方法の多数の他の変形形態を識別できるに違いない。上の処理のいくつかの追加の変形形態および機能強化を、下で説明する。
【００８３】
説明したばかりの処理では、シンボルの潜在的により大きいｎ−ｋベクトルであるｒ＝Ａ’＊Ｅ１を計算する。消去の個数および受信されたリペアシンボルの位置がわかったならば、ｒの要素をＡ＊Ｅ１から破棄することができる。その結果、この手法は、不必要な計算を実行する可能性を許す（ｒの計算されるシンボルを破棄できるので）。しかし、この不必要な計算は、それ以外の形でプロセッサがＦＥＣ計算によって占有されない可能性がある時間の間に行われる。計算全体の量を、復号化に使用されるｋ個のシンボルの受信の後にすべての処理が開始される伝統的な復号化のワーストケース未満に保つことができることは、明白であるに違いない。
【００８４】
上で説明した処理では、シンボルのベクトルｒは、シンボルが到着する間に記憶されることに留意されたい。リペアシンボルの総サイズと等しい量のメモリが、このために必要である。Ａを形成するＡ’の行が識別される時に、このメモリを再利用することができる。特定のリペアシンボルが受信されないことを識別することが可能である場合には、ｒのその項目に対応するメモリを解放することができる。十分なリペアシンボル（すなわち、欠けているソースシンボルの個数と等しい個数のリペアシンボル）が受信されるや否や、Ａを形成するＡ’の行を識別することができ、受信されるさらなるリペアシンボルのすべてを破棄することができる。
【００８５】
ｎ−ｋ個のシンボルと等しい量のメモリが、ｒの記憶のために割り振られる。ワーストケースでは、ｋ個のシンボルのためのさらなる量のメモリも、ソースシンボルが到着する時にソースシンボルを記憶するために必要である、すなわち、総メモリ必要量は、シンボルｎ個分である。
【００８６】
さらなる変形形態では、図７に示されたＢ−１＊（Ｅ２−Ａ＊Ｅ１）の計算を、２つのサブステップに分割することができ、その第１サブステップは、リペアシンボルが到着する時に実行される。これは、式６に従って動作するのではなく、式８に従って、行ごとに、リペアシンボルが到着する時に動作するようにするために復号化器を再構成することに頼る。
【００８７】
ＢＵ＊Ｓ２＝ＢＬ＊（Ｅ２−Ａ＊Ｅ１）      （式８）
式８では、ＢＵは、上三角の形であり、ＢＬは、下三角の形である。到着する各リぺアシンボル（すなわち、Ｅ２の要素）を用いて、これらの行列のそれぞれの追加の行を、Ｂの逆行列のガウス消去処理のステップを実行することによって計算することができる。
【００８８】
さらに、ＢＬ＊（Ｅ２−Ａ＊Ｅ１）の値も、リペアシンボルが到着する時に計算することができる。このフェーズでは、各連続するリペアシンボルが、ＢＬ＊（Ｅ２−Ａ＊Ｅ１）の付随する項目の値を計算するために、最後のリペアシンボルより多くの作業を必要とするので、リペアシンボルが到着する時間にまたがって、作業負荷が均一には拡散されないことに留意することが重要である。
【００８９】
したがって、十分なリペアシンボルが到着した後に実行すべき残りの作業は、系（式８）を解くことであり、これは、後退代入によって行うことができる。
【００９０】
リペアパケットの先行送信
リペアパケットがソースパケットの前に送信される場合に、上の処理に対するある種の変形形態を作ることができる。この手法は、ソースパケットがリペアパケットの後に送信される場合にはソースパケットをバッファリングしなければならないので、ＦＥＣ送信機で追加の遅延を注入するというコストを有する。
【００９１】
しかし、この手法には複数の利点がある。よい受信状態でソースブロックの途中でストリームに参加する受信機は、より大量のソースデータを受信し、したがって、ＦＥＣ受信機待ち時間が減る。失われたリペアパケットの位置は、既知であり、したがって、これらのシンボルに対応する（Ｅ２−Ａ＊Ｅ１）の要素の計算を回避することができる。受信されたリペアシンボルの個数がｒである場合に、ｋ−ｒ個のソースシンボルが受信されたならば、（Ｅ２−Ａ＊Ｅ１）の行を破棄することができ、その後に受信されるソースシンボルに付随する計算を減らすことができる。その結果、復号化を、合計ｋ個のシンボルのためのメモリだけを使用して完了することができる。
【００９２】
２Ｄ符号に関する改善されたインターリービング
２次元符号とは、シンボルが２次元格子に配置され、独立の消去訂正符号が各行のシンボルおよび各列のシンボルに適用される符号である。使用可能な計算リソースおよび他のリソースに応じて、復号化手順を反復することができ、これによって、符号のエラー訂正能力が潜在的に高まる。この形では、たとえばリードソロモン符号またはＸＯＲ符号など、任意のエラー訂正符号を適用することができる。この説明では、消去符号に関してこのクラスの符号を提示するが、エラー訂正符号および消去訂正符号の当業者に明らかである通り、同一の手法を、エラー訂正符号に簡単に適用することができる。
【００９３】
周知の通り、２次元符号の性能は、符号シンボルをオリジナルの順序以外の順序で送信することによって改善することができる。しかし、これは、ＦＥＣ符号をサポートしない受信機に関して複雑さを追加し、送信機と受信機との間の消失が少ない場合に、ファイルの受信に必要な時間を増やす。移動端末の場合に、この追加の受信時間は、追加の電力消費を意味し、これが電池寿命を減らす。
【００９４】
代替の手法は、２次元符号を適用する前に、ソースシンボルのオリジナル順序に非自明な置換を適用することである。ソースシンボルは、オリジナルの順序で送信され、ＦＥＣをサポートしない受信機の複雑さが減り、消失が少ない場合の受信時間が減る。リペアシンボルは、生成された順序またはある他の順序のいずれかで、ソースシンボルの前に、ソースシンボルの間に散在して、またはソースシンボルの後に送信される。
【００９５】
この手法では、送信機と受信機との両方が、適用された置換を知っている。これは、送信機と受信機との両方に既知の明確に定義された組織的な形で置換を導出することによって達成することができる。たとえば、特定の擬似乱数生成処理を、送信機と受信機との両方で定義し、置換を生成するのに使用することができる。もう１つの例は、次の処理によって置換を定義することであるはずである。
【００９６】
ｋが、ソースシンボルの個数であり、ｋ’が、ｋ以上の最小の素数であるものとする。ｋ未満の２つの整数ａおよびｂを選択する。次に、ソースシンボルが、最初に０，．．．，ｋ−１という番号を与えられる場合に、新しい順序付けは、次のように定義される。
【００９７】
１）すべてのソースシンボルが新しい順序付けに追加されている場合には、停止する
２）ｂ＜ｋである場合には、新しい順序付けの次のソースシンボルは、シンボルｂである
３）ｂ＝（ｂ＋ａ）  ｍｏｄ  ｋ’
４）（１）に進む
上の方法の不利益は、選択される置換に依存して、オリジナルのシンボル送信順序付けで隣接する２つのシンボルが２次元符号で同一行または同一列に現れることが、可能なままであることである。これは、２つの隣接するシンボルの消失が、単一の行内または単一の列内に集中するので、バースト消失に対する符号の脆弱性に対する悪影響を有する。
【００９８】
さらなる変形形態では、隣接するシンボルを絶対に同一行または同一列に写像しない置換が選択される。ソースブロックが正方形である場合に、そのような置換は、たとえば、数０，．．．，ｋ１＝ｋ２の２つの置換σ１およびσ２を選択することによって定義することができ、ここで、ｋ１およびｋ２は、それぞれ２次元ソースブロックの行および列の個数である。次に、ｓ［ｉ，ｊ］が、ソースブロック内の位置（ｉ，ｊ）のシンボルを表し、ｓ’［ｉ，ｊ］が、置換されたソースブロック内の位置（ｉ，ｊ）のシンボルを表すものとする。次に、
ｓ’［ｉ，ｊ］＝ｓ［（σ１（ｊ）＋σ２（ｉ））％ｋ１，ｊ］      （式９）
を定義する。
【００９９】
次に、２次元符号を、置換されたソースブロックに適用する。ソースシンボルは、オリジナルの順序で送信される。次に、リペアシンボルを、任意の順序で送信することができる。有利なことに、同一行または同一列の符号からのリペアシンボルは、絶対に連続しては送信されない。
【０１００】
一般化された符号
このセクションでは、多次元符号の一般化されたクラスを導入する。この一般化されたクラスの符号に関する符号化処理および復号化処理は、実施の複雑さにおいて、２次元符号の特定の事例とほぼ同等である。前と同様に、この説明は、消去訂正符号に関して提示されるが、本明細書で提示される技法を、エラー訂正符号にも適用できることを理解されたい。
【０１０１】
この一般化されたクラスの符号は、ソースシンボルごとに１列、リペアシンボルごとに１列を有する２進行列に関して定義することができる。この行列の各行は、次のように、別個の消去訂正符号を表す。これらの別個の消去符号を、本明細書ではコンポーネント消去符号と称し、符号全体をコンパウンド符号と称する。上で説明したものなどの２次元符号の場合に、コンポーネント消去符号は、個々の行および列の符号であり、コンパウンド符号は、コンポーネント符号の組合せから形成される２次元符号である。一般化された事例について、行ごとに、コンポーネント消去訂正符号は、２つの条件が存在する場合に構成される。
【０１０２】
第１の条件は、コンポーネント符号のソースシンボルが、その列が特定の行に”１”を有するコンパウンド符号のソースシンボルと、その列が特定の行に”１”を有し、コンパウンド符号リペアシンボルの列が行列内の下側インデックスの１つの行に”１”を有するコンパウンド符号のリペアシンボルとを含むことである。これらのシンボルを、コンパウンド符号のソースシンボル全体から区別するために、”コンポーネント符号ソースシンボル”と呼ぶ。
【０１０３】
第２の条件は、コンポーネント符号リペアシンボルが、その列が特定の行に”１”を有し、その列が下側インデックスの行に”１”を全く有しないコンパウンド符号リペアシンボルを含むことである。これらのシンボルを、コンパウンド符号のリペアシンボル全体から区別するために、”コンポーネント符号リペアシンボル”と呼ぶ。
するコンポーネント消去符号によって決定される。このリペアシンボルは、行列の後続行内にコンポーネント符号ソースシンボルとして現れる可能性がある。
【０１０４】
本明細書で提示する一般化では、２Ｄリードソロモン符号は、ｋ１＋ｋ２個の行および（ｋ１＊ｋ２）＋ｋ１＊（ｎ２−ｋ２）＋ｋ２＊（ｎ１−ｋ１）個の列を有する行列に関して説明される。最初のｋ１個の行は、通常の２次元表現の行にまたがるリードソロモン符号に対応する。残りのｋ２個の行は、通常の２次元表現の列にまたがるリードソロモン符号に対応する。ここで、（ｎ１−ｋ１）は、２Ｄリードソロモン符号の列ごとに生成されるリペアシンボルの個数であり、（ｎ２−ｋ２）は、２Ｄリードソロモン符号の行ごとに生成されるリペアシンボルの個数である。
【０１０５】
明らかに、任意の多次元リードソロモン符号を、この形で表現することができる。
【０１０６】
追加の符号を、異なる行列構成を使用して構成することができる。たとえば、低密度パリティチェック（ＬＤＰＣ）符号の一般クラスは、ＸＯＲ消去符号に基づくこのクラスの符号の例を提供する。本明細書で提示する一般化は、これらの符号を定義する行列を、他の消去符号、たとえばリードソロモン符号を使用して適用することを可能にする。この一般化では、リードソロモンがＸＯＲ演算の代わりに使用されるので、複数のリペアシンボルを、行列の行ごとに生成することができる。
【０１０７】
最後に、連鎖符号（たとえば、Ｌｕｂｙ  Ｉおよび他の文献に記載の連鎖符号）およびマルチステージ連鎖符号（たとえば、ＳｈｏｋｒｏｌｌａｈｉＩおよび他の文献に記載の連鎖符号）をこの一般化に適用して、ファウンテン符号の特性を有する新しい符号を生成することもできる。
【０１０８】
この一般化を適用するためには、符号を記述する行列が、ＦＥＣ符号化器とＦＥＣ復号化器との両方に既知でなければならない。特定の符号の場合に、行列の構造を、ＦＥＣ符号化器とＦＥＣ復号化器との両方に前もって供給することができ、正確な符号を記述する特定のパラメータだけを、通信チャネルを介して供給することができる。
【０１０９】
本明細書で説明するクラスの符号は、２次元符号に使用されるアルゴリズムの一般化である共通の復号化アルゴリズムによって復号化することができる。受信機は、通信チャネルからできる限り多数のソースシンボルおよびリペアシンボルを集め、その後、次の処理を繰り返す。
【０１１０】
ａ）行列の行ごとに、その行について未知のままであるシンボル（コンポーネント符号ソースシンボルおよびコンポーネント符号リペアシンボル）の個数を計算し、
ｂ）未知のシンボルの個数がコンポーネント符号リペアシンボル（すなわち、元々はその行のコンポーネント符号によって生成されたリペアシンボル）の個数以下である行ごとに、未知のコンポーネント符号ソースシンボルの値を決定するために行復号化動作を試みる。この復号化動作が成功であり、いずれかのコンポーネント符号リペアシンボルが未知のままである場合には、未知のコンポーネント符号リペアシンボルの値を決定するために符号化動作を実行し、
ｃ）なんらかの動作がステップ（ｂ）で実行され、いくつかのソースシンボルが未知のままである場合には、ステップ（ａ）に戻る。そうでない場合には、停止する。
【０１１１】
上の処理は、例としてのみ説明されたものである。さらなる最適化を、たとえばさらなる復号化動作で支援する可能性を有しないコンポーネント符号リペアシンボルの計算を避けるために、適用することができる。これらの動作は、ハードウェア、ソフトウェアなどによって実施される、受信機の復号化器部分によって実行することができる。
【０１１２】
最後に、上で注記したように、上の一般化された符号構成は、リードソロモン符号に制限されず、任意の消去符号を適用して、各行の行リペアシンボルを構成することができる。明らかに、ＸＯＲ演算が使用される場合に、結果は、上で言及した符号を含む、ＬＤＰＣ符号の周知のクラスである。
【０１１３】
ＦＥＣ送信
このセクションでは、ＦＥＣ送信機がパケット（ソースパケットとリペアパケットとの両方）の送信を刻時する方法おおよび処理を説明する。ここでは、単一のソースブロックに関するパケットの送信に集中するが、これらの処理および方法が、ソースブロックに区分されるソースストリームにシームレスに適用されるように設計されていることに留意されたい。
【０１１４】
ｋが、ソースブロック内のソースシンボルの個数であるものとし、Ｔが、ソースブロックの保護期間であるものとし、ｐが、分数として表される保護量であるものとし、したがって、ｐ・ｋ個のリペアシンボルが、ソースブロックについて送信される。ｋ、Ｔ、およびｐの値は、各ソースブロックが形成されつつある時にＦＥＣ送信機によって動的に決定することができ、したがって、あるソースブロックのｋおよびＴの値は、そのソースブロックのソースシンボルのほとんどまたはすべてがＦＥＣ送信機に到着した時にＦＥＣ送信機だけに既知である場合があり、ｐの値は、ソースブロックのソースシンボルのすべてがＦＥＣ送信機に到着した後に決定することができる。また、ＦＥＣ送信機は、異なるソースブロックのシンボルサイズを変更することができる。したがって、特定のソースブロックのこれらのパラメータの多数またはすべてが、そのソースブロックのデータを十分に受け取ったＦＥＣ受信機に既知になる可能性がある。
【０１１５】
ＦＥＣエンドツーエンド待ち時間に関する懸念がない場合には、次のＦＥＣ基本送信機が、しばしば、適切である。
【０１１６】
ＦＥＣ基本送信機  たとえばＴ秒の期間にわたって、ソースブロックのソースシンボルが到着する時に、これらのソースシンボルをバッファリングする。次に、たとえばＴ’秒の期間にわたって、そのソースブロックのｐ・ｋ個のリペアシンボルを生成する。次に、後続のＴ秒にわたって均等に拡散してソースシンボルおよびリペアシンボルを送信する。
【０１１７】
このＦＥＣ基本送信機は、次の特性を有する。
【０１１８】
１．保護期間はＴであり、これは、ＦＥＣ送信機でソースシンボルを受け取る時間と同一である。
【０１１９】
２．ソースブロックについて送信されるシンボルは、経時的に均等に拡散される。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がシンボルの伝送中にいつ発生するかに依存しないことを意味し、これは望ましい特性である。
【０１２０】
３．このＦＥＣ送信機は、シンボルの全体的な送信レートの変動を導入しない。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合に、すべてのシンボルの送信レートは、やはり一定であり、このＦＥＣ送信機でのソースシンボルのオリジナルの到着レートが可変である場合に、少なくともソースブロックあたりのシンボルの一定の送信レートが、変動を減衰させる。これは、望ましい特性である。
【０１２１】
４．ＦＥＣ受信機待ち時間は、Ｔ程度に少ないものとすることができる。これは、（１＋ｐ）・ｋ個のシンボルの最小限のバッファリング（すべてのソースブロックがｋ個のソースシンボルを含むと仮定して）を意味し、これは、可能な最小限であり、したがって望ましい。
【０１２２】
５．ソースブロックのシンボルは、インターリーブされない。これは、ＦＥＣ受信機の論理を単純にし、したがって望ましい。
【０１２３】
このＦＥＣ基本送信機が有する１つの望ましくない特性は、ＦＥＣエンドツーエンド待ち時間が、２・Ｔ＋Ｔ’であり、これがかなり大きくなる可能性があることである。対話型アプリケーションまたはライブ・アプリケーションに関して、ＦＥＣエンドツーエンド待ち時間を最小化することが非常に望ましく、したがって、これらのアプリケーションに関して、次のＦＥＣ送信機を説明し、検討する。
【０１２４】
ＦＥＣ送信機Ａ：たとえばＲ秒の期間にわたって、ソースシンボルが到着する時にそれらのソースシンボルを送信する。受信および次のソースブロックのソースシンボルの送信にまたがって均等に拡散して、リペアシンボルを送信する。
【０１２５】
ＦＥＣ送信機Ａは、次の特性を有する。
【０１２６】
１．保護期間Ｔは、２・Ｒである（次のソースブロックも、Ｒ秒の期間にわたって受け取られるソースシンボルを含むと仮定して）。
【０１２７】
２．ソースブロックについて送信されるシンボルは、ソースシンボル到着が経時的に均等に拡散している場合であっても、経時的に均等に拡散はされない。これは、後続ソースシンボル送信の間の平均時間がｋ／Ｒであるが、後続リペアシンボル送信の間の平均時間がｐ・ｋ／Ｒであるからである。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がシンボルの伝送中にいつ発生するかに依存することを意味する。これは、停止がいつ発生するかと独立に所与の停止持続時間に耐えるために保護量を設計している場合に、ソースシンボル伝送またはリペアシンボル伝送のレートのうちのより大きい方に非最適に基づく保護の量を提供しなければならないことを意味する。これは、ある種のアプリケーションで望ましくない特性である。
【０１２８】
３．ソースストリーム全体のシンボルの全体的な送信レートは、ソースシンボルの送信レートから大きくは変動しない。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合には、すべてのシンボルの送信レートは一定であり、ソースシンボルのオリジナルの送信レートが可変である場合には、リペアパケットが均等に拡散されて送信されるので、オリジナルソースストリームの変動性が、多少減衰される。これは、望ましい特性である。
【０１２９】
４．ＦＥＣ受信機待ち時間は、少なくともＴ＝２・Ｒであり、これは、たとえば対話型アプリケーションなど、いくつかのアプリケーションでは望ましくない。というのは、オリジナルソースブロックの持続時間が、Ｒに過ぎないからである。これは、少なくとも（２＋ｐ）・ｋ個のシンボルのバッファリングが必要である（すべてのソースブロックがｋ個のソースシンボルを含むと仮定して）ことを意味する。これは、可能な最低限である（１＋ｐ）・ｋよりはるかに大きく、したがって、これは、いくつかのアプリケーションで望ましくない。
【０１３０】
５．あるソースブロックのリペアシンボルが、次のソースブロックからのソースシンボルとインターリーブされる。これは、複数のソースブロックのシンボルを同時に記憶し、保存することを必要とするので、ＦＥＣ受信機論理を潜在的に必要であるものより複雑にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを多少難しくする。
【０１３１】
したがって、全体的なＦＥＣ送信機Ａは、混合された品質を有し、ある種のアプリケーションでは好ましくない場合がある。
【０１３２】
ＦＥＣ送信機Ｂ：たとえばＲ秒の期間にわたって、ソースシンボルが到着する時にそれらのソースシンボルを送信する。ソースシンボル到着の平均レートで均等に拡散してリペアシンボルを送信し、したがって、リペアシンボルは、ｐ・Ｒ秒にわたって均等に拡散される。
【０１３３】
ＦＥＣ送信機Ｂは、次の特性を有する。
【０１３４】
１．保護期間Ｔは、（１＋ｐ）・Ｒである。
【０１３５】
２．ソースブロックについて送信されるシンボルは、ソースシンボル到着が経時的に均等に拡散されている場合には、経時的に均等に拡散される。これは、固定持続時間のバースト停止がある時に消失に対して提供される保護のレベルが、停止がソースブロックのシンボルの伝送内でいつ発生するかに依存しないことを意味し、これは、望ましい特性である。
【０１３６】
３．ソースストリーム全体のシンボルの全体的な送信レートの変動が、導入される。具体的に言うと、ソースシンボルのオリジナルの送信レートが一定である場合であっても、リペアシンボルの伝送が後続ソースブロックのシンボルの送信と部分的にオーバーラップするだけなので、シンボルの全体的な送信レートは、非常に可変であり、変動が多い。これは、ある種のアプリケーションで望ましい特性ではない。
【０１３７】
４．ＦＥＣ受信機待ち時間は、少なくともＴ＝（１＋ｐ）・Ｒであり、これは、いくつかのアプリケーションで望ましくない。というのは、オリジナルソースブロックの持続時間が、Ｒに過ぎないからである。これは、少なくとも（１＋２・ｐ）・ｋ個のシンボルのバッファリングが必要である（すべてのソースブロックがｋ個のソースシンボルを含むと仮定して）ことを意味する。これは、可能な最低限である（１＋ｐ）・ｋよりはるかに大きい。
【０１３８】
５．あるソースブロックのリペアシンボルが、次のソースブロック（および、ｐの値に依存して、おそらくは後続ソースブロックも）からのソースシンボルとインターリーブされる。これは、複数のソースブロックのシンボルを同時に記憶し、保存することを必要とするので、ＦＥＣ受信機論理を潜在的に必要であるものより複雑にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを多少難しくする。
【０１３９】
したがって、全体的なＦＥＣ送信機Ｂは、混合された品質を有し、ある種のアプリケーションでは好ましくない場合がある。戦略ＡおよびＢは、ＦＥＣ符号化器が、最後のソースシンボルが受信された後にリペアシンボルを作るのにかなりの時間を要する場合があることを考慮に入れておらず、実用的なＦＥＣ送信機では、これが考慮に入れられる必要があることに留意されたい。しかし、ＦＥＣ符号化時間を考慮に入れるために戦略を変更することが、その望ましくない特性のいずれをも改善しないことに留意されたい。
【０１４０】
いくつかの条件で好ましい実施形態は、下で説明するＦＥＣ送信機Ｃになるはずである。
【０１４１】
ＦＥＣ送信機Ｃ：あるソースブロックを形成するソースシンボルが、Ｒ＝Ｔ秒の期間にわたって到着し、Ｔは、保護期間である。ｕ＝ｐ／（１＋ｐ）であるものとし、Ｔ’≧ｕ・Ｔであるものとし、ここで、Ｔ’−ｕ・Ｔは、あるソースブロックの最後のソースシンボルの受け取りの後に、ＦＥＣ符号化器がそのソースブロックの最初のリペアシンボルを生成し、下で規定する送信レートでそのソースブロックの後続リペアシンボルの生成を継続できるのに十分な時間である。ｔが、ＦＥＣ送信機での現在時刻であるものとする。
【０１４２】
１．ソースブロックがこのＦＥＣ送信機によって開始される時に、ｔをｔ＝０に初期化する。
【０１４３】
２．現在時刻ｔが、区間０≦ｔ≦Ｔに含まれる間に、ソースシンボルが現在時刻ｔに受け取られるたびに、そのソースシンボルを、時刻Ｔ’＋ｔ／（１＋ｐ）に送信されるようにスケジューリングする。
【０１４４】
３．ソースブロックが時刻Ｔに完了した時に、ｋ個のソースシンボルが受け取られていると仮定する。そのソースブロックのｐ・ｋ個のリペアシンボルを、時間区間Ｔ’＋Ｔ／（１＋ｐ）からＴ’＋Ｔまで（長さｕ・Ｔの区間である）にわたって均等に送信されるようにスケジューリングする。
【０１４５】
ＦＥＣ送信機Ｃは、次の特性を有する。
【０１４６】
１．保護期間Ｔは、その間にソースブロックのソースシンボルが到着する時間期間と同一の持続時間である。
【０１４７】
２．ソースシンボルの全体的な送信レートの変動は、時間において倍率１／（１＋ｐ）だけ圧縮されるが、同一の大きさのままになる。これは、保護量が増えるにつれて、ＦＥＣ符号化されたストリームによって使用される帯域幅の量が増え、したがって、より多くの帯域幅を使用する時には、ストリーミングレートの変動の大きさを減らすことがより望ましいはずなので、いくつかのアプリケーションで完全に望ましくはない可能性がある。これは、固定持続時間のバースト消失に対して提供される保護のレベルが、消失がいつ発生するかに依存する可能性があることをも意味し、これは、望ましくない場合がある。しかし、特殊な事例として、ソースシンボルのオリジナルの送信レートが一定である場合に、ＦＥＣ符号化されたストリームの送信レートも一定であり、したがって、固定持続時間のバースト消失に関して提供される保護のレベルは、消失がいつ発生するかに依存しない。
【０１４８】
３．ＦＥＣエンドツーエンド待ち時間は、ＦＥＣ符号化待ち時間およびＦＥＣ復号化待ち時間が０に接近するので、Ｔ’＋ｕ・Ｔ程度に短くすることができる。
【０１４９】
４．ＦＥＣ受信機待ち時間は、ＦＥＣ復号化待ち時間が０に接近するので、Ｔ程度に短くすることができる。これは、（１＋ｐ）・ｋ個のシンボルのバッファリングだけが必要である（すべてのソースブロックがｋ個のソースシンボルを含むと仮定して）ことを意味する。これは、可能な最小限の量であり、したがって、これは望ましい。
【０１５０】
５．あるソースブロックのリペアシンボルは、次のソースブロックからのソースシンボルとインターリーブされない、すなわち、あるソースブロックのすべてのシンボルが、後続ソースブロックのシンボルが送信される前に送信される。これは、本質的に１つのソースブロックのシンボルだけを同時に記憶し、保存することを必要とするので、ＦＥＣ受信機の論理を単純にし、また、所与のソースブロックからの追加シンボルが今後は到着しないと判断し、そのソースブロックの復号化の試みをあきらめるべき時を判定するのを簡単にする。
【０１５１】
６．ＦＥＣ送信機は、最後のソースシンボルの到着と最初のリペアシンボルの送信との間にＴ’−ｕ・Ｔの時間遅れがあるので（Ｔ’は、ＦＥＣ符号化器の能力に基づいて適当に調整できるパラメータである）、ＦＥＣ符号化器が、最後のソースシンボルが受け取られた後にリペアシンボルを作るのかなりの長さの時間を要する可能性があることを考慮に入れる。
【０１５２】
したがって、全体的なＦＥＣ送信機Ｃは、上のリストの特性２で説明したように、ＦＥＣ送信機Ｃが、ソースシンボルの送信レートの変動のオリジナルの大きさを維持することを除いて、説明したそれぞれの形において望ましい。
【０１５３】
下で説明するＦＥＣ送信機Ｄは、ＦＥＣ送信機Ｃに関して上でリストした望ましい特性のすべてを維持するが、ソースシンボルの送信レートの変動の大きさを減衰させるという有益な結果をも維持する。したがって、ＦＥＣ送信機Ｄは、複数の利点を有し、いくつかの場合に好ましい実施形態であるものとすることができる。
【０１５４】
ＦＥＣ送信機Ｄ：あるソースブロックを形成するソースシンボルが、Ｔ秒の期間にわたって到着し、Ｔは、保護期間である。ｕ＝ｐ／（１＋ｐ）であるものとし、Ｔ’≧ｕ・Ｔであるものとし、ここで、Ｔ’−ｕ・Ｔは、あるソースブロックの最後のソースシンボルの受け取りの後に、ＦＥＣ符号化器がそのソースブロックの最初のリペアシンボルを生成し、下で規定する送信レートでそのソースブロックの後続リペアシンボルの生成を継続できるのに十分な時間である。ｔが、ＦＥＣ送信機での現在時刻であるものとする。この処理の各時点で、Ｂが、そのソースブロックについて受け取られたソースシンボルの個数であるものとし、Ｓが、ＦＥＣ送信機によってこれまでに送信されたソースシンボルの個数であるものとする。
【０１５５】
処理は、ソースブロックがＦＥＣ送信機によって開始される時に開始され、この処理は、ｔ＝０およびＢ＝Ｓ＝０に初期化する。次に、現在時刻ｔが、区間０≦ｔ≦Ｔ’に含まれる間に、ソースシンボルが受け取られるたびに、ＢにＢ＋１をセットし、現在時刻ｔが、区間Ｔ’＜ｔ≦Ｔに含まれる間に、ソースシンボルが受け取られるたびに、ＢにＢ＋１をセットし、時刻ｔに、式１０に従ってｙｔを定義し、ここで、現在時刻ｔの前の各時点ｘに、ＢｘおよびＳｘは、時刻ｘでのＢおよびＳのめいめいの値である。時刻ｔにｙｔ≧１である場合に、この処理は、次の受け取られているがまだ送信されていないソースシンボルを送信し、Ｓ＝Ｓ＋１をセットする。
2008546361.tif 000007
（式１０）
これらのステップに続いて、すべてのソースシンボルが、時刻Ｔまでに受け取られており、したがってソースブロックにｋ＝ＢＴ個のソースシンボルがある。この点で、この処理は、現在時刻ｔが時間の区間Ｔ＜ｔ≦Ｔ’＋Ｔ／（１＋ｐ）に含まれる間に、残りのＢＴ−ＳＴ個の未送信のソースシンボルをその区間にわたって均等に拡散して送信する。次に、この処理は、現在時刻ｔが時間の区間Ｔ／（１＋ｐ）＜ｔ≦Ｔ’＋Ｔに含まれる間に、ｐ・ｋ個のリペアシンボルをその区間にわたって均等に拡散して送信する。
【０１５６】
ＦＥＣ送信機Ｄは、ＦＥＣ送信機Ｃの望ましい特性を有し、さらに、ＦＥＣ送信機Ｃの特性２は、ＦＥＣ送信機Ｄについて、ソースストリーム全体のシンボルの全体的な送信レートの変動が減衰されるという点で、次に示すものに改善される。具体的に言うと、ソースストリームの変動は、Ｔ’が増えるにつれてより大きく減衰され、一般に、Ｔ’は、保護量が増えるにつれて増える。
【０１５７】
これは、保護量が増えるにつれて、ＦＥＣ符号化されたストリームによって使用される帯域幅の量が増え、したがって、より多くの帯域幅を使用する時に、ストリーミングレートの変動を減らすことがさらに望ましいので、望ましい。また、これは、変動が減衰する時に、固定持続時間のバースト停止がある時の消失に対して提供される保護のレベルが、停止がいつ発生するかにより弱く依存するので望ましく、これは、望ましい特性である。特殊な事例として、オリジナルのソースストリームが一定レートである場合に、ＦＥＣ符号化されたストリームも一定レートである。全体的なＦＥＣ送信機Ｄは、他の送信機より望ましいものである可能性があり、したがって、多くの条件について好ましい。
【０１５８】
ＦＥＣ送信機Ｄの多数の可能な変形形態があり、その一部は、本明細書で説明され、他の変形形態は、この開示を読んだ後に当業者に明白になるであろう。
【０１５９】
たとえば、ステップ３ｂには、ｙｔの計算があるが、類似する結果をもたらす正確な計算の代わりの単純な近似を含むこの計算を実行する多数の可能な方法がある。もう１つの例として、ステップ３ｃでは、条件ｙｔ≧１に基づいて別のソースシンボルをいつ送信すべきかに関する判断を、変更することができ、たとえば、条件ｙｔ≧０またはある定数αについてｙｔ≧αに置換することができる。そのような変形形態は、類似する結果をもたらす。変形形態のもう１つの例として、次のソースシンボルまたはリペアシンボルを個別に送信するのではなく、シンボルのグループを、各パケット内で一緒に受け取りまたは送信することができ、各パケット内で受け取られまたは送信されるグループのサイズは、パケットごとに変更することができる。この場合に、受け取られたシンボルを説明する手順、および次のソースシンボルまたはリペアシンボルをいつ送信すべきかに関する手順は、単純な形で簡単に変更することができる。
【０１６０】
もう１つの変形形態の例として、シンボルではなくビットが送信され、受信される、すなわち、潜在的に、一時にシンボル全体ではなくシンボルの諸部分が送信され、受信されるものとすることができ、シンボルを送信する手順およびシンボルを受信する手順は、たとえばシンボルではなくビット単位でまたは可変サイズパケットの単位でのデータの送信および受信に対処するように簡単に変更することができる。
【０１６１】
ＦＥＣ送信機Ｄの１つの可能な変形形態が、下で説明し、図８Ａ、８Ｂ、９、１０、１１、１２、および１３に示すＦＥＣ送信機Ｅである。ＦＥＣ送信機Ｅは、ＦＥＣ送信機Ｄに類似し、具体的には、Ｔは、保護期間の持続時間であり、ソースブロックの持続時間であり、ｕ＝ｐ／（１＋ｐ）であり、Ｔ’≧ｕ・Ｔは、送信機が現在のソースブロックのソースシンボルの受け取りを開始する時と、送信機が現在のソースブロックのソースシンボルの送信を開始する時との間の時間の持続時間である。ＦＥＣ送信機Ｅは、現在のソースブロックの処理を、４つの処理すなわち、図８Ａに示されているように、ソース初期処理、ソース中間処理、ソース最終処理、およびリペア送信処理に分解する。この４つの処理のそれぞれの相対的な時間区間および持続時間は、図８Ａで、それぞれ”時間区間”と示された列および”継続時間”と示された列に示されている。時間区間は、現在のソースブロックが開始される時刻に対して相対的に表され、したがって、ｔ＝０は、現在のソースブロックが開始される時刻に対応する。したがって、図８Ａに示されているように、ソース初期処理は、時刻ｔ＝０に開始され、時刻ｔ＝Ｔ’に終了し、したがって、持続時間Ｔ’を有する。同様に、ソース中間処理は、時刻ｔ＝Ｔ’に開始され、時刻ｔ＝Ｔに終了し、したがって、持続時間Ｔ−Ｔ’を有し、ソース最終処理は、時刻ｔ＝Ｔに開始され、時刻ｔ＝Ｔ’＋Ｔ／（１＋ｐ）に終了し、したがって、持続時間Ｔ’−ｕ・Ｔを有し、リペア送信処理は、時刻ｔ＝Ｔ’＋Ｔ／（１＋ｐ）に開始され、時刻ｔ＝Ｔ’＋Ｔに終了し、したがって、持続時間ｕ・Ｔを有する。
【０１６２】
図８Ｂに示されているように、異なるソースブロックに関する４つの処理が、オーバーラップしていることに留意されたい。たとえば、現在のソースブロックのソース初期処理は、まず、前のソースブロックのソース最終処理と同時であり、その後に、前のソースブロックのリペア送信処理と同時である。もう１つの例として、現在のソースブロックのソース最終処理および現在のソースブロックのリペア送信処理は、次のソースブロックのソース初期処理と同時である。
【０１６３】
図８Ｂに示されているように、各時点で、ソースシンボルが、正確に１つのソースブロックだけについて受け取られており、符号シンボルが、正確に１つのソースブロックだけについて送信されている。たとえば、現在のソースブロックのソース初期処理中には、符号シンボルが、前のソースブロックについて送信されており、ソースシンボルが、現在のソースブロックについて受け取られている。もう１つの例として、現在のソースブロックのソース中間処理中には、ソースシンボルが、現在のソースブロックについて受け取られており、符号シンボルが、現在のソースブロックについて送信されている。
【０１６４】
ＦＥＣ送信機Ｅは、次の特性を有する。（ａ）ソースシンボルが、Ｔ秒の間にソースブロックごとに受け取られ、（ｂ）符号シンボルが、Ｔ秒の間にソースブロックごとに送信され、（ｃ）あるソースブロックのソースシンボルの受け取りの始めとそのソースブロックのソースシンボルの送信の始めとの間にＴ’の時間持続時間があり、（ｄ）現在のソースブロックのすべてのソースシンボルが、次のソースブロックのソースシンボルが受け取られる前に受け取られ、（ｅ）現在のソースブロックのすべての符号シンボルが、次のソースブロックの符号シンボルが送信される前に送信される。したがって、ＦＥＣ送信機Ｅは、ソースブロックのインターリービングを全く有しない。
【０１６５】
図９に、ＦＥＣ送信機Ｅのソース初期処理を示す。図９のステップ９０５で、現在のソースブロックが始まり、したがって、現在のソースブロックの、受け取られたソースシンボルの個数Ｂと送信されたソースシンボルの個数Ｓとの両方を０に初期化し、現在時刻ｔに０をセットし、現在のソースブロックのソースシンボルをバッファリングするのに使用されるＢＵＦＦＥＲを、空になるように初期化する。ステップ９１０で、検査を行って、現在時刻ｔがＴ’以上であるかどうかを調べ、そうである場合には、この処理は、ステップ９２０で図１０のソース中間処理に進む。ステップ９１０でのテストの実施が、一般に、十分に頻繁に行われ、その結果、そのテストが真である時にｔがＴ’に非常に近くなることを意味することに留意されたい。同一のコメントが、ＦＥＣ送信機Ｅのすべての処理で２つの時刻の間で不等比較が行われる、下で説明するすべてのさらなるステップにあてはまる。ステップ９１０で、ｔがＴ’未満である場合には、ステップ９３０で検査を行って、次のソースシンボルが到着しているかどうかを調べる。次のソースシンボルが到着していない場合には、この処理はステップ９１０にループバックするが、次のソースシンボルが到着している場合には、ステップ９４０で、受け取られたソースシンボルの個数Ｂをインクリメントし、受け取られたソースシンボルをＢＵＦＦＥＲに追加し、その後、処理はステップ９１０にループバックする。
【０１６６】
図１０に、ＦＥＣ送信機Ｅのソース中間処理を示す。図１０のステップ１００５で、ＴＬＡＳＴの値を現在時刻ｔ（Ｔ’以上であるが、図９のステップ９１０でのテストの精度に依存して、Ｔ’に非常に近い）に初期化し、ＴＮＥＸＴをＴＬＡＳＴ＋Ｔ’／（（１＋ｐ）・Ｂ）に初期化する。ＴＮＥＸＴは、次のソースシンボルが送信をスケジューリングされる時刻である。ステップ１０１０で、検査を行って、現在時刻ｔがＴ以上であるかどうかを調べ、そうである場合には、この処理はステップ１０２０に進み、ステップ１０２０は、現在のソースブロックのソースシンボルの受け取りが完了したことを示し、したがって、ＢＵＦＦＥＲは、ソースブロックのソースシンボルのすべてを含み、処理は、ステップ１０２０で図１１に示されたソース最終処理に進む。ステップ１０１０でｔがＴ未満の場合には、ステップ１０４０で、検査を行って、ｔがＴＮＥＸＴ以上であるかどうかを調べる。ステップ１０４０でのテストが真である場合には、次のソースシンボルを送信すべき時であり、したがって、処理はステップ１０８０に進む。ステップ１０８０では、まだ送信されていない最初に受け取られたソースシンボルを送信し、送信されたソースシンボルの個数Ｓを１つインクリメントし、ＴＬＡＳＴを現在時刻に更新し、ＴＮＥＸＴをＴＬＡＳＴ＋（Ｔ’−ｕ・ＴＬＡＳＴ）／（Ｂ−Ｓ）に更新し、その後、処理はステップ１０１０にループバックする。ステップ１０４０でのテストが偽である場合には、ステップ１０５０で検査を行って、ソースシンボルが到着したかどうかを調べる。ソースシンボルが到着していない場合には、処理は、ステップ１０１０にループバックするが、ソースシンボルが到着している場合には、処理はステップ１０６０に継続する。ステップ１０６０では、到着したソースシンボルをＢＵＦＦＥＲの末尾に追加し、Ｂの値を１つインクリメントし、ＴＮＥＸＴを、ソースシンボルの受け取りに基づいてＴＬＡＳＴ＋（Ｔ’−ｕ・ＴＬＡＳＴ）／（Ｂ−Ｓ）に更新し、その後、処理はステップ１０１０に即座にループバックする。
【０１６７】
図１１に、ＦＥＣ送信機Ｅのソース最終処理を示す。図１１のステップ１１０５で、ＴＬＡＳＴの値を現在時刻ｔ（Ｔ以上であるが、図１０のステップ１０１０でのテストの精度に依存して、Ｔに非常に近い）に初期化し、ＴＮＥＸＴをＴＬＡＳＴ＋（Ｔ’−ｕ・Ｔ）／（Ｂ−Ｓ）に初期化する。ＴＮＥＸＴは、次のソースシンボルが送信をスケジューリングされる時刻である。ステップ１１１０で、検査を行って、現在時刻ｔがＴ’＋Ｔ／（１＋ｐ）と等しいかどうかを調べ、そうである場合には、処理はステップ１１２０に進み、ステップ１１２０は、現在のソースブロックのソースシンボルの送信が完了したことを示し、処理は、ステップ１１２０で図１２に示されたリペア送信処理に進む。ステップ１１１０でｔがＴ’＋Ｔ／（１＋ｐ）と等しくない場合には、ステップ１１３０で、検査を行って、ｔがＴＮＥＸＴと等しいかどうかを調べる。ステップ１１３０のテストが真である場合には、次のソースシンボルを送信すべき時であり、したがって、処理はステップ１１４０に進む。ステップ１１４０では、まだ送信されていない最初に受け取られたソースシンボルを送信し、送信されたソースシンボルの個数Ｓを１つインクリメントし、ＴＬＡＳＴを現在時刻ｔに更新し、ＴＮＥＸＴをＴＬＡＳＴ＋（Ｔ’＋Ｔ／（１＋ｐ）−ＴＬＡＳＴ）／（Ｂ−Ｓ）に更新し、その後、処理はステップ１１１０にループバックする。ステップ１１３０でのテストが偽である場合には、処理はステップ１１１０に即座にループバックする。
【０１６８】
図１２に、ＦＥＣ送信機Ｅのソースリペア処理を示す。図１２のステップ１２０５で、ＴＬＡＳＴの値を現在時刻ｔ（Ｔ’＋Ｔ／（１＋ｐ）以上であるが、図１１のステップ１１１０でのテストの精度に依存して、Ｔ’＋Ｔ／（１＋ｐ）に非常に近い）に初期化し、ＴＤＥＬＴＡにＴ／（（１＋ｐ）・Ｂ）をセットし、ＴＮＥＸＴをＴＬＡＳＴ＋ＴＤＥＬＴＡに初期化し、ここで、ＴＤＥＬＴＡは、各リペアシンボルの間の時間増分であり、ＴＮＥＸＴは、次のリペアシンボルが送信をスケジューリングされる時刻である。ステップ１２１０で、検査を行って、現在時刻ｔがＴ’＋Ｔ以上であるかどうかを調べ、そうである場合には、処理はステップ１２２０に進み、ステップ１２２０は、現在のソースブロックのリペアシンボルの送信が完了したことを示し、したがって、現在のソースブロックが完了し、したがって、ＢＵＦＦＥＲを、後続ソースブロックに再利用することができる。ステップ１２１０でｔがＴ’＋Ｔ未満である場合には、ステップ１２３０で検査を行って、ｔがＴＮＥＸＴ以上であるかどうかを調べる。ステップ１２３０のテストが真である場合には、次のリペアシンボルを送信すべき時であり、したがって、処理はステップ１２４０に進む。ステップ１２４０では、ＢＵＦＦＥＲに格納されたソースブロックに基づいて、ソースブロックについて新しいリペアシンボルを生成し、送信し、ＴＬＡＳＴをＴＮＥＸＴに更新し、ＴＮＥＸＴをＴＬＡＳＴ＋ＴＤＥＬＴＡに更新し、その後、処理はステップ１２１０にループバックする。ステップ１２３０でのテストが偽の場合には、処理はステップ１２１０に即座にループバックする。
【０１６９】
ＦＥＣ送信機Ｅについて説明した処理と同時に発生する他の処理および計算がある場合がある。たとえば、リペアシンボルの生成に備えて４つの処理のうちの１つまたは複数と同時に発生するＢＵＦＦＥＲの前処理がある可能性があり、前処理されたＢＵＦＦＥＲは、リペア処理のステップ１２４０でリペアシンボルを生成するための基礎として使用することができる。同一のまたは類似する結果を達成する他の同等の処理がある可能性もあり、たとえば、リペアシンボルを、リペア処理のステップ１２４０で説明したように送信される直前に生成するのではなく、送信される時の前に生成することができる。
【０１７０】
ソースブロックインターリービング
一部のＦＥＣ符号は、任意の実用的サイズのソースブロックにまたがって効率的に符号化することができ、任意のサイズのシンボルを効率的に扱うことができる。しかし、他のＦＥＣ符号は、より大きいソースブロックを孤立的に扱うことを難しくする、実用的制限を有する。これは、ストリーミングレートがより高い時および／またはシンボルを必ずより短くしなければならない（たとえば、シンボルを搬送する、より短いパケットの使用のゆえに）時および／またはより長い保護期間が使用される時に、特に心配の種である。
【０１７１】
例として、リードソロモン符号は、２５６個を超える要素を有する有限体を扱う時に非実用的になる可能性があり、２５６個の要素の有限体を扱うことは、ソースブロックあたりの符号シンボルの個数を２５７個までに制限する。この場合に、この問題に対する解決策の１つは、ソースブロックをインターリーブすること、すなわち、異なるソースブロックからのシンボルを混合された順序で送信することである。したがって、全体的には、前のセクションで説明したように、ソースブロックの間のインターリービングを全く有しないことが望ましいが、一部のＦＥＣ符号に関しては、複数のソースブロックと、ソースブロックあたりのシンボルの個数とを使用するためにインターリービングを可能にすると同時に、あるソースブロックのオリジナルのストリーミング時間より長い、そのソースブロックの保護期間を可能にすることが、有用である。このセクションでは、ソースブロックをインターリーブするＦＥＣ送信機のいくつかの好ましい実施形態を提供する。
【０１７２】
いくつかの場合に、ＦＥＣ送信機が異なるソースブロックからのシンボルの送信をインターリーブすることを可能にし、その結果、各ソースブロックのシンボルを、そのソースブロックのストリーミング時間より長い保護期間にまたがって拡散できるようにすることに関する利益がある場合がある。これを行う理由の１つは、時間依存消失（たとえば、バースト的消失）に対するよりよい保護がもたらされること、すなわち、ソースブロックに関する保護期間が長くなるにつれて、固定持続時間のバースト消失に対する保護をもたらすのに、より少ない保護量が必要になることである。あるソースブロックのオリジナルのストリーミング時間を、ｔ秒とすることができ、そのソースブロックの所望の保護期間を、ｐ秒とすることができ、ここで、ｐ＞ｔである。インターリービングを使用するＦＥＣ送信機の他の望ましい特性には、（１）ソースパケットがそのオリジナルの順序で送信され、（２）各後続ソースブロックの最後の符号シンボルが受信される時刻が、経時的にできる限り均一に拡散されることが含まれる。
【０１７３】
第１のインターリービングの特性（ソースパケットがオリジナルの順序で送信される）は、受信機のタイプごとにＦＥＣ送信機で導入される待ち時間を最小化し、また、ＦＥＣの使用が、非ＦＥＣ受信機の大きい追加の待ち時間を引き起こさない。これは、受信機がストリームに同調する時にＦＥＣ受信機で導入される待ち時間をも最小化する、すなわち、ＦＥＣ受信機が最初にパケットを受信し始める時とそのＦＥＣ受信機がそれらを安全に使用可能にし始めることができる時との間の遅延を最小化する。
【０１７４】
第２のインターリービングの特性（各後続ソースブロックの最後の符号シンボルが受信される時刻が、経時的にできる限り均一に拡散される）は、ＣＰＵのより滑らかな使用をもたらす。最後の符号シンボルが、あるソースブロックについて受信される時刻は、そのソースブロックを復号化するためのすべての情報がＦＥＣ復号化器から使用可能になる時刻であり、これは、通常、ＦＥＣ復号化器が規定された復号化待ち時間バジェット内で復号化を終了するために最も激しく働かなければならないワーストケース消失条件の下の時である。したがって、ソースブロックの最後の符号シンボルの受信を均一に拡散することによって、ＦＥＣ復号化に関するＣＰＵのより滑らかな使用が可能になる。
【０１７５】
この説明では、多数の例で、ＦＥＣ送信機がパケットでシンボルを伝送すると仮定し、各パケットは、異なる個数のシンボルを含むことができる。下の説明を単純にするために、オリジナルソースストリームでのソースパケット順序が、０、１、２、３、４、５、６、７、８、９、１０、１１、１２、１３、１４、１５、１６、１７などであると仮定し、ここで、この値は、パケットのインデックスを示す。
【０１７６】
任意の時点にアクティブなｓ個のソースブロックがあり、ソースブロックあたりｋ個のソースパケットがあるものとする（この単純化された説明では、すべてのソースパケットが同一の長さであると仮定する）。下のＦＥＣ送信機は、ソースブロックがソースパケットからどのように形成されるかと、ソースパケットが送信される順序とを説明するものである。あるソースブロックのリペアパケットは、そのソースブロックのソースパケットの前に、後に、またはそれと混合されてのいずれかで送信することができ、本明細書で説明するように、異なる戦略には利点がある。
【０１７７】
ＦＥＣ送信機Ｆ：送信パターンは、各ｎ＝ｓ・ｋ個のパケットを繰り返し、ここで、ｎは、保護期間内のソースパケットの個数である。したがって、これは、それぞれがｋ個のソースパケットのｓ個のソースブロックに区分された、保護期間内のｎ個のソースパケットと考えることができる。ソースパケットの送信順序は、そのオリジナルの送信順序である。ｉ＝０，．．．，ｓ−１について、ｉ番目のソースブロックは、ソースパケットｉ，ｓ＋ｉ，２ｓ＋ｉ，．．．，（ｋ−１）・ｓ＋ｉを含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、各ソースブロックの最初のリペアパケットは、各ソースブロックの第２のリペアパケットが送信される前に送信される。それぞれ６個のソースパケットの３つのソースブロックを有する例（したがって、保護期間は、持続時間においてソースパケット１８個分である）は、次の通りである。
【０１７８】
ソースブロック０は、ソースパケット０、３、６、９、１２、１５を含み、
ソースブロック１は、ソースパケット１、４、７、１０、１３、１６を含み、
ソースブロック２は、ソースパケット２、５、８、１１、１４、１７を含む。
【０１７９】
ＦＥＣ送信機Ｆは、第１のインターリービングの特性を満足するが、第２のインターリービングの特性を満足しない。第１のインターリービングの特性が満足されるのは、単に、ソースパケットの送信順序がオリジナルの送信順序であるからである。ＦＥＣ送信機Ｆが、第２のインターリービングの特性を満足しない理由を知るために、連続するソースパケット０、１、２が、それぞれソースブロック０、１、２からのパケットであり、したがって、この３つのソースブロックの復号化時間が、連続するパケットにまたがる、すなわち、ソースブロックのこのインターリービングに関する復号化時間が、繰り返すパターン”１，１，１，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，１，１，１，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０．．．”であることに留意されたい。このパターンでは、各項目が、パケットの受信を示し、１は、その項目がソースブロックのうちの１つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、バースト的であり、均一に拡散してはおらず、したがって、この例から、ＦＥＣ送信機Ｆが、上の第２のインターリービングの特性を満足しないことがわかる。
【０１８０】
ＦＥＣ送信機Ｇ：送信パターンは、各ｎ＝ｓ・ｋ個のパケットを繰り返し、ここで、ｎは、保護期間内のソースパケットの個数である。したがって、これは、それぞれがｋ個のソースパケットのｓ個のソースブロックに区分された、保護期間内のｎ個のソースパケットと考えることができる。ソースパケットの送信順序は、０，ｋ，２ｋ，．．．，（ｓ−１）・ｋ，１，ｋ＋１，２ｋ＋１，．．．，（ｓ−１）・ｋ＋１，．．．，ｋ−１，２ｋ−１，３ｋ−１，．．．，ｓ・ｋ−１である。ｉ＝０，．．．，ｓ−１について、ｉ番目のソースブロックは、ソースパケットｋ・ｉ，ｋ・ｉ＋１，ｋ・ｉ＋２，．．．，ｋ・ｉ＋ｋ−１を含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、各ソースブロックの最初のリペアパケットは、各ソースブロックの第２のリペアパケットが送信される前に送信される。それぞれ６個のソースパケットの３つのソースブロックを有する例（したがって、保護期間は、持続時間においてソースパケット１８個分である）は、次の通りである。
【０１８１】
ソースブロック０は、ソースパケット０、１、２、３、４、５を含み、
ソースブロック１は、ソースパケット６、７、８、９、１０、１１を含み、
ソースブロック２は、ソースパケット１２、１３、１４、１５、１６、１７を含む。
【０１８２】
ソースパケットの送信順序は、次の通りである。０、６、１２、１、７、１３、２、８、１４、３、９、１５、４、１０、１６、５、１１、１７。
【０１８３】
ＦＥＣ送信機Ｇは、第１のインターリービングの特性を満足しないが、第２のインターリービングの特性を満足する。第１のインターリービングの特性が満足されないのは、単に、ソースパケットの送信順序がオリジナルの送信順序ではないからである。ＦＥＣ送信機Ｇが、第２のインターリービングの特性を満足する理由を知るために、３つのソースブロックの復号化時間が、これらのパケットにまたがって均一に拡散される、すなわち、ソースブロックのこのインターリービングの復号化時間が、繰り返しパターン１，０，０，０，０，０，１，０，０，０，０，０，１，０，０，０，０，０．．．であることに留意されたい。このパターンでは、各項目が、パケットの受信を示し、１は、その項目がソースブロックのうちの１つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、均一に拡散されており、したがって、この例から、ＦＥＣ送信機Ｇが、上の第２のインターリービングの特性を満足することがわかる。
【０１８４】
第１のインターリービングの特性と第２のインターリービングの特性との両方を同時に満足するインターリーブＦＥＣ送信機の次の実施形態について、個々のソースブロックごとに、前のセクションで説明した単一ソースブロックＦＥＣ送信機の好ましい実施形態が、ソースブロックごとにいつシンボルを送信するかを決定するのに使用されると仮定する。
【０１８５】
ＦＥＣ送信機Ｈ：ソースパケットの送信順序は、そのオリジナルの送信順序である。このＦＥＣ送信機を説明するために、ソースパケットは、概念上、ｓ個の列を有する行列の行に順次配置され、ｉ＝０，．．．，ｓ−１について、列ｉは、ｉ，ｓ＋ｉ，２ｓ＋ｉ，．．．，（ｋ−１）・ｓ＋ｉ  ｍｏｄｕｌｏ  ｎのいずれかと合同であるインデックスを有するソースパケットを含む。
【０１８６】
ソースブロックは、１列の中のソースパケットの連続するシーケンスから形成される。列ｉの最初のソースブロックは、インデックスｉを有するソースパケットから始まる。列ｉ内の各後続のソースブロックは、インデックスｆｌｏｏｒ（ｋ・ｉ／ｓ）・ｓ＋ｉ  ｍｏｄ  ｎを有するソースパケットから始まり、したがって、列ｉ内の最初のソースブロックを除くすべてのソースブロックが、ｋ個のソースパケットを含む。各ソースブロックのリペアパケットは、ソースパケットと同一の順序でインターリーブされる、すなわち、列ｉ内の所与のソースブロックのすべてのリペアパケットは、列ｉ内の後続ソースブロックのリペアパケットの前に送信される。それぞれ６個のソースパケットの３つのソースブロックを有する例（したがって、保護期間は、持続時間においてソースパケット１８個分である）は、次の通りである。
【０１８７】
上で説明した行列は、
１００
０００
０１０
０００
００１
０００
である。
【０１８８】
したがって、列０の第１のソースブロックは、ソースパケット０、３、６、９、１２、１５を含み、列１の第１のソースブロックは、ソースパケット１、４を含み、列１の第２のソースブロックは、ソースパケット７、１０、１３、１６、１９、２２を含み、列２の第１のソースブロックは、ソースパケット２、５、８、１１を含み、列２の第２のソースブロックは、ソースパケット１４、１７、２０、２３、２６、２９を含む、などである。
【０１８９】
ＦＥＣ送信機Ｈは、第１のインターリービングの特性と第２のインターリービングの特性との両方を満足する。第１のインターリービングの特性が満足されるのは、単に、ソースパケットの送信順序がオリジナルの送信順序であるからである。ＦＥＣ送信機Ｈが、第２のインターリービングの特性を満足する理由を知るために、ソースブロックのこのインターリービングの復号化時間が、繰り返しパターン”１，０，０，０，０，０，０，１，０，０，０，０，０，０，１，０，０，０”であることに留意されたい。このパターンでは、各項目が、ソースパケットの受信を示し、１は、その項目がソースブロックのうちの１つに関する復号化時間であることを示す。このパターンからわかるように、復号化時間は、できる限り均一に拡散されており、したがって、この例から、ＦＥＣ送信機Ｆが、上の第２のインターリービングの特性を満足することがわかる。
【０１９０】
上の特性（１）および（２）を満足し、この開示を読んだ後に見つけることができる、ＦＥＣ送信機Ｈの多数の変形形態がある。たとえば、上で説明したＦＥＣ送信機Ｈは、ストリーム内のソースパケットのすべてが同一のサイズである時およびソースパケットのストリーミングレートが一定である時に、良好に働く。下で説明するＦＥＣ送信機Ｉは、ソースパケットが可変長である時および／またはソースパケットのストリーミングレートが一定でない時に良好に働く、ＦＥＣ送信機Ｈの変形形態である。
【０１９１】
ＦＥＣ送信機Ｉ：所望の保護期間がｔ秒であり、任意の時点にｓ個のアクティブなソースブロックがあるものとする。この処理を、図１３を参照して説明する。図１３のステップ１３０５で、ｚ＝ｔ／ｓに、あるソースブロックの終りと別のソースブロックの始めとの間の秒単位の時間増分をセットし、バイトカウンタＢ０，Ｂ１，．．．，Ｂｓ−１のすべてを０に初期化する。ステップ１３１０で、変数ｉを０に初期化し、現在時刻を０に初期化し、変数ｉは、どのソースブロックが次に終了するかを記憶するのに使用され、現在時刻は、ソースブロックがいつ終了するかを記憶するのに使用される。ステップ１３１４で、現在時刻を、ＦＥＣ送信機のクロックを使用して、ステップ１３１０で最初に０にセットされた時から経過した時間の長さに従ってインクリメントして、更新する。ステップ１３１８で、検査を行って、現在時刻がｚ未満であるかどうかを調べ、これが真である場合には、処理は、ステップ１３２０に継続して、次のソースパケットが使用可能であるかどうかを調べる。使用可能なソースパケットがない場合には、処理はステップ１３１４に戻るが、使用可能な次のソースパケットがある場合には、ステップ１３３０で、次のソースパケットを受け入れ、Ｘは、バイト単位のそのソースパケットのサイズである。ステップ１３４０で、Ｂｊが最小になるインデックスｊを計算する。ステップ１３５０で、受け入れたばかりのソースパケットをソースブロックｊに追加し、ステップ１３６０で、Ｂｊの値をこのソースパケットのサイズＸだけインクリメントし、処理は、ステップ１３１４に戻る。そうではなく、ステップ１３１８で、現在時刻が少なくともｚである場合には、ステップ１３７０で、ｚの値をｔ／ｓだけインクリメントし、ステップ１３８０で、ｉの値を、１つインクリメントし、アクティブなソースブロックの個数ｓを法とする剰余をとり、ステップ１３９０で、インデックスｉを有する現在のソースブロックを終了し、インデックスｉを有する新しいソースブロックを開始し、その後、処理はステップ１３１４に戻る。
【０１９２】
この処理がどのように働くかの例として、ｔ＝６秒かつｓ＝３であり、したがって、ｔ／ｓ＝２であるものとする。最初の２秒のうちに受け取られるソースパケットが、次の通りであるものとする。
【０１９３】
サイズが５００バイトのソースパケット０
サイズが７５０バイトのソースパケット１
サイズが４００バイトのソースパケット２
サイズが４９０バイトのソースパケット３
サイズが７００バイトのソースパケット４
また、同一の極小値を有する複数のバイトカウンタがある場合に、最小のインデックスを有するバイトカウンタを、最小であると考えるものとする。すると、ソースパケット０は、ソースブロック０に追加され、Ｂ０＝５００であり、ソースパケット１は、ソースブロック１に追加され、Ｂ１＝７５０であり、ソースパケット２は、ソースブロック２に追加され、Ｂ２＝４００であり、ソースパケット３は、ソースブロック２に追加され、Ｂ２＝８９０であり、ソースパケット４は、ソースブロック０に追加され、Ｂ０＝１２００である。
【０１９４】
同一の例を継続すると、現在時刻が２秒に達する時に、ソースブロック１は、終了し、サイズ７５０バイトのソースパケット１だけを含み、新しいソースブロック１が、開始される。次が、後続の２秒に送信機に到着するソースパケットのシーケンスを記述するものとする。
【０１９５】
サイズが５００バイトのソースパケット５
サイズが３８０バイトのソースパケット６
サイズが４００バイトのソースパケット７
サイズが６００バイトのソースパケット８
サイズが７００バイトのソースパケット９
サイズが４００バイトのソースパケット１０
サイズが３５０バイトのソースパケット１１
サイズが８００バイトのソースパケット１２
サイズが２００バイトのソースパケット１３
サイズが５００バイトのソースパケット１４
この時点で、ソースブロック２は、終了し、合計２７７０バイトのソースパケットすなわち、ソースパケット２、３、６、９、１２を含み、新しいソースブロック２が、開始される。次のソースパケットのシーケンスが、後続の２秒に送信機に到着するものとする。
【０１９６】
サイズが３５０バイトのソースパケット１５
サイズが５００バイトのソースパケット１６
サイズが４５０バイトのソースパケット１７
サイズが８００バイトのソースパケット１８
サイズが６５０バイトのソースパケット１９
サイズが４００バイトのソースパケット２０
サイズが６００バイトのソースパケット２１
サイズが３５０バイトのソースパケット２２
サイズが２００バイトのソースパケット２３
サイズが６００バイトのソースパケット２４
この時点で、ソースブロック０は、終了し、合計４１５０バイトのソースパケットすなわち、ソースパケット０、４、７、１０、１３、１４、１７、２０、および２１を含み、新しいソースブロック０が、開始される。
【０１９７】
ＦＥＣ送信機Ｉは、各列に割り振られるソースパケットのバイトの総数が、各時点でできる限り等しくなり、ソースブロックの復号化時間が、ｚ＝ｔ／ｓの区間で経時的に等しく拡散されるという特性を有する。ソースパケットレートが一定であり、ソースパケットサイズがすべて同一である場合に、ＦＥＣ送信機Ｉが、本質的にＦＥＣ送信機Ｈと同一の解決策をもたらすことに留意されたい。たとえば、上の例で、それぞれ２秒の６つのソースパケットがあり、ソースパケットのすべてがサイズにおいて１０００バイトである場合に、ＦＥＣ送信機Ｉは、次の行列を作る。
【０１９８】
０００
０１０
０００
００１
０００
１００
０００
０１０
０００
００１
０００
１００
この例では、各ソースブロック内のソースパケットの個数が６であり、インターリービングパターンが、上のＦＥＣ送信機Ｈに関するインターリービングの例の単純なシフトであることに留意されたい。
【０１９９】
本発明を、例示的実施形態に関して説明してきたが、当業者は、多数の変更が可能であることを認めるであろう。たとえば、本明細書で説明した処理は、ハードウェア構成要素、ソフトウェア構成要素、および／またはその任意の組合せを使用して実施することができる。したがって、本発明を、例示的実施形態に関して説明したが、本発明が、添付の特許請求の範囲の範囲に含まれるすべての修正形態および同等物を含むことが意図されていることを了解されたい。
【０２００】
関連出願の相互参照
本願は、参照によってその全体が組み込まれている２００５年６月１０日出願の米国仮出願第６０／６８９，３３３号の利益を主張し、その非仮出願である。
【図面の簡単な説明】
【０２０１】
【図１】本発明の一実施形態による通信システムを示すブロック図である。
【図２】受信機遅延を示す図である。
【図３Ａ】受信機遅延の成分を例示する図である。
【図３Ｂ】復号化中のＦＥＣに関するＣＰＵ使用率を例示する図である。
【図４】本発明の一実施形態に従って使用可能な復号化行列の例を示す図である。
【図５】本発明の一実施形態による復号化処理の一部を示すフローチャートである。
【図６】本発明の一実施形態による復号化処理の一部を示すもう１つのフローチャートである。
【図７】復号化ステップのうちの１つの、変形形態を示すフローチャートである。
【図８Ａ】ソースブロックの処理の異なるフェーズを示す図である。
【図８Ｂ】連続するソースブロックの処理の異なるフェーズの間の関係を示す図である。
【図９】ＦＥＣ送信機のソース初期処理を示すフローチャートである。
【図１０】ＦＥＣ送信機のソース中間処理を示すフローチャートである。
【図１１】ＦＥＣ送信機のソース最終処理を示すフローチャートである。
【図１２】ＦＥＣ送信機のソースリペア処理を示すフローチャートである。
【図１３】ＦＥＣ送信機に関するフローチャートである。
【図１】
2008546361.tif 000008
【図２】
2008546361.tif 000009
【図３Ａ】
2008546361.tif 000010
【図３Ｂ】
2008546361.tif 000011
【図４】
2008546361.tif 000012
【図５】
2008546361.tif 000013
【図６】
2008546361.tif 000014
【図７】
2008546361.tif 000015
【図８Ａ】
2008546361.tif 000016
【図８Ｂ】
2008546361.tif 000017
【図９】
2008546361.tif 000018
【図１０】
2008546361.tif 000019
【図１１】
2008546361.tif 000020
【図１２】
2008546361.tif 000021
【図１３】
2008546361.tif 000022