Fehlerkorrektur im Slack Space unter Verwendung von Reed-Solomon Codes

Abstract

Mit den gängigen Methoden Daten zu speichern kann normalerweise nicht der gesamte zur Verfügung stehende Speicherplatz genutzt werden. Ungenutzte Bereiche die dennoch als beschrieben markiert sind, der so genannte Slack Space, kann und soll verwendet werden um Daten zu speichern. Doch damit ergeben sich Probleme, die den Einsatz von Fehlerkorrigierenden Codes notwendig machen. Reed-Solomon (RS) Codes scheinen sich hier besonders gut zu eignen, vor allem da Dank des Guruswami-Sudan (GS) Decodieralgorithmus eine Möglichkeit gegeben ist jenseits der Minimaldistanz zu korrigieren. Daher werden im Folgenden zuerst zwei Codierungs- und die dazu gehörenden Decodierungsmethoden (der Berlekamp-Massey (BM) und der GS Algorithmus) für RS Codes untersucht. Die Vorteile der systematischen Codierung mit Generatorpolynom sowie die Decodierung mittels GS Algorithmus werden herausgearbeitet und ein Algorithmus beschrieben um mit Generatorpolynom und GS Algorithmus speichereffizient arbeiten zu können. Vor allem die Parameter des GS Algorithmus werden sehr genau analysiert, da dieser auf Grund seines größeren Korrekturradius eine Reduktion des Speicherbedarfs ermöglicht. Mittels gängiger Methoden der Codierungstheorie, wie z.B. der Verkettung von Codes, können Daten beliebiger Größe gespeichert werden sofern genug Platz vorhanden ist. Analysiert und verglichen werden zum Abschluss drei verschiedene Varianten um Daten im Slack Space zu speichern.

When using conventional methods for saving data on electronic devices it is usually not possible to occupy the entire allocated disk space. Empty clusters that are nevertheless marked as allocated, the so called slack space, can and should be used for saving data. But using those clusters leads to problems which makes the use of error-correcting codes necessary. Reed-Solomon (RS) codes seem to fit very well, especially because of the Guruswami-Sudan (GS) decoding algorithm which offers a very good possibility for decoding beyond the minimum distance. In this diploma thesis we will first discuss two different methods of coding and their corresponding decoding algorithms (the Berlekamp-Massey (BM) and the GS algorithm) regarding RS codes. The advantages of systematic coding with generator polynomials and decoding using the GS algorithm will be reviewed and a memory-efficient algorithm using the generator polynomials and the GS algorithm will be described. The parameters of the GS decoding dlgorithm will be analysed in detail, because of it's ability to often correct beyond the d/2 limit, which allows memory-efficient saving of data. Using conventional methods of coding theory (e.g. code concatenation), data of any size can be saved as long as the slack space is big enough. In conclusion we will analyse and compare three different methods for saving data in slack space.