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 Xk − 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,
Peterson15 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, 18
following the elegant description in Gemmell and Sudan. 3
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.