MINT lernen

Abituraufgaben: Codierung im Abitur

Lauflänge für ein Display, Huffman für einen Sensor.

Dein Fortschritt:
0 / 0 Aufgaben
1

Pixelgrafik für ein Display

AFB I–II

Ein kleines Display zeigt Symbole in 8 × 8 Pixeln (w = weiß, s = schwarz). Die Zeilen eines Symbols werden zeilenweise gespeichert. Die ersten drei Zeilen lauten:

Zeile 0: wwwsswww
Zeile 1: wwssssww
Zeile 2: wssssssw
  1. Wenden Sie die Lauflängencodierung in der Notation Anzahl-Wert auf die drei Zeilen an.
  2. Berechnen Sie Kompressionsverhältnis und Datenersparnis für diese drei Zeilen, wenn jedes Zeichen gleich viel Speicher belegt.
  3. Begründen Sie, warum man bei der Codierung ganzer Bilder vereinbaren sollte, ob eine Zeile immer mit w beginnt.

Hinweise

Hinweis zu Aufgabe a)
Folgen gleicher Pixel zählen, Anzahl vor Wert.
Hinweis zu Aufgabe b)
24 Zeichen im Original — wie viele nach der Codierung?
Hinweis zu Aufgabe c)
Denken Sie an ein Protokoll, bei dem man nur Anzahlen speichert.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Zeile 0: 3w2s3w · Zeile 1: 2w4s2w · Zeile 2: 1w6s1w.

Erwartungshorizont zu Aufgabe b)

Original 24 Zeichen, codiert 18 Zeichen. Verhältnis 18 : 24 = 0,75; Datenersparnis (1 − 0,75) · 100 % = 25 %.

Erwartungshorizont zu Aufgabe c)

Wechseln sich w und s immer ab, reicht es, nur die Anzahlen zu speichern (3 2 3). Dann muss eindeutig feststehen, mit welcher Farbe begonnen wird — sonst ist die Decodierung mehrdeutig. Beginnt eine Zeile mit s, notiert man zuerst eine 0 für w. So eine Vereinbarung ist Teil eines Protokolls zwischen Sender und Empfänger.

2

Huffman für einen Sensor

AFB II–III

Ein Umweltsensor sendet Zustandsmeldungen als einzelne Buchstaben: N (normal), W (Warnung), F (Fehler), A (Alarm). In einer Stichprobe von 100 Meldungen kamen vor: N 70-mal, W 20-mal, F 6-mal, A 4-mal.

  1. Erstellen Sie mit dem Huffman-Verfahren einen Code für die vier Meldungen. Stellen Sie den Baum dar.
  2. Berechnen Sie die Bitzahl für die 100 Meldungen und vergleichen Sie mit einer festen Codelänge von 2 Bit.
  3. Beurteilen Sie den Einsatz des Codes, wenn sich im Winter die Häufigkeiten stark ändern.

Hinweise

Hinweis zu Aufgabe a)
Zuerst A (4) und F (6) zusammenfassen.
Hinweis zu Aufgabe b)
Häufigkeit mal Codelänge, summiert über alle vier.
Hinweis zu Aufgabe c)
Was passiert mit der Bitzahl, wenn plötzlich A häufig ist?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

A 4 + F 6 → 10; 10 + W 20 → 30; 30 + N 70 → 100. Codes (links 0, rechts 1): N = 1, W = 01, F = 001, A = 000 (andere Beschriftung gleichwertig).

Erwartungshorizont zu Aufgabe b)

70 · 1 + 20 · 2 + 6 · 3 + 4 · 3 = 70 + 40 + 18 + 12 = 140 Bit. Feste Länge: 100 · 2 = 200 Bit. Verhältnis 140 : 200 = 0,7, Ersparnis 30 %.

Erwartungshorizont zu Aufgabe c)

Der Code ist auf die Stichprobe optimiert. Werden A und F häufiger, kosten ihre 3-Bit-Codes mehr, im Extremfall mehr als die feste Länge. Möglich: Code regelmäßig neu berechnen und die Codetabelle mitsenden, oder bei feste Länge bleiben. Begründete Abwägung erwartet.