Datenrepräsentation und -übertragung Übungsblatt 1 Prof. Dr. Dirk

Datenrepräsentation und -übertragung
Übungsblatt 1
Prof. Dr. Dirk Hoffmann
Aufgabe 1: Shannon-Fano Kompression
Aufgabe 5: Arithmetische Codierung
Konstruieren Sie ein Beispiel das zeigt, dass der Shannon-Fano Algorithmus für manche
Nachrichten ein schlechteres Ergebnis liefert als der Algorithmus von Huffman.
a)
b)
Aufgabe 2: Huffman-Bäume
c)
Baum 1
Baum 2
Baum 3
Codieren Sie die Nachricht abb mit Hilfe der Arithmetischen Codierung.
Codieren Sie die Nachrichten a, aa und aaa unter Verwenden der gleichen
Wahrscheinlichkeitsverteilung wie in a). Was stellen Sie fest?
Wiederholen Sie die Codierung von Teilaufgabe a) unter Verwendung eines
Endezeichens.
Baum 4
Aufgabe 6: Burrows-Wheeler-Transformation
Nehmen Sie an, die Burrows-Wheeler-Transformation erzeugt die folgende Ausgabe:
Nachricht:
Index
!
a)
b)
c)
!
!
!
a)
BNNBUNNEAAAA
5
Vervollständigen Sie die abgebildete Rotationsmatrix:
B
Welche der oben dargestellten Bäume sind keine Huffman-Bäume?
Welcher der Bäume repräsentiert einen Huffman-Code zur Codierung der
Zeichenkette „ARKANSAS“?
Wie viele andere Huffman-Bäume gibt es für die Zeichenkette „ARKANSAS“?
Konstruieren Sie die Bäume.
N
N
B
U
Aufgabe 3: Ternäre Huffman-Codes
N
Gegeben sei das folgende Alphabet mit zugehörigen Auftrittswahrscheinlichkeiten:
N
A
B
C
D
E
F
G
0.49
0.26
0.12
0.04
0.04
0.03
0.02
a)
b)
c)
Finden Sie einen binären Huffman-Code.
Berechnen Sie die mittlere Codewortlänge.
Finden sie einen ternären Huffmann-Code. Im Gegensatz zu binären Codes
besitzen ternäre Codes drei Zeichen (0,1,2) zur Codierung der Zeichenketten.
Aufgabe 4: Lempel-Ziv Kompression
a)
b)
Codieren Sie die Nachricht „IN ULM UM ULM UND UM ULM HERUM“ mit der
Hilfe des Lempel-Ziv 77 Algorithmus.
Decodieren Sie die folgende Nachricht:
<0,0,B><0,0,A><0,0,N><2,2,E>,<4,3,B><3,1,U>
E
A
A
A
A
b)
Wie lautet die Originalnachricht?
Aufgabe 7: Burrows-Wheeler-Transformation (2)
Ist der Einsatz der Burrows-Wheeler-Transformation sinnvoll, wenn die Eingabedaten
a)
b)
aus einer Shannon‘schen Datenquelle stammen?
vorher optimal verschlüsselt wurden?

Download Report