Reed-Solomon Codes: A Tutorial and a Java Toolbox

Introduction to Coding Theory

A code is a set of messages, called codewords, that can be transmitted between two parties. One form that codewords can take is of bitstrings (i.e., strings of 0s and 1s), as in Reed-Muller and Hamming codes. A notable use of a Reed-Muller code was in the Mariner 9 space probe, which transmitted photographs of Mars (it remains in orbit around Mars to this day). The code had length 32 (that is, each codeword contained 32 bits) for which the number of codewords was 64. Before being transmitted, photographs were broken down into a collection of pixels. Each pixel was assigned one of 64 levels of grayness and then encoded as one of the 64 codewords. Mariner 9 used this code to transmit 7,329 black-and-white images of Mars, covering the entire planet.

Since transmissions from the probe had to travel such a long distance and were fairly weak, there was a marked potential for bit errors to occur during transmission. As a result, the code was useful only because bit errors could often be corrected after the bitstrings were received back at Earth. This was due to the fact that the code had a minimum distance of 16, that is, each codeword differed from each other codeword in at least 16 positions. Provided that no more than seven bit errors occurred, a received bitstringwasguaranteedto differ in fewer positionsfromthe sent codeword than fromany other codeword. The code is an example of an error-correcting code, specifically seven-error-correcting, since any seven or fewer bit errors in a codeword can be corrected.

The interplay among a code's length, number of codewords, minimum distance, and error-correction capability is a fundamental area of study in coding theory. Indeed, if the Reed-Muller code had been longer or had fewer codewords, then the minimum distance could have been greater and more bit errors could have been corrected. However, longer codewords would have taken more time to transmit (hence fewer photos could have been sent), and fewer codewords would have resulted in photographs less sharp, due to the fewer levels of grayness that could have been encoded.