Codierung und Information
Aktuelles
- Die Ausarbeitungen bitte bis zum 13. Juni (23:59 Uhr) über UniWorX abgeben
- Die 90-Sekunden-Vorträge finden am 9. Mai um 18 Uhr im Raum 169, Oettingenstr. 67 statt.
- Vorbesprechung mit Themenvergabe: Mi 25.04.2012, 16:00 c.t., L109, Oettingenstr. 67.
- Zur Abwicklung von organisatorischen Fragen wird um eine Anmeldung bei UniWorX gebeten.
Inhalt
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 schützen, 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. 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.
In diesem Seminar werden verschiedene Codierungsverfahren und ihre theoretischen Grundlagen und Eigenschaften behandelt.
Das Seminar richtet sich an alle Studenten der Informatik und Medieninformatik, d.h. Studenten der jeweiligen Bachelor-, Master- oder Diplomstudiengänge. Da die Anforderungen für Seminare in den jeweiligen Studienordnungen variieren, wird auch die erforderliche Prüfungsleistung je nach Studiengang angepasst.
Organisation
- Umfang: Blockseminar am Ende des Semesters
- Veranstalter: Andreas Abel, Stephan Barth, Martin Hofmann, Steffen Jost, Ulrich Schöpp
Anforderungen
- Blitzvortrag 90 Sekunden: Inhaltsübersicht, 1 Folie
- Vortrag: 20 Minuten + 5 Minuten Diskussion
- Anwesenheit während der Seminarsitzungen
- 7000-14000 Zeichen
- Bei Master- und Diplomstudenten werden die Anforderungen mit den Betreuern abgesprochen.
Zeit und Ort
- 90-Sekunden-Vorträge: 9. Mai., 18 Uhr, Raum 169, Oettingenstr. 67
- Abgabe der Ausarbeitungen bis spätestens 13.06.
- Reviews der Ausarbeitung bis 20.06.
- Seminarvorträge: 27. Juni, 28. Juni
Mittwoch 27.06.2012, 10 s.t. - 16 Uhr Raum C 007 10.00 Beginn: Einleitung 10.15-10.35 1 Schermuly 10.40-11.00 2 Martinetti 11.05-11.25 3 Peschel 11.30- Mittags-Pause 45 min Raum 067 12.15 4 Bisinger 12.40 5 Reihl 13.05 6 Seiler 13.30 7 Klutsch 13.55 Pause 20 min Raumwechsel Raum 161 14.15 8 Zhang 14.40 9 Walonka 15.05 10 Cortrie 15.30 11 Dietsche Donnerstag 28.06.2012, 10 s.t. - 14 Uhr Raum C 007 10.00 Beginn 10.05 13 Yagoubov 10.30 14 Schoening 10.55 15 Jaeckel 11.20 16 Klinger 11.45 Pause 45 min 12.30 17 Hoerl 12.55 18 Vogel 13.20
Themen
- 1. Einführende Beispiele (Betreuer: SB)
- 2. Quellen, Entropie, Begriff der Quellencodierung, Fanobedingung (Betreuer: AA)
- 3. Quellencodierung nach Shannon-Fano und Huffman (Betreuer: AA)
- 4. Kraftsche Ungleichung, Shannons Hauptsatz der Quellencodierung (Betreuer: AA)
- 5. Transinformation (Mass für die stat. Abhängigkeit zweier Quellen) (Betreuer: AA)
- 6. Anwendungen der Transinformation:(Betreuer: MH)
- Shannons Satz von der perfekten Verschlüsselung, Ungleichung von Fano.
- 7. Blockcodes, Minimaldistanz, Kugelpackungsschranke (Betreuer: US)
- 8. Kanalbegriff. Kanalkapazität. Shannons (Betreuer: US)
- Kanalcodierungssatz: Hintergrund und obere Schranke
- 9. Hamming Codes (Betreuer: SJ)
- 10. Lineare Codes (Betreuer: SJ)
- 11. Reed Muller Code, Definition und Anwendungen (Raumfahrt) (Betreuer: SJ)
- 12. Reed Muller Code, Mehrheitsdecodierung (Betreuer: SJ)
- 13. Reed-Solomon Code. Definition + Grundlagen (Betreuer: MH)
- 14. Codierung bei CDs mit Reed-Solomon Code (Betreuer: SB)
- 15. Faltungscodes (Betreuer: US)
- 16. Rekursive Faltungscodes (Betreuer: US)
- 17. Freie Distanz und rekursive Decodierung von Faltungscodes (Betreuer: MH)
- 18. Viterbi Algorithmus & Anwendung auf Hidden Markov (Betreuer: MH)
Themenzuweisung
Vorname | Nachname | Betreuer | |
Sabine | Schermuly | SB | 01: Einfuehrung |
Zara | Martinetti | AA | 02: Entropie |
Michael | Peschel | AA | 03: Quellencodierung |
Benjamin | Bisinger | AA | 04: Kraftsche Ungleichung |
Felix | Reihl | AA | 05: Transinfo |
Nepomuk | Seiler | MH | 06: Anwendung Transinfo |
Thomas | Klutsch | US | 07: Blockcodes |
Shaonan | Zhang | US | 08: Kanalbegriff |
Christian | Walonka | SJ | 09: Hamming |
Isabella | Cortrie | SJ | 10: Lineare Codes |
Nina | Dietsche | SJ | 11: Reed Muller |
Anne-Kathrin | Seher | SJ | 12: Reed Muller |
Andrei | Yagoubov | MH | 13: Reed Solomon |
Guido | Schöning | SB | 14: CD codieren |
Lars | Jäckel | US | 15: Faltungscodes (Physik 6. Sem) |
Max | Klinger | US | 16: Rekursive Faltung |
David | Hörl | MH | 17: Freie Distanz |
Andreas | Vogel | MH | 18: Viterbi |
Betreuer: AA=Andreas Abel, SB=Stephan Barth, MJ=Martin Hofmann, SJ=Steffen Jost, US=Ulrich Schöpp
Literatur
Die Bücher von Willems, Heise-Quattrocchi sowie das Handbuch zur Codierungstheorie können im Sekretariat bei Frau Roden stundenweise ausgeliehen werden.
- Skript vom Sommersemester 2009, Vorlesunsgsseite von 2009
- Wolfgang Willems: Codierungstheorie, Gruyter, Berlin 1999
- W. Heise, P. Quattrocchi: "Informations- und Codierungstheorie", Springer 1995
- Pless, Huffman (Hrsg.): Handbook of Coding Theory, (2 Volumes), Elsevier, Amsterdam 1998
- Originalarbeit von Shannon (1948)
- Skript von Ueli Maurer ETHZ (Inf&Komm WS 03/04)
- Wikipedia Artikel zu Shannon-Fano
- Tutorial zu Faltungscodes auf www.complextoreal.com
- Skript von Herrn Braun.
Artikelaktionen