Luby変換コード

コンピュータサイエンスにおいて、ルビー変換コード（LTコード）は、ほぼ最適な消失訂正コードである実用的なファウンテンコードの最初のクラスです。これらは1998年にマイケル・ルビーによって発明され、2002年に公開されました。 ^[1]他のファウンテンコードと同様に、LTコードは疎な二部グラフに依存して、受信オーバーヘッドと引き換えにエンコードとデコードの速度を向上させています。LTコードの特徴は、排他的論理和演算（）に基づく非常に単純なアルゴリズムを使用してメッセージをエンコードおよびデコードすることです。^[2] $\oplus$

LT コードは、符号化アルゴリズムが原理的に無限の数のメッセージパケットを生成できるため、レートレスです (つまり、メッセージをデコードするために受信する必要があるパケットの割合は任意に小さくすることができます)。LTコードは、消失訂正符号であるため、消失訂正チャネルでデジタルデータを確実に送信できます。

LT コードの次の世代はRaptor コードです(たとえば、IETF RFC 5053 または IETF RFC 6330 を参照)。これは線形時間エンコードおよびデコードを備えています。Raptor コードは基本的に LT コードに基づいています。つまり、Raptor コードのエンコードには 2 つのエンコードステージが使用され、2 番目のステージは LT エンコードです。同様に、Raptor コードによるデコードは主に LT デコードに依存しますが、LT デコードはより高度なデコード技術と混在しています。最も高度なファウンテンコードである IETF RFC 6330 で指定されている RaptorQ コードは、LT コードのみを使用する場合と比較して、デコード確率とパフォーマンスが大幅に優れています。

LT コードを使用する理由は何ですか?

消去チャネルを介してデータを転送する従来の方式は、継続的な双方向通信に依存しています。

送信者は情報パケットをエンコードして送信します。
受信側は受信したパケットのデコードを試みます。デコードできる場合、受信側は送信側に確認応答を返します。デコードできない場合、受信側は送信側にパケットの再送信を要求します。
この双方向のプロセスは、メッセージ内のすべてのパケットが正常に転送されるまで継続されます。

携帯電話のワイヤレス放送に使用されるネットワークなど、特定のネットワークにはフィードバックチャネルがありません。これらのネットワーク上のアプリケーションには、依然として信頼性が必要です。一般的なファウンテンコード、特に LT コードは、基本的に一方向の通信プロトコルを採用することでこの問題を回避します。

送信者は情報のパケットを次々とエンコードして送信します。
受信側は、受信した各パケットを評価します。エラーがある場合、エラーのあるパケットは破棄されます。それ以外の場合、パケットはメッセージの一部として保存されます。
最終的に、受信側はメッセージ全体を再構築するのに十分な有効パケットを取得します。メッセージ全体が正常に受信されると、受信側は送信が完了したことを通知します。

前述のように、IETF RFC 6330 で指定されている RaptorQ コードは、実際には LT コードよりも優れています。

LTエンコーディング

エンコード処理は、エンコードされていないメッセージをほぼ等しい長さのn個のブロックに分割することから始まります。次に、疑似乱数ジェネレータを使用してエンコードされたパケットが生成されます。

次のパケットの次数d（1 ≤ d ≤ n ）はランダムに選択されます。
メッセージから正確にd 個のブロックがランダムに選択されます。
M _{i が}メッセージのi番目のブロックである場合、次のパケットのデータ部分は次のように計算されます。

M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,

ここで、{ i ₁、 i ₂、...、 i _d } は、このパケットに含まれるd 個のブロックに対してランダムに選択されたインデックスです。

エンコードされたパケットにプレフィックスが追加され、メッセージに含まれるブロック数n 、このパケットのデータ部分に排他的論理和演算されたブロック数d 、およびインデックスのリスト { i ₁、 i ₂、...、 i _d }が定義されます。
最後に、何らかの形式のエラー検出コード（巡回冗長検査のような単純なもの）がパケットに適用され、パケットが送信されます。

このプロセスは、受信側がメッセージを受信し、正常にデコードされたことを通知するまで継続されます。

LTデコード

デコード処理では、「排他的論理和」演算を使用してエンコードされたメッセージを取得します。

