Hilfe in grundlegender Informatik?

...komplette Frage anzeigen k-Bit.-Fehler - (Mathematik, Informatik, Beweis)

4 Antworten

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.

Steht H_d für die Hamming Distanz? Wofür steht C(r) und wofür [C(r)]?

Was du siehst ist ein Beweis durch Widerspruch.
Du möchtest Beweisen, das ein k-Bit-Fehler bei [C(r)]' erkennbar ist, wenn k < MIN H_d(C).

Der Satz gilt als bewiesen, wenn du das Gegenteil widerlegen kannst bzw. dies zum Widerspruch führt.
Also versuchst du zu beweisen, das ein k-Bit Fehler bei [C(r)]' nicht erkennbar ist, wenn k < MIN H_d(C).

Dann konstruierst du ein Szenario das gelten müsste wenn die Annahme korrekt ist. (Pfeil 2)
Nun pickst du dir aber einen Fall da heraus, für den die Annahme nicht stimmig ist, bzw. die zum Widerspruch mit dem Szenario führt (Pfeil 3+4)

Damit ist die gewünschte Aussage belegt.

Ohne Vorkenntnisse kann man am Argument schon erkennen, was dem zugrunde liegt, und zwar etwa folgende Kenntnisse, die du hoffentlich irgendwo gelernt hast:

  • wenn der Fehler bei einem Wort w nicht erkannt werden kann, so wird w als gültiges Wort erkannt, d. h. w ∈ G_C.
  • Für alle Wörter u,v ∈ G_C gilt Hᵈ(u, v) ≥ Min Hᵈ(C).


Aus diesen beiden Kenntnissen, sind die ersten zwei Implikationen nachvollziehbar: es wird Angenommen, der Fehler bei [C(r)]´ sei nicht erkennbar, daher gilt [C(r)]´∈ G_C. Da C(r) und [C(r)]´ gültige Wörter sind, d. h. in G_C liegen, gilt aus der All-Aussage Hᵈ([C(r)]´, C(r)) ≥ Min Hᵈ(C).


Der Rest des Arguments ist selbsterklärend.
kreisfoermig 14.10.2016, 13:46

oben hätte ich ja schreiben müssen: u,v ungleiche Codes.

0

Da steht nur was von einem Fehler, warum ist dann einer erkennbar der andere nicht?

Verstehst du das Prinzip des Wiederspruchbeweises nicht?

Was möchtest Du wissen?