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.Die wichtigsten Inhalte sind:
- Entropie und Information
- Asymptotische Äquipartition und typische Sequenzen
- Quellcodierung
- Kanalkapazität und Kanalcodierung
- Shannons Kanalcodierungstheorem
- Hamming Codes
- Differentielle Entropie
- Gauss-Kanal
- Ratenverzerrungstheorie
Ankündigungen
- Am 12.05 findet keine Übungstunde statt. Nächste Übung wieder am 26.05
Vorlesungen
| Datum | Inhalt der Vorlesung | Material | Literatur |
|---|---|---|---|
| 25.02. | Einführung und Motivation | Aufnahme, Vorlesungsnotizen | [CT, Kap. 1, 2] |
| 04.03. | Definition von gemeinsamer Entropie, bedingter Entropie, wechselseitiger Information, KL-Divergenz. Eigenschaften und Zusammenhang dieser Grössen. Jensens Ungleichung. | Aufnahme, Vorlesungsnotizen | [CT, Kap. 2.1 -2.6] |
| 11.03. | Datenberarbeiungungleichung, Fano's Ungleichung, Typische Ereignisse | Aufnahme, Vorlesungsnotizen | [CT, Kap. 2, 3] |
| 18.03. | Verlustbehaftete Datenkompression, Kraft-Ungleichung, (Symbol) Codes | Aufnahme, Vorlesungsnotizen | [CT, Kap. 3, 5] |
| 25.03. | Kraft-Ungleichung, Optimale Codes, Huffman Codes | Aufnahme, Vorlesungsnotizen | [CT, Kap. 5.1 - 5.8] |
| 01.04. | Optimalität Huffman Codes, Arithmetische Codes | Aufnahme, Vorlesungsslides, Vorlesungsnotizen | [CT, Kap. 13.3] |
| 15.04. | Lemple-Ziv, Kanalcodierung | Aufnahme, Vorlesungsslides, Vorlesungsnotizen | [CT, Kap. 13.4, 7] |
| 22.04. | Kanalkapazität | Aufnahme, Vorlesungsnotizen | [CT, Kap. 7.1-7.6] |
| 29.04. | Kanalkodierungstheorem | Aufnahme, Vorlesungsnotizen | [CT, Kap. 7.7] |
| 06.05. | Beweis der Erreichbarkeit Kanalkodierungstheorem und Umkehrung, Einführung Hamming Codes | Aufnahme, Vorlesungsnotizen | [CT, Kap. 7.6-7.11] |
| 20.05. | Hamming Codes, Quellen-Kanal-Codierungssatz, Differentielle Entropie | Aufnahme, Vorlesungsnotizen | [CT, Kap. 7.11-7.13, CT, Kap. 8.1 - 8.3] |
| 27.05. | Gauss-Kanal | Aufnahme, Vorlesungsnotizen | [CT, Kap. 9] |
| 03.06. | Ratenverzerrungstheorie | Aufnahme, Vorlesungsnotizen | [CT, Kap. 10-10.3] |
Tutorials
| Datum | Inhalt der Übung | Material | Literatur |
|---|---|---|---|
| 03.03. | Information und Entropie | Aufnahme, Slides | |
| 17.03. | Verlustbehaftete Komprimierung und Symbole Codes | Aufnahme_1, Aufnahme_2, Slides | |
| 31.03. | Quellcodierung für Symbol Codes, Kraft Ungleichung, Huffman Coding | Aufnahme, Slides | |
| 14.04. | Arithmetische Codierung, Lempel-Ziv | Aufnahme, Slides | |
| 28.04. | Kanalkapazität | Aufnahme, Slides | |
| 26.05. | Lineare Codes, Hamming Codes, Kanalcodierungstheorem für lineare Codes | Aufnahme, Slides |
Übungsblätter
Materialien
- Skript (Das Skript ist eine gute Referenz und deckt einen Grossteil des Stoffes ab. Es dient aber nicht als Ersatz zur Vorlesung!)
Verwenden Sie Ihre nethz-Zugangsdaten für den Zugriff.
Zeiten und Räume
Vorlesung
Do 14-16 in ML F 36. Bis auf weiters auf Zoom
Übung
Mi 16-18 (zweiwöchentlich) in HG D 7.1 Bis auf weiteres auf Zoom
Übungstermine: 3.3.2021, 17.3.2021, 31.3.2021, 14.04, 28.04, 26.05
Leistungsbewertung
Es wird eine schriftliche Prüfung von 120 Minuten Dauer geben.
Prüfungen vergangener Jahre
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
- [P] V. Pless. Introduction to the Theory of Error-Correcting Codes , 3rd edition. John Wiley, 1998.
Kontakt
Dozent: Prof. J. M. BuhmannAssistent: Fabian Laumer