Codierungstheorie
Konstruktion und Anwendung Linearer Codes
A. Betten, H. Fripertinger, A. Kerber, A. Wassermann, K.-H. Zimmermann
Springer Verlag Berlin, 1998, 360 Seiten, 49,99 €
ISBN 3-540-64502-0
Bei vorliegendem Buch handelt es sich um eine elementare Einführung in die Theorie der linearen Codes. Da in ihm die algebraischen Grundlagen ausführlich erklärt werden, sollte es sich trotz der algebraischen Begründung sehr gut zum Studium auch für Nichtmathematiker mit mathematischen Grundkenntnissen eignen wie zum Beispiel Informatiker und Physiker.
Das Buch ist in drei Kapitel eingeteilt. Das erste enthält eine allgemeine Einführung der linearen Codes als Unterräume von Vektorräumen über endlichen Körpern. Es werden die Parameter eines Codes Blocklänge, Dimension und Minimaldistanz sowie die daraus abgeleiteten Begriffe Informationsrate und Fehlerkorrekturrate eingeführt und deren Relationen untersucht. Insbesondere werden die klassischen Schrankensätze von Singleton, Hamming, Plotkin, Gilbert-Varshamov etc. bewiesen. Anschliessend werden wichtige Klassen von Codes wie Hamming-Codes, Reed-Muller-Codes, MDS- und MLD-Codes vorgestellt und untersucht. Des weiteren werden wichtige Konstruktionsprinzipien diskutiert wie Punktieren, Verkürzen, Verlängern, Einschränken, Aufblasen, Summen und Tensorprodukt bilden etc.
Das zweite Kapitel ist speziell den zyklischen Codes gewidmet. Das sind lineare Codes, die zusätzlich unter zyklischer Verschiebung der Koordinaten invariant sind. Diese können auch als Ideale eines Restklassenrings aufgefasst werden und sind daher nicht nur den Methoden der linearen Algebra sondern auch der Ringtheorie zugänglich. Nach einer allgemeinen systematischen Einführung wird insbesondere auf BCH-, Reed-Solomon- und Quadratische-Reste-Codes eingegangen. Nach einem Einschub über Codierung und Decodierung zyklischer Codes werden von zyklischen Codes abgeleitete Codes wie verallgemeinerte Reed-Solomon-Codes (Generalisierung), Alternant- und klassische Goppa-Codes (Einschränkung) und verallgemeinerte Justesen-Codes (Konkatenation) besprochen. Im letzten Teil werden zyklische Codes als Unterräume einer Gruppenalgebra dargestellt und speziell Reed-Muller-Codes nochmals in diesem Kontext behandelt.
Im dritten Kapitel über Anzahlen und Repräsentanten von Isometrieklassen verlassen die Autoren den Standardstoff und widmen sich der Klassifikation linearer Codes bis auf Isometrie. Es werden zuerst die Klassifikationsprinzipien und Methoden ausführlich beschrieben wie zum Beispiel die Zerlegung in unzerlegbare lineare Codes. Exemplarisch wird die Klassifikation bis auf Isometrie für kleine Parameter unter Verwendung der Computeralgebrapakete SYMMETRICA und DISCRETA durchgeführt und in Tabellen vorgestellt. Ein weiteres Hauptthema in diesem Kapitel ist die Repräsentantenauswahl in einer Isometrieklasse und dessen Berechnung. In den abschliessenden Abschnitten wird ergänzend die Gitterbasisrelation erklärt und auf das Problem der Berechnung der Minimaldistanz angewandt sowie die zufällige Erzeugung linearer Codes mit dem Dixon-Wilf-Algorithmus vorgestellt und auf Blockcodes verallgemeinert.
Das Buch insgesamt ist sehr sorgfältig und leserfreundlich abgefasst. Neben dem ausführlich präsentierte Stoff mit vielen Beispielen und tabellarischen Übersichten enthält es zu jedem Abschnitt eine Reihe hilfreicher Übungsaufgaben. Es ist damit als einführende Lektüre - im dritten Kapitel auch als Ergänzung zu anderen Standardwerken über lineare Codes - sehr zu empfehlen.
Rezension: B. Heinrich Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 26 - März 2000