1 Einführung

Das Szenario ist wie folgt:

Auf einer Verbindung werden mit dem XOR-Code kodierte Pakete übertragen. Dabei gehen Pakete verloren. Ein Paket erreicht entweder unbeschadet das Ziel oder es geht komplett verloren. Die Möglichkeit, dass empfangene Pakete Fehler enthalten, gibt es nicht. Der Zielcomputer kann aus den restlichen Paketen die Originalnachricht wieder herstellen.

Die Wünsche an Kodierungsverfahren sind,

• dass sie schnell sind. Ein optimales Kodierungsverfahren läuft in linearer Zeit. Ein solches Kodierungsverfahren ist aber bislang noch nicht gefunden worden. Das XOR-Kodierungsverfahren läuft in quadratischer Zeit. Durch die Möglichkeit Multiplikationen durch XORs zu ersetzen, wird ein weiterer Geschwindigkeitsgewinn erlangt. So ist das XOR-Kodierungsverfahren in der Lage eine Bitrate von einigen Megabits pro Sekunde zu erreichen, welches z.B. für Videoübertragungen mittlerer Qualität genutzt werden kann.

• dass möglichst viele Pakete verloren gehen dürfen. Idealerweise dürfen soviele Pakete verloren gehen, wie der Kodierungsalgorithmus zu der unkodierten Nachricht hinzugefügt hat. Man nennt einen Code, der solches leistet maximum distance seperable (MDS). Unser XOR-Code leistet dies.

XOR-Codes sind eine angepaÿte Version der Reed-Solomon-Codes. Diese Codes nden in der Praxis groÿe Anwendung. Beispielsweise werden sie in der Raumfahrt von der NASA ab dem Voyager-Flug im Jahre 1977 standardmäÿig zur Datenübertragung, wie zum Beispiel zur Bildübertragung, benutzt. Es ist klar, dass hier zerstörte Pakete nicht einfach neu angefordert können, weil die Signallaufzeit, obwohl das Signal mit Lichtgeschwindigkeit reist, extrem lang ist und gesendete Daten vielleicht in der Raumsonde schon wieder gelöscht sind. Weitere Anwendungen sind zu nden bei CDs, DVDs, Barcodes, Mobilkommunikation, Wireless-LAN, Satelliten-Kommunikation, digitales Fernsehn, DSL ... .

2

2 Denitionen

Definition: Kodierungsschema / Kodieralgorithmus

Ein (m, n, b, r)-Kodierungsschema besteht aus einem Kodierungsalgorithmus (in unserem Fall XOR), der eine Nachricht M = (M 1 , . . . , M m )

bestehend aus m Paketen jedes Paket aus b Bits bestehend auf eine kodierte Nachricht E(M ) = (E 1 (M ), . . . , E n (M ))

abbildet, in welcher wieder die Pakete aus b Bits bestehen. r Pakete der kodierten Nachricht reichen aus, um die Originalnachricht M wieder herzustellen. Die einzelnen Werte in der Übersicht: • m: Anzahl der Pakete der Originalnachricht • n: Anzahl der Pakete der kodierten Nachricht • b: Anzahl der Bits pro Paket

• r: Anzahl der Pakete der kodierten Nachricht, aus denen die Originalnachricht wiederhergestellt werden kann. Somit dürfen maximal n − r Pakete auf dem Übertragungsweg verloren gehen, damit eine Dekodierung möglich ist.

Definition: Maximum distance seperable (MDS)

Ein Code heiÿt Maximum distance seperable kurz MDS, wenn gilt r = m.

D.h. es dürfen maximal soviele Pakete verlorengehen, so dass die Anzahl der noch vorhandenen Pakete gleich der Anzahl der Pakete der Originalnachricht ist.

Definition: systematisch

Ein Code heiÿt 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 Informationspakete genannt; die restlichen n − m Pakete redundante Pakete.

3

Definition: linear

Ein Code heiÿt linear, wenn die Abbildung, die aus der nicht kodierten eine kodierte Nachricht macht, eine lineare Abbildung ist. Da diese Abbildung linear ist, kann sie somit durch eine Matrix beschrieben werden. Diese Matrix nennt man Generatormatrix. Ein Code ist systematisch, wenn die ersten m Zeilen der Generatormatrix die Identitätsmatrix bilden.

Definition: endlicher Körper

Ein endlicher Körper (auch endlicher Feld oder Galois Feld genannt) ist eine endliche Menge in der die Körperaxiome gelten, welche da sind Kommutativgesetz, Assoziativgesetz, neutrales Element der Addition und Multiplikation und Distributivgesetz. Ein solches Feld hat eine Ordnung p, welche die Gröÿe des Feldes darstellt. Man schreibt oder moderner GF [p] F p

Eine Restklasse der Mächtigkeit p stellt einen Körper dar, wenn p eine Primzahl ist. Beispiel ist der endliche Körper GF [2], welcher folgende Additions und Multiplikationstabelle besitzt:

Definition: Polynomkörper

GF [2 L ]

ist ein Körper der Polynome (L−1)-ten Grades über GF [2]. Der Körper der Polynome GF [2 ⁴ ] sieht wie folgt aus: 0 0 · x ³ + 0 · x ² + 0 · x ¹ + 0 · x 0

1 0 · x ³ + 0 · x ² + 0 · x ¹ + 1 · x ⁰ 2 0 · x ³ + 0 · x ² + 1 · x ¹ + 0 · x ⁰ 3 0 · x ³ + 0 · x ² + 1 · x ¹ + 1 · x ⁰ 4 0 · x ³ + 1 · x ² + 0 · x ¹ + 0 · x ⁰ 5 0 · x ³ + 1 · x ² + 0 · x ¹ + 1 · x ⁰ 6 0 · x ³ + 1 · x ² + 1 · x ¹ + 0 · x ⁰ 7 0 · x ³ + 1 · x ² + 1 · x ¹ + 1 · x ⁰ Definition: Nichtreduzierbares Polynom

Ein Polynom p(x) ∈ GF [X] wird nicht redzierbar über GF [X] genannt,

4