Vorwort

Der vorliegende Text ist entstanden aus dem Vorlesungsmanuskript zu meiner Vorlesung Codierungstheorie im Sommersemester 2001 an der Universität Ulm. Die Vorlesung richtete sich an Studenten, die über Grundkenntnisse in elementarer Algebra verfügen. In der Vorlesung wurden die Standardthemen der Codierungstheorie bis hin zu den algebraisch-geometrischen Codes behandelt; das entspricht etwa dem Inhalt der Kapitel 0 bis 6. Besondere Aufmerksamkeit wurde auch den konkreten Anwendungen in der Nachrichtentechnik wie etwa der Codierung von Daten auf Speichermedien gewidmet. Die elementare Codierungstheorie endet im Kapitel 5 mit der sehr schwierigen Frage nach der expliziten Konstruktion von fehlerkorrigierenden linearen Codes, die bei vorgegebener Blocklänge n und Korrekturfähigkeit von e Fehlern eine hohe Informationsrate haben. Es geht also um das kombinatorische Problem:

Zu vorgegebenem n und e konstruiere man Untervektorräume C Î Fⁿ_q möglichst großer Dimension k, so dass sich zwei verschiedene Vektoren x,y Î C immer in mindestens d := 2e + 1 Koordinaten unterscheiden.

Dabei interessiert man sich insbesondere für Codes mit großer Blocklänge n. Dann wird diese Frage mit relativen Bezugsgrößen R := k/n und d := d/n gestellt. Dabei steht R für die Informationsrate und d für die Zuverlässigkeit des Codes. Diese beiden Größen konkurrieren miteinander. Elementare Überlegungen zeigen, dass R + d £ 1 + 1/n gelten muss. Weiterhin kann man auch sehr leicht die Existenz von kombinatorischen (eventuell nicht linearen) Codes zeigen, so dass R + d ³ 1 - H(d) für eine gewisse Funktion H(d) gilt; vgl. Bild 5.1 auf Seite 100. Jedoch ist es äußerst schwierig, Codes zu konstruieren, die diese untere Schranke erfüllen bzw. noch besser als diese sind und zusätzlich noch linear sind.

V.D. Goppa hat zu dieser Frage wichtige Beiträge geliefert; mit Hilfe von algebraischen Kurven konstruierte er Codes, die zur Lösung dieser Frage führten. Die Bearbeitung dieses Themas ist das eigentliche Ziel dieses Buches. In den Kapiteln 6 bis 9 werden die Theorie der algebraisch-geometrischen Codes und die dafür notwendigen Grundlagen über algebraische Kurven detailliert dargestellt. Dieser Teil des Buches fordert den Leser wesentlich mehr als der erste Teil, weil dazu fundierte Grundkenntnisse in Algebra vorausgesetzt sind.

Die Theorie der algebraischen Kurven wird zunächst in sehr kurzer Form in Abschnitt 6.1 referiert, um möglichst schnell zu den algebraisch-geometrischen Codes zu kommen. Zum Verständnis dieser Codes benötigt man im Wesentlichen nur den Satz von Riemann-Roch und den Residuensatz, wobei die Kenntnis der Beweise dieser Sätze nicht erforderlich ist. Das Hauptanliegen in Kapitel 6 ist es, die Frage nach optimalen Codes in ein Problem über rationale Punkte auf Kurven zu übersetzen und (optimale) Kurven mit vielen rationalen Punkten zu konstruieren. Diese Beispiele gehen auf die Arbeit von Garcia und Stichtenoth [G-S] zurück. Die hier gegebenen Beweise sind geometrischer Natur im Gegensatz zum Vorgehen in [G-S], wo mittels Funktionenkörper argumentiert wird.

Anschließend wird der Problemkreis der Anzahl von rationalen Punkten auf algebraischen Kurven über endlichen Körpern intensiv weiter verfolgt. In Kapitel 7 wird die Theorie der Zetafunktion einer algebraischen Kurve behandelt; die Rationalität der Zetafunktion sowie die Riemannsche Vermutung im Kurvenfall werden vollständig bewiesen. Damit wird die Hasse-Weil-Schranke für die Anzahl der rationalen Punkte auf einer algebraischen Kurve hergeleitet. Als Folgerungen gewinnt man die Schranken von Serre und Drinfeld-Vladut. Durch die Beispiele in Kapitel 6 wird somit die Drinfeld-Vladut-Schranke als scharfe Abschätzung im Fall eines Grundkörpers mit q² Elementen nachgewiesen.

In Kapitel 9 wird die Codierung und Decodierung von algebraisch-geometrischen Codes erklärt. Für die Codierung wird ein effektiver Algorithmus zur Berechnung einer Basis von L(D) beschrieben, der originär auf Hensel und Landsberg zurückgeht und von Coates in [Co] wieder aufgegriffen wurde. Das Decodierungsverfahren von Skorobogatov und Vladut, das eigentlich nur für kleine Fehlerraten arbeitet, sowie das Verfahren von Feng und Rao, das Fehlergrößen bis zum designierten Abstand korrigieren kann, werden algorithmisch behandelt.

Um explizit mit algebraischen Kurven und den daraus abgeleiteten Codes rechnen zu können, ist ein tieferes Verständnis der algebraischen Kurven natürlich unumgänglich. Daher ist in Kapitel 8 die Brill-Noether Theorie vollständig ausgeführt. Ich habe mich bewusst für diesen klassischen Zugang zu den algebraischen Kurven entschieden, weil diese Theorie am ehesten explizite Rechnungen erläutert und ohne den aufwändigen Apparat der Cohomologietheorie auskommt.

Im Anhang werden noch einige Themen der kommutativen Algebra und algebraischen Geometrie erläutert. Dabei wird jedoch vorausgesetzt, dass der Leser mit den Grundlagen der kommutativen Algebra insoweit vertraut ist, wie sie in einer zweisemestrigen Algebravorlesung üblicherweise abgehandelt werden.

Zum Schluss möchte ich vielfachen Dank abstatten: An meine Mitarbeiter Urs Hartl, Matthias Künzer, Andreas Martin und Volker Pahnke, die das Manuskript durchgelesen und durch ihre Anregungen und Kritik den Text optimiert haben. Zu danken habe ich meinen Fachkollegen Hans-Joachim Nastold und Roland Huber sowie Gabriele Nebe für kritische Durchsicht von einigen Passagen des Textes. Mein besonderer Dank gilt Winfried Scharlau, durch dessen Vorlesung ich zu diesem Themenkreis gestoßen bin. Schließlich möchte ich Martin Aigner als Herausgeber dieser Buchreihe beim Vieweg-Verlag für seine inhaltlichen Vorschläge danken.