Tornado-Code - Tornado code

In der Codierungstheorie sind Tornado-Codes eine Klasse von Löschcodes , die die Fehlerkorrektur unterstützen . Tornado-Codes erfordern ein konstantes C redundantere Blöcke als die dateneffizienteren Reed-Solomon-Löschcodes , sind jedoch viel schneller zu generieren und können Löschungen schneller beheben. Softwarebasierte Implementierungen von Tornado-Codes sind bei kleinen Längen etwa 100-mal schneller und bei größeren Längen etwa 10.000-mal schneller als Reed-Solomon-Löschcodes. Seit der Einführung von Tornado-Codes sind viele andere ähnliche Löschcodes entstanden, insbesondere Online-Codes , LT-Codes und Raptor-Codes .

Tornado-Codes verwenden einen mehrschichtigen Ansatz. Alle Schichten mit Ausnahme der letzten verwenden einen LDPC- Fehlerkorrekturcode, der schnell ist, aber möglicherweise ausfällt. Die letzte Schicht verwendet einen Reed-Solomon-Korrekturcode, der langsamer ist, aber hinsichtlich der Fehlerbehebung optimal ist. Tornado-Codes bestimmen, wie viele Ebenen, wie viele Wiederherstellungsblöcke in jeder Ebene und die Verteilung zum Generieren von Blöcken für die nicht endgültigen Ebenen verwendet werden.

Überblick

Die Eingabedaten sind in Blöcke unterteilt. Blöcke sind Folgen von Bits, die alle gleich groß sind. Wiederherstellungsdaten verwenden dieselbe Blockgröße wie die Eingabedaten. Das Löschen eines Blocks (Eingabe oder Wiederherstellung) wird auf andere Weise erfasst. (Zum Beispiel besteht ein Block von der Festplatte keine CRC-Prüfung oder ein Netzwerkpaket mit einer bestimmten Sequenznummer ist nie angekommen.)

Die Anzahl der Wiederherstellungsblöcke wird vom Benutzer angegeben. Dann wird die Anzahl der Ebenen zusammen mit der Anzahl der Blöcke in jeder Ebene bestimmt. Die Anzahl in jeder Ebene wird durch einen Faktor B bestimmt, der kleiner als eins ist. Wenn es N Eingangsblöcke gibt, hat die erste Wiederherstellungsstufe B * N Blöcke, die zweite hat B * B * N, die dritte hat B * B * B * N und so weiter.

Alle Wiederherstellungsstufen außer der letzten verwenden einen LDPC, der von xor (exklusiv-oder) funktioniert. Xor arbeitet mit Binärwerten, 1s und 0s. A x oder B ist 1, wenn A und B unterschiedliche Werte haben, und 0, wenn A und B dieselben Werte haben. Wenn Sie das Ergebnis von (A x oder B) und A erhalten, können Sie den Wert für B bestimmen. (A x oder B x oder A = B) Wenn Sie das Ergebnis von (A x oder B) und B erhalten, können Sie auch bestimmen Der Wert für A. Dies erstreckt sich auf mehrere Werte. Wenn also das Ergebnis von (A x oder B x oder C x oder D) und 3 der Werte gegeben ist, kann der fehlende Wert wiederhergestellt werden.

Die Wiederherstellungsblöcke in Ebene 1 sind also nur das xor eines Satzes von Eingabeblöcken. In ähnlicher Weise sind die Wiederherstellungsblöcke in Ebene zwei jeweils das x oder eines Satzes von Blöcken in Ebene eins. Die im xor verwendeten Blöcke werden ohne Wiederholung zufällig ausgewählt. Die Anzahl der Blöcke , die für die Erstellung eines Wiederherstellungsblocks benötigt werden, wird jedoch aus einer sehr spezifischen Verteilung für jede Ebene ausgewählt.

Da xor eine schnelle Operation ist und die Wiederherstellungsblöcke nur eine Teilmenge der Blöcke in der Eingabe (oder auf einer niedrigeren Wiederherstellungsstufe) sind, können die Wiederherstellungsblöcke schnell generiert werden.

Die letzte Stufe ist ein Reed-Solomon-Code. Reed-Solomon-Codes sind hinsichtlich der Wiederherstellung nach Fehlern optimal, lassen sich jedoch nur langsam generieren und wiederherstellen. Da jede Ebene weniger Blöcke als die vorherige hat, verfügt der Reed-Solomon-Code über eine kleine Anzahl von Wiederherstellungsblöcken, die generiert und für die Wiederherstellung verwendet werden können. Obwohl Reed-Solomon langsam ist, muss es nur eine kleine Datenmenge verarbeiten.

Während der Wiederherstellung wird zuerst der Reed-Solomon-Code wiederhergestellt. Dies funktioniert garantiert, wenn die Anzahl der fehlenden Blöcke in der vorletzten Ebene geringer ist als die Anzahl der vorhandenen Blöcke in der letzten Ebene.

Wenn die LDPC (xor) -Wiederherstellungsstufe niedriger ist, kann die darunter liegende Stufe mit hoher Wahrscheinlichkeit wiederhergestellt werden, wenn alle Wiederherstellungsblöcke vorhanden sind und die darunter liegende Stufe höchstens C 'weniger Blöcke als die Wiederherstellungsstufe fehlt. Der Algorithmus für die Wiederherstellung besteht darin, einen Wiederherstellungsblock zu finden, bei dem nur einer seiner Generierungssätze auf der unteren Ebene fehlt. Dann ist das xor des Wiederherstellungsblocks mit allen vorhandenen Blöcken gleich dem fehlenden Block.

Patentfragen

Tornado-Codes wurden früher in den Vereinigten Staaten von Amerika patentiert. Die Patente US6163870 A (eingereicht am 6. November 1997) und US 6081909 A (eingereicht am 6. November 1997) beschreiben Tornado-Codes und sind zum 6. November 2017 abgelaufen. Patente US6307487 B1 (eingereicht am 5. Februar 1999) und US6320520 B1 (eingereicht am 6. Februar 1997) 17. September 1999) erwähnen ebenfalls Tornado-Codes und sind zum 5. Februar 2019 bzw. 17. September 2019 abgelaufen.

Zitate

Michael Luby hat die Tornado-Codes erstellt.

Externe Links

Eine lesbare Beschreibung von CMU (PostScript) [1] und eine andere von Luby vom International Computer Science Institute (PostScript) [2] .

Siehe auch

Anmerkungen

Verweise

  • M. Mitzenmacher (2004). "Digitale Brunnen: Eine Umfrage und ein Ausblick". Proc. 2004 IEEE Information Theory Workshop (ITW) .
  • M. Luby , M. Mitzenmacher , A. Shokrollahi , D. Spielman , V. Stemann (1997). "Praktische verlustresistente Codes". Vorträge des neunundzwanzigsten jährlichen ACM-Symposiums zur Theorie des Rechnens : 150–159. CS1-Wartung: mehrere Namen: Autorenliste ( Link )
  • M. Luby , M. Mitzenmacher , A. Shokrollahi (1998). "Analyse zufälliger Prozesse mittels And-Or Tree Evaluation". Vorträge des 9. jährlichen ACM-SIAM-Symposiums zu diskreten Algorithmen : 364–373. CS1-Wartung: mehrere Namen: Autorenliste ( Link )