Forum

Einloggen | Registrieren | RSS  

Suche:  

Hamming-Distanz (Computertechnik)

verfasst von Torsten(R) E-Mail, 12.07.2011, 22:32 Uhr

» 1. Ist das so weit richtig?
Das hängt alles von den Voraussetzungen ab. Ohne zu wissen, wie dein Alphabet aussieht, kann die Frage nicht beantwortet werden.

Ich versuche es einfach mal an dem denkbar einfachsten Beispiel zu erklären: dem (3, 1)-Hamming Code.
Dieses Alphabet kodiert ein Nutzdatenbit in drei Bit.
Das Alphabet besteht aus den Werten 000 und 111. Alle anderen Kombinationen sind unbelegt und dürfen im Normalfall nicht vorkommen.
Der Hamming-Abstand des Alphabets beträgt 3.

Wird jetzt die Kombination 000 gesendet, aber durch einen Bitfehler während der Übertragung 001 empfangen, dann beträgt der Abstand zu 000 exakt 1, der Abstand zu 111 aber 2.
001 wird also auf 000 abgebildet.
Der Fehler wurde erkannt und behoben.
Merke: Auf einem Hamming-Alphabet mit Abstand 3 kann ein einzelner Übertragungsfehler erkannt und behoben werden.

Wird jetzt wieder versucht, 000 zu senden, aber es treten zwei Bitfehler auf und der Empfänger liest 011, dann wird fälschlicherweise der Wert 111 erkannt. Zwei Bitfehler können also mit einem Alphabet mit Abstand 3 nicht behoben werden.
Frage: Welcher Abstand wäre dazu notwendig?

Wenn das für den Fall klar ist, dann überlege Dir am besten noch mal allgemeiner für ein Alphabet mit Abstand n=1..5, 6 oder 7 (je nachdem wie viel Ausdauer Du hast)
a) Wie viele zufällige Bitfehler pro Übertragung erkannt werden können
b) Wie viele zufällige Bitfehler pro Übertragung repariert werden können

» Wenn ich eine Hamming-Distanz von 1-Bit habe (also nur ein 1 Bit unterscheidet sich im Code), dann kann ich einfach diese eine Bit durch Prbieren "reparieren" - es sind ja nur zwei Möglichkeiten.
Bei Hamming-Codes musst Du nicht "probieren". Das Verfahren ist vollkommen deterministisch.

Gruß
Torsten

antworten

Gesamter Thread:

Hamming-Distanz - Grundlagenforscher(R), 12.07.2011, 19:10 (Computertechnik)
Hamming-Distanz - Torsten(R), 12.07.2011, 19:54
Hamming-Distanz - Grundlagenforscher(R), 12.07.2011, 19:58
Hamming-Distanz - Torsten(R), 12.07.2011, 20:27
Hamming-Distanz - Grundlagenforscher(R), 12.07.2011, 22:12
Hamming-Distanz - Torsten(R), 12.07.2011, 22:32
Hamming-Distanz - Grundlagenforscher(R), 12.07.2011, 22:42
Hamming-Distanz - Torsten(R), 13.07.2011, 07:29
Hamming-Distanz - Grundlagenforscher(R), 13.07.2011, 11:34
Hamming-Distanz - hws(R), 13.07.2011, 13:22
Hamming-Distanz - Grundlagenforscher(R), 13.07.2011, 14:00
Hamming-Distanz - hws(R), 13.07.2011, 16:32
Hamming-Distanz - x y, 13.07.2011, 16:56
Hamming-Distanz - hws(R), 13.07.2011, 17:07