噴水コード

符号理論において、ファウンテン符号（レートレス消失訂正符号とも呼ばれる）は、与えられたソースシンボルの集合から潜在的に無限の符号化シンボルのシーケンスを生成できるという特性を持つ消失訂正符号の一種であり、理想的には、元のソースシンボルは、ソースシンボルの数と等しいかわずかに大きいサイズの符号化シンボルの任意のサブセットから復元できる。ファウンテンまたはレートレスという用語は、これらの符号が固定の符号化率を示さないという事実を指す。

ファウンテン符号は、元のk個のソースシンボルが、正常に受信されたk個の符号化シンボル（つまり、消去されたシンボルを除く）から復元できる場合に最適です。ファウンテン符号は、効率的な符号化および復号化アルゴリズムを備え、 k'個の符号化シンボルから元のk個のソースシンボルを高い確率で復元できることが知られています。ここで、k'はkよりわずかに大きい値です。

LT符号は、ファウンテン符号の最初の実用化でした。その後、ラプター符号とオンライン符号が導入され、入力シンボルのプリコーディング段階を通じて線形時間符号化および復号化の計算量を実現しました。三角ネットワーク符号化は、非線形符号化を用いて線形符号化と復号化を実現し、後退置換法を用いて復号化を実現しました。

アプリケーション

ファウンテン コードは、固定のコード レートで柔軟に適用できます。また、事前に固定のコード レートを決定できない場合や、大量のデータの効率的なエンコードとデコードが必要な場合にも適用できます。

一例として、データ カルーセルが挙げられます。これは、大きなファイルが一連の受信者に継続的にブロードキャストされるものです。[ 1 ]固定レートの消失訂正符号を使用すると、ソース シンボルを (伝送エラーにより) 失った受信者は、クーポン コレクターの問題に直面します。つまり、まだ持っていない符号化シンボルを正常に受信する必要があるということです。この問題は、従来の短い長さの消失訂正符号を使用する場合に、ファイルを複数のブロックに分割し、それぞれを個別に符号化する必要があるため、はるかに顕著になります。受信者は、各ブロックについて、必要な数の失われた符号化シンボルを収集する必要があります。ファウンテン コードを使用すると、受信者は、ソース シンボルのセットよりもわずかに大きいサイズの符号化シンボルのサブセットを取得すれば十分です。 (実際には、ブロードキャストは通常​​、ネットワークと受信者の特性、および必要な配信の信頼性に基づいて、オペレータによって固定期間にスケジュールされます。そのため、ファウンテン コードは、ファイルのブロードキャストがスケジュールされた時点で動的に決定される符号化レートで使用されます。)

もう 1 つのアプリケーションは、信頼性の高いマルチキャストシナリオでのハイブリッド ARQです。つまり、受信者によって要求されるパリティ情報は、マルチキャスト グループ内の すべての受信者にとって潜在的に役立つ可能性があります。

標準では

ラプター符号は現時点で最も効率的なファウンテン符号であり、[ 2 ]非常に効率的な線形時間符号化および復号化アルゴリズムを持ち、符号化と復号化の両方で生成されたシンボルごとに少数の定数回のXOR演算のみを必要とします。[ 3 ] IETF RFC 5053は体系的なラプター符号を詳細に規定しており、ブロードキャストファイル配信およびストリーミングサービスの3GPP MBMS標準、 DVBネットワーク上でIPサービスを提供するためのDVB-H IPDC標準、IPネットワーク上で商用TVサービスを提供するためのDVB-IPTVなど、IETF以外の複数の標準に採用されています。この符号は、ソースブロックで最大8,192個のソースシンボルと、ソースブロック用に生成された合計最大65,536個の符号化シンボルで使用できます。この符号は、1,000個のソースシンボルを含むソースブロックに適用した場合の平均相対受信オーバーヘッドは0.2%で、99.9999%の確率で相対受信オーバーヘッドが2%未満です。[ 4 ]相対受信オーバーヘッドは、元のソースデータを復元するためにソースデータの長さを超えて必要な追加のエンコードデータとして定義され、ソースデータのサイズに対するパーセンテージで測定されます。例えば、相対受信オーバーヘッドが0.2%の場合、1 メガバイトのソースデータは1.002メガバイトのエンコードデータから復元できることを意味します。

