Die Vorwörter aus

Werner Heise, Pasquale Quattrocchi :
Informations- und Codierungstheorie.

Mathematische Grundlagen der Daten-Kompression
und -Sicherung in diskreten Kommunikationssystemen.

3. Aufl., Springer-Verlag, Berlin-Heidelberg 1995

Vorwort zur ersten Auflage

Frau Professor Judita Cofman machte den italienischen Autor im März 1977 darauf aufmerksam, daß seine Arbeiten über scharf dreifach transitive Permutationsmengen mit den Arbeiten des deutschen Autors über Minkowski-Ebenen in wesentlichen Ergebnissen deckungsgleich waren.

Der Italiener lud den Deutschen daraufhin als Gastprofessor des Consiglio Nazionale delle Ricerche (CNR) am Mathematischen Institut der Universität Modena ein; die Konkurrenz wandelte sich schnell in eine dauerhafte Freundschaft.

Ausgehend von unserem ursprünglichen Arbeitsgebiet, der endlichen Geometrie, interessierten wir uns zunehmend für die Codierungstheorie. In Vorlesungen und Seminaren der Technischen Universität München und in Seminaren an der Universität Modena (während der sich alljährlich wiederholenden Gastaufenthalte des deutschen Autors in Italien) spürten wir den Mangel an für Studenten geeigneten Lehrbüchern, die über eine bloße Einführung hinausführten. Die meisten weiterführenden Bücher sind entweder nachrichtentechnischer Natur oder wenden sich an Spezialisten mit besonderen mathematischen Vorkenntnissen.

Als wir dieses Buch schrieben, stellten wir uns den Leser als Studenten der Informatik im 5. Semester vor, der sich für die mathematischen Grundlagen der Informations- und Codierungstheorie interessiert. Zur Bequemlichkeit des Lesers haben wir die benötigten (und als bekannt vorausgesetzten) Grundbegriffe aus Analysis, Wahrscheinlichkeitsrechnung und Algebra rekapituliert. (So ist beispielsweise der Abschnitt 3.1 den grundlegenden Eigenschaften der Logarithmus-Funktionen gewidmet.) Die Darstellung dieser Grundbegriffe sollte nicht dazu verleiten, die entsprechenden Abschnitte als Lehrbuch der Algebra oder Wahrscheinlichkeitsrechnung zu mißbrauchen: Nur für den Gegenstand dieses Buches relevante Grundlagen sind dargestellt.

Zu Problemen der technischen Realisation von Kommunikationssystemen haben wir geschwiegen. Als Mathematiker haben wir dazu nichts zu sagen.

Das Buch konzentriert sich auf den mathematischen Aspekt der Daten-Kompression und -sicherung in diskreten Kommunikationssystemen. Das heißt zum Beispiel, daß in Abschnitt 9.6 die mathematischen Grundlagen der Decodierung der BCH-Codes ausführlich dargestellt werden, daß aber der Berlekamp-Massey-Algorithmus - ein effizientes Verfahren zur Aufstellung der für die Decodierung benötigten linearen Gleichungssysteme über GF(q) - selbst nicht gebracht wird, ganz zu schweigen von der technischen Realisation des Decodierers.

Abgesehen von wenigen Ausnahmen in sehr speziellen Passagen (zum Beispiel in Abschnitt 8.12) werden die Aussagen dieses Buches bewiesen; deswegen haben wir im Text im allgemeinen auf Literaturhinweise und Prioritätszuweisungen verzichtet.

Ein Student der Informatik sollte nicht zuviel Zeit für ein Randgebiet der Informatik wie die Informations- und Codierungstheorie verschwenden. Wir haben deswegen auf Übungsaufgaben verzichtet und statt dessen durchgerechnete Beispiele in den Text eingefügt.

Wir danken Frau Doris Jahn für das sorgfältige Tippen des Manuskriptes und machen sie für alle mathematischen Fehler haftbar. Der italienische Autor übernimmt dafür die Verantwortung für alle Tipp-Fehler. Der deutsche Autor weist jede Verantwortung weit von sich. Das Stichwortverzeichnis hat Frau Ulrike Heise angefertigt. Die Herren Arrigo Bonisoli, Pavel Filip und Jean Georgiades wurden von uns freundlichst gezwungen, das Manuskript auf Fehler zu kontrollieren; die Herren Professoren Dr. Helmut Vogel und Dr. Heinz Wähling lasen Abschnitt 3.6 beziehungsweise Kapitel 7 durch. Jeder unentdeckte Fehler vermindert unseren Dank. Der Vater des deutschen Autors, Bruno Heise, hat die Diagramme gezeichnet. Danke, Papa! Als Materialisten danken wir dem Consiglio Nazionale delle Ricerche überaus herzlich für die Finanzierung der Gastaufenthalte in Modena. Herrn Rossbach vom Springer-Verlag danken wir für die unbürokratische Betreuung.

Eine persönliche Anmerkung für unseren gemeinsamen Landsmann Reinhold Messner: Bitte verzeihen Sie uns die respektlose Bemerkung in Kapitel 10. Seien Sie versichert, daß wir Ihre sportlichen Leistungen bewundern.

