Hammingdistanz (Kombinatorik) |
19.05.2004, 15:27 | sonja1893 | Auf diesen Beitrag antworten » |
Hammingdistanz (Kombinatorik) 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. |
||
19.05.2004, 17:19 | 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 |
||
20.05.2004, 12:14 | sonja1893 | Auf diesen Beitrag antworten » |
Ist das dann bei c) bzw. ? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|