Hamming Metrik

31.05.2007, 20:11

Wehm

Hamming Metrik

Hoi.

Sei A eine nichtleere Menge, n eine positive natürliche Zahl und C eine nichtleere Teilmenge von $\begin{eqnarray*} A^n \end{eqnarray*}$ , d.h . von

$\begin{eqnarray*} A^n := \{(a_1,a_2,...,a_n):a_1,...,a_n \in A \} \end{eqnarray*}$

Ferner sei $\begin{eqnarray*} d( (a_1,...,a_n),(b_1,b_2,...,b_n) ) := Anzahl der j mit a_j \not= b_j \end{eqnarray*}$

Zeigen Sie dass d eine Metrik auf C ist.

Man muss hier doch stumpf die Axiome nachrechnen

1. d(x,y) = 0 wenn x=y

Das gilt hier, ist ja trivial

2. Symmetrie d(x,y) = d(y,x)

Das ist auch trivial

Was soll man bei 1 und 2 denn nachrechnen?

3. Dreiecksungleich $\begin{eqnarray*} d(x,y) \le d(x,y) + d(y,z) \end{eqnarray*}$

Hiermit habe ich meine Probleme, es soll ja gelten

$\begin{eqnarray*} d( (a_1,...a_n), (b_1,...b_n) ) \le d( (a_1,...a_n), (b_1,...b_n) ) + d( (b_1,...,b_n), (c_1,...c_n) ) \end{eqnarray*}$

Ist doch auch klar, der Abstand zwischen a und b ist gleich dem zwischen a und b, und wenn man dann noch den positiven Abstand zwischen b und c dazuaddiert, wird die rechte Seite größer.

Ich glaube mein Problem ist, dass ich "Anzahl der j mit $\begin{eqnarray*} a_j \not= b_j \end{eqnarray*}$ " nicht verstehe.

Grüße,
Wehm

31.05.2007, 20:13

Dual Space

Auf diesen Beitrag antworten »

RE: Hamming Metrik

Zitat:

Original von Wehm
3. Dreiecksungleich $\begin{eqnarray*} d(x,y) \le d(x,y) + d(y,z) \end{eqnarray*}$

Die Dreiecksungleichung lautet aber $\begin{eqnarray*} d(x,z) \le d(x,y) + d(y,z). \end{eqnarray*}$ Deine Version gilt trivialerweise immer. Augenzwinkern

01.06.2007, 13:57

Wehm

Auf diesen Beitrag antworten »

Zu Zeigen
$\begin{eqnarray*} d((a_1,...,a_n),(c_1,...,c_n) ) \le d( (a_1,...,a_n), (b_1,...,b_n) ) + d( (b_1,...b_n),(c_1,...,c_n) ) \end{eqnarray*}$

Statt einen Doppelkreuz # für Anzahl der a_j != b_j verwende ich jetzt ein *. IRgendwie will der kein Doppelkreuz machen.

$\begin{eqnarray*} d((a_1,...,a_n),(c_1,...,c_n) )= * a_j \not= c_j \end{eqnarray*}$

$\begin{eqnarray*} d( (a_1,...,a_n), (b_1,...,b_n) ) = * a_j \not= b_j \end{eqnarray*}$

$\begin{eqnarray*} d( (b_1,...b_n),(c_1,...,c_n) ) = * b_j \not= c_j \end{eqnarray*}$

Wie soll ich daraus jetzt etwas folgern können?

Sei z. B. $\begin{eqnarray*} a_1 \not= c_1 \end{eqnarray*}$ , Rest identisch

$\begin{eqnarray*} d((a_1,...,a_n),(c_1,...,c_n)) =1 \end{eqnarray*}$

Und beim nächsten ist $\begin{eqnarray*} b_2 \not= a_2 \end{eqnarray*}$

$\begin{eqnarray*} d( (a_1,...,a_n), (b_1,...,b_n) ) =1 \end{eqnarray*}$

Damit ergibt sich
$\begin{eqnarray*} b_2 \not= c_2 \end{eqnarray*}$

$\begin{eqnarray*} d( (b_1,...b_n),(c_1,...,c_n) ) = * b_j \not= c_j \end{eqnarray*}$

Wenn alle anderen b_j und c_j übereinstimmen, dann ist das Ergebnis ja 1
$\begin{eqnarray*} d( (b_1,...b_n),(c_1,...,c_n) ) =1 \end{eqnarray*}$

Per Beispiel stimmts aber logisch schlussfolgern kann ich das leider nicht. Wie macht man das?

Gruß, Wehm.

Neue Frage »

Antworten »

Hamming Metrik

Verwandte Themen