Deutsch
Menü

Grundlagen der Informationstheorie und Kodierung

Welche Aussage beschreibt das Prinzip des LZ77-Verfahrens, das in ZIP, gzip und anderen Formaten verwendet wird, richtig?

  1. AHäufigen Symbolen werden kurze, seltenen Symbolen lange Codewörter zugeordnet
  2. BAnteile, die menschliche Augen oder Ohren kaum bemerken, werden verworfen, um die Daten zu verkleinern
  3. CEine Zeichenfolge, die schon einmal vorkam, wird durch ein Paar aus der Entfernung zur früheren Position und der Länge ersetzt
Antwort und Erläuterung anzeigen

Antwort: C. Eine Zeichenfolge, die schon einmal vorkam, wird durch ein Paar aus der Entfernung zur früheren Position und der Länge ersetzt

Das LZ77-Verfahren nutzt die bereits verarbeiteten Daten wie ein Wörterbuch und ersetzt eine erneut auftretende Zeichenfolge durch ein Paar aus Entfernung und Länge: „ab so vielen Zeichen zurück, so viele Zeichen lang“. Es verkleinert Daten mit vielen Wiederholungen, ohne die Symbolwahrscheinlichkeiten vorher zu kennen, und ist eine verlustfreie Kompression, die die ursprünglichen Daten vollständig wiederherstellt. Das Deflate-Verfahren von ZIP und gzip kodiert das Ergebnis der LZ77-Ersetzung zusätzlich mit einem Huffman-Code.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Informationstheorie und Kodierung

  1. Mit dem LZ77-Verfahren komprimierte Daten werden wiederhergestellt. Die Daten lauten in dieser Reihenfolge „Zeichen A“, „Zeichen B“, „(Entfernung 2, Länge 5)“. (Entfernung d, Länge L) bedeutet, L-mal Zeichen für Zeichen „das Zeichen, das d Zeichen vor dem Ende der bereits wiederhergestellten Zeichenkette steht, ans Ende kopieren“. Welche Zeichenkette ergibt sich?
  2. Bei welcher Anwendung muss beim Komprimieren verlustfreie Kompression statt verlustbehafteter Kompression verwendet werden?
  3. An eine Bitfolge von Daten wird ein gerades Paritätsbit angehängt, sodass die Zahl der Einsen gerade ist, und mitgesendet. Welche Aussage über die Prüfung, bei der der Empfänger die Einsen zählt, ist richtig?
  4. Gesendet werden 4 Zeilen mit je 4 Datenbits; an jede Zeile wird rechts ihr gerades Paritätsbit angehängt, und am Ende folgt eine Zeile mit den geraden Paritätsbits der Spalten (Kreuzparität). Empfangen wurden Zeile 1: 1011 1, Zeile 2: 0100 0, Zeile 3: 1100 0, Zeile 4: 0101 0, Paritätszeile: 0100 (das rechte Bit jeder Zeile ist die Zeilenparität). Wenn genau 1 Bit falsch ist, an welcher Position liegt es?
  5. Die Daten werden byteweise addiert, und die unteren 8 Bit der Summe werden als Prüfwert (Prüfsumme) angehängt und mitgesendet. Welchen Fehler kann diese Prüfung nicht erkennen?