Hammingdistanz (Kombinatorik)

Neue Frage »

sonja1893 Auf diesen Beitrag antworten »
Hammingdistanz (Kombinatorik)
Will man Nachrichten über einen Sendekanal von A nach B schicken, so tritt in der Praxis das Problem auf, dass die Übertragung fehlerhaft ist, d.h. es kommt oftmals nicht genau die Nachricht an, die gesendet wurde. In der Kodierungstheorie entwirft man deshalb fehlerkorrigierende Kodes. Dazu betrachten wir 0-1-Wörter x der Länge n, d.h. x = , wobei , für i = 1, . . . , n. Sei y = ein zweites 0-1-Wort der Länge n. Der Hammingabstand d(x, y) zwischen x und y ist die Anzahl der Positionen i mit . Der Hammingball von x mit Radius r ist B(x, r) = { y | d(x, y) r }.
Wird ein Kodewort x über einen Kanal gesendet, so werden eventuell manche Bits fehlerhaft übertragen und statt x ein Wort empfangen. Nehmen wir an, dass pro Wort höchstens f Bits fehlerhaft übertragen werden. Wir wählen dann unseren Kode so, dass je zwei Kodewörter mindestens den Hammingabstand 2f +1 haben. Wird nun ein Wort x' empfangen, das kein Kodewort ist, so ersetzen wir x' durch dasjenige Kodewort xmit kleinstem Hammingabstand zu x'. Man sagt, der Kode ist f-fehlerkorrigierend.

a) Geben Sie d(x, y) an, für x = 11010010 und y = 10011000.

b) Geben Sie B(x, r) an für x = 1001 und r = 2. Welche Wörter haben Abstand 4 von x?

c) Wieviele Wörter enthalten { y | d(x, y) = k } und B(x, r)?

d) Wieviele Kodewörter hat ein f-fehlerkorrigierender Kode maximal?

e) Der 3-Wiederholungskode kodiert ein Wort w der Länge l dadurch, dass w dreimal hintereinander geschrieben wird, also durch x = www mit Länge n = 3l.
• Wie groß ist der minimale Hammingabstand zweier Kodewörter?
• Wieviele Fehler kann der 3-Wiederholungskode korrigieren?
• Wieviele Kodewörter der Länge n = 3l gibt es? Vergleichen Sie dies mit der theoretisch möglichen Anzahl von Kodewörtern eines 1-fehlerkorrigierenden Kodes.

Also die a) kann ich selber beantworten: zwischen x und y sind 3 Bits umgekippt, also ist d(x, y) = 3.
Aber der Rest ist ein bisschen zu konfus für mich.
SirJective Auf diesen Beitrag antworten »

Bei Aufgabe b) ist verlangt, alle Woerter anzugeben, deren Hammingabstand von 1001 hoechstens gleich 2 ist, wo also hoechstens 2 Bit gekippt sind.
Und es sind alle Woerter gesucht, deren Hammingabstand von 1001 gleich 4 ist, wo also 4 Bit gekippt sind.

Bei Aufgabe c) musst du bestimmen, wieviele Moeglichkeiten es gibt, genau k Bit zu kippen in einem n-Bit-Wort. Bei dieser Anzahl sollte es egal sein, welches Wort x ist, da es nur auf die Kippungen ankommt, nicht auf die Werte (ob 0->1 oder 1->0).
Und es ist gefragt, wieviele Moeglichkeiten es gibt, hoechstens r Bit zu kippen.Beide Fragen laufen darauf hinaus, "Ziehen ohne Zuruecklegen" zu spielen.

Soviel erstmal als Anfang.
Gruss,
SirJective
 
 
sonja1893 Auf diesen Beitrag antworten »

Ist das dann bei c) bzw. ? verwirrt
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »