Loading article…
符号理論において、ファウンテン符号（無レート消去符号とも呼ばれる）は、与えられたソースシンボルの集合から潜在的に無限の符号化シンボル列を生成できるという性質を持つ消去符号の一種であり、理想的には、ソースシンボルの数と等しいか、わずかに大きいサイズの符号化シンボルの任意の部分集合から元のソースシンボルを復元できる。ファウンテンまたは無レートという用語は、これらの符号が固定の符号化率を示さないという事実を指している。
噴水符号は、正常に受信した任意のk個の符号化シンボル（消去されたものを除く）から元のk個のソースシンボルを復元できる場合に最適である。効率的な符号化および復号アルゴリズムを持ち、 kよりわずかに大きい任意のk'個の符号化シンボルから元のk個のソースシンボルを高い確率で復元できる噴水符号が知られている。
LT符号は、ファウンテン符号を実用化した最初の例である。その後、ラプター符号やオンライン符号が導入され、入力シンボルの事前符号化段階を通して、線形時間での符号化・復号を実現している。三角ネットワーク符号化は、非線形符号化を用いて線形符号化・復号を実現し、逆代入法を用いて復号を行う。
ファウンテンコードは、固定符号化率で柔軟に適用できるほか、固定符号化率を事前に決定できない場合や、大量のデータの効率的な符号化と復号化が必要な場合にも適しています。
一例として、データカルーセルが挙げられます。これは、大きなファイルが複数の受信機に継続的にブロードキャストされる方式です。[ 1 ]固定レートの消去符号を使用する場合、送信エラーによってソースシンボルが欠落した受信機は、クーポンコレクターの問題に直面します。つまり、まだ持っていない符号化シンボルを正常に受信する必要があるのです。この問題は、従来の短長消去符号を使用する場合に顕著になります。ファイルは複数のブロックに分割され、それぞれが個別に符号化されるため、受信機は各ブロックに必要な数の欠落した符号化シンボルを収集しなければなりません。ファウンテン符号を使用する場合、受信機はソースシンボルのセットよりわずかに大きいサイズの符号化シンボルの任意のサブセットを取得すれば十分です。（実際には、ブロードキャストは通常、ネットワークと受信機の特性および必要な配信信頼性に基づいて、オペレータによって一定期間スケジュールされるため、ファウンテン符号は、ファイルのブロードキャストがスケジュールされた時点で動的に決定される符号化レートで使用されます。）
もう一つの応用例は、信頼性の高いマルチキャストシナリオにおけるハイブリッドARQです。受信側から要求されたパリティ情報は、マルチキャストグループ内のすべての受信側にとって有用となる可能性があります。
ラプター符号は、現時点で最も効率的なファウンテン符号であり、[ 2 ]非常に効率的な線形時間エンコードおよびデコードアルゴリズムを備え、エンコードとデコードの両方で生成されるシンボルごとに少数の定数回のXOR演算しか必要としません。[ 3 ] IETF RFC 5053 では、体系的なラプター符号が詳細に規定されており、IETF 以外の複数の標準、例えば放送ファイル配信およびストリーミングサービス用の3GPP MBMS標準、 DVBネットワーク上で IP サービスを提供するDVB-H IPDC標準、IP ネットワーク上で商用 TV サービスを提供するDVB-IPTVなどに採用されています。この符号は、ソース ブロックで最大 8,192 個のソース シンボル、ソース ブロック用に生成されるエンコード済みシンボルの合計最大 65,536 個で使用できます。この符号は、1,000 個のソース シンボルを持つソース ブロックに適用した場合、平均相対受信オーバーヘッドが 0.2% であり、99.9999% の確率で相対受信オーバーヘッドが 2% 未満です。[ 4 ]相対受信オーバーヘッドは、元のソースデータを復元するためにソースデータの長さを超えて必要となる追加のエンコードデータとして定義され、ソースデータのサイズに対する割合として測定されます。たとえば、相対受信オーバーヘッドが 0.2% の場合、これは 1メガバイトのソースデータを1.002 メガバイトのエンコードデータから復元できることを意味します。
より柔軟性が高く、受信オーバーヘッドが改善された高度なラプター符号であるRaptorQが、IETF RFC 6330で規定されています。規定された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コードなどの大規模な消去コード（他のシステムよりもはるかに優れたデータ保護を提供）、バックグラウンド修復プロセス（他のシステムと比較して修復帯域幅要件を大幅に削減）、およびストリームデータ構成（エンコードされたシンボルがすべて利用できない場合でもデータに高速アクセスが可能）の使用に基づいています。
{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク){{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。