Codierungstheorie

Die Kodierungstheorie ist die mathematische Theorie der fehlererkennenden und -korrigierenden Codes. Solche Codes kommen überall 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 Codierungstheorie auch Methoden aus der Kombinatorik, der Zahlentheorie sowie der endlichen Geometrie zum Einsatz.

Geschichte

Als die Begründer der algebraischen Codierungstheorie 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 Codierungstheorie 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 codiert 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 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 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 Faltungs-Codes.

Siehe auch

• Kanalkodierung
• Blockcode
• Faltungscode
• Paritätsbit
• Binärer linearer Code

Literatur

• Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: Informations- und Kodierungstheorie, 2. neu bearb. und erw. Auflage, Teubner, Stuttgart Leipzig Wiesbaden März 2003, ISBN 3-519-23003-8
• Ralph-Hardo Schulz: Codierungstheorie. Eine Einführung., 2. Auflage, Vieweg Verlag, Wiesbaden 2003, ISBN 3-528-16419-0
• Richard W. Hamming: Coding and Information Theory, Prentice-Hall, Englewood Cliffs, N.J. 1980, ISBN 0-13-139139-9
• Werner Heise, Pasquale Quattrocchi: Informations- und Codierungstheorie. Mathematische Grundlagen der Daten-Kompression und -Sicherung in diskreten Kommunikationssystemen, 3. Auflage, Springer, Berlin-Heidelberg 1995, ISBN 3-540-57477-8
• Vera S. Pless, W. Cary Huffman (eds.): Handbook of Coding Theory, (2 Volumes), Elsevier, Amsterdam 1998, ISBN 0-444-50088-X
• Wolfgang Willems: Codierungstheorie, (Taschenbuch), Gruyter, Berlin 1999, ISBN 3-110-15873-6