Seminar/Proseminar zur Diskreten Mathematik (Lineare Codes)
Wintersemester 2023/24
Neuigkeiten
- Die schriftlichen Ausarbeitungen müssen bis zum 28.11.2023 via Assignments abgegeben werden.
- Die Vorträge finden am 12.12.2023 statt.
- Die Einführungsfolien und das Infoblatt sind unter Resources zu finden.
- Die Themenvergabe findet am 31.10.2023 ab 10 Uhr (c. t.) in A7/SR 140 statt. Das ist auch der erste Termin der Veranstaltung.
Inhalt
Im (Pro-)Seminar zur Diskreten Mathematik I im Wintersemester 2023/24 geht es um lineare Codes. Solche Codes kommen dann zum Einsatz, wenn Informationen über fehleranfällige Kanäle übertragen werden sollen, wie zum Beispiel beim Abtippen von Kartennummern, oder bei der Datenübertragung über drahtlose Netze. Lineare Codes bedienen sich Methoden der linearen Algebra und der diskreten Mathematik, um Übertragungsfehler zu erkennen oder sogar zu korrigieren.
Themenliste
| Nr. | Datum | Sprecher:in | Thema | Literatur |
|---|---|---|---|---|
| 1 | 31.10.2023 | Niels Lindner | Einführung | |
| 2 | Grundlagen linearer Codes (Vektorräume über Restklassenkörpern, Definition von linearen Codes, Rate, Hamming-Abstand, Hamming-Gewicht, Generatormatrix, äquivalente Codes) | §2.1-2.2, §2.5.1-2.5.2 | ||
| 3 | Decodierung (Duale Codes, Kontrollmatrix, Maximum-Likelihood-Decodierung, Syndrom-Decodierung, Nebenklassenführer) | §2.3-2.4, §2.5.3-2.5.4 | ||
| 4 | Hamming-, Simplex- und Golay-Codes (Definitionen, elementare Eigenschaften, Kugelpackungsschranke, perfekte Codes) | §3 | ||
| 5 | Reed-Muller-Codes (Plotkin-Konstruktion, rekursive Definition, Eigenschaften, Majority-Logic-Decodierung) | §4 | ||
| 6 | Reed-Solomon-Codes (allgemeine endliche Körper als Quotientenringe des Polynomrings, Singleton-Schranke, MDS-Codes, Definition von Reed-Solomon-Codes, erste Eigenschaften) | §5 | ||
| 7 | Zyklische Codes (Theorie, Schieberegister, Meggitt-Decodierung, Cyclic Redundancy Check) | §6 | ||
| 8 | BCH-Codes (Primitive Einheitswurzeln, kleiner Satz von Fermat, Vandermonde-Matrizen, BCH-Codes, QR-Codes, PGZ-Decodierung, Berlekamp-Massey-Algorithmus) | §7 |
Literatur
- O. Manz (2017). Fehlerkorrigierende Codes - Konstruieren, Anwenden, Decodieren. Springer Vieweg Wiesbaden. https://doi.org/10.1007/978-3-658-14652-8
- R.-H. Schulz (2003). Codierungstheorie - Eine Einführung (2. Aufl.). Vieweg+Teubner Verlag Wiesbaden. https://doi.org/10.1007/978-3-322-80328-3
- W. Willems (2008). Codierungstheorie und Kryptographie. Birkhäuser Basel. https://doi.org/10.1007/978-3-7643-8612-2
- R. Roth (2006). Introduction to Coding Theory. Cambridge: Cambridge University Press. https://doi.org/10.1017/CBO9780511808968
- J. van Lint (1971). Coding Theory. Springer Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-20712-3
Zusätzliche Informationen
Whiteboard: Die Kommunikation erfolgt über das Whiteboard-System der FU. Die Liste der Themen wird zu Beginn des Semesters über die Whiteboard-Homepage des Kurses bekanntgegeben.
Voraussetzungen: Solide Kenntnisse in linearer Algebra und Grundkenntnisse in diskreter Mathematik werden empfohlen.
Zur erfolgreichen Teilnahme gehört die Anfertigung einer Ausarbeitung der wesentichen Inhalte Ihres Vortrages in professioneller Qualität (LaTeX, 5-8 Seiten). Die Ausarbeitung soll eine Literaturrecherche einschließen. Sie wird Ihnen eine Woche vor dem Präsentationstermin benotet und korrigiert zurückgegeben, damit Sie bereits vor dem Vortrag ein Feedback haben.
Die Vorträge sollen eine Dauer von ca. 45 Minuten haben. Die regelmäßige und aktive Teilnahme an den Terminen des Seminars (nicht nur an dem Tag, an dem man Sie selbst vortragen) und die rechtzeitige Abgabe der Ausarbeitung sind notwendige Bedingungen für ein Bestehen des Seminars.
Die Endnote setzt sich zu 2/3 aus dem Vortrag und zu 1/3 aus der Ausarbeitung zusammen.
Kontakt
| Name | Raum | |
| Prof. Dr. Niels Lindner | lindner@zib.de | ZIB 3007 |