Read Solomon Project(page3)

ICMS

Page:

IMPLEMENTING REED SOLOMON CODES

Encoding

Suppose a message consisting of k symbols (a_o, a₁, ... , a_k-1 ) is to be transmitted at a time. Then the encoding procedure is as follows:

1	From F choose a primitive element g (a generator of the multiplicative cyclic group of non-zero elements of the field F ).
2	Define the polynomial f(x) over the field F : f(x) = a_o + a₁x + a₂x² + ... + a_k-1x^k-1
3	Evaluate f(1), f(g), f(g²), f(g³), ..., f(g^n-1)
4	The encoded (and then transmitted) message is (f(1), f(g), f(g²), f(g³), &, f(g^n-1))

From a geometric point of view, what gets transmitted is not the polynomial f(x), but n points which lie on the graph of f(x). If errors occur during transmission, some of the points transmitted fail to lie on the graph of the polynomial. We know that k points are sufficient to determine any polynomial of degree k - 1. As n is larger than k, the transmitted points overdetermine the polynomial. This extra information allows us to recover the message even if some errors have occurred.

Error Decoding

When errors occur during transmission, the n points fail to lie on any polynomial of degree k - 1. The decoding process pulls these points back on to a polynomial of degree k - 1. There are several polynomials of this degree on which k of these n points lie. The Berlekamp algorithm finds the "correct" polynomial to fit the points in an efficient manner.

Erasure Decoding

As with any error correcting code, an RS code with minimum distance 2t +1, will accurately correct up to t errors. If on the other hand, the location of the errors is known, then 2t errors can be corrected accurately. Thus, burst errors of length 2t can be corrected if their location is known. Generally speaking, if the minimum distance in a Reed Solomon code is 2t +1, then one can correct a burst error of length b (i.e., b consecutive errors) and m errors where b +2m < 2t +1.

The Reed Solomon codes are now routinely used in devices that store or transmit digital information. They have been used in a big way to extract information from badly scratched CDs, Magnetic Tapes etc.