Kodierungstheorie

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

Große Teile der Kodierungstheorie beruhen auf der Algebra, weshalb auch häufig der Begriff algebraische Kodierungstheorie benutzt wird, um eine klare Grenze zur verwandten Informationstheorie zu ziehen. Neben der Algebra kommen in der Kodierungstheorie auch Methoden aus der Kombinatorik, der Zahlentheorie sowie der endlichen Geometrie zum Einsatz (zum Beispiel Dichteste Kugelpackungen).

Geschichte

Als die Begründer der algebraischen Kodierungstheorie gelten Marcel J. E. 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.

Beschreibung

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 Kodierungstheorie daran interessiert, die Datenmenge durch Einfügen von Redundanzen bewusst 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 kodiert werden. Speziell die Vorschaltung eines Kompressionsverfahrens ist oft angebracht, da dadurch in den Daten eine statistische 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 die Kodierungs- und Decodierungsalgorithmen nicht zu hohe technische Voraussetzungen erfordern. Es ist zurzeit 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 endlichen Vektorraums), und die zyklischen Codes (Struktur einer endlichen Algebra) entstanden. Auch die Untersuchung des zugehörigen Gruppenringes über einem endlichen Körper gibt oft weiteren Aufschluss über die Struktur des Codes. Eine weitere Klasse von Codes sind die Faltungscodes.

Siehe auch

• Kanalkodierung
• Blockcode
• Paritätsbit

Literatur

• Richard Wesley Hamming: Coding and Information Theory. Prentice-Hall, Englewood Cliffs NJ 1980, ISBN 0-13-139139-9.
• Werner Heise, Pasquale Quattrocchi: Informations- und Codierungstheorie. Mathematische Grundlagen der Daten-Kompression und -Sicherung in diskreten Kommunikationssystemen. 3. neubearbeitete Auflage. Springer, Berlin u. a. 1995, ISBN 3-540-57477-8 (Springer-Lehrbuch).
• Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: Informations- und Kodierungstheorie. 2. neu bearbeitete und erweiterte Auflage. Teubner, Stuttgart u. a. 2003, ISBN 3-519-23003-8.
• Vera S. Pless, W. Cary Huffman (Hrsg.): Handbook of Coding Theory. 2 Bände. Elsevier, Amsterdam u. a. 1998, ISBN 0-444-50088-X.
• Ralph-Hardo Schulz: Codierungstheorie. Eine Einführung. 2. aktualisierte und erweiterte Auflage. Vieweg Verlag, Wiesbaden 2003, ISBN 3-528-16419-0.
• Wolfgang Willems: Codierungstheorie. de Gruyter, Berlin u. a. 1999, ISBN 3-110-15873-6 (De-Gruyter-Lehrbuch).