Fundamentals of Error-Correcting Codes
W. C. Huffman und V. Pless
Cambridge University Press, 2003, 646 Seiten, 64,00 $
ISBN 0-521-78280-5
Ein halbes Jahrhundert nach der Geburtsstunde der Codierungstheorie (Publikation von C. Shannons Artikel A mathematical theory of communication, 1948) erschien das zweibändige Handbook of Coding Theory, eine Sammlung aus 33 Beiträgen verschiedener Autoren zum aktuellen Stand der Forschung auf diesem Gebiet. Herausgeber des Handbook sind die beiden Autoren des vorliegenden Buches, das nach ihren eigenen Angaben unter anderem als Hinführung zum Handbook dienen soll.
Das Buch eignet sich für Leser mit soliden Kenntnissen in linearer Algebra; die benötigten Grundlagen aus der Algebra (z. B. endliche Körper, euklidischer Algorithmus) bzw. elementaren Zahlentheorie werden im Text entwickelt.
Der Hauptteil der Buches (Kapitel 1–11) ist der sogenannten elementaren Codierungstheorie gewidmet. Im einführenden Kapitel werden die Grundkonzepte linearer Codes erklärt: Erzeuger- und Kontrollmatrizen, Konstruktionen mit Codes, Äquivalenzbegriffe, Dualität, sowie erste Beispielklassen (Hamming-, Golay und Reed-Muller-Codes) und der Satz von Shannon. Die Kugelpackungsschranke liefert eine Überleitung zum zweiten Kapitel, in dem in aller Ausführlichkeit die verschiedenen (asymptotischen) Schranken behandelt werden. Die im Kapitel 3 entwickelten elementaren Aussagen über endliche Körper und verwandte Themen finden direkte Anwendung im folgenden Kapitel über zyklische Codes. Im fünften Kapitel werden BCH- und spezielle Reed-Solomon-Codes vorgestellt und mehrere Decodier-Algorithmen erklärt. Die QR-Codes (quadratische Reste) werden im sechsten Kapitel als Spezialfall der von V. Pless eingeführten sogenannten duadischen Codes entwickelt. Auch das siebte Kapitel über Gewichtsverteilungen behandelt nicht nur den Standardstoff, sondern z. B. auch verallgemeinerte Hamming-Gewichte.
Blockpläne (Designs) und Steinersysteme sind das Thema des achten Kapitels, wo u. A. die Nichtexistenz einer projektiven Ebene der Ordnung 10 (in Form einer Zusammenfassung) als Anwendung gegeben wird. Auf die Bedeutung der Steinersysteme für die Symmetriegruppen der Codes wird hier allerdings nicht eingegangen.
Zwei Kapitel über selbstduale Codes liegen mitten im Forschungsgebiet der Autoren. Die hier behandelten Themen gehen deutlich über den Umfang anderer Lehrbücher hinaus. In diesen Kapiteln finden sich auch besonders zahlreiche Research Problems. Das elfte Kapitel behandelt den Überdeckungsradius (die kleinste Zahl d, so dass jedes Wort des Alphabets Abstand höchstens d von einem Codewort hat) und Formeln zur Bestimmung desselben für einige Klassen von Codes.
Die letzten vier Kapitel des Buches lassen sich am besten als Ausblicke in andere Gebiete der Codierungstheorie verstehen. Im zwölften Kapitel werden erstmals nichtlineare Codes, nämlich sogenannte lineare Codes über Z/4Z, betrachtet, die als additive Untergruppen von (Z/4Z)n definiert sind und in Zusammenhang mit einigen bekannten Familien nichtlinearer binärer Codes stehen.
Die Einführung in die algebraische Geometrie und geometrische Goppa-Codes (Kapitel 13) ist sehr elementar und knapp gehalten und deshalb nicht beweisvollständig. Hauptresultat in diesem Kapitel (ebenfalls ohne Beweis) ist die Existenz geometrischer Codes, für die die Gilbert-Varshamov-Schranke überschritten wird (Tsfasman-Vladut-Zink). So wird auf wenigen Seiten klar, warum diese Codes sich wachsenden Interesses erfreuen.
Zwei Kapitel über Convolution Codes and Soft Decision schließen diesen zweiten Teil des Buches ab.
Der vorliegende Text ist gut zum Selbststudium geeignet, zahlreiche Übungsaufgaben (z. T. sehr elementar, aber eigentlich immer nützlich) erhöhen die Fingerfertigkeit im Umgang mit dem vorgestellten Material. Mindestens genauso wertvoll ist das Buch jedoch für die Vorbereitung von Vorlesungen und Übungen. Damit man angesichts der Fülle des Materials den Überblick behält, haben die Autoren der Einleitung einen Auswahlvorschlag für eine einsemestrige Vorlesung sowie Themenblöcke für weiterführende Vorlesungen beigefügt. Aber auch als Ergänzung zu anderen Texten und als Fundgrube für Beispiele und Gegenbeispiele ist dieses Buch überaus gut zu gebrauchen. Erfreulich sind auch die Abschnitte über Anwendungen z. B. in der CD-Codierung oder in der Raumfahrt.
Es ist den Autoren gelungen den Text klar verständlich zu halten, und es hat sich sicher ausgezahlt, dass sie dabei auf die Anregungen von Studenten und Kollegen (nach einigen Testläufen in Kursen) zurückgreifen konnten. Die große Sorgfalt, mit der dieses Buch geschrieben und bis zu seiner endgültigen Form überarbeitet wurde, ist heute leider nicht mehr selbstverständlich.
Rezension: Julia Hartmann (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 35 - Oktober 2004