Grafikzeile oder Text?
AFB I–IIVerglichen werden zwei Datensätze: (1) eine Schwarz-Weiß-Grafikzeile aus 100 Pixeln: 40 weiß, 20 schwarz, 40 weiß; (2) der Text SEESTERNE. Lauflänge speichert die Anzahl mit 7 Bit (Grafik) bzw. 4 Bit (Text), der Wert braucht 1 Bit (Grafik) bzw. 3 Bit (Text).
- Berechnen Sie für die Grafikzeile die Länge mit Lauflänge und mit Huffman.
- Ermitteln Sie für den Text die Länge mit festem Code, Lauflänge und Huffman.
- Erklären Sie die Ergebnisse mit den Eigenschaften der Daten.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Lauflänge: 3 Läufe · (7 + 1) = 24 Bit. Huffman: zwei Zeichen → je 1 Bit → 100 Bit (kein Gewinn gegenüber 1 Bit je Pixel).
Erwartungshorizont zu Aufgabe b)
Fest: 5 Zeichen → 3 Bit → 27 Bit. Lauflänge: Läufe S, EE, S, T, E, R, N, E → 8 · (4 + 3) = 56 Bit. Huffman: z. B. T + R = 2, N + S = 3, 2 + 3 = 5, E 4 + 5 = 9 → E 1 Bit, übrige 3 Bit → \(4+5\cdot3=19\) Bit.
Erwartungshorizont zu Aufgabe c)
Die Grafik hat lange Läufe, aber zwei gleich wichtige Zeichen — ideal für Lauflänge. Der Text hat kaum Läufe, aber ein sehr häufiges Zeichen (E) — ideal für Huffman.
Kombinieren wie beim Fax
AFB II–IIIBeim Fax (Gruppe 3) wird jede Zeile erst in Lauflängen zerlegt. Die Lauflängen werden dann nicht mit fester Bitbreite gespeichert, sondern mit einem Huffman-Code, in dem häufige Lauflängen kurze Codewörter haben.
Eine Testseite liefert 1000 Läufe mit dieser Verteilung:
| Lauflänge | 1–3 | 4–15 | 16–63 | 64–1728 |
|---|---|---|---|---|
| Anteil | 45 % | 30 % | 15 % | 10 % |
| Codewortlänge (Huffman) | 2 Bit | 4 Bit | 7 Bit | 11 Bit |
- Interpretieren Sie die Verteilung: Warum sind kurze Läufe am häufigsten?
- Bestätigen Sie, dass ein Lauf mit dieser Codierung im Mittel 4,25 Bit braucht, und vergleichen Sie mit einer festen Bitbreite von 11 Bit.
- Erörtern Sie Vor- und Nachteile dieser Kombination gegenüber reiner Lauflänge.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Buchstabenstriche sind schmal und die Abstände zwischen ihnen kurz — dort wechseln Schwarz und Weiß oft. Lange Läufe gibt es nur an Rändern und Leerzeilen.
Erwartungshorizont zu Aufgabe b)
\(0{,}45\cdot2+0{,}3\cdot4+0{,}15\cdot7+0{,}1\cdot11=0{,}9+1{,}2+1{,}05+1{,}1=4{,}25\) Bit. Mit festen 11 Bit (nötig für Läufe bis 1728): \(k=\tfrac{4{,}25}{11}\approx39\,\%\) — für 1000 Läufe 4250 statt 11 000 Bit.
Erwartungshorizont zu Aufgabe c)
Pro: sehr kurze Codes für häufige kurze Läufe, keine Obergrenze durch feste Bitbreite, Tabelle ist genormt und muss nicht übertragen werden. Contra: aufwendigere Decodierung; ein Bitfehler verschiebt die Codewortgrenzen und kann den Rest der Zeile zerstören. Für Faxgeräte überwiegen die Vorteile — die Zeile wird bei Fehlern ohnehin neu synchronisiert.