Equivalently, the encoding consists of the values of the poly-
nomial f (X) at n different points. Formally, if F is a finite
field with at least n elements, and S = (a , a ,...,a ) is a
12 n
sequence of n distinct elements, the RS encoding RS (m)

F, S, n, k of a message m = (m , m , . . . , m ) is given by

0 1 k− 1

RS (m)=(f(a),f(a),...,f(a)) F,s,n,k 12 3

the unique curve with equation Y − f (X) = 0 where degree( f ) < k that passes through all but e ≤ (n − k)/2 locations i, namely those in E. If there was no noise, fitting a curve through all n points is easy—it is just polynomial interpolation. We know Y − f (X) passes through n − e points, so we can get a curve that passes through all the points by fitting vertical lines through the error points along with the curve Y − f (X) = 0; see Figure 2. Algebraically, if we define

where f (X) = m + m X + . . . + m X^{k − 1}. We stress here that the

0 1 k− 1

choice of S is up to the code designer—we will exploit this feature in Section 3. 2.

The following basic algebraic fact will be crucial:

( 1)

A non-zero polynomial p(X) of degree D over a field F can have at most D distinct roots, i.e., at most D elements a Î F can satisfy p(a) = 0.

This fact implies that the encodings of two distinct messages m and m´ by RS must differ in more than n − k locations.^c

F, S, n, k

The minimum distance of the RS code is thus at least n − k + 1. It is in fact equal to n − k + 1: e.g., consider encodings of the messages corresponding to the zero polynomial and the polynomial . A minimum distance of (n − k + 1) is the best possible for a code of dimension k, making RS codes optimal in this regard.

then the curve P(X, Y) = 0 passes through all the points, i.e., P(a , y ) = 0 for every i. The second factor in the expression ( 1)

ii is called the error-locator polynomial, which has the error locations as its roots.

Given P(X, Y), one can find its factors (which can be done efficiently) and thus read off the message polynomial f (X) from the Y − f (X) factor. But how do we find P(X, Y)? Finding P(X, Y) in its factored form ( 1) is begging the question, but note that we can also write P(X, Y) in the form P(X, Y) = D (X)

1

Y − N (X) where degree(D ) ≤ e ≤ (n − k)/2 and degree(N ) < e 11 1

+ k ≤ (n + k)/2.

Knowing such a polynomial exists, we can try to find a non-zero bivariate polynomial Q(X, Y) = D (X)Y − N (X) satisfying

22

2. 1. correcting errors in Rs codewords

Why is the above large distance useful? If at most (n − k)/2 errors corrupt the evaluations of a polynomial f (X), then the encoding of f (X) remains the best fit of the corrupted data in terms of agreements than the encoding of any other polynomial g (X) of degree less than k. Thus, one can hope to recover f (X) and the correct message even in the presence of (n − k)/2 errors. However, it is not immediate how to isolate the errors and recover f (X) efficiently. We do not know the locations of the errors, and trying all possibilities will need exponential time.

Back in 1960, even before polynomial running time was formalized as the notion underlying efficient algorithms, Peterson¹⁵ described a polynomial time algorithm to solve the above problem. We now describe the high-level idea behind a different algorithm, due to Welch and Berlekamp, ¹⁸ following the elegant description in Gemmell and Sudan. ³

Assume that the encoding ( f (a ),…, f (a ) ) of a polynomial
1n
f (X) was transmitted, and we receive a corrupted version ( y ,
1
y ,. .. , y ), where the set E = {i : y ≠ f (a )} of error locations
2 n ii
has size at most (n − k)/2. Suppose we miraculously knew the
set E. Then we could simply discard the y ’s corresponding
i
to these locations, and interpolate f (X) through the rest of
the correct data points. We will have at least (n + k)/2 ≥ k loca-
tions, so interpolation will uniquely identify f (X).
error location via Bivariate interpolation: The key is thus a
clever method to locate the set E of error locations quickly.
To motivate this, let us cast the problem geometrically as an
equivalent noisy curve fitting problem. We are given n points
(a , y ), i = 1, 2, . . . , n, in the “plane” F × F. The goal is to find
ii

1. degree(D ) ≤ (n − k)/2 and degree (N ) < (n + k)/2

22

2. Q(a ,y ) = 0 fori = 1, 2, . . . ,n ii

This can be done by setting up a system of linear equations over F with unknowns being the coefficients of D (X) and

2

N (X), and n linear constraints Q(a , y ) = 0. We have called the

2 ii polynomial Q(X, Y) since we cannot assume that the solution will in fact equal P(X, Y) (there may be multiple nonzero solutions to the above system). Solving this linear system can certainly be done in polynomial time, and also admits fast, practical methods.

One can prove, using elementary algebra, that when the number of errors e ≤ (n − k)/2, any interpolated Q(X, Y) satisfying the above two conditions must have P(X, Y) as a factor,

figure 2: an Rs codeword (polynomial f(X) evaluated on points a ,

1

a , . .. , a ); its corruption by two errors (at locations a and a ); and 211 25 illustration of the curve fitting through the noisy data using correct curve and “error-locator lines.”

^c If not, RSF,S,n,k(m)−RSF,S,n,k(m´), which corresponds to the evaluation of the non-zero polynomial of degree at most k − 1, has at least k zeroes: a contradiction.