Nachrichten müssen häufig über ungesicherte Kanäle, wie zum Beispiel das Internet, übertragen werden. Unsichere Kanäle zeichnen sich dadurch aus, dass sie keine Garantie darüber geben können, ob versandte Nachrichten auch tatsächlich das Ziel erreichen. Viele Verfahren bei Duplexverbindungen nutzen die Möglichkeit, zerstörte Pakete neu anzufordern. Häufig ist jedoch wegen der langen Zeit, die man auf solche duplizierten Datenpakete warten muss, oder wegen einer Simplexverbindung dies nicht möglich. Man wünscht sich deshalb ein Verfahren, welches zusätzliche redundante Informationen zu den eigentlichen Daten hinzufügt, durch die es möglich ist, verloren gegangene Daten zu rekonstruieren. Das XOR-Kodierverfahren leistet genau dies. Im folgenden wird vorgestellt, wie es dies in quadratischer Zeit tut, wodurch es in der Lage ist, Echtzeitdaten z.B. Echtzeitvideoübertragung in hoher Geschwindigkeit zu kodieren und zu dekodieren.
Inhaltsverzeichnis
1 Einführung
2 Definitionen
3 Arbeitsweise eines linearen Codes
4 Der Isomorphismus τ
5 Cauchymatrix
6 Konstruktion und Kodierung des XOR-Codes
7 Dekodierung
8 Implementationsdetails
9 Referenzen
Zielsetzung und thematische Schwerpunkte
Ziel der Arbeit ist die Vorstellung und Analyse eines fehlerresistenten Kodierverfahrens auf Basis von XOR-Operationen, das durch Hinzufügen redundanter Informationen eine effiziente Rekonstruktion verlorener Datenpakete in Echtzeit ermöglicht.
- Mathematische Grundlagen von Kodierungsschemata und linearen Codes
- Einsatz von Isomorphismen und Endlichen Körpern zur effizienten Berechnung
- Verwendung der Cauchymatrix für die Erstellung fehlerresistenter XOR-Codes
- Detaillierte Analyse des Kodierungs- und Dekodierungsprozesses
- Implementationsaspekte und Laufzeitoptimierungen für die praktische Anwendung
Auszug aus dem Buch
Der Isomorphismus τ
Zum Kodieren und Dekodieren der Nachrichten benötigen wir beim XOR-Code XORs. Diese sind Blockweise gegeben, d.h. wir können immer mehrere Bits gleichzeitig XORs berechnen. Um diese Parallelität benutzen zu können, transformieren wir mit τ.
Sei GF[2][X] der Körper der Polynome über GF[2]. Sei p(X) ein nichtreduzierbares Polynom (L-1)-ten Grades. Dann ist GF[2L] isomorph zu GF[2][X]/p(X).
Wir können weiter die Elemente des Körpers GF[2L] durch den Isomorphismus τ als Matrix darstellen. Wir betrachten dazu die Koeffizienten eines Polynoms f ∈ GF[2L]:
f(X) = ∑ fiXi, fi ∈ GF[2] ist i-ter Koeffizient
Sei nun τ(f) für unser f ∈ GF[2L] die Matrix, deren i-te Spalte der Koeffizientenvektor von Xi-1 f mod p(X) ist.
Zusammenfassung der Kapitel
1 Einführung: Das Szenario der verlustbehafteten Nachrichtenübertragung wird erläutert und die Notwendigkeit von XOR-basierten Kodierverfahren aufgezeigt.
2 Definitionen: Zentrale Begriffe wie Kodierungsschema, Maximum Distance Separable (MDS), Endlicher Körper und Polynomkörper werden präzise definiert.
3 Arbeitsweise eines linearen Codes: Es wird dargelegt, wie Nachrichten mittels einer Generatormatrix kodiert und mittels Invertierung wieder rekonstruiert werden können.
4 Der Isomorphismus τ: Dieser Abschnitt beschreibt die mathematische Transformation von Elementen in Matrizen, um XOR-Operationen parallel und effizient durchführen zu können.
5 Cauchymatrix: Die Eigenschaften der Cauchymatrix hinsichtlich Invertierbarkeit und Determinantenberechnung werden als Grundlage für den XOR-Code vorgestellt.
6 Konstruktion und Kodierung des XOR-Codes: Hier erfolgt die konkrete Anwendung der vorherigen mathematischen Konzepte zur Erstellung eines MDS-Codes.
7 Dekodierung: Der dreistufige Algorithmus zur Wiederherstellung verloren gegangener Informationen wird detailliert erläutert.
8 Implementationsdetails: Praktische Hinweise zur Programmierung und zur Optimierung der Rechenzeit bei der Kodierung und Dekodierung werden gegeben.
9 Referenzen: Eine Auflistung der verwendeten Literatur und Quellen für die theoretischen Grundlagen.
Schlüsselwörter
XOR-Code, Fehlerresistenz, Datenübertragung, Kodierungsverfahren, Rekonstruktion, Cauchymatrix, MDS-Code, Isomorphismus, Endliche Körper, Polynomkörper, Generatormatrix, Dekodierung, Redundanz, Fehlerkorrektur, Echtzeit-Übertragung.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundlegend?
Die Arbeit behandelt die Entwicklung und Implementierung eines fehlerresistenten Verfahrens zur Datenübertragung, das auf der XOR-Kodierung basiert, um Datenverluste bei der Übertragung über ungesicherte Kanäle auszugleichen.
Was sind die zentralen Themenfelder?
Die zentralen Themen umfassen Informationstheorie, lineare Algebra (insbesondere Matrizen und Determinanten) sowie die Anwendung algebraischer Strukturen wie endlicher Körper auf praktische Probleme der Nachrichtentechnik.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Erstellung eines Kodierverfahrens, das in quadratischer Zeit arbeitet und es ermöglicht, verlorene Datenpakete durch Hinzufügung redundanter Informationen ohne erneute Anforderung zu rekonstruieren.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine mathematisch-theoretische Herleitung verwendet, die auf der Theorie linearer Codes und der Matrixinvertierung (speziell mittels Cauchymatrix) basiert, ergänzt durch algorithmische Ansätze zur effizienten Umsetzung.
Was wird im Hauptteil behandelt?
Der Hauptteil erstreckt sich von der Definition der mathematischen Voraussetzungen (Körper, Polynome) über den Aufbau des XOR-Codes und den Isomorphismus bis hin zur praktischen Dekodierung und Implementierung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird maßgeblich durch Begriffe wie XOR-Code, Cauchymatrix, MDS-Code, Fehlerresistenz und Redundanz charakterisiert.
Warum wird der Isomorphismus τ für den XOR-Code verwendet?
Der Isomorphismus τ dient dazu, Feldoperationen in Matrizenoperationen zu überführen, was eine parallele Verarbeitung der XOR-Operationen ermöglicht und somit die Rechengeschwindigkeit steigert.
Was macht den beschriebenen Code zu einem "Maximum Distance Separable" (MDS) Code?
Ein Code ist MDS, wenn die Anzahl der Informationen, die verloren gehen können, exakt der Anzahl der redundanten Pakete entspricht, was die maximale Effizienz bei der Fehlerwiederherstellung bedeutet.
- Quote paper
- Christoph Tornau (Author), 2004, XOR-basierte fehlerresidente Kodierverfahren, Munich, GRIN Verlag, https://www.grin.com/document/23497
