Kodierungstheorie (KDT)

Wie bleiben Daten fehlerfrei? Du lernst, wie Informationen trotz Störungen sicher übertragen werden, entwickelst eigene Codes und verstehst, wie sie z. B. bei Kommunikation, Bildern oder Verschlüsselung eingesetzt werden.

Inhalte

• Die Kodierungstheorie untersucht Verfahren zur Konstruktion und Verwendung von fehlertoleranten Codes. Die Urväter der Kodierungstheorie sind vor allem Hamming, Golay und Shannon, die in den 1940er und 1950er Jahren fundamentale Arbeiten hierzu verfasst haben. Inzwischen ist die Kodierungstheorie zu einem stark verzweigten und wichtigem Gebiet geworden, dessen Anwendungen sich vor allem in der Nachrichten- und Speichertechnologie finden, aber auch in der Bildverabeitung, der Mustererkennung und natürlich der Kryptographie. Sogar in der Biologie findet die Kodierungstheorie ihren Platz. Offensichtlich spielen algorithmische Probleme eine große Rolle in der Kodierungstheorie. Effiziente Algorithmen zur Kodierung oder Dekodierung von leistungsstarken Codes sind ebenso wichtig wie die Codes selbst. Aus diesem Grunde hat die Kodierungstheorie zur Entwicklung zahlreicher sehr interessanter Algorithmen geführt. Zudem führen kodierungstheoretische Resultate zu überraschenden Anwendungen in der Komplexitätstheorie und in anderen Bereichen der Informatik.
• In dieser Veranstaltung sollen die Grundzüge der Kodierungstheorie, also die elementare Kodierungstheorie besprochen werden. Wir wollen eine Einführung in die Grundfragen und Grundlagen der Theorie der linearen Codes geben. Dazu werden wir die gängigen Klassen von Codes samt zugehöriger Decodieralgorithmen vorstellen. Zu diesen gehören u. a. Reed-Solomon-Codes, Hamming-Codes, Golay-Codes, BCH-Codes, quadratische Reste-Codes, Reed-Muller-Codes sowie die klassischen Goppa-Codes. Daneben sollen einige der asymptotischen Schranken für die Informationsrate von Codes bewiesen werden.

Lernziele/Kompetenzen

Die Studierenden sind in der Lage,

• mathematische Grundlagen der Kodierungstheorie zu verstehen und anzuwenden,
• (lineare) Codes zu analysieren,
• Codes bezüglich Fehlertoleranz und Fehlerkorrektur zu entwickeln und
• Anwendungen der Kodierungstheorie in der Informatik zu verstehen.

Literatur

• W.C. Huffman and V. Pless. Fundamentals of Error-Correcting Codes, Cambridge, 2003.
• J.H. van Lint. Introduction to Coding Theory. Springer Verlag, 1999.
• Werner Lütkebohmert. Codierungstheorie. Vieweg Studium Verlag, 1. edition, 2003.
• MacWilliams, F.J. and Sloane, N.J.A. The Theory of Error-Correcting Codes. North- Holland, Amsterdam, 1977.
• D. Jungnickel, Codierungstheorie. Spektrum Akademischer Verlag, 1995.
• R.-H. Schulz, Codierungstheorie. Vieweg, 2003.

Dozentinnen / Dozenten

• Prof. Dr. Lutz Strüngmann

Empfohlene Vorkenntnisse 

• Mathematik für die Informatik 2 (MA2)

Daten zum Modul

Semester	6/7
Unterrichtssprache	Deutsch
Häufigkeit	Unregelmäßig Im Durchschnitt alle 2 Semester
Kreditpunkte (CP)	5
Modulverantwortlich	Prof. Dr. Lutz Strüngmann
Dauer	1 Semester
Studienleistung	Keine
Prüfungsvorleistung	Keine
Prüfungsleistung	Continuous Assessment (CA)

Semesterwochenstunden (SWS) 

Vorlesung	2 SWS
Übung	2 SWS
Summe	4 SWS

Arbeitsaufwand (Workload) 

Vorlesung	45 h
Selbststudium	60 h
Aufgaben	15 h
Prüfungsvorbereitung	30 h
Summe	150 h