Die Hamming-Distanz am einfachen Beispiel:
Du hast die Wörter 000, 011 und 110.
Damit sind die Hamming-Distanzen wie folgt:
H_d(000,011)= 2, H_d(000,110)= 2, H_d(011,110)= 2
--> Die minimale Hamming-Distanz ist 2.
Dir werden jetzt durch eine schlechte Leitung, in der häufiger mal Bits umgedreht werden (aus 0 wird 1 und anders herum) diese Wörter zuschickt.
Die Aussage ist jetzt wie folgt: Wenn du weißt, dass von einem Wort nicht mehr als k Bits umgedreht werden, so kannst du einen Fehler erkennen, wenn k kleiner ist als die minimale Hamming-Distanz (MIN H_d).
Zurück zum Beispiel: Die minimale Hamming-Distanz ist 2. Wir sollten einen Fehler von bis zu einem Bit bemerken.
k=0: Dir soll das Wort "000" zugeschickt werden. Es kommt zu keinem Fehler bei der Übertragung. Du bekommst also das Wort "000". Du bist glücklich.
k=1: Dir soll das Wort "000" zugeschickt werden. Es kann allerdings zu einem Fehler kommen. Es könnten also bei dir die Wörter bei einem geänderten Bit auch die Worte "100","010" und "001" bei dir ankommen. Da dies aber keine gültigen Worte sind, weißt du, dass hier ein Fehler vorliegt.
k=2. Dir soll das Wort "000" zugeschickt werden. Es kann dabei zu zwei Fehlern kommen. Es könnte also zum Beispiel auch das Wort "011" oder "110" bei dir ankommen. Da dies gültige Worte sind, hast du keine Ahnung, ob ein Fehler vorliegt oder gar, welches Wort dir eigentlich gesendet wurde.
Wir wollen jetzt zeigen, dass der Satz nicht nur im Beispiel gilt, sondern immer:
Dies zeigen wir mit einem Widerspruchsbeweis.
Ein Widerspruchsbeweis geht dabei immer so, dass wir das Gegenteil unser Behauptung annehmen und dann zeigen, dass dies zu einem Fehler führen muss. Wenn das Gegenteil aber falsch ist, muss die Behauptung richtig sein.
Wir nehmen daher nun an, dass weniger Fehler auftauchen können als die minimale Hamming-Distanz. Trotzdem kann bei einem Wort mit k Fehlern ein Fehler nicht erkannt werden. (--> Das ist jetzt das Gegenteil zu der Behauptung, dass wir es erkennen würden)
--> Damit der Fehler nicht erkannt werden kann, muss das Wort mit k Fehlern aussehen wie ein anderes echtes Wort. (Wenn es anders aussehen würde, würden wir ja merken, dass es kein Wort ist)
--> Für dieses echte Wort müsste dann aber gelten, dass es zu allen anderen gültigen Worten mindestens die Hamming-Distanz hat. (So ist ja die minimale Hamming-Distanz formuliert)
--> Wenn das echte Wort aber zu allen Worten mindestens die minimale Hamming-Distanz hat, muss es die insbesondere auch zu dem Ausgangswort, das eigentlich gesendet wurde, die minimale Hamming-Distanz haben. Dann muss die Anzahl der geänderten Bits aber auch mindestens die Hamming-Distanz betragen. (Definition der Hamming-Distanz...)
--> Das ist ein Widerspruch zur Annahme, dass die Anzahl der geänderten Bits kleiner ist als die Hamming-Distanz.
--> Da wir mit dem Gegenteil der Behauptung einen Widerspruch produziert haben, muss die Behauptung, dass wir den Fehler erkennen würde, gelten.