Grundlagen der Informatik
Kapitel 4: Kanalcodierung

In den vorangegangenen Kapiteln haben wir gesehen, wie wir Nachrichten aus einer Quelle heraus möglichst kompakt, also mit niedriger mittlerer Codelänge codiert. Bei der Kanalcodierung geht es darum, Nachrichten so zu codieren, dass sie auch nach dem passieren eines Kanals, der die Nachricht unter umständen verzerrt bzw. verrauscht überträgt, wieder entziffert werden kann.

4.1 Paritätskontrollcodes

Wir wollen im folgenden Nachrichten betrachten, die k Informationsstellen besitzen. Die codierte Nachricht habe dann insgesamt n Stellen und besteht aus k Informationsbits und n-k Prüfbits.

Beispiel: Aus Nachrichten mit sieben Stellen codieren wir Codewörter mit 8 Stellen, es wird also ein Prüfbit angehängt.

Bei den Paritätscontrollcodes handelt es sich um solche Codes, deren Prüfbits eine Aussage über die Anzahl von Einsen oder Nullen in einer Nachricht zulassen. Wir unterscheidern zwischen gerader und ungerader Parität. Arbeitet man mit gerader Paritätskontrolle, so wird die Nachricht so ergänzt, dass zusammen mit den Prüfbits gerade Parität (eine gerade Anzahl von Einsen) vorliegt. Bei ungerader Parität wird entsprechend auf eine ungerade Anzahl von Einsen ergänzt.

Beispiel: Wir betrachten die Nachricht 0110101 und wollen eine Prüfstelle anhängen. Unsere Nachricht enthält vier Einsen, das heißt bei gerader Parität müssen wir eine Null anhängen, damit die gerade Anzahl erhalten bleibt, für die ungerade Parität hängen wir eine Eins an und erhalten eine ungerade Anzahl von Einsen.

Betrachten wir einen Kanal, bei dem die Wahrscheinlichkeit, dass eine Stelle gestört ist, immer gleich ist. Das heißt, für jedes übertragene Bit ist die Wahrscheinlichkeit p eines Fehlers gleich groß. Wir sprechen dann vom sogenannten weißen Rauschen. Wie sich Beweisen lässt, ist dann die Wahrscheinlichkeit w, dass ein Fehler bei der Übertragung nicht erkannt wird, wie folgt zu berechnen:

Mit einem Prüfbit kann man zwar Fehler erkennen, aber noch lange nicht korrigieren. Unser Ziel ist es jedoch, ein falsch übertragenes Codewort wieder in die entsprechende Nachricht zu korrigieren. Dazu bedient man sich zum Beispiel der Rechteckcodes, bei denen die Nachricht zunächst als Rechteck aufgeschrieben wird und dann jeweils jede Zeile und jede Spalte einzeln auf gerade oder ungerade Parität ergänzt wird. Sehen wir uns ein Beispiel an:

Beispiel: Wir betrachten eine Nachricht mit k=9 Informationsstellen: 010 110 111. Schreiben wir uns die Nachricht als 3x3 - Matrix auf und ergänzen auf gerade Parität:

Die grün gekennzeichneten Bits entsprechen unserer Nachricht, die schwarzen Bits sind die Prüfbits für gerade Parität. Das rote Bit in der Ecke ergänzt die Prüfpits auf gerade Parität. Sehen wir uns nun mal drei mögliche Übertragungsfehler an:

Die blau gekennzeichneten Bits sind falsch Übertragen worden.

Beispiel 1: Der Decodierer erkennt Paritätsfehler in Zeile 2 und Spalte 2, er erkennt das entsprechende Bit als falsch und dreht es um (auf 1). Die Nachricht konnte decodiert werden, der Fehler wurde entfernt.
Beispiel 2: Der Decodierer erkennt einen Fehler in Spalte 2, findet aber keine entsprechenden Zeilenfehler. Auserdem ist das rote Paritätsprüfbit falsch. Der Fehler wird richtig dem Prüfbit der 2. Spalte zugeordnet. Die Informationsbits werden als richtig erkannt.
Beispiel 3: Der Decodierer erkennt Fehler in der 1. und dritten Zeile, jedoch in keiner Zeile. Da wir nicht wissen, ob die Paritäts- oder die Informationsbits falsch sind, können wir den Fehler zwar erkennen, aber nicht eindeutig decodieren. Die Information kann nicht decodiert werden, die Nachricht muss erneut übermittelt werden.

Erkentniss: Wir können Einzehlfehler korrigieren und Doppelfehler erkennen.

4.2 Hamming Metrik

Die Hamming Metrik hilft uns, Aussagen über den Abstand zweier Codewörter zueinander zu machen. Dieser Abstand d gibt an, in wie vielen Stellen sich die beiden Wörter unterscheiden ( 010 unterscheidet sich von 111 in 2 Stellen -> d( 010, 111 ) = 2 ). Wir überprüfen, wie groß der Abstand von einem empfangenen Wort zu den Codewörtern ist. Der Abstand gibt dann gleich die Anzahl der Fehler bei der Übertragung. Veranschaulichen kann man das in einem Würfel, weshalb man auch die Menge der Codewörter mit W(n) bezeichnet, wobei n die Anzahl der Bits eines Wortes ist. Es gibt dann wieder 2^n Codewörter. Für n=3 kann man dann tatsächlich einen Würfel aufzeichnen und seine Eckpunkte mit den Codewörtern von 000 bis 111 beschriften. Dabei unterscheiden sich benachbarte Punkte um nur ein Bit, ihr Abstand ist eins.

Bei der Mindestabstandsdecodierung legt man fest, welchen Abstand zwei beliebige Codewörter aus W(n) mindestens haben müssen. Damit können wir einen speziellen Code definieren: den (n, M, d)-Code, wobei n die Anzahl der Bits in einem Wort, M die Anzahl der Codeworte und d der Mindestabstand ist. Damit lassen sich bis zu 0.5( d - 1 ) Fehler korrigieren. q.e.d.

Wir müssen uns damit auseinander setzen, einen Algorithmus zur Berechnung der maximalen Anzahl der Codewörter bei gegebenem n und d zu finden. Für n = d ist dies trivial ( M = 2: 0. . . 0 und 1 . . . 1 ), ebenso für d = 1 ( M = 2^n, weil sich jedes Codewort ja mindestens um 1 von jedem anderen unterscheidet, sonst wären sie ja gleich). Aber für n = 10, d = 3 lässt sich das schon nicht mehr vernünftig berechnen. Wir können nur eine Abschätzung der oberen Grenze vornehmen um eine Anzahl A(n,d) zu gewinnen. Sei e=0.5(d-1):

Unser Ziel ist es, perfekte Codes zu entwickeln. Dazu muss gelten:

1. Der Mindestabstand der Codewörter ist 2e + 1

2. Die Anzahl der Codewörter ist eine Potenz von 2. Der Exponent sei k

Sei C ein Code, |C| = 2^k. Ist C perfekt, so gilt: