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
1 Einfiihrung
Das Szenario ist. wie folgt:
Abbildung in dieser Leseprobe nicht enthalten
Auf einer Verbinclung werden rriit derri XOR-Code kodierte Paket.e ubert.ra- gen. Dabei gehen Paket.e verloren. Ein Paket. erreicht entweder unbeschadet das Ziel oder es geht komplett verloren. Die Moglichkeit, class empfangene Paket.e Fehler enthalten, gibt. es nicht. Der Zielcomputer kann aus den rest- lichen Paketen die Originalnachricht wieder herstellen.
Die Wunsclre an Kodierungsverfa.hren sind,
- dass sie schnell sind. Ein optimales Kodierungsverfahren lauft in li- nearer Zeit. Ein solches Kodierungsverfahren ist. aber bislang noch nicht. gefunden worden. Das XOR,-Kodierungsverfahren lauft in qua- dratischer Zeit.. Durch die Moglichkeit. Multiplikationen durch XORs zu ersetzen, wire! ein weiterer Geschwindigkeit.sgewinn erlangt. So ist. das XOR-Kodierungsverfahren in der Lage eine Bitrate von einigen Megabits pro Sekunde zu erreichen, welches z.B. fur Videoubertragungen init.t.lerer Qualitat genutzt werden kann.
- dass moglichst viele Pakete verloren gehen diirfen. Idealerweise diirfen soviele Paket.e verloren gehen, wie der Kodierungsalgorithmus zu der unkodierten Nachricht hinzugefiigt hat. Man nennt einen Code, der solches leistet maximum distance seperable (MDS). Unser XOR-Code leistet dies.
XOR,-Codes sind eine angepafst.e Version der Reed-Solomon-Codes. Diese Codes hnden in der Praxis grofse Anwendung. Beispielsweise werden sie in der Ra.umfa.hrt von der NASA ab derri Voyager-Flug irn Jahre 1977 standardma- fsig zur Datenubertragung, wie zurn Beispiel zur Bildubert.ragung, benutzt. Es ist. klar, class hier zerstorte Paket.e nicht. einfach neu angefordert konnen, weil die Signahaufzeit., obwohl das Signal rriit. Licht.geschwindigkeit. reist, ex- t.rein lang ist. und gesendet.e Dat.en vieheicht. in der R.aumsonde schon wieder geloscht. sind. Weit.ere Anwendungen sind zu hnden bei CDs, DVDs, Barcodes, Mobilkommunikation, Wireless-LAN, Satelliten-Kommunikat.ion, digit, ales Fernsehn, DSL
2 Definitionen
Definition: Kodierungsschema / Kodieralgorithmus
Ein (m, n, b, r)-Kodierungsschema besteht aus einem Kodierungsalgo- rithmus (in unserem Fall XOR), der eine Nacliriclit
M = (Mi,...,Mm)
bestehend aus m Paketen - jedes Paket aus b Bits bestehend - auf eine kodierte Nacliriclit
E (M) = (Ei(M ),...,En(M))
abbildet, in welcher wieder die Pakete aus b Bits bestehen. r Pakete der kodierten Nachricht reichen aus, um die Originalnadiricht M wieder lierzustellen.
Die einzelnen Werte in der Ubersiclit:
- m: Anzahl der Pakete der Originalnadiricht
- n: Anzahl der Pakete der kodierten Nachricht
- b: Anzahl der Bits pro Paket
- r: Anzahl der Pakete der kodierten Nachricht, aus denen die Ori- ginalnachricht wiederhergestellt werdeu kauu.
Somit diirfen maximal n — r geheu, darriit eiue Dekodieruug rrioglich ist.
Definition: Maximum distance seperable (MDS)
Ein Code heiftt Maximum distance seperable kurz MDS, weuu gilt r = m.
D.h. es diirfen maximal soviele Pakete verlorengehen, so dass die Anzahl der uoch vorhaudeueu Pakete gleich der Anzahl der Pakete der Originalnadiricht ist.
Definition: systematise!!
Ein Code heiftt systematisch, wenn die ersten m Paktete einer Nachricht M die Nachricht selbst enthalten. Die restlichen Pakete sind red- undante Informationen. Die ersten m Pakete werden Informations- pakete genannt; die restlichen n — m Pakete redundante Pakete.
[...]
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.