ラプターコード

コンピュータサイエンスにおいて、ラプターコード（rap id tor nado ; ^[1] Tornadoコードを参照）は、線形時間符号化および復号化を備えた最初のファウンテンコードとして知られています。これらは、2000年または2001年にAmin Shokrollahiによって発明され、2004年に拡張概要として初めて公開されました。ラプターコードは、最初の実用的なファウンテンコードクラスであるLTコードに比べて、理論的にも実用的にも大幅に改善されています。

Raptor コードは、一般的なファウンテン コードと同様に、等しいサイズのソース シンボルk個からなる特定のソース ブロック データを、潜在的に無限のエンコード シンボル シーケンスにエンコードします。これにより、k個以上のエンコード シンボルを受信すると、ソース ブロックをゼロ以外の確率で復元できます。受信したエンコード シンボルの数が k よりわずかに大きい場合、受信したエンコード シンボルの数が 1 に非常に近づくにつれて、ソース ブロックを復元できる確率が増加します。たとえば、最新世代の Raptor コードである RaptorQ コードでは、k 個のエンコード シンボルを受信した場合のデコード失敗の可能性は 1% 未満であり、k+2 個のエンコード シンボルを受信した場合のデコード失敗の可能性は 100 万分の 1 未満です。シンボルのサイズは、1 バイトから数百または数千バイトまで任意です。

ラプター コードは体系的でも非体系的でもよい。体系的の場合、元のソース ブロックのシンボル、つまりソース シンボルは、エンコード シンボルのセット内に含まれます。体系的なラプター コードの例としては、第 3 世代パートナーシップ プロジェクトによるモバイル セルラー無線放送およびマルチキャストでの使用や、ハンドヘルド デバイスへの IP データキャストのDVB-H 標準での使用が挙げられます。^{[引用が必要]}これらの標準で使用されるラプター コードは、IETF RFC 5053 でも定義されています。

オンライン コードは、非体系的なファウンテン コードの例です。

Raptor の最も高度なバージョンは、IETF RFC 6330 で定義されている RaptorQ コードです。RaptorQ コードは体系的なコードであり、線形時間のエンコードおよびデコード パフォーマンスを実現する方法で実装でき、ほぼ最適な回復プロパティを備え、最大 56,403 個のソース シンボルをサポートし、基本的に無制限の数のエンコード シンボルをサポートできます。

IETF RFC 6330で定義されている RaptorQ コードは、高品質の放送ビデオ ストリーミング (堅牢なモバイル TV) と効率的で信頼性の高い放送ファイル配信 (データキャスト) を可能にするために、次世代 TV ( ATSC 3.0 ) 標準の一部として指定されています。特に、RaptorQ コードは ATSC 3.0 内の A/331 で指定されています。^{[2] ATSC 3.0 標準部品のリストについては、} ATSC 標準のリストを参照してください。次世代 TV (ATSC 3.0) は、従来の TV をはるかに超えて、一般的なデータ配信サービスを可能にする放送インターネットを提供します。

ラプター コードは 2 つのコードを連結して形成されます。

通常はかなり高いレートの固定レート消失コードが、「プリコード」または「外部コード」として適用されます。このプリコード自体は複数のコードの連結である可能性があり、たとえば、3GPP で標準化されたコードでは、バイナリ グレイ シーケンスから派生した高密度パリティ チェック コードが、単純な通常の低密度パリティ チェック コードと連結されています。別の可能性としては、ハミング コードと低密度パリティ チェック コード の連結が挙げられます。

内部コードは、プリコーディング操作の結果を受け取り、エンコード シンボルのシーケンスを生成します。内部コードはLT コードの一種です。各エンコード シンボルは、プリコード出力から疑似ランダムに選択されたシンボル セットのXORです。出力シンボルを形成するために XOR されるシンボルの数は、特定の確率分布に従って各出力シンボルに対して疑似ランダムに選択されます。

この分布、およびこの分布をサンプリングして XOR 演算するシンボルを選択するための疑似乱数を生成するメカニズムは、送信者と受信者の両方が知っている必要があります。 1 つのアプローチでは、各シンボルに識別子が付いており、これを疑似乱数ジェネレータのシードとして使用してこの情報を生成します。送信者と受信者の両方が同じプロセスに従います。

