Luby_transform_code
コンピューター サイエンスでは、Luby 変換コード( LT コード) は、最適に近い消失訂正コードである実用的なファウンテン コードの最初のクラスです。それらは1998 年に Michael Luby によって発明され、2002 年に公開されました。LT コードの際立った特徴は、排他的論理和演算 ( ⊕
{ oplus }
) メッセージをエンコードおよびデコードします。
LT コードはレートレスです。これは、エンコード アルゴリズムが原則として無限の数のメッセージ パケットを生成できるためです (つまり、メッセージをデコードするために受信する必要があるパケットの割合は、任意に小さくすることができます)。これらは、消去チャネルで確実にデジタル データを送信するために使用できるため、消去訂正コードです。
LT コードの次の世代はラプター コード(たとえば、IETF RFC 5053 または IETF RFC 6330 を参照) であり、線形時間のエンコードとデコードを行います。ラプター コードは基本的に LT コードに基づいています。つまり、ラプター コードのエンコードは 2 つのエンコード ステージを使用し、2 番目のステージは LT エンコードです。同様に、Raptor コードを使用したデコードは主に LT デコードに依存していますが、LT デコードはより高度なデコード技術と混在しています。最も高度なファウンテン コードである IETF RFC 6330 で指定された RaptorQ コードは、LT コードのみを使用する場合と比較して、非常に優れたデコード確率とパフォーマンスを備えています。
コンテンツ
1 LT コードを使用する理由
2 LTエンコーディング
3 LTデコード
4 バリエーション
5 LT コードの最適化
6 こちらもご覧ください
7 注意事項と参考文献
8 外部リンク
LT コードを使用する理由
消去チャネルを介してデータを転送するための従来のスキームは、継続的な双方向通信に依存しています。
送信者は情報のパケットをエンコードして送信します。
受信側は、受信したパケットのデコードを試みます。デコードできる場合、受信者は確認応答を送信者に送り返します。それ以外の場合、受信者は送信者にパケットの再送信を要求します。
この双方向プロセスは、メッセージ内のすべてのパケットが正常に転送されるまで続きます。
セルラー ワイヤレス ブロードキャストに使用されるネットワークなど、特定のネットワークにはフィードバック チャネルがありません。これらのネットワーク上のアプリケーションには、依然として信頼性が必要です。Fountain コード全般、特に LT コードは、基本的に一方向通信プロトコルを採用することでこの問題を回避します。
送信者は情報のパケットをエンコードしてパケットを送信します。
受信者は、受信した各パケットを評価します。エラーが発生した場合、エラーのあるパケットは破棄されます。それ以外の場合、パケットはメッセージの一部として保存されます。
最終的に、受信者はメッセージ全体を再構築するのに十分な有効なパケットを取得します。メッセージ全体が正常に受信されると、受信者は送信が完了したことを知らせます。
前述のように、IETF RFC 6330 で指定された RaptorQ コードは、実際には LT コードよりも優れています。
LTエンコーディング
符号化プロセスは、符号化されていないメッセージをほぼ同じ長さのnブロックに分割することから始まります。次に、疑似乱数ジェネレーターを使用して、エンコードされたパケットが生成されます。
次のパケットの次数d (1 ≤ d ≤ n ) はランダムに選択されます。
メッセージから正確にd個のブロックがランダムに選択されます。
M iがメッセージのi番目のブロックである場合、次のパケットのデータ部分は次のように計算されます。
MI 1 ⊕ M I 2 ⊕ ⋯ ⊕ I0 I1 I2
{ M_{i_{1}}oplus M_{i_{2}}oplus cdots oplus M_{i_{d}}，}
