トルネードコード

符号理論において、トルネード符号は誤り訂正をサポートする消失訂正符号の一種である。トルネード符号は、データ効率に優れたリード・ソロモン消失訂正符号よりも定数C個の冗長ブロックを必要とするが、生成がはるかに高速で、消失の修正も高速である。ソフトウェアベースのトルネード符号の実装は、リード・ソロモン消失訂正符号よりも、短い符号では約100倍、長い符号では約10,000倍高速である。^{[1]トルネード符号の導入以来、}オンライン符号、LT符号、ラプター符号など、同様の消失訂正符号が数多く登場している。

トルネード コードは階層化アプローチを採用しています。最後の層を除くすべての層では、高速ですが失敗する可能性のあるLDPCエラー訂正コードが使用されています。最終層では、低速ですが障害回復の点では最適なリード ソロモン訂正コードが使用されています。トルネード コードは、レベルの数、各レベルの回復ブロックの数、および最終層以外の層のブロック生成に使用される分布を指定します。

入力データはブロックに分割されます。ブロックはすべて同じサイズのビットのシーケンスです。リカバリ データは入力データと同じブロック サイズを使用します。ブロック (入力またはリカバリ) の消去は、他の手段によって検出されます (たとえば、ディスクからのブロックが CRC チェックに合格しなかったり、指定されたシーケンス番号のネットワーク パケットが到着しなかったりします)。

リカバリ ブロックの数は、ユーザーが指定します。次に、レベル数と各レベルのブロック数が決定されます。各レベルの数は、1 未満の係数 B によって決定されます。入力ブロックが N 個ある場合、最初のリカバリ レベルには B*N ブロック、2 番目のレベルには B×B×N、3 番目のレベルには B×B×B×N というように続きます。

最後のレベルを除くすべての回復レベルでは、XOR (排他的論理和) によって機能する LDPC が使用されます。XOR は、1 と 0 のバイナリ値に対して動作します。A xor B は、A と B の値が異なる場合は 1、A と B の値が同じ場合は 0 になります。(A xor B) と A の結果が与えられた場合、B の値を決定できます (A xor B xor A = B) 同様に、(A xor B) と B の結果が与えられた場合、A の値を決定できます。これは複数の値に拡張されるため、(A xor B xor C xor D) の結果と任意の 3 つの値が与えられた場合、失われた値を回復できます。

したがって、レベル 1 のリカバリ ブロックは、入力ブロックのセットの XOR にすぎません。同様に、レベル 2 のリカバリ ブロックはそれぞれ、レベル 1 のブロックのセットの XOR です。XOR で使用されるブロックは、重複することなくランダムに選択されます。ただし、リカバリ ブロックを作成するために XOR されるブロックの数は、レベルごとに非常に特定の分布から選択されます。

xor は高速な演算であり、リカバリ ブロックは入力内のブロックのサブセットのみの xor (またはより低いリカバリ レベル) であるため、リカバリ ブロックを迅速に生成できます。

最後のレベルはリード・ソロモン符号です。リード・ソロモン符号は障害からの回復という点では最適ですが、生成と回復に時間がかかります。各レベルのブロック数は前のレベルよりも少ないため、リード・ソロモン符号では生成して回復に使用する回復ブロックの数が少なくなります。そのため、リード・ソロモンは遅いですが、処理するデータの量はわずかです。

回復中は、リード・ソロモン コードが最初に回復されます。最終レベルから 2 番目のレベルで失われたブロックの数が最終レベルに存在するブロックの数より少ない場合、これが機能することが保証されます。

さらに下に行くと、LDPC (XOR) 回復レベルは、すべての回復ブロックが存在し、その下のレベルで回復レベルより最大 C' 少ないブロックが欠落している場合、高い確率でその下のレベルを回復するために使用できます。回復のアルゴリズムは、生成セットの 1 つだけが下位レベルから欠落している回復ブロックを見つけることです。次に、回復ブロックと存在するすべてのブロックの XOR は、欠落しているブロックと等しくなります。

トルネードコードは、以前はアメリカ合衆国内で特許を取得していました。^[2]特許US6163870 A（1997年11月6日出願）およびUS 6081909 A（1997年11月6日出願）はトルネードコードについて記述しており、2017年11月6日をもって失効しています。特許US6307487 B1（1999年2月5日出願）およびUS6320520 B1（1999年9月17日出願）もトルネードコードについて言及しており、それぞれ2019年2月5日と2019年9月17日をもって失効しています。

マイケル・ルビーがトルネードコードを作成した。^{[3] [4]}

• 消去コード
• ラプターコード

• Byers JW、Luby M、Mitzenmacher M、Rege A (1998 年 10 月)。「バルク データの信頼性の高い配布のためのデジタル ファウンテン アプローチ」。SIGCOMM '98 : Proceedings。ACM SIGCOMM '98 会議、コンピュータ通信のアプリケーション、テクノロジ、アーキテクチャ、プロトコル。pp. 56–67。doi : 10.1145/285237.285258。
• Luby M、Mitzenmacher M、Shokrollahi A、Spielman D、Stemann V (1997)。「実用的な損失耐性コード」。第 29 回 ACM コンピューティング理論シンポジウム議事録: 150–159。
• Luby M、Mitzenmacher M、Shokrollahi A (1998)。「AND-OR ツリー評価によるランダム プロセスの分析」。第 9 回 ACM-SIAM 離散アルゴリズム シンポジウム議事録: 364–373。
• Mitzenmacher M (2004)。「デジタルファウンテン：調査と展望」。2004 IEEE 情報理論ワークショップ (ITW) 議事録。

CMUによる判読可能な説明(PostScript) [1]と、国際コンピュータサイエンス研究所のLubyによる判読可能な説明(PostScript) [2]。