非体系的な Raptor コードの場合、エンコードされるソース データはプリコーディング ステージへの入力として使用されます。

体系的な Raptor コードの場合、プリコーディング ステージへの入力は、まず最初のk 個の出力シンボルを生成するエンコード操作の逆をソース データに適用することによって取得されます。したがって、結果のシンボルに通常のエンコード操作を適用すると、元のソース シンボルがコードの最初のk 個の出力シンボルとして再生成されます。最初のk 個の出力シンボルを生成する疑似ランダム プロセスが、可逆な操作を生成する ようにする必要があります。

Raptor コードのデコードには 2 つの方法があります。連結アプローチでは、LT コードに使用されるようなビリーフ プロパゲーション アルゴリズムを使用して、最初に内部コードをデコードします。この操作で十分な数のシンボルが復元され、外部コードがそのコードに適したデコード アルゴリズムを使用して残りのシンボルを復元できる場合、デコードは成功します。

複合アプローチでは、内部コードと外部コードの両方で定義されたシンボル間の関係は、通常の方法、通常はガウス消去法で解くことができる単一の複合同時方程式セットとして扱われます。

Raptor コードでは、ソース ブロックからエンコード シンボルを生成するのにO(シンボル サイズ)の時間が必要であり、少なくともk 個のエンコード シンボルからソース ブロックを復元するのにO(ソース ブロック サイズ)の時間が必要です。

オーバーヘッドとは、ソース ブロックを完全に復元するために、元のソース ブロック内のソース シンボルの数k を超えて受信する必要がある追加のエンコード シンボルの数です。(基本的な情報理論の考察に基づくと、 k個未満のエンコード シンボルを受信した場合、 k個のソース シンボルを含むソース ブロックを完全に復元することはできません。) 復元確率とは、ソース ブロックから生成されたランダムなエンコード シンボルを指定された数だけ受信したときに、ソース ブロックが完全に復元される確率です。

IETF RFC 6330で指定されている RaptorQ コードでは、回復確率と回復オーバーヘッドの間に次のようなトレードオフがあります。

• オーバーヘッドが 0 シンボルの場合の回復確率は 99% を超えます (受信したk 個のエンコード シンボルからの回復)。
• 1 シンボルのオーバーヘッドで 99.99% を超える回復確率 ( k+1 個の受信エンコード シンボルからの回復)。
• 2 シンボルのオーバーヘッドで 99.9999% を超える回復確率 ( k+2 個の受信エンコード シンボルからの回復)。

これらの記述はIETF RFC 6330でサポートされているkの全範囲、つまりk =1,...,56403に当てはまります。詳細についてはIETF RFC 6330を参照してください。 ^[3]

Qualcomm, Inc. は、 IETF RFC 5053で規定されている Raptor コードの IPR ステートメントと、IETF RFC 6330 で規定されているより高度な RaptorQ コードの IPR ステートメントを公開しました。これらのステートメントは、Qualcomm, Inc. がMPEG DASH 標準に関して行ったライセンス契約を反映しています 。MPEG DASH 標準は、DASH Industry Forum のメンバー企業を含むさまざまな企業によって導入されています。

• 消去コード
• ファウンテンコード
• LTコード
• 竜巻コード

• ATSC 3.0 (先進テレビ規格委員会 3.0)
• 3GPP (第3世代パートナーシッププロジェクト)
• DVB (デジタルビデオ放送)
• 3GPP TS26.346 マルチメディア ブロードキャスト/マルチキャスト サービスの 3GPP 技術仕様: プロトコルとコーデック。
• RFC5053 オブジェクト配信のための Raptor 前方誤り訂正方式
• DVB-H IPデータキャスト仕様

• Shokrollahi, Amin (2006 年 6 月)。「Raptor コード」。IEEE Transactions on Information Theory。52 : 2551–2567。doi : 10.1109 /TIT.2006.874390。
• RFC 5053 の「IPR」検索結果（一部の特許所有者の声明付き）
• RFC 6330 の「IPR」検索結果（一部の特許所有者の声明付き）