IETF RFC 6330では、より柔軟性が高く受信オーバーヘッドが改善された、より高度なRaptorコードであるRaptorQが規定されています。規定されているRaptorQコードは、ソースブロック内の最大56,403個のソースシンボル、およびソースブロックに対して生成されるエンコードシンボルの合計が最大16,777,216個まで使用できます。このコードは、ソースブロック内のソースシンボルの数に等しいエンコードシンボルの任意のセットから高い確率でソースブロックを復元でき、まれにソースブロック内のソースシンボルの数よりわずかに多いエンコードシンボルのセットからでも復元できます。RaptorQコードは、ATSC A-331 (ATSC 3.0)で規定されているROUTEインスタンス化の不可欠な部分です。

データ保存用

消失訂正符号は、一定の冗長性と信頼性レベルを維持しつつ、ストレージユニット数を大幅に削減できるため、データストレージアプリケーションで使用されています。データストレージ、特に分散ストレージアプリケーションにおける消失訂正符号設計の要件は、通信やデータストリーミングのシナリオとは大きく異なる可能性があります。データストレージシステムの符号化要件の一つは、体系的な形式、つまり元のメッセージシンボルが符号化シンボルの一部であることです。体系的な形式であれば、ストレージユニットからデコードすることなくメッセージシンボルを読み取ることができます。さらに、ストレージノード間の帯域幅と通信負荷がボトルネックとなる可能性があるため、最小限の通信で済む符号は、特にノードに障害が発生し、初期レベルの冗長性を達成するためにシステムを再構築する必要がある場合に非常に有益です。この点において、ファウンテン符号は、障害発生時に効率的な修復プロセスを可能にすることが期待されています。つまり、符号化されたシンボルが1つ失われた場合、そのシンボルを復元するために、他の符号化シンボル間で過度の通信や計算を必要としないはずです。実際、修復のレイテンシは、ストレージスペースの節約よりも重要になる場合があります。修理可能な噴水コード[ 5 ]は、貯水システムの噴水コード設計目標に対応するために計画されています。噴水コードとその適用に関する詳細な調査は、こちらをご覧ください。[ 6 ]

Liquid Cloud Storageでは、ファウンテンコードを使用した分散ストレージへの異なるアプローチが提案されています。[ 7 ] [ 8 ] Liquid Cloud Storageは、 IETF RFC 6330 で指定されているRaptorQコードなどの大規模な消失訂正コード（他のシステムよりも大幅に優れたデータ保護を提供）、バックグラウンド修復プロセス（他のシステムと比較して修復帯域幅の要件を大幅に削減）、ストリームデータ編成（エンコードされたシンボルがすべて利用可能でない場合でもデータへの高速アクセスを可能にする）の使用に基づいています。

参照

注記

  1. ^ J. Byers, M. Luby , M. Mitzenmacher , A. Rege (1998). 「バルクデータの信頼性の高い配信のためのデジタルファウンテンアプローチ」(PDF) .{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  2. ^ 「Qualcomm Raptorテクノロジー - 前方誤り訂正」 2014年5月30日. 2010年12月29日時点のオリジナルよりアーカイブ。2011年6月7日閲覧。
  3. ^ (ショクロラヒ 2006 )
  4. ^ T. Stockhammer、A. Shokrollahi、M. Watson、M. Luby、T. Gasiba（2008年3月）。Furht, B.、Ahson, S.（編）「モバイルマルチメディア放送におけるアプリケーション層フォワードエラー訂正」。モバイル放送ハンドブック：DVB-H、DMB、ISDB-T、メディアFLO。CRC Press。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  5. ^ Asteris, Megasthenis; Dimakis, Alexandros G. (2012). 「修復可能なファウンテンコード」. IEEE Journal on Selected Areas in Communications . 32 (5): 1037– 1047. arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522 . S2CID 1300984 . 
  6. ^ Arslan, Suayb S. (2014). 「増分冗長性、ファウンテンコード、および高度なトピック」. arXiv : 1402.6016 [ cs.IT ].
  7. ^ Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). 「Liquid Cloud Storage」. ACM Transactions on Storage . 15 : 1– 49. arXiv : 1705.07983 . doi : 10.1145/3281276 . S2CID 738764 . 
  8. ^ルビー、M.;パドヴァニ、R.リチャードソン、T.ミンダー、L.アガルワル、P. (2017)。 「リキッドクラウドストレージ」。arXiv : 1705.07983v1 [ cs.DC ]。

参考文献

「 https://en.wikipedia.org/w/index.php?title=Fountain_code&oldid=1309533504」より取得