Daten komprimieren und übertragen: Zusammenfassung – Informatik Grundkurs

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$. ASCII: 7 Bit, gespeichert in 1 Byte.

$2^{n}\ge N$

Rastergrafik

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

$S=B\cdot H\cdot\text{Farbtiefe}$

Lauflänge

Jeder Lauf wird ein Anzahl-Wert-Paar: WWWWSSSW → 4W 3S 1W. Mit $k$ Bit höchstens $2^{k}-1$ Wiederholungen.

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

Kompressionsverhältnis

Komprimiert durch original, gleiche Einheit. Über 100 %: die Datei ist gewachsen.

$k=\tfrac{S_{\text{komp}}}{S_{\text{orig}}}$, Einsparung $1-k$

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-Codierung

Häufige Zeichen bekommen kurze, seltene lange Codewörter — ohne Trennzeichen eindeutig lesbar.

Baum bauen

Immer die zwei kleinsten Häufigkeiten zusammenfassen; neue Knoten zählen mit. Die Wurzel trägt die Textlänge.

kleinste + zweitkleinste

Codewörter

Weg von der Wurzel zum Blatt, links 0, rechts 1. Gleichstände dürfen frei entschieden werden.

Tiefe = Codewortlänge

Präfixfrei

Kein Codewort ist Anfang eines anderen, weil alle Zeichen in Blättern stehen.

eindeutig decodierbar

Decodieren

Bit für Bit durch den Baum; im Blatt Zeichen notieren und zurück zur Wurzel.

nach jedem Blatt: Wurzel

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. Kein verlustfreies Verfahren verkürzt jede Datei.

Daten übertragen

Sender, Kanal und Empfänger brauchen eine gemeinsame Vereinbarung — das Protokoll regelt Format, Bedeutung und Ablauf.

Kommunikationsmodell

Sender codiert, Kanal transportiert, Empfänger decodiert. Störungen kippen oder verschlucken Bits.

Sender → Kanal → Empfänger

Protokoll

Syntax (Format), Semantik (Bedeutung), Ablauf (Reihenfolge, Fehlerreaktion).

z. B. #nr;daten$

Pakete

Lange Nachrichten zerlegen; Kopf mit Nummer und Länge. Die Nummer stellt die Reihenfolge wieder her.

Kopf + Nutzdaten

Stop-and-Wait

Senden, auf ACK mit Nummer warten; Timeout → erneut senden. Duplikate verwerfen, aber quittieren.

ACKnr

Übertragungsdauer

$t=\dfrac{\text{Datenmenge}}{\text{Datenrate}}$

Datenrate in bit/s: 25 MB = 200 Mbit, bei 50 Mbit/s also 4 s.

Regel 1 — Einheiten

Erst alle Größen in dieselbe Einheit bringen (Bit/Byte, KB/MB), dann rechnen.

Regel 2 — Sonderfälle prüfen

Leere Nachricht, Sonderzeichen in den Daten, verlorenes Paket, verlorene Quittung: Ein Entwurf ist erst gut, wenn er diese Fälle behandelt.

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