Idea of Reed-Solomon Codes

Recommended Reading

Despite the fact that this section is self-sufficient and explains all mathematical facts without referring to third-party sources, the desire to improve your knowledge is quite natural and can only be welcome. Therefore, it will be much better if you do not limit yourself to this book only and, instead, read a variety of specialized literature, each time noting the depth of the gap between your vague idea and a true understanding. The theory of error-correcting encoding is so vast that you could spend virtually your whole life studying it.

What are some starting points for this study?

• Blahut Richard Theory and Practice of Error Control Codes

  This is a very good book ”a must have . According to obscure rumors, it has been published somewhere on the Net. I, however, have been unable to find it. The large number of references to it, however, is evidence of its quality.

• James Plank A tutorial on Reed-Solomon Coding for fault-tolerance in RAID-like systems

A very good reference on the use of Reed-Solomon codes for building fault-tolerant systems similar to RAID, oriented towards programmers lacking fundamental math education and explaining clearly the idea of error-correcting encoding. It also provides source codes in C. An electronic copy is available at: http://www.cs.utk.edu/~plank/plank/papers/CS-96 “332.pdf. I strongly recommend that you read this manual, even if you are not going to create RAID systems.

• Joel Sylvester Reed-Solomon Codes

A very brief description of the Reed-Solomon codes working principles, supplied with flowcharts instead of the source code. It isn t a comprehensive manual, but it still provides an understanding of the general pattern. Available at: http://www.elektrobit.co.uk/pdf/reedsolomon.pdf

• Tom Moore REED-SOLOMONPACKAGE (old tutorial)

An excellent compendium of several manuals on Reed-Solomon codes ”probably the best that I ve ever seen. Includes a brief description of the theory of Galois fields, the basic principles of constructing Reed-Solomon coders/decoders, and complete listings illustrated their implementation in C ( unfortunately , very sparsely commented). This information was last posted in FIDO on 28.12.1994 in the comp.compression conference. It can be easily found using Google using the following keywords: Reed-Solomon+main+ECC . Strongly recommended.

• Ross N.Williams A painless guide to CRC error detection algorithms

A detailed manual on CRC. Very useful because of the easily readable, understandable description of the polynomial arithmetic, without which operation with Reed-Solomon codes would simply be impossible . You can find it at ftp://www.internode.net.au/ clients /rocksoft/papers/crc_v3.txt

• ftape (driver of the tape drive from the Linux distribution set)

No procedure of tape backup can do without error-correction codes! It s hard even to imagine. Therefore, this analysis of the source codes of the drivers for tape devices provides rich food for thought (provided, of course, that the driver being investigated actually uses the Reed-Solomon codes). The ftape Linux driver is the one you need. With regard to the code responsible for encoding/decoding Reed-Solomon codes, it is located in the ftape-ECC.c/ftape-ECC.h files. This is an example of good programming, so I recommend it.

• James S.Plank GFLIB C Procedures for Galois Field Arithmetic and Reed-Solomon Coding

A library for working with Reed-Solomon codes. Contains complete source codes of all required functions and is distributed according to GPL license. Can be found on any GNU site, including the following: http://www.cs.utk.edu/~plank/plank/gflib/gflib.tar.