0 Daumen
790 Aufrufe

Aufgabe:

"Hamming Metrik:"

Sei A = {a1, a2, ..., aM} ein endliches Alphabet.
Auf den Codes x = (x1, ..., xN) der länge N, mit xn ∈ A für n = 1, ..., N , definiert man d: AN x AN → ℝ (x,y) ↦ d(x,y) durch
d(x,y) := Anzahl der Elemente in {n ∈ {1, ..., N}: xn ≠ yn} := | {n ∈ {1, ..., N}: xn ≠ yn} |

Zeigen Sie, dass dadurch eine Metrik auf dem Coderaum definiert wird.

Problem/Ansatz:

Also die ersten beiden Bedingungen einer Metrik d(x,y) = 0 ⇔ x=y und d(x,y) = d(y,x) sind mir klar.



Bei der dritte Bedingung: d(x,y) ≤ d(x,z) + d(z,y)  bin ich mir nicht sicher.

Darf ich einfach sagen: " Sei A das Alphabet mit A = {0,1} " und das damit beweisen?

Oder muss ich den Beweis allgemein halten, also auch für ein Alphabet welches beispielsweise die Länge M=100 hat?



Für "Bits" wie sie in der Informatik vorkommen (Also A = {0,1}) kann ich die Aufgabe alleine lösen, aber bei der anderen Variante hätte ich keine Idee.

Avatar von

Hallo,

die Größe des Alphabets spielt für diese Frage keine Rolle. Die Hamming-Metrik zählt ja nur die Anzahl der Abweichungen. Ob es für eine eventuelle Abweichung nur eine Mölgihckeit gibt (1 statt 0 oder 0 statt 1) oder ob es viele Varianten gibt, ist hier egal.

Also geht der Beweis für \(A=\{0,1\}\) genauso für jedes andere Alphabet.

Gruß

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community