Grundlagen der Informationstheorie und Kodierung

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?

  1. AABAB
  2. BABABABA
  3. CABAAAAA
Antwort und Erläuterung anzeigen

Antwort: B. ABABABA

Man beginnt mit „AB“ aus A und B. Das A 2 Zeichen zurück wird kopiert und ergibt „ABA“, dann das B, das nun 2 Zeichen zurück liegt, und ergibt „ABAB“; mit jedem kopierten Zeichen rückt auch die Kopierquelle um eins weiter, sodass nach 5 kopierten Zeichen „ABABABA“ mit 7 Zeichen entsteht. Die Länge darf also größer als die Entfernung sein, und indem gerade kopierte Zeichen als Quelle dienen, lässt sich eine lange Wiederholung eines kurzen Musters mit einem einzigen Paar darstellen.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Informationstheorie und Kodierung

  1. Bei welcher Anwendung muss beim Komprimieren verlustfreie Kompression statt verlustbehafteter Kompression verwendet werden?
  2. 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?
  3. 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?
  4. 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?
  5. An die Daten 1101 werden 3 CRC-Prüfbits mit dem Generatorpolynom x³ + x + 1 (Bitfolge 1011) angehängt. Die Prüfbits sind der Rest der Division von 1101000, also den Daten mit 3 angehängten Nullen, durch 1011, wobei bei der Division statt der Subtraktion das exklusive ODER (XOR) verwendet wird. Wie lauten die Prüfbits?