t-fehlerkorrigierende Codes

Die Menge aller Codewörter nennt man einen Code . Der Abstand zweier Codewörter ist die Anzahl der Stellen, in denen sich diese Codewörter unterscheiden. Der Minimalabstand des Codes ist der kleinste Abstand, der zwischen zwei Codewörtern von vorkommt.

Beispiel

Für gilt .
Für gilt ; je zwei Codewörter haben den Abstand 2.
Für gilt ; es gibt in aber auch Codewörter mit dem Abstand 3.

Kennt man den Minimalabstand eines Codes , dann kann man leicht ablesen, wie viele Übertragungsfehler korrigierbar sind. Codes, die t Fehler korrigieren, werden t-fehlerkorrigierend genannt.
Ein Code ist t-fehlerkorrigierend genau dann, wenn gilt.

Beispiel Fortsetzung

ist 1-fehlerkorrigierend, ist 0-fehlerkorrigierend (damit sind also keine Fehler korrigierbar), ist 1-fehlerkorrigierend.

Für jeden t-fehlerkorrigierenden Code gilt . Gilt Gleichheit, dann nennt man einen t-perfekten Code.

Beispiel

Der Wiederholungscode ist t-perfekt.