Forum

Hallo die Damen und Herren,

1. Meine ET-Prüfung ist bestens gelaufen - ich hoffe es wird eine zwei oder besser

Somit DANKE an alle, die mir bei meinen Fragen mit Rat und Tat zur Seite standen

2. Meine neue Frage

Mir ist bekannt wie ich die Hamming distanz zwischen zwei Codewörtern herausfinde.

Beispiel mit 3 Codewörtern:

a) 0110
b) 1100
c) 1111


Ich vergleiche jetzt paarweise alle 3 Wörter:

a) 0110
b) 1100 => Distanz 3

a) 0110
c) 1111 => Distanz 2

b) 1100
c) 1111 => Distanz 2

So - die Distanz für den kompletten Code ist 2.

1. Frage:

Warum nehme ich hier den minimalsten Abstand?

2. Frage:

Wie betreibe ich a) eine Fehleranlyse (ist doch letztlich der Vergleich der einzelnen Paarungen) und
b) wie kann ich eine Fehlerkorrektur vornehmen? Könnte mir das jemand mal an einem praktischen Beispiel nahe bringen? Der Erläuterungen im Netz sind nicht so toll...Da steht auch noch was von wegen 1-Bit und 2-Bit und x-Bit Fehlern... da steige ich auch nicht so durch?

Wer kann mal helfen? Wäre echt nett

VG Grundlagenforscher

» a) 0110
» b) 1100 => Distanz 3

Nein.

» Wie betreibe ich a) eine Fehleranlyse (ist doch letztlich der Vergleich
» der einzelnen Paarungen) und
» b) wie kann ich eine Fehlerkorrektur vornehmen? Könnte mir das jemand mal
» an einem praktischen Beispiel nahe bringen? Der Erläuterungen im Netz sind
» nicht so toll...

Ganz vereinfacht ausgedrückt: Für eine fehlerhafte Übertragung muss der Hamming-Abstand zum ursprünglichen (fehlerfreien) Code kleiner sein als der Hamming-Abstand zu allen anderen Codes.
Dann ist (auf Basis der Annahme, dass die Fehlerzahl kleiner als ein bekannter Grenzwert ist) die Wahl eindeutig.

» Da steht auch noch was von wegen 1-Bit und 2-Bit und x-Bit Fehlern... da steige ich auch nicht so durch?

1-Bit Fehler: 1 Bit ist fehlerhaft übertragen worden
2-Bit Fehler: 2 Bits sind fehlerhaft übertragen worden
x-Bit Fehler: ...

Gruß
Torsten

» Ganz vereinfacht ausgedrückt: Für eine fehlerhafte Übertragung muss der
» Hamming-Abstand zum ursprünglichen (fehlerfreien) Code kleiner sein als
» der Hamming-Abstand zu allen anderen Codes.
» Dann ist (auf Basis der Annahme, dass die Fehlerzahl kleiner als ein
» bekannter Grenzwert ist) die Wahl eindeutig.
»
» » Da steht auch noch was von wegen 1-Bit und 2-Bit und x-Bit Fehlern... da
» steige ich auch nicht so durch?
»
» 1-Bit Fehler: 1 Bit ist fehlerhaft übertragen worden
» 2-Bit Fehler: 2 Bits sind fehlerhaft übertragen worden
» x-Bit Fehler: ...
»
» Gruß
» Torsten

Sry, aber ich komme da nicht raus. warum muss der Hamming-Abstand zum ursprünglicehn Code kleiner sein als zu allen anderen Codes? Wenn ich doch in jedem Codewort 2 Bit-Fehler habe, habe ich doch insgesamt 6 Bitfehler (wenn wir davon ausgehen, dass ich 3 Paare miteinander verglichen habe und bei jedem eine D von 2 rausgekommen ist...)

VG

» Sry, aber ich komme da nicht raus. warum muss der Hamming-Abstand zum
» ursprünglicehn Code kleiner sein als zu allen anderen Codes? Wenn ich doch
» in jedem Codewort 2 Bit-Fehler habe, habe ich doch insgesamt 6 Bitfehler
» (wenn wir davon ausgehen, dass ich 3 Paare miteinander verglichen habe und
» bei jedem eine D von 2 rausgekommen ist...)

