Mathematik macht Freu(n)de FEHLERKORRIGIERENDE CODES GERNOT GRESCHONIG Viele technische Anwendungen der Datenübertragungstechnik und Datenspeichertechnik sind fehlerbehaftet und daher besteht die Notwendigkeit, bei der Übertragung beziehungsweise Speicherung der Daten auftretende Fehler in gewissem Umfang erkennen und korrigieren zu können. Praktisch ist dieses Ziel unter Inkaufnahme eines Verlustes an Speicher- beziehungsweise Übertragungskapazität erreichbar. In einem der einfachsten (aber praktisch trotzdem bedeutenden) fehlerkorrigierenden Code werden die durch vier Datenbits (0 − 1 Informationen) darstellbaren 24 = 16 Kombinationen eineindeutig auf eine 16 elementige Teilmenge der durch 7 Datenbits darstellbaren 27 = 128 darstellbaren Kombinationen abgebildet. Diese 16 ausgewählten aus 128 möglichen Kombinationen sind so beschaffen, dass sich zwei erlaubte Bitmuster an mindestens drei Stellen unterscheiden. Dadurch kann ein Übertragungsfehler in einem solchen Bitmuster aus sieben Bits korrigiert werden, denn das ursprüngliche Bitmuster unterscheidet sich nur um das eine fehlerhafte Bit und das ursprüngliche Bitmuster ist das einzige zulässige mit dieser Eigenschaft. Dies folgt unmittelbar aus der Eigenschaft der sogenannten Hamming-Distanz als Metrik, welche den Abstand zweier Bitmuster genau durch die Anzahl der Stellen mit unterschiedlichen Bits bemisst. Weiters können zwei Übertragungsfehler in einem derartigen Siebenerblock erkannt, jedoch nicht mehr korrigiert werden. Bisher erscheint die Realisierung solch einer Kodierung als ausschließlich kombinatorisches Problem. Eine wesentliche Klasse von Codes, die sogenannten linearen Codes, können aber durch die Methoden der linearen Algebra in Vektorräumen über dem endlichen Körper Zp (für eine Primzahl p, im Binärsystem für p = 2) behandelt werden. Dabei können Kodierung, Fehlererkennung durch Matrizenrechnung vorgenommen werden, die Fehlerkorrektur ergibt sich durch Orthogonalisierung im betreffenden Hilbertaum. Literatur [1] Fehlerkorrigierende Codes, Skriptum von Prof. Gerhard Dorfer (TU Wien), verfügbar auf http://dmg.tuwien.ac.at/dorfer/codes/Pdf_Dateien/Skriptum_2016S.pdf 1
© Copyright 2024 ExpyDoc
