Man erkauft sich diese Fehlersicherheit zum Preis einer etwas längeren Datenübertagung als es bei einer immer fehlerfreien Leitung nötig ist, da neben den eigentlichen Daten auch Prüfdaten übertragen werden müssen. Man nennt diese Prüfdaten treffender Redundanz und so eine Datenübertragung redundante Datenübertragung.
Es ist immer abzuwägen, in welchem Ausmaß eine Datenübertragung über einen bestimmten Kanal (sei's ein Modem, SCSI-Bus, etc.) Fehlererkennung bzw. Fehlerkorrektur bedarf oder ob zuviel Sicherheit (längere Übertragung wegen zusätzlichen Prüfdaten) zu einem unvertretbaren Leistungseinbuße führt.
Beispiel: Datenfernübertragung (DFÜ)
Für Übertragung von Daten über eine Modemleitung ist es
sicher angebracht, irgendeine Fehlererkennung im Protokoll zu
haben. Hier ist aber meist von fehlerkorrigierenden Protokollen
abzuraten, da diese nur Fehler korrigieren können, wenn sie
vereinzelt auftreten. Bei einer Modemverbindung treten Fehler jedoch
meist in einem Büschel (burst) auf.
So ist es besser die Datenübertragung in kleine unabhängige
Pakete aufzuteilen und Fehlererkennung zu benutzen. Treten nun Fehler
gehäuft auf, wird dies erkannt und man sendet nochmal das
Datenpaket, in dem Fehler auftraten.
Hingegen ist es sicher nicht ratsam, den internen Bus eines Prozessors
mit redundanten Informationen zur Fehlererkennung zu belasten, wenn dieser
Bus ohnehin keine Fehler produziert.
Beispiel: Datenübertragung auf Zeit: Datenspeicherung
Man kann das Speichern von Daten auch als eine Datenübertragung
über einen längeren Zeitraum ansehen. Das Senden von Daten
entspricht das Schreiben auf ein Speichermedium, und das Empfangen
entspricht dem Lesen. Dazwischen vergeht Zeit, in der das
Speichermedium zerkratzt oder auf andere Art verändert wird, beim
Lesen der Daten kann es so zu Fehlern kommen.
Daher kann auch Fehlererkennung bzw. Fehlerkorrektur für das
Speichern von Nutzen sein. Wie im Beispiel der DFÜ ist hier
wieder abzuwägen, in wie weit Fehlererkennung nötig ist.
Man braucht für das Abspeichern einer längeren einfachen
Textdatei meist keine Sicherheitsvorkehrungen zu treffen. Selbst wenn
ein paar Bytes hintereinander falsch sind, so ist nur ein Wort im Text
unleserlich, was nicht soviel ausmacht, da der Mensch meist aus dem
Satzzusammenhang den Fehler korrigieren kann. Also ist eine Textdatei
ohnehin ausreichend redundant.
Ganz anders sieht es bei einer gepackten ZIP-Datei aus. Hat nur ein
einziges Zeichen einen Fehler so kann die Datei vollständig
unbrauchbar sein, da die Informationen darin nicht redundant, sondern
gerade dicht gepackt sind. Daher nutzt das ZIP
Format immer eine CRC Prüfung
(Cyclic Redundancy Code) , um wenigstens Fehler erkennen zu
können.
Ein weiteres Beispiel sind ausführbare Dateien (z.B. EXE-Dateien,
Binaries,etc.). Wird hier nur ein Bit verändert, so kann das Programm
bei nächster Ausführung deswegen Abstürzen.
Grundlagen der Fehlererkennung/korrektur
Was ist eigentlich Fehlererkennung/korrektur?
Um sich einen Überblick zu verschaffen, wie
Fehlererkennung/korrektur genau funktioniert, geht man von dem
abstrakten Schema der Nachrichten-
bzw. Datenübertragung aus.
Notwendigkeit von Redundanz für Fehlererkennung und erläuterndes Beispiel
In der Einführung wurde schon angesprochen, dass
Fehlererkennung nur durch Redundanz zu erreichen ist. Um das noch
klarer zu machen, betrachte man folgendes:
Es sei eine Quelle mit vier verschiedenen Symbolen gegeben (z.B. rechts, links, oben und unten) und man kodiert diese Symbole binär
Im obigen Beispiel könnte man die Kodewörter um ein
Paritätsbit verlängern, d.h. man zählt in jedem Kodewort die
Einsen und ist die Anzahl gerade, so schreibt man hinter das Kodewort
eine Null sonst eine Eins.
Gültige Kodewörter sind somit
Fehlererkennung mit Paritätsprüfung erkennt einen Fehler
Fehlererkennung mit Paritätsprüfung versagt bei zwei Fehlern
Das hängt davon ab, welche Art von Rauschen der
Übertragungskanal hat: In der Theorie wird gerne ein Kanal
mit weißem Rauschen genommen, d.h. Kodezeichen werden alle mit
der gleichen Wahrscheinlichkeit unabhängig voneinander
verfälscht.
Menschen als Übertragungskanal rufen ein völlig anderes
Rauschen hervor, sie verdrehen zum Beispiel Kodezeichen, was eine
elektrische Leitung nur schwerlich leisten könnte.
Fortan werden nur die Kanäle betrachtet, die überwiegend
weißes Rauschen besitzen (Hier geht es um die Theorie).
Unter diesen Bedingungen treten Fehler unabhängig voneinander mit
der gleichen Wahrscheinlichkeit auf. Bekommt der Empfänger ein
ungültiges Kodewort, wurde mit der größten
Wahrscheinlichkeit das gültige Kodewort gesendet, das sich von
dem ungültigen Kodewort in den wenigsten Stellen unterscheidet.
Im vorigen Beispiel gibt es aber ein Problem, man hat mehrere gültige Kodewörter, die sich in der genau gleichen minimalen Anzahl von Kodestellen unterscheiden:
Ungültig Gültig und Unterschied 1 Bit
001 000 rechts 011 unten
010 011 unten 110 oben
100 101 links 000 rechts
111 101 links 110 oben
Man kann so ziemlich schlecht den Fehler korrigieren, weil man sich für eines von zwei gleich wahrscheinlich echten Kodeworten entscheiden muß. Also scheint mit dem einfachen Paritybit eine Fehlerkorrektur eines einzelnen Fehlers nicht möglich zu sein.
In obigem Beispiel hatten wir einen Kode der Länge 3 mit 2 Datenbits und 1 Prüfbit. Nimmt man aber anstatt einem k Prüfbits, kann man theoretisch 2^k verschiedene Zustände darstellen anstatt mit einem Prüfbit nur 2^1 = 2 Zustände. Wenn man ein binäres Kodewort der Länge n hat, müsste man bei Fehlerkorrektur sagen können, an welcher der n Stellen der Fehler auftrat oder ob kein Fehler aufgetreten ist: Das sind n+1 verschiedene Zustände und daher muß folgendes gelten
2^k >= n+1.Die k Prüfbits müssen mindestens die n verschiedenen Stellen darstellen können, an denen ein Fehler auftrat und ebenso, dass kein Fehler auftrat.
Hammingkode
Wie konstruiert man den Kode, der diese Ungleichung auch genau
erfüllt also zur Gleichung macht?
Die Idee hinter diesem als Hammingkode bekannten Kode ist, dass
die k Prüfbits die Stelle an der, der Fehler auftrat, als k-Bit
Binärzahl darstellen. Wenn kein Fehler auftrat, sollen die
Prüfbits eine 0 darstellen.
Ein Kodewort besteht aus k Kontrollstellen und den eigentlichen m
Datenbits, was zusammen ein Kodewort der Länge m+k=n macht.
Ein Prüfbit soll dabei eine Art Paritätsprüfung
ermöglichen, d.h. wenn das endgültige Kodewort beim
Empfänger ankommt, so soll der Empfänger folgendes für
jedes Prüfbit tun:
Je nach Prüfbit addiert er einige bestimmte Datenbits und
zählt noch das Prüfbit dazu, dann teilt er das Ergebnis
ganzahlig durch 2 und betrachtet den Rest der Division. Kommt 0 heraus
so ist in den betrachteten Datenbits und im Prüfbit kein
einzelner Fehler aufgetreten. Ist der Rest dagegen 1, so muß in
einem dieser Bits ein Fehler aufgetreten sein. Da für jedes der k
Prüfbits eine solche Prüfprozedur durchgeführt wird,
hat man k verschiedene Ergebnisse vom Wert 0 oder 1. Man kann diese
Ergebnisse hintereinander schreiben und erhält eine Binärzahl,
die auch Syndrom genannt wird. Diese Binärzahl soll gemäß
der Idee des Hammingkodes die Fehlerstelle darstellen. Für diese
Zahl oder auch Syndrom muß folgendes gelten
Fehler passiert an Position Syndrom muß dies darstellen
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
. .
. .
. .
Daraus kann man ablesen, dass das letzte Prüfbit die
Positionen 1,3,5,7,.. in seiner Paritätsprüfung enthalten muß, das
vorletzte Prüfbit 2,3,6,7,10,11,... das zweitletzte die Stellen
4,5,6,7,12,13,14,15,... und sofort.
Man kann diesen Kode für den Fall konstruieren, vier Datenbits mit Einzelfehlerkorrektur zu versehen. Nach obiger Ungleichung muß gelten
2^k >= n+1 = m+k+1 = 4+k+1Für k = 3 ist die Ungleichung genau erfüllt
8=2^3 >= 4+3+1 = 8Das Kodewort hat also die Länge 7 und man hat 4 Datenbits und 3 Prüfbits. Um es möglichst einfach zu haben, werden hier die Stellen des Kodeworts von rechts nach links durchnummeriert und als Prüfbits werden die 1.,2. und 4. Stelle des Kodeworts gewählt, d.h. die eigentlichen Datenbits befinden sich an der 3.,5.,6. und 7. Stelle des Kodeworts.
Stellen 7 6 5 4 3 2 1
Bits _ _ _ _ _ _ _
Daten * * * *
Prüfbits K K K
Stellen 7 6 5 4 3 2 1
Bits 1 0 1 _ 1 _ _
Prüfung #1 1+0+1+0 = 0 (in mod 2 gerechnet)
1 0 1 0 1 _ _
Prüfung #2 1+0+ 1+0 = 0 (in mod 2 gerechnet)
1 0 1 0 1 0 _
Prüfung #3 1+ 1+ 1+ 1 = 0 (in mod 2 gerechnet)
1 0 1 0 1 0 1
Endgültiges Kodewort 1 0 1 0 1 0 1
Ergebnis von Prüfung #1,#2,#3: 0 0 0
Zuerst sucht man den Wert des ersten Prüfbits, das sich an
Stelle 4 befindet. Das erste Prüfbit ist das zweitletzte. Nach
obiger Idee muß die Paritätsprüfung somit über die
Stellen 4,5,6,7 ausgeführt werden. Man addiert diese Stellen
1+0+1+x = 2+x; dabei ist das x das erste Prüfbit an Stelle 4.
Welchen Wert soll man dafür wählen? 2+x muß durch zwei
geteilt den Rest 0 ergeben, das heißt nichts anderes als 2+x muß
durch zwei teilbar sein, also wählt man für x eine 0. Man
muß an Stelle 4 eine 0 schreiben. 1 0 1 0 1 _ _.
Nun wird der Wert des zweiten bzw. vorletzten Prüfbits gesucht, das
sich an Stelle 2 befindet. In der Paritätsprüfung des vorletzten
Prüfbits müssen die Stellen 2,3,6,7 betrachtet werden. Man
hat 1+0+1+x = 2+x. Also muß man eine 0 an Stelle 2 schreiben.
Schließlich muß das letzte Prüfbit an Stelle 1 die Prüfung
über die Stellen 1,3,5,7 vollziehen; dies ergibt 1+1+1+x = 3+x.
x muß 1 sein damit 3+x durch 2 teilbar ist (Rest der Division 0).
Daher muß eine 1 an Stelle 1 stehen.
Das endgültige Kodewort ist 1 0 1 0 1 0 1 .
Schreibt man die Ergebnisse der Prüfungen #1,#2 und #3 hintereinander so erhält man 000 (Syndrom). Wird das Kodewort ohne Fehler übertragen, führt der Empfänger die drei Paritätsprüfungen durch, schreibt die Ergebnisse hintereinander und erhält dieses Syndrom 000, was "kein Fehler" bedeutet.
Man nehme an, in Stelle 4 des Kodeworts tritt ein Fehler auf. Dann erhält der Empfänger statt
1 0 1 0 1 0 1
*
das Kodewort 1 0 1 1 1 0 1.
Berechnet man das Syndrom, so ergeben die Paritätsprüfungs 100. Es ist ein
Fehler an Stelle 4 aufgetreten. 2^k >= n+1, also 2^10 = 1024 >= 1023+1 = 1024.
Wie sieht es mit Kodes aus, die zwei oder n Fehler korrigieren können, oder kann
ein Kode vielleicht n Fehler korrigieren und dabei auch 2*n Fehler erkennen? Welche
Ungleichungen müssen solche Kodes erfüllen?
Um diese Fragen zu beantworten, kann man versuchen, das Problem der Fehlerkorrektur von
einem anderen Blickwinkel zu betrachten.
Eine geometrische Sicht auf binäre Kodes
Man kann sich ein binäres Kodewort der Länge n als einen Punkt im
n-dimensionalen Raum vorstellen, wobei die i. Stelle des Kodeworts die i. Koordinate im
n-dimensionalen Raum angibt.
An einer Stelle des Kodeworts steht entweder eine 1 oder 0, so dass es nur zwei
Werte für jede Koordinate gibt (0 und 1). Mit n Koordinaten kann man so nur 2^n
verschiedene Punkte im n-dimensionalen Raum darstellen, was mit der Zahl der
möglichen Kodeworte von 2^n übereinstimmt. Diese 2^n Punkte (Kodewörter)
sind die Eckpunkte eines n-dimensionalen Würfels.
Hammingabstand
Sendet man ein Kodewort, so ist dies ein bestimmter Eckpunkt auf dem Würfel. Tritt
im Kanal ein einzelner Fehler auf, so bewegt sich der Kodewortpunkt auf einer bestimmten
Kante des Würfels zu einem direkt daneben liegenden Eckpunkt.
Nimmt man an, dass man wieder einen Kode mit Redundanz betrachtet, so gibt es
Punkte auf dem Würfel, die gültige Kodewörter darstellen und solche die
ungültige darstellen. Fordert man jetzt von diesem Kode, dass der Abstand
zwischen zwei gültigen Kodewortpunkten mindestens 2 Kanten beträgt, so ist ein
einzelner Fehler immer erkennbar:
Denn sendet man ein gültiges Kodewort und tritt ein einzelner Fehler auf, so wird
der Kodewortpunkt um nur eine Kante verschoben , so dass dadurch nie ein gültiger
Kodewortpunkt erreicht werden kann, da ja mindestens eine Verschiebung um 2 Kanten dafür
nötig ist, um wieder auf einem gültigen Kodewortpunkt zu landen.
Also wird man beim Auftreten eines einzelnen Fehlers immer ein ungültiges Kodewort
empfangen und somit ist Einzelfehlererkennung in solch einem Kode gegeben.
Fordert man von einem Kode mit Redundanz darüber hinaus, dass der Minimalabstand zwischen zwei gültigen Kodewörtern 3 Kanten auf dem Würfel beträgt, so läßt ein einzelner Fehler den empfangenen Kodewortpunkt näher an dem ursprünglichen Kodewortpunkt und damit hat man Einzelfehler Korrektur ermöglicht.
Was man durch diese Betrachtungsweise gewonnen hat, ist eine Abstandsfunktion,
die Hammingabstand genannt wird. Dieser Hammingabstand gibt an wieviele
Kanten man auf dem Würfel mindestens ablaufen muß, um von einem bestimmten
Kodewortpunkt A zu einem anderen Kodewort B zu gelangen. Diese Zahl stimmt
mit der Anzahl der Binärstellen überein, in denen sich das Kodewort A und B
unterscheiden.
Bedeutung des minimalen Hammingabstands eines Kodes
Interessant ist es nun in einem binären Kode den kleinsten Hammingabstand, den
zwei gültige Kodewörter haben können, zu betrachten. Dieser Abstand
wird auch minimaler Hammingabstand des Kodes genannt.
Ein Kode mit minimalem Hammingabstand von 1 ermöglicht keine Fehlererkennung
(abändern einer Stelle führt wieder auf ein gültiges Kodewort),
ein Kode mit minimalem Hammingabstand von 2 gewährt Einzelfehlererkennung,
von 3 ermöglicht entweder Doppelfehlererkennung oder Einzelfehlerkorrektur,
da bei einem Fehler der empfangene Kodewortpunkt näher beim ursprünglichen
Kodewortpunkt liegt als zu irgendeinem anderen gültigen Kodewort.
Mit einem Kode mit minimaler Hammingdistanz von 5 ist eine Doppelfehlererkennung
möglich.
Minimaler Hammingabstand Möglichkeiten
des Kodes
1 keine Fehlererkennung
2 Einzelfehlererkennung
3 Einzelfehlerkorrektur oder Doppelfehlererkennung
4 Einzelfehlerkorrektur und Doppelfehlererkennung
oder Dreifachfehlererkennung
5 Doppelfehlerkorrektur oder Vierfachfehlererkennung
etc.
/ 3 \ / 3 \ / 3 \
1+3+3 = ( ) + ( ) + ( ) = 7 Kodewörter in Hammingkugel mit Radius 2.
\ 0 / \ 1 / \ 2 /
Allgemein kann man durch obige Anschauung daraufkommen, dass die Anzahl
der Kodewörter in einer Hammingkugel mit Radius r um ein Kodewort A
über einen binären Kode der Länge n gegeben ist durch:
r
___ / n \
\ ( ) = Anzahl der Kodewörter in Hammingkugel mit Radius r
/__ \ i /
i=0
Hamminggrenze: Ungleichung für efache Fehlerkorrektur
Zuerst wird nochmals die Ungleichung für einen Kode hergeleitet,
der Einzelfehlerkorrektur zu läßt. Man hat einen
binären Kode der Länge n=m+k; wobei m die Anzahl der
Datenbits und k die Anzahl der Kontrollbits ist. Es gibt also 2^m
gültige Kodewörter und 2^k ungültige
Kodewörter.
Sendet man ein gültiges Kodewort X und tritt irgendwo ein einzelner
Fehler auf, so befindet sich das tatsächlich empfangene Kodewort X', in der
Hammingkugel mit dem Radius 1 um das gesendete Kodewort, da sich das empfangene
Kodewort nur in einer Stelle vom ursprünglichen Kodewort unterscheidet
und so nur den Hammingabstand 1 von ihm besitzt.
Betrachtet man jetzt alle anderen Kodewörter Y und zieht jeweils eine
Hammingkugel von Radius 1 um diese, so wäre es fatal, wenn das tatsächlich
empfangene Kodewort X', in einer dieser anderen Hammingkugeln läge. Denn
dann hätte man wenigstens zwei gültige Kodeworte X und Y, die sich nur
um eine Stelle vom empfangenen Kodewort X€ unterscheiden. In so einer Situation
kann man sich nicht entscheiden, was die bessere Wahl darstellt, da man zwei
gleichwahrscheinlich richtige Kandidaten hat. Um dies zu vermeiden, dürfen
sich die Hammingkugeln mit Radius 1 nicht überlappen.
n m m+k m k 2 >= 2 * (n+1) <=> 2 >= 2 (n+1) <=> 2 >= n+1.Genauso kann man dies für Doppelfehlerkorrektur herleiten:
n m / n \ k / n \
2 >= 2 * (1+n+ ( ) ) <=> 2 >= (1+n+ ( ) )
\ 2 / \ 2 /
Allgemein gilt dann für efache Fehlerkorrektur:
e e
k ___ / n \ ___ / n \
2 >= \ ( ) bzw. k >= ld( \ ( ) )
/__ \ i / /__ \ i /
i = 0 i=0
Die Ungleichung rechts wird auch als Hamminggrenze bezeichnet.
Zusammenfassung
Diese Abhandlung ging auf die Grundlagen der Fehlererkennung/korrektur ein
und versuchte folgende Dinge zu verdeutlichen:
1 ermöglicht keinerlei Fehlererkennung
2 Einzelfehlererkennung
3 Einzelfehlerkorrektur oder Doppelfehlererkennung
4 Einzelfehlerkorrektur plus Doppelfehlererkennung
Um abrundend noch einen geschichtlichen Aspekt einzuwerfen, sei noch angemerkt, dass der Hammingkode bzw. die Hamminggrenze von R. W. Hamming 1950 gefunden wurden. Hamming ist in diesem Jahr (1998) im Januar im Alter von 83 Jahren gestorben. Schlieśen mńchte ich mit einem Zitat Hammings: