ファイルダウンロードおよびストリーミングのシステム
通信チャネルを介して転送元から転送先まで転送するデータを符号化する方法が提供される。入力シンボルの順序集合に作用して、入力シンボルから複数の冗長シンボルを生成する方法を含む。入力シンボルおよび冗長シンボルを含むシンボルの合成セットから複数の出力シンボルを生成する方法を含む。ここで、可能な出力シンボルの数はシンボルの合成セットのシンボル数に比較し非常に大きい。ここで、少なくとも一つの出力シンボルはシンボルの合成セットの複数のシンボルから、シンボルおよび入力シンボルの順序集合が出力シンボルのいかなる所定数からも所望の精度まで再生できるようなものの合成セットのシンボルの全て少ないものから生成される。
第1の入力シンボルを使用して算出される第1のスタティックシンボル群が、該第1の入力シンボルとは互いに異なる第2の入力シンボルを使用して算出される第2のスタティックシンボル群と弱い共通の帰属関係を有するように、確定的過程において転送される順序付けられた入力シンボル群から複数の冗長シンボルを生成する。
第1の入力シンボルを使用して算出される第1のスタティックシンボル群が、該第1の入力シンボルとは互いに異なる第2の入力シンボルを使用して算出される第2のスタティックシンボル群と弱い共通の帰属関係を有するように、確定的過程において転送される順序付けられた入力シンボル群から複数の冗長シンボルを生成する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、通信システムにおける符号化、復号化に関するものであり、より詳細には通信データの誤りおよびギャップを考慮した符号化、復号化を行う通信システムに関するものである。実施例において、データは、ブロードキャストまたはマルチキャスト無線ネットワークを介して受信機に転送される。
【背景技術】
【0002】
送り手と受け手との間で通信チャネルを介して行うファイルおよびストリームの転送は多くの文献の主題として取り上げられてきた。好ましくは、受け手は、送り手からチャネルを介して送信される正確なデータのコピーをあるレベルの確実性をもって受信することを望む。ほとんどの物理的に実現可能なシステムがそうであるように、チャネルは完全な忠実度を有していないため、転送により消失するか歪められるデータを取り扱う方法に関心が生じる。受け手は、いつ破損データが誤ってデータ受信されたかの判断を常に行えるとは限らないので、通常、破損データ(誤り)に比較し欠落データ(消去)を取扱うのは容易である。多くの誤り訂正符号は、消去および/または誤りを修正するために開発された。一般的に、データが送信されているチャネルおよび送信されているデータの性質の不忠実度に関する何らかの情報に基づいて使用する特定の符号(コード)が選択される。たとえば、チャネルが長期間の不忠実度を有することが既知の場合、そのアプリケーションのためにはバースト誤り符号が最適であり得る。短くまれな誤りだけが予想される場合、簡単なパリティ符号が最善であり得る。
【0003】
送信機および受信機が通信のために必要とされる演算能力および電力の全てを有し、送受信装置間のチャネルが相対的にエラーフリーの通信を可能とするのに十分クリーンであるときに、データ転送は直接なされる。そして、チャネルが悪環境であるか、または、送信機および/または受信機の能力が制限されている場合に、データ転送の問題はより難しくなる。
【0004】
1つのソリューションは、受信機が転送における消去および誤りから回復可能とするために、データを送信機で符号化する前方エラー訂正(FEC)技術を活用する方法である。受信機が送信機に誤りについての通信が可能な受信機から送信機への逆方向チャネルが利用可能な場合、その伝送プロセスを調整可能である。しかし、しばしば逆方向チャネルは利用可能ではない。たとえば、送信機が多数の受信機に対して送信している場合、送信機はそれらの全ての受信機からの逆方向チャネルを処理することが可能でないかもしれない。その結果、通信プロトコルはしばしば逆方向チャネルなしで設計されることを必要とし、そして、送信機はこれらのチャネル状況の全容無しに広く様々なチャネル状況を取扱わなければならないかもしれない。
【0005】
受信機がポータブルまたは移動可能である低出力の小型デバイスであり高帯域でデータを受信することを必要とする場合、送信機と受信機間のデータ転送の問題はより難しくなる。たとえば、ファイルまたはストリームをブロードキャストまたはマルチキャストにより、固定された送信機から多数もしくは不確定数のポータブルまたは移動可能な受信機に配信するよう設定される無線ネットワークであり、受信機が演算能力、記憶容量、利用できる電力、アンテナサイズ、デバイスサイズおよびその他の設計制約条件において拘束される場合である。
【0006】
このようなシステムでは、逆方向チャネルが少ないか皆無であり、メモリー制限、コンピューティングサイクル制限、移動可能性およびタイミングを含む考慮が必要である。各々の受信機の電源の予測不可能なオン/オフ、範囲の出入り、リンクエラー、セル切替、セル内輻輳によるファイルまたはストリームパケットに対する強制的一時的な優先度引き下げなどにより損失が発生するため、望ましくは、潜在的に大きい数の受信機に配信するために必要なデータの転送時間の最小化するよう設計しなければならない。
【0007】
データ転送のために使用するパケットプロトコルの場合、パケット網を通じて送信されるファイル、ストリームまたは他のデータブロックは等しいサイズ入力シンボルに仕切られ、入力シンボルは連続的なパケットとして配置される。入力シンボルが実際にビットストリームに分解されるか否かに関わらず、入力シンボルの”サイズ”はビット単位で測定することができる。そして、入力シンボルが2M個のシンボルのアルファベットから選択される場合、入力シンボルはMビットのサイズを有する。この種のパケットベースの通信システムにおいて、パケットに基づいた符号体系が適切である。指定された受け手がネットワークによる消去が発生したにもかかわらずオリジナルファイルの正確なコピーを回復可能な場合、ファイル転送は信頼性が高いと呼ばれる。指定された受け手がネットワークによる消去が発生したにもかかわらずタイムリーな方法でストリーム各部の正確なコピーを回復可能な場合、ストリーム転送は信頼性が高いと呼ばれる。また、ファイルまたはストリームの一部が回復可能でない、または、ストリーミングにおいてストリームの一部がただちに回復可能ではない場合などには、ファイル転送およびストリーム転送はいくらか信頼性が高くありえる。パケット損失は、散発的な輻輳の発生によりルータのバッファリングメカニズムが処理限界に達し入力パケットが強制的にドロップされることにより生じる。そのため、転送中の消去発生に対する保護について多くの研究がなされてきた。
【0008】
ファイルまたはストリームの入力シンボルから任意数の出力シンボルを生成する連鎖反応符号を使用することが知られている。受信機が、既に知っているデータを複製する追加データを受信する情報複製の方法に対して、この方法には情報付加的な出力シンボルの生成を含む多くの用途がある。連鎖反応符号を生成、利用、動作している新規の技術がいくつか公開されており、たとえば、Lubyに発行される米国特許第6,307,487号”Information Additive Code Generator and Decoder for Communication Systems”(”ルビーI”)、Lubyらに発行される米国特許第6,320,520号”Information Additive Group Code Generator and Decoder for Communication Systems”(以下、”ルビーII”)、そして、2003年3月27日にショクロラヒらに発行された米国特許公開2003/0058958号”Multi-Stage Code Generator and Decoder for Communication Systems”(以下、”ショクロラヒ”)に示されている。許可される範囲において、全ての目的のためこれらの全ての開示を本願明細書に引用する。
【0009】
連鎖反応符号器により作成される出力シンボルの特性の1つとして、受信機は十分な出力シンボルを受信するとすぐにオリジナルファイルまたはオリジナルストリームのブロックを回復することが可能であるということがある。具体的には、高確率を有するオリジナルのK個の入力シンボルを回復するために、受信機はおよそK+A個の出力シンボルを必要とする。ここで、比A/Kは”相対的受信オーバーヘッド”と呼ばれる。相対的受信オーバーヘッドは、入力シンボル数K、および、復号器の信頼性に依存する。たとえば、ある特定実施例において、K=60,000であり、少なくとも1−10−8の確率で入力ファイルまたはストリームのブロックを復号器が復号化可能な相対的受信オーバーヘッドが5%の場合、K=10,000では、相対的受信オーバーヘッドが15%の場合同様の確率で復号化可能となる。ある実施例においては、連鎖反応コードの相対的受信オーバーヘッドは(13*sqrt(K)+200)/Kとして計算することが出来、ここで、sqrt(K)は入力シンボル数Kの二乗根である。この実施例において、連鎖反応コードの相対的受信オーバーヘッドは、Kが小さい値であるほど大きくなる傾向がある。
【0010】
ルビーI、ルビーIIおよびショクロラヒは、本発明による特定の実施例において使用可能なシステム及び方法の教示を提供する。しかしながら、それらのシステム及び方法は、本発明および他の多くのバリエーション、変更態様を必要とせず、代替物が使用可能であることが理解できるであろう。
【0011】
また、マルチステージ連鎖反応(”MSCR”)符号を使用することも公知であり、例えばショクラヒに記載されデジタルファウンテン社により開発され”Raptor”として商品名の符号がある。マルチステージ連鎖反応符号は、たとえば、ソースファイルまたはソースストリームから入力シンボルを受信し、そこから中間シンボルを生成し、連鎖反応符号を用いた中間シンボルを符号化する符号器により用いられる。より詳しくは、送信される入力シンボルの順序集合から複数の冗長シンボルが生成される。そして、入力シンボルおよび冗長シンボルを含むシンボルの複合セットから複数の出力シンボルが生成される。ここで、可能な出力シンボルの数はシンボルの複合セットのシンボルの数に比較し非常に大きい。また、少なくとも一つの出力シンボルは、シンボルの複合セットの1つのシンボルより多く全てシンボル数より少ないシンボルから生成され、入力シンボルの順序集合が所定数Nの何れの出力シンボルからも所望の精度まで再生できるようなシンボルである。
【0012】
用途によっては、他のバリエーションの符号がより適切であり、他のもの選択されるかもしれない。
【発明の開示】
【発明が解決しようとする課題】
【0013】
転送元から転送先まで通信チャネルを介して転送されるデータを符号化する方法を提供する。
【課題を解決するための手段】
【0014】
本発明のある実施例によれば、転送元から転送先まで通信チャネルを介して転送されるデータを符号化する方法が提供される。その方法は、入力シンボルの順序集合を操作し、入力シンボルから複数の冗長シンボルを生成することを含む。また、その方法は、入力シンボルおよび冗長シンボルを含むシンボルの複合セットから複数の出力シンボルを生成することを含み、可能な出力シンボルの数はシンボルの複合セットのシンボルの数に比較し非常に大きく、少なくとも一つの出力シンボルはシンボルの複合セットの1つのシンボルより多く全てシンボル数より少ないシンボルから生成され、入力シンボルの順序集合が任意の所定数の出力シンボルからも所望の精度まで再生できるようなシンボルである。複数の冗長シンボルは、第1入力シンボルを使用して算出されるスタティックシンボルの第1セットは、第1入力シンボルと異なる第2入力シンボルを使用して算出されるスタティックシンボルの第2セットと弱い関連性を有するように、確定的過程において送信される入力シンボルの順序集合から生成される。
【0015】
本発明のさらに別の実施例によれば、通信チャネルを介して転送先から転送されるデータを受信するシステムは類似した技術を使用し提供される。そのシステムは、通信チャネルを通じて送信される出力シンボルを受信するための通信チャネルに接続された受信モジュールを含み、各々の出力シンボルは入力シンボルおよび冗長シンボルの複合セットの少なくとも1つのシンボルから生成され、少なくとも1つの出力シンボルは複合セットの1より多く全てより少ないシンボルから生成され、可能な出力シンボルの数は複合セットのシンボルの数に比較し非常に大きく、入力シンボルは順序集合からなる入力シンボルであり、冗長シンボルは入力シンボルから生成される。ここで、複数の冗長シンボルは、第1入力シンボルを使用して算出されるスタティックシンボルの第1セットは、第1入力シンボルと異なる第2入力シンボルを使用して算出されるスタティックシンボルの第2セットと弱い関連性を有するように、確定的過程において送信される入力シンボルの順序集合から生成される。
【0016】
本発明のさらに別の実施例によれば、搬送波により表現されるコンピュータデータ信号が提供される。
【発明の効果】
【0017】
多数の利点が、本発明により達成される。たとえば、ある実施例においては、チャネルを介して転送するデータの符号化に必要な計算能力が低減可能である。さらに他の実施例において、このデータの復号化に必要な計算能力が低減可能である。実施例により、これらの利点の1つ以上を達成できる。これらおよびその他の利点の更なる詳細が、本願明細書全体および特に下記記載により提供される。
【0018】
本願明細書において開示される本発明の性質および効果の更なる理解は、明細書および添付の図面の残りの部分を参照することで認識される。
【発明を実施するための最良の形態】
【0019】
(関連出願の相互参照)
本出願は、2004年5月7日に出願された米国特許出願番号第60/569,127号の”FILE DOWNLOAD AND STREAMING SYSTEM”に基づく優先権を主張する。それは、全ての目的のためにその開示全体を本願明細書に引用しこの文書に全部記載されるものとして組み込まれる。
【0020】
詳細な説明の後に以下の3つの付録を示す。付録Aは、システマチックインデックスJ(K)の値の例を含む。付録B.1は、テーブルV0の値の例を含む。そして、付録B.2は、テーブルV1の値の例を含む。
【0021】
(特定実施例の詳細な説明)
ここに記載される特定実施例において、”マルチステージ符号化”として表記される符号体系が記載されており、その実施例はショクロラヒにより提供される。
【0022】
ここに記載されるマルチステージ符号化は複数の段階によりデータを符号化する。常にではないが、一般的には、第1段階では予め指定される量の冗長性をデータに付加する。第2段階ではオリジナルデータおよび符号化の第1段階により計算される冗長シンボルから連鎖反応コード等を使用し出力シンボルを生成する。本発明の一特定実施例において、受信されたデータは、最初に連鎖反応復号プロセスを使用して復号化される。その処理により完全にオリジナルデータを回復することが出来ない場合、第2の復号ステップが適用される。
【0023】
マルチステージ符号化の実施例において、冗長シンボルは、符号化の第一段階において、入力ファイルまたはストリームのブロックから生成される。これらの実施例では、符号化の第二段階で、出力シンボルは、入力ファイルまたはストリームのブロックおよび冗長シンボルの組合せから生成される。これらの実施例において、出力シンボルは、必要に応じて生成されることができる。第二段階が連鎖反応符号化を含む実施例において、各々の出力シンボルは他の出力シンボルが生成される方法に関係なく生成されることができる。一旦生成されると、これらの出力シンボルはパケット内に配置され転送先に転送される。ここで、各々のパケットは1個以上の出力シンボルを含んでいる。非パケット化転送技術も利用可能であり同様に使うことができる。
【0024】
ここで使用される用語”ファイル”は、1個以上のソースを格納し1以上の転送先にユニットとして配信される任意のデータを示している。したがって、文書、画像、およびファイルサーバまたはコンピュータ記憶装置からのファイルは、すべて、転送される”ファイル”の例である。ファイルは、周知のサイズ(例えばハードディスクに保存される1メガバイトの画像)でもよいし、未知のサイズ(例えばストリーミングソースの出力から取得されるファイル)でもよい。いずれの場合においても、ファイルは一連の入力シンボルであり、各々の入力シンボルはファイル内の位置および値を有する。
【0025】
ここで使用される用語”ストリーム”は、1個以上のソースを格納もしくは生成された順番に各時点で特定のレートで配信される任意のデータを示している。ストリームは、固定レートまたは可変レートでありえる。したがって、MPEG映像ストリーム、AMR音声ストリーム、遠隔装置の制御に使用されるデータストリームは全て転送される”ストリーム”の例である。各時点でのストリームのレートは、既知(例えば4メガビット/秒)でもよいし、未知(例えば各時点のレートが前もって分からない可変レートストリーム)いずれの場合においても、ストリームは一連の入力シンボルであり、各々の入力シンボルはストリーム内の位置および値を有する。
【0026】
転送は、ファイルまたはストリームを配信するために1以上の送信機から1以上の受信機までチャネルを介してデータを送信する処理である。また、送信機を符号器と称することもある。1台の送信機が完全なチャネルにより任意数の受信機に接続している場合、受信データは入力ファイルまたはストリームの正確なコピーであり、全てのデータが正しく受信される。ここでは、現実のチャネルの多くの場合と同様、チャネルが完全でないと仮定する。多くのチャネルの欠点の中で、重要な2つの欠点は、データ消去およびデータ消去の特殊例とみなすことが可能なデータ不完全性である。データ消去は、チャネルが消失またはデータがドロップした場合に発生する。データ不完全性は、いくつかのデータが素通りするまで受信機がデータを受信し始めない場合、受信機が転送が終了する前にデータを受信するのを止めた場合、受信機が一部の送信データを受信することを選択する場合、および/または、受信機が断続的に止まり、再びデータを受信し始めた場合に発生する。データ不完全性の例としては、移動中の衛星送信機が入力ファイルまたはストリームを示すデータを送信している場合、受信機が範囲内に入る前に転送を始めるかもしれない。一旦受信機が範囲内に入ると衛星が動いて範囲外に出るまでデータを受信することが出来、一旦受信機が範囲に入るとデータを受信可能となり、それまで、受け側がどのポイント、他のものにより送信されている同じ入力ファイルかストリームについてデータを受信し始めるためにその衛星アンテナ(それは、どの時間の間にデータを受信していないか)をリダイレクトすることができるかそれが有する衛星は範囲へ移動した。この説明を読むことから明らかでなければならなくしながら、データ不完全性はデータ消去の特例である。これは、次のことの故である。あたかも受け側が全ての時範囲において、あるかのように、受け側はデータ不完全性(そして、受け側には、同じ問題がある)を処理できる、しかし、チャネルは受け側がデータを受信し始めた位置まで全てのデータを消失した。また、周知のように、通信システム設計で、検出可能な誤りは、単に検出可能な誤りを有する全てのデータブロックまたはシンボルをドロップすることによって、消去に等しいとみなされることができる。
【0027】
若干の通信システムにおいて、受け側は、多数の送信機によってまたは並列に接続を使用している1台の送信機により生成されるデータを受信する。たとえば、ダウンロードの速度を上げるために、受け側は、同時に同じファイルに関して送信データに複数の送信機につながるかもしれない。別の例としてマルチキャスト転送で、多数のマルチキャストデータストリームは、受け側が総計の伝送速度をそれらを送信機に接続しているチャネルの帯域幅と適合させるためにこれらのストリームの一つ以上につながることができるために送信されるかもしれない。全てのこの種の場合において、懸念は、全てのその送信データを確保することが受け側に独立用途の中であるということである。すなわち、多重ソースデータは、そうである冗長ストリームの伝送速度が異なるストリームのために非常に異なるときでも、そして、損失の任意のパターンがあるときに、一つの。
【0028】
一般に、通信チャネルは、送信機およびデータ転送のための受け側を接続するそれである。通信チャネルはリアルタイムチャネルでありえた。ここで、チャネルがデータを得ながら、チャネルは送信機から受け側までデータを移動する、または、通信チャネルは、送信機から受け側までいくつかまたはデータの全てをその通過に格納する格納チャネルであるかもしれない。後者の実施例は、ディスク記憶装置または他の記憶装置である。その実施例において、送信機、データを生成するプログラムまたはデバイスを、案出できる。そして、記憶装置にデータを送信する。受け側は、記憶装置からデータを読み込むプログラムまたはデバイスである。送信機が記憶装置(記憶装置自体)上へデータを得るために使用するメカニズムそして、受け側が集合的に記憶装置からデータを得るために使用するメカニズムは、チャネルを形成する。それらのメカニズムまたは記憶装置がデータを消失できるという可能性がある場合、それは通信チャネルのデータ消去とみなされるだろう。
【0029】
送信機および受け側がシンボルが消されることができる通信チャネルによって、隔てられるときに、入力ファイルまたはストリームの正確なコピーを送信しなくて、その代わりに、入力ファイルから生成されるデータまたはそれが消去の回復によって、アシストするストリーム(それは、入力ファイルまたはストリームの全部または一部を含むことができた)を伝送しないことが、好ましい。エンコーダとは、そのようなタスクを処理する回路、デバイス、モジュール、または符号セグメントである。1つの符号器の動作を見る方法は符号器が入力シンボルから出力シンボルを生成するということである。ここで、一連の入力シンボル値は入力ファイルまたはストリームのブロックを表す。ストリームおよび値の入力ファイルまたはブロックで、各々の入力シンボルは、このように位置を有する。復号器は、受け側により受信される出力シンボルから入力シンボルを回復する回路、デバイス、モジュールまたはコードセグメントである。マルチステージ符号化において、符号器および復号器は、各々異なる作業を実行しているサブモジュールに、更に分けられる。
【0030】
マルチステージコード体系の実施例において、符号器および復号器はサブモジュールに更に分けられることが可能である。そして、各々が異なる作業を実行する。例えば、実施例によっては、符号器は、本明細書において、スタティック符号器およびダイナミック符号器と称されることを含む。ここで使用しているように、「スタティック符号器」は入力シンボルのセットから多くの冗長シンボルを生成する符号器である。そこにおいて、冗長シンボルの数は符号化の前に決定される。スタティック符号化しているコードの実施例はリード−ソロモン符号、トルネード符号、ハミング符号、低密度パリティチェック(LDPC:Low Density Parity Check)符号、その他を含む。そして、用語スタティック復号器がスタティック符号器によって、符号化されたデータを復号化できる復号器に関連するために本願明細書において、使われる。
【0031】
ここで使用しているように、”ダイナミック符号器”は、入力シンボルのセットから出力シンボルを生成する、可能な出力シンボルの数が入力シンボルの数大きい大きさの程度である。そして、生成される出力シンボルの数が固定する必要はない符号器である。ダイナミック符号器の1つの実施例は、連鎖反応符号器(例えばLuby IおよびLuby IIに記載されている符号器)である。用語”ダイナミック復号器”が、ダイナミック符号器によって、符号化されたデータを復号化できる復号器に関連するために、本願明細書において、使われる。
【0032】
マルチステージ符号化の実施例は、いかなる特定の種類もの入力シンボルに、限られている必要はない。一般的に、入力シンボルのための値は若干の自然数M.のための2Mのシンボルのアルファベットから選ばれるにおいて、この種の場合、入力シンボルは入力ファイルまたはストリームからデータの一連のMビットにより表されることができる。たとえば、Mの値は、出力シンボルのアプリケーション、通信チャネルおよび/またはサイズを使う能力に基づいて、しばしば決定される。加えて、出力シンボルのサイズは、入力シンボルのアプリケーション、チャネルおよび/またはサイズに基づいてしばしば決定される。場合によっては、出力シンボル値および入力シンボル値が同一サイズ(すなわち、ビットの同数により表現されるか同じアルファベットから選択された)である場合、符号化処理は単純化されるかもしれない。この場合それから、出力シンボル値サイズが制限されるときに、入力シンボル値サイズは制限される。たとえば、それは、制限されたサイズのパケットの出力シンボルをすることを要求されることができる。出力シンボルに伴うキーについての若干のデータが受信機でキーを回復するために送信されることになっている場合、出力シンボルは、1つのパケットにおいて、キーについて出力シンボル値およびデータに対応するのに十分好ましくは小さいだろう。
【0033】
一例として、入力ファイルが倍数である、メガバイトファイル、入力ファイルは、各々の入力シンボルを符号化している数千、何百または数バイトだけを有する数千、数万または何十万もの入力シンボルに分解されるかもしれない。別の例としてパケットベースのインターネットチャネルのために、1024バイトのサイズのペイロードを有するパケットは、適当かもしれない(1バイトは、8ビットである)。この例では、各々のパケットが1出力シンボルおよび8バイトの補助情報を含む場合、8128bits((1024−8)*8)の出力シンボルサイズは適当だろう。このように、入力シンボルサイズは、M=(1024−8)*8つまり8128ビットに選ばれることができた。別の例として、若干の衛星システムはMPEGパケット規格を使用する。ここで、各々のパケットのペイロードは188バイトを含む。その実施例において、各々のパケットが1出力を含む場合、シンボルおよび4バイトの補助情報(1472bits((188−4)*8)の出力シンボルサイズ)は適当だろう。このように、入力シンボルサイズは、M=(188−4)*8または1472ビットに選ばれることができた。汎用の通信システムを使用しているマルチステージ符号化において、アプリケーション特有のパラメータ(例えば入力シンボルサイズ(すなわちM個の入力シンボルによって、符号化されるビットの数)は、アプリケーションによって、セットされる変数であるかもしれない。
【0034】
別の例として、可変サイズ転送元パケットを使用させられるストリームのために、各々の転送元パケットが最高でも総計のサイズを転送元パケットわずかに大きくする入力シンボルの整数でおおわれていることができるために、シンボルサイズはむしろ小さいために選ばれるかもしれない。
【0035】
各々の出力シンボルは、値を有する。好ましい一実施例(下で考慮する)において、各々の出力シンボルもそれとともにその”キー”と呼ばれている識別子を結びつける。望ましくは、各々の出力シンボルのキーは、受け側が1出力シンボルと他の出力シンボルを区別できるために、受け側で容易に測定されることができる。望ましくは、出力シンボルのキーは、他の全ての出力シンボルのキーとは別である。前の技術で述べられるキーイングのさまざまな形式が、ある。たとえば、Luby Iは、本本発明の実施例において、使用されることができるキーイングのさまざまな形式を描く。
【0036】
データ消去または受け側が必ずしも転送が開始するときに受信を開始しなくて、終えないところの予想および端がある所で、マルチステージ符号化は特に役立つ。後の状態は本明細書において、”データ不完全性”と呼ぶ。消去イベントとみなす事項において、Luby I.に記載されている連鎖反応符号化の利点で多くのマルチステージ符号、マルチステージ出力シンボルは情報付加的であるので、任意の適当な数のパケットは所望の精度に入力ファイルまたはストリームを回復するために用いることがありえる。マルチステージ符号化が使われるときに、これらの状況は通信プロセスに悪影響を与えない。−その理由は、次のことにある。マルチステージ符号化により生成される出力シンボルは情報付加的である。たとえば、100のパケットが突然のノイズを引き起こしているデータ消去のために消失する場合、パケットがありえる余分の百は消されたパケットの損失を交換するために爆発の後、上向いた。それが送信し始めるときに受信機が送信機に同調を行わなかったので何千ものパケットが消失する場合、受信機は、そうすることができたちょうど受信転送の他のいかなる期間からも何千ものそれらのパケット、または他のものから送信機。マルチステージ符号化については、受信機は特定のいずれもパケットの中でセットしたピックアップを強いられないので、それは1台の送信機から若干のパケットを受信することができて、送信機を他のものに切り替えることができて、若干のパケットを消失することができて、始めまたは既知の転送の端を見のがすことができて、まだストリームの入力ファイルまたはブロックを回復できる。受信機送信機間で協調のない転送を接続して、残す能力は、通信プロセスを単純化するのに役に立つ。
【0037】
いくつかの実施形態では、ファイルまたはストリームを使用しているマルチステージ符号化を送信することは入力シンボルをストリームの入力ファイルまたはブロックから生成するか、形成するかまたは抽出することを含むことができる。そして、冗長シンボルを計算する。そして、一つ以上の出力シンボル(各々の出力シンボルがそれぞれに他の全ての出力シンボルのそのキーに基づいて生成されるところ)に入力および冗長シンボルを符号化して、チャネルの上の一つ以上の受け側に出力シンボルを送信する。加えて、実施例によっては、入力ファイルのコピーまたはストリームを使用しているマルチステージ符号化のブロックを受信する(そして、回復すること)ことは、より多くのデータストリームのうちの1つから出力シンボルの若干のセットまたはサブセットを受信して、受信された出力シンボルの値およびキーから入力シンボルを復号化することを含むことができる。
【0038】
本願明細書において、記載されていながら、消去が符号化する適切なFECは、上記のあげられた問題点を克服するために用いることができて、用途をマルチメディアの同報およびマルチキャスティングシステムおよびサービスを含む多くのフィールドで見つける。この後に「マルチステージ連鎖反応コード」と称するFEC消去コードは、この種のシステムおよびサービスの電流および将来の必要条件の多数を満たす特性を有する。
【0039】
いかなるパケット損失状況のためにも、そして、いかなる関連したサイズものソースファイルまたはいかなる関連したレートものストリームの交付のために、マルチステージ連鎖反応コードの若干の基本特性は、以下の通りである。
(a)個々の受信機デバイス”RD”の受信オーバーヘッドは、最小化される、
(b)ソースファイルをいかなる数のRDに配信するために必要なトータル転送時間を、最小化できる
(c)転送スケジュールの適切な選択については、いかなる数のRDに対する配信されたストリームの品質は、入力シンボルの数と関連して送られる出力シンボルの数のために最大にされることができる。
RDは、携帯デバイスであるかもしれないか、車両に埋め込まれているかもしれないか、持ち歩けるかもしれない(すなわち、使用中のときに、移動可能であるが、一般的に動いていない)かまたは、場所に固定するかもしれない。
【0040】
復号化のために必要とされる作業メモリの量は低くて、上記の特性をまだ提供できる。そして、必要とされる計算の量は符号化する。そして、復号化する最小限である。この文書において、我々は、提供するシンプルな、そして、容易なマルチステージ連鎖反応コードの若干のバリエーションの説明をインプリメントする。
【0041】
マルチステージ連鎖反応コードは、ファウンテンコードである。すなわち、必要に応じてパケットを符号化することがありえるさらに同じだけはオンザフライを生成した。そして、各々がストリームのソースファイルまたはブロックを回復することに等しく役立つユニークな符号化しているシンボルを含んだ。多くの効果が、FECコードの他方式に対してファウンテンコードを使用することにある。1つの効果は、パケット損失状況およびRD有効性に関係なく、ファウンテンコードが各々のRDがストリームのソースファイルまたはブロックを回復するために受信することを必要とするパケットを符号化することの数を最小化するということである。これは、厳しいパケット損失状況の下でさえ真で、移動機RDが、たとえば、断続的につけられるだけである時であるまたは長いファイルダウンロードセッションにわたって利用できる。
【0042】
有利さが能力である他のものは、転送が進行中である間、どれくらいの符号化しているパケットにオンザフライを生成するべきかについて決定になされて、必要に応じて多くの符号化しているパケットとして正確に生成する。これは、たとえば応答がそれらがストリームのソースファイルかブロックを回復するのに十分な符号化しているパケットを受信したか否か、指示しているRDからある場合、役立つことがありえる。期待されてパケット損失状況が厳しくないときに、転送は、早く終了されることができる。パケット損失状況がより厳しい期待されるまたはRDは、期待されてしばしば利用できない、転送は、継ぎ目なく延長されることができる。
【0043】
他の効果は、逆多重化の能力である。逆多重化は、RDがストリームのソースファイルまたはブロックを回復するために独立送信機で生成されるパケットを符号化して受信されて組み合わさることが可能である時である。逆多重化の1つの実用は、異なる送信機からパケットを符号化することを受信することに関して、下に記載されている。
【0044】
将来のパケット損失、RD有効性およびアプリケーション状況は、予測するのが難しい、予測不可能な状況の下で適切に作用するために可能に、柔軟なとしてあるFECソリューションを選択することは重要である。マルチステージ連鎖反応コードは、FECコードの他方式によって、マッチしない柔軟度を提供する。
【0045】
本発明の態様は、次に図に関して記載されている。
【0046】
<システムの概要>
図1は、マルチステージ符号化を使用する通信システム100のブロック図である。通信システム100において、入力ファイル101または入力ストリーム105が、入力シンボル生成器110に対し提供される。入力シンボル生成器110は入力ファイルまたはストリームから1個以上の一連の入力シンボル(IS(0),IS(1),IS(2),...)を生成し、各々の入力シンボルは値および位置(図1の括弧内の整数として示す)を有する。上述したように、各々の入力シンボルが入力ファイルまたはストリームのMビットを符号化するため、入力シンボルの可能な値(すなわちアルファベット)は一般的に2M個のシンボルからなるアルファベットである。Mの値は通常使用する通信システム100により決定される、しかし、Mが使用する用途が多様でありえるため汎用システムでは入力シンボル生成器110のためのシンボルサイズ入力を含むかもしれない。入力シンボル生成器110の出力は、符号器115に提供される。
【0047】
スタティックキー生成器130は、スタティックキーS0,S1...のストリームを生成する。通常、生成されるスタティックキーの数は制限されており特定実施例の符号器115に依存する。スタティックキーの生成は、以降で更に詳細に説明する。ダイナミックキー生成器120は、符号器115により生成される各々の出力シンボルに対するダイナミックキーを生成する。同じ入力ファイルまたはストリームのブロックのダイナミックキーの大部分がユニークとなるように、各々のダイナミックキーは生成される。たとえば、利用可能なキー生成器の実施例がルビーIに記載されている。ダイナミックキー生成器120およびスタティックキー生成器130の出力は、符号器115に提供される。
【0048】
ダイナミックキー生成器120によって提供された各々のキーIから、符号器115は値B(I)の出力シンボルを生成する。そして、入力シンボルは入力シンボル生成器により提供される。符号器115の動作については以下で更に詳細に説明する。各々の出力シンボルの値は対応するキー、1個以上の入力シンボルの何らかの関数、そして、おそらく入力シンボルから計算される冗長シンボルに基づいて生成される。本明細書において、ある特定の出力シンボルのもとである入力シンボルおよび冗長シンボルの集合を、出力シンボルの”関連シンボル”または単にその”付随物(associates)”と呼ぶ。関数(”値関数”)および付随物の選択については、以降で更に詳細に記載されている処理に従って行われる。常にではないが、一般的にはMは入力シンボルおよび出力シンボルに対して同一である、すなわち、それら双方は同じビット数に符号化する。
【0049】
いくつかの実施形態では、符号器115は付随物を選択するために入力シンボルの数Kを使用する。入力がストリーミングファイルである場合のようにKが前もってわかっていない場合には、Kは単に推定値であってもよい。また、符号器115により生成される入力シンボルおよび任意の中間シンボルの配置割り当てに対し、値Kが符号器115により使用されるかもしれない。
【0050】
符号器115は送信モジュール140に出力シンボルを提供する。また、送信モジュール140にはダイナミックキー生成器120から各々の出力シンボルのキーが提供される。送信モジュール140は出力シンボルを送信する。そして、送信モジュール140は使用するキーイング方法に従い送信された出力シンボルのキーに関する何らかのデータをチャネル145を介して受信モジュール150に送信するかもしれない。チャネル145は消去チャネルであるとみなされるが、それは通信システム100が適切に動作するための必要条件ではない。送信モジュール140はチャネル145を介して出力シンボルおよび対応するキーに関する必要データを送信するのに適合しており、受信モジュール150はチャネル145を介してシンボルと対応するキーに関する何らかのデータを受信するのに適合していれば、モジュール140、145および150は、適切なハードウェア構成機器、ソフトウェア構成要素、物理メディアまたはそれのいかなる組合せによっても実現可能である。Kの値は、付随物を決定するために用られる場合、チャネル145を介して送信されるか、または、定刻より早い持間に符号器115および復号器155に対して予めセットしておいてもよい。
【0051】
前述したように、チャネル145はリアルタイムチャネル(例えば、インターネット、テレビ送信機からテレビ受信機への放送リンク経路、あるポイントから他のポイントへの電話接続)で有り得る他、チャネル145は格納チャネル(例えば、CD−ROM、ディスク装置、ウェブサイト等)でも有り得る。さらに、チャネル145はリアルタイムチャネルおよび格納チャネルの組合せでも有り得る。例えば、ある人がパソコンから電話回線を介してインターネットサービスプロバイダー(ISP)まで入力ファイルを送信する際に形成されるチャネルのように、入力ファイルはウェブサーバに格納され、インターネットを介して受け側に送信される。
【0052】
チャネル145が消去チャネルであると仮定されるので、システム100において、受信モジュール150から出力される出力シンボルと送信モジュール140に入力される出力シンボルとは1対1の対応があると仮定することは出来ない。実際、チャネル145がパケット網を含む場合、2個以上のパケットの相対的順序がチャネル145を通過中に保存されると仮定することさえ出来ないかもしれない。従って、出力シンボルのキーは上述の1以上のキーイング方法を利用して決定され、必ずしも受信モジュール150から出力シンボルが出力される順序で決定されるというわけではない。
【0053】
受信モジュール150は復号器155に出力シンボルを提供し、受信モジュール150が受信するこれらの出力シンボルのキーに関するデータはダイナミックキー再生器160に提供される。ダイナミックキー再生器160は、受信された出力シンボルのためのダイナミックキーを再生し、復号器155にダイナミックキーを提供する。スタティックキー生成器163は、スタティックキーS0,S1...を再生し、復号器155に提供する。スタティックキー生成器は、符号化および復号化プロセスにおいて双方で使用する乱数発生器135にアクセスする。同一の挙動となるようにするため、この種のデバイスにより乱数が生成される場合同一の物理装置へのアクセスであってもよいし、同一の乱数生成アルゴリズムへのアクセスであってもよい。復号器155は、ダイナミックキー再生器160およびスタティックキー生成器163により提供される出力シンボルに対応するキーを使用し、入力シンボル(IS(0),IS(1),IS(2),...)を回復する。復号器155は、入力ファイル101または入力ストリーム105のコピー170を生成する入力ファイル再構築器165に回復した入力シンボルを提供する。
【0054】
<符号器>
図2は、図1に示される符号器115の一特定実施例のブロック図である。符号器115は、スタティック符号器210、ダイナミック符号器220、および、冗長計算機230を備えている。スタティック符号器210は、以下の入力を受信する。
【0055】
a)入力シンボル生成器110により提供され入力シンボルバッファ205に格納されたオリジナルの入力シンボルIS(0),IS(1),IS(2),...,IS(K−1)
b)オリジナルの入力シンボルの数K
c)スタティックキー生成器130により提供されるスタティックキーS0,S1,...
d)冗長シンボルの数R
スタティック符号器205は、これらの入力を受信するとすぐに、後述するようにR個の冗長シンボルRE(0),RE(1),...,RE(R−1)を計算する。常にではないが一般的に冗長シンボルは入力シンボルと同じサイズである。一特定実施例において、スタティック符号器210により生成される冗長シンボルは、入力シンボルバッファ205に格納される。入力シンボルバッファ205は論理的なものでもよい。すなわち、ファイルまたはストリームのブロックは1つの場所に物理的に格納してもよいし、入力シンボルのシンボルバッファ205内の位置は、ただ単にオリジナルのファイルまたはストリームのブロック内のシンボルの位置の名称変更でもよい。
【0056】
ダイナミック符号器は、入力シンボルおよび冗長シンボルを受信し下記に詳述されているように出力シンボルを生成する。冗長シンボルが入力シンボルバッファ205に格納される一実施例においては、ダイナミック符号器220は入力シンボルバッファ205から入力シンボルおよび冗長シンボルを受信する。
【0057】
冗長計算機230は、入力シンボルの数Kから冗長シンボルの数Rを計算する。この計算は下記に詳述されている。
【0058】
<スタティック符号器の概要>
スタティック符号器210の一般動作は図3および図4に示される。図3は、スタティック符号化の方法一実施例の簡略フローチャートを例示している。ステップ305において、変数j(どれだけ冗長シンボルが生成されたかについての情報を保持する)はゼロにセットされる。そして、ステップ310では、第1の冗長シンボルRE(0)は少なくともいくつかの入力シンボルIS(0),...,IS(K−1)の関数F0として計算される。それから、ステップ315で、変数jはインクリメントされる。次に、ステップ320で、冗長シンボルの全てが生成されたか(すなわち、jがR−1より大きいか?)どうかが検査される。もしYesの場合はフローは終了する。そうでなければ、フローは、ステップ325へ進む。ステップ325において、RE(j)は入力シンボルIS(0),...,IS(K−1)および以前に生成された冗長シンボルRE(0),...,RE(j−1)の関数Fjとして計算される。ここで、Fjは入力シンボルの何れかまたは冗長シンボルの何れかに依存する関数である必要はない。ステップ315、320および325はR個の冗長シンボルが計算されるまで繰り返される。
【0059】
再度図1および図2を参照すると、実施例によっては、スタティック符号器210はスタティックキー生成器130から1個以上のスタティックキーS0,S1...を受信する。これらの実施例では、スタティック符号器210は、いくつかまたは全部の関数F0,F1,...Fj−1を決定するためにスタティックキーを使用する。たとえば、スタティックキーS0は関数F0を決定するために利用可能であり、スタティックキーS1は関数F1を決定するために利用可能である。もしくは、1個以上のスタティックキーS0,S1,...を関数F0を決定するために利用可能であり、1個以上のスタティックキーS0,S1,...を関数F1を決定するために利用可能である。他の実施態様では、スタティックキーは必要でなく、スタティックキー生成器130は必要でない。
【0060】
次に図2および図3を参照すると、実施例によっては、スタティック符号器210により生成される冗長シンボルは、入力シンボルバッファ205に格納されてもよい。図4は、スタティック符号器210の一実施例の動作の簡略図である。特に、スタティック符号器210は、入力シンボルバッファ205から受信した入力シンボルIS(0),...,IS(K−1),RE(0),...,RE(j−1)の関数Fjとして、冗長シンボルRE(j)を生成する。そして、入力シンボルバッファ205の中に戻し格納する。関数F0,F1,...,FR−1の正確な形式は、特定の用途に依存する。常ではないが一般的には、関数F0,F1,...,FR−1は、関連するいくつかあるいは全ての引数の排他的論理和を含んでいる。上述の通り、これらの関数は実際に図1のスタティックキー生成器130により生成されるスタティックキーを使用するかもしれないし使用しないかもしれない。たとえば、後述する一特定実施例では、最初のいくつかの関数はハミング符号を実装し、スタティックキーS0,S1,...を全く使用しない。また、残りの関数は低密度パリティチェック符号を実装し、スタティックキーを明示的に利用する。
【0061】
<マルチステージ符号器の概要>
再度図2を参照すると、ダイナミック符号器220は、入力シンボルIS(0),...,IS(K−1)および冗長シンボルRE(0),...,RE(R−1)および各々の出力シンボルのキーIを受信する。この集合はオリジナルの入力シンボルおよび冗長シンボルを含んでおり、今後”ダイナミック入力シンボル”の集合と呼ぶ。図5はダイナミック符号器の一実施例の簡略ブロック図であり、ウェイトセレクタ510、アソシエータ515、値関数セレクタ520および計算機525を含む。図5に示すように、K+R個のダイナミック入力シンボルはダイナミックシンボルバッファ505に格納される。実質的に、ダイナミック符号器500は図6に例示される動作を実行する。すなわち、選択された入力シンボルの何らかの値関数として出力シンボル値B(I)を生成する。
【0062】
図7は、本発明によるスタティック符号器の一特定実施例の簡略ブロック図である。スタティック符号器600は、パラメータ計算機605、ハミング符号器610および低密度パリティチェック(LDPC)符号器620を備えている。ハミング符号器610は、入力シンボルバッファ625からの入力シンボルIS(0),...,IS(K−1)、入力シンボルの数K、および、パラメータDを受信するように接続される。そして、ハミング符号器610は、ハミング符号に従ってD+1個の冗長シンボルHA(0),HA(1),...,HA(D)を生成する。
【0063】
図8は、図7に示されるスタティック符号器を使用する本発明の一実施例の動作を例示する。
【0064】
図9は、パラメータ計算機(例えば図7のパラメータ計算機605)の一実施例の簡略フローチャートであり、上述のパラメータDおよびEを計算する。最初に、ステップ705で、パラメータDは1に初期化される。そして、ステップ710で、2D−D−1がK未満かどうかが判定される。NOの場合フローはステップ730へ進む。YESの場合フローはステップ720へ進み、パラメータDはインクリメントされる。それから、フローはステップ710へ進む。Dが決定されると、ステップ730で、R−D−1としてパラメータEが算出される。
【0065】
図10は本発明の一実施例に従うこのような符号器の簡略フローチャートであり以下に説明する。最初に、ステップ805で、変数iはゼロに初期化される。変数iは、すでに生成される冗長シンボルの数の情報を得続ける。ステップ810において、数tは、K/2以上の最も少ない奇数の整数として算出される。ステップ815において、値P1,P2,...,Ptは、K、tおよびスタティックキーSに基づいて生成される。値P1,P2,...,Ptは、冗長シンボルを生成するために用いる入力シンボルの位置を指示する。ある特定の実施例では、図5のアソシエータ515のようなアソシエータは、PI,P2,...,Ptを生成するために用いる。特に、W(I)個の入力として値tは提供され、K+R個の入力として値Kは提供される。そして、スタティックキーSiはキーIの入力として提供される。tの多くの異なる値が類似した符号化効果を得る点に留意する必要がある。このように、この特定の選択は1つの例にすぎない。ステップ820において、RE(i)の値は、値IS(PI),IS(P2),...,IS(Pt)のXORとして計算される。ステップ825において、変数iは次の冗長シンボルの計算を準備するために1だけインクリメントされる。そして、ステップ830で、全ての冗長シンボルが計算されたかどうかは判定される。そうでない場合には、フローはステップ815に戻る。
【0066】
図11は、本発明による復号器の簡略ブロック図を例示している図である。復号器900は、たとえば、図1の復号器155を実装するために用いられる。
【0067】
復号器900は、ダイナミック復号器905とスタティック復号器910を備えている。ダイナミック復号器905により回復される入力シンボルおよび冗長シンボルは、回復バッファ915に格納される。ダイナミック復号化終了後、スタティック復号器910は、ダイナミック復号器905により回復されない入力シンボルがあれば回復を試みる。特に、スタティック復号器910は回復バッファ915からの入力シンボルと冗長シンボルを受信する。
【0068】
図12は、本発明による復号化のための方法の簡略フローチャートを例示している図である。ステップ1005において、Q個の出力シンボルは、復号器により受信される。Qの値は、入力シンボルの数および使用するある特定のダイナミック符号器に依存する。Qの値は、また、復号器が入力シンボルを回復できる所望の精度に依存する。たとえば、復号器が高確率を有する入力シンボルの全てを回復できることが要求される場合、Qは入力シンボルの数より大きな数として選択される。特に、用途によっては、入力シンボルの数が大きいときに、Qは3%未満程度オリジナル入力シンボルの数より大きい。ほかの応用において、入力シンボルの数が少ないときに、Qは少なくとも10%程度入力シンボルの数より大きい。具体的には、Qは入力シンボルの数Kに数Aを加えた値として選ばれることができる。ここで、Aは復号器が高確率を有する入力シンボルの全てを再生させることができることを確保するために選ばれる。数Aの決定は、下で更に詳細に記載されている。復号器は入力シンボル(時々または常に)の全てを復号化することができないことを許容する場合、QはK+A未満でありえるかKに等しくありえるかさらにK未満でありえる。明確に、全体のコード体系の1つの目的はしばしば可能な限り数Qを減少させることである、その一方で、所望の精度に関して復号プロセスの成功に関する良好な見込みに基づく保証を維持する。
【0069】
ステップ1010において、ダイナミック復号器905は受信したQ個出力シンボルから入力シンボルおよび冗長シンボルを再生する。ステップ1005および1010が実質的に並行して実行されることができることは、よく理解されている。たとえば、ダイナミック復号器905は、復号器がQ個の出力シンボルを受信する前に入力シンボルおよび冗長シンボルを再生させ始めることができる。 ダイナミック復号器905がQ個の出力シンボルを処理したあと、入力シンボルが所望の精度に回復されたかどうかは判定される。所望の精度は、たとえば、全ての入力シンボルまたは全てより少ないいくつか、パーセンテージ、その他である。YESの場合、フローは終わる。NOの場合は、フローはステップ1020へ進む。ステップ1020において、スタティック復号器910は、ダイナミック復号器905が回復することができなかった入力シンボルの回復を試みる。スタティック符号器910がダイナミック復号器905により回復された入力シンボルおよび冗長シンボルを処理した後フローが終了する。
【0070】
図13は、本発明による復号化のための方法の他の実施例を示している簡略フローチャートである。この実施例は、図11に関して記載されたものと類似していて、共通のステップ1005、1010、1015および1025を含む。しかし、ステップ1025の後、フローはステップ1030へ進む。そこにおいて、入力シンボルが所望の精度に回復されたかどうかは判定される。YESの場合、フローは終了する。NOの場合、フローはステップ1035へ進む。ステップ1035において、一つ以上の付加的な出力シンボルが受信される。それから、フローはステップ1010へ進行する。その結果、ダイナミック復号器905および/またはスタティック復号器910は残留する非回復の入力シンボルを回復することを試みることができる。
【0071】
図14は、本発明による復号化のための方法のさらにもう一つの実施例を示している簡略フローチャートである。ステップ1055において、出力シンボルは復号器により受信される。そして、ステップ1060で、ダイナミック復号器905は受信された出力シンボルから入力シンボルおよび冗長シンボルを再生させる。それから、ステップ1065で、ダイナミック復号化が終了すべきかどうかが判定される。この判定は、処理した出力シンボルの数、回復した入力シンボルの数、付加的な入力シンボルが回復されている現在の速度、出力シンボルの処理に費やした時間は、その他の一つ以上に基づいて行われる。
【0072】
ステップ1065において、ダイナミック復号化を終了しないと決定される場合、フローはステップ1055へ進行する。しかし、ステップ1065において、ダイナミック復号化を終了すると決定される場合、フローはステップ1070へ進む。ステップ1070において、入力シンボルが所望の精度に回復されたかどうかが判定される。YESである場合、フローは終了する。NOの場合は、フローはステップ1075へ進む。ステップ1075において、スタティック復号器910は、ダイナミック復号器905が回復することができなかった入力シンボルの回復を試みる。スタティック符号器910が、ダイナミック符号器905によって回復された入力シンボルおよび冗長シンボルを処理した後、フローは終了する。
【0073】
図15は、本発明によるダイナミック復号器の一実施例を示す。ダイナミック復号器1100は、図5に示されるダイナミック符号器500と類似した構成要素を含む。復号器1100は、Luby IおよびLuby IIに記載されている連鎖反応復号器の実施例と類似している。ダイナミック復号器1100は、ウェイトセレクタ510と、アソシエータ515と、値関数セレクタ520と、出力シンボルバッファ1105と、短縮器1115と、回復器1120と、回復バッファ1125とを備える。
【0074】
図16は、スタティック復号器の一実施例の簡略ブロック図を示している。データが図7に関して記載されているスタティック符号器などによって、符号化されるときに、この実施例を用いることができる。スタティック復号器1200は、LDPC復号器1205とハミング復号器1210を備えている。LDPC復号器1205は回復バッファ1215から入力シンボルおよび冗長シンボルを受信する。そして、ダイナミック復号器の復号ステップの後、回復バッファ1215の未回復のシンボルの回復を試みる。いくつかの実施形態では、回復バッファ1215は、回復バッファ1125(図15)である。
【0075】
LDPC復号器およびハミング復号器の多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。1つの特定実施例において、ハミング復号器は、ガウス消去アルゴリズムを使用して行う。ガウス消去アルゴリズムの多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。
【0076】
<バリエーション>
上述のマルチステージ連鎖反応コードはシステマティックコードではない。すなわち、ソースブロックのオリジナルソースシンボルの全てが必ずしも送信される符号化シンボルであるというわけではない。しかしながら、システマチックFECコードは、ファイルダウンロードシステムまたはサービスに役立ち、ストリーミングシステムまたはサービスにとって非常に重要である。下記の実施に示すように、変更を加えられたコードは、システマチックで、まだファウンテンコードおよび他の記載されている特性を維持するよう実行されることができる。
【0077】
それがマルチステージ符号を使用した補足的なサービスのバラエティが設計者に容易である一つの理由は、それが送信機の中の関連性の無いソースファイルまたはストリームを復元するために多数の送信機から符号化シンボルを受信して組み合わせることができるということである。唯一の必要条件は、送信機がそれらがコードのパケットを符号化する際に送信する符号化シンボルを生成するためのキーと異なるセットを使用するということである。これを達成する方法は、この種の各々の送信機によって、異なる範囲のキー空間を使用するか、または、各々の送信機でランダムにキーを生成することを含む。
【0078】
例えば、この能力の用途の中で、ファイルダウンロードサービスに対する補足的なサービスがマルチステージ連鎖反応符号を許容するならば、ファイルダウンロードセッションからソースファイルを復元するのに十分な符号化しているパケットを受信せず、送信機から付加的な符号化コードが送信されるよう要求する(例えば、HTTPセッションを経て)。送信機はソースファイルから符号化シンボルを生成し送信し(例えばHTTPを使用して)、ソースファイルを回復するため全てのこれらの符号化シンボルはファイルダウンロードセッションから受信されるそれと混合されうる。このアプローチを使用することによって、異なる送信機同士が送信機間の調整を必要とせずインクリメント式ソースファイル配信サービスを提供でき、その各々個々の受信機は各々のソースファイルを回復するための符号化パケットを最低限の数だけ受信すればよい。
【0079】
<マルチステージコードのさまざまなステージの実現例>
<FEC方式定義>
これらの技術を使用しているパケットは、ヘッダ情報(例えばソースブロック番号(SBN)(パケットの範囲内の符号化シンボルが関係するソースブロックのための16ビット整数識別子)および符号化シンボルID(ESI)(パケットの範囲内の符号化シンボルのための16ビット整数識別子)を含んでいる4オクテットのFECペイロードID)により表されるかもしれない。ソースブロック番号および符号化シンボルIDの1つの適切な解釈は、下記のセクションBにおいて定義される。FECオブジェクト転送情報は、FEC符号化ID、転送長(F)およびパラメータT(下において、定められるZ、NおよびA)を含みうる。パラメータTおよびZは16ビット符号なし整数である、NおよびAは8ビット符号なし整数である。
【0080】
MBMS前方誤り訂正のFEC符号化方式は、下記のセクションにおいて定義される。それは2つの異なるFECペイロードIDフォーマット(1つはFEC転送元パケットのため、もう1つはFEC修復パケットのため)を定義する。しかし、非システマチック符号のバリエーションもまた可能である。
【0081】
転送元FECペイロードIDは、ソースブロック番号(SBN)(パケットの範囲内の符号化シンボルが関係するソースブロックのための16ビット整数識別子)および符号化シンボルID(ESI)(パケットの範囲内の符号化シンボルのための16ビット整数識別子)を含むかもしれない。その一方で、修復FECペイロードIDは、ソースブロック番号(SBN)(パケットの範囲内の修復シンボルが関係するソースブロックのための16ビット整数識別子)、符号化シンボルID(ESI)(パケットの範囲内の修復シンボルのための16ビット整数識別子)およびソースブロック長(SBL)(16ビット:ソースブロック内のソースシンボルの数を表す)を含みうる。ソースブロック番号、符号化シンボルIDおよびソースブロック長の解釈は、以下定義される。
【0082】
FECオブジェクト転送情報は、FEC符号化ID、最大ソースブロック長(シンボル単位)およびシンボルサイズ(バイト単位)を含みうる。シンボルサイズおよび最大ソースブロック長は、シンボルサイズ(T)(16ビット:符号化シンボルのサイズを表す(バイト単位)および)最大ソースブロック長(16ビット:ソースブロックの最大長を表す(シンボル単位))の4オクテット部を含み得る。
【0083】
下記のセクションは、システマチックMSCR前方誤り訂正符号およびMBMSおよび他の用途へのその適用を指定する。MSCRはファウンテンコードである。すなわち、符号器はブロックのソースシンボルからオンザフライで必要なだけ多く数ののソースシンボルを生成することが出来る。復号器は、ソースシンボルの数よりわずかに多いいかなる符号化シンボルのセットからもソースブロックを回復可能である。この文書に記載されている符号はシステマティック符号であり、修復シンボルと同じ数だけオリジナルソースシンボルは受信機に送信機から変形されずに送信される。
【0084】
<B.1 定義、記号および略号>
<B.1.1 定義>
本明細書において以下の用語および定義を適用する。
【0085】
ソースブロック:MSCR符号化の目的で一緒に考慮されるK個のソースシンボルのブロック。
【0086】
ソースシンボル:符号化プロセスの間使用されるデータの最小単位。ソースブロック内の全てのソースシンボルは同一のサイズである。
【0087】
符号化シンボル:データパケットに含まれるシンボル。符号化シンボルは、ソースシンボルおよび修復シンボルを含む。ソースブロックから生成される修復シンボルは、ソースブロックのソースシンボルと同様に同一のサイズである。
【0088】
システマティックコード:ソースブロックのため送信される符号化シンボルの一部としてソースシンボルが含まれるコード。
【0089】
修復シンボル:ソースブロックのため送信されるソースシンボルでない符号化シンボル。修復シンボルはソースシンボルに基づいて生成される。
【0090】
中間シンボル:逆の符号化プロセスを使用してソースシンボルから生成されるシンボル。修復シンボルは中間シンボルから直接生成される。符号化シンボルは中間シンボルを含まない。すなわち、中間シンボルはデータパケットに含まれない。
【0091】
シンボル:データの単位。バイトで表現されるサイズはシンボルサイズとして既知である。
【0092】
符号化シンボルグループ:一緒に送られる符号化シンボルグループ。すなわち、同一パケット内においてソースシンボルに対する関係が単一の符号化シンボルIDに由来するもの。
【0093】
符号化シンボルID:符号化シンボルグループのシンボルとソースシンボルの関係を定義する情報。
【0094】
符号化パケット:符号化シンボルを含むデータパケット
サブブロック:ソースブロックはサブブロックに分解され、それぞれは作業メモリ内において復号化されるために十分に小さい。K個のソースシンボルを含むソースブロックに対して、各々のサブブロックはK個のサブシンボルを含み、ソースブロックの各シンボルは各サブブロックの1個のサブシンボルから構成される。
【0095】
サブシンボル:シンボルの一部。各ソースシンボルは、ソースブロック内のサブブロックである多くのサブシンボルから構成される。
【0096】
ソースパケット:ソースシンボルを含むデータパケット。
【0097】
修復パケット:修復シンボルを含むデータパケット。
【0098】
<B.1.2 記号>
i、j、x、h、a、b、d、v、m:自然数を表す
ceil(x):x以上である最小の自然数を表す
choose(i,j):繰り返しのないi個のオブジェクトの中からj個のオブジェクトを選択する方法の数を表す
floor(x):x以下である最大の自然数を表す
i%j:iモジュロjを表す
X^Y:等しい長さのビット列XおよびYに対し、XとYとのビット毎の排他論理和を表す
A:シンボル配列パラメータを表し、シンボルおよびサブシンボルのサイズはAの倍数に制限される
AT:Aの転置行列を表す
A−1:Aの逆行列を表す
K:1個のソースブロック内にあるシンボルの数を表す
KMAX:1つのソースブロック内にあるソースシンボルの最大数を表し、8192に設定される
L:1つのソースブロックに対する予め符号化されるシンボルの数を表す
S:1つのソースブロックに対するLDPCシンボルの数を表す
H:1つのソースブロックに対するハーフシンボルの数を表す
C:中間シンボル(C[0],C[1],C[2],...,C[L−1])の配列を表す
C’:ソースシンボル(C’[0],C’[1],C’[2],...,C’[K−1])の配列を表す
X:負でない整数値を表す
V0、V1:4バイト整数の2つの配列、V0[0],V0[1],...,V0[255]およびV1[0],V1[1],...,V1[255]を表す
Rand[X、i、m]:擬似乱数発生器である
Deg[v]:度数発生器である
LTEnc[K、C、(d、a、b)]:LT符号化シンボル生成器である
Trip[K、X]:トリプル生成関数である
G:符号化シンボル群内のシンボルの数である
N:ソースブロック内のサブブロックの数である
T:シンボルサイズ(バイト)であり、ソースブロックがサブブロックに区切られているとき、T=T’・Nである
T’:サブシンボルサイズ(バイト)であり、ソースブロックがサブブロックに区切られていないときT’は関連しない
F:ファイルダウンロードのときのファイルサイズ(バイト)である
I:サブブロックサイズ(バイト)である
P:ファイルダウンロードの場合、各パケットのペイロードサイズ(バイト)であり、ファイルダウンロード転送パラメータの推奨導出に使用される。ストリーミングの場合、各修復パケットのペイロードサイズ(バイト)であり、ストリーミング転送パラメータの推奨導出に使用される
Q:Q=65521、すなわち、Qは216未満の最大の素数である
Z:ファイルダウンロードのときのソースブロックの数である
J(K):Kに関連するシステマチックインデックスである
G:任意の生成行列を表す
IS:SxSの恒等行列を表す
0SxH:SxHの零行列を表す
<B.1.3 略号>
本明細書において以下の略号を用いる。
【0099】
ESI(Encoding Symbol ID):符号化シンボルID
LDPC(Low Density Parity Check):低密度パリティチェック
LT(Luby Transform):ルビー変換
SBN(Source Block Number):ソースブロック番号
SBL(Source Block Length):ソースブロック長(シンボル単位)
<B.2 概要>
これら各々のアプリケーションに特定されるMSCR前方誤り訂正符号は、MBMSファイル配信およびMBMSストリーミングアプリケーションの双方に適用可能である。MSCR符号の態様は、本明細書のセクションB.3およびB.4で述べる。
【0100】
システマチックMSCR符号の構成要素は、セクションB.5に記載されている基本的な符号器である。第1に、中間シンボルについての知識がソースシンボルを復元するのに十分であるように、どのようにオリジナルソースシンボルから一組の中間シンボルの値を導き出すかが記述される。第2に、符号器は、各々多数の中間シンボルの排他的論理和である修復シンボルを作成する。符号化シンボルは、ソースおよび修復シンボルの組合せである。中間シンボル従ってまたソースシンボルはいかなる十分に大きい符号化シンボル群からも回復可能な方法で修復シンボルは生成される。
【0101】
この文書は、システマチックMSCRコード符号器を定義する。多くの考えられる復号化アルゴリズムが利用可能である。効率的な復号化アルゴリズムは、セクションB.6において提供される。
【0102】
中間のおよび修復シンボルの組立の一部分は、セクションB.5に記載されている擬似乱数発生器に基づく。この生成器は、送信機および受信機の双方で利用できる512の乱数の固定セットに基づく。数の実施例のセットは、付録B.1において提供される。
【0103】
最後に、ソースシンボルからの中間シンボルの組立は、”システマチックインデックス”により支配される。システマチックインデックスの値の実施例セットは、4個のソースシンボルからKMAX=8192個のソースシンボルまでのソースブロックサイズのためものが付録Aに示される。
【0104】
<B.3 ファイルダウンロード>
<B.3.1 ソースブロック構築>
<B.3.1.1 全般>
MSCR符号器をソースファイルに適用するために、ファイルはZ(≧1)個のブロック(ソースブロックとして知られる)としてに分解されうる。MSCR符号器は、それぞれに各々のソースブロックに適用される。各々のソースブロックは一意な整数ソースブロック番号(SBN)であり、第1のソースブロックのSBNは0、第2は1などである。各々のソースブロックは各々のサイズがTバイトのソースシンボルの数(K)に分割される。各々のソースシンボルは一意の整数符号化シンボル識別子(ESI)であり、ソースブロックの第1のソースシンボルのESIは0、第2は1などである。
【0105】
K個のソースシンボルを有する各々のソースブロックはN(≧1)個のサブブロックに分けられる。それは作業メモリにおいて復号化されるのに十分小さい。各々のサブブロックは、サイズT’のK個のサブシンボルに区分される。
【0106】
ファイルの各々のソースブロックの値に対してKの値が必ずしも同一であるというわけではない点、および、ソースブロックの各々のサブブロックに対してT’が必ずしもの同一であるというわけではない点に注意する。しかしながら、ファイルの全てのソースブロックに対してシンボルサイズTは同一であり、ソースブロックのあらゆるサブブロックに対してシンボル数Kは同一である。ファイルの、ソースブロックおよびサブブロックへの正確な分割は、後述のB.3.1.2に記載されている。
【0107】
図17は二次元行列に配置されたソースブロックの例を示す。ここで、各々のエントリはT’バイトのサブシンボルであり、各々の列はサブブロックであり、各々の行はソースシンボルである。この例では、T’の値は、あらゆるサブブロックに対して同一である。各々のサブシンボルのエントリに示される数は、ソースブロック中でのオリジナルの順番を示している。たとえば、Kの番号をつけられたサブシンボルは、ソースブロックのT’・KからT’・(K+1)−1個までのバイトを含む。そして、ソースシンボルiは、各々のサブブロックからの第iのサブシンボルの連結であり、i、K+i、2・K+i、...、(N−1)・K+iの番号をつけられたソースブロックのサブシンボルに対応する。
【0108】
<B.3.1.2 ソースブロックとサブブロック分割>
ソースブロックおよびサブブロックの構築は、F、A、T、Z、Nの5個のパラメータおよび関数Partition[]に基づいて決定される。5個のパラメータは次のように定義される。
【0109】
F:ファイルサイズ(バイト)である
A:シンボル配列パラメータ(バイト)である
T:シンボルサイズ(バイト)であり、必ずAの倍数となる
Z:ソースブロックの数である
N:各ソースブロック内のサブブロックの数である
これらのパラメータは、ceil(ceil(F/T)/Z)=<KMAXとなるようにセットされる。これらのパラメータ導出の推奨値がセクションB.3.4において提供される。
【0110】
関数Partition[]は一対の整数(I、J)を入力として4整数(IL、IS、JL、JS)を導出する。具体的には、Partition[I、J]の値は、4整数のシーケンス(IL、IS、JL、JS)であり、IL、=ceil(I/J)、IS=Floor(I/J)、JL=I−IS・J、JS=J−JLである。Partition[]は、サイズIのブロックをほぼ等しいJのブロックに分割するパラメータを導出する。具体的には、長さILのJL個のブロックと長さISのJS個のブロックである。
【0111】
ソースファイルは、以下の通りにソースブロックおよびサブブロックに仕切られる。
【0112】
Kt=ceil(F/T)のとき
(KL、KS、ZL、ZS)=Partition[Kt,Z]
(TL、TS、NL、NS)=Partition[T/A,N]
それから、ファイルは、Z=ZL+ZS個の隣接するソースブロックに仕切られ、最初のZL個のソースブロックは各々KL・Tバイトであり、残りのZS個のソースブロックは各々KS・Tバイトである。
【0113】
Kt・T>Fのとき、符号化に用いられ、最後のシンボルは最後のKt・T−Fの部分をパディングされる。
【0114】
次に、各々のソースブロックはN=NL+NS個の隣接するサブブロックに仕切られ、最初のNL個のサブブロックは各々TL・AのサイズのK個の隣接するサブシンボルを含み、残りのNS個のサブブロックは各々TS・AのサイズのK個の隣接するサブシンボルを含む。シンボル配列パラメータAは、サブシンボルが常にAバイトの倍数であることを確保する。
【0115】
最後に、ソースブロックの第m番目のシンボルは、各々N個のサブブロックから第m番目のサブシンボルの連結を含む。
【0116】
<B.3.2 符号化パケット構築>
<B.3.2.1 全般>
各々の符号化パケットは、以下の情報を含む。
【0117】
ソースブロック番号(SBN)
符号化シンボルID(ESI)
符号化シンボル
各々のソースブロックは、他と独立してそれぞれに符号化される。ソースブロックはゼロから連続的に番号をつけられる。
【0118】
0からK−1の符号化シンボルID値は、ソースシンボルを識別する。Kからの符号化シンボルは前方へ修復シンボルを識別する。
【0119】
<B.3.2.2 符号化パケット構築>
各々の符号化パケットは、好ましくは、完全なソースシンボル(ソースパケット)あるいは完全な修復シンボル(修復パケット)のいずれかを含む。パケットは、同じソースブロックから任意数のシンボルを含むことができる。オブジェクトを符号化しているFECにパケットの最後のシンボルがパディングバイトを含む場合、これらのバイトはパケットに含まなくてもよい。さもないと、全シンボルだけは含まれる。
【0120】
各々のソースパケットにより転送される符号化シンボルID、Xは、そのパケットにおいて保持される最初のソースシンボルの符号化シンボルIDである。パケットの次のソースシンボルは順序付けられた符号化シンボルID、X+1からX+G−1を有し、ここで、Gはパケット内のシンボルの数である。
【0121】
同様に、修復パケットに格納された符号化シンボルID、Xは、修復パケットの最初の修復シンボルの符号化シンボルIDであり、パケットの次の修復シンボルは順序付けられた符号化シンボルID、X+1からX+G−1を有し、ここで、Gはパケット内のシンボルの数である。
【0122】
ここで、受信機が修復パケットの合計数を知ることは必要でない点に注意する。修復シンボルのG個の修復シンボルトリプル(d[0],a[0],b[0]),...,(d[G−1],a[G−1],b[G−1])は、ESI Xを有する修復パケット内に配置され、以降のB.5.3.4において定義されるトリプル生成器を使用して計算される。
【0123】
各々のi=0,...,G−1に対して、
(d[i],a[i],b[i])=Trip[K,X+i]
ESI Xを有する修復パケットに配置されるG個の修復シンボルは、セクションB.5.3にて説明したように、中間シンボルCおよびLT符号器LTenc[K,C,(d[i],a[i],b[i])]を用い修復シンボルトリプルに基づいて計算される。
【0124】
<B.3.3 転送>
このセクションは、ファイル送出のためのMSCR前方誤り訂正を利用しているMSCR符号器/復号器およびいかなる転送プロトコルの間でも情報交換を記載する。
【0125】
ファイル送出のためのMSCR符号器および復号器は、転送プロトコルから以下の情報を必要とする。バイト単位のファイルサイズ、F、シンボル配列パラメータ、A、シンボルサイズ(T)(バイト単位でAの倍数である)、ソースブロックの数、Z、各々のソースブロックのサブブロックの数、N。ファイル配信のためのMSCR符号器は、加えて、符号化されるファイルがFバイトであることを必要とする。
【0126】
MSCR符号器は、各々のパケットのために、SBN、ESIおよび符号化シンボルを含む符号化パケット情報を転送プロトコルに出力する。転送プロトコルは透過的にMSCR復号器にこの情報を伝える。
【0127】
<B.3.4 推奨パラメータ(情報提供)>
<B.3.4.1 パラメータ決定アルゴリズム>
このセクションは4つの転送パラメータA,T,ZおよびNの導出の推奨値を提供する。
【0128】
この推奨値は以下の入力パラメータに基づいている。
【0129】
F:ファイルサイズ(バイト)
W:サブブロックサイズ目標(バイト)
P:最大のパケットペイロードサイズ(バイト)、Aの倍数であると仮定される
A:シンボル配列ファクタ(バイト)
KMAX:ソースブロック当たりのソースシンボルの最大数
KMIN:ソースブロック当たりのシンボルの最小目標数
GMAX:パケット当たりのシンボルの最大目標数
上記の入力に基づいて、転送パラメータT、ZおよびNは、以下の通りに算出される。
【0130】
G=min{ceil(P・KMIN/F),P/A,GMAX}−パケット当たりの平均シンボル数
T=floor(P/(A・G))・A
Kt=ceil(F/T)−ファイル内の総シンボル数
Z=ceil(Kt/KMAX)
N=min{ceil(ceil(Kt/Z)・T/W),T/A}
GおよびNの値は上述のように導出され下限として考慮される。例えば、2の累乗に近似した数などに、これらの値を増やすことは、有利となり得る。特に、上記のアルゴリズムはシンボルサイズTが最大パケットサイズPを区分することを保証しない。そして、正確にPのサイズのパケットが使用可能とはならない。その代わりに、Gは、P/Aを区分する値として選択される場合、シンボルサイズTはPの因子である。そして、サイズPのパケットが使うことができる。
【0131】
入力パラメータ、W、A、KMINおよびGMAXの推奨された設定は、以下の通りである。
【0132】
W=256KB A=4 KMIN=1024 GMAX=10
<B.3.4.2 例>
上記のアルゴリズムは図18に示すように結果として転送パラメータに導く。そして、W、A、KMINおよびGMAXおよびP=512のための推奨値となる。
【0133】
<B.4 ストリーミング>
<B.4.1 ソースブロック構築>
この文書において定義したように、ソースブロックは転送プロトコルによって組み立てられる。そして、システマチックMSCR前方誤り訂正符号を利用する。ソースブロックの組立および修復シンボルの組立に使われるシンボルサイズTは転送プロトコルにより提供される。いかなるソースブロックについてもソースシンボルの数が最高でもKMAXであるために、パラメータTがセットされるかもしれない。
【0134】
推奨されたパラメータは、セクションB.4.4に示される。
【0135】
<B.4.2 符号化パケット構築>
B.4.3にて説明するように各々の修復パケットは、SBN、ESI、SBLおよび修復シンボルを含む。修復パケットの中で含まれる修復シンボルの数は、パケット長から計算される。修復パケットに入れられるESI値および修復シンボルを生成するために用いる修復シンボルのトリプルは、セクションB.3.2.2にて説明したように、計算される。
【0136】
<B.4.3 転送>
このセクションは、MSCR符号器/復号器間の情報交換を記載し、いかなる転送プロトコルもストリーミングのためのMSCR前方誤り訂正を利用する。トリーミングのためのMSCR符号器は、各々のソースブロックのための転送プロトコルから、以下の情報を使用するかもしれない。シンボルサイズT(バイト)、ソースブロックのシンボル数K、ソースブロック番号(SBN)、符号化されるソースシンボル(K・Tバイト)。MSCR符号器は、各々の修復パケットのために、SBN、ESI、SBLおよび修復シンボルを含んでいるパケット情報を符号化することに関する転送プロトコルを出力する。転送プロトコルは透過的にMSCR復号器にこの情報を伝えるかもしれない。
【0137】
<B.4.4 推奨パラメータ>
<B.4.4.1 パラメータ決定アルゴリズム>
このセクションは、を転送パラメータTの導出の推奨値を提供する。この推奨値は、以下の入力パラメータに基づく。
【0138】
B:最大ソースブロックサイズ(バイト)
P:最大のパケットペイロードサイズ(バイト)、Aの倍数であると仮定される
A:シンボル配列ファクタ(バイト)
KMAX:ソースブロック当たりのソースシンボルの最大数
KMIN:ソースブロック当たりのシンボルの最小目標数
GMAX:修復パケット当たりのシンボルの最大目標数
これらの入力上の必要条件は、ceil(B/P)=<KMAXである。上記の入力に基づいて、転送パラメータTは、以下の通りに算出される。
【0139】
G=min{ceil(P・KMIN/B),P/A、GMAX}−パケット当たりのシンボル平均数
T=floor(P/(A・G))・A
上で導出されるTの値は、使用するTの実効値のガイドと思われなければならない。そのTをPに区分することは有利でもある。または、フルサイズ修復シンボルが消失する転送元パケット(ソースブロックのソースシンボルの最大数KMAXを超えない限り)終了後部分的なソースシンボルを回復するために用いるときに、より小さいTの値が消耗を最小化することはセットに有利でもよい。P、全ての転送元パケットが同一サイズである場合、それがそのようにTをそれに選ぶために有利で修復パケットPの中で、さらに、例えば、Tで優れたものは、転送元パケット径分布に依存できる実際のペイロードサイズは、Tの倍数であって、各々の転送元パケットがソースブロックにおいて、占めるバイト数(数バイトできる限りより大きく、または)に等しい。
【0140】
入力パラメータ、A、KMINおよびGMAXの推奨された設定は、以下の通りである。
【0141】
A=4 KMIN=1024 GMAX=10
<B.4.4.2 例>
上記のアルゴリズムは図19に示すように結果として転送パラメータに導く。そして、A、KおよびGMAXおよびP=512のための推奨値となる。
【0142】
<B.5 システマチックMSCR符号化器>
<B.5.1 符号化の概要>
システマチックMSCR符号器は、K個のソースシンボルを含むソースブロックから修復シンボルを生成するために用いる。シンボルは、符号化および復号プロセスの基本的なデータ単位である。各々のソースブロック(サブブロック)のために、全てのシンボル(サブシンボル)は、同一サイズである。符号化および復号化のためのシンボル(サブシンボル)に実行される動作は、排他的論理和演算である。
【0143】
C’[0],...,C’[K−1]はK個のソースシンボルを示す
C[0],...,C[L−1]はL個の中間シンボルを示す
符号化の第一段階は、K個のソースシンボルから中間シンボルの数(L>K)を生成することである。このステップにおいて、K転送元トリプル(d[0],a[0],b[0]),...,(d[K−1],a[K−1],b[K−1])はセクションB.5.4.4にて説明したように、Trip[]を使用して生成したK個のソーストリプルは、Kソースシンボルを伴い、逆の符号化プロセスを使用しているソースシンボルからL個の中間シンボルC[0],...,C[L−1]を決定するために用いる。この処理は、MSCR復号プロセスにより認識されることができる。
【0144】
特定の”所与の符号化関係”は、L個の中間シンボルの中で保持しなければならない。セクションB.5.2は、これらの関係および中間シンボルがソースシンボルから生成される方法を記載する。
【0145】
一旦中間シンボルが生成されると、修復シンボルは作成される。そして、単一のデータパケットにグループ、一つ以上の修復シンボルは配置される。各々の修復シンボルグループは、符号化シンボルID(ESI)および符号化シンボルの数(G)と関係している。ESIは、生成するために用いるトリプルの3整数(d、a、b)(各々の修復シンボル間のセクションB.5.4.4.にて説明したように、Trip[]を使用する)。これは、セクションB.3およびセクションB.5.4に記載されている生成器を使用し、B.4にて説明したように実行される。各々の(d,a,b)−トリプルはセクションB.5.4.3.に記載されているLTEnc[K,C[0],...,C[L−1],(d,a,b)]生成器を使用している中間シンボルから、対応する修復シンボルを生成するために用いる。
【0146】
<B.5.2 符号化の第1段階:中間シンボル生成>
<B.5.2.1 全般>
第1の符号化しているステップは、ソースシンボルC’[0],...,C’[K−1]からL個の中間シンボルC[0],...,C[L−1]を生成する予め行われる符号化ステップである。中間シンボルは、制約条件の2つのセットによって、独自に定義される。
【0147】
1.中間シンボルは、ソースシンボルのトリプルの一組によって、ソースシンボルに関連がある。セクションB.5.4.4にて説明したように、ソースシンボルトリプルの生成には、セクション5.2.2で定義されるを使用しているTrip[]を使用する。
【0148】
2.一組の予め行われる符号化関係は、それ自身を中間シンボルの中で保持する。これらは、セクションB.5.2.3において定義される。
【0149】
L個の中間シンボルの生成は、セクション5.2.4において定義される。
【0150】
<B.5.2.2 ソースシンボルのトリプル>
K個のソースシンボルのそれぞれは、0<i<Kのトリプル(d[i],a[i],b[i])に関係している。ソースシンボルトリプルは、セクションB.5.4.4で定義されるトリプル生成器を使用して決定される。
【0151】
0<i<Kを満たすそれぞれのiについて、
(d[i],a[i],b[i])=Trip[K,i]
<B.5.2.3 符号化前の関連付け>
L個の中間シンボルの間の予めの符号化関係は、第1のK個の中間シンボルに関して最後のL−K個の中間シンボルを表すことにより定義される。
【0152】
最後のL−K個の中間シンボルC[K],...,C[L−1]はS LDPCシンボルを含む、そして、SおよびHの値がそうであるHハーフシンボルは後述するようにKから決定される。そのため、L=K+S+Hである。
【0153】
X:X・(X−1)=2・Kとなる最小の自然数である
S:S>=ceil(0.01・K)+Xとなる最小の素数整数
H:(H、ceil(H/2))>=K+Sとなる最小の整数である
H’:ceil(H/2)L=K+S+H
C[0]、...、C[K−1] 最初のK個の中間シンボルを示す
C[K]、...、C[K+S−1] S LDPCシンボルを示す(ゼロに初期化される)
C[K+S]、...、C[L−1] H ハーフシンボルを示す(ゼロに初期化される)
S LDPCシンボルは、以下の処理の最後でC[K],...,C[K+S−1]の値であるように定義される。
【0154】
i=0、...、K−1 について以下を実行
a=1+(floor(i/S)%(S−1))
b=i%S
C[K+b]=C[K+b]^C[i]
b=(b+a)%S
C[K+b]=C[K+b]^C[i]
b=(b+a)%S
C[K+b]=C[K+b]^C[i]
H ハ−フシンボルは以下のように定義される。
【0155】
g[i]=i^(floor(i/2)) 全ての自然数iについて
注:g[i]はグレイシーケンスであり、各々の要素は前のものと単一のビット位置において異なる。
【0156】
g[j,k]は、jth要素を示す、j=0,1,2,...要二進表示で素が正確にk個のゼロでないビットを備えているg[i]の部分系列を示す。
【0157】
それから、ハーフシンボルは、以下の処理の後、C[K+S],...,C[L−1]の値として定義される。
【0158】
h=0,...,H−1 について以下を実行
j=0,...,K+S−1 について以下を実行
もしg[j,H’]のビットhが1の場合、C[h+K+S]=C[h+K+S]^C[j]
<B.5.2.4 中間シンボル>
<B.5.2.4.1 定義>
所与のK個のソースシンボルC’[0],C’[1],...,C’[K−1]についてL個の中間シンボルC[0],C[1],...,C[L−1]は以下を満たすように独自に定義されるシンボル値である。
【0159】
1.K個のソースシンボルC’[0],C’[1],...,C’[K−1]は、K個の制約条件がある
C’[i]≡LTEnc[K,(C[0],...,C[L−1]),(d[i],a[i],b[i])] 0<i<Kである全てのiについて
2.B.5.2.3で予め定義された符号化関係を満足するL個の中間シンボルC[0],C[1],...,C[L−1]
<B.5.2.4.2 中間シンボルの計算>
このサブセクションは、B.5.2.4.1の制約条件を満たしているL中間シンボルC[0],C[1],...,C[L−1]の算出方法を記載する。 K個の入力シンボルからN個の出力シンボルを生成するコードのための生成行列GはGF(2)の上のNxKマトリックスである。各々の列は出力シンボルのうちの1つに対応する。そして、入力シンボルのうちの1つおよびithとなる出力シンボルのところに対する各々の行は行が列のゼロでないエントリを含むそれらの入力シンボルの合計に等しい。
【0160】
そして、L個の中間シンボルは、以下の通りに算出されることができる。
【0161】
C:L個の中間シンボル(C[0],C[1],...,C[L−1])の列ベクトルを示す
D:S+Hのゼロシンボルを含む列ベクトルで、K個のソースシンボルC’[0],C’[1],...,C’[K−1]が続く
よって、上記の制約条件はGF(2)の上のLxLマトリックスと定義され、Aは
A・C=D である。
【0162】
マトリックスAは、以下の通りに組み立てられることが可能である。
【0163】
GLDPCは、DPCシンボルのSxKの生成行列である、そのため、
GLDPC・(C[0],...,C[K−1])T=(C[K],...,C[K+S−1])T
GHalfは、ハーフシンボルのH×(K+S)の生成行列である、そのため、
GHalf・(C[0],...,C[S+K−1])T=(C[K+S],...,C[K+S+H−1])T
IS:SxSの恒等行列を表す
IH:HxHの恒等行列を表す
0SxH:SxHの零行列を表す
GLT:LT符号器により生成される符号化シンボルのK×Lの生成行列である
そのため、
GLT・(C[0],...,C[L−1])T=(C’[0],C’[1],...,C’[K−1])T
すなわち、GLTi,j=1 もしC[i]は排他的論理和の生成したシンボルを含むだけなら
LTEnc[K,(C[0],...,C[L−1]),(d[i],a[i],b[i])]
そして、
Aの最初のS列は、GLDPC|IS|ZS×Hに等しい。
【0164】
Aの次のH列は、GHalf|IHに等しい。
【0165】
Aの残りのK列は、GLTに等しい。
【0166】
マトリックスAは、図20に示される。中間シンボルはそれから算出されることができる。
【0167】
C=A−1・D
いかなるKにおいても行列Aは最大ランクを有し、逆変換可能であるようにソーストリプルは生成される。この算出は、L個の中間シンボルC[0],C[1],...,C[L−1]を作成するためにMSCR復号プロセスをK個のソースシンボルC’[0],C’[1],...,C’[K−1]に適用することにより認識されることができる。
【0168】
ソースシンボルから効率的に中間シンボルを生成するために、それのような効率的な復号器実施態様がセクションB.6に記載されて用いられるというそれは、推奨される。ソースシンボルトリプルは、そのアルゴリズムを使用しているソースシンボルの効率的な復号化を容易にするように設計されている。
【0169】
<B.5.3 符号化の第2段階:LT符号化>
第二の符号化ステップにおいて、ESI Xを有する修復シンボルは、生成器を適用することによって、セクションB.3.2.2およびB.4.2に従ってトリプル(d,a,b)=Trip[K,X]を使用しているL個の中間シンボルC[0],C[1],...,C[L−1]にセクションB.5.4において定義されるLTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]を生成する。
【0170】
<B.5.4 生成器>
<B.5.4.1 乱数生成器>
乱数発生器Rand[X,m]は以下の通りに定められる。ここで、Xは非負整数である、iは非負整数である。そして、mは自然数である。そして、生成される値は0とm−1との間の整数である。V0およびV1を各々256のエントリの配列であるようにさせる。ここで、各々のエントリは4バイトの符号なし整数である。これらの配列は、セクションB.7において提供される。そして、
Rand[X,i,m]=(V0[(X+i)%256]^V1[(floor(X/256)+i)%256])%m
<B.5.4.2 度数生成器>
度数生成器[v]は以下の通りに定められる。vは少なくとも0で220=1048576より小さい整数である。
【0171】
図21において、 f[j−1]≦v<f[j]となるインデックスjを探す
Deg[v]=d[j]
<B.5.4.3 LT符号化シンボル生成器>
符号化シンボル生成器LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]は、以下の入力をする。
【0172】
Kは、ソースブロック(サブブロック)のためのソースシンボル(またはサブシンボル)の数である。LはセクションB.5.2にて説明したように、Kに由来するようにさせる。そして、L’L以上の最小の素数とする。
【0173】
(C[0],C[1],...,C[L−1])はセクションB.5.2にて説明したように、生成されるL個の中間シンボル(サブシンボル)である。
【0174】
(d、a、b)はセクションB.5.3.4で定義されたトリプル生成器使用して決定されるソーストリプルである。ここで、dは符号化シンボル度数を示す整数であり、aは1からL’−1に含まれる整数であり、bは0からL’−1に含まれる整数である。
【0175】
以下のアルゴリズムにより、符号化シンボル生成器は1つの符号化シンボルを出力として生成する。
【0176】
b≧Lにあいだ、b=(b+a)%L’を実行する
LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]=C[b]
j=1,...,min(d−1,L−1) について以下を実行する。
【0177】
b=(b+a)%L’
LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]=LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]^C[b]
<B.5.4.4 トリプル生成器>
トリプル生成器Trip[K,X]には次のものが入力される。
【0178】
K:ソースシンボル数
X:符号化シンボルID
LはB.5.2で説明したようにKに基づいて決定される
L’はL以上の最小の素数である
Q=65521、216未満の最大の素数
J(K)は、付録Aにおいて定義される、Kと関係するシステマチックデックスである。
【0179】
トリプル生成器の出力はトリプル(d、a、b)であり、以下の通りに決定される。
【0180】
1. A=(53591+J(K)・997)%Q
2. B=10267・(J(K)+1)%Q
3. Y=(B+X・A)%Q
4. v=Rand[Y,0,220]
5. d=Deg[v]
6. a=1+Rand[y,1,L’−1]
7. b=Rand[Y,2,L’]
<B.6 FEC復号化の実現例>
<B.6.1 全般>
このセクションは、この仕様に記載されているMSCRコードのための効率的な復号化アルゴリズムを記載する。各々がシンボルを符号化することを受信した注は、中間シンボルの間に均衡化の値と思われることができる。これらの連立方程式および中間シンボルの間の周知の予め符号化関係から、連立方程式を解くためのいかなるアルゴリズムも、中間シンボルおよびそれ故、ソースシンボルをうまく復号化できる。しかしながら、選択されるアルゴリズムは、復号化の計算効率に、大きな影響を及ぼす。
【0181】
<B.6.2 ソースブロックの復号化>
<B.6.2.1 全般>
復号器がそれが復号化するためにそうであるソースブロックの構造を知っていると仮定される。そして、シンボルサイズTでありK個のシンボルをソースブロックに含む。
【0182】
セクションB.5に記載されているアルゴリズムから、MSCR復号器は合計数L=K+S+Hを算出できる予め符号化シンボルの中で、そして、それらが復号化されるソースブロックからどのように生成されたかについて決定する。この説明において、復号化されるソースブロックのための受信された符号化しているシンボルが復号器に通過すると仮定される。さらに、この種の各々の符号化しているシンボルのために、数および排他論理和が符号化しているシンボルに等しい中間シンボルのセットが復号器に通過すると仮定される。ソースシンボルの場合、セクションB.5.2.2に記載されているソースシンボルトリプルは、各々のソースシンボルを与えるために概説する中間シンボルの数およびセットを指示する。
【0183】
N≧Kをソースブロックのための受信された符号化しているシンボルの数であるようにさせる。そして、M=S+H+N。LビットマトリックスAによる以下のMは、復号化されるソースブロックのための復号器に通過する情報に由来できる。CはL個の中間シンボルの列ベクトルであって、Dは受信機(MシンボルでぶりのS+HがLDPCおよびHalfシンボル(これらは、それ自身LDPCおよびHalfシンボルおよびLDPCおよびHalfシンボルのためでない検査符号である)に対応する0値を有するシンボルである)にとって公知の値を有するMシンボルの列ベクトルであるようにさせるようにさせる。そして、Mシンボルの残りのNは、ソースブロックのための受信された符号化しているシンボルである。それから、AはA・C=Dを満たすビットマトリックスである。ここで、GF[2]の上のマトリックス乗算を示す。一旦Cが複号化されるとインデックスjに対応する中間シンボルが符号化のインデックスiに対応するLDPC、Halfまたは符号化しているシンボルにXOR演算される場合A[i,j]=1である。または、インデックスiがLDPCまたはHalfシンボルおよびインデックスに対応する場合、jは同じLDPCまたはHalfシンボルに対応する。他の全てのiおよびjについて、A[i,j]=0である。
【0184】
ソースブロックが周知のAからCを復号化して、等しい復号化およびそれがそうであるDはそのCをクリアする復号化できるのときかつそのときに限ってGF[2]はLである。シンボルがシンボルが各々の行方不明のソースシンボルを得るためにXOR演算される中間シンボルの数およびセットを決定するためにトリプルにするソースを使用して得られることが可能である転送元をはずす。
【0185】
復号化Cの第一段階は、復号化予定を形成することになっている。このステップにおいて、L恒等行列によるLに、Aは、ガウス消去(列動作および列および行の並べ替えを使用する)を用いて、そして、M−L列を放棄した後に変換される。復号化予定はガウス消去処理の間、列動作および列および行の並べ替えのシーケンスを含んで、Aに、そして、DからのCの復号化が復号化予定の化成と並行して場所に持っていくことができるD.以外に依存するだけである、または、復号化が復号化予定に基づいてその後起こることができる。
【0186】
復号化予定およびCの復号化の間の相関関係は、以下の通りである。まず最初にc[0]=0,c[1]= 1...,c[L−1]=L−1およびd[0]=0,d[1]=1...,d[M−1]=M−1である。
【0187】
復号化予定において、そしてD[d[i]]がXOR演算される復号プロセスシンボルにおいて、−Aの各々の時間列iは、列iにXOR演算されるシンボルD[d[i’]]。
【0188】
復号化予定において、そしてd[i]の値が値と交換される復号プロセスで−各々の時間列iは、列iと交換されるd[i’]。
【0189】
復号化予定において、そしてc[j]の値がc[j’]の値と交換した復号プロセスで−各々の時間行jは、行jと交換される。
【0190】
この通信から、ソースブロックの復号化のシンボルの排他的論理和の合計数がガウス消去の段数動作(交換でない)であることは、明らかである。Aがガウス消去の後のLの恒等行列による。そして、最後のM−Lを廃棄した後のLであるので、LシンボルD[d[0]],D[d[1]],...,D[d[L−1]]がLシンボルC[c[0]],C[c[1]],...,C[c[L−1]]の値であることは復号化に成功したことは明白である。
【0191】
復号化が成功しているのであるにせよ、ガウス消去が復号化予定には関係がない形式に実行される命令。しかしながら、復号化の速度は、重く、ガウス消去が実行されるオーダーに依存する。(さらにまた、Aのまばらな表現を維持することは重要である。但し、これはここで記載されていない)。このセクションの剰余は、比較的効率的であるガウス消去が実行されることができた命令を記載する。
【0192】
<B.6.2.2 第1段階>
マトリックスAが下位行列に仕切られて、概念的にあるガウス消去の第一段階。部分行列サイズは、0まで初期化される非負整数iおよびuによって、パラメータで表される。Aのサブマトリックスは、以下の通りである
(1) Iが第1のi列および第1のi行の交差によって、定めた部分行列。これは、位相における各々のステップ終了後の恒等行列である。
(2) 第1のi列および第1のi行以外はおよび最後のu行の交差により定義される部分行列。この部分行列の全てのエントリは、ゼロである。
(3) 第1のi行および第1のi列以外はの交差により定義される部分行列。この部分行列の全てのエントリは、ゼロである。
(4) 全ての列および最後のu行の交差により定義される部分行列U。
(5) 部分行列Vは、第1のi行以外はおよび最後のu行および第1のi列以外はの交差によって、形をなした。
【0193】
図22は第一段階の初めのA.対各々のステップの= A.の下位行列を例示する、列のAは選択される。Vの構造により定義される以下のグラフが、Aのどの列が選択されるか決定する際に使われる。Vを横切る行は、グラフのノードである。そして、正確にVの2つのものを有する列は、2つのものの位置の2つの行(ノード)を接続するグラフの端である。グラフのノード/刃の各対間の経路があるように、このグラフのA構成要素はノード(行)および端(列)の最大セットである。構成要素のサイズは、構成要素のノード数(行)である。
【0194】
Lステップが、最高でも第一段階にある。i+u=Lとき、位相は、うまく終える、すなわちVおよびVより上の全ゼロ部分行列が消える。そして、Aは、含むI、下記の全0部分行列I、そして、U.失敗していくつかでVの前のステップがそこで消える場合、失敗を復号化する際の位相両端部は、そのステップで選択をするVのゼロでない列でない。各々のステップにおいて、Aの列は、以下の通りに選択される。Vの全てのエントリがゼロである場合、列は選択されない、そして、復号化は失敗する。Aの少なくとも一つの列が正確にVのrものを有するように、rを最小限の整数であるようにさせる。r#2がそれから正確に最小限のオリジナル程度を有するVのrものを有する列を全てのこの種の列から選択する場合。r=2がそれから正確にXにより定義されるグラフの最大サイズ構成要素の一部であるVの2つのものを有する列を選択する場合、列がこのステップで選択されたあと、選ばれた列がVと交差する第一系列であるために、Vを横切るAの第一系列は選ばれた列と交換される。選ばれた列のrのうちの1つがVの第一塔に現れるために、そして、残りのr−1がVの最後の行に現れるために、Vを横切るものの中のAの行は追加注文される。
【0195】
それから、選ばれた列は、Vの第一のものを有する選ばれた列の下で、Aの全ての他の列にXOR演算される。
【0196】
最後に、iは1時までに増加する。そして、uはr−1まで増加する。そして、それはステップを完了する。
【0197】
<B.6.2.3 第2段階>
部分行列Uは、更に仕切られる最初のi列、Uupper、そして、残りのM−i列、Ulower。ガウス消去は、その順位がu(復号化失敗)より少ないと決定するかuがこぐ第一が恒等行列(第二段階の成功)であるマトリックスにそれを変換するために、Ulower上の第二段階において、実行される。u恒等行列Iuによって、このuを呼ぶ。Ulower−Iuと交差するAのM−L列は、放棄される。この位相の後、Aは、L列およびL行を有する。
【0198】
<B.6.2.4 第3段階>
第二段階の後、L恒等行列によって、LにAを変換し終わるために外へゼロに合うことを必要とするAの唯一の部分は、Uupperである。部分行列Uupperの段数iは、通常、Uupperの行uの数非常に大きい。効率的にUupper(以下の前計算マトリックスU)からのゼロまで』、第三段階およびそれからUのIuに基づいて計算される』が、Uupperからゼロまで第四段階において、使われる。Iuの列が仕切られるuは、各々(u/8)グループの8本の列を張る。それから、8本の列の各群のために、8本の列の全てのゼロ以外の組合せは、計算される。そして、28に結果としてなる−1=255列(これは、28−8−1=247により行われることができるグループにつき列の中で排他論理和は、ハミング重みの組合せからIuに現れるものがある必要を行わないことを−計算する)。このように、結果として生じる前計算マトリックスUは、.255がこぐceil(u/8)およびu行を有する。そのUを強調する形式的にマトリックスAの一部でない、しかし、Uupper−B.からのゼロに対する第四段階の使われる。
<B.6.2.5 第4段階>
列にAの各々の第1のi列間の、Uupperの8つの行エントリのセットが全てゼロ(そして前計算マトリックスUの列)でない場合この列のUupper部分行列の8つの行の各群間の、8つの行のパターンがそうであるマッチは、列にXOR演算した。このようにねらいを定める排他的論理和を犠牲にした列のそれらの8つの行が、Uの中で外に。
【0199】
この位相AがL恒等行列および完全な復号化によるLであったあと、予定はうまく形成された。それから、シンボルを符号化して公知の対応する復号化を含んでいる排他的論理和は、復号化予定に基づいて中間シンボルを回復するために完成していることがありえる。
【0200】
全てのソースシンボルと関連するトリプルは、B.5.2.2に従って計算される。受信されたソースシンボルのためのトリプルが、復号化において、使われる。行方不明のソースシンボルのためのトリプルは、どの中間シンボルが行方不明のソースシンボルを回復するためにXOR演算されることを必要とするかについて決定するために用いる。
【0201】
<マルチステージ符号の特性>
上述の多くの例において、入出力シンボルはビットの同数のための98を符号化する。そして、各々の出力シンボルは1つのパケット(完全に受信されるか完全に消失する輸送の装置であるパケット)において、配置される。いくつかの実施形態では、各々のパケットがいくつかの出力シンボルを含むために、通信システムは変更を加えられる。多くの要因に基づいて、出力シンボル値のサイズは、それから、ストリームのファイルまたはブロックを入力シンボルに最初に分割する際の入力シンボル値のサイズで測定されるサイズに対するセットである。復号プロセスは基本的に不変のままである。但し、次の場合は除く−各々のパケットが受信されながら、出力シンボルは束に到着する。
【0202】
入力シンボルおよび出力シンボルサイズの設定は、通常、ストリームのファイルまたはブロックのサイズおよび出力シンボルが送信されることになっている通信システムにより口述される。たとえば、通信システムが少しのデータを定義済みサイズのパケットまたは他の方法のグループビットに分類する場合、シンボルサイズの計画はパケットまたはグループ化サイズから開始される。そこから、デザイナーはどれくらいの出力シンボルが1つのパケットかグループにおいて、担持されるかについて決定する。そして、それは出力シンボルサイズを決定する。説明を簡単にするため、デザイナーは入力シンボルサイズを出力シンボルサイズに等しくたぶん設定する、しかし、入力データが異なる入力シンボルサイズをより便利にする場合、それが使うことができる。
【0203】
上記の符号化プロセスは、ストリームのオリジナルファイルまたはブロックに基づいて出力シンボルを含んでいるパケットのストリームを作成する。ストリームの各々の出力シンボルは他の全ての出力シンボルの中でそれぞれに生成される。そして、作成されることができる出力シンボルの数上の下であるか上の跳躍がない。キーは、各々の出力シンボルを伴う。そのキーおよびストリーム(出力シンボルの値を決定する)の入力ファイルまたはブロックの若干の内容。連続的に生成された出力シンボルは連続的なキーを有する必要はない、そして、それがランダムに好ましい使用目的によってはキーのシーケンスを生成するか、または疑似ランダム的にシーケンスを生成する。
【0204】
マルチステージ復号化は入力シンボル値、それからファイルまたはブロックが、非常に高い確率によって、平均上のK+A出力シンボルからの改装本でありえながら、ストリームのオリジナルファイルかブロックがK等しい大きさの入力シンボルおよび各々の出力シンボル値に分割されることができるかどうかは同じ長さである特性を有する。ここで、AはKと比較して小さい。たとえば、上に導入される重み分布のために、Kが19,681大きい場合、Aの値がa*Kを上回るという確率は多くても10−12である。そして、それはKのいかなる値のためもの多くても10−10である。特定の出力シンボルがランダムであるか疑似乱数のオーダーにおいて、生成されるので、移動中の特定の出力シンボルの損失がランダムとみなされて、そして、若干の小さい相違は、入力ファイルを回復するために必要な出力シンボルまたはブロックの実数値の中に存在する。場合によっては。ここで受信機が出力パケットの一つ以上の転送元からより多くのパケットを集めることができる場合、パケットが十分に全ての入力ファイルまたはブロック、入力ファイルまたはブロックを復号化しないためにそうであるK+Aの特定のコレクションはまだ回収可能である。
【0205】
出力シンボルの数が1の解答により制限されるだけであるので、K+Aより適切に、出力シンボルを、生成できる。たとえば、Iが32ビット数である場合、40億の異なる出力シンボルを、生成できるのに、ストリームのファイルまたはブロックはK=50,000入力シンボルを含むことができた。ある用途では、少数のそれらの40億の出力シンボルだけは生成されることができて、送信されることができる。そして、それはストリームの入力ファイルまたはブロックが可能な出力シンボルの非常に小さい割合いを有する改装本でありえるという近い確信および入力ファイルまたはブロックがK出力シンボル(入力シンボルサイズが出力シンボルサイズと同様であると仮定する)よりわずかに改装本でありえるかなりの確率である。
【0206】
ある用途では、それは、受け入れられてもよいために入力シンボルの全てを復号化するか、または、比較的低い確率によって、以外、入力シンボルの全てを復号化することが可能なことが可能である。この種のアプリケーションにおいて、受信機は、K+A出力シンボルを受信した後に入力シンボルの全てを復号化することを試みるのを止めることができる。または、受信機は、K+A出力シンボル未満の受信の後で出力シンボルを受信するのを止めることができる。ある用途では、受信機は、K以下出力シンボルを受信しさえすることができるだけである。このように、本本発明の若干の実施例で、所望の精度が全ての入力シンボルの完全回復である必要があるというわけではないと理解されることになっている。
【0207】
更に、不完全な回復が受け入れられる若干のアプリケーションで、データが入力シンボルの全てが回復されることができるというわけでないようであるものまたはこの種のその完全回復を符号化されることができること、入力シンボルは、そうする必要とする多くのより多くの出力シンボルの中で受信入力シンボルの数である。この種の符号化は、通常、より計算でない能力を必要として、このように、符号化の計算能力を減少させる受け入れられる方法であってもよい。 上記の図のさまざまな機能ブロックがハードウェアおよび/またはソフトウェアの組合せにより行うことができることが、よく理解されていることになっている。そして、いくつかまたはいくつかのブロックの相関性の全てがそうすることができる特殊作成のそれは、ある合成。同様に、また、本願明細書において、記載されているさまざまな方法がハードウェアおよび/またはソフトウェアの組合せにより行うことができると理解されることになっている。
【0208】
前記説明は、例示的であり限定的でない。本発明の多くのバリエーションは、この開示の再調査に応じて、従来技術において、技術のそれらにとって明らかになる。本発明の範囲は、従って、前記説明に関して決定されてはならない。その代わりに等価物のそれらの完全な範囲とともに、添付の請求の範囲に関して決定されなければならない。
【0209】
<付録A. システマチックインデックスJ(K)の値>
Kの値それぞれについて、ソースシンボルトリプル群(d[0],a[0],b[0]),...,(d[L−1],a[L−1],b[L−1])がL個の中間シンボルが固有となるよう指定可能な特性を有するように、システマチックインデックスJ(K)は設計されている。すなわち、セクションB.5.2.4.2のマトリックスAは最大の階数(ランク)であり逆変換可能な特性を有するように設計されている。以下は、4から8192が含まれるKの値に対応するシステマチックインデックスのリストである。値の順序は、読書の順序と同じである。すなわち、第1行の最初の数値から第1行の最後の数値、そして、第2行の最初の数値に続き、以下同様である。
<付録B.1 テーブルV0の値>
これらの値は、上述の明細書のセクションB.5.4.1で述べられたテーブルV0の値の例示的なセットを示している。各々の成分は10進数表記の32ビット整数である。値の順序は、第1カラムの最上段から第1カラムの最下段、そして、第2カラムの最上段に続き、以下同様である。
<付録B.2 テーブルV1の値>
これらの値は、上述の明細書のセクションB.5.4.1で述べられたテーブルV1の値の例示的なセットを示している。各々の成分は10進数表記の32ビット整数である。値の順序は、第1カラムの最上段から第1カラムの最下段、そして、第2カラムの最上段に続き、以下同様である。
【図面の簡単な説明】
【0210】
【図1】本発明の一実施例に従う通信システムのブロック図である。
【図2】本発明の一実施例に従う符号器のブロック図である。
【図3】本発明の一実施例に従う冗長シンボルを生成する方法の簡略ブロック図である。
【図4】本発明の一実施例に従うスタティック符号器の基本操作の簡略ブロック図である。
【図5】本発明の一実施例に従うダイナミック符号器の簡略ブロック図である。
【図6】本発明の一実施例に従うダイナミック符号器の基本操作の簡略ブロック図である。
【図7】本発明の一実施例に従うスタティック符号器の簡略ブロック図である。
【図8】本発明の一実施例に従うスタティック符号器の基本操作の簡略ブロック図である。
【図9】一特定実施例に従うスタティック符号器の符号化パラメータを算出する方法の簡略図である。
【図10】本発明の他の実施例に従うスタティック符号器の簡略フローチャートである。
【図11】本発明の一実施例に従う復号器の簡略ブロック図である。
【図12】本発明の一実施例に従う復号器の動作の簡略フローチャートである。
【図13】本発明の他の実施例に従う復号器の動作の簡略フローチャートである。
【図14】本発明のさらにもう一つの実施例に従う復号器の動作の簡略フローチャートである。
【図15】本発明の一実施例に従うダイナミック復号器の簡略ブロック図である。
【図16】本発明の一実施例に従うスタティック復号器の簡略ブロック図である。
【図17】サブシンボル写像からのソースシンボルを示す図である。
【図18】さまざまなファイルサイズのファイルのダウンロードパラメータの可能な設定を示す図である。
【図19】さまざまなソースブロックサイズのストリーミングパラメータの可能な設定を示す図である。
【図20】ソースおよび中間シンボルとの関係を示すマトリックスの形式を示す図である。
【図21】度数生成器の度数分布を示す図である。
【図22】復号化に使用可能なマトリックスAの形式を示す図である。
【技術分野】
【0001】
本発明は、通信システムにおける符号化、復号化に関するものであり、より詳細には通信データの誤りおよびギャップを考慮した符号化、復号化を行う通信システムに関するものである。実施例において、データは、ブロードキャストまたはマルチキャスト無線ネットワークを介して受信機に転送される。
【背景技術】
【0002】
送り手と受け手との間で通信チャネルを介して行うファイルおよびストリームの転送は多くの文献の主題として取り上げられてきた。好ましくは、受け手は、送り手からチャネルを介して送信される正確なデータのコピーをあるレベルの確実性をもって受信することを望む。ほとんどの物理的に実現可能なシステムがそうであるように、チャネルは完全な忠実度を有していないため、転送により消失するか歪められるデータを取り扱う方法に関心が生じる。受け手は、いつ破損データが誤ってデータ受信されたかの判断を常に行えるとは限らないので、通常、破損データ(誤り)に比較し欠落データ(消去)を取扱うのは容易である。多くの誤り訂正符号は、消去および/または誤りを修正するために開発された。一般的に、データが送信されているチャネルおよび送信されているデータの性質の不忠実度に関する何らかの情報に基づいて使用する特定の符号(コード)が選択される。たとえば、チャネルが長期間の不忠実度を有することが既知の場合、そのアプリケーションのためにはバースト誤り符号が最適であり得る。短くまれな誤りだけが予想される場合、簡単なパリティ符号が最善であり得る。
【0003】
送信機および受信機が通信のために必要とされる演算能力および電力の全てを有し、送受信装置間のチャネルが相対的にエラーフリーの通信を可能とするのに十分クリーンであるときに、データ転送は直接なされる。そして、チャネルが悪環境であるか、または、送信機および/または受信機の能力が制限されている場合に、データ転送の問題はより難しくなる。
【0004】
1つのソリューションは、受信機が転送における消去および誤りから回復可能とするために、データを送信機で符号化する前方エラー訂正(FEC)技術を活用する方法である。受信機が送信機に誤りについての通信が可能な受信機から送信機への逆方向チャネルが利用可能な場合、その伝送プロセスを調整可能である。しかし、しばしば逆方向チャネルは利用可能ではない。たとえば、送信機が多数の受信機に対して送信している場合、送信機はそれらの全ての受信機からの逆方向チャネルを処理することが可能でないかもしれない。その結果、通信プロトコルはしばしば逆方向チャネルなしで設計されることを必要とし、そして、送信機はこれらのチャネル状況の全容無しに広く様々なチャネル状況を取扱わなければならないかもしれない。
【0005】
受信機がポータブルまたは移動可能である低出力の小型デバイスであり高帯域でデータを受信することを必要とする場合、送信機と受信機間のデータ転送の問題はより難しくなる。たとえば、ファイルまたはストリームをブロードキャストまたはマルチキャストにより、固定された送信機から多数もしくは不確定数のポータブルまたは移動可能な受信機に配信するよう設定される無線ネットワークであり、受信機が演算能力、記憶容量、利用できる電力、アンテナサイズ、デバイスサイズおよびその他の設計制約条件において拘束される場合である。
【0006】
このようなシステムでは、逆方向チャネルが少ないか皆無であり、メモリー制限、コンピューティングサイクル制限、移動可能性およびタイミングを含む考慮が必要である。各々の受信機の電源の予測不可能なオン/オフ、範囲の出入り、リンクエラー、セル切替、セル内輻輳によるファイルまたはストリームパケットに対する強制的一時的な優先度引き下げなどにより損失が発生するため、望ましくは、潜在的に大きい数の受信機に配信するために必要なデータの転送時間の最小化するよう設計しなければならない。
【0007】
データ転送のために使用するパケットプロトコルの場合、パケット網を通じて送信されるファイル、ストリームまたは他のデータブロックは等しいサイズ入力シンボルに仕切られ、入力シンボルは連続的なパケットとして配置される。入力シンボルが実際にビットストリームに分解されるか否かに関わらず、入力シンボルの”サイズ”はビット単位で測定することができる。そして、入力シンボルが2M個のシンボルのアルファベットから選択される場合、入力シンボルはMビットのサイズを有する。この種のパケットベースの通信システムにおいて、パケットに基づいた符号体系が適切である。指定された受け手がネットワークによる消去が発生したにもかかわらずオリジナルファイルの正確なコピーを回復可能な場合、ファイル転送は信頼性が高いと呼ばれる。指定された受け手がネットワークによる消去が発生したにもかかわらずタイムリーな方法でストリーム各部の正確なコピーを回復可能な場合、ストリーム転送は信頼性が高いと呼ばれる。また、ファイルまたはストリームの一部が回復可能でない、または、ストリーミングにおいてストリームの一部がただちに回復可能ではない場合などには、ファイル転送およびストリーム転送はいくらか信頼性が高くありえる。パケット損失は、散発的な輻輳の発生によりルータのバッファリングメカニズムが処理限界に達し入力パケットが強制的にドロップされることにより生じる。そのため、転送中の消去発生に対する保護について多くの研究がなされてきた。
【0008】
ファイルまたはストリームの入力シンボルから任意数の出力シンボルを生成する連鎖反応符号を使用することが知られている。受信機が、既に知っているデータを複製する追加データを受信する情報複製の方法に対して、この方法には情報付加的な出力シンボルの生成を含む多くの用途がある。連鎖反応符号を生成、利用、動作している新規の技術がいくつか公開されており、たとえば、Lubyに発行される米国特許第6,307,487号”Information Additive Code Generator and Decoder for Communication Systems”(”ルビーI”)、Lubyらに発行される米国特許第6,320,520号”Information Additive Group Code Generator and Decoder for Communication Systems”(以下、”ルビーII”)、そして、2003年3月27日にショクロラヒらに発行された米国特許公開2003/0058958号”Multi-Stage Code Generator and Decoder for Communication Systems”(以下、”ショクロラヒ”)に示されている。許可される範囲において、全ての目的のためこれらの全ての開示を本願明細書に引用する。
【0009】
連鎖反応符号器により作成される出力シンボルの特性の1つとして、受信機は十分な出力シンボルを受信するとすぐにオリジナルファイルまたはオリジナルストリームのブロックを回復することが可能であるということがある。具体的には、高確率を有するオリジナルのK個の入力シンボルを回復するために、受信機はおよそK+A個の出力シンボルを必要とする。ここで、比A/Kは”相対的受信オーバーヘッド”と呼ばれる。相対的受信オーバーヘッドは、入力シンボル数K、および、復号器の信頼性に依存する。たとえば、ある特定実施例において、K=60,000であり、少なくとも1−10−8の確率で入力ファイルまたはストリームのブロックを復号器が復号化可能な相対的受信オーバーヘッドが5%の場合、K=10,000では、相対的受信オーバーヘッドが15%の場合同様の確率で復号化可能となる。ある実施例においては、連鎖反応コードの相対的受信オーバーヘッドは(13*sqrt(K)+200)/Kとして計算することが出来、ここで、sqrt(K)は入力シンボル数Kの二乗根である。この実施例において、連鎖反応コードの相対的受信オーバーヘッドは、Kが小さい値であるほど大きくなる傾向がある。
【0010】
ルビーI、ルビーIIおよびショクロラヒは、本発明による特定の実施例において使用可能なシステム及び方法の教示を提供する。しかしながら、それらのシステム及び方法は、本発明および他の多くのバリエーション、変更態様を必要とせず、代替物が使用可能であることが理解できるであろう。
【0011】
また、マルチステージ連鎖反応(”MSCR”)符号を使用することも公知であり、例えばショクラヒに記載されデジタルファウンテン社により開発され”Raptor”として商品名の符号がある。マルチステージ連鎖反応符号は、たとえば、ソースファイルまたはソースストリームから入力シンボルを受信し、そこから中間シンボルを生成し、連鎖反応符号を用いた中間シンボルを符号化する符号器により用いられる。より詳しくは、送信される入力シンボルの順序集合から複数の冗長シンボルが生成される。そして、入力シンボルおよび冗長シンボルを含むシンボルの複合セットから複数の出力シンボルが生成される。ここで、可能な出力シンボルの数はシンボルの複合セットのシンボルの数に比較し非常に大きい。また、少なくとも一つの出力シンボルは、シンボルの複合セットの1つのシンボルより多く全てシンボル数より少ないシンボルから生成され、入力シンボルの順序集合が所定数Nの何れの出力シンボルからも所望の精度まで再生できるようなシンボルである。
【0012】
用途によっては、他のバリエーションの符号がより適切であり、他のもの選択されるかもしれない。
【発明の開示】
【発明が解決しようとする課題】
【0013】
転送元から転送先まで通信チャネルを介して転送されるデータを符号化する方法を提供する。
【課題を解決するための手段】
【0014】
本発明のある実施例によれば、転送元から転送先まで通信チャネルを介して転送されるデータを符号化する方法が提供される。その方法は、入力シンボルの順序集合を操作し、入力シンボルから複数の冗長シンボルを生成することを含む。また、その方法は、入力シンボルおよび冗長シンボルを含むシンボルの複合セットから複数の出力シンボルを生成することを含み、可能な出力シンボルの数はシンボルの複合セットのシンボルの数に比較し非常に大きく、少なくとも一つの出力シンボルはシンボルの複合セットの1つのシンボルより多く全てシンボル数より少ないシンボルから生成され、入力シンボルの順序集合が任意の所定数の出力シンボルからも所望の精度まで再生できるようなシンボルである。複数の冗長シンボルは、第1入力シンボルを使用して算出されるスタティックシンボルの第1セットは、第1入力シンボルと異なる第2入力シンボルを使用して算出されるスタティックシンボルの第2セットと弱い関連性を有するように、確定的過程において送信される入力シンボルの順序集合から生成される。
【0015】
本発明のさらに別の実施例によれば、通信チャネルを介して転送先から転送されるデータを受信するシステムは類似した技術を使用し提供される。そのシステムは、通信チャネルを通じて送信される出力シンボルを受信するための通信チャネルに接続された受信モジュールを含み、各々の出力シンボルは入力シンボルおよび冗長シンボルの複合セットの少なくとも1つのシンボルから生成され、少なくとも1つの出力シンボルは複合セットの1より多く全てより少ないシンボルから生成され、可能な出力シンボルの数は複合セットのシンボルの数に比較し非常に大きく、入力シンボルは順序集合からなる入力シンボルであり、冗長シンボルは入力シンボルから生成される。ここで、複数の冗長シンボルは、第1入力シンボルを使用して算出されるスタティックシンボルの第1セットは、第1入力シンボルと異なる第2入力シンボルを使用して算出されるスタティックシンボルの第2セットと弱い関連性を有するように、確定的過程において送信される入力シンボルの順序集合から生成される。
【0016】
本発明のさらに別の実施例によれば、搬送波により表現されるコンピュータデータ信号が提供される。
【発明の効果】
【0017】
多数の利点が、本発明により達成される。たとえば、ある実施例においては、チャネルを介して転送するデータの符号化に必要な計算能力が低減可能である。さらに他の実施例において、このデータの復号化に必要な計算能力が低減可能である。実施例により、これらの利点の1つ以上を達成できる。これらおよびその他の利点の更なる詳細が、本願明細書全体および特に下記記載により提供される。
【0018】
本願明細書において開示される本発明の性質および効果の更なる理解は、明細書および添付の図面の残りの部分を参照することで認識される。
【発明を実施するための最良の形態】
【0019】
(関連出願の相互参照)
本出願は、2004年5月7日に出願された米国特許出願番号第60/569,127号の”FILE DOWNLOAD AND STREAMING SYSTEM”に基づく優先権を主張する。それは、全ての目的のためにその開示全体を本願明細書に引用しこの文書に全部記載されるものとして組み込まれる。
【0020】
詳細な説明の後に以下の3つの付録を示す。付録Aは、システマチックインデックスJ(K)の値の例を含む。付録B.1は、テーブルV0の値の例を含む。そして、付録B.2は、テーブルV1の値の例を含む。
【0021】
(特定実施例の詳細な説明)
ここに記載される特定実施例において、”マルチステージ符号化”として表記される符号体系が記載されており、その実施例はショクロラヒにより提供される。
【0022】
ここに記載されるマルチステージ符号化は複数の段階によりデータを符号化する。常にではないが、一般的には、第1段階では予め指定される量の冗長性をデータに付加する。第2段階ではオリジナルデータおよび符号化の第1段階により計算される冗長シンボルから連鎖反応コード等を使用し出力シンボルを生成する。本発明の一特定実施例において、受信されたデータは、最初に連鎖反応復号プロセスを使用して復号化される。その処理により完全にオリジナルデータを回復することが出来ない場合、第2の復号ステップが適用される。
【0023】
マルチステージ符号化の実施例において、冗長シンボルは、符号化の第一段階において、入力ファイルまたはストリームのブロックから生成される。これらの実施例では、符号化の第二段階で、出力シンボルは、入力ファイルまたはストリームのブロックおよび冗長シンボルの組合せから生成される。これらの実施例において、出力シンボルは、必要に応じて生成されることができる。第二段階が連鎖反応符号化を含む実施例において、各々の出力シンボルは他の出力シンボルが生成される方法に関係なく生成されることができる。一旦生成されると、これらの出力シンボルはパケット内に配置され転送先に転送される。ここで、各々のパケットは1個以上の出力シンボルを含んでいる。非パケット化転送技術も利用可能であり同様に使うことができる。
【0024】
ここで使用される用語”ファイル”は、1個以上のソースを格納し1以上の転送先にユニットとして配信される任意のデータを示している。したがって、文書、画像、およびファイルサーバまたはコンピュータ記憶装置からのファイルは、すべて、転送される”ファイル”の例である。ファイルは、周知のサイズ(例えばハードディスクに保存される1メガバイトの画像)でもよいし、未知のサイズ(例えばストリーミングソースの出力から取得されるファイル)でもよい。いずれの場合においても、ファイルは一連の入力シンボルであり、各々の入力シンボルはファイル内の位置および値を有する。
【0025】
ここで使用される用語”ストリーム”は、1個以上のソースを格納もしくは生成された順番に各時点で特定のレートで配信される任意のデータを示している。ストリームは、固定レートまたは可変レートでありえる。したがって、MPEG映像ストリーム、AMR音声ストリーム、遠隔装置の制御に使用されるデータストリームは全て転送される”ストリーム”の例である。各時点でのストリームのレートは、既知(例えば4メガビット/秒)でもよいし、未知(例えば各時点のレートが前もって分からない可変レートストリーム)いずれの場合においても、ストリームは一連の入力シンボルであり、各々の入力シンボルはストリーム内の位置および値を有する。
【0026】
転送は、ファイルまたはストリームを配信するために1以上の送信機から1以上の受信機までチャネルを介してデータを送信する処理である。また、送信機を符号器と称することもある。1台の送信機が完全なチャネルにより任意数の受信機に接続している場合、受信データは入力ファイルまたはストリームの正確なコピーであり、全てのデータが正しく受信される。ここでは、現実のチャネルの多くの場合と同様、チャネルが完全でないと仮定する。多くのチャネルの欠点の中で、重要な2つの欠点は、データ消去およびデータ消去の特殊例とみなすことが可能なデータ不完全性である。データ消去は、チャネルが消失またはデータがドロップした場合に発生する。データ不完全性は、いくつかのデータが素通りするまで受信機がデータを受信し始めない場合、受信機が転送が終了する前にデータを受信するのを止めた場合、受信機が一部の送信データを受信することを選択する場合、および/または、受信機が断続的に止まり、再びデータを受信し始めた場合に発生する。データ不完全性の例としては、移動中の衛星送信機が入力ファイルまたはストリームを示すデータを送信している場合、受信機が範囲内に入る前に転送を始めるかもしれない。一旦受信機が範囲内に入ると衛星が動いて範囲外に出るまでデータを受信することが出来、一旦受信機が範囲に入るとデータを受信可能となり、それまで、受け側がどのポイント、他のものにより送信されている同じ入力ファイルかストリームについてデータを受信し始めるためにその衛星アンテナ(それは、どの時間の間にデータを受信していないか)をリダイレクトすることができるかそれが有する衛星は範囲へ移動した。この説明を読むことから明らかでなければならなくしながら、データ不完全性はデータ消去の特例である。これは、次のことの故である。あたかも受け側が全ての時範囲において、あるかのように、受け側はデータ不完全性(そして、受け側には、同じ問題がある)を処理できる、しかし、チャネルは受け側がデータを受信し始めた位置まで全てのデータを消失した。また、周知のように、通信システム設計で、検出可能な誤りは、単に検出可能な誤りを有する全てのデータブロックまたはシンボルをドロップすることによって、消去に等しいとみなされることができる。
【0027】
若干の通信システムにおいて、受け側は、多数の送信機によってまたは並列に接続を使用している1台の送信機により生成されるデータを受信する。たとえば、ダウンロードの速度を上げるために、受け側は、同時に同じファイルに関して送信データに複数の送信機につながるかもしれない。別の例としてマルチキャスト転送で、多数のマルチキャストデータストリームは、受け側が総計の伝送速度をそれらを送信機に接続しているチャネルの帯域幅と適合させるためにこれらのストリームの一つ以上につながることができるために送信されるかもしれない。全てのこの種の場合において、懸念は、全てのその送信データを確保することが受け側に独立用途の中であるということである。すなわち、多重ソースデータは、そうである冗長ストリームの伝送速度が異なるストリームのために非常に異なるときでも、そして、損失の任意のパターンがあるときに、一つの。
【0028】
一般に、通信チャネルは、送信機およびデータ転送のための受け側を接続するそれである。通信チャネルはリアルタイムチャネルでありえた。ここで、チャネルがデータを得ながら、チャネルは送信機から受け側までデータを移動する、または、通信チャネルは、送信機から受け側までいくつかまたはデータの全てをその通過に格納する格納チャネルであるかもしれない。後者の実施例は、ディスク記憶装置または他の記憶装置である。その実施例において、送信機、データを生成するプログラムまたはデバイスを、案出できる。そして、記憶装置にデータを送信する。受け側は、記憶装置からデータを読み込むプログラムまたはデバイスである。送信機が記憶装置(記憶装置自体)上へデータを得るために使用するメカニズムそして、受け側が集合的に記憶装置からデータを得るために使用するメカニズムは、チャネルを形成する。それらのメカニズムまたは記憶装置がデータを消失できるという可能性がある場合、それは通信チャネルのデータ消去とみなされるだろう。
【0029】
送信機および受け側がシンボルが消されることができる通信チャネルによって、隔てられるときに、入力ファイルまたはストリームの正確なコピーを送信しなくて、その代わりに、入力ファイルから生成されるデータまたはそれが消去の回復によって、アシストするストリーム(それは、入力ファイルまたはストリームの全部または一部を含むことができた)を伝送しないことが、好ましい。エンコーダとは、そのようなタスクを処理する回路、デバイス、モジュール、または符号セグメントである。1つの符号器の動作を見る方法は符号器が入力シンボルから出力シンボルを生成するということである。ここで、一連の入力シンボル値は入力ファイルまたはストリームのブロックを表す。ストリームおよび値の入力ファイルまたはブロックで、各々の入力シンボルは、このように位置を有する。復号器は、受け側により受信される出力シンボルから入力シンボルを回復する回路、デバイス、モジュールまたはコードセグメントである。マルチステージ符号化において、符号器および復号器は、各々異なる作業を実行しているサブモジュールに、更に分けられる。
【0030】
マルチステージコード体系の実施例において、符号器および復号器はサブモジュールに更に分けられることが可能である。そして、各々が異なる作業を実行する。例えば、実施例によっては、符号器は、本明細書において、スタティック符号器およびダイナミック符号器と称されることを含む。ここで使用しているように、「スタティック符号器」は入力シンボルのセットから多くの冗長シンボルを生成する符号器である。そこにおいて、冗長シンボルの数は符号化の前に決定される。スタティック符号化しているコードの実施例はリード−ソロモン符号、トルネード符号、ハミング符号、低密度パリティチェック(LDPC:Low Density Parity Check)符号、その他を含む。そして、用語スタティック復号器がスタティック符号器によって、符号化されたデータを復号化できる復号器に関連するために本願明細書において、使われる。
【0031】
ここで使用しているように、”ダイナミック符号器”は、入力シンボルのセットから出力シンボルを生成する、可能な出力シンボルの数が入力シンボルの数大きい大きさの程度である。そして、生成される出力シンボルの数が固定する必要はない符号器である。ダイナミック符号器の1つの実施例は、連鎖反応符号器(例えばLuby IおよびLuby IIに記載されている符号器)である。用語”ダイナミック復号器”が、ダイナミック符号器によって、符号化されたデータを復号化できる復号器に関連するために、本願明細書において、使われる。
【0032】
マルチステージ符号化の実施例は、いかなる特定の種類もの入力シンボルに、限られている必要はない。一般的に、入力シンボルのための値は若干の自然数M.のための2Mのシンボルのアルファベットから選ばれるにおいて、この種の場合、入力シンボルは入力ファイルまたはストリームからデータの一連のMビットにより表されることができる。たとえば、Mの値は、出力シンボルのアプリケーション、通信チャネルおよび/またはサイズを使う能力に基づいて、しばしば決定される。加えて、出力シンボルのサイズは、入力シンボルのアプリケーション、チャネルおよび/またはサイズに基づいてしばしば決定される。場合によっては、出力シンボル値および入力シンボル値が同一サイズ(すなわち、ビットの同数により表現されるか同じアルファベットから選択された)である場合、符号化処理は単純化されるかもしれない。この場合それから、出力シンボル値サイズが制限されるときに、入力シンボル値サイズは制限される。たとえば、それは、制限されたサイズのパケットの出力シンボルをすることを要求されることができる。出力シンボルに伴うキーについての若干のデータが受信機でキーを回復するために送信されることになっている場合、出力シンボルは、1つのパケットにおいて、キーについて出力シンボル値およびデータに対応するのに十分好ましくは小さいだろう。
【0033】
一例として、入力ファイルが倍数である、メガバイトファイル、入力ファイルは、各々の入力シンボルを符号化している数千、何百または数バイトだけを有する数千、数万または何十万もの入力シンボルに分解されるかもしれない。別の例としてパケットベースのインターネットチャネルのために、1024バイトのサイズのペイロードを有するパケットは、適当かもしれない(1バイトは、8ビットである)。この例では、各々のパケットが1出力シンボルおよび8バイトの補助情報を含む場合、8128bits((1024−8)*8)の出力シンボルサイズは適当だろう。このように、入力シンボルサイズは、M=(1024−8)*8つまり8128ビットに選ばれることができた。別の例として、若干の衛星システムはMPEGパケット規格を使用する。ここで、各々のパケットのペイロードは188バイトを含む。その実施例において、各々のパケットが1出力を含む場合、シンボルおよび4バイトの補助情報(1472bits((188−4)*8)の出力シンボルサイズ)は適当だろう。このように、入力シンボルサイズは、M=(188−4)*8または1472ビットに選ばれることができた。汎用の通信システムを使用しているマルチステージ符号化において、アプリケーション特有のパラメータ(例えば入力シンボルサイズ(すなわちM個の入力シンボルによって、符号化されるビットの数)は、アプリケーションによって、セットされる変数であるかもしれない。
【0034】
別の例として、可変サイズ転送元パケットを使用させられるストリームのために、各々の転送元パケットが最高でも総計のサイズを転送元パケットわずかに大きくする入力シンボルの整数でおおわれていることができるために、シンボルサイズはむしろ小さいために選ばれるかもしれない。
【0035】
各々の出力シンボルは、値を有する。好ましい一実施例(下で考慮する)において、各々の出力シンボルもそれとともにその”キー”と呼ばれている識別子を結びつける。望ましくは、各々の出力シンボルのキーは、受け側が1出力シンボルと他の出力シンボルを区別できるために、受け側で容易に測定されることができる。望ましくは、出力シンボルのキーは、他の全ての出力シンボルのキーとは別である。前の技術で述べられるキーイングのさまざまな形式が、ある。たとえば、Luby Iは、本本発明の実施例において、使用されることができるキーイングのさまざまな形式を描く。
【0036】
データ消去または受け側が必ずしも転送が開始するときに受信を開始しなくて、終えないところの予想および端がある所で、マルチステージ符号化は特に役立つ。後の状態は本明細書において、”データ不完全性”と呼ぶ。消去イベントとみなす事項において、Luby I.に記載されている連鎖反応符号化の利点で多くのマルチステージ符号、マルチステージ出力シンボルは情報付加的であるので、任意の適当な数のパケットは所望の精度に入力ファイルまたはストリームを回復するために用いることがありえる。マルチステージ符号化が使われるときに、これらの状況は通信プロセスに悪影響を与えない。−その理由は、次のことにある。マルチステージ符号化により生成される出力シンボルは情報付加的である。たとえば、100のパケットが突然のノイズを引き起こしているデータ消去のために消失する場合、パケットがありえる余分の百は消されたパケットの損失を交換するために爆発の後、上向いた。それが送信し始めるときに受信機が送信機に同調を行わなかったので何千ものパケットが消失する場合、受信機は、そうすることができたちょうど受信転送の他のいかなる期間からも何千ものそれらのパケット、または他のものから送信機。マルチステージ符号化については、受信機は特定のいずれもパケットの中でセットしたピックアップを強いられないので、それは1台の送信機から若干のパケットを受信することができて、送信機を他のものに切り替えることができて、若干のパケットを消失することができて、始めまたは既知の転送の端を見のがすことができて、まだストリームの入力ファイルまたはブロックを回復できる。受信機送信機間で協調のない転送を接続して、残す能力は、通信プロセスを単純化するのに役に立つ。
【0037】
いくつかの実施形態では、ファイルまたはストリームを使用しているマルチステージ符号化を送信することは入力シンボルをストリームの入力ファイルまたはブロックから生成するか、形成するかまたは抽出することを含むことができる。そして、冗長シンボルを計算する。そして、一つ以上の出力シンボル(各々の出力シンボルがそれぞれに他の全ての出力シンボルのそのキーに基づいて生成されるところ)に入力および冗長シンボルを符号化して、チャネルの上の一つ以上の受け側に出力シンボルを送信する。加えて、実施例によっては、入力ファイルのコピーまたはストリームを使用しているマルチステージ符号化のブロックを受信する(そして、回復すること)ことは、より多くのデータストリームのうちの1つから出力シンボルの若干のセットまたはサブセットを受信して、受信された出力シンボルの値およびキーから入力シンボルを復号化することを含むことができる。
【0038】
本願明細書において、記載されていながら、消去が符号化する適切なFECは、上記のあげられた問題点を克服するために用いることができて、用途をマルチメディアの同報およびマルチキャスティングシステムおよびサービスを含む多くのフィールドで見つける。この後に「マルチステージ連鎖反応コード」と称するFEC消去コードは、この種のシステムおよびサービスの電流および将来の必要条件の多数を満たす特性を有する。
【0039】
いかなるパケット損失状況のためにも、そして、いかなる関連したサイズものソースファイルまたはいかなる関連したレートものストリームの交付のために、マルチステージ連鎖反応コードの若干の基本特性は、以下の通りである。
(a)個々の受信機デバイス”RD”の受信オーバーヘッドは、最小化される、
(b)ソースファイルをいかなる数のRDに配信するために必要なトータル転送時間を、最小化できる
(c)転送スケジュールの適切な選択については、いかなる数のRDに対する配信されたストリームの品質は、入力シンボルの数と関連して送られる出力シンボルの数のために最大にされることができる。
RDは、携帯デバイスであるかもしれないか、車両に埋め込まれているかもしれないか、持ち歩けるかもしれない(すなわち、使用中のときに、移動可能であるが、一般的に動いていない)かまたは、場所に固定するかもしれない。
【0040】
復号化のために必要とされる作業メモリの量は低くて、上記の特性をまだ提供できる。そして、必要とされる計算の量は符号化する。そして、復号化する最小限である。この文書において、我々は、提供するシンプルな、そして、容易なマルチステージ連鎖反応コードの若干のバリエーションの説明をインプリメントする。
【0041】
マルチステージ連鎖反応コードは、ファウンテンコードである。すなわち、必要に応じてパケットを符号化することがありえるさらに同じだけはオンザフライを生成した。そして、各々がストリームのソースファイルまたはブロックを回復することに等しく役立つユニークな符号化しているシンボルを含んだ。多くの効果が、FECコードの他方式に対してファウンテンコードを使用することにある。1つの効果は、パケット損失状況およびRD有効性に関係なく、ファウンテンコードが各々のRDがストリームのソースファイルまたはブロックを回復するために受信することを必要とするパケットを符号化することの数を最小化するということである。これは、厳しいパケット損失状況の下でさえ真で、移動機RDが、たとえば、断続的につけられるだけである時であるまたは長いファイルダウンロードセッションにわたって利用できる。
【0042】
有利さが能力である他のものは、転送が進行中である間、どれくらいの符号化しているパケットにオンザフライを生成するべきかについて決定になされて、必要に応じて多くの符号化しているパケットとして正確に生成する。これは、たとえば応答がそれらがストリームのソースファイルかブロックを回復するのに十分な符号化しているパケットを受信したか否か、指示しているRDからある場合、役立つことがありえる。期待されてパケット損失状況が厳しくないときに、転送は、早く終了されることができる。パケット損失状況がより厳しい期待されるまたはRDは、期待されてしばしば利用できない、転送は、継ぎ目なく延長されることができる。
【0043】
他の効果は、逆多重化の能力である。逆多重化は、RDがストリームのソースファイルまたはブロックを回復するために独立送信機で生成されるパケットを符号化して受信されて組み合わさることが可能である時である。逆多重化の1つの実用は、異なる送信機からパケットを符号化することを受信することに関して、下に記載されている。
【0044】
将来のパケット損失、RD有効性およびアプリケーション状況は、予測するのが難しい、予測不可能な状況の下で適切に作用するために可能に、柔軟なとしてあるFECソリューションを選択することは重要である。マルチステージ連鎖反応コードは、FECコードの他方式によって、マッチしない柔軟度を提供する。
【0045】
本発明の態様は、次に図に関して記載されている。
【0046】
<システムの概要>
図1は、マルチステージ符号化を使用する通信システム100のブロック図である。通信システム100において、入力ファイル101または入力ストリーム105が、入力シンボル生成器110に対し提供される。入力シンボル生成器110は入力ファイルまたはストリームから1個以上の一連の入力シンボル(IS(0),IS(1),IS(2),...)を生成し、各々の入力シンボルは値および位置(図1の括弧内の整数として示す)を有する。上述したように、各々の入力シンボルが入力ファイルまたはストリームのMビットを符号化するため、入力シンボルの可能な値(すなわちアルファベット)は一般的に2M個のシンボルからなるアルファベットである。Mの値は通常使用する通信システム100により決定される、しかし、Mが使用する用途が多様でありえるため汎用システムでは入力シンボル生成器110のためのシンボルサイズ入力を含むかもしれない。入力シンボル生成器110の出力は、符号器115に提供される。
【0047】
スタティックキー生成器130は、スタティックキーS0,S1...のストリームを生成する。通常、生成されるスタティックキーの数は制限されており特定実施例の符号器115に依存する。スタティックキーの生成は、以降で更に詳細に説明する。ダイナミックキー生成器120は、符号器115により生成される各々の出力シンボルに対するダイナミックキーを生成する。同じ入力ファイルまたはストリームのブロックのダイナミックキーの大部分がユニークとなるように、各々のダイナミックキーは生成される。たとえば、利用可能なキー生成器の実施例がルビーIに記載されている。ダイナミックキー生成器120およびスタティックキー生成器130の出力は、符号器115に提供される。
【0048】
ダイナミックキー生成器120によって提供された各々のキーIから、符号器115は値B(I)の出力シンボルを生成する。そして、入力シンボルは入力シンボル生成器により提供される。符号器115の動作については以下で更に詳細に説明する。各々の出力シンボルの値は対応するキー、1個以上の入力シンボルの何らかの関数、そして、おそらく入力シンボルから計算される冗長シンボルに基づいて生成される。本明細書において、ある特定の出力シンボルのもとである入力シンボルおよび冗長シンボルの集合を、出力シンボルの”関連シンボル”または単にその”付随物(associates)”と呼ぶ。関数(”値関数”)および付随物の選択については、以降で更に詳細に記載されている処理に従って行われる。常にではないが、一般的にはMは入力シンボルおよび出力シンボルに対して同一である、すなわち、それら双方は同じビット数に符号化する。
【0049】
いくつかの実施形態では、符号器115は付随物を選択するために入力シンボルの数Kを使用する。入力がストリーミングファイルである場合のようにKが前もってわかっていない場合には、Kは単に推定値であってもよい。また、符号器115により生成される入力シンボルおよび任意の中間シンボルの配置割り当てに対し、値Kが符号器115により使用されるかもしれない。
【0050】
符号器115は送信モジュール140に出力シンボルを提供する。また、送信モジュール140にはダイナミックキー生成器120から各々の出力シンボルのキーが提供される。送信モジュール140は出力シンボルを送信する。そして、送信モジュール140は使用するキーイング方法に従い送信された出力シンボルのキーに関する何らかのデータをチャネル145を介して受信モジュール150に送信するかもしれない。チャネル145は消去チャネルであるとみなされるが、それは通信システム100が適切に動作するための必要条件ではない。送信モジュール140はチャネル145を介して出力シンボルおよび対応するキーに関する必要データを送信するのに適合しており、受信モジュール150はチャネル145を介してシンボルと対応するキーに関する何らかのデータを受信するのに適合していれば、モジュール140、145および150は、適切なハードウェア構成機器、ソフトウェア構成要素、物理メディアまたはそれのいかなる組合せによっても実現可能である。Kの値は、付随物を決定するために用られる場合、チャネル145を介して送信されるか、または、定刻より早い持間に符号器115および復号器155に対して予めセットしておいてもよい。
【0051】
前述したように、チャネル145はリアルタイムチャネル(例えば、インターネット、テレビ送信機からテレビ受信機への放送リンク経路、あるポイントから他のポイントへの電話接続)で有り得る他、チャネル145は格納チャネル(例えば、CD−ROM、ディスク装置、ウェブサイト等)でも有り得る。さらに、チャネル145はリアルタイムチャネルおよび格納チャネルの組合せでも有り得る。例えば、ある人がパソコンから電話回線を介してインターネットサービスプロバイダー(ISP)まで入力ファイルを送信する際に形成されるチャネルのように、入力ファイルはウェブサーバに格納され、インターネットを介して受け側に送信される。
【0052】
チャネル145が消去チャネルであると仮定されるので、システム100において、受信モジュール150から出力される出力シンボルと送信モジュール140に入力される出力シンボルとは1対1の対応があると仮定することは出来ない。実際、チャネル145がパケット網を含む場合、2個以上のパケットの相対的順序がチャネル145を通過中に保存されると仮定することさえ出来ないかもしれない。従って、出力シンボルのキーは上述の1以上のキーイング方法を利用して決定され、必ずしも受信モジュール150から出力シンボルが出力される順序で決定されるというわけではない。
【0053】
受信モジュール150は復号器155に出力シンボルを提供し、受信モジュール150が受信するこれらの出力シンボルのキーに関するデータはダイナミックキー再生器160に提供される。ダイナミックキー再生器160は、受信された出力シンボルのためのダイナミックキーを再生し、復号器155にダイナミックキーを提供する。スタティックキー生成器163は、スタティックキーS0,S1...を再生し、復号器155に提供する。スタティックキー生成器は、符号化および復号化プロセスにおいて双方で使用する乱数発生器135にアクセスする。同一の挙動となるようにするため、この種のデバイスにより乱数が生成される場合同一の物理装置へのアクセスであってもよいし、同一の乱数生成アルゴリズムへのアクセスであってもよい。復号器155は、ダイナミックキー再生器160およびスタティックキー生成器163により提供される出力シンボルに対応するキーを使用し、入力シンボル(IS(0),IS(1),IS(2),...)を回復する。復号器155は、入力ファイル101または入力ストリーム105のコピー170を生成する入力ファイル再構築器165に回復した入力シンボルを提供する。
【0054】
<符号器>
図2は、図1に示される符号器115の一特定実施例のブロック図である。符号器115は、スタティック符号器210、ダイナミック符号器220、および、冗長計算機230を備えている。スタティック符号器210は、以下の入力を受信する。
【0055】
a)入力シンボル生成器110により提供され入力シンボルバッファ205に格納されたオリジナルの入力シンボルIS(0),IS(1),IS(2),...,IS(K−1)
b)オリジナルの入力シンボルの数K
c)スタティックキー生成器130により提供されるスタティックキーS0,S1,...
d)冗長シンボルの数R
スタティック符号器205は、これらの入力を受信するとすぐに、後述するようにR個の冗長シンボルRE(0),RE(1),...,RE(R−1)を計算する。常にではないが一般的に冗長シンボルは入力シンボルと同じサイズである。一特定実施例において、スタティック符号器210により生成される冗長シンボルは、入力シンボルバッファ205に格納される。入力シンボルバッファ205は論理的なものでもよい。すなわち、ファイルまたはストリームのブロックは1つの場所に物理的に格納してもよいし、入力シンボルのシンボルバッファ205内の位置は、ただ単にオリジナルのファイルまたはストリームのブロック内のシンボルの位置の名称変更でもよい。
【0056】
ダイナミック符号器は、入力シンボルおよび冗長シンボルを受信し下記に詳述されているように出力シンボルを生成する。冗長シンボルが入力シンボルバッファ205に格納される一実施例においては、ダイナミック符号器220は入力シンボルバッファ205から入力シンボルおよび冗長シンボルを受信する。
【0057】
冗長計算機230は、入力シンボルの数Kから冗長シンボルの数Rを計算する。この計算は下記に詳述されている。
【0058】
<スタティック符号器の概要>
スタティック符号器210の一般動作は図3および図4に示される。図3は、スタティック符号化の方法一実施例の簡略フローチャートを例示している。ステップ305において、変数j(どれだけ冗長シンボルが生成されたかについての情報を保持する)はゼロにセットされる。そして、ステップ310では、第1の冗長シンボルRE(0)は少なくともいくつかの入力シンボルIS(0),...,IS(K−1)の関数F0として計算される。それから、ステップ315で、変数jはインクリメントされる。次に、ステップ320で、冗長シンボルの全てが生成されたか(すなわち、jがR−1より大きいか?)どうかが検査される。もしYesの場合はフローは終了する。そうでなければ、フローは、ステップ325へ進む。ステップ325において、RE(j)は入力シンボルIS(0),...,IS(K−1)および以前に生成された冗長シンボルRE(0),...,RE(j−1)の関数Fjとして計算される。ここで、Fjは入力シンボルの何れかまたは冗長シンボルの何れかに依存する関数である必要はない。ステップ315、320および325はR個の冗長シンボルが計算されるまで繰り返される。
【0059】
再度図1および図2を参照すると、実施例によっては、スタティック符号器210はスタティックキー生成器130から1個以上のスタティックキーS0,S1...を受信する。これらの実施例では、スタティック符号器210は、いくつかまたは全部の関数F0,F1,...Fj−1を決定するためにスタティックキーを使用する。たとえば、スタティックキーS0は関数F0を決定するために利用可能であり、スタティックキーS1は関数F1を決定するために利用可能である。もしくは、1個以上のスタティックキーS0,S1,...を関数F0を決定するために利用可能であり、1個以上のスタティックキーS0,S1,...を関数F1を決定するために利用可能である。他の実施態様では、スタティックキーは必要でなく、スタティックキー生成器130は必要でない。
【0060】
次に図2および図3を参照すると、実施例によっては、スタティック符号器210により生成される冗長シンボルは、入力シンボルバッファ205に格納されてもよい。図4は、スタティック符号器210の一実施例の動作の簡略図である。特に、スタティック符号器210は、入力シンボルバッファ205から受信した入力シンボルIS(0),...,IS(K−1),RE(0),...,RE(j−1)の関数Fjとして、冗長シンボルRE(j)を生成する。そして、入力シンボルバッファ205の中に戻し格納する。関数F0,F1,...,FR−1の正確な形式は、特定の用途に依存する。常ではないが一般的には、関数F0,F1,...,FR−1は、関連するいくつかあるいは全ての引数の排他的論理和を含んでいる。上述の通り、これらの関数は実際に図1のスタティックキー生成器130により生成されるスタティックキーを使用するかもしれないし使用しないかもしれない。たとえば、後述する一特定実施例では、最初のいくつかの関数はハミング符号を実装し、スタティックキーS0,S1,...を全く使用しない。また、残りの関数は低密度パリティチェック符号を実装し、スタティックキーを明示的に利用する。
【0061】
<マルチステージ符号器の概要>
再度図2を参照すると、ダイナミック符号器220は、入力シンボルIS(0),...,IS(K−1)および冗長シンボルRE(0),...,RE(R−1)および各々の出力シンボルのキーIを受信する。この集合はオリジナルの入力シンボルおよび冗長シンボルを含んでおり、今後”ダイナミック入力シンボル”の集合と呼ぶ。図5はダイナミック符号器の一実施例の簡略ブロック図であり、ウェイトセレクタ510、アソシエータ515、値関数セレクタ520および計算機525を含む。図5に示すように、K+R個のダイナミック入力シンボルはダイナミックシンボルバッファ505に格納される。実質的に、ダイナミック符号器500は図6に例示される動作を実行する。すなわち、選択された入力シンボルの何らかの値関数として出力シンボル値B(I)を生成する。
【0062】
図7は、本発明によるスタティック符号器の一特定実施例の簡略ブロック図である。スタティック符号器600は、パラメータ計算機605、ハミング符号器610および低密度パリティチェック(LDPC)符号器620を備えている。ハミング符号器610は、入力シンボルバッファ625からの入力シンボルIS(0),...,IS(K−1)、入力シンボルの数K、および、パラメータDを受信するように接続される。そして、ハミング符号器610は、ハミング符号に従ってD+1個の冗長シンボルHA(0),HA(1),...,HA(D)を生成する。
【0063】
図8は、図7に示されるスタティック符号器を使用する本発明の一実施例の動作を例示する。
【0064】
図9は、パラメータ計算機(例えば図7のパラメータ計算機605)の一実施例の簡略フローチャートであり、上述のパラメータDおよびEを計算する。最初に、ステップ705で、パラメータDは1に初期化される。そして、ステップ710で、2D−D−1がK未満かどうかが判定される。NOの場合フローはステップ730へ進む。YESの場合フローはステップ720へ進み、パラメータDはインクリメントされる。それから、フローはステップ710へ進む。Dが決定されると、ステップ730で、R−D−1としてパラメータEが算出される。
【0065】
図10は本発明の一実施例に従うこのような符号器の簡略フローチャートであり以下に説明する。最初に、ステップ805で、変数iはゼロに初期化される。変数iは、すでに生成される冗長シンボルの数の情報を得続ける。ステップ810において、数tは、K/2以上の最も少ない奇数の整数として算出される。ステップ815において、値P1,P2,...,Ptは、K、tおよびスタティックキーSに基づいて生成される。値P1,P2,...,Ptは、冗長シンボルを生成するために用いる入力シンボルの位置を指示する。ある特定の実施例では、図5のアソシエータ515のようなアソシエータは、PI,P2,...,Ptを生成するために用いる。特に、W(I)個の入力として値tは提供され、K+R個の入力として値Kは提供される。そして、スタティックキーSiはキーIの入力として提供される。tの多くの異なる値が類似した符号化効果を得る点に留意する必要がある。このように、この特定の選択は1つの例にすぎない。ステップ820において、RE(i)の値は、値IS(PI),IS(P2),...,IS(Pt)のXORとして計算される。ステップ825において、変数iは次の冗長シンボルの計算を準備するために1だけインクリメントされる。そして、ステップ830で、全ての冗長シンボルが計算されたかどうかは判定される。そうでない場合には、フローはステップ815に戻る。
【0066】
図11は、本発明による復号器の簡略ブロック図を例示している図である。復号器900は、たとえば、図1の復号器155を実装するために用いられる。
【0067】
復号器900は、ダイナミック復号器905とスタティック復号器910を備えている。ダイナミック復号器905により回復される入力シンボルおよび冗長シンボルは、回復バッファ915に格納される。ダイナミック復号化終了後、スタティック復号器910は、ダイナミック復号器905により回復されない入力シンボルがあれば回復を試みる。特に、スタティック復号器910は回復バッファ915からの入力シンボルと冗長シンボルを受信する。
【0068】
図12は、本発明による復号化のための方法の簡略フローチャートを例示している図である。ステップ1005において、Q個の出力シンボルは、復号器により受信される。Qの値は、入力シンボルの数および使用するある特定のダイナミック符号器に依存する。Qの値は、また、復号器が入力シンボルを回復できる所望の精度に依存する。たとえば、復号器が高確率を有する入力シンボルの全てを回復できることが要求される場合、Qは入力シンボルの数より大きな数として選択される。特に、用途によっては、入力シンボルの数が大きいときに、Qは3%未満程度オリジナル入力シンボルの数より大きい。ほかの応用において、入力シンボルの数が少ないときに、Qは少なくとも10%程度入力シンボルの数より大きい。具体的には、Qは入力シンボルの数Kに数Aを加えた値として選ばれることができる。ここで、Aは復号器が高確率を有する入力シンボルの全てを再生させることができることを確保するために選ばれる。数Aの決定は、下で更に詳細に記載されている。復号器は入力シンボル(時々または常に)の全てを復号化することができないことを許容する場合、QはK+A未満でありえるかKに等しくありえるかさらにK未満でありえる。明確に、全体のコード体系の1つの目的はしばしば可能な限り数Qを減少させることである、その一方で、所望の精度に関して復号プロセスの成功に関する良好な見込みに基づく保証を維持する。
【0069】
ステップ1010において、ダイナミック復号器905は受信したQ個出力シンボルから入力シンボルおよび冗長シンボルを再生する。ステップ1005および1010が実質的に並行して実行されることができることは、よく理解されている。たとえば、ダイナミック復号器905は、復号器がQ個の出力シンボルを受信する前に入力シンボルおよび冗長シンボルを再生させ始めることができる。 ダイナミック復号器905がQ個の出力シンボルを処理したあと、入力シンボルが所望の精度に回復されたかどうかは判定される。所望の精度は、たとえば、全ての入力シンボルまたは全てより少ないいくつか、パーセンテージ、その他である。YESの場合、フローは終わる。NOの場合は、フローはステップ1020へ進む。ステップ1020において、スタティック復号器910は、ダイナミック復号器905が回復することができなかった入力シンボルの回復を試みる。スタティック符号器910がダイナミック復号器905により回復された入力シンボルおよび冗長シンボルを処理した後フローが終了する。
【0070】
図13は、本発明による復号化のための方法の他の実施例を示している簡略フローチャートである。この実施例は、図11に関して記載されたものと類似していて、共通のステップ1005、1010、1015および1025を含む。しかし、ステップ1025の後、フローはステップ1030へ進む。そこにおいて、入力シンボルが所望の精度に回復されたかどうかは判定される。YESの場合、フローは終了する。NOの場合、フローはステップ1035へ進む。ステップ1035において、一つ以上の付加的な出力シンボルが受信される。それから、フローはステップ1010へ進行する。その結果、ダイナミック復号器905および/またはスタティック復号器910は残留する非回復の入力シンボルを回復することを試みることができる。
【0071】
図14は、本発明による復号化のための方法のさらにもう一つの実施例を示している簡略フローチャートである。ステップ1055において、出力シンボルは復号器により受信される。そして、ステップ1060で、ダイナミック復号器905は受信された出力シンボルから入力シンボルおよび冗長シンボルを再生させる。それから、ステップ1065で、ダイナミック復号化が終了すべきかどうかが判定される。この判定は、処理した出力シンボルの数、回復した入力シンボルの数、付加的な入力シンボルが回復されている現在の速度、出力シンボルの処理に費やした時間は、その他の一つ以上に基づいて行われる。
【0072】
ステップ1065において、ダイナミック復号化を終了しないと決定される場合、フローはステップ1055へ進行する。しかし、ステップ1065において、ダイナミック復号化を終了すると決定される場合、フローはステップ1070へ進む。ステップ1070において、入力シンボルが所望の精度に回復されたかどうかが判定される。YESである場合、フローは終了する。NOの場合は、フローはステップ1075へ進む。ステップ1075において、スタティック復号器910は、ダイナミック復号器905が回復することができなかった入力シンボルの回復を試みる。スタティック符号器910が、ダイナミック符号器905によって回復された入力シンボルおよび冗長シンボルを処理した後、フローは終了する。
【0073】
図15は、本発明によるダイナミック復号器の一実施例を示す。ダイナミック復号器1100は、図5に示されるダイナミック符号器500と類似した構成要素を含む。復号器1100は、Luby IおよびLuby IIに記載されている連鎖反応復号器の実施例と類似している。ダイナミック復号器1100は、ウェイトセレクタ510と、アソシエータ515と、値関数セレクタ520と、出力シンボルバッファ1105と、短縮器1115と、回復器1120と、回復バッファ1125とを備える。
【0074】
図16は、スタティック復号器の一実施例の簡略ブロック図を示している。データが図7に関して記載されているスタティック符号器などによって、符号化されるときに、この実施例を用いることができる。スタティック復号器1200は、LDPC復号器1205とハミング復号器1210を備えている。LDPC復号器1205は回復バッファ1215から入力シンボルおよび冗長シンボルを受信する。そして、ダイナミック復号器の復号ステップの後、回復バッファ1215の未回復のシンボルの回復を試みる。いくつかの実施形態では、回復バッファ1215は、回復バッファ1125(図15)である。
【0075】
LDPC復号器およびハミング復号器の多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。1つの特定実施例において、ハミング復号器は、ガウス消去アルゴリズムを使用して行う。ガウス消去アルゴリズムの多くのバリエーションは、当業者にとって周知で、本発明による各種実施形態において、使用されることができる。
【0076】
<バリエーション>
上述のマルチステージ連鎖反応コードはシステマティックコードではない。すなわち、ソースブロックのオリジナルソースシンボルの全てが必ずしも送信される符号化シンボルであるというわけではない。しかしながら、システマチックFECコードは、ファイルダウンロードシステムまたはサービスに役立ち、ストリーミングシステムまたはサービスにとって非常に重要である。下記の実施に示すように、変更を加えられたコードは、システマチックで、まだファウンテンコードおよび他の記載されている特性を維持するよう実行されることができる。
【0077】
それがマルチステージ符号を使用した補足的なサービスのバラエティが設計者に容易である一つの理由は、それが送信機の中の関連性の無いソースファイルまたはストリームを復元するために多数の送信機から符号化シンボルを受信して組み合わせることができるということである。唯一の必要条件は、送信機がそれらがコードのパケットを符号化する際に送信する符号化シンボルを生成するためのキーと異なるセットを使用するということである。これを達成する方法は、この種の各々の送信機によって、異なる範囲のキー空間を使用するか、または、各々の送信機でランダムにキーを生成することを含む。
【0078】
例えば、この能力の用途の中で、ファイルダウンロードサービスに対する補足的なサービスがマルチステージ連鎖反応符号を許容するならば、ファイルダウンロードセッションからソースファイルを復元するのに十分な符号化しているパケットを受信せず、送信機から付加的な符号化コードが送信されるよう要求する(例えば、HTTPセッションを経て)。送信機はソースファイルから符号化シンボルを生成し送信し(例えばHTTPを使用して)、ソースファイルを回復するため全てのこれらの符号化シンボルはファイルダウンロードセッションから受信されるそれと混合されうる。このアプローチを使用することによって、異なる送信機同士が送信機間の調整を必要とせずインクリメント式ソースファイル配信サービスを提供でき、その各々個々の受信機は各々のソースファイルを回復するための符号化パケットを最低限の数だけ受信すればよい。
【0079】
<マルチステージコードのさまざまなステージの実現例>
<FEC方式定義>
これらの技術を使用しているパケットは、ヘッダ情報(例えばソースブロック番号(SBN)(パケットの範囲内の符号化シンボルが関係するソースブロックのための16ビット整数識別子)および符号化シンボルID(ESI)(パケットの範囲内の符号化シンボルのための16ビット整数識別子)を含んでいる4オクテットのFECペイロードID)により表されるかもしれない。ソースブロック番号および符号化シンボルIDの1つの適切な解釈は、下記のセクションBにおいて定義される。FECオブジェクト転送情報は、FEC符号化ID、転送長(F)およびパラメータT(下において、定められるZ、NおよびA)を含みうる。パラメータTおよびZは16ビット符号なし整数である、NおよびAは8ビット符号なし整数である。
【0080】
MBMS前方誤り訂正のFEC符号化方式は、下記のセクションにおいて定義される。それは2つの異なるFECペイロードIDフォーマット(1つはFEC転送元パケットのため、もう1つはFEC修復パケットのため)を定義する。しかし、非システマチック符号のバリエーションもまた可能である。
【0081】
転送元FECペイロードIDは、ソースブロック番号(SBN)(パケットの範囲内の符号化シンボルが関係するソースブロックのための16ビット整数識別子)および符号化シンボルID(ESI)(パケットの範囲内の符号化シンボルのための16ビット整数識別子)を含むかもしれない。その一方で、修復FECペイロードIDは、ソースブロック番号(SBN)(パケットの範囲内の修復シンボルが関係するソースブロックのための16ビット整数識別子)、符号化シンボルID(ESI)(パケットの範囲内の修復シンボルのための16ビット整数識別子)およびソースブロック長(SBL)(16ビット:ソースブロック内のソースシンボルの数を表す)を含みうる。ソースブロック番号、符号化シンボルIDおよびソースブロック長の解釈は、以下定義される。
【0082】
FECオブジェクト転送情報は、FEC符号化ID、最大ソースブロック長(シンボル単位)およびシンボルサイズ(バイト単位)を含みうる。シンボルサイズおよび最大ソースブロック長は、シンボルサイズ(T)(16ビット:符号化シンボルのサイズを表す(バイト単位)および)最大ソースブロック長(16ビット:ソースブロックの最大長を表す(シンボル単位))の4オクテット部を含み得る。
【0083】
下記のセクションは、システマチックMSCR前方誤り訂正符号およびMBMSおよび他の用途へのその適用を指定する。MSCRはファウンテンコードである。すなわち、符号器はブロックのソースシンボルからオンザフライで必要なだけ多く数ののソースシンボルを生成することが出来る。復号器は、ソースシンボルの数よりわずかに多いいかなる符号化シンボルのセットからもソースブロックを回復可能である。この文書に記載されている符号はシステマティック符号であり、修復シンボルと同じ数だけオリジナルソースシンボルは受信機に送信機から変形されずに送信される。
【0084】
<B.1 定義、記号および略号>
<B.1.1 定義>
本明細書において以下の用語および定義を適用する。
【0085】
ソースブロック:MSCR符号化の目的で一緒に考慮されるK個のソースシンボルのブロック。
【0086】
ソースシンボル:符号化プロセスの間使用されるデータの最小単位。ソースブロック内の全てのソースシンボルは同一のサイズである。
【0087】
符号化シンボル:データパケットに含まれるシンボル。符号化シンボルは、ソースシンボルおよび修復シンボルを含む。ソースブロックから生成される修復シンボルは、ソースブロックのソースシンボルと同様に同一のサイズである。
【0088】
システマティックコード:ソースブロックのため送信される符号化シンボルの一部としてソースシンボルが含まれるコード。
【0089】
修復シンボル:ソースブロックのため送信されるソースシンボルでない符号化シンボル。修復シンボルはソースシンボルに基づいて生成される。
【0090】
中間シンボル:逆の符号化プロセスを使用してソースシンボルから生成されるシンボル。修復シンボルは中間シンボルから直接生成される。符号化シンボルは中間シンボルを含まない。すなわち、中間シンボルはデータパケットに含まれない。
【0091】
シンボル:データの単位。バイトで表現されるサイズはシンボルサイズとして既知である。
【0092】
符号化シンボルグループ:一緒に送られる符号化シンボルグループ。すなわち、同一パケット内においてソースシンボルに対する関係が単一の符号化シンボルIDに由来するもの。
【0093】
符号化シンボルID:符号化シンボルグループのシンボルとソースシンボルの関係を定義する情報。
【0094】
符号化パケット:符号化シンボルを含むデータパケット
サブブロック:ソースブロックはサブブロックに分解され、それぞれは作業メモリ内において復号化されるために十分に小さい。K個のソースシンボルを含むソースブロックに対して、各々のサブブロックはK個のサブシンボルを含み、ソースブロックの各シンボルは各サブブロックの1個のサブシンボルから構成される。
【0095】
サブシンボル:シンボルの一部。各ソースシンボルは、ソースブロック内のサブブロックである多くのサブシンボルから構成される。
【0096】
ソースパケット:ソースシンボルを含むデータパケット。
【0097】
修復パケット:修復シンボルを含むデータパケット。
【0098】
<B.1.2 記号>
i、j、x、h、a、b、d、v、m:自然数を表す
ceil(x):x以上である最小の自然数を表す
choose(i,j):繰り返しのないi個のオブジェクトの中からj個のオブジェクトを選択する方法の数を表す
floor(x):x以下である最大の自然数を表す
i%j:iモジュロjを表す
X^Y:等しい長さのビット列XおよびYに対し、XとYとのビット毎の排他論理和を表す
A:シンボル配列パラメータを表し、シンボルおよびサブシンボルのサイズはAの倍数に制限される
AT:Aの転置行列を表す
A−1:Aの逆行列を表す
K:1個のソースブロック内にあるシンボルの数を表す
KMAX:1つのソースブロック内にあるソースシンボルの最大数を表し、8192に設定される
L:1つのソースブロックに対する予め符号化されるシンボルの数を表す
S:1つのソースブロックに対するLDPCシンボルの数を表す
H:1つのソースブロックに対するハーフシンボルの数を表す
C:中間シンボル(C[0],C[1],C[2],...,C[L−1])の配列を表す
C’:ソースシンボル(C’[0],C’[1],C’[2],...,C’[K−1])の配列を表す
X:負でない整数値を表す
V0、V1:4バイト整数の2つの配列、V0[0],V0[1],...,V0[255]およびV1[0],V1[1],...,V1[255]を表す
Rand[X、i、m]:擬似乱数発生器である
Deg[v]:度数発生器である
LTEnc[K、C、(d、a、b)]:LT符号化シンボル生成器である
Trip[K、X]:トリプル生成関数である
G:符号化シンボル群内のシンボルの数である
N:ソースブロック内のサブブロックの数である
T:シンボルサイズ(バイト)であり、ソースブロックがサブブロックに区切られているとき、T=T’・Nである
T’:サブシンボルサイズ(バイト)であり、ソースブロックがサブブロックに区切られていないときT’は関連しない
F:ファイルダウンロードのときのファイルサイズ(バイト)である
I:サブブロックサイズ(バイト)である
P:ファイルダウンロードの場合、各パケットのペイロードサイズ(バイト)であり、ファイルダウンロード転送パラメータの推奨導出に使用される。ストリーミングの場合、各修復パケットのペイロードサイズ(バイト)であり、ストリーミング転送パラメータの推奨導出に使用される
Q:Q=65521、すなわち、Qは216未満の最大の素数である
Z:ファイルダウンロードのときのソースブロックの数である
J(K):Kに関連するシステマチックインデックスである
G:任意の生成行列を表す
IS:SxSの恒等行列を表す
0SxH:SxHの零行列を表す
<B.1.3 略号>
本明細書において以下の略号を用いる。
【0099】
ESI(Encoding Symbol ID):符号化シンボルID
LDPC(Low Density Parity Check):低密度パリティチェック
LT(Luby Transform):ルビー変換
SBN(Source Block Number):ソースブロック番号
SBL(Source Block Length):ソースブロック長(シンボル単位)
<B.2 概要>
これら各々のアプリケーションに特定されるMSCR前方誤り訂正符号は、MBMSファイル配信およびMBMSストリーミングアプリケーションの双方に適用可能である。MSCR符号の態様は、本明細書のセクションB.3およびB.4で述べる。
【0100】
システマチックMSCR符号の構成要素は、セクションB.5に記載されている基本的な符号器である。第1に、中間シンボルについての知識がソースシンボルを復元するのに十分であるように、どのようにオリジナルソースシンボルから一組の中間シンボルの値を導き出すかが記述される。第2に、符号器は、各々多数の中間シンボルの排他的論理和である修復シンボルを作成する。符号化シンボルは、ソースおよび修復シンボルの組合せである。中間シンボル従ってまたソースシンボルはいかなる十分に大きい符号化シンボル群からも回復可能な方法で修復シンボルは生成される。
【0101】
この文書は、システマチックMSCRコード符号器を定義する。多くの考えられる復号化アルゴリズムが利用可能である。効率的な復号化アルゴリズムは、セクションB.6において提供される。
【0102】
中間のおよび修復シンボルの組立の一部分は、セクションB.5に記載されている擬似乱数発生器に基づく。この生成器は、送信機および受信機の双方で利用できる512の乱数の固定セットに基づく。数の実施例のセットは、付録B.1において提供される。
【0103】
最後に、ソースシンボルからの中間シンボルの組立は、”システマチックインデックス”により支配される。システマチックインデックスの値の実施例セットは、4個のソースシンボルからKMAX=8192個のソースシンボルまでのソースブロックサイズのためものが付録Aに示される。
【0104】
<B.3 ファイルダウンロード>
<B.3.1 ソースブロック構築>
<B.3.1.1 全般>
MSCR符号器をソースファイルに適用するために、ファイルはZ(≧1)個のブロック(ソースブロックとして知られる)としてに分解されうる。MSCR符号器は、それぞれに各々のソースブロックに適用される。各々のソースブロックは一意な整数ソースブロック番号(SBN)であり、第1のソースブロックのSBNは0、第2は1などである。各々のソースブロックは各々のサイズがTバイトのソースシンボルの数(K)に分割される。各々のソースシンボルは一意の整数符号化シンボル識別子(ESI)であり、ソースブロックの第1のソースシンボルのESIは0、第2は1などである。
【0105】
K個のソースシンボルを有する各々のソースブロックはN(≧1)個のサブブロックに分けられる。それは作業メモリにおいて復号化されるのに十分小さい。各々のサブブロックは、サイズT’のK個のサブシンボルに区分される。
【0106】
ファイルの各々のソースブロックの値に対してKの値が必ずしも同一であるというわけではない点、および、ソースブロックの各々のサブブロックに対してT’が必ずしもの同一であるというわけではない点に注意する。しかしながら、ファイルの全てのソースブロックに対してシンボルサイズTは同一であり、ソースブロックのあらゆるサブブロックに対してシンボル数Kは同一である。ファイルの、ソースブロックおよびサブブロックへの正確な分割は、後述のB.3.1.2に記載されている。
【0107】
図17は二次元行列に配置されたソースブロックの例を示す。ここで、各々のエントリはT’バイトのサブシンボルであり、各々の列はサブブロックであり、各々の行はソースシンボルである。この例では、T’の値は、あらゆるサブブロックに対して同一である。各々のサブシンボルのエントリに示される数は、ソースブロック中でのオリジナルの順番を示している。たとえば、Kの番号をつけられたサブシンボルは、ソースブロックのT’・KからT’・(K+1)−1個までのバイトを含む。そして、ソースシンボルiは、各々のサブブロックからの第iのサブシンボルの連結であり、i、K+i、2・K+i、...、(N−1)・K+iの番号をつけられたソースブロックのサブシンボルに対応する。
【0108】
<B.3.1.2 ソースブロックとサブブロック分割>
ソースブロックおよびサブブロックの構築は、F、A、T、Z、Nの5個のパラメータおよび関数Partition[]に基づいて決定される。5個のパラメータは次のように定義される。
【0109】
F:ファイルサイズ(バイト)である
A:シンボル配列パラメータ(バイト)である
T:シンボルサイズ(バイト)であり、必ずAの倍数となる
Z:ソースブロックの数である
N:各ソースブロック内のサブブロックの数である
これらのパラメータは、ceil(ceil(F/T)/Z)=<KMAXとなるようにセットされる。これらのパラメータ導出の推奨値がセクションB.3.4において提供される。
【0110】
関数Partition[]は一対の整数(I、J)を入力として4整数(IL、IS、JL、JS)を導出する。具体的には、Partition[I、J]の値は、4整数のシーケンス(IL、IS、JL、JS)であり、IL、=ceil(I/J)、IS=Floor(I/J)、JL=I−IS・J、JS=J−JLである。Partition[]は、サイズIのブロックをほぼ等しいJのブロックに分割するパラメータを導出する。具体的には、長さILのJL個のブロックと長さISのJS個のブロックである。
【0111】
ソースファイルは、以下の通りにソースブロックおよびサブブロックに仕切られる。
【0112】
Kt=ceil(F/T)のとき
(KL、KS、ZL、ZS)=Partition[Kt,Z]
(TL、TS、NL、NS)=Partition[T/A,N]
それから、ファイルは、Z=ZL+ZS個の隣接するソースブロックに仕切られ、最初のZL個のソースブロックは各々KL・Tバイトであり、残りのZS個のソースブロックは各々KS・Tバイトである。
【0113】
Kt・T>Fのとき、符号化に用いられ、最後のシンボルは最後のKt・T−Fの部分をパディングされる。
【0114】
次に、各々のソースブロックはN=NL+NS個の隣接するサブブロックに仕切られ、最初のNL個のサブブロックは各々TL・AのサイズのK個の隣接するサブシンボルを含み、残りのNS個のサブブロックは各々TS・AのサイズのK個の隣接するサブシンボルを含む。シンボル配列パラメータAは、サブシンボルが常にAバイトの倍数であることを確保する。
【0115】
最後に、ソースブロックの第m番目のシンボルは、各々N個のサブブロックから第m番目のサブシンボルの連結を含む。
【0116】
<B.3.2 符号化パケット構築>
<B.3.2.1 全般>
各々の符号化パケットは、以下の情報を含む。
【0117】
ソースブロック番号(SBN)
符号化シンボルID(ESI)
符号化シンボル
各々のソースブロックは、他と独立してそれぞれに符号化される。ソースブロックはゼロから連続的に番号をつけられる。
【0118】
0からK−1の符号化シンボルID値は、ソースシンボルを識別する。Kからの符号化シンボルは前方へ修復シンボルを識別する。
【0119】
<B.3.2.2 符号化パケット構築>
各々の符号化パケットは、好ましくは、完全なソースシンボル(ソースパケット)あるいは完全な修復シンボル(修復パケット)のいずれかを含む。パケットは、同じソースブロックから任意数のシンボルを含むことができる。オブジェクトを符号化しているFECにパケットの最後のシンボルがパディングバイトを含む場合、これらのバイトはパケットに含まなくてもよい。さもないと、全シンボルだけは含まれる。
【0120】
各々のソースパケットにより転送される符号化シンボルID、Xは、そのパケットにおいて保持される最初のソースシンボルの符号化シンボルIDである。パケットの次のソースシンボルは順序付けられた符号化シンボルID、X+1からX+G−1を有し、ここで、Gはパケット内のシンボルの数である。
【0121】
同様に、修復パケットに格納された符号化シンボルID、Xは、修復パケットの最初の修復シンボルの符号化シンボルIDであり、パケットの次の修復シンボルは順序付けられた符号化シンボルID、X+1からX+G−1を有し、ここで、Gはパケット内のシンボルの数である。
【0122】
ここで、受信機が修復パケットの合計数を知ることは必要でない点に注意する。修復シンボルのG個の修復シンボルトリプル(d[0],a[0],b[0]),...,(d[G−1],a[G−1],b[G−1])は、ESI Xを有する修復パケット内に配置され、以降のB.5.3.4において定義されるトリプル生成器を使用して計算される。
【0123】
各々のi=0,...,G−1に対して、
(d[i],a[i],b[i])=Trip[K,X+i]
ESI Xを有する修復パケットに配置されるG個の修復シンボルは、セクションB.5.3にて説明したように、中間シンボルCおよびLT符号器LTenc[K,C,(d[i],a[i],b[i])]を用い修復シンボルトリプルに基づいて計算される。
【0124】
<B.3.3 転送>
このセクションは、ファイル送出のためのMSCR前方誤り訂正を利用しているMSCR符号器/復号器およびいかなる転送プロトコルの間でも情報交換を記載する。
【0125】
ファイル送出のためのMSCR符号器および復号器は、転送プロトコルから以下の情報を必要とする。バイト単位のファイルサイズ、F、シンボル配列パラメータ、A、シンボルサイズ(T)(バイト単位でAの倍数である)、ソースブロックの数、Z、各々のソースブロックのサブブロックの数、N。ファイル配信のためのMSCR符号器は、加えて、符号化されるファイルがFバイトであることを必要とする。
【0126】
MSCR符号器は、各々のパケットのために、SBN、ESIおよび符号化シンボルを含む符号化パケット情報を転送プロトコルに出力する。転送プロトコルは透過的にMSCR復号器にこの情報を伝える。
【0127】
<B.3.4 推奨パラメータ(情報提供)>
<B.3.4.1 パラメータ決定アルゴリズム>
このセクションは4つの転送パラメータA,T,ZおよびNの導出の推奨値を提供する。
【0128】
この推奨値は以下の入力パラメータに基づいている。
【0129】
F:ファイルサイズ(バイト)
W:サブブロックサイズ目標(バイト)
P:最大のパケットペイロードサイズ(バイト)、Aの倍数であると仮定される
A:シンボル配列ファクタ(バイト)
KMAX:ソースブロック当たりのソースシンボルの最大数
KMIN:ソースブロック当たりのシンボルの最小目標数
GMAX:パケット当たりのシンボルの最大目標数
上記の入力に基づいて、転送パラメータT、ZおよびNは、以下の通りに算出される。
【0130】
G=min{ceil(P・KMIN/F),P/A,GMAX}−パケット当たりの平均シンボル数
T=floor(P/(A・G))・A
Kt=ceil(F/T)−ファイル内の総シンボル数
Z=ceil(Kt/KMAX)
N=min{ceil(ceil(Kt/Z)・T/W),T/A}
GおよびNの値は上述のように導出され下限として考慮される。例えば、2の累乗に近似した数などに、これらの値を増やすことは、有利となり得る。特に、上記のアルゴリズムはシンボルサイズTが最大パケットサイズPを区分することを保証しない。そして、正確にPのサイズのパケットが使用可能とはならない。その代わりに、Gは、P/Aを区分する値として選択される場合、シンボルサイズTはPの因子である。そして、サイズPのパケットが使うことができる。
【0131】
入力パラメータ、W、A、KMINおよびGMAXの推奨された設定は、以下の通りである。
【0132】
W=256KB A=4 KMIN=1024 GMAX=10
<B.3.4.2 例>
上記のアルゴリズムは図18に示すように結果として転送パラメータに導く。そして、W、A、KMINおよびGMAXおよびP=512のための推奨値となる。
【0133】
<B.4 ストリーミング>
<B.4.1 ソースブロック構築>
この文書において定義したように、ソースブロックは転送プロトコルによって組み立てられる。そして、システマチックMSCR前方誤り訂正符号を利用する。ソースブロックの組立および修復シンボルの組立に使われるシンボルサイズTは転送プロトコルにより提供される。いかなるソースブロックについてもソースシンボルの数が最高でもKMAXであるために、パラメータTがセットされるかもしれない。
【0134】
推奨されたパラメータは、セクションB.4.4に示される。
【0135】
<B.4.2 符号化パケット構築>
B.4.3にて説明するように各々の修復パケットは、SBN、ESI、SBLおよび修復シンボルを含む。修復パケットの中で含まれる修復シンボルの数は、パケット長から計算される。修復パケットに入れられるESI値および修復シンボルを生成するために用いる修復シンボルのトリプルは、セクションB.3.2.2にて説明したように、計算される。
【0136】
<B.4.3 転送>
このセクションは、MSCR符号器/復号器間の情報交換を記載し、いかなる転送プロトコルもストリーミングのためのMSCR前方誤り訂正を利用する。トリーミングのためのMSCR符号器は、各々のソースブロックのための転送プロトコルから、以下の情報を使用するかもしれない。シンボルサイズT(バイト)、ソースブロックのシンボル数K、ソースブロック番号(SBN)、符号化されるソースシンボル(K・Tバイト)。MSCR符号器は、各々の修復パケットのために、SBN、ESI、SBLおよび修復シンボルを含んでいるパケット情報を符号化することに関する転送プロトコルを出力する。転送プロトコルは透過的にMSCR復号器にこの情報を伝えるかもしれない。
【0137】
<B.4.4 推奨パラメータ>
<B.4.4.1 パラメータ決定アルゴリズム>
このセクションは、を転送パラメータTの導出の推奨値を提供する。この推奨値は、以下の入力パラメータに基づく。
【0138】
B:最大ソースブロックサイズ(バイト)
P:最大のパケットペイロードサイズ(バイト)、Aの倍数であると仮定される
A:シンボル配列ファクタ(バイト)
KMAX:ソースブロック当たりのソースシンボルの最大数
KMIN:ソースブロック当たりのシンボルの最小目標数
GMAX:修復パケット当たりのシンボルの最大目標数
これらの入力上の必要条件は、ceil(B/P)=<KMAXである。上記の入力に基づいて、転送パラメータTは、以下の通りに算出される。
【0139】
G=min{ceil(P・KMIN/B),P/A、GMAX}−パケット当たりのシンボル平均数
T=floor(P/(A・G))・A
上で導出されるTの値は、使用するTの実効値のガイドと思われなければならない。そのTをPに区分することは有利でもある。または、フルサイズ修復シンボルが消失する転送元パケット(ソースブロックのソースシンボルの最大数KMAXを超えない限り)終了後部分的なソースシンボルを回復するために用いるときに、より小さいTの値が消耗を最小化することはセットに有利でもよい。P、全ての転送元パケットが同一サイズである場合、それがそのようにTをそれに選ぶために有利で修復パケットPの中で、さらに、例えば、Tで優れたものは、転送元パケット径分布に依存できる実際のペイロードサイズは、Tの倍数であって、各々の転送元パケットがソースブロックにおいて、占めるバイト数(数バイトできる限りより大きく、または)に等しい。
【0140】
入力パラメータ、A、KMINおよびGMAXの推奨された設定は、以下の通りである。
【0141】
A=4 KMIN=1024 GMAX=10
<B.4.4.2 例>
上記のアルゴリズムは図19に示すように結果として転送パラメータに導く。そして、A、KおよびGMAXおよびP=512のための推奨値となる。
【0142】
<B.5 システマチックMSCR符号化器>
<B.5.1 符号化の概要>
システマチックMSCR符号器は、K個のソースシンボルを含むソースブロックから修復シンボルを生成するために用いる。シンボルは、符号化および復号プロセスの基本的なデータ単位である。各々のソースブロック(サブブロック)のために、全てのシンボル(サブシンボル)は、同一サイズである。符号化および復号化のためのシンボル(サブシンボル)に実行される動作は、排他的論理和演算である。
【0143】
C’[0],...,C’[K−1]はK個のソースシンボルを示す
C[0],...,C[L−1]はL個の中間シンボルを示す
符号化の第一段階は、K個のソースシンボルから中間シンボルの数(L>K)を生成することである。このステップにおいて、K転送元トリプル(d[0],a[0],b[0]),...,(d[K−1],a[K−1],b[K−1])はセクションB.5.4.4にて説明したように、Trip[]を使用して生成したK個のソーストリプルは、Kソースシンボルを伴い、逆の符号化プロセスを使用しているソースシンボルからL個の中間シンボルC[0],...,C[L−1]を決定するために用いる。この処理は、MSCR復号プロセスにより認識されることができる。
【0144】
特定の”所与の符号化関係”は、L個の中間シンボルの中で保持しなければならない。セクションB.5.2は、これらの関係および中間シンボルがソースシンボルから生成される方法を記載する。
【0145】
一旦中間シンボルが生成されると、修復シンボルは作成される。そして、単一のデータパケットにグループ、一つ以上の修復シンボルは配置される。各々の修復シンボルグループは、符号化シンボルID(ESI)および符号化シンボルの数(G)と関係している。ESIは、生成するために用いるトリプルの3整数(d、a、b)(各々の修復シンボル間のセクションB.5.4.4.にて説明したように、Trip[]を使用する)。これは、セクションB.3およびセクションB.5.4に記載されている生成器を使用し、B.4にて説明したように実行される。各々の(d,a,b)−トリプルはセクションB.5.4.3.に記載されているLTEnc[K,C[0],...,C[L−1],(d,a,b)]生成器を使用している中間シンボルから、対応する修復シンボルを生成するために用いる。
【0146】
<B.5.2 符号化の第1段階:中間シンボル生成>
<B.5.2.1 全般>
第1の符号化しているステップは、ソースシンボルC’[0],...,C’[K−1]からL個の中間シンボルC[0],...,C[L−1]を生成する予め行われる符号化ステップである。中間シンボルは、制約条件の2つのセットによって、独自に定義される。
【0147】
1.中間シンボルは、ソースシンボルのトリプルの一組によって、ソースシンボルに関連がある。セクションB.5.4.4にて説明したように、ソースシンボルトリプルの生成には、セクション5.2.2で定義されるを使用しているTrip[]を使用する。
【0148】
2.一組の予め行われる符号化関係は、それ自身を中間シンボルの中で保持する。これらは、セクションB.5.2.3において定義される。
【0149】
L個の中間シンボルの生成は、セクション5.2.4において定義される。
【0150】
<B.5.2.2 ソースシンボルのトリプル>
K個のソースシンボルのそれぞれは、0<i<Kのトリプル(d[i],a[i],b[i])に関係している。ソースシンボルトリプルは、セクションB.5.4.4で定義されるトリプル生成器を使用して決定される。
【0151】
0<i<Kを満たすそれぞれのiについて、
(d[i],a[i],b[i])=Trip[K,i]
<B.5.2.3 符号化前の関連付け>
L個の中間シンボルの間の予めの符号化関係は、第1のK個の中間シンボルに関して最後のL−K個の中間シンボルを表すことにより定義される。
【0152】
最後のL−K個の中間シンボルC[K],...,C[L−1]はS LDPCシンボルを含む、そして、SおよびHの値がそうであるHハーフシンボルは後述するようにKから決定される。そのため、L=K+S+Hである。
【0153】
X:X・(X−1)=2・Kとなる最小の自然数である
S:S>=ceil(0.01・K)+Xとなる最小の素数整数
H:(H、ceil(H/2))>=K+Sとなる最小の整数である
H’:ceil(H/2)L=K+S+H
C[0]、...、C[K−1] 最初のK個の中間シンボルを示す
C[K]、...、C[K+S−1] S LDPCシンボルを示す(ゼロに初期化される)
C[K+S]、...、C[L−1] H ハーフシンボルを示す(ゼロに初期化される)
S LDPCシンボルは、以下の処理の最後でC[K],...,C[K+S−1]の値であるように定義される。
【0154】
i=0、...、K−1 について以下を実行
a=1+(floor(i/S)%(S−1))
b=i%S
C[K+b]=C[K+b]^C[i]
b=(b+a)%S
C[K+b]=C[K+b]^C[i]
b=(b+a)%S
C[K+b]=C[K+b]^C[i]
H ハ−フシンボルは以下のように定義される。
【0155】
g[i]=i^(floor(i/2)) 全ての自然数iについて
注:g[i]はグレイシーケンスであり、各々の要素は前のものと単一のビット位置において異なる。
【0156】
g[j,k]は、jth要素を示す、j=0,1,2,...要二進表示で素が正確にk個のゼロでないビットを備えているg[i]の部分系列を示す。
【0157】
それから、ハーフシンボルは、以下の処理の後、C[K+S],...,C[L−1]の値として定義される。
【0158】
h=0,...,H−1 について以下を実行
j=0,...,K+S−1 について以下を実行
もしg[j,H’]のビットhが1の場合、C[h+K+S]=C[h+K+S]^C[j]
<B.5.2.4 中間シンボル>
<B.5.2.4.1 定義>
所与のK個のソースシンボルC’[0],C’[1],...,C’[K−1]についてL個の中間シンボルC[0],C[1],...,C[L−1]は以下を満たすように独自に定義されるシンボル値である。
【0159】
1.K個のソースシンボルC’[0],C’[1],...,C’[K−1]は、K個の制約条件がある
C’[i]≡LTEnc[K,(C[0],...,C[L−1]),(d[i],a[i],b[i])] 0<i<Kである全てのiについて
2.B.5.2.3で予め定義された符号化関係を満足するL個の中間シンボルC[0],C[1],...,C[L−1]
<B.5.2.4.2 中間シンボルの計算>
このサブセクションは、B.5.2.4.1の制約条件を満たしているL中間シンボルC[0],C[1],...,C[L−1]の算出方法を記載する。 K個の入力シンボルからN個の出力シンボルを生成するコードのための生成行列GはGF(2)の上のNxKマトリックスである。各々の列は出力シンボルのうちの1つに対応する。そして、入力シンボルのうちの1つおよびithとなる出力シンボルのところに対する各々の行は行が列のゼロでないエントリを含むそれらの入力シンボルの合計に等しい。
【0160】
そして、L個の中間シンボルは、以下の通りに算出されることができる。
【0161】
C:L個の中間シンボル(C[0],C[1],...,C[L−1])の列ベクトルを示す
D:S+Hのゼロシンボルを含む列ベクトルで、K個のソースシンボルC’[0],C’[1],...,C’[K−1]が続く
よって、上記の制約条件はGF(2)の上のLxLマトリックスと定義され、Aは
A・C=D である。
【0162】
マトリックスAは、以下の通りに組み立てられることが可能である。
【0163】
GLDPCは、DPCシンボルのSxKの生成行列である、そのため、
GLDPC・(C[0],...,C[K−1])T=(C[K],...,C[K+S−1])T
GHalfは、ハーフシンボルのH×(K+S)の生成行列である、そのため、
GHalf・(C[0],...,C[S+K−1])T=(C[K+S],...,C[K+S+H−1])T
IS:SxSの恒等行列を表す
IH:HxHの恒等行列を表す
0SxH:SxHの零行列を表す
GLT:LT符号器により生成される符号化シンボルのK×Lの生成行列である
そのため、
GLT・(C[0],...,C[L−1])T=(C’[0],C’[1],...,C’[K−1])T
すなわち、GLTi,j=1 もしC[i]は排他的論理和の生成したシンボルを含むだけなら
LTEnc[K,(C[0],...,C[L−1]),(d[i],a[i],b[i])]
そして、
Aの最初のS列は、GLDPC|IS|ZS×Hに等しい。
【0164】
Aの次のH列は、GHalf|IHに等しい。
【0165】
Aの残りのK列は、GLTに等しい。
【0166】
マトリックスAは、図20に示される。中間シンボルはそれから算出されることができる。
【0167】
C=A−1・D
いかなるKにおいても行列Aは最大ランクを有し、逆変換可能であるようにソーストリプルは生成される。この算出は、L個の中間シンボルC[0],C[1],...,C[L−1]を作成するためにMSCR復号プロセスをK個のソースシンボルC’[0],C’[1],...,C’[K−1]に適用することにより認識されることができる。
【0168】
ソースシンボルから効率的に中間シンボルを生成するために、それのような効率的な復号器実施態様がセクションB.6に記載されて用いられるというそれは、推奨される。ソースシンボルトリプルは、そのアルゴリズムを使用しているソースシンボルの効率的な復号化を容易にするように設計されている。
【0169】
<B.5.3 符号化の第2段階:LT符号化>
第二の符号化ステップにおいて、ESI Xを有する修復シンボルは、生成器を適用することによって、セクションB.3.2.2およびB.4.2に従ってトリプル(d,a,b)=Trip[K,X]を使用しているL個の中間シンボルC[0],C[1],...,C[L−1]にセクションB.5.4において定義されるLTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]を生成する。
【0170】
<B.5.4 生成器>
<B.5.4.1 乱数生成器>
乱数発生器Rand[X,m]は以下の通りに定められる。ここで、Xは非負整数である、iは非負整数である。そして、mは自然数である。そして、生成される値は0とm−1との間の整数である。V0およびV1を各々256のエントリの配列であるようにさせる。ここで、各々のエントリは4バイトの符号なし整数である。これらの配列は、セクションB.7において提供される。そして、
Rand[X,i,m]=(V0[(X+i)%256]^V1[(floor(X/256)+i)%256])%m
<B.5.4.2 度数生成器>
度数生成器[v]は以下の通りに定められる。vは少なくとも0で220=1048576より小さい整数である。
【0171】
図21において、 f[j−1]≦v<f[j]となるインデックスjを探す
Deg[v]=d[j]
<B.5.4.3 LT符号化シンボル生成器>
符号化シンボル生成器LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]は、以下の入力をする。
【0172】
Kは、ソースブロック(サブブロック)のためのソースシンボル(またはサブシンボル)の数である。LはセクションB.5.2にて説明したように、Kに由来するようにさせる。そして、L’L以上の最小の素数とする。
【0173】
(C[0],C[1],...,C[L−1])はセクションB.5.2にて説明したように、生成されるL個の中間シンボル(サブシンボル)である。
【0174】
(d、a、b)はセクションB.5.3.4で定義されたトリプル生成器使用して決定されるソーストリプルである。ここで、dは符号化シンボル度数を示す整数であり、aは1からL’−1に含まれる整数であり、bは0からL’−1に含まれる整数である。
【0175】
以下のアルゴリズムにより、符号化シンボル生成器は1つの符号化シンボルを出力として生成する。
【0176】
b≧Lにあいだ、b=(b+a)%L’を実行する
LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]=C[b]
j=1,...,min(d−1,L−1) について以下を実行する。
【0177】
b=(b+a)%L’
LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]=LTEnc[K,(C[0],C[1],...,C[L−1]),(d,a,b)]^C[b]
<B.5.4.4 トリプル生成器>
トリプル生成器Trip[K,X]には次のものが入力される。
【0178】
K:ソースシンボル数
X:符号化シンボルID
LはB.5.2で説明したようにKに基づいて決定される
L’はL以上の最小の素数である
Q=65521、216未満の最大の素数
J(K)は、付録Aにおいて定義される、Kと関係するシステマチックデックスである。
【0179】
トリプル生成器の出力はトリプル(d、a、b)であり、以下の通りに決定される。
【0180】
1. A=(53591+J(K)・997)%Q
2. B=10267・(J(K)+1)%Q
3. Y=(B+X・A)%Q
4. v=Rand[Y,0,220]
5. d=Deg[v]
6. a=1+Rand[y,1,L’−1]
7. b=Rand[Y,2,L’]
<B.6 FEC復号化の実現例>
<B.6.1 全般>
このセクションは、この仕様に記載されているMSCRコードのための効率的な復号化アルゴリズムを記載する。各々がシンボルを符号化することを受信した注は、中間シンボルの間に均衡化の値と思われることができる。これらの連立方程式および中間シンボルの間の周知の予め符号化関係から、連立方程式を解くためのいかなるアルゴリズムも、中間シンボルおよびそれ故、ソースシンボルをうまく復号化できる。しかしながら、選択されるアルゴリズムは、復号化の計算効率に、大きな影響を及ぼす。
【0181】
<B.6.2 ソースブロックの復号化>
<B.6.2.1 全般>
復号器がそれが復号化するためにそうであるソースブロックの構造を知っていると仮定される。そして、シンボルサイズTでありK個のシンボルをソースブロックに含む。
【0182】
セクションB.5に記載されているアルゴリズムから、MSCR復号器は合計数L=K+S+Hを算出できる予め符号化シンボルの中で、そして、それらが復号化されるソースブロックからどのように生成されたかについて決定する。この説明において、復号化されるソースブロックのための受信された符号化しているシンボルが復号器に通過すると仮定される。さらに、この種の各々の符号化しているシンボルのために、数および排他論理和が符号化しているシンボルに等しい中間シンボルのセットが復号器に通過すると仮定される。ソースシンボルの場合、セクションB.5.2.2に記載されているソースシンボルトリプルは、各々のソースシンボルを与えるために概説する中間シンボルの数およびセットを指示する。
【0183】
N≧Kをソースブロックのための受信された符号化しているシンボルの数であるようにさせる。そして、M=S+H+N。LビットマトリックスAによる以下のMは、復号化されるソースブロックのための復号器に通過する情報に由来できる。CはL個の中間シンボルの列ベクトルであって、Dは受信機(MシンボルでぶりのS+HがLDPCおよびHalfシンボル(これらは、それ自身LDPCおよびHalfシンボルおよびLDPCおよびHalfシンボルのためでない検査符号である)に対応する0値を有するシンボルである)にとって公知の値を有するMシンボルの列ベクトルであるようにさせるようにさせる。そして、Mシンボルの残りのNは、ソースブロックのための受信された符号化しているシンボルである。それから、AはA・C=Dを満たすビットマトリックスである。ここで、GF[2]の上のマトリックス乗算を示す。一旦Cが複号化されるとインデックスjに対応する中間シンボルが符号化のインデックスiに対応するLDPC、Halfまたは符号化しているシンボルにXOR演算される場合A[i,j]=1である。または、インデックスiがLDPCまたはHalfシンボルおよびインデックスに対応する場合、jは同じLDPCまたはHalfシンボルに対応する。他の全てのiおよびjについて、A[i,j]=0である。
【0184】
ソースブロックが周知のAからCを復号化して、等しい復号化およびそれがそうであるDはそのCをクリアする復号化できるのときかつそのときに限ってGF[2]はLである。シンボルがシンボルが各々の行方不明のソースシンボルを得るためにXOR演算される中間シンボルの数およびセットを決定するためにトリプルにするソースを使用して得られることが可能である転送元をはずす。
【0185】
復号化Cの第一段階は、復号化予定を形成することになっている。このステップにおいて、L恒等行列によるLに、Aは、ガウス消去(列動作および列および行の並べ替えを使用する)を用いて、そして、M−L列を放棄した後に変換される。復号化予定はガウス消去処理の間、列動作および列および行の並べ替えのシーケンスを含んで、Aに、そして、DからのCの復号化が復号化予定の化成と並行して場所に持っていくことができるD.以外に依存するだけである、または、復号化が復号化予定に基づいてその後起こることができる。
【0186】
復号化予定およびCの復号化の間の相関関係は、以下の通りである。まず最初にc[0]=0,c[1]= 1...,c[L−1]=L−1およびd[0]=0,d[1]=1...,d[M−1]=M−1である。
【0187】
復号化予定において、そしてD[d[i]]がXOR演算される復号プロセスシンボルにおいて、−Aの各々の時間列iは、列iにXOR演算されるシンボルD[d[i’]]。
【0188】
復号化予定において、そしてd[i]の値が値と交換される復号プロセスで−各々の時間列iは、列iと交換されるd[i’]。
【0189】
復号化予定において、そしてc[j]の値がc[j’]の値と交換した復号プロセスで−各々の時間行jは、行jと交換される。
【0190】
この通信から、ソースブロックの復号化のシンボルの排他的論理和の合計数がガウス消去の段数動作(交換でない)であることは、明らかである。Aがガウス消去の後のLの恒等行列による。そして、最後のM−Lを廃棄した後のLであるので、LシンボルD[d[0]],D[d[1]],...,D[d[L−1]]がLシンボルC[c[0]],C[c[1]],...,C[c[L−1]]の値であることは復号化に成功したことは明白である。
【0191】
復号化が成功しているのであるにせよ、ガウス消去が復号化予定には関係がない形式に実行される命令。しかしながら、復号化の速度は、重く、ガウス消去が実行されるオーダーに依存する。(さらにまた、Aのまばらな表現を維持することは重要である。但し、これはここで記載されていない)。このセクションの剰余は、比較的効率的であるガウス消去が実行されることができた命令を記載する。
【0192】
<B.6.2.2 第1段階>
マトリックスAが下位行列に仕切られて、概念的にあるガウス消去の第一段階。部分行列サイズは、0まで初期化される非負整数iおよびuによって、パラメータで表される。Aのサブマトリックスは、以下の通りである
(1) Iが第1のi列および第1のi行の交差によって、定めた部分行列。これは、位相における各々のステップ終了後の恒等行列である。
(2) 第1のi列および第1のi行以外はおよび最後のu行の交差により定義される部分行列。この部分行列の全てのエントリは、ゼロである。
(3) 第1のi行および第1のi列以外はの交差により定義される部分行列。この部分行列の全てのエントリは、ゼロである。
(4) 全ての列および最後のu行の交差により定義される部分行列U。
(5) 部分行列Vは、第1のi行以外はおよび最後のu行および第1のi列以外はの交差によって、形をなした。
【0193】
図22は第一段階の初めのA.対各々のステップの= A.の下位行列を例示する、列のAは選択される。Vの構造により定義される以下のグラフが、Aのどの列が選択されるか決定する際に使われる。Vを横切る行は、グラフのノードである。そして、正確にVの2つのものを有する列は、2つのものの位置の2つの行(ノード)を接続するグラフの端である。グラフのノード/刃の各対間の経路があるように、このグラフのA構成要素はノード(行)および端(列)の最大セットである。構成要素のサイズは、構成要素のノード数(行)である。
【0194】
Lステップが、最高でも第一段階にある。i+u=Lとき、位相は、うまく終える、すなわちVおよびVより上の全ゼロ部分行列が消える。そして、Aは、含むI、下記の全0部分行列I、そして、U.失敗していくつかでVの前のステップがそこで消える場合、失敗を復号化する際の位相両端部は、そのステップで選択をするVのゼロでない列でない。各々のステップにおいて、Aの列は、以下の通りに選択される。Vの全てのエントリがゼロである場合、列は選択されない、そして、復号化は失敗する。Aの少なくとも一つの列が正確にVのrものを有するように、rを最小限の整数であるようにさせる。r#2がそれから正確に最小限のオリジナル程度を有するVのrものを有する列を全てのこの種の列から選択する場合。r=2がそれから正確にXにより定義されるグラフの最大サイズ構成要素の一部であるVの2つのものを有する列を選択する場合、列がこのステップで選択されたあと、選ばれた列がVと交差する第一系列であるために、Vを横切るAの第一系列は選ばれた列と交換される。選ばれた列のrのうちの1つがVの第一塔に現れるために、そして、残りのr−1がVの最後の行に現れるために、Vを横切るものの中のAの行は追加注文される。
【0195】
それから、選ばれた列は、Vの第一のものを有する選ばれた列の下で、Aの全ての他の列にXOR演算される。
【0196】
最後に、iは1時までに増加する。そして、uはr−1まで増加する。そして、それはステップを完了する。
【0197】
<B.6.2.3 第2段階>
部分行列Uは、更に仕切られる最初のi列、Uupper、そして、残りのM−i列、Ulower。ガウス消去は、その順位がu(復号化失敗)より少ないと決定するかuがこぐ第一が恒等行列(第二段階の成功)であるマトリックスにそれを変換するために、Ulower上の第二段階において、実行される。u恒等行列Iuによって、このuを呼ぶ。Ulower−Iuと交差するAのM−L列は、放棄される。この位相の後、Aは、L列およびL行を有する。
【0198】
<B.6.2.4 第3段階>
第二段階の後、L恒等行列によって、LにAを変換し終わるために外へゼロに合うことを必要とするAの唯一の部分は、Uupperである。部分行列Uupperの段数iは、通常、Uupperの行uの数非常に大きい。効率的にUupper(以下の前計算マトリックスU)からのゼロまで』、第三段階およびそれからUのIuに基づいて計算される』が、Uupperからゼロまで第四段階において、使われる。Iuの列が仕切られるuは、各々(u/8)グループの8本の列を張る。それから、8本の列の各群のために、8本の列の全てのゼロ以外の組合せは、計算される。そして、28に結果としてなる−1=255列(これは、28−8−1=247により行われることができるグループにつき列の中で排他論理和は、ハミング重みの組合せからIuに現れるものがある必要を行わないことを−計算する)。このように、結果として生じる前計算マトリックスUは、.255がこぐceil(u/8)およびu行を有する。そのUを強調する形式的にマトリックスAの一部でない、しかし、Uupper−B.からのゼロに対する第四段階の使われる。
<B.6.2.5 第4段階>
列にAの各々の第1のi列間の、Uupperの8つの行エントリのセットが全てゼロ(そして前計算マトリックスUの列)でない場合この列のUupper部分行列の8つの行の各群間の、8つの行のパターンがそうであるマッチは、列にXOR演算した。このようにねらいを定める排他的論理和を犠牲にした列のそれらの8つの行が、Uの中で外に。
【0199】
この位相AがL恒等行列および完全な復号化によるLであったあと、予定はうまく形成された。それから、シンボルを符号化して公知の対応する復号化を含んでいる排他的論理和は、復号化予定に基づいて中間シンボルを回復するために完成していることがありえる。
【0200】
全てのソースシンボルと関連するトリプルは、B.5.2.2に従って計算される。受信されたソースシンボルのためのトリプルが、復号化において、使われる。行方不明のソースシンボルのためのトリプルは、どの中間シンボルが行方不明のソースシンボルを回復するためにXOR演算されることを必要とするかについて決定するために用いる。
【0201】
<マルチステージ符号の特性>
上述の多くの例において、入出力シンボルはビットの同数のための98を符号化する。そして、各々の出力シンボルは1つのパケット(完全に受信されるか完全に消失する輸送の装置であるパケット)において、配置される。いくつかの実施形態では、各々のパケットがいくつかの出力シンボルを含むために、通信システムは変更を加えられる。多くの要因に基づいて、出力シンボル値のサイズは、それから、ストリームのファイルまたはブロックを入力シンボルに最初に分割する際の入力シンボル値のサイズで測定されるサイズに対するセットである。復号プロセスは基本的に不変のままである。但し、次の場合は除く−各々のパケットが受信されながら、出力シンボルは束に到着する。
【0202】
入力シンボルおよび出力シンボルサイズの設定は、通常、ストリームのファイルまたはブロックのサイズおよび出力シンボルが送信されることになっている通信システムにより口述される。たとえば、通信システムが少しのデータを定義済みサイズのパケットまたは他の方法のグループビットに分類する場合、シンボルサイズの計画はパケットまたはグループ化サイズから開始される。そこから、デザイナーはどれくらいの出力シンボルが1つのパケットかグループにおいて、担持されるかについて決定する。そして、それは出力シンボルサイズを決定する。説明を簡単にするため、デザイナーは入力シンボルサイズを出力シンボルサイズに等しくたぶん設定する、しかし、入力データが異なる入力シンボルサイズをより便利にする場合、それが使うことができる。
【0203】
上記の符号化プロセスは、ストリームのオリジナルファイルまたはブロックに基づいて出力シンボルを含んでいるパケットのストリームを作成する。ストリームの各々の出力シンボルは他の全ての出力シンボルの中でそれぞれに生成される。そして、作成されることができる出力シンボルの数上の下であるか上の跳躍がない。キーは、各々の出力シンボルを伴う。そのキーおよびストリーム(出力シンボルの値を決定する)の入力ファイルまたはブロックの若干の内容。連続的に生成された出力シンボルは連続的なキーを有する必要はない、そして、それがランダムに好ましい使用目的によってはキーのシーケンスを生成するか、または疑似ランダム的にシーケンスを生成する。
【0204】
マルチステージ復号化は入力シンボル値、それからファイルまたはブロックが、非常に高い確率によって、平均上のK+A出力シンボルからの改装本でありえながら、ストリームのオリジナルファイルかブロックがK等しい大きさの入力シンボルおよび各々の出力シンボル値に分割されることができるかどうかは同じ長さである特性を有する。ここで、AはKと比較して小さい。たとえば、上に導入される重み分布のために、Kが19,681大きい場合、Aの値がa*Kを上回るという確率は多くても10−12である。そして、それはKのいかなる値のためもの多くても10−10である。特定の出力シンボルがランダムであるか疑似乱数のオーダーにおいて、生成されるので、移動中の特定の出力シンボルの損失がランダムとみなされて、そして、若干の小さい相違は、入力ファイルを回復するために必要な出力シンボルまたはブロックの実数値の中に存在する。場合によっては。ここで受信機が出力パケットの一つ以上の転送元からより多くのパケットを集めることができる場合、パケットが十分に全ての入力ファイルまたはブロック、入力ファイルまたはブロックを復号化しないためにそうであるK+Aの特定のコレクションはまだ回収可能である。
【0205】
出力シンボルの数が1の解答により制限されるだけであるので、K+Aより適切に、出力シンボルを、生成できる。たとえば、Iが32ビット数である場合、40億の異なる出力シンボルを、生成できるのに、ストリームのファイルまたはブロックはK=50,000入力シンボルを含むことができた。ある用途では、少数のそれらの40億の出力シンボルだけは生成されることができて、送信されることができる。そして、それはストリームの入力ファイルまたはブロックが可能な出力シンボルの非常に小さい割合いを有する改装本でありえるという近い確信および入力ファイルまたはブロックがK出力シンボル(入力シンボルサイズが出力シンボルサイズと同様であると仮定する)よりわずかに改装本でありえるかなりの確率である。
【0206】
ある用途では、それは、受け入れられてもよいために入力シンボルの全てを復号化するか、または、比較的低い確率によって、以外、入力シンボルの全てを復号化することが可能なことが可能である。この種のアプリケーションにおいて、受信機は、K+A出力シンボルを受信した後に入力シンボルの全てを復号化することを試みるのを止めることができる。または、受信機は、K+A出力シンボル未満の受信の後で出力シンボルを受信するのを止めることができる。ある用途では、受信機は、K以下出力シンボルを受信しさえすることができるだけである。このように、本本発明の若干の実施例で、所望の精度が全ての入力シンボルの完全回復である必要があるというわけではないと理解されることになっている。
【0207】
更に、不完全な回復が受け入れられる若干のアプリケーションで、データが入力シンボルの全てが回復されることができるというわけでないようであるものまたはこの種のその完全回復を符号化されることができること、入力シンボルは、そうする必要とする多くのより多くの出力シンボルの中で受信入力シンボルの数である。この種の符号化は、通常、より計算でない能力を必要として、このように、符号化の計算能力を減少させる受け入れられる方法であってもよい。 上記の図のさまざまな機能ブロックがハードウェアおよび/またはソフトウェアの組合せにより行うことができることが、よく理解されていることになっている。そして、いくつかまたはいくつかのブロックの相関性の全てがそうすることができる特殊作成のそれは、ある合成。同様に、また、本願明細書において、記載されているさまざまな方法がハードウェアおよび/またはソフトウェアの組合せにより行うことができると理解されることになっている。
【0208】
前記説明は、例示的であり限定的でない。本発明の多くのバリエーションは、この開示の再調査に応じて、従来技術において、技術のそれらにとって明らかになる。本発明の範囲は、従って、前記説明に関して決定されてはならない。その代わりに等価物のそれらの完全な範囲とともに、添付の請求の範囲に関して決定されなければならない。
【0209】
<付録A. システマチックインデックスJ(K)の値>
Kの値それぞれについて、ソースシンボルトリプル群(d[0],a[0],b[0]),...,(d[L−1],a[L−1],b[L−1])がL個の中間シンボルが固有となるよう指定可能な特性を有するように、システマチックインデックスJ(K)は設計されている。すなわち、セクションB.5.2.4.2のマトリックスAは最大の階数(ランク)であり逆変換可能な特性を有するように設計されている。以下は、4から8192が含まれるKの値に対応するシステマチックインデックスのリストである。値の順序は、読書の順序と同じである。すなわち、第1行の最初の数値から第1行の最後の数値、そして、第2行の最初の数値に続き、以下同様である。
<付録B.1 テーブルV0の値>
これらの値は、上述の明細書のセクションB.5.4.1で述べられたテーブルV0の値の例示的なセットを示している。各々の成分は10進数表記の32ビット整数である。値の順序は、第1カラムの最上段から第1カラムの最下段、そして、第2カラムの最上段に続き、以下同様である。
<付録B.2 テーブルV1の値>
これらの値は、上述の明細書のセクションB.5.4.1で述べられたテーブルV1の値の例示的なセットを示している。各々の成分は10進数表記の32ビット整数である。値の順序は、第1カラムの最上段から第1カラムの最下段、そして、第2カラムの最上段に続き、以下同様である。
【図面の簡単な説明】
【0210】
【図1】本発明の一実施例に従う通信システムのブロック図である。
【図2】本発明の一実施例に従う符号器のブロック図である。
【図3】本発明の一実施例に従う冗長シンボルを生成する方法の簡略ブロック図である。
【図4】本発明の一実施例に従うスタティック符号器の基本操作の簡略ブロック図である。
【図5】本発明の一実施例に従うダイナミック符号器の簡略ブロック図である。
【図6】本発明の一実施例に従うダイナミック符号器の基本操作の簡略ブロック図である。
【図7】本発明の一実施例に従うスタティック符号器の簡略ブロック図である。
【図8】本発明の一実施例に従うスタティック符号器の基本操作の簡略ブロック図である。
【図9】一特定実施例に従うスタティック符号器の符号化パラメータを算出する方法の簡略図である。
【図10】本発明の他の実施例に従うスタティック符号器の簡略フローチャートである。
【図11】本発明の一実施例に従う復号器の簡略ブロック図である。
【図12】本発明の一実施例に従う復号器の動作の簡略フローチャートである。
【図13】本発明の他の実施例に従う復号器の動作の簡略フローチャートである。
【図14】本発明のさらにもう一つの実施例に従う復号器の動作の簡略フローチャートである。
【図15】本発明の一実施例に従うダイナミック復号器の簡略ブロック図である。
【図16】本発明の一実施例に従うスタティック復号器の簡略ブロック図である。
【図17】サブシンボル写像からのソースシンボルを示す図である。
【図18】さまざまなファイルサイズのファイルのダウンロードパラメータの可能な設定を示す図である。
【図19】さまざまなソースブロックサイズのストリーミングパラメータの可能な設定を示す図である。
【図20】ソースおよび中間シンボルとの関係を示すマトリックスの形式を示す図である。
【図21】度数生成器の度数分布を示す図である。
【図22】復号化に使用可能なマトリックスAの形式を示す図である。
【特許請求の範囲】
【請求項1】
通信チャネルを介して転送元から転送先まで転送するデータを符号化する方法であって、
第1の入力シンボルを使用して算出される第1のスタティックシンボル群が、該第1の入力シンボルとは互いに異なる第2の入力シンボルを使用して算出される第2のスタティックシンボル群と弱い共通の帰属関係を有するように、確定的過程において転送される順序付けられた入力シンボル群から複数の冗長シンボルを生成するステップと、
前記入力シンボルおよび冗長シンボルを含む複合シンボル群から、可能な出力シンボルの数は該複合シンボル群のシンボルの数に比較して非常に大きく、少なくとも1つの出力シンボルは前記複合シンボル群の2以上のシンボルから生成され、任意の所定数(N)の出力シンボルから前記順序付けられた入力シンボル群が所望の精度まで回復可能となる、複数の出力シンボルを生成するステップと、
を含む方法。
【請求項2】
さらに、通信チャネルを介して前記複数の出力シンボルを送信するステップを含む請求項1に記載の方法。
【請求項3】
さらに、前記複数の出力シンボルを記憶媒体に蓄積するステップを含む請求項1に記載の方法。
【請求項4】
前記複数の冗長シンボルは、LDPC符号により生成される請求項1に記載の方法。
【請求項5】
前記所望の精度は、前記入力シンボルの完全回復である請求項1に記載の方法。
【請求項6】
前記所望の精度は、高確率での前記入力シンボルの完全回復である請求項1に記載の方法。
【請求項7】
前記所望の精度は、前記順序付けられた入力シンボル群の入力シンボルの数より少ないG個の入力シンボルの回復である請求項1に記載の方法。
【請求項8】
多くとも、前記順序付けられた入力シンボル群の入力シンボルの数より少ないG個の入力シンボルが任意の個数の出力シンボルからも再生可能である請求項1に記載の方法。
【請求項9】
前記複数の冗長シンボルを生成するステップにおいて、各々の冗長シンボルについて、
分布にしたがってt個の互いに異なる入力シンボルを決定し、
前記t個の互いに異なる入力シンボルのXOR演算として各々の冗長シンボルを計算する
請求項1に記載の方法。
【請求項10】
さらに、通信チャネルを介して前記複数の出力シンボルを送信するステップを含み、前記複数の出力シンボルを生成するステップは該出力シンボルを送信するステップと実質的に並行して実行される請求項1に記載の方法。
【請求項11】
前記複数の冗長シンボルは、スタティックシンボル、ハミングシンボル、および、パディングシンボルを含み、該シンボルの合計個数は素数となるよう選択される請求項1に記載の方法。
【請求項1】
通信チャネルを介して転送元から転送先まで転送するデータを符号化する方法であって、
第1の入力シンボルを使用して算出される第1のスタティックシンボル群が、該第1の入力シンボルとは互いに異なる第2の入力シンボルを使用して算出される第2のスタティックシンボル群と弱い共通の帰属関係を有するように、確定的過程において転送される順序付けられた入力シンボル群から複数の冗長シンボルを生成するステップと、
前記入力シンボルおよび冗長シンボルを含む複合シンボル群から、可能な出力シンボルの数は該複合シンボル群のシンボルの数に比較して非常に大きく、少なくとも1つの出力シンボルは前記複合シンボル群の2以上のシンボルから生成され、任意の所定数(N)の出力シンボルから前記順序付けられた入力シンボル群が所望の精度まで回復可能となる、複数の出力シンボルを生成するステップと、
を含む方法。
【請求項2】
さらに、通信チャネルを介して前記複数の出力シンボルを送信するステップを含む請求項1に記載の方法。
【請求項3】
さらに、前記複数の出力シンボルを記憶媒体に蓄積するステップを含む請求項1に記載の方法。
【請求項4】
前記複数の冗長シンボルは、LDPC符号により生成される請求項1に記載の方法。
【請求項5】
前記所望の精度は、前記入力シンボルの完全回復である請求項1に記載の方法。
【請求項6】
前記所望の精度は、高確率での前記入力シンボルの完全回復である請求項1に記載の方法。
【請求項7】
前記所望の精度は、前記順序付けられた入力シンボル群の入力シンボルの数より少ないG個の入力シンボルの回復である請求項1に記載の方法。
【請求項8】
多くとも、前記順序付けられた入力シンボル群の入力シンボルの数より少ないG個の入力シンボルが任意の個数の出力シンボルからも再生可能である請求項1に記載の方法。
【請求項9】
前記複数の冗長シンボルを生成するステップにおいて、各々の冗長シンボルについて、
分布にしたがってt個の互いに異なる入力シンボルを決定し、
前記t個の互いに異なる入力シンボルのXOR演算として各々の冗長シンボルを計算する
請求項1に記載の方法。
【請求項10】
さらに、通信チャネルを介して前記複数の出力シンボルを送信するステップを含み、前記複数の出力シンボルを生成するステップは該出力シンボルを送信するステップと実質的に並行して実行される請求項1に記載の方法。
【請求項11】
前記複数の冗長シンボルは、スタティックシンボル、ハミングシンボル、および、パディングシンボルを含み、該シンボルの合計個数は素数となるよう選択される請求項1に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【公表番号】特表2007−536834(P2007−536834A)
【公表日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願番号】特願2007−511719(P2007−511719)
【出願日】平成17年5月9日(2005.5.9)
【国際出願番号】PCT/US2005/016334
【国際公開番号】WO2005/112250
【国際公開日】平成17年11月24日(2005.11.24)
【出願人】(501114844)デジタル ファウンテン, インコーポレイテッド (25)
【Fターム(参考)】
【公表日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願日】平成17年5月9日(2005.5.9)
【国際出願番号】PCT/US2005/016334
【国際公開番号】WO2005/112250
【国際公開日】平成17年11月24日(2005.11.24)
【出願人】(501114844)デジタル ファウンテン, インコーポレイテッド (25)
【Fターム(参考)】
[ Back to top ]