Vorlesung 04 Entropie und Redundanz

Termin¶

Montag, 07.04.2025 in Raum L2.09

Ziele¶

Entropie und Redundanz verstehen
Anwendung der Informationstheorie: Kompression und Fehlerkorrektur

Drehbuch¶

Was	Dauer	Material
Wiederholung: Was ist Information? Was ist Entropie?	15 min	DAVT-03-Information.pdf
Übungsaufgaben 1 + 2	25 min	DAVT-A03-Information.pdf
Einführung oder Wiederholung Binärbäume	15 min	Wikipedia
Übungsaufgaben 3 + 4	35 min	DAVT-A03-Information.pdf

Ergebnisse¶

Aufgabe 01¶

"Es schneit in Dubai." enthält am meisten Information, da es am unwahrscheinlichsten ist. "In Los Angeles scheint die Sonne." gilt eigentlich fast immer oder zumindest häufiger als "Es regnet in Furtwangen." und ist daher auf dem letzten Platz, weil es den geringsten Informationsgehalt hat.

Die Aufgabe ist so gedacht, dass man die Information im Sinne der Bedeutung interpretiert. Man könnte auch nach der Anzahl der Zeichen gehen und dann anhand der relativen Häufigkeiten der Zeichen argumentieren. In der Klausur wird dies klarer formuliert. Lernziel ist hier das Verständnis, dass unwahrscheinliche Ereignisse einen höheren Informationsgehalt haben.

Aufgabe 02¶

Lösungen:

H("AABBCCDD") = 2 Bit alle Zeichen gleich wahrscheinlich: P("A") = 1/4, I("A") = -log(1/4) = 2 also 4 * 1/4 * 2 = 2

H("AAAABCCD") = 1,75 Bit unterschiedliche Wahrscheinlichkeiten, aber immer Zweierpotenzen und daher ohne Taschenrechner zu berechnen.

H("AAAAAAAA") = 0 Bit da keine Information drin steckt. Immer nur "A" ist eine Art Prüfsignal.

Aufgabe 03¶

Lösungen:

AABBCCDD --> A: 00, B: 01, C: 10, D: 11

Binärbaum A3 a

Code A3 a

AAAABCCD --> A: 1, B: 000, C: 01, D: 001

Binärbaum A3 b

Code A3 b

Hinweis zum Begriff Präfixcode: das ist dasselbe wie präfixfreier Code, also ein Code bei dem kein anderer Code zu Beginn eines anderen vorkommt. Das ermöglicht die sequentielle Decodierung.

Aufgabe 04¶

Für den ersten Fall werden insgesamt 16 Bit benötigt, also 2 Bit pro Zeichen. Das entspricht genau der Entropie. Also ist der Code optimal.

Für den zweiten Fall werden insgesamt 14 Bit benötigt, also 1,75 Bit pro Zeichen. Das entspricht genau der Entropie. Also ist auch dieser Code optimal.

Was man verstanden haben sollte¶

Aus einem Binärbaum entsteht immer ein präfixfreier Code, wenn die Codewörter an den Blättern hängen.
Die Entropie ist eine untere Grenze für den bestmöglichen Code.