Modena, im Februar 1983
W. H., P. Q.

Vorwort zur zweiten Auflage

Folgendes hat sich geändert: Viele Schreibmaschinen-Tippfehler der ersten Auflage wurden durch vornehmere Textverabeitungs-Tippfehler ersetzt. Wo die Erfahrungen des Unterrichts es ermöglichten, wurde die Darstellung gestrafft, gedehnt oder geglättet. Das betrifft insbesondere die Kapitel 1, 7 und 8. Der Begriff systematischer Code wird jetzt im orthodoxen Sinne verwandt. Der Begriff optimaler Code wurde konsequent durch MDS-Code ersetzt und wird jetzt in einem umfassenderen Sinne gebraucht. Die Konvolutionscodes heißen jetzt Faltungscodes. Diese Terminologieänderungen entspringen keiner tiefen Einsicht, sondern wurden in Anpassung an den allgemeinen Sprachgebrauch vorgenommen. In Abschnitt 8.7 werden neben der Varshamov-Schranke auch die Gilbert-Schranke für lineare Codes und die Griesmer-Schranke bewiesen. Die Kapitel 9 und 10 wurden gründlich revidiert. Da ist sozusagen kein Buchstabe auf dem alten geblieben. In den Abschnitten 9.1 und 9.4 wurde das Automorphismenproblem für lineare und zyklische Codes sehr viel sauberer beschrieben. In Abschnitt 9.7 wird nach einem fast trivial zu nennenden Beweis des quadratischen Reziprozitätsgesetzes die Theorie der Quadratische-Rest-Codes bis zur Quadratwurzelschranke unter Einschluß des Gleason-Prange-Theorems zum erstenmal in einem Lehrbuch lückenlos und frei von groben Fehlern dargestellt. In Kapitel 10 wurde großer Wert darauf gelegt, die Begriffe Faltungscode und Faltungscodierer zu trennen.

Soweit zum Abschreiben für den Rezensenten.

In Kapitel 7 und 10 haben wir uns über Fehler zweier ,,very important persons`` mokiert. Wer sich als Zensurenverteiler und Dogmenverkünder betätigt, oder wer auf junge Mathematiker am Beginn ihrer Karriere einschlägt, sollte auch einiges einstecken können. Bei allen anderen Kollegen, die sich durch irgendeine Passage oder durch die Nichterwähnung ihrer Person in die Wade gebissen fühlen, entschuldigen wir uns von vornherein. So war das nicht gemeint. Im Zeichen von Glasnost lehnen wir Personenkult ab.

Bei der Überarbeitung des Buches haben uns viele geholfen. Dafür bedanken wir uns ganz herzlich. Zunächst einmal sind unsere zum Teil unvergeßlich vergeßlichen Studenten zu nennen, für die dieses Buch geschrieben wurde, und deren Kritik wir sehr ernst nehmen. Dr. Michael Kaplan fand bei der Durchsicht des Manuskripts viele Fehler. Der Diplomand Thomas Honold arbeitete fast das gesamte Manuskript gründlich durch und veranlaßte zahlreiche Verbesserungen und Berichtigungen. Er entdeckte alle lückenhaften Argumentationen, bei denen wir der Faulheit nachgegeben und uns ,,'s wird schon so sein!`` gedacht hatten; unerbittlich drang er auf Präzisierung. Dr. sc. nat. Ludwig Staiger las das Manuskript ebenfalls durch, kritisierte schlampige Formulierungen, beseitigte massenweise Fehler und machte uns auf einschlägige Arbeiten sowjetischer Codierungstheoretiker aufmerksam. Seinem fachmännischen Rat sind wir ausnahmslos gefolgt. Die Erörterung der Code-Verkettung in Abschnitt 8.10.4 entstammt seiner Feder; da beseitigte er schwachsinnige Ausführungen der ersten Auflage. Die deutschen Postverwaltungen transportierten das Papier kilogrammweise zuverlässig und verlustfrei von München nach Berlin und retour; das ist nicht selbstverständlich, sondern verdient ein großes Lob. Die italienische Post sabotierte die Fertigstellung des Buches nach Kräften: Mit einer durchschnittlichen Geschwindigkeit von 0,2 m/sec beförderte sie einen Express-Brief von Modena nach München. Auch der Zoll hat Teile des Manuskripts begutachtet und gestempelt, aber leider keine nützlichen Kommentare geliefert.

Die Ideen zu einigen neuen Bildern stammen von einem Freund, der nicht genannt werden will; ein herzliches Dankeschön nach Frankfurt. Herrn Dr. Michael Kaplan und Herrn Dr. Peter Vachenauer danke ich für die geduldige Einweihung in die Geheimnisse der Textverarbeitung.

Bei Frau Ingeborg Mayer und Herrn Dr. Hans Wössner vom Springer-Verlag bedanke ich mich für die familiäre und freundschaftliche Betreuung. Am Telephon verabschiedeten wir uns stets mit ,,Tschüß``.

München, im September 1988
W. H.

