Übung — AFB III (Verallgemeinern und Reflektieren)

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.

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.

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.

Musterlösung: Jedes Paar besteht aus genau zwei Ziffern Anzahl und genau einem Zeichen Wert: R2D2 → 01R012011D012. Der Decoder liest immer drei Zeichen: die ersten beiden ergeben die Anzahl, das dritte ist der Wert — auch wenn es eine Ziffer ist. Läufe über 99 werden geteilt (150 A → 99A 51A). Nachteil: Kurze Läufe kosten jetzt drei statt zwei Zeichen.

Musterlösung: Kommt eine Quittung erst nach dem Timeout an, hat der Sender das Paket schon erneut geschickt. Ohne Nummer könnte er diese späte Quittung für die des nächsten Pakets halten und weiterzählen, obwohl dieses verloren ging. Mit Nummer ordnet er jede Quittung eindeutig zu.

Musterlösung: Beim festen Code liegen die Grenzen fest; ein gekipptes Bit verfälscht genau ein Zeichen. Beim Huffman-Code kann das Bit ein Codewort verlängern oder verkürzen — alle folgenden Grenzen verschieben sich, bis der Strom zufällig wieder synchron ist. Kompression macht Daten also fehleranfälliger; umso wichtiger ist danach ein Fehlerschutz.

Musterlösung: Kippen \(a\) Bits von 0 auf 1 und \(b\) Bits von 1 auf 0 (\(a+b=k\)), ändert sich die Anzahl der Einsen um \(a-b=k-2b\). Da \(2b\) gerade ist, wechselt die Parität genau dann, wenn \(k\) ungerade ist. Nur dann ist die vereinbarte Parität verletzt und der Empfänger meldet einen Fehler.

Musterlösung: Soll das Syndrom \(s_2s_1s_0\) die Stelle direkt als Dualzahl angeben, muss Gruppe \(k\) genau die Stellen enthalten, deren Dualzahl an Position \(k\) eine 1 hat: \(G_0=\{1,3,5,7\}\), \(G_1=\{2,3,6,7\}\), \(G_2=\{4,5,6,7\}\). Die Stellen 1, 2, 4 liegen jeweils nur in einer Gruppe — dort kann das Prüfbit frei gesetzt werden, ohne andere Gruppen zu stören. Die übrigen Stellen 3, 5, 6, 7 tragen d0 bis d3; daraus folgen die Gruppen p0: d0 d1 d3, p1: d0 d2 d3, p2: d1 d2 d3.

Musterlösung: Ein achtes Bit ergänzt das Codewort zu gerader Gesamtparität. Beim Empfang: Gesamtparität gerade und Syndrom 0 → fehlerfrei. Gesamtparität ungerade → ungerade Fehlerzahl, bei höchstens zwei Fehlern also genau einer: an der Syndrom-Stelle korrigieren (Syndrom 0: das achte Bit selbst). Gesamtparität gerade, Syndrom ≠ 0 → Doppelfehler: nicht korrigieren, neu anfordern. Kosten: 4 Datenbits in 8 Bit, Coderate 50 %.

Musterlösung: Sinnvoll ist: erst komprimieren, dann sichern. Die Prüfbits schützen dann genau den Bitstrom, der über den Kanal geht; ein gekipptes Bit wird vor dem Huffman-Decodieren korrigiert, sodass keine Folgefehler entstehen. Umgekehrt würde Huffman die Redundanz der Prüfbits gerade entfernen und Codewortgrenzen verschieben — ein Kanalfehler im komprimierten Strom könnte nicht mehr über die Hamming-Gruppen lokalisiert werden.