Fehlerkorrektur

Mit der Tendenz zu sehr großen Massenspeichersystemen wird die Notwendigkeit der Fehlerkorrektur immer größer. Da einerseits die Fehlerrate möglichst niedrig sein soll, um eine verlässliche Reaktion eines Systems zu bekommen, andererseits aber die Fehlerrate steigt, wenn man die Abstände zwischen den gespeicherten Bits erniedrigt (= höhere Speicherkapazität), ist es notwendig, nicht nur Fehlererkennung sondern auch Fehlerkorrektur zu betreiben.

Ein kurzes Beispiel möge eine Vorstellung vermitteln, welche Fehlerraten im täglichen Gebrauch von Massenspeichern noch akzeptabel sind. Angenommen man ist im Besitz eines Speichersystems, das 5 MBit pro Sekunde lesen und schreiben kann (also eine gewöhnliche Harddisk). Würde diese Harddisk ununterbrochen verwendet werden, so würde bei einer Fehlerrate von 10^-6 alle 0.2 Sekunden ein Fehler auftreten, bei einer Fehlerrate von 10^-9 alle 3 Minuten und bei einer Fehlerrate von 10^-12 alle 2 Tage. Erst eine Fehlerrate von 10^-14 gewährleistet einen fehlerfreien Betrieb von ca. 8 Monaten.

Im Gegensatz zur Fehlererkennung, die im einfachsten Fall mit Hilfe von Parity-Bits bewerkstelligt wird, können Fehlerkorrekturverfahren nicht nur Fehler erkennen, sondern diese auch bis zu einem bestimmten Maß korrigieren. Solche Fehlerkorrekturverfahren können die Fehlerrate eines Speichermediums um den Faktor 10³ bis 10¹⁰ (!) erniedrigen. Mit Hilfe dieser Verfahren kann man also eine Rohfehlerrate von z.B. 10^-9 auf eine nicht korrigierbare Fehlerrate von z.B. 10^-15 absenken.

Die ersten Fehlerkorrekturverfahren wurden um 1950 entwickelt (R.W. Hamming, M.J.E. Golay) und konnten zum Teil nur Einzelbitfehler korrigieren. Erst zehn Jahre später wurden Korrekturverfahren entwickelt, die auch mehrere Fehler, die womöglich noch nebeneinander liegen (Fehler-Burst), korrigieren können. Eines dieser Verfahren ist das Verfahren nach I.S. Reed und G. Solomon, das inzwischen eines der am meisten verwendeten Verfahren ist.

Um zu zeigen, wie Fehlerkorrekturverfahren im Prinzip arbeiten, sei wegen seiner Einfachheit im Folgenden kurz das Verfahren nach Hamming (Hamming-7/4-Code) beschrieben. Es kann Einzelbitfehler korrigieren und arbeitet nach folgendem Prinzip: Es werden jeweils vier Datenbits zu einer Einheit zusammengefasst und zu den vier Datenbits drei Prüfbits errechnet. Daten- und Prüfbits werden zusammen auf der Platte abgespeichert. Beim Lesen der Daten werden nun wieder die Prüfbits errechnet und mit den abgespeicherten Prüfbits verglichen. Aus dem Vergleich dieser Bits kann man erkennen, ob ein Bit falsch gelesen wurde, und welches Bit falsch ist.

Im Einzelnen funktioniert der Hamming-7/4-Code so: Angenommen es sind die Datenbits a, b, c und d gegeben, so werden die drei Prüfbits p1-p3 errechnet, indem man aus jeweils drei der Datenbits die Parität ermittelt:

            p1 := Par(a,b,c)
            p2 := Par(a,b,d)
            p3 := Par(a,c,d)

Die Datenbits a-d und die Prüfbits p1-p3 werden zusammen abgespeichert. Tritt nun ein Fehler beim Lesen auf, so kann dieser Fehler entweder in den Datenbits auf getreten sein oder in den Prüfbits. Man errechnet nun die Prüfbits aus den gelesenen Datenbits und vergleicht diese mit den gelesenen Prüfbits. Nach der folgenden Tabelle kann nun das fehlerhafte Bit ermittelt werden.

Der Hamming-Code kann keine Mehrbitfehler erkennen oder korrigieren. Da aber gerade bei magnetischen oder optischen Speichern Mehrbitfehler sehr häufig sind (z.B. ein Teil der Oberfläche beschädigt), ist diese Art der Fehlerkorrektur nur schlecht für diese Zwecke einsetzbar. Es wurden in der Folge jedoch Verfahren entwickelt, die es gestatten, auch aufeinander folgende Mehrbitfehler zu korrigieren. Eines dieser Verfahren ist das Reed-Solomon-Verfahren.

Die folgende Tabelle führt ein paar gebräuchliche Fehlerkorrekturverfahren an.