Brunnencode - Fountain code

In der Codierungstheorie sind Fontänencodes (auch als Rateless Erasure Codes bekannt ) eine Klasse von Erasure Codes mit der Eigenschaft, dass eine potenziell unbegrenzte Folge von Codierungssymbolen aus einem gegebenen Satz von Quellsymbolen erzeugt werden kann, so dass die ursprünglichen Quellsymbole idealerweise aus einer beliebigen Teilmenge der Codierungssymbole mit einer Größe gleich oder nur geringfügig größer als die Anzahl der Quellsymbole wiederhergestellt. Der Begriff Fountain oder Rateless bezieht sich darauf, dass diese Codes keine feste Coderate aufweisen .

Ein Fontänencode ist optimal, wenn die ursprünglichen k Quellsymbole aus irgendwelchen k erfolgreich empfangenen Codierungssymbolen wiederhergestellt werden können (dh ohne diejenigen, die gelöscht wurden). Fountain Codes bekannt , die ein effiziente Codierung hat und Decodierung Algorithmen und, mit denen der Wiederherstellung der ursprünglichen k Quellensymbole von jedem k ‚ der Codierung Symbole mit hohen Wahrscheinlichkeit, wo k‘ ist nur geringfügig größer ist als k .

LT-Codes waren die erste praktische Umsetzung von Fontänencodes. Raptor - Codes und Online - Codes wurden anschließend eingeführt und erreichen lineare Zeit - Codierung und -Decodierung Komplexität durch eine Vorcodierung Stufe der Eingangssymbole.

Anwendungen

Fontänencodes sind bei einer festen Coderate flexibel anwendbar oder wo eine feste Coderate nicht a priori bestimmt werden kann und wo eine effiziente Codierung und Decodierung großer Datenmengen erforderlich ist.

Ein Beispiel ist das eines Datenkarussells , bei dem eine große Datei kontinuierlich an eine Reihe von Empfängern gesendet wird. Bei Verwendung eines Festraten-Löschcodes steht ein Empfänger, dem ein Quellsymbol fehlt (aufgrund eines Übertragungsfehlers), vor dem Problem des Coupon-Sammlers : Er muss erfolgreich ein Codierungssymbol empfangen, das er noch nicht hat. Dieses Problem wird bei der Verwendung eines herkömmlichen Löschcodes kurzer Länge noch deutlicher, da die Datei in mehrere Blöcke aufgeteilt werden muss, die jeweils separat codiert werden: Der Empfänger muss nun für jeden Block die erforderliche Anzahl an fehlenden Codierungssymbolen sammeln . Unter Verwendung eines Fontänencodes reicht es für einen Empfänger aus, jede Teilmenge von Codierungssymbolen abzurufen, deren Größe etwas größer ist als die Menge der Quellsymbole. (In der Praxis wird die Sendung in der Regel von einem Betreiber basierend auf den Eigenschaften des Netzwerks und der Empfänger und der gewünschten Lieferzuverlässigkeit für einen festen Zeitraum geplant, und daher wird der Fontänencode mit einer Coderate verwendet, die dynamisch zu dem Zeitpunkt bestimmt wird, wenn die Datei soll gesendet werden.)

Eine weitere Anwendung ist die Hybrid-ARQ in zuverlässigen Multicast- Szenarien: Paritätsinformationen, die von einem Empfänger angefordert werden, können potenziell für alle Empfänger in der Multicast-Gruppe nützlich sein .

Brunnencodes in Normen

Raptor-Codes sind derzeit die effizientesten Fontänencodes, die sehr effiziente lineare Zeitcodierungs- und -decodierungsalgorithmen aufweisen und nur eine kleine konstante Anzahl von XOR- Operationen pro erzeugtem Symbol sowohl für die Codierung als auch für die Decodierung erfordern . IETF RFC 5053 legt im Einzelnen ein systematischer Raptor - Code, der über die IETF in mehrere Standards angenommen wurde, wie in der 3GPP - MBMS - Standard für Broadcast - Datei Lieferung und Streaming - Dienste, die DVB-H IPDC Standard für die Bereitstellung von IP - Dienste über DVB - Netzwerke , und DVB-IPTV zur Bereitstellung kommerzieller TV-Dienste über ein IP-Netzwerk. Dieser Code kann mit bis zu 8.192 Quellsymbolen in einem Quellblock verwendet werden, und insgesamt werden bis zu 65.536 codierte Symbole für einen Quellblock generiert. Dieser Code hat einen durchschnittlichen relativen Empfangs-Overhead von 0,2%, wenn er auf Quellblöcke mit 1.000 Quellsymbolen angewendet wird, und hat einen relativen Empfangs-Overhead von weniger als 2% mit einer Wahrscheinlichkeit von 99,9999%. Der relative Empfangs-Overhead ist definiert als die zusätzlichen Codierungsdaten, die über die Länge der Quelldaten hinaus erforderlich sind, um die ursprünglichen Quelldaten wiederherzustellen, gemessen als Prozentsatz der Größe der Quelldaten. Wenn beispielsweise der relative Empfangs-Overhead 0,2% beträgt, bedeutet dies, dass Quelldaten der Größe 1  Megabyte aus 1,002 Megabyte Codierungsdaten wiederhergestellt werden können.

