Dein Lernbereich wird geladen
App wird gestartet …
Dein Lernbereich wird geladen
App wird gestartet …
Die Hamming-Distanz zählt, an wie vielen Positionen sich zwei gleich lange Zeichenfolgen unterscheiden.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
dimensionslos, ganze Anzahl von Stellen; 0 bis n
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Zwei gleich lange Wörter über demselben Alphabet | Bitfolgen oder Symbole | |
| Wortlänge | Stellen | |
| Indikator: 1 bei wahrer Bedingung, sonst 0 | dimensionslos |
d_H(x,y)=\sum_{i=1}^{n}\mathbf{1}[x_i\ne y_i]Die Metrik setzt gleich lange Wörter über demselben Alphabet voraus und zählt Positionen mit ungleichen Symbolen. Für Binärwörter entspricht sie dem Gewicht des bitweisen XOR. Bei einem Code mit minimaler Hamming-Distanz dmin lassen sich bis zu dmin−1 Fehler sicher erkennen und bis zu floor((dmin−1)/2) Fehler eindeutig korrigieren, sofern die Empfangsfehler innerhalb dieser Grenze liegen. Diese Aussage allein liefert noch keinen effizienten Decoder.
Die Metrik setzt gleich lange Wörter über demselben Alphabet voraus und zählt Positionen mit ungleichen Symbolen. Für Binärwörter entspricht sie dem Gewicht des bitweisen XOR. Bei einem Code mit minimaler Hamming-Distanz dmin lassen sich bis zu dmin−1 Fehler sicher erkennen und bis zu floor((dmin−1)/2) Fehler eindeutig korrigieren, sofern die Empfangsfehler innerhalb dieser Grenze liegen. Diese Aussage allein liefert noch keinen effizienten Decoder.
Die Hamming-Distanz zählt, an wie vielen Positionen sich zwei gleich lange Zeichenfolgen unterscheiden.
Garantierte Korrekturzahl
Die Garantie setzt einen Code mit Mindestabstand dmin voraus.
Erkläre am Beispiel zu Hamming-Distanz von Bitfolgen, welche Eingabegrößen zur gesuchten Ausgabe führen.
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Die Hamming-Distanz zählt, an wie vielen Positionen sich zwei gleich lange Zeichenfolgen unterscheiden.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Die Beziehung ohne ihre angegebenen Voraussetzungen auf einen anderen Fall übertragen.
Prüfe vor dem Einsetzen den Gültigkeitsbereich: Die Metrik setzt gleich lange Wörter über demselben Alphabet voraus und zählt Positionen mit ungleichen Symbolen. Für Binärwörter entspricht sie dem Gewicht des bitweisen XOR. Bei einem Code mit minimaler.
Formelcluster
Die Hamming-Distanz zählt, an wie vielen Positionen sich zwei gleich lange Zeichenfolgen unterscheiden.
x=1011101 und y=1001001 unterscheiden sich an Position 3 und 5, daher dH=2. Ein Code mit dmin=3 kann damit garantiert einen Bitfehler korrigieren.
Bitfehler messen, Codewörter vergleichen und Mindestabstände für Fehlererkennung oder -korrektur beurteilen.
Eine typische Aufgabe Schritt für Schritt: Hamming-Distanz von Bitfolgen (dH(x,y) = Zahl unterschiedlicher Stellen).
Aufgabe
Erkläre am Beispiel zu Hamming-Distanz von Bitfolgen, welche Eingabegrößen zur gesuchten Ausgabe führen.
Rechenweg
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Die Hamming-Distanz zählt, an wie vielen Positionen sich zwei gleich lange Zeichenfolgen unterscheiden.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Vergleiche zwei Wörter Zeichen für Zeichen und zähle jede Position, an der die Symbole verschieden sind. Für x=1011101 und y=1001001 unterscheiden sich die dritte und fünfte Stelle, also dH=2. Gleiche Länge ist Voraussetzung; die Metrik zählt keine Einfügungen oder Löschungen. Bei Bitfolgen kann ein XOR gebildet und anschließend die Anzahl der Einsen gezählt werden. Die Distanz vergleicht Positionen, nicht numerische Werte. Fehlerkorrektur-Aussagen beziehen sich auf den Mindestabstand des gesamten Codes und garantieren nur innerhalb der mathematischen Fehlergrenze. Für Rauschen mit Einfügungen oder Löschungen ist eine andere Distanzdefinition erforderlich. Prüfe die Voraussetzungen.
Ist dmin der kleinste Hamming-Abstand zwischen zwei verschiedenen gültigen Codewörtern, kann der Code bis zu dmin−1 Fehler sicher erkennen. Zur eindeutigen Korrektur genügt ein Fehlerumfang t mit 2t<dmin. Bei dmin=3 wird daher ein Bitfehler korrigiert, aber zwei Fehler sind nicht garantiert korrigierbar. Die Grenze ist eine Garantie im Worst Case und sagt nichts darüber, wie oft Fehler tatsächlich auftreten. Die Distanz vergleicht Positionen, nicht numerische Werte. Fehlerkorrektur-Aussagen beziehen sich auf den Mindestabstand des gesamten Codes und garantieren nur innerhalb der mathematischen Fehlergrenze. Für Rauschen mit Einfügungen oder Löschungen ist eine andere Distanzdefinition erforderlich. Prüfe die Voraussetzungen.
Ein XOR-Bit ist genau dann 1, wenn die beiden Eingabebits an dieser Position verschieden sind. Die Hamming-Distanz zweier gleich langer Binärwörter ist daher das Hamming-Gewicht ihres bitweisen XOR, also die Anzahl seiner Einsen. Für 1011101 XOR 1001001 entsteht 0010100, das zwei Einsen besitzt. Diese Berechnung ist praktisch, darf aber nur für gleich lange Bitfolgen verwendet werden. Die Distanz vergleicht Positionen, nicht numerische Werte. Fehlerkorrektur-Aussagen beziehen sich auf den Mindestabstand des gesamten Codes und garantieren nur innerhalb der mathematischen Fehlergrenze. Für Rauschen mit Einfügungen oder Löschungen ist eine andere Distanzdefinition erforderlich. Prüfe die Voraussetzungen.
Die garantierte Korrekturzahl ist floor((dmin−1)/2). Für dmin=5 folgt floor(4/2)=2: Jeder Empfang, der höchstens zwei Bitpositionen von einem gültigen Codewort abweicht, lässt sich eindeutig diesem Wort zuordnen. Drei Fehler können die Empfangsfolge näher an ein anderes Codewort bringen. Die Garantie beruht auf Hamming-Kugeln, die sich bei diesem Abstand nicht überschneiden. Die Distanz vergleicht Positionen, nicht numerische Werte. Fehlerkorrektur-Aussagen beziehen sich auf den Mindestabstand des gesamten Codes und garantieren nur innerhalb der mathematischen Fehlergrenze. Für Rauschen mit Einfügungen oder Löschungen ist eine andere Distanzdefinition erforderlich. Prüfe die Voraussetzungen.
Die übliche Hamming-Distanz ist für gleich lange Zeichenfolgen definiert. Bei unterschiedlicher Länge wäre unklar, ob fehlende Positionen, Einfügungen oder Verschiebungen als Fehler zählen sollen. Ergänze nicht stillschweigend Nullen, denn das verändert die Bedeutung der Folge. Für Einfügungs- und Löschungsfehler werden Editierdistanz oder andere Metriken verwendet. Wähle die Metrik passend zum Fehlerkanal, statt nur den bequemsten Zahlenwert zu berechnen. Die Distanz vergleicht Positionen, nicht numerische Werte. Fehlerkorrektur-Aussagen beziehen sich auf den Mindestabstand des gesamten Codes und garantieren nur innerhalb der mathematischen Fehlergrenze. Für Rauschen mit Einfügungen oder Löschungen ist eine andere Distanzdefinition erforderlich. Prüfe die Voraussetzungen.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Hamming-Distanz von Bitfolgen":
Frage (Vorderseite)
Welche Formel beschreibt Hamming-Distanz von Bitfolgen?
Antwort in deinem Set
Frage (Vorderseite)
Wie stellst du dH(x,y) = Zahl unterschiedlicher Stellen nach Garantierte Korrekturzahl um?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei dH(x,y) = Zahl unterschiedlicher Stellen?
Antwort in deinem Set
+ 7 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 10 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Erstelle ein kuratiertes FSRS-Prüfungsset für dH(x,y) = Zahl unterschiedlicher Stellen: Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential