Löschcode - Erasure code

In der Codierungstheorie ist ein Löschcode ein Vorwärtsfehlerkorrekturcode (FEC) unter der Annahme von Bitlöschungen (anstelle von Bitfehlern), der eine Nachricht von k Symbolen in eine längere Nachricht (Codewort) mit n Symbolen umwandelt, so dass die die ursprüngliche Nachricht kann aus einer Teilmenge der n Symbole wiederhergestellt werden . Der Bruch r  =  k / n wird Coderate genannt . Der Bruch k'/k , wobei k' die Anzahl der für die Wiederherstellung erforderlichen Symbole bezeichnet, wird als Empfangseffizienz bezeichnet .

Optimale Löschcodes

Optimale Löschcodes haben die Eigenschaft, dass irgendwelche k der n Codewortsymbole ausreichen, um die ursprüngliche Nachricht wiederherzustellen (dh sie haben eine optimale Empfangseffizienz). Optimale Löschcodes sind maximal abstandstrennbare Codes (MDS-Codes).

Paritätsprüfung

Paritätsprüfung ist der Sonderfall, bei dem n = k + 1 gilt. Aus einer Menge von k Werten wird eine Prüfsumme berechnet und an die k Quellwerte angehängt : ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$

${\displaystyle v_{k+1}=-\sum_{i=1}^{k}v_{i}.}$

Der Satz von k  + 1 Werten ist nun bezüglich der Prüfsumme konsistent. Wenn einer dieser Werte, , gelöscht wird, kann er leicht durch Summieren der verbleibenden Variablen wiederhergestellt werden: ${\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}$${\displaystyle v_{e}}$

${\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}$

Polynomiales Oversampling

Beispiel: Fehler-Mail ( k = 2)

Im einfachen Fall, bei dem k = 2 ist, können Redundanzsymbole erzeugt werden, indem verschiedene Punkte entlang der Linie zwischen den beiden ursprünglichen Symbolen abgetastet werden. Dies wird mit einem einfachen Beispiel dargestellt, das err-mail genannt wird:

Alice möchte Bob ihre Telefonnummer (555629) per Err-Mail schicken. Err-Mail funktioniert wie E-Mail, außer

1. Etwa die Hälfte aller Post geht verloren.
2. Nachrichten mit mehr als 5 Zeichen sind unzulässig.
3. Es ist sehr teuer (ähnlich wie Luftpost).

Anstatt Bob zu bitten, die von ihr gesendeten Nachrichten zu bestätigen, entwickelt Alice das folgende Schema.

1. Sie zerlegt ihre Telefonnummer in zwei Teile a = 555, b = 629 und sendet 2 Nachrichten – „A=555“ und „B=629“ – an Bob.
2. Sie konstruiert eine lineare Funktion , in diesem Fall , so dass und .${\displaystyle f(i)=a+(ba)(i-1)}$${\displaystyle f(i)=555+74(i-1)}$${\displaystyle f(1)=555}$${\displaystyle f(2)=629}$

1. Sie berechnet die Werte f (3), f (4) und f (5) und überträgt dann drei redundante Nachrichten: "C=703", "D=777" und "E=851".

Bob weiß, dass die Form von f ( k ) ist , wobei a und b die beiden Teile der Telefonnummer sind. Angenommen, Bob erhält "D=777" und "E=851". ${\displaystyle f(i)=a+(ba)(i-1)}$

Bob kann Alices Telefonnummer rekonstruieren, indem er die Werte von a und b aus den erhaltenen Werten ( f (4) und f (5)) berechnet . Bob kann diesen Vorgang mit zwei beliebigen Err-Mails ausführen, sodass der Löschcode in diesem Beispiel eine Rate von 40% hat.

Beachten Sie, dass Alice ihre Telefonnummer nicht in nur einer E-Mail codieren kann, da sie sechs Zeichen enthält und dass die maximale Länge einer E-Mail-Nachricht fünf Zeichen beträgt. Wenn sie ihre Telefonnummer in Stücken sendete und Bob bittet, den Empfang jedes Stücks zu bestätigen, müssten ohnehin mindestens vier Nachrichten gesendet werden (zwei von Alice und zwei Bestätigungen von Bob). Der Löschcode in diesem Beispiel, der fünf Nachrichten erfordert, ist also recht sparsam.

