Lauflänge, Huffman und Kompressionsverhältnis — 30 Aufgaben zur Codierung.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Aufgaben vom Wiedererkennen der Notation (AFB I) bis zur Beurteilung, wann Kompression lohnt (AFB III).
A1
Eigenschaften des Huffman-Codes
AFB I
Gib alle zutreffenden Aussagen zum Huffman-Verfahren an.
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Prüfen“.
Huffman ist verlustfrei: Die Originaldaten lassen sich exakt wiederherstellen. Bei Gleichstand sind mehrere Bäume möglich, alle mit derselben Gesamtbitzahl.
Frage: Woher weiß der Empfänger, welcher Code zu welchem Zeichen gehört?Warum? Ohne Codetabelle ist die Bitfolge nicht lesbar.
Hilfe: Präfixfrei heißt: Man erkennt das Codeende ohne Trennzeichen.
A2
Wartezeit für alle Pakete
AFB IIMix
Eine Nachricht mit 2500 Zeichen wird in Pakete mit höchstens 1000 Zeichen Nutzdaten zerlegt, das letzte Paket darf kürzer sein. Der Sender schickt ein Paket erst, wenn die Quittung des vorigen da ist; jedes Paket wartet 0,5 s auf seine Quittung. Die reine Sendezeit der Bits ist so klein, dass du sie vernachlässigen kannst. Schätze ab, wie lange die Übertragung dauert, und stelle den Regler auf etwa 0,1 s genau ein.
Schiebe den Regler auf deine Schätzung — Pfeiltasten bewegen ihn feiner. Nach dem Prüfen siehst du den Trefferbereich.
0 s5 s
Die Zahl der Pakete ergibt sich aus der Ganzzahldivision: 2500 / 1000 = 2 volle Pakete, und 2500 mod 1000 = 500 ist nicht 0, also kommt ein drittes, kürzeres Paket dazu. Drei Pakete warten je 0,5 s: 1,5 s. Wer nur 2500 / 1000 = 2 rechnet, vergisst das Restpaket.
Wie viele Pakete werden gebraucht? Ganzzahldivision und Rest helfen: Wie oft passen 1000 Zeichen in 2500, und was bleibt übrig?
Bleibt ein Rest, braucht er ein eigenes, kürzeres Paket. Die Dauer ist die Zahl aller Pakete mal die Wartezeit je Paket.
A3
Welche Bitbreite lohnt sich?
AFB III
Eine Bildzeile mit 91 Pixeln besteht aus sieben Läufen der Längen 34, 3, 5, 2, 40, 1 und 6 (abwechselnd weiß und schwarz). Sie wird mit Anzahl-Wert-Paaren gespeichert: k Bit für die Anzahl, 1 Bit für den Wert. Mit k Bit sind höchstens 2k − 1 Wiederholungen je Paar möglich, längere Läufe werden auf mehrere Paare verteilt. Entscheide dich für das k zwischen 1 und 8, bei dem die Zeile am wenigsten Speicher braucht, und gib diesen kleinsten Bedarf an.
Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Bit
k = 5 gibt 9 Paare · 6 = 54 Bit, k = 6 gibt 7 Paare · 7 = 49 Bit (der Lauf der Länge 40 passt noch in ein Paar), k = 7 gibt 7 · 8 = 56 Bit. Ein größeres k macht jedes Paar länger, ohne weitere Läufe zu sparen.
Rechne für jedes k die Zahl der Paare: Ein Lauf der Länge n braucht n geteilt durch (2k − 1), aufgerundet, Paare. Jedes Paar kostet k + 1 Bit.
Probiere k = 5, 6 und 7: Bei k = 6 passen Läufe bis 63 in ein Paar, bei k = 5 (höchstens 31) müssen zwei Läufe geteilt werden.
