Raptor-Code - Raptor code
In der Informatik sind Raptor-Codes ( rap id tor nado ; siehe Tornado-Codes ) die erste bekannte Klasse von Fontänencodes mit linearer Zeitcodierung und -decodierung . Sie wurden 2000/2001 von Amin Shokrollahi erfunden und 2004 erstmals als Extended Abstract veröffentlicht. Raptor-Codes sind eine bedeutende theoretische und praktische Verbesserung gegenüber LT-Codes , die die erste praktische Klasse von Fontänen-Codes waren .
Raptor-Codes codieren, wie bei Fontänen-Codes im Allgemeinen, einen gegebenen Quelldatenblock, der aus einer Anzahl k gleich großer Quellsymbole besteht, in eine potenziell unbegrenzte Folge von Codierungssymbolen, so dass der Empfang von beliebigen k oder mehr Codierungssymbolen dem Quellblock ermöglicht, mit einer Wahrscheinlichkeit ungleich null wiederhergestellt werden. Die Wahrscheinlichkeit, dass der Quellblock wiederhergestellt werden kann, nimmt zu, wenn die Anzahl der über k empfangenen Codiersymbole sehr nahe 1 wird, sobald die Anzahl der empfangenen Codiersymbole nur sehr geringfügig größer als k ist . Bei der neuesten Generation von Raptor-Codes, den RaptorQ- Codes, beträgt die Wahrscheinlichkeit eines Decodierungsfehlers, wenn k Codierungssymbole empfangen wurden, weniger als 1%, und die Wahrscheinlichkeit eines Decodierungsfehlers, wenn k+2 Codierungssymbole empfangen wurden, ist geringer als einer von einer Million. ( Weitere Erläuterungen hierzu finden Sie im Abschnitt Wiederherstellungswahrscheinlichkeit und Overhead weiter unten.) Ein Symbol kann eine beliebige Größe haben, von einem einzelnen Byte bis hin zu Hunderten oder Tausenden von Bytes.
Raptor-Codes können systematisch oder nicht-systematisch sein. Im systematischen Fall werden die Symbole des ursprünglichen Quellblocks, dh die Quellsymbole, in den Satz von Codierungssymbolen aufgenommen. Einige Beispiele für einen systematischen Raptor-Code sind die Verwendung durch das 3rd Generation Partnership Project im Mobilfunk und Multicasting sowie durch DVB-H-Standards für IP-Datacast zu Handheld-Geräten (siehe externe Links). Die in diesen Standards verwendeten Raptor-Codes sind auch in IETF RFC 5053 definiert.
Online-Codes sind ein Beispiel für einen nicht systematischen Fontänencode.
RaptorQ-Code
Die fortschrittlichste Version von Raptor ist der RaptorQ-Code, der in IETF RFC 6330 definiert ist. Der RaptorQ-Code ist ein systematischer Code, kann so implementiert werden, dass eine lineare Codierungs- und Decodierungsleistung erreicht wird, hat nahezu optimale Wiederherstellungseigenschaften (siehe Wiederherstellungswahrscheinlichkeit und Weitere Informationen finden Sie im Abschnitt Overhead weiter unten), unterstützt bis zu 56.403 Quellsymbole und kann eine im Wesentlichen unbegrenzte Anzahl von Codierungssymbolen unterstützen.
Der in IETF RFC 6330 definierte RaptorQ-Code ist als Teil des Next Gen TV ( ATSC 3.0 )-Standards spezifiziert , um qualitativ hochwertiges Broadcast-Videostreaming (robustes mobiles TV) und eine effiziente und zuverlässige Übermittlung von Broadcast-Dateien (Datacasting) zu ermöglichen. Insbesondere ist der RaptorQ-Code in A/331 spezifiziert : Signaling, Delivery, Synchronization, and Error Protection within ATSC 3.0 (siehe Liste der ATSC-Standards für eine Liste der ATSC 3.0-Standardteile). Next Gen TV (ATSC 3.0) geht weit über das traditionelle Fernsehen hinaus und bietet ein Broadcast-Internet, das allgemeine Datenbereitstellungsdienste ermöglicht.
Überblick
Raptor-Codes werden durch die Verkettung von zwei Codes gebildet.
Ein Löschcode mit fester Rate , normalerweise mit einer ziemlich hohen Rate, wird als „Vorcode“ oder „Außencode“ verwendet. Dieser Vorcode kann selbst eine Verkettung mehrerer Codes sein, zum Beispiel wird in dem durch 3GPP standardisierten Code ein Paritätsprüfcode hoher Dichte, der aus der binären Gray-Sequenz abgeleitet wird, mit einem einfachen regulären Paritätsprüfcode niedriger Dichte verkettet . Eine andere Möglichkeit wäre eine Verkettung eines Hamming-Codes mit einem Paritätsprüfcode geringer Dichte.
Der innere Code nimmt das Ergebnis der Vorcodierungsoperation und erzeugt eine Folge von Codierungssymbolen. Der innere Code ist eine Form von LT-Codes . Jedes Codierungssymbol ist das XOR eines pseudozufällig ausgewählten Satzes von Symbolen aus der Vorcodierungsausgabe. Die Anzahl von Symbolen, die XOR-verknüpft werden, um ein Ausgabesymbol zu bilden, wird für jedes Ausgabesymbol gemäß einer bestimmten Wahrscheinlichkeitsverteilung pseudozufällig gewählt.
Diese Verteilung sowie der Mechanismus zum Erzeugen von Pseudozufallszahlen zum Abtasten dieser Verteilung und zum Auswählen der mit XOR zu verknüpfenden Symbole müssen sowohl dem Sender als auch dem Empfänger bekannt sein. Bei einem Ansatz wird jedes Symbol von einer Kennung begleitet, die als Startwert für einen Pseudozufallszahlengenerator verwendet werden kann, um diese Informationen zu erzeugen, wobei sowohl der Sender als auch der Empfänger dem gleichen Prozess folgen.
Bei nicht-systematischen Raptor-Codes werden die zu codierenden Quelldaten als Eingabe für die Vorcodierungsstufe verwendet.
Im Fall von systematischen Raptor-Codes wird die Eingabe in die Vorcodierungsstufe erhalten, indem zuerst die Umkehrung der Codierungsoperation, die die ersten k Ausgabesymbole erzeugt, auf die Quelldaten angewendet wird. Somit bewirkt das Anwenden der normalen Codieroperation auf die resultierenden Symbole, dass die ursprünglichen Quellsymbole als die ersten k Ausgabesymbole des Codes regeneriert werden. Es muss sichergestellt werden, dass die Pseudozufallsprozesse, die die ersten k Ausgangssymbole erzeugen, eine invertierbare Operation erzeugen.
Dekodierung
Zum Decodieren von Raptor-Codes sind zwei Ansätze möglich. Bei einem verketteten Ansatz wird der innere Code zuerst decodiert, wobei ein Wahrscheinlichkeitsausbreitungsalgorithmus verwendet wird, wie er für die LT-Codes verwendet wird. Das Decodieren ist erfolgreich, wenn diese Operation eine ausreichende Anzahl von Symbolen wiedergewinnt, so dass der äußere Code die verbleibenden Symbole unter Verwendung des für diesen Code geeigneten Decodieralgorithmus wiederherstellen kann.
Bei einem kombinierten Ansatz werden die Beziehungen zwischen Symbolen, die sowohl durch den inneren als auch den äußeren Code definiert werden, als ein einziger kombinierter Satz simultaner Gleichungen betrachtet, die mit üblichen Mitteln, typischerweise durch Gaußsche Elimination , gelöst werden können .
Rechenkomplexität
Raptor-Codes benötigen O (Symbolgröße) Zeit, um ein Codierungssymbol aus einem Quellblock zu erzeugen, und benötigen O (Quellblockgröße) Zeit, um einen Quellblock aus mindestens k Codierungssymbolen wiederherzustellen .
Wiederherstellungswahrscheinlichkeit und Overhead
Der Overhead besteht darin, wie viele zusätzliche Codierungssymbole über die Anzahl k von Quellsymbolen im ursprünglichen Quellblock hinaus empfangen werden müssen, um den Quellblock vollständig wiederherzustellen. (Auf der Grundlage elementarer informationstheoretischer Überlegungen ist eine vollständige Wiederherstellung eines Quellblocks mit k Quellsymbolen nicht möglich, wenn weniger als k Codierungssymbole empfangen werden.) Die Wiederherstellungswahrscheinlichkeit ist die Wahrscheinlichkeit, dass der Quellblock beim Empfang einer gegebenen Anzahl von . vollständig wiederhergestellt wird zufällige Codierungssymbole, die aus dem Quellblock erzeugt werden.
Der in IETF RFC 6330 angegebene RaptorQ-Code hat den folgenden Kompromiss zwischen Wiederherstellungswahrscheinlichkeit und Wiederherstellungsaufwand:
- Mehr als 99% Wiederherstellungswahrscheinlichkeit mit einem Overhead von 0 Symbolen (Wiederherstellung von k empfangenen Codierungssymbolen).
- Wiederherstellungswahrscheinlichkeit von mehr als 99,99 % mit einem Overhead von 1 Symbol (Wiederherstellung von k+1 empfangenen Codierungssymbolen).
- Mehr als 99,9999% Wiederherstellungswahrscheinlichkeit mit einem Overhead von 2 Symbolen (Wiederherstellung von k+2 empfangenen Codierungssymbolen).
Diese Anweisungen gelten für den gesamten Bereich von k, der in IETF RFC 6330 unterstützt wird, dh k = 1,...,56403. Siehe IETF RFC 6330 für weitere Details.
Rechtsstellung
Qualcomm, Inc. hat eine IPR-Erklärung für den Raptor-Code gemäß IETF RFC 5053 und eine IPR-Erklärung für den fortgeschritteneren RaptorQ-Code gemäß IETF RFC 6330 veröffentlicht. Diese Aussagen spiegeln die Lizenzverpflichtung wider, die Qualcomm, Inc. in Bezug auf den MPEG DASH-Standard . Der MPEG DASH-Standard wurde von einer Vielzahl von Unternehmen eingesetzt, darunter Mitgliedsunternehmen des DASH Industry Forum.
Siehe auch
Anmerkungen
Verweise
- Shokrollahi, Amin, "Raptor Codes", IEEE Transactions on Information Theory, vol. 52, S. 2551-2567, 2006. PDF (Login erforderlich)
- ATSC 3.0 (Advanced Television Standards Committee 3.0)
- 3GPP (Das Partnerschaftsprojekt der 3. Generation)
- DVB (Digitale Videoübertragung)
- 3GPP TS26.346 3GPP Technische Spezifikation für Multimedia Broadcast/Multicast Service: Protokolle und Codecs.
- RFC5053 Raptor Forward Error Correction Scheme für die Objektlieferung
- DVB-H IP Datacasting-Spezifikationen
- RFC6330 RaptorQ Forward Error Correction Scheme für die Objektlieferung
- [1] "IPR"-Suchergebnis für RFC 5053, mit Aussagen einiger Patentinhaber
- [2] "IPR"-Suchergebnis für RFC 6330, mit Aussagen einiger Patentinhaber
