Proseminar: Redundanz

Vortrag 3: Lineare Binärcodes

Hanna Hakala



Einleitung

Angenommen, es werden Nachrichten in binärer Form über einen Datenkanal gesendet. Ist der Kanal gestört, kann es vorkommen, dass einzelne Bits "umkippen": aus einer Eins wird eine Null oder umgekehrt. Solche Störungen können dazu führen, dass die Nachricht unbrauchbar wird. Noch schlimmer ist es, wenn der Empfänger eine falsche Nachricht bekommt. Durch geschickte Codierung von Nachrichten können solche Effekte oft vermieden werden.

Die Theorie von linearen Binärcodes auf dieser Seite basiert auf drei Annahmen:

Symmetrie des Datenkanales bedeutet, dass Nullen mit der gleichen Wahrscheinlichkeit zu Einsen werden, wie umgekehrt. Die Unabhängigkeit der Fehler bedeutet, dass die Fehler sowohl von anderen Fehlern als auch von der Nachricht unabhängig sind. Die dritte Annahme schließt büschelgestörte Kanäle aus, in denen die Fehlerquote sich zeitlich im bestimmten Rytmus ändert, und zwar von sehr hoch zu sehr niedrig. In der Praxis sind diese Bedingungen selten erfüllt.

Ein symmetrischer Binärkanal mit Fehlerwahrscheinlichkeit p


Erwünschte Redundanz bedeutet das Setzen von zusätzlichen Bits in der zu sendende Nachricht, und zwar so, dass sich verschiedene Nachrichten möglichst viel voneinander unterscheiden. Dadurch wird erreicht, dass eine gestörte Nachricht mehr der originalen als einer anderen korrekten Nachricht ähnelt. Später wird gezeigt, dass die Wahrscheinlichkeit, die tatsächlich gesendete Nachricht aus der empfangenen, gestörten Nachricht zu erhalten desto größer ist, je mehr Redundanz die Nachrichten enthalten. Die Übertragungsgeschwindigkeit leidet aber unter der Redundanz. Zusammenfassend kann man sagen, dass Übertragungssicherheit immer gegen Übertragungsgeschwindigkeit eingetauscht wird.


Codierung

Bestimmen von Codewörtern mit Kontrollmatrix

Eine Nachricht, die aus k Zeichen u1u2.....uk (ui = 0/1) besteht, wird in ein Codewort x1x2.....xn (xi=0/1) kodiert, wobei n>=k ist. n ist die Länge des Codes. Die Codewörter für alle verschiedenen Nachrichten mit k Zeichen bilden den Code.

Bei systematischen linearen Codes ist der erste Teil vom Codewort die Nachricht selbst. Dazu kommen n-k Kontrollzeichnen (Parity Check Bits). Um die Kontrollzeichen zu bestimmen, definiert man eine Kontrollmatrix ( parity check matrix ) H wie folgt:

H = [ A | In-k ]

wobei A irgendeine (n-k)*k-Matrix und In-k die (n-k)*(n-k)-Einheitsmatrix ist. Es soll dann gelten:

H * xtr = 0

1. Beispiel
011100x10
011010*x2=0
110001x30
x40
x50
x60
 Gleichungen sehen dann so aus:

x2 + x3 + x4 = 0
x1 + x3 + x5 = 0
x1 + x2 + x6 = 0