ファウンテンコード

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

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

LT コードは、ファウンテン コードの最初の実用的な実現でした。その後、ラプター コードとオンライン コードが導入され、入力シンボルの事前コーディング段階を通じて 線形時間エンコードとデコードの複雑さを実現しました。

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

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

もう 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 と呼ばれるより高度な Raptor コードがIETF RFC 6330 で指定されています。指定された RaptorQ コードは、ソース ブロック内の最大 56,403 個のソース シンボル、およびソース ブロック用に生成された合計最大 16,777,216 個のエンコード シンボルで使用できます。このコードは、ソース ブロック内のソース シンボルの数に等しいエンコード シンボルのセットからソース ブロックを高い確率で復元でき、まれにソース ブロック内のソース シンボルの数よりわずかに多い数から復元できることもあります。RaptorQ コードは、ATSC A-331 (ATSC 3.0) で指定されている ROUTE インスタンス化の不可欠な部分です。

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

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

• オンラインコード
• 線形ネットワークコーディング
• 秘密共有
• トルネードコード、ファウンテンコードの前身

• Amin Shokrollahi および Michael Luby ( 2011)。 「 Raptor Codes」。通信および情報理論の基礎と動向。6 ( 3–4)。Now Publishers: 213–322。doi :10.1561/0100000060。S2CID  1731099。
• Luby, Michael (2002)。「LT コード」。第 43 回 IEEE コンピュータ サイエンスの基礎に関するシンポジウム、2002 年。議事録。pp . 271–282。doi :10.1109/ sfcs.2002.1181950。ISBN 0-7695-1822-2.S2CID 1861068  。
• A. Shokrollahi (2006)、「Raptor Codes」、IEEE Transactions on Information Theory、52 (6): 2551–2567、doi :10.1109/tit.2006.874390、S2CID  61814971。
• P. Maymounkov (2002 年 11 月)。「オンライン コード」(PDF) (技術レポート)。
• David JC MacKay (2003)。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。Bibcode : 2003itil.book..... M。ISBN 0-521-64298-1。
• M. Luby、A. Shokrollahi、M. Watson、T. Stockhammer (2007 年 10 月)、オブジェクト配信のための Raptor 前方誤り訂正方式、RFC  5053{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。
• M. Luby、A. Shokrollahi、M. Watson、T. Stockhammer、L. Minder (2011 年 5 月)、オブジェクト配信のための RaptorQ 前方誤り訂正方式、RFC  6330{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。