Mit einer Codetabelle arbeiten
AFB I–IIDie Abbildung zeigt einen Codebaum (links 0, rechts 1) für die Zeichen A, E, L, S und T.
- Geben Sie die Codetabelle an und codieren Sie das Wort SALAT.
- Wenden Sie den Code an, um die Bitfolge 011100110 zu decodieren.
- Weisen Sie nach, dass der Code präfixfrei ist.
- Erläutern Sie die Folgen, wenn bei der Übertragung von ESEL das erste Bit kippt.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
A 00, E 01, L 10, S 110, T 111. SALAT → 110 00 10 00 111 = 11000100111 (11 Bit).
Erwartungshorizont zu Aufgabe b)
01 → E, 110 → S, 01 → E, 10 → L: ESEL.
Erwartungshorizont zu Aufgabe c)
Die 2-Bit-Codewörter 00, 01, 10 sind keine Anfänge von 110 oder 111 (die mit 11 beginnen); 110 und 111 unterscheiden sich im letzten Bit. Oder: Alle Zeichen stehen in Blättern.
Erwartungshorizont zu Aufgabe d)
111 → T, 10 → L, 01 → E, 10 → L: TLEL. Ein einziges gekipptes Bit verschiebt die Codewortgrenzen, sodass mehrere Zeichen falsch sind — der Empfänger bemerkt den Fehler nicht, weil alle Codewörter gültig sind.
Decodieren in Python
AFB II–IIIEin Text aus 1000 Zeichen wird Huffman-codiert. Häufigkeiten und Codewörter:
| Zeichen | E | N | R | I | S | T |
|---|---|---|---|---|---|---|
| Häufigkeit | 350 | 200 | 150 | 120 | 100 | 80 |
| Codewort | 00 | 10 | 010 | 011 | 110 | 111 |
Die Codetabelle wird mitgeschickt: je Zeichen 8 Bit für das Zeichen, 4 Bit für die Codewortlänge und das Codewort selbst.
- Berechnen Sie die Länge des codierten Textes und der Codetabelle.
- Beurteilen Sie den Nutzen der Kompression im Vergleich zu 8 Bit je Zeichen und zu einem Code fester Länge.
- Implementieren Sie eine Python-Funktion
decodiere(bits, tabelle).tabelleist ein Dictionary wie{"00": "E", "10": "N", …},bitseine Zeichenkette aus 0 und 1. - Erweitern Sie die Funktion so, dass sie einen Übertragungsfehler meldet, wenn am Ende Bits übrig bleiben oder der Puffer länger als das längste Codewort wird.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Text: \(350\cdot2+200\cdot2+150\cdot3+120\cdot3+100\cdot3+80\cdot3=2450\) Bit. Tabelle: \(6\cdot(8+4)+(2+2+3+3+3+3)=72+16=88\) Bit. Zusammen 2538 Bit.
Erwartungshorizont zu Aufgabe b)
ASCII: 8000 Bit → \(k\approx32\,\%\). Fester 3-Bit-Code (6 Zeichen): 3000 Bit (+ kleine Tabelle) → Huffman spart gegenüber diesem noch gut 15 %. Die Tabelle fällt bei 1000 Zeichen kaum ins Gewicht; der Code lohnt sich.
Erwartungshorizont zu Aufgabe c)
def decodiere(bits, tabelle): text = "" puffer = "" for b in bits: puffer = puffer + b if puffer in tabelle: text = text + tabelle[puffer] puffer = "" return text
Weil der Code präfixfrei ist, ist das erste gefundene Codewort immer das richtige.
Erwartungshorizont zu Aufgabe d)
maxlen = max(len(c) for c in tabelle) … # in der Schleife nach puffer = puffer + b: if len(puffer) > maxlen: return None # ungültige Bitfolge if puffer != "": return None # Reste am Ende
Rückgabe None signalisiert den Fehler. Hinweis: Bei vollständigen Codebäumen wie hier kann der Puffer nie zu lang werden — dann bleibt nur die Prüfung am Ende.