Kodierungstheorie


Kodierungstheorie

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.

Inhaltsverzeichnis

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

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).

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Richard-W.-Hamming-Medaille — Die Richard W. Hamming Medaille ist eine Auszeichnung, die jährlich durch das IEEE (Institute of Electrical and Electronics Engineers) für außergewöhnliche Leistungen in der Informationstechnik vergeben wird. Die Medaille ist nach dem… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Fehlervorwärtskorrektur — Als Kanalkodierung (auch Kanalcodierung) bezeichnet man in der Nachrichtentechnik das Verfahren, digitale Daten bei der Übertragung über gestörte Kanäle durch Hinzufügen von Redundanz gegen Übertragungsfehler zu schützen. Die mathematischen… …   Deutsch Wikipedia

  • Kanalcodierung — Als Kanalkodierung (auch Kanalcodierung) bezeichnet man in der Nachrichtentechnik das Verfahren, digitale Daten bei der Übertragung über gestörte Kanäle durch Hinzufügen von Redundanz gegen Übertragungsfehler zu schützen. Die mathematischen… …   Deutsch Wikipedia

  • Präfix-Code — Präfixcode oder präfixfreier Code ist ein Begriff aus der Kodierungstheorie. Als Präfixcode wird ein Code bezeichnet, der die Präfix Eigenschaft erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf kein… …   Deutsch Wikipedia

  • Präfixcode — oder präfixfreier Code ist ein Begriff aus der Kodierungstheorie. Als Präfixcode wird ein Code bezeichnet, der die Präfix Eigenschaft erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf kein Codewort den… …   Deutsch Wikipedia

  • Reed-Solomon-Code — Reed Solomon Codes (kurz RS Codes) sind leistungsfähige Kodierungsverfahren, die beim Lesen oder Empfangen der mit ihnen codierten digitalen Daten erlauben, Fehler zu erkennen und zu korrigieren (Vorwärtsfehlerkorrektur). Bei nach dem DVB… …   Deutsch Wikipedia

  • Besondere Zahlen — sind zum einen Zahlen, die im Sinne der Zahlentheorie eine oder mehrere auffällige Eigenschaften besitzen. Außerdem haben viele Zahlen eine besondere Bedeutung in der Mathematik und/oder in Bezug auf die reale Welt. Diese letzteren Zahlen werden… …   Deutsch Wikipedia

  • Bitseriell — Bei der seriellen Datenübertragung werden Daten, sofern sie digital sind, bitweise hintereinander über ein bestimmtes Medium übertragen. Es gibt verschiedene Standards, über die eine serielle Übertragung erfolgen kann. Die Auflistung einiger… …   Deutsch Wikipedia

  • Bitserielle Übertragung — Bei der seriellen Datenübertragung werden Daten, sofern sie digital sind, bitweise hintereinander über ein bestimmtes Medium übertragen. Es gibt verschiedene Standards, über die eine serielle Übertragung erfolgen kann. Die Auflistung einiger… …   Deutsch Wikipedia