Kodierungstheorie

Kodierungstheorie ist das Teilgebiet der Informatik und Informationstheorie, das sich mit der Konstruktion, Analyse und Optimierung von Codierungssystemen befassen, um Informationen zuverlässig über verrauschte Kanäle zu übertragen oder auf fehleranfälliger Hardware zu speichern. Zentral ist die Idee der Redundanz, die es ermöglicht, Fehler zu erkennen und zu korrigieren, oft durch mathematische Strukturen.

Grundbegriffe: Ein Code besteht aus Wörtern der Länge n über einem Alphabet, oft Z_2 oder einem endlichen Feld GF(q). Blockcodes kodieren k Bit zu n Bit; der Code hat die Rate R = k/n. Lineare Codes werden durch Generator- und Paritätsprüfmatrizen beschrieben. Die Mindestdistanz d bestimmt die Fehlererkennung und -korrektur; Hamming-Distanz misst Unterschiede zwischen Codewörtern. Decoding-Algorithmen reichen von einfachen Hamming-Decodern bis zu komplexen Maximum-Likelihood- oder iterativen Verfahren.

Theoretische Grundlagen: Kanalmodelle wie AWGN, Shannon-Grenze und das codierungstheorem; bei großer Blocklänge existieren Codes, die bei Rate unter der Kapazität eine kleinste Fehlerrate erreichen. Praktische Codes müssen jedoch effizient dekodierbar bleiben; Finite-Feld-Arithmetik ist zentral.

Wichtige Codes und Entwicklungen: Hamming-Codes, Reed-Solomon-Codes (spezifisch in Datenträgern und QR-Codes), BCH-Codes, LDPC- und Turbo-Codes, Polar-Codes. Anwendungen in Kommunikation, Datenspeicherung, Barcodes. Block- und Sequenzencodes finden breite Verwendung.

Geschichte und Bedeutung: Die Idee geht auf Shannon (1948) zurück; Hamming (1950) entwickelte frühere Codes; seit den 1990ern/2000ern führten graphbasierte und probabilistische Codes zu praktischen, nahen optimalen Lösungen in vielen Systemen.