Seminar im Sommersemester 1995


Seminar über Kodierungstheorie

Wolfgang K. Seiler


Die Kodierungstheorie beschäftigt sich mit dem Entwurf und der Anwendung von fehlererkennenden und fehlerkorrigierenden Codes sowie den zugehörigen (De-)Kodierungsalgorithmen. Einfachste Beispiele fehlererkennender Codes sind die vielfach anzutreffenden Prüfziffern, fehlerkorrigierende Codes werden etwa bei Musik-CDs angewandt (Reed-Solomon-Code) oder bei D-Netz Telephonen (Reed-Muller-Code).

Da in der Praxis fast ausschliesslich binäre Codes verwendet werden, d.h. Codes, die nur auf zwei Zeichen 0 und 1 beruhen, fasst man Codewörter im allgemeinen als Elemente eines Vektorraums über dem Körper mit zwei Elementen auf. Falls die Menge aller Codewörter einen Untervektorraum bildet, spricht man von einem linearen Code; solche Codes sind sehr einfach und schnell zu kodieren und zu dekodieren. Nichtlineare Codes haben demgegenüber den Vorteil, daß sie mit gleichem Aufwand an Prüfziffern im allgemeinen mehr Fehler erkennen und korrigieren können.

Ab etwa 1993 fanden unabhängig voneinander zwei Forschergruppen, daß auch viele nichtlineare Codes, beispielsweise die oben erwähnten Reed-Muller-Codes, als linear aufgefasst werden können, wenn man sie nicht über dem Körper mit zwei Elementen sondern über Z/4Z betrachtet; inzwischen werden immer mehr solche Beispiele gefunden. Diese mathematisch recht einfachen Arbeiten haben erhebliche praktische Bedeutung, da sie zu sehr viel einfacheren und schnelleren Kodierungsalgorithmen als den bislang bekannten führen.

Im Seminar wurden zunächst die Grundbegriffe der Kodierungstheorie behandelt, insbesondere lineare Codes, zyklische Codes und BCD-Codes, zum Schluß dann auch einige der Ergebnisse über die Z/4Z-Linearität nichtlinearer Codes.