Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] [Suche]
Mathematik-Online-Lexikon:

Hamming-Abstand

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Endliche Folgen aus 0 und $ 1$ nennt man in der Kodierungstheorie (Binär-)Wörter. Der Hamming-Abstand zweier $ n$-stelliger Wörter $ x$ und $ y$

$\displaystyle d_H(x,y) =$    Anzahl der $\displaystyle k$ mit $\displaystyle x_k\ne y_k $

ist eine Metrik auf der Menge der $ n$-stelligen Binärwörter.

Beispielsweise ist für $ n=3$

$\displaystyle d(011,110)=2 $

und die (offene) Kugel $ B(101;2)$ um $ x=101$ mit Radius $ 2$ enthält die Elemente

$\displaystyle 001,\quad 111,\quad 100\,. $

Die Elemente, die sich von $ 101$ an zwei Stellen unterscheiden, gehören nicht dazu, da der Abstand kleiner als zwei sein muss.

Die Positivität und Symmetrie sind offensichtlich. Die Dreiecksungleichung folgt aus der äquivalenten Definition

$\displaystyle d_H(x,y)=\sum_{j=1}^n \vert x_j-y_j\vert $

und der Dreiecksungleichung für Beträge

$\displaystyle \vert x_j-z_j\vert=\vert x_j-y_j+y_j-z_j\vert\le \vert x_j-y_j\vert+\vert y_j-z_j\vert\,. $

(Autoren: App/Höllig)
[Verweise]
  automatisch erstellt am 25.  1. 2006