Aufgabenblock — AFB III
Begründen statt nur rechnen: widerlegen, herleiten, entwerfen und beurteilen. Formulieren Sie Ihre Antwort zuerst selbst in ganzen Sätzen, bevor Sie die Musterlösung aufklappen.
Widerlegen Sie die Behauptung: „Ein gutes verlustfreies Verfahren macht jede Datei kleiner.“
Hinweis: Zählen statt rechnen.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Es gibt \(2^{n}\) Dateien mit genau \(n\) Bit, aber nur \(2^{0}+2^{1}+\dots+2^{n-1}=2^{n}-1\) kürzere Bitfolgen. Ein verlustfreies Verfahren muss verschiedene Dateien auf verschiedene Ergebnisse abbilden, sonst ließe es sich nicht umkehren. Also bleibt mindestens eine Datei übrig, die nicht kürzer wird.
Bewerten Sie den Vorschlag, Fotos vor der Lauflängencodierung auf 16 Graustufen zu runden.
Hinweis: Betrachten Sie Speicher und Qualität getrennt.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Rohe Fotopixel unterscheiden sich fast immer leicht — Lauflänge erzeugt dann fast nur Läufe der Länge 1 und vergrößert die Datei. Nach dem Runden fallen viele Nachbarn auf dieselbe Stufe; es entstehen lange Läufe, und schon das Runden halbiert den Speicher (8 → 4 Bit). Der Preis ist eine bleibende Abweichung von bis zu 8 Graustufen und sichtbare Stufen in Verläufen. Für Vorschaubilder ist der Vorschlag sinnvoll, für Archiv- oder Diagnosebilder nicht.
Begründen Sie, warum jeder aus einem Codebaum abgelesene Code präfixfrei ist.
Hinweis: Wo stehen die Zeichen?
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Wäre Codewort \(u\) Präfix von \(v\), läge der Knoten von \(u\) auf dem Weg von der Wurzel zu \(v\). Dann hätte er Kinder, wäre also kein Blatt. Zeichen stehen aber nur in Blättern — Widerspruch.