Vorlesung im Sommersemester 2008 an der Technischen Universität Berlin.
Auf dieser Seite werden im Lauf der VL relevante Informationen
zur Verfügung gestellt.
Die Codierungstheorie beschäftigt sich mit dem Problem, wie digitale Daten
über einen Kanal fehlerfrei übertragen werden können, auch wenn
der Kanal in begrenztem Maß Fehler in den Datenstrom einbringt (zum
Beispiel Kratzer auf einer CD, Störungen im Funkverkehr zwischen
Mobiltelefonen oder Satelliten).
Der erste Teil der VL behandelt elementare Codierungstheorie und einige
Anwendungen in der Praxis. Der zweite (und umfangreichere)
Teil der VL geht auf die mathematischen
Konstruktionen der arithmetischen Codierungstheorie aus
algebraischer Zahlentheorie und algebraischer Geometrie ein.
Voraussetzungen: Algebra I und Algebra II, teilweise
Wahrscheinlichkeitstheorie, Zahlentheorie und ggf. algebraische Kurven.
Sprechzeiten: F. Heß nach der Vorlesung und nach Vereinbarung, M. Wagner: Di 14-16, MA812
F. Heß
MA804
314-25062
M. Wagner
MA812
314-23761
Unsere email-Adressen beginnen mit unseren Nachnamen gefolgt von dem Suffix @math.tu-berlin.de. Bei Heß muss das ß durch ein ss ersetzt werden. Für die Vorlesung besteht die email-Adresse aus codth und dem Suffix @math.tu-berlin.de.
Gruppenarbeit in Zweier-Gruppen.
Scheinkriterium: 50% der erreichbaren Punkte in jeder Semesterhälfte.
Die Abgabe der praktischen Aufgaben hat am selben Tag zu erfolgen
wie die Übungsaufgaben. Ist ein Kash-Programm gefragt,
so wird ein lauffähiges Kash-Programm verlangt, das als Attachment per Mail an
M. Wagner geschickt wird.
ERASMUS Studenten beachten bitte, daß die oben genannten Scheinkriterien
dem Bestehen der Vorlesung mit Note "ausreichend" gleichkommen. Weniger Punkte
bzw. kein Schein bedeuten, daß die Vorlesung nicht bestanden wurde.
Bitte auch zum Anfang der VL bei F. Heß melden!
Für Informatiker, welche die VL als Wahlfach hören wollen, setzt sich
die prüfungsrelevante Studienleistung aus den erreichten Punkten der
wöchentlichen Übungsaufgaben und einer mündlichen
Prüfung am Ende der VL zusammen.
Fortsetzung: Im Anschluß an diese VL werden im Wintersemester
2008 planmäßig folgende Veranstaltungen
angeboten: Kryptographie, Zahlentheorie II, Seminar.
16.4. Beginn der VL. Organisatorisches. Fragestellungen der
Codierungstheorie, Beispiele, grundlegene Definitionen,
Hamming-Dekodierung.
17.4. Informationstheorie, Maximum-Likelyhood-Dekodierung,
Satz von Shannon.
23.4. Entropie und Kanalkapazität.
24.4. Lineare Codes, Erzeugermatrix, Kontrollmatrix, Minimalabstand
und Kontrollmatrix, Syndromdekodierung.
30.4. Duale Codes, Singleton Schranke, MDS-Codes (mit Erklärung der
Abkürzung), MDS-Vermutung. Duale Codes von MDS-Codes. Gewichtspolynom und
MacWilliams Identität. Gewichtspolynom eines MDS-Codes.
7.4. Konstruktionen von Codes aus Codes (Parity-Check, Punktierung,
direkte Summe, Plotkin, Verklebung, Tensorprodukt). Bemerkungen zum
Dekodierungsproblem und Anwendungen in der Kryptographie. Reed-Solomon Codes.
8.4. Reed-Solomon Codes. Abgeschlossenheit unter
Dualisierung. Dekodierung von Reed-Solomon Codes mittels linearer Algebra:
Syndromdekodierung bei bekannten Fehlerpositionen. Lineares
Gleichungssystem für die Koeffizienten des Fehlerlokalisierungspolynoms
bei Reed-Solomon Codes.
14.4. Zyklische Codes (Übung, pdf).
Dekodierung von Reed-Solomon Codes mittels Polynomarithmetik:
Quotient von Fehlerpolynom und Fehlerlokalisierungspolynom als Potenzreihe mit
Syndromkoeffizienten, Padéapproximation, LLL für
Funktionenkörper. Laufzeitvergleich.
(pdf)
15.4. Beweis der Padéapproximation mittels LLL für
Funktionenkörper. Fehlerbursts und Korrigierung. Burstkorrektur bei zyklischen
Codes.
21.5. BCH Codes (Übung). Spreizung, Verkettung, Cross Interleaving. Dekodierung bei Cross
Interleaving: Dekodierung von Fehlern und Auslöschungen. Verkürzung
eines MDS-Codes.
22.5. Anwendungsbeispiel: CIRC Code auf Audio-CDs.
28.5. Anwendungsbeispiel: CIRC Code auf Audio-CDs. Reed-Muller Codes
über GF(p): Konstruktion. (pdf, update
vom 4.6.)
29.5. Reed-Muller Codes über GF(p): Parameter.
4.6. Reed-Muller Codes über GF(p): Dualer Code und Dekodierung. Bemerkungen.
5.6. Gruppencodes. Spezialfälle zyklische Codes (Beispiel
Reed-Solomon Codes mit primitiven Einheitswurzeln, Erzeugerpolynom)
und Reed-Muller
Codes. Vergleich mit Auswertungscodes. Konstruktionen von Codes für
beschränkte und unbeschränkte Parameter. Beispiel Klassifikation
perfekter Codes. Maximale Codes und asymptotische
Informationsrate. Asymptotische Singleton-Schranke.
11.6. Weitere Schranken für Codes. Algebraische
Funktionenkörper. Rationaler Funktionenkörper. Motivation.
12.6. Algebraische
Funktionenkörper (pdf, Vorsicht, nur grobe
Notizen, Update vom 19.6.). Stellen, Divisoren,
Hauptdivisoren, Divisorenklassengruppe,
Riemann-Roch Räume, das Konzept von algebraisch-geometrischen Codes.
Verbindung von Stellen zu Primidealen in Holomorphieringen.
18.6. Endliche Erweiterungen von Dedekindringen.
Trägheitsgrad, Verzweigungsindex, Gradformel.
19.6. Endlichkeit ganzer Abschlüsse in Körpererweiterungen
unter geeigneten Voraussetzungen.
25.6. Anwendungen auf den Funktionenkörperfall. Darstellung aller
Stellen als Primideale von (zwei) Holomorphieringen. Grad von
Nullstellen-, Polstellen- und Hauptdivisoren.
26.6. Satz von Riemann-Roch und Rechenregeln für die Dimension
von Divisoren.
2.7. Algebraisch-geometrische Codes. Definition und Aussagen über n,
k, d. Codes für globale Funktionenkörper vom Geschlecht Null sind
MDS-Codes. Globale Funktionenkörper vom Geschlecht Null sind
rational, haben aber nur q+1 viele Stellen.
3.7. Interpretation der Reed-Solomon Codes als
algebraisch-geometrische Codes. Algebraisch-geometrische Codes sind
abgeschlossen unter Dualisierung.
9.7. Dekodierung algebraisch-geometrischer Codes
nach Skorobogatov-Vladut.
(pdf, Update vom 10.7.)
10.7. Dekodierung algebraisch-geometrischer Codes. Bemerkungen zum
Verfahren von Feng-Rao.
16.7. Elliptische und hyperelliptische Funktionenkörper. Bemerkungen
zur MDS Vermutung für elliptische und hyperelliptische Codes. Satz von
Hasse-Weil über die Anzahl der Stellen vom Grad eins, obere Schranke von
Tsfasman-Vladut und untere Schranke von Tsfasman-Vladut-Zink (bei quadratischem
q) für die
asymptotisch maximale Anzahl der Stellen vom Grad eins.
17.7. Folgerung für die asymptotisch maximale Informationsrate bei
gegebener relativer Minimaldistanz und Vergleich mit der Gilbert-Varshomov
Schranke. Norm-Spur Turm von Garcia-Stichtenoth. Bemerkungen zur
Realisierbarkeit von Codes als Goppa Codes und Anwendung des Dekodierproblems
in der Kryptographie.
