www.wikidata.de-de.nina.az

Kodierungstheorie Die ist die mathematische Theorie der fehlererkennenden und korrigierenden Codes Solche Codes kommen d

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

Literatur Bearbeiten

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

Einzelnachweise Bearbeiten

  1. Golay, Notes on digital coding, Proc. IRE, Band 37, 1949, S. 657, (Memento vom 7. Oktober 2016 im Internet Archive)
  2. Hamming, Error detecting and error correcting codes, Bell System Techn. J. Band 29, 1950, S. 147–160, PDF
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Kodierungstheorie ist die mathematische Theorie der fehlererkennenden und korrigierenden Codes Solche Codes kommen dort zur Anwendung wo digitale Daten gegen bei Ubertragung oder Speicherung auftretende Fehler geschutzt werden sollen Beispiele sind die Kommunikation mit Objekten im Weltraum und das Speichern von Daten auf einer CD Grosse Teile der Kodierungstheorie beruhen auf der Algebra weshalb auch haufig 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 Inhaltsverzeichnis 1 Geschichte 2 Beschreibung 3 Siehe auch 4 Literatur 5 EinzelnachweiseGeschichte BearbeitenAls die Begrunder der algebraischen Kodierungstheorie gelten Marcel J E Golay der 1949 den nur eine halbe Seite umfassenden Artikel Notes on digital coding veroffentlichte 1 sowie Richard Hamming mit seiner aus patentrechtlichen Grunden 1950 zeitverzogert erschienenen Arbeit Error detecting and error correcting codes 2 Beschreibung BearbeitenVon der Kryptographie und der Datenkompression unterscheidet sich die Kodierungstheorie in ihrer Zielsetzung Wahrend bei ersteren die Daten gegen ungewollte Empfanger abgesichert bzw die Datenmenge reduziert werden soll ist man in der Kodierungstheorie daran interessiert die Datenmenge durch Einfugen von Redundanzen bewusst zu erhohen um dadurch eine Absicherung gegen auftretende Fehler zu erreichen Diese Arten der Datenmodifikation konnen auch miteinander kombiniert werden Es ist nicht unublich dass Daten zuerst komprimiert dann kryptographisch verschlusselt und schliesslich gegen Ubertragungsfehler 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 Kenngrosse fur die in einer festen Datenmenge enthaltenen Informationsmenge sowie die Korrekturrate eine Kenngrosse fur 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 moglich alle diese Eigenschaften gleichzeitig zu optimieren Deshalb muss in der Praxis stets neu entschieden werden welcher Code den besten Kompromiss fur eine bestimmte Anwendung bietet Fur einfache Algorithmen zur Kodierung und Decodierung ist es hilfreich dem Code eine moglichst reichhaltige algebraische Struktur aufzupragen 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 zugehorigen Gruppenringes uber einem endlichen Korper gibt oft weiteren Aufschluss uber die Struktur des Codes Eine weitere Klasse von Codes sind die Faltungscodes Siehe auch BearbeitenKanalkodierung Blockcode ParitatsbitLiteratur BearbeitenRichard 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 Schonfeld 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 Bande Elsevier Amsterdam u a 1998 ISBN 0 444 50088 X Ralph Hardo Schulz Codierungstheorie Eine Einfuhrung 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 Einzelnachweise Bearbeiten Golay Notes on digital coding Proc IRE Band 37 1949 S 657 PDF Memento vom 7 Oktober 2016 im Internet Archive Hamming Error detecting and error correcting codes Bell System Techn J Band 29 1950 S 147 160 PDF Abgerufen von https de wikipedia org w index php title Kodierungstheorie amp oldid 233970416