Rechnernetze
Home Nach oben

Neue Kodierungsverfahren

 

Die Leitungskodierung stellt einen wichtigen Teil der Datenübertragung dar, so dass sie insbesondere für die Rechnernetze eine große Bedeutung besitzt. Dennoch fällt dieses Gebiet in die Regel in den Bereich der Nachrichtentechnik, weniger der Informatik selbst. Sie können daher an dieser Stelle nur am Rande erläutert werden.

Auch in diesem Gebiet gibt es eine Reihe von Verbesserungen, die in viele technische Geräte Eingang gefunden haben.

Reed-Solomon

Bereits in den sechziger Jahren wurden sogenannte Reed-Solomon-Kodierungen entwickelt. Sie werden beispielsweise in CDs verwendet, können aber auch zur Fehlerkorrektur in Datenübertragungssystemen verwendet werden. Sie benutzen eine etwas allgemeinere Sichtweise als das CRC-Verfahren.

Bei Reed-Solomon werden nicht Bits sondern Zeichen betrachtet, die in der Regel aus einer Menge von 2n Elementen gewählt werden. Auf diesen Daten werden Addition und Multiplikation so definiert, dass es sich um einen endlichen algebraischen Körper handelt (GF(2n)=Gauß-Feld mit 2n Elementen). Seien r<2n Elemente als Datenwerte zu senden, die durch den Vektor x dargestellt werden. Diesen werden Kontrollzeichen hinzugefügt, so dass man den Zeichenvektor y erhält. Insgesamt lässt sich dieser Zusammenhang als lineares Gleichungssystem schreiben,

A*x=y

wobei A eine Matrix mit 2n Zeilen und r Spalten ist, x der Zeichenvektor der Länge r, und y der Codevektor der Länge 2n. Die ersten r Zeilen der Matrix A sind Einheitsvektoren, die restlichen sind von diesen linear unabhängige Vektoren, in der Regel Elemente aus der Vandermonde-Matrix. Damit sind die ersten r Elemente des Vektors y gleich jenen von x, während die restlichen die Kontrollinformation enthalten. Seien jetzt 2n-r Elemente von y fehlerhaft, so können die entsprechenden Zeilen  aus dem linearen Gleichungssystem gestrichen werden, das Gleichungssystem gelöst werden und x aus diesem Gleichungssystem berechnet werden. Damit lassen sich - wenn die Fehlerstellen bekannt sind - hieraus die korrekten Daten rekonstruieren.

Dieses Verfahren lässt sich z.B. für RAID-Systeme verwenden, bei denen mehrere Plattenlaufwerke parallel arbeiten und redundante Laufwerke hinzugefügt werden. Fallen ein oder mehrere Laufwerke aus, lassen sich die fehlerhaften Daten wieder restaurieren.

Um dieses Verfahren bei der Fehlerkorrektur einsetzen zu können, müssen die fehlerhaften Stellen bekannt sein. Dazu werden diese Stellen zunächst mit einem anderen Verfahren ermittelt, wozu allerdings einige Stellen benötigt werden. Daher können hiermit statt 2n-r nur (2n-r)/2 Zeichen rekonstruiert werden.

Das Reed-Solomon-Verfahren ist das optimale Blockkodierungsverfahren, welche jede vorgegebene Anzahl von Fehlern in einem Block korrigieren kann.

Viterbi-Kodierung

Eine weitere Klasse von Kodierungsverfahren wird als Konvolutionsverfahren bezeichnet. Hierbei werden aus übertragenen Daten neue Daten berechnet, wobei die Folge von gesendeten Daten verwendet wird um die nächsten zu berechnen. Durch diese innere Abhängigkeit können in einem bestimmten Umfang Daten korrigiert werden. Das Fehlerkorrekturverhalten wird als besser als das von Reed-Solomon angegeben.

Turbo-Kodierung

Eine weitere Entwicklung, die auf 1993 datiert wird, wird als Turbo-Kodierung bezeichnet. Hier werden parallele Konvolutionsverfahren eingesetzt, so dass eine bessere Kodierung erzielt wird. Gegenwärtig wird die Turbo-Kodierung bereits in einigen Systemen eingesetzt, vor allem in der Weltraumfahrt, da hier die Sendeleistung deutlich verringert werden kann.