Deine drei Beispielcodes sind wohl eher eine Vorübung und haben nichts mit der Frage fehlerkorrigierender Codes zu tun.

Dazu müsstest Du erstmal ein Alphabet über den Hamming-Codes definieren.
Du könntest also erstmal alle 6 Bit langen Hamming-Codes mit Abstand 3 aufschreiben. Tipp: Es sind 8.

Dann können wir Dir auch gerne mal an dem Beispiel Deines Alphabets zeigen, wie man damit 1-Bit Fehler korrigiert.

Gruß
Torsten

Hi,

ich glaube ich habe es so weit begriffen, aber berichtigt mich:

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.

Wenn ich aber eine Hamming-Distanz von (miax.) 2 Bit habe, kann ich zwar erkennen, wo der Fehler auftritt, aber die Fehler nicht korrigieren, weil...?

Wenn ich eine Hammingdistanz von (mind.) 3 Bit habe kann ich die Fehler erkennen UND korrigieren, weil...?

1. Ist das so weit richtig?
2. Kann mir jemand das "...weil?" so ergänzen, dass ich es verstehe?

» 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

erstmal danke für die schnell antwort.

jetzt aber gleich die nächste frage:

was ist der unterschied zwischen "Determinismus" und "Determiniertheit"??

Heißt ersteres, dass nur ein Wert am Ende rauskommen? Und heißt letzteres, dass der Wert am Ende auf grund des Algorithmus eine ganz bestimmte größe annimmt? Ich verstehe den unterschied nicht so recht?!

» was ist der unterschied zwischen "Determinismus" und "Determiniertheit"??

Das weiß doch sogar Wikipedia:
http://de.wikipedia.org/wiki/Algorithmus#Determinismus

Ein bißchen suchen, bevor Du hier fragst, kann sicher nicht schaden.

Gruß
Torsten

habe gestern noch danach eine (noch einfacherere) Erklärung gefunden...

Aber danke für den Hinweis!

» habe gestern noch danach eine (noch einfacherere) Erklärung gefunden...

Und die willst du uns vorenthalten?

hws

» » habe gestern noch danach eine (noch einfacherere) Erklärung gefunden...
»
» Und die willst du uns vorenthalten?
»
» hws

Determinismus = Weg und Ziel (des Algorithmus) sind klar definiert bzw. stehen vorab fest.

Determiniertheit = Nur das Ziel (Ergebnis) steht fest, der Weg dorthin ist aber indertiministisch (also kann sich abhängig von den Werten, Eingaben etc.) unterscheiden. Muss aber am Ende wieder zusammen laufen.

Kann man das so stehen lassen?


Nochmal zur Hammingdistanz:

Warum ist bei einer Distanz für D=3 eine Fehlerkorrektur möglich? wenn das ursprüngliche Signal 111 war und das Signal, dass angekommen ist 000 ist, habe ichdoch 2^3 Möglcihkeiten, das Signal darzustellen. Warum sollte es mir ausgerechnet bei D=3 möglich sein, von 000 auf 111 zu kommen? Schleierhaft ist das...

Kann nochmal jemand helfen?

VG

» Determinismus = Weg und ...
Ach so, die Deninition. Ich dachte Erklärung der Hamming Distanz.

» Warum ist bei einer Distanz für D=3 eine Fehlerkorrektur möglich? wenn das
» ursprüngliche Signal 111 war und das Signal, dass angekommen ist 000 ist,
» habe ichdoch 2^3 Möglcihkeiten, das Signal darzustellen. Warum sollte es
» mir ausgerechnet bei D=3 möglich sein, von 000 auf 111 zu kommen?
» Schleierhaft ist das...

Da geht was durcheinander. 000 gesendet und 111 emfangen: 3 Bitfehler und das kann man weder korrigieren noch empfangen. Der Empfänger nimmt 111 als korrekt an.
Nur 011 oder 100 kann er erkennen und korrigieren.

hws

» Da geht was durcheinander. 000 gesendet und 111 emfangen: 3 Bitfehler und
» das kann man weder korrigieren noch empfangen.

Ooch, es braucht nur ausreichend langen Hammingcode.

» Ooch, es braucht nur ausreichend langen Hammingcode.

Aber nicht bei D=3 wie im Beispiel ..

hws