Vorwort zur dritten Auflage

Eigentlich wollte ich an dem Buch außer der Umstellung auf das Textverarbeitungssystem Signum!Drei der Firma Application Systems Heidelberg Software GmbH nicht viel ändern. Unveränderte Neudrucke von Büchern über sich verändernde Themen gleichen aber dem Aussetzen Unmündiger; die moralischen Bedenken siegten über die Faulheit: Die vorliegende dritte Auflage ist kein Update, sondern ein Upgrade.

Bei guten Codierungen werden die Nachrichten und die sie symbolisierenden Signale gleichmäßig gegen Störungen geschützt. Die Homogenität drückt sich in Transitivitätseigenschaften der Symmetrien des Codes aus. Dieser Gesichtspunkt wurde verstärkt berücksichtigt. Schon in dem als Motivation gedachten Abschnitt 1.7.3 werden strukturerhaltende Abbildungen von Codes, die Isometrien und Automorphismen bezüglich der Hamming-Metrik, behandelt.

Die Kapitel 2 bis 6 wurden - bis auf eine Vereinfachung des Beweises des Satzes über die maximale Effzienz einer Quellencodierung auf Seite 144f. - nur stilistisch überarbeitet.

In Abschnitt 7.1 habe ich die Grundlagen der linearen Algebra zum Zwecke der Sprachregelung breiter dargestellt. Der Abschnitt 7.5 enthält nun eine Liste der wichtigsten Eigenschaften der Kreisteilungspolynome.

Die Kapitel 8 und 9 sind nicht mit der zweiten Auflage kompatibel: Hier wurden die Dinge umgestellt, vereinfacht, gestrichen und ergänzt; auch die Codierungstheorie hat sich in den letzten stürmischen sechs Jahren gewandelt, und ich habe einiges dazugelernt.

Herr Dr. Thomas Honold hat mich in meiner Auffassung bestärkt, keinen Personenkult zu betreiben: In den Disquisitiones von Carl Friedrich Gauß fand er eine Liste der Generatorpolynome der Quadratische-Rest-Codes einer Länge n=23. Namensnennungen sind nicht als Prioritätszuweisungen zu verstehen, vielleicht findet man noch interessante babylonische Scherben.

Bei den Korrekturen haben mich Frau Dipl.-Math. Ioana Constantinescu und Herr Dr. Thomas Honold sehr zuverlässig unterstützt. Dafür und für die stete Forderung nach Ausführlichkeit (,,Ein Leser, der zugunsten des Kaufes dieses Buches auf eine Tankfüllung bleihaltigen Superbenzins verzichtet, hat ein Anrecht darauf, sich nicht alles selbst überlegen zu müssen.``) bin ich ihnen sehr dankbar. Als Grundlage für den neuen Abschnitt 9.7 diente mir die Ausarbeitung einer Vorlesung, die Herr Dr. Michael Kaplan an der Universität der Basilicata in Potenza gehalten hat; mein heißer Dank in das Büro nebenan! Herr Professor Dr. Pavel Filip las im Wintersemester 1992/93 die Informations- und Codierungstheorie an der TU München, davon habe ich profitiert; danke Pavlovic! Herr Professor Dr. Ludwig Staiger bewahrte mich davor, in Kapitel 10 einen Bock zu schießen; danke Luigi! Herr Professor Dr. Arrigo Bonisoli versicherte mir, daß er die vor zehn Jahren begonnene Übertragung des Buches in das Italienische fortsetzen werde; lieber Sole, ich entschuldige mich dafür, daß Du Deine bisherigen Übersetzungen wegen Veraltung wirst wegwerfen müssen! Bei Herrn Professor Dr. Dr. h.c. Roland Bulirsch bedanke ich mich für die Beschaffung der Zeichensätze der Firma Holger Schlicht Types Hamburg. Die Zusammenarbeit mit Frau Ingeborg Mayer und Herrn Dr. Hans Wössner vom Springer-Verlag verdient das Prädikat ,,ideal``; ich bedanke mich für die mir gebotene Freiheit und freundschaftliche Behandlung.

Auch der Koautor der ersten Auflage hofft, daß die vorliegende dritte Auflage einen solchen Reifegrad erreicht hat, daß wir es verantworten können, dieses Buch den Männern zu widmen, die uns die Mathematik beigebracht haben, den Professoren Dr. Dr. h.c. Helmut Karzel und Luigi Antonio Rosati.

Die Wiedervereinigung erlaubt es mir, zwei Mißverständlichkeiten aus dem Vorwort zur zweiten Auflage auszuräumen:
Bei dem ungenannten Frankfurter Freund, der die Ideen zu einigen Bildern beisteuerte, handelt es sich um den Karikaturisten Karl Koppe aus Frankfurt an der Oder; herzlichen Dank, Karl!
Die italienischen Zollbeamten haben mich nie kontrolliert. Ein deutscher demokratischer Zöllner studierte den Entwurf des Kapitels über Faltungscodes sehr gründlich und ließ mich unter Bedenken passieren.

München, im November 1994
W. H.

Werner Heise, München, 28. September 1995