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

 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.