Kodierungstheorie

Kodierungstheorie

Die Kodierungstheorie ist die mathematische Theorie der fehlererkennenden und -korrigierenden Codes. Sie kommt überall dort zur Anwendung, wo digitale Daten gegenüber bei Übertragung oder Speicherung auftretenden Fehlern geschützt werden sollen. Beispiele sind die erdgebundene Kommunikation mit Objekten im Weltraum oder das Speichern von Daten auf einer CD.

Große Teile der Codierungstheorie beruhen auf der Kombinatorik und vor allem auf der Algebra, weshalb auch häufig der Begriff algebraische Kodierungstheorie benutzt wird um eine klare Grenze zur verwandten Informationstheorie zu ziehen. Als die Begründer der algebraischen Codierungstheorie gelten Marcel Golay, der 1949 den nur eine halbe Seite umfassenden Artikel Notes on digital coding veröffentlichte, sowie Richard Hamming mit seiner aus patentrechtlichen Gründen 1950 zeitverzögert erschienenen Arbeit Error-detecting and error-correcting codes.

Von der Kryptographie und der Datenkompression unterscheidet sich die Kodierungstheorie in ihrer Zielsetzung: Während bei ersteren die Daten gegen ungewollte Empfänger abgesichert bzw. die Datenmenge reduziert werden soll, ist man in der Codierungstheorie daran interessiert, die Datenmenge durch Einfügen von Redundanzen bewußt zu erhöhen, um dadurch eine Absicherung gegen auftretende Fehler zu erreichen. Diese Arten der Datenmodifikation können auch miteinander kombiniert werden: Es ist nicht unüblich, dass Daten zuerst komprimiert, dann kryptographisch verschlüsselt und schließlich gegen Übertragungsfehler codiert werden. Speziell die Vorschaltung eines Kompressionsverfahrens ist oft angebracht, da dadurch in den Daten eine Gleichverteilung der Zeichen hergestellt wird, von der die Kodierung profitiert.

Wichtige Parameter eines Codes sind die Informationsrate (eine Kenngröße für die in einer festen Datenmenge enthaltenen Informationsmenge), sowie die Korrekturrate (eine Kenngröße für die Fehlerresistenz bei einer festen Datenmenge). Neben Codes mit einer guten Informations- und Korrekturrate ist man in der Regel auch daran interessiert, dass der Codierungs- und der Decodierungsalgorithmus nicht zu hohe technische Voraussetzungen erfordern. Es ist nicht möglich, alle diese Eigenschaften gleichzeitig zu optimieren. Deshalb muss in der Praxis stets neu entschieden werden, welcher Code den besten Kompromiss für eine bestimmte Anwendung bietet.

Für einfache Algorithmen zur Kodierung und Decodierung ist es hilfreich, dem Code eine möglichst reichhaltige algebraische Struktur aufzuprägen. Auch die theoretische Behandlung solcher Codes ist einfacher als im allgemeinen Fall. Vor diesem Hintergrund sind die Gruppencodes (Struktur einer Gruppe), die linearen Codes (Struktur eines Vektorraums), und die zyklischen Codes (Struktur einer Algebra) entstanden. Eine weitere Klasse von Codes sind die Faltungs-Codes.

Inhaltsverzeichnis

1 Einfache Beispiele 1.1 Paritätskontrolle (parity check) 1.2 ISBN-Code 2 Literatur

Einfache Beispiele

Paritätskontrolle (parity check)

Die Paritätskontrollcodierung hängt einer Folge von Bits (Informationswort) ein Paritätskontrollbit an: Je nachdem, ob die Summe der Einsen (Paritätssumme) im Informationswort gerade oder ungerade ist, wird eine Null bzw. eine Eins angehängt. Die resultierende Bitfolge hat in jedem Fall eine gerade Paritätssumme und ist um eine Stelle länger als das Informationswort. Es wird Codewort genannt.

Beispiel: Das Informationswort 0011101 hat vier Einsen. Vier ist eine gerade Zahl, das Paritätskontrollbit ist also die Null, und das resultierende Codewort ist 00111010. Das Informationswort 1010010 hat hingegen eine ungerade Paritätssumme und wird in das Codewort 10100101 codiert. Beide Codewörter weisen eine gerade Paritätssumme auf.

Ein derart kodiertes Wort kann nun gespeichert oder übertragen werden. Sollte dabei ein Bit verfälscht werden (eine Null in eine Eins oder eine Eins in eine Null), so ist die Paritätssumme des resultierenden Worts ungerade, und der Dekodierer erkennt, dass es zu einem Fehler gekommen ist. Es ist aber für den Dekodierer nicht möglich, den Fehler zu korrigieren, da nicht bekannt ist, welches Bit verfälscht wurde. Falls das Kommunikationssystem Rückfragen zulässt, wird der Decodierer die fragliche Bitfolge nochmal anfordern. Wurde jedoch mehr als ein Bit verfälscht, so ist es eventuell gar nicht möglich, den Fehler zu erkennen, da die Paritätssumme dann auch gerade sein kann. Man sagt: Der Paritätskontrollcode ist 1-fehlererkennend und 0-fehlerkorrigierend.

Die ursprüngliche Form der ASCII-Zeichentabelle besteht aus 128 Zeichen, jedes Zeichen ist durch eine Folge von sieben Bits eindeutig festgelegt. Da ein Rechner acht Bits zu einem Byte zusammenfasst, wird dieses achte Bit gerne verwendet, um ein Paritätskontrollbit anzuhängen.

ISBN-Code

Der ISBN-Code basiert auf einer ähnlichen Idee wie der Paritätskontrollcode. Ein Buch bekommt eindeutig eine neunstellige Nummer zugeteilt. Schreibt man diese Nummer als , so hängt der Kodierer diesem Informationswort eine Prüfziffer an. Diese berechnet sich als die Zahl, die als Rest bei der ganzzahligen Teilung von durch 11 entsteht. Sollte bei der Teilung der Rest 10 übrig bleiben, so wird dieser in Anlehnung an das römische Zahlensystem durch den Buchstaben X symbolisiert. Da ISBN-Nummern häufig mündlich weitergegeben werden, ist der Code besonders auf die Erkennung von menschlichen Fehlern ausgelegt: Wird bei der Übertragung eine Stelle verändert oder werden zwei Stellen vertauscht, so ist die Gleichung für die Prüfziffer nicht mehr gültig und der Fehler wird erkannt.

Literatur

• Richard W. Hamming: Coding and Information Theory, Prentice Hall, Inc. 1980, ISBN 0-13-139139-9
• Heise, Quattrocchi: Informations- und Codierungstheorie, 3. Auflage, Springer-Verlag: Berlin-Heidelberg 1995, ISBN 3-540-57477-8

See also: Kodierungstheorie, ASCII, Abstrakte Algebra, Algebra (Struktur), Algebraische Struktur, Bit, Byte, Code, Compact Disc