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
- Übungsblatt 1, Lösungen zu Übungsblatt 1
- Übungsblatt 2, Lösungen zu Übungsblatt 2
- Übungsblatt 3, Lösungen zu Übungsblatt 3
- Übungsblatt 4, Lösungen zu Übungsblatt 4
- Übungsblatt 5, Lösungen zu Übungsblatt 5
- Übungsblatt 6, Lösungen zu Übungsblatt 6
- Übungsblatt 7, Lösungen zu Übungsblatt 7, lz_decode.py
- Übungsblatt 8, Lösungen zu Übungsblatt 8
- Übungsblatt 9, Lösungen zu Übungsblatt 9
- Übungsblatt 10, Lösungen zu Übungsblatt 10
- Übungsblatt 11, Lösungen zu Übungsblatt 11
- Übungsblatt 12, Lösungen zu Übungsblatt 12
Materialien
- 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
Verwenden Sie Ihre nethz-Zugangsdaten für den Zugriff.
Literatur
- [CT] T. Cover, J. Thomas. Elements of Information Theory. 2nd Edition. John Wiley, 2006.
- [M] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
- [S] C. E. Shannon. A Mathematical Theory of Communication. 1948.
- [Mau] U. Maurer. Information und Kommunikation Vorlesungsskript, 2003
Kontakt
Dozent: Luis HaugAssistentin: Frances Hubis