現在のパケットがクリーンでない場合、またはすでに処理されたパケットを複製する場合、現在のパケットは破棄されます。
現在正常に受信されたパケットの次数d > 1の場合、まずメッセージキュー領域内のすべての完全にデコードされたブロックに対して処理され (次の手順で詳しく説明します)、次にその削減次数が 1 より大きい場合はバッファー領域に格納されます。
次数d = 1の新しいクリーンなパケット (ブロックM _i ) が受信されると (または、前の手順で現在のパケットの次数が 1 に減ると)、そのパケットはメッセージキューイング領域に移動され、バッファー内にある次数d > 1 のすべてのパケットと照合されます。これは、 M _{i を}使用してエンコードされたバッファーされたパケットのデータ部分と排他的論理和演算され、その一致したパケットの次数が減算され、そのパケットのインデックスのリストがM _iの適用を反映するように調整されます。
このプロセスがバッファ内の次数d = 2のブロックのロックを解除すると、そのブロックは次数 1 に削減され、メッセージキュー領域に移動され、バッファ内に残っているパケットに対して処理されます。
メッセージのnブロックすべてがメッセージキュー領域に移動されると、受信側は送信側にメッセージが正常にデコードされたことを通知します。

この復号化手順は、任意のビット列Aに対してA A = 0 となるため有効である。d − 1 個の異なるブロックを排他的論理和して次数dのパケットにした後、一致しないブロックの元の符号化されていない内容だけが残る。記号では、 $\oplus$

{\begin{aligned}&{}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}

バリエーション

上で説明したエンコードおよびデコード処理には、いくつかのバリエーションが考えられます。たとえば、各パケットの先頭に実際のメッセージブロックインデックス { i ₁、 i ₂、 ...、 i _d } のリストを付ける代わりに、エンコーダは、インデックスのリストを作成するために使用される疑似乱数ジェネレータ(PRNG) またはインデックステーブルのシードとして機能する短い「キー」を送信するだけです。同じ RNG またはインデックステーブルを備えた受信機は、このシードから「ランダム」なインデックスのリストを確実に再作成できるため、デコード処理を正常に完了できます。または、平均次数の低い単純な LT コードと堅牢なエラー訂正コードを組み合わせることで、最適化された LT コードよりも実際に優れたパフォーマンスを発揮するラプターコードを構築できます。^[3]

LTコードの最適化

ストレート LT コードを最適化するために使用できるパラメータは 1 つだけです。それは次数分布関数 (上記のLT エンコードセクションで次数dの疑似乱数生成器として説明されています) です。実際には、他の「ランダム」な数値 (インデックスのリスト { i ₁、 i ₂、 ...、 i _d } ) は常に [0、 n ) 上の均一分布から取得されます。ここで、 nはメッセージが分割されたブロックの数です。^[4]

ルビー自身^[1]は、次のように定義される「理想的なソリトン分布」について議論した。

{\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\}&={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}

この次数分布は、理論的には、デコード処理が完了する前に送信される冗長コードワードの予想数を最小化します。しかし、理想的なソリトン分布は実際にはうまく機能しません。予想される動作の周りの変動により、デコード処理のどこかの段階で (縮小された) 次数 1 のパケットが利用できなくなり、デコードが失敗する可能性が高くなるためです。さらに、元のブロックの一部は、送信パケットのいずれにも XOR されません。したがって、実際には、修正された分布である「ロバストソリトン分布」が理想的な分布の代わりに使用されます。修正の効果は、一般に、非常に小さい次数 (約 1) のパケットが多く生成され、次数 1 より大きいパケットが少なくなることです。ただし、すべての元のブロックが何らかのパケットに含まれるようにするために選択されたかなり大きな量のパケットのスパイクは除きます。^[4]

参照

注釈と参考文献

^ ab M.Luby、「LT コード」、第 43 回 IEEE コンピュータサイエンスの基礎に関するシンポジウム、2002 年。
^ ⊕ で表される排他的論理和(XOR) 演算には、 A ⊕ A = 0という非常に便利な特性があります。ここで、 Aは任意のビット文字列です。
^ Fountain codes、DJC MacKay著、IEEE Proc.-Commun.、Vol. 152、No. 6、2005年12月に初版発行。
^ ab 重要度サンプリングアプローチによる LT コードの次数分布の最適化、Esa Hyytiä、Tuomas Tirronen、Jorma Virtamo (2006) 著。

外部リンク

「C# での Luby 変換コードの実装」
「C/C++ でのストレージ用 Fountain コードの実装」
「ファウンテンコード入門: Python による LT コード」

[Luby-1] M.Luby、「LT コード」、第 43 回 IEEE コンピュータサイエンスの基礎に関するシンポジウム、2002 年。

[2] ⊕ で表される排他的論理和(XOR) 演算には、 A ⊕ A = 0という非常に便利な特性があります。ここで、 Aは任意のビット文字列です。

[MacKay-3] Fountain codes、DJC MacKay著、IEEE Proc.-Commun.、Vol. 152、No. 6、2005年12月に初版発行。

[Tirronen-4] 重要度サンプリングアプローチによる LT コードの次数分布の最適化、Esa Hyytiä、Tuomas Tirronen、Jorma Virtamo (2006) 著。