Informationstheorie

Kursbeschreibung

Die Vorlesung vermittelt die Grundlagen von Shannons Informations- und Codierungstheorie. Die wichtigsten Themen sind: Entropie, Information, Datenkompression, Kanalcodierung, Codes. Ziel der Vorlesung ist es, sowohl mit den theoretischen Grundlagen der Informationstheorie vertraut zu machen, als auch den praktischen Einsatz der Theorie anhand ausgewählter Beispiele aus der Datencodierung und Datenkompression zu illustrieren.

Zeiten und Räume

Vorlesung

Do 13-15 in CAB G 52

Übung

Mi 15-17 (zweiwöchentlich) in HG D 3.3.

Übungstermine: 27.2., 20.3., 27.3., 17.4., 8.5., 22.5.

Inhalte der einzelnen Vorlesungen

Datum	Inhalt der Vorlesung	Literatur
21.02.	Einführung, Beispiele für Codes (Wiederholcodes, (7,4)-Hamming-Code)	[M, Kapitel 1]
28.02.	Definition von Entropie, gemeinsamer Entropie, bedingter Entropie, wechselseitiger Information, KL-Divergenz. Eigenschaften und Zusammenhang dieser Grössen.	[CT, Kapitel 2], [M, Kapitel 2, 8]
07.03.	Codes (Quellcodes) und deren Eigenschaften, Codebäume, Kraft-Ungleichung, Optimalität von Codes, Schranken an die erwartete Länge	[CT, Kapitel 5], [M, Kapitel 5]
14.03.	Codes bzgl. falscher Verteilung. Huffman-Coding, Optimalität von Huffman-Codes. Kraft-Ungleichung für eindeutig decodierbare Codes	[CT, Kapitel 5], [M, Kapitel 5]
21.03.	Typische Mengen und Asymptotische Gleichverteilung. Shannon's Quellcodierungstheorem.	[CT, Kapitel 3], [M, Kapitel 4, 6]
28.03.	Arithmetische Codes, Lempel-Ziv-Codes	[M, Kapitel 6], [CT, Kapitel 13]
04.04.	Lempel-Ziv-Codes (Fortsetzung). Kanäle und ihre Kapazitäten. Motivation Kanalcodierung	[M, Kapitel 6, 9], [CT, Kapitel 13, 7]
11.04.	Codes und Raten von Codes. Gemeinsam typische Sequenzen und Gemeinsame Asymptotische Gleichverteilung	[M, Kapitel 9], [CT, Kapitel 7]
18.04.	Shannons Kanalcodierungstheorem, Beweis des Erreichbarkeitsteils, Fano-Ungleichung	[M, Kapitel 10], [CT, Kapitel 7]
02.05.	Beweis des zweiten Teils des Kanalcodierungstheorems (Kapazität als obere Schranke); Fehlerbehaftete Kommunikation oberhalb der Kapazität. Lineare Codes	[M, Kapitel 10], [CT, Kapitel 7], [Mau, Kapitel 5]
09.05.	Lineare Codes, Hamming-Codes, Lineare Codes via Polynomevaluation	[Mau, Kapitel 5]
16.05.	Reed-Solomon-Codes	[Mau, Kapitel 5]
23.05.	Polar-Codes	arXiv:0807.3917

Übungsblätter

Materialien

Merkblatt Diskrete Wahrscheinlichkeitstheorie

Skript (vorläufige Version, nicht gründlich Korrektur gelesen!)

Verwenden Sie Ihre nethz-Zugangsdaten für den Zugriff.

Leistungsbewertung

Es wird eine schriftliche Prüfung von 120 Minuten Dauer geben.

Siehe Eintrag im VVZ für weitere Informationen.

Prüfungen vergangener Jahre