Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
Jörg Widmer

Übungsblatt 4

Übung: 17.05.2002

Die Aufgaben, die auf dieser Seite ausgefüllt werden können, werden auch über das Web ausgewertet. Dazu muß die Matrikelnummer eingegeben werden und das Ganze abgeschickt werden. Voraussetzung ist allerdings, daß der Studierende auch für die elektronische Auswertung angemeldet ist.


Aufgabe 1: Hamming Code

Gegeben sei folgender Code:

0000 0000A
0000 0111B
0011 1000C
1100 0001D
0001 1110E

  1. Wie groß ist die Hammingdistanz dieses Codes?

    1 2 3 4 5 6 7 8

  2. Bei wievielen Bitfehlern können also fehlerhafte Codewörter noch eindeutig decodiert werden?

    1 2 3 4 5 6 7 8

  3. Ein Empfänger erhält folgende Codewörter:

    1100 0001 A B C D E
    0001 1000 A B C D E
    0000 1110 A B C D E
    0000 0111 A B C D E
    0001 1100 A B C D E

    Welche Zeichen wurden Übermittelt?



Aufgabe 2 (Hamming-Code)

Folgende Daten sind im Hammingcode kodiert (even parity):
  1. 0 1001 1011
    01101 10101 11101 11011 01010

  2. 0 0100 0111
    01101 10101 11101 11011 01010

Es können höchstens 1-Bit-Fehler auftreten (d.h. der Code ist in der Lage, 1-Bit-Fehler zu beheben). Wie heißen die übertragenen Nutzdaten?

Achtung, die Bits sind von links nach rechts durchnummeriert! (Lösungshinweis: Tanenbaum, Kapitel 3.2.1.)

Aufgabe 3 (CRC)

Führen Sie den CRC für folgende Parameter aus:

M(x): 111001101
G(x): x^5 + x^3 + x + 1
T(x)= ?

1010111010101010 11100110101010 10101100101110 101101110110 1001010011010

Freiwillige Zusatzaufgabe: Schreiben Sie ein Programm (in einer beliebigen Programmiersprache) fuer den CRC, anstatt das Polynom von Hand zu berechnen. Wie läßt sich so ein Programm effizient gestalten?

Aufgabe 4 (Flußkontrolle)

Eine Reihe von Datenpaketen der Größe 100 bit wird ununterbrochen über eine zuverlässige 9600 bit/s-Verbindung übertragen. Gemäß dem Stop-and-Wait-Protokoll wird nach jedem gesendeten Paket auf eine Bestätigung gewartet. Die Ausbreitungsgeschwindigkeit betrage 2*108 m/s, Sender und Empfänger seien 10 km voneinander entfernt. Die Verarbeitungszeiten bei Sender und Empfänger seinen vernachlässigbar, ebenso die Paketlängen der ACKs.
  1. Zu wieviel Prozent wird die Übertragungsrate von 9600 bit/s bei diesem Protokoll nur ausgenutzt?
    95,82 96,00 99,05 99,80

  2. Die Bitfehlerrate dieser Verbindung betrage 10-4, d.h. von 104 übertragenen Bits ist im Mittel eines fehlerhaft. Wie groß ist die Wahrscheinlichkeit, daß ein ganzes Paket korrekt übertragen wird?
    0,00 % 1,00 % 99,00 % 99,05 % 99,90 % 100,00 %

  3. Wieviele Pakete von 100 übertragenen kommen im Durchschnitt also korrekt an?

  4. Geben Sie nun für diese fehlerbehaftete Verbindung die Effizienz an, d.h. zu wieviel Prozent die Übertragungsleistung der Leitung genutzt wird.
    0 % rund 1 % 98,01 % 98,06 % 100 %

Abgabedaten:

Matrikelnummer:  Password: 

Universität:
Mannheim
Freiburg
andere

Jörg Widmer widmer@pi4.informatik.uni-mannheim.de