``A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems''

James S. Plank

Technical Report UT-CS-96-332, University of Tennessee, July, 1996.


This is a preliminary version submitted to ``Software, Practice & Experience.'' It was accepted and has been published with the following citation:

Software -- Practice & Experience, 27(9), September, 1997, pp. 995-1012.

Please cite that paper in preference to this technical report.


Important!!

The information dispersal matrix A given in this paper does not have the desired properties. Please see Technical Report CS-03-504 for a correction to this problem.

Available via anonymous ftp to cs.utk.edu in pub/plank/papers/CS-96-332.ps (and in PDF at CS-96-332.pdf).


Paper Errata

On page 8 of the tech report (1000 of the journal article), there is a typographical error. 3 / 7 should = 10, not 14.

Procedures for Reed-Solomon Coding

Please see http://web.eecs.utk.edu/~plank/plank/gflib/ for an implementation of Galois-Field arithmetic in GF(2^8) and GF(2^16), and for Reed-Solomon coding as described in this paper.

Abstract

It is well-known that Reed-Solomon codes may be used to provide error correction for multiple failures in RAID-like systems. The coding technique itself, however, is not as well-known. To the coding theorist, this technique is a straightforward extension to a basic coding paradigm and needs no special mention. However, to the systems programmer with no training in coding theory, the technique may be a mystery. Currently, there are no references that describe how to perform this coding that do not assume that the reader is already well-versed in algebra and coding theory.

This paper is intended for the systems programmer. It presents a complete specification of the coding algorithm plus details on how it may be implemented. This specification assumes no prior knowledge of algebra or coding theory. The goal of this paper is for a systems programmer to be able to implement Reed-Solomon coding for reliability in RAID-like systems without needing to consult any external references.

Postscript of the paper
PDF of the paper

Both of these have been updated as of February, 2003. However, please still see Tech Report CS-03-504 above for a correction to the information dispersal matrix problem.


Citation Information