Zehn Übungen zum Codieren, Decodieren und Berechnen der Codelänge.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Ein Wort codieren
AFB I
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Geben Sie die Codierung von NEST als Bitfolge an.
Tragen Sie die Bitfolge ohne Leerzeichen ein — Enter prüft direkt.
N 10 · E 0 · S 1111 · T 1110 → 10 0 1111 1110, am Stück 11 Bit.
Ansatz: Codewörter der Reihe nach aneinanderhängen.
Weiter: Keine Leerzeichen eintippen.
A2
Einen Bitstrom decodieren
AFB I
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Bestimmen Sie das Wort zur Bitfolge 11001011100.
Tragen Sie die Bitfolge ohne Leerzeichen ein — Enter prüft direkt.
110 → R, 0 → E, 10 → N, 1110 → T, 0 → E: RENTE. Nach jedem vollständigen Codewort beginnt man wieder am Anfang.
Ansatz: Lesen Sie Bit für Bit, bis ein Codewort passt.
Weiter: Beginnt es mit 0, ist es sofort E.
A3
Stimmt's? — Codieren und decodieren
AFB I
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Nennen Sie zu jeder Aussage, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Eine Bitfolge ist nur dann vollständig decodiert, wenn sie mit dem Ende eines Codeworts aufhört.
Ansatz: Gehen Sie jede Bitfolge von links durch.
Weiter: 111 ohne weiteres Bit: noch kein Blatt.
A4
Länge mit der Formel
AFB II
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Der Text lautet TESTER. Berechnen Sie die Beiträge der Zeichen und die Gesamtlänge.
Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls.
Zeichen
Häufigkeit h
Länge l
h · l
T
4
E
1
S
1
R
1
Summe L
6
\(L=2\cdot4+2\cdot1+1\cdot4+1\cdot3=17\) Bit. Der Code passt nicht gut zu diesem Text: T ist hier so häufig wie E, bekommt aber 4 Bit.
Ansatz: \(L=\sum h(z)\cdot l(z)\).
Weiter: Längen aus der Codetabelle ablesen.
A5
Mittlere Codewortlänge
AFB IIMix
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Ein Text aus 20 Zeichen enthält E 10-mal, N 4-mal, R 3-mal, T 2-mal und S 1-mal. Ermitteln Sie die Kennzahlen.
Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Ordnen Sie jeder Bitfolge ihr Wort zu.
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Wer die Bitfolgen von hinten liest oder nach einem Blatt nicht zur Wurzel zurückkehrt, landet bei falschen Wörtern — Präfixfreiheit gilt nur von vorn.
Ansatz: Von links beginnen, Codewort für Codewort.
Weiter: Eine 0 allein ist immer E.
A7
Bens Decodierung
AFB II
Codetabelle: E = 0, N = 10, R = 110, T = 1110, S = 1111. Ben decodiert 1011101111. Überprüfen Sie seine Schritte.
In diesem Text stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Ben hat nach T nur ein Bit weitergelesen und dann aufgegeben. Richtig: so lange Bits sammeln, bis ein Blatt erreicht ist.
Ansatz: Zählen Sie die Bits: 10 Stück.
Weiter: 2 + 4 + 4 = 10.
A8
Was folgt aus der Präfixfreiheit?
AFB IIMix
Erläutern Sie, was Präfixfreiheit für die Übertragung bedeutet — markieren Sie alle zutreffenden Aussagen.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Präfixfreiheit macht Decodieren eindeutig, aber nicht fehlerfest: Wird aus 0 (E) durch ein gekipptes Bit 1, liest der Empfänger ein längeres Codewort — die Grenzen verrutschen.
Ansatz: Was passiert, wenn im Kanal ein Bit kippt?
Weiter: Gleich lang ist ein Sonderfall, keine Bedingung.
A9
Passt der Code zum Text?
AFB IIITrick
Ein Text aus 16 Zeichen enthält S 9-mal, E 1-mal, N, R und T je 2-mal. Er wird mit der Tabelle oben codiert (E = 0 … S = 1111). Bewerten Sie diese Wahl.
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
Länge mit der Tabelle:
Länge mit einem eigenen Huffman-Baum:
Länge mit festem 3-Bit-Code:
Fazit:
Tabelle: \(9\cdot4+1\cdot1+2\cdot2+2\cdot3+2\cdot4=55\) Bit — schlechter als der feste Code mit 48 Bit. Eigener Baum: 1 + 2 = 3, 2 + 2 = 4, 3 + 4 = 7, 7 + 9 = 16; S bekommt 1 Bit, alle anderen 3 Bit: \(9+3\cdot7=30\) Bit. Ein Huffman-Code gilt immer nur für die Häufigkeiten, aus denen er gebaut wurde.
Ansatz: Tabelle: \(\sum h\cdot l\) mit S = 4 Bit.
Weiter: Eigener Baum: das häufige S bekommt 1 Bit.
A10
Lohnt sich Huffman?
AFB III
Die Codetabelle muss mitgeschickt werden. Beurteilen Sie, wie sich der Vorteil von Huffman gegenüber einem festen Code entwickelt.
Wählen Sie für jede Zeile eine Stufe: 1 = großer Nachteil, 2 = kleiner Nachteil, 3 = etwa gleich, 4 = kleiner Vorteil, 5 = großer Vorteil. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = großer Nachteil5 = großer Vorteil
ein Text aus 8 Zeichen, alle verschieden
ein Buch mit 500 000 Zeichen normaler Sprache
ein langer Text, alle 26 Buchstaben gleich häufig
ein langer Text, fast nur aus einem Zeichen
eine SMS mit 40 Zeichen deutscher Sprache
Die Tabelle kostet eine feste Menge Bits. Bei kurzen Texten frisst sie die Einsparung, bei langen Texten mit ungleichen Häufigkeiten fällt sie kaum ins Gewicht. Gleich häufige Zeichen bringen keinen Vorteil.
Ansatz: Zwei Fragen: Wie lang ist der Text? Wie ungleich die Häufigkeiten?