Dieses Beispiel ist ein wenig konstruiert. Für wirklich generische Löschcodes, die für jeden Datensatz funktionieren, benötigen wir etwas anderes als das angegebene f ( i ).

Allgemeiner Fall

Die obige lineare Konstruktion kann auf Polynominterpolation verallgemeinert werden . Außerdem werden jetzt Punkte über einem endlichen Körper berechnet .

Zuerst wählen wir einen endlichen Körper F mit Ordnung von mindestens n , aber normalerweise eine Potenz von 2. Der Sender nummeriert die Datensymbole von 0 bis k  − 1 und sendet sie. Dann konstruiert er ein (Lagrange-)Polynom p ( x ) der Ordnung k, so dass p ( i ) gleich dem Datensymbol i ist . Dann sendet er p ( k ), ..., p ( n  − 1). Der Empfänger kann nun auch Polynominterpolation verwenden, um die verlorenen Pakete wiederzugewinnen, vorausgesetzt, er empfängt erfolgreich k Symbole. Wenn die Ordnung von F kleiner als 2 ^{b ist} , wobei b die Anzahl der Bits in einem Symbol ist, können mehrere Polynome verwendet werden.

Der Sender kann die Symbole k bis n  − 1 'on the fly' konstruieren , dh die Arbeitslast gleichmäßig auf die Übertragung der Symbole verteilen. Wenn der Empfänger seine Berechnungen 'on the fly' durchführen möchte, kann er ein neues Polynom q konstruieren , so dass q ( i ) = p ( i ) wenn Symbol i < k erfolgreich empfangen wurde und q ( i ) = 0 wenn Symbol i < k wurde nicht empfangen. Sei nun r ( i ) = p ( i ) −  q ( i ). Zunächst wissen wir, dass r ( i ) = 0 ist, wenn das Symbol i < k erfolgreich empfangen wurde. Zweitens, wenn Symbol i ≥ k erfolgreich empfangen wurde, dann r ( i ) = p ( i ) -  q ( i ) berechnet werden. Wir haben also genügend Datenpunkte, um r zu konstruieren und auszuwerten, um die verlorenen Pakete zu finden. Sowohl der Sender als auch der Empfänger benötigen also O ( n ( n  −  k )) Operationen und nur O ( n  −  k ) Platz für 'on the fly'.

Umsetzung in der realen Welt

Dieser Prozess wird durch Reed-Solomon-Codes implementiert , wobei Codewörter unter Verwendung einer Vandermonde-Matrix über einem endlichen Feld konstruiert werden .

Nahezu optimale Löschcodes

Nahezu optimale Löschcodes erfordern (1 + ε) k Symbole, um die Nachricht wiederherzustellen (wobei > 0). Das Reduzieren von ε kann auf Kosten der CPU-Zeit erfolgen. Nahezu optimale Löschcodes tauschen Korrekturfunktionen gegen Rechenkomplexität: Praktische Algorithmen können mit linearer Zeitkomplexität codieren und decodieren.

Fontänencodes (auch als ratenlose Löschcodes bekannt ) sind bemerkenswerte Beispiele für nahezu optimale Löschcodes . Sie können eine Nachricht mit k Symbolen in eine praktisch unendlich codierte Form umwandeln , dh sie können eine beliebige Anzahl von Redundanzsymbolen erzeugen, die alle zur Fehlerkorrektur verwendet werden können. Empfänger können mit der Dekodierung beginnen, nachdem sie etwas mehr als k kodierte Symbole empfangen haben .

Das Regenerieren von Codes behebt das Problem der Wiederherstellung (auch Reparatur genannt) verlorener codierter Fragmente aus vorhandenen codierten Fragmenten. Dieses Problem tritt in verteilten Speichersystemen auf, bei denen die Kommunikation zur Aufrechterhaltung der codierten Redundanz ein Problem darstellt.

Anwendungen der Löschcodierung in Speichersystemen