Ein fortschrittlicher Raptor-Code mit größerer Flexibilität und verbessertem Empfangs-Overhead, genannt RaptorQ, wurde in IETF RFC 6330 spezifiziert. Der angegebene RaptorQ-Code kann mit bis zu 56.403 Quellsymbolen in einem Quellblock verwendet werden und insgesamt bis zu 16.777.216 kodiert für einen Quellblock generierte Symbole. Dieser Code ist in der Lage, einen Quellblock mit hoher Wahrscheinlichkeit aus einem beliebigen Satz codierter Symbole gleich der Anzahl von Quellsymbolen im Quellblock und in seltenen Fällen aus etwas mehr als der Anzahl von Quellsymbolen im Quellblock wiederherzustellen. Der RaptorQ-Code ist ein integraler Bestandteil der ROUTE-Instanziierung, die in ATSC A-331 (ATSC 3.0) spezifiziert ist.

Fontänencodes zur Datenspeicherung

Löschcodes werden in Datenspeicheranwendungen aufgrund massiver Einsparungen bei der Anzahl von Speichereinheiten für ein bestimmtes Maß an Redundanz und Zuverlässigkeit verwendet. Die Anforderungen an das Design von Löschcode für die Datenspeicherung, insbesondere für verteilte Speicheranwendungen, können sich in Bezug auf Kommunikations- oder Datenstreaming-Szenarien stark unterscheiden. Eine der Anforderungen an die Codierung von Datenspeichersystemen ist die systematische Form, dh die ursprünglichen Nachrichtensymbole sind Teil der codierten Symbole. Die systematische Form ermöglicht das Ablesen der Nachrichtensymbole ohne Entschlüsselung aus einem Speicher. Da außerdem die Bandbreite und die Kommunikationslast zwischen Speicherknoten ein Engpass sein können, sind Codes, die eine minimale Kommunikation ermöglichen, besonders dann sehr vorteilhaft, wenn ein Knoten ausfällt und eine Systemrekonstruktion erforderlich ist, um das anfängliche Redundanzniveau zu erreichen. In dieser Hinsicht wird erwartet, dass Fontänencodes einen effizienten Reparaturprozess im Fehlerfall ermöglichen: Wenn ein einzelnes codiertes Symbol verloren geht, sollte es nicht zu viel Kommunikation und Berechnung zwischen anderen codierten Symbolen erfordern, um das verlorene Symbol wiederzubeleben. Tatsächlich kann die Reparaturlatenz manchmal wichtiger sein als die Einsparung von Speicherplatz. Reparierbare Fontänencodes werden projiziert, um die Designziele von Fontänencodes für Speichersysteme zu erreichen. Eine ausführliche Übersicht über Fontänencodes und deren Anwendung finden Sie unter.

Ein anderer Ansatz für verteilte Speicherung mit Fontänencodes wurde in Liquid Cloud Storage vorgeschlagen. Liquid Cloud Storage basiert auf der Verwendung eines großen Löschcodes wie dem RaptorQ-Code, der in IETF RFC 6330 spezifiziert ist (der einen erheblich besseren Datenschutz bietet als andere Systeme) und einen Hintergrundreparaturprozess verwendet (der die Anforderungen an die Reparaturbandbreite im Vergleich zu anderen Systemen erheblich reduziert) ) und die Verwendung einer Stream-Datenorganisation (die einen schnellen Zugriff auf Daten ermöglicht, auch wenn nicht alle codierten Symbole verfügbar sind).

Siehe auch

Anmerkungen

Verweise