Informationen zur Vorlesung "Kodierungstheorie" im Sommersemester 2009 am Institut für Informatik der LMU.
| Dozenten: | Martin Hofmann, Klaus Aehlig |
| Vorlesung: | Mi 13-16, Raum 033 (Oettingenstr. 67) |
| Übung: | Do 8-10, Raum 23 (Oettingenstr. 67) |
Zur Vorlesung gibt es kein Skript, massgeblich ist die Tafelanschrift. Zur Erleichterung stellen wir jedoch bis auf weiteres ein ASCII Konzept zur Verfuegung. Es gibt keine Garantie auf Vollständigkeit.
| Datum | Inhalt | Material |
|---|---|---|
| 22.04.09 | Motivation, Einführende Beispiele: ISBN, Wdh.code, (7,16,3)-Hammingcode. Information, Entropie, Quellencodierung nach Shannon-Fano und Huffman, Kraftsche Ungleichung. | Skript, Übungsblatt |
| 29.04.09 | Hauptsatz der Quellencodierung, Transinformation, Satz von der perfekten Verschluesselung, Fano-Ungleichung, Hamming-Distanz, Kanalkapazitaet, Hauptsatz der Kanalcodierung (ohne Beweis!) | Skript, Übungsblatt |
| 6.5.2009 | Hamming Codes, lineare Codes und notwendige lineare Algebra | Skript, Übungsblatt |
| 13.5.2009 | Satz von Varsamov, Syndrom-Decodierung, Simplex-Code, Plotkin-Schranke | Skript, Übungsblatt |
| 20.5.2009 | Beweis des Shannonschen Kanalcodierungssatzes mit gemeinsam typischen Mengen. | Skript,Übungsblatt |
| 27.5.2009 | Reed-Muller Code. Mehrheitsdecodierung. | Skript,Übungsblatt |
| 3.6.2009 | Reed-Solomon Codes | Skript, Übungsblatt |
| 10.6.2009 | Cyclic Redundancy Checks; Zusammengesetzte Codes (Konkatenation, Block, CIRC, etc) | Skript, Übungsblatt |
| 17.6.2009 | Zyklische Codes, BCH-Schranke | Skript, Übungsblatt |
| 01.07.2009 | Faltungscodes, Generatormatrizen, Potenzreihen. | Skript, Übungsblatt |
| 08.07.2009 | Freie Distanz, Decodierung von Faltungscodes, Viterbi Algorithmus, Fano Algorithmus, Punktierung, Tailbiting, Ausblick auf Turbocodes. | Skript, Übungsblatt |
| 15.07.2009 | Beispiele, wo Codes noch auftauchen (Derandomisierung, probabilistic communication complexity, secret sharing) | Skript |
Die Codierungstheorie befasst sich mit der Übertragung von Information über fehlerbehaftete Kanäle. Anders als bei der Kryptographie geht es nicht darum, die Informationen vor unerwünschten Zuhörern zu schuetzen, sondern darum, Fehler bei der Übertragung zu erkennen oder zu korrigieren.
Eine einfache Aufgabe der Codierungstheorie ist die folgende: man codiere eine Bitfolge (zum Beispiel 4 Bit) so, dass ein Bitfehler korrigiert werden kann.
Sendet man die vier Bit einfach doppelt, so hat man acht Bit verbraucht und kann einen Fehler erkennen, nicht aber korrigieren. Kommt etwa 00100011 an, so weiß man, dass ein Fehler aufgetreten ist; die urspruenglich gesendete Information koennte aber 0010 (Fehler im achten Bit) oder 0011 (Fehler im vierten Bit) gewesen sein. Sendet man die vier Bit dreimal hintereinander, so kann man per Mehrheitsentscheidung einen Bitfehler korrigieren, hat aber zwölf Bit aufgewendet.
Wir lernen in der Vorlesung ein Verfahren, den Hamming-Code, kennen, welches die vier Bit auf nur sieben Bit aufblaeht und doch die Korrektur eines Fehlers erlaubt.
Bei einer Mars-Expedition in den 70er Jahren wurde ein Codierungsverfahren verwendet, der (5,1)-Reed-Muller Code, welches 6 Informationsbits mit 32 Bit codiert und dadurch 7 Bitfehler korrigieren kann.
Bei Audio-CDs und im Mobilfunk wiederum kommt der Reed-Solomon Code zum Einsatz, welcher Burstfehler (mehrere aufeinanderfolgende Bitfehler, "Kratzer") besonders gut korrigieren kann.
Die Vorlesung behandelt all diese Verfahren und die dazugehoerigen Grundlagen. Wenn es die Zeit erlaubt, bieten wir einen Ausblick auf die Verwendung von Codierungsverfahren in der Komplexitaetstheorie.