Die klassische Methode zur Wiederherstellung nach Fehlern in Speichersystemen war die Replikation. Die Replikation verursacht jedoch einen erheblichen Overhead in Bezug auf verschwendete Bytes. Daher verwenden immer größere Speichersysteme, wie sie in Rechenzentren verwendet werden, löschcodierte Speicher. Die in Speichersystemen am häufigsten verwendete Form der Löschcodierung ist der Reed-Solomon-Code (RS) . In einem ( k , m ) RS-Code wird ein gegebener Satz von k Datenblöcken, die "Chunks" genannt werden, in ( k + m ) Chunks codiert . Der Gesamtsatz von Chunks besteht aus einem Streifen . Die Codierung erfolgt so, dass man die gesamten Daten wiederherstellen kann , solange mindestens k von ( k + m ) Chunks verfügbar sind. Dies bedeutet, dass ein ( k , m ) RS-codierter Speicher bis zu m Fehler tolerieren kann .

Beispiel: Im RS (10, 4)-Code, der in Facebook für ihr HDFS verwendet wird , werden 10 MB Benutzerdaten in zehn 1-MB-Blöcke aufgeteilt. Dann werden vier zusätzliche 1-MB-Paritätsblöcke erstellt, um Redundanz bereitzustellen. Dies kann bis zu 4 gleichzeitige Ausfälle tolerieren. Der Speicher-Overhead beträgt hier 14/10 = 1,4X.

Bei einem vollständig replizierten System müssen die 10 MB Benutzerdaten viermal repliziert werden, um bis zu vier gleichzeitige Ausfälle zu tolerieren. Der Speicher-Overhead beträgt in diesem Fall 50/10 = 5X.

Dies vermittelt einen Eindruck vom geringeren Speicheraufwand von löschcodierten Speichern im Vergleich zur vollständigen Replikation und damit den Reiz heutiger Speichersysteme.

Beispiele

Hier sind einige Beispiele für Implementierungen der verschiedenen Codes:

Nahezu optimale Löschcodes

• Tornado-Codes
• Paritätsprüfcodes mit niedriger Dichte

Nahezu optimale Fontänencodes (ratelose Löschung)

• Brunnencode
• Online-Codes
• LT-Codes
• Raptor-Codes
• Netzwerkcodes

Optimale Löschcodes

• Parität : Wird in RAID- Speichersystemen verwendet.
• Parchive
• Tahoe-LAFS enthält zfec
• Reed–Solomon-Codes
• Erasure Resilient Systematic Code , ein MDS-Code, der Reed-Solomon in der maximalen Anzahl redundanter Pakete übertrifft, siehe RS(4,2) mit 2 Bits oder RS(9,2) mit 3 Bits
• Codes regenerieren siehe auch Speicher-Wiki .
• jeder andere MDB-Code (eine Art "Maximaler Abstand trennbarer Code")

Sonstiges

• Rechtschreibalphabet

Siehe auch

• Fehlerkorrekturcodes weiterleiten.
• Secret-Sharing (unterscheidet sich darin, dass das ursprüngliche Geheimnis verschlüsselt und verschleiert wird, bis das Decodierungsquorum erreicht ist)

Verweise

Externe Links

• Jerasure ist eine Freie-Software-Bibliothek, die Reed-Solomon- und Cauchy-Löschcodetechniken mit SIMD-Optimierungen implementiert.
• Software FEC in Computer Communications von Luigi Rizzo beschreibt optimale Löschkorrekturcodes
• Feclib ist eine nahezu optimale Erweiterung von Luigi Rizzos Arbeit, die Bandmatrizen verwendet. Viele Parameter können eingestellt werden, wie die Größe der Breite des Bandes und die Größe des endlichen Feldes. Es nutzt auch erfolgreich die große Registergröße moderner CPUs aus. Wie es im Vergleich zu den oben erwähnten nahezu optimalen Codes abschneidet, ist unbekannt.
• Coding for Distributed Storage Wiki zum Regenerieren von Codes und Wiederherstellen von Löschcodes.
• ECIP "Erasure Code Internet Protocol" 1996 entwickelt, war die erste Anwendung von FEC "Forward Error Correction" im Internet. Es wurde zuerst kommerziell verwendet, um Live-Videos von Sir Arthur C. Clarke in Sri Lanka an die UIUC in Indiana zu streamen .