XOR-basierte fehlerresidente Kodierverfahren

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 Me­gabits 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 Co­des 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 wie­der 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 An­zahl der uoch vorhaudeueu Pakete gleich der Anzahl der Pakete der Originalnadiricht ist.

Definition: systematise!!

Ein Code heiftt systematisch, wenn die ersten m Paktete einer Nach­richt 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.

[...]