Kompression und Fehlererkennung: Zusammenfassung – Informatik Leistungskurs

Daten codieren und komprimieren

Codes fester Länge übersetzen Zeichen und Farben in Bits; Lauflänge fasst Wiederholungen zusammen, das Verhältnis $k$ misst den Gewinn.

Code fester Länge

Mit $n$ Bit gibt es $2^{n}$ Codewörter; für $N$ Zeichen das kleinste $n$ mit $2^{n}\ge N$.

$2^{n}\ge N$

Rastergrafik

RGB: drei Kanäle zu je 8 Bit, Hexcode #RRGGBB. Speicher = Pixel mal Farbtiefe.

$S=B\cdot H\cdot b$

Lauflänge

Jeder Lauf wird ein Paar in der Reihenfolge Anzahl-Wert: rrrssssgrr → 3r4s1g2r.

$L=\text{Läufe}\cdot\text{Bits je Paar}$

Kompressionsverhältnis

Komprimiert durch original, gleiche Einheit; Datenersparnis ist der Rest bis 100 %.

$k=\tfrac{S_{\text{komp}}}{S_{\text{orig}}}$, Ersparnis $(1-k)\cdot100\,\%$

Speicherbedarf einer Rastergrafik

$S=\text{Breite}\cdot\text{Höhe}\cdot\text{Farbtiefe}$

Ergebnis in Bit; durch 8 für Byte. Beispiel: $800\cdot600\cdot24$ Bit $=1{,}44$ MB.

Bit und Byte

Formeln liefern Bit, Dateien werden in Byte angegeben. Faktor 8 nie vergessen.

Huffman, Implementierung und Verlust

Häufige Zeichen bekommen kurze Codewörter; beide Verfahren lassen sich mit wenigen Zeichenketten- und Baumoperationen implementieren. Wo das nicht reicht, wird bewusst Information weggelassen.

Huffman-Baum

Immer die zwei kleinsten Häufigkeiten zusammenfassen; Codewort = Weg zum Blatt, links 0, rechts 1 — präfixfrei.

$L=\sum h(z)\cdot l(z)$

Lauflänge in Java

code = code + anzahl + wert je Lauf; dekodieren: Ziffern sammeln mit anzahl · 10 + Ziffer.

c - '0'

Huffman dekodieren

Mit BinTree: 0 → getLeft(), 1 → getRight(); bei isLeaf() Zeichen ausgeben, zurück zur Wurzel.

linear in der Bitzahl

Verlustbehaftet

Entfernt zusätzlich Irrelevanz (JPEG, MP3): Quantisieren, Unterabtasten. Nicht umkehrbar.

$k=\tfrac{b_{\text{neu}}}{b_{\text{alt}}}$

Länge der Huffman-Codierung

$L=\sum h(z)\cdot l(z)$, $\bar l=\tfrac{L}{n}$

Beispiel ANANASBANANE: 24 Bit statt 36 Bit mit 3-Bit-Code. Die Codetabelle kommt bei der Übertragung dazu.

Verfahren wählen

Lauflänge bei langen Läufen, Huffman bei ungleichen Häufigkeiten, verlustbehaftet nur, wo nicht jedes Bit zählt. Kein verlustfreies Verfahren verkürzt jede Datei.

Sicher übertragen

Ein Protokoll regelt Format und Ablauf; Prüfbits machen Fehler erkennbar oder sogar korrigierbar.

Protokoll

Syntax (Rahmen #nr;daten$), Semantik, Ablauf. Nummern stellen die Reihenfolge wieder her.

Kopf + Nutzdaten

Stop-and-Wait

Senden, auf ACKnr warten; Timeout → erneut senden. Duplikate verwerfen, aber quittieren.

ACKnr

Paritätsbit

Gerade Parität: Einsen insgesamt gerade. Erkannt wird jede ungerade Anzahl gekippter Bits, korrigiert keine.

$p=E\bmod 2$

Hamming (7,4)

p0 p1 d0 p2 d1 d2 d3; p0: d0 d1 d3, p1: d0 d2 d3, p2: d1 d2 d3, jede Gruppe gerade.

korrigiert 1 Fehler

Fehlerstelle im (7,4)-Hamming-Code

$\text{Stelle}=s_0+2\,s_1+4\,s_2$

$s_k$ = Parität der Gruppe von $p_k$ mit Prüfbit; 0 heißt kein Fehler. In Java: Index = Stelle − 1.

Regel 1 — Stellen und Indizes

Stellen werden ab 1 gezählt, Reihungen und Zeichenketten ab 0.

Regel 2 — Sonderfälle prüfen

Leerer Text, Ziffern in den Daten, verlorenes Paket, zwei gekippte Bits: Ein Entwurf ist erst gut, wenn er diese Fälle behandelt.

1AFB I — Reproduzieren10 Aufgaben› ?Selbsttest40 Fragen mit Auswertung›