Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fehlererkennung oder Korrektur bei Hamming
Wie das System Fehler erkennt oder korrigiert ist mir ja eigentlich klar, aber die Frage auf die ich beim letzten Mal keine Antwort wusste ist: Warum ist Fehlererkennung alternativ zur Korrektur. Muss ich nicht erstmal einen Fehler erkennen bevor ich ihn korrigieren kann ? Wo genau liegt da das Problem der technischen Umsetzung ? Und falls jemand meint das käme in der Klausur nicht dran möchte ich trotzdem gerne eine Antwort. Ich will das verstehen ^^
Der Hamming-Code weist, unabhängig von der gewählten Blockgröße, immer eine Distanz von drei auf. Dies bedeutet, dass sich benachbarte Codewörter immer um drei Bits unterscheiden. Tritt ein Fehler an einer Stelle eines Codeworts auf, wird dieses als ungültig erkannt und kann eindeutig dem richtigen Codewort zugeordnet, der Übertragungsfehler also korrigiert werden. Treten hingegen zwei Fehler in einem Codewort auf, funktioniert diese Zuordnung nicht mehr – die Korrektur des Decoders ordnet das empfangene Codewort fälschlich einem anderen zu. Dies wird als „Falschkorrektur“ bezeichnet. Eine andere Form des Versagens tritt bei drei Übertragungsfehlern auf: Hier erkennt der Decoder das fehlerhafte Codewort als gültig an.
Hamming-Codes können also nur einen Bitfehler pro Datenwort korrekt korrigieren. Bis zu zwei Bitfehler können erkannt werden. (Wikipedia)
Das blieb mir immer hängen : “1 Bit korrigieren, 2 Bit erkennen”
Es folgt ein relativ unstrukturierter Braindump ohne richtig guten roten Faden. Ich hoffe, er hilft dir trotzdem ein bisschen weiter. 
Um n Bitfehler pro Codewort korrekt zu erkennen, müssen alle Codewörter voneinander eine minimale Hammingdistanz von n + 1 haben. Die Erkennung funktioniert folgendermaßen:
- Liegt das empfangene Datenwort in der Menge der gültigen Codewörter, liegt kein Fehler vor.
- Ist es ein ungültiges Codewort, liegt ein Übertragungsfehler vor. Wir können aber keine Aussage darüber treffen, welches Datenwort ursprünglich gesendet wurde - der Fehler ist also nicht korrigierbar.
Um n Bitfehler pro Codewort zu erkennen und korrekt zu korrigieren, muss die minimale Hammingdistanz gleich 2 n + 1 sein. Das Korrigieren sieht dann so aus:
- Wenn das empfangene Datenwort ein gültiges Codewort ist, ist alles in Butter.
- Wenn wir ein ungültiges Datenwort empfangen, suchen wir aus der Menge aller gültigen Codewörter dasjenige, das die kürzeste Hammingdistanz zum empfangenen Wort hat, und sagen: Das wird wahrscheinlich das ursprünglich gesendete Datenwort sein.
Bildlich kann man sich das sehr gut als einen Raum vorstellen, in dem jedes gültige Codewort durch einen Punkt dargestellt ist. Wenn man einen Punkt genau trifft, geht man davon aus, dass das Wort korrekt übertragen wurde. Liegt man daneben, sucht man sich den Punkt, der am nächsten dran liegt (→ Korrektur). Wenn es mehrere Punkte mit dem gleichen Abstand vom empfangenen Wort gibt, kann man sich nicht eindeutig entscheiden und hat den Fehler nur erkannt.
Verallgemeinert lässt sich sagen: Wenn alle Wörter eines Codes voneinander mindestens die Hammingdistanz HDmin besitzen, dann kann man
- bis zu HDmin - 1 Bitfehler pro Datenwort erkennen und
- bis zu floor((HDmin - 1) / 2) Bitfehler pro Datenwort korrigieren.
Erkennen heißt, “Hey da ist ein Fehler. Mhm… aber welches Wort das mal war kann ich nicht erkennen. Naja. Fordere ich es eben neu an/Warne den Nutzer.”
Will sagen: Mit erkennen ist nicht ‘erkennen und korrigieren’ sondern ‘erkennen, aber nicht entscheiden können wohin korrigiert werden soll’ gemeint. Bevor der Fehler korrigiert wird, ist natürlich klar, dass es da einen gibt, er wurde sozusagen bemerkt.
Mit erkennen ist zB gemeint, dass bei einer HD von 3 und Änderung auf zwei bit, zwar erkannt wird, dass es einen Fehler gibt, jedoch nicht entschieden werden kann, welches der (beiden) möglichen Codeworte denn nun gesendet wurde. Gleiches gilt für eine HD von 5 und 3 Fehler etc.
Theoretisch kann auch bei einer HD von 5 und 2 Fehlern schon nur noch erkannt werden, dazu gibts auch iwo eine Folie im Script. Die Frage ist nur, wie groß man die Wahrscheinlichkeit wählen will, falsch zu korrigieren. Will man eine kleine Wahrscheinlichkeit, nimmt man bei HD=5 1 Fehler korrigieren, 3 erkennen. Ist man wagemutiger nimmt man 2 korrigiern, 1 erkennen.
mit den Varianten habe ich auch ein Problem
ich Skript steht zum Beispiel bei HD=6
Variante 1: 5 Fehler erkennen
Variante 2: 1 Fehler korrigieren und 4 erkennen
Variante 3: 2 Fehler korrigieren und 3 erkennen
wie kommt man denn auf Variante 2 und 3?
Wo steht das im Skript? Entweder hab ich jetzt nen Denkfehler oder du hast dich mehrfach verschrieben.
Das ist die Frage mit der Wahrscheinlichkeit. Wenn du ganz sicher gehen willst, korrigierst du gar nicht (6 (!) 5 erkennen). Wenn du davon ausgehst, dass schon nicht mehr als 4bit auf einmal kippen werden, dann korrigierst du einen Fehler (macht 2 weniger erkennen, weil du ja vom Wort zuvor und danach jeweils ein bit korrigieren musst). Und wenn du davon ausgehst, dass nicht auf einmal mehr als 3 bit kippen werden, kannst du 2 korrigieren und 3 gekippte Bits erkennen.
Aber ich bin auch ncoh ein wenig verschlafen O:-)
PS: Jup, war ziemlicher Müll, was ich da geschrieben hab… irgendwie hatte ich in absoluten fehlerhaften Codes gedacht… 
@Danieru, ich bzw. wir haben auch ein bisschen gerätselt, aber du machst es einfach so:
Variante 1: einfach die Formel für Fehler erkennen nehmen. In dem Beispiel 5
Variante 2: Formel für Fehlerkorrigieren, dann haste ja raus wie viele Fehler du maximal korrigieren kannst. In dem Beispiel 2, dann hast du noch 3 mal erkennen für die Differenz 5-2
Variante 3: Man kann natürlich auch nur 1 korrigieren => 5 -1 = 4 erkennen.
so haben wir uns das hergeleitet, weil explizit ist das im skript glaube ich auch nicht erwähnt