|
|
Reed-Solomon codes
Despite revolutionary
developments in capacity-approaching codes in recent years, Reed-Solomon
(RS) codes remain very relevant today, especially for high rate systems
with relatively small data packets. RS codes are straightforward to
decode and have excellent burst correction capability. But in addition
to their practical value in facilitating reliable communication over
noisy channels, Reed-Solomon codes are also beautiful and elegant and
almost endlessly fascinating in their own right. We will only provide a
brief introduction on this page, and the reader is strongly encouraged
to seek out more information, for instance
here,
here,
here,
and
here.
Before we describe the codes
themselves we will need to touch on some background material. A full
understanding of RS codes, however, requires a certain level of
mathematical maturity that is not possible to provide in a short
monograph.
Linear Block Codes
Reed-Solomon codes are
linear block codes. A block code is a way of mapping some number k of
symbols to another number n of symbols with n > k. We will call the
block of k symbols a messageword, and the block of n symbols a codeword.
The process of mapping k message symbols to n code symbols is called
encoding, and the reverse process is called decoding. This mapping can
be systematic, wherein the block of n codeword symbols consists of the k
messageword symbols plus (n-k) added redundant symbols, or
non-systematic, where the messageword symbols cannot be directly
recovered from the codeword without decoding. Generally, any linear
block code can be represented as an "equivalent" systematic code. A
block code is called "linear" if the sum of two codewords is always a
valid codeword, and a scalar multiple of any codeword is also a valid
codeword.
Codeword Symbols
So coding generally maps k
symbols to n symbols, but what do we mean by symbols? A binary code uses
two values, for example the binary numbers {0,1}, as symbols. In general, though, a code uses q-ary
symbols. Q-ary symbols, as the name suggests, use symbols taken from an
alphabet A of q possible values. So, for example, 3-ary symbols would be
symbols chosen from a set of three elements, such as {0, 1, 2}.
Practical RS codes use q = 256, which, it turns out, can be rather
conveniently represented using 8-bit symbols called bytes, familiar to
computer users. So a Reed-Solomon code of length n = 255 consists of 255
8-bit symbols per codeword, or 2040 binary bits.
Fields
The 8-bit symbols used in
practical RS codes are manipulated in the encoding process not as
ordinary binary numbers, but as elements of a mathematical structure
called a Finite Field, or Galois Field, in honor of their inventor, the
brilliant French mathematician Evariste Galois. Without getting too
caught up in the details, a field is a set of elements that can be
added, subtracted, multiplied, and divided, with the important
stipulation that the result of any of those operations is always still
an element of the field. Additionally, we require that additive and
multiplicative inverses and identity elements exist for each (non-zero)
element of the field, and that the field elements obey the familiar
commutative, associative, and distributive properties. The real numbers
are a familiar example of a field: we can add, subtract, multiply and
divide any two (non-zero) real numbers, and the result is always another
real number. Multiplicative and additive inverses can be found for any
real number; the multiplicative identity element is '1', the additive
identity element is '0'. The real numbers are an infinite field. We can
construct a field with a finite number of elements, if we follow certain
rules for constructing such fields.
Finite Fields, or Galois Fields
Let's choose, for example, the field
with 5 elements, and call the elements {0, 1, 2, 3, 4}. We will denote
this field GF(5), or the Galois field with 5 elements. Note that though
the elements of our finite field with 5 elements look like the ordinary
integers, they are not; this is simply a convenient notation. The most
important rule is that adding subtracting, multiplying and dividing any
two elements of the field always results in another element of the field
(i.e. the operation is "closed"). So what happens when we add, say, 3
and 4? Clearly the result can't be 7, because the only elements in our
field are {0, 1, 2, 3, 4}. One possible and intuitive solution is to use
modular arithmetic, that is, to do operations in the finite field with 5
elements using mod 5 arithmetic. One way to illustrate this is using the
division algorithm. The division algorithm is a way of representing a
number (the dividend) as a multiple of another number (the divisor),
plus some remainder. In our example, we divide 3 + 4 = 7 by 5, and take
the remainder: 7 = 5 x 1 + 2. The remainder (or "residue") is always less than 5, and
therefore is in our set {0, 1, 2, 3, 4}. So, using mod 5 arithmetic, on
our finite field, 3 + 4 = 2. We won't sweat the details here, but
suffice it to say that this method always works, and our set of five
elements is, in fact, a field if we conduct all our operations using mod
5 arithmetic. In fact, this construction method works for all finite
fields with a prime number of elements. So, for example, we could
construct a finite field with 23 elements {0, 1, 2, ..., 22} using
modulo 23 arithmetic. We can also construct finite fields with a power
of a prime number of elements (i.e. fields with order -- that is, number
of elements -- pm, for any prime p) using polynomial arithmetic modulo an irreducible polynomial. This is, in fact, the type of finite field used in practical
RS codes, namely, fields with 28 = 256 elements. These fields
can be constructed using an irreducible polynomial (whose coefficients
are taken from GF(2), i.e. are binary numbers) of degree 8. An
irreducible polynomial is to polynomial arithmetic what a prime number
is to integer arithmetic, it can't be factored evenly into the product
of two smaller polynomials, just as a prime number, by definition, can't
be factored into the product of two integers.
Polynomials
We can construct RS codes
using linear algebra alone, but for practical reasons it is customary to
add an additional structural constraint to our RS codes. We will map our
k message symbols to a polynomial of degree k - 1, and call the result
the message polynomial m(x) = mk-1xk-1 + mk-2xk-2
+ ... + m1x + m0. The n codeword symbols can be
mapped to a codeword polynomial of degree n - 1. c(x) = cn-1xn-1
+ cn-2xn-2 + ... + c1x + c0.
Cyclic codes
In addition to being linear
block codes, RS codes are cyclic codes. In simple terms, a code is
cyclic if, for every codeword of the form {c0, c1,
..., cn-1}, {cn-1, c0, c1,
..., cn-2} is also a codeword. That is, all circular shifts
of any codeword in the code are also codewords in the code. In
polynomial terms, if c(x) is a codeword, then x ∙ c(x) mod (xn
- 1) is also a codeword. In fact, it's easy to show that multiplication
of a cyclic codeword by xm results in a (right) circular
shift of the codeword m places. Since RS codes are also linear, we know
that the sum of two codewords is always a codeword, and multiplication
of a codeword by a scalar always results in a codeword, we can write
expressions like: an-1xn-1c(x) + an-2xn-2c(x)
+ ... + a0c(x) with the result always guaranteed to be a
codeword of the code if the code is a linear cyclic code. This leads to
the remarkable result that multiplying any codeword c(x) by any
polynomial a(x) (reducing the result modulo xn -1) results in
a valid codeword. In fact, we won't prove it here, but for any cyclic
code there exists exactly one irreducible polynomial of least degree,
called the generator polynomial of the code. The code then consists of
all polynomial multiples of the generator polynomial (i.e. the generator
polynomial can be used to "generate" the code). This fact is crucial to
the efficient construction of RS codes, because polynomial
multiplication is relatively easy to implement in hardware. Note that
all our polynomial coefficients are Galois field elements as defined
above, and hence all our arithmetic operations must be done using Galois
field arithmetic. Also note that straightforward multiplication of a
message m(x) by a generator polynomial to create a codeword, i.e. c(x) =
m(x) g(x), results in a non-systematic codeword. Most practical RS
codeword schemes use a systematic form, so it is customary to create a
codeword by multiplying the message by xn-k (which is
equivalent to shifting the message to the n-k highest coefficients in
the codeword polynomial), dividing the result by g(x) and adding to make
the systematic codeword. c(x) = xn-km(x) + Rg(x)[xn-km(x)],
where Rg(x)[∙] denotes the remainder that results
from dividing by g(x).
Defining
Reed-Solomon codes
So, now that we've provided
some rudimentary background, it's time to define Reed-Solomon codes
themselves. There are two common definitions of Reed-Solomon codes: as
polynomial codes over finite fields (construction 1), and as cyclic codes of length q-1
over GF(q) (construction 2). Other definitions are possible, for example those
involving orthogonal arrays, or the frequency domain construction, or as
a projective geometry over GF(q), but, in the interest of brevity, we
will concern ourselves with the two popular constructions outlined
above. We will maintain that these two definitions are not strictly
equivalent, though in the case of cyclic code constructions of length n
= q - 1 it is possible to show the equivalence of the two constructions.
Polynomial Codes over Certain Finite Fields (construction I)
This is the original
definition used by Irving S. Reed and Gustave Solomon in their landmark
1960 paper "Polynomial codes over certain finite fields" published in
the Journal of the Society for Industrial and Applied Mathematics. The
idea is this: given the message m(x) in the form of a polynomial, as
outlined above, whose k coefficients are taken from the finite field
GF(q), simply evaluate the polynomial
at n distinct elements of the finite field, to obtain the n coefficients
of the codeword. In other words, if we denote n distinct elements of the
field a0, a1, a2, ..., an-1,
then:
(c0, c1,
c2, ..., cn-1) = m(a0), m(a1),
m(a2), ..., m(an-1)
Although this construction
is certainly straightforward, it is generally not used in practice, due
to the lack of efficient methods for encoding and decoding. Also note
that this construction is not systematic, and that it yields codes of
length q if used over all the elements of the field GF(q), though often
the evaluation of the message at zero, m(0), is omitted, giving a code
of length n = q - 1.
A generalization of the
above construction leads to the definition of Generalized Reed-Solomon (GRS)
codes: let a0, a1, ..., an-1 be n
distinct elements of GF(q), and let v0, v1, ..., vn-1
be n non-zero (but not necessarily distinct) elements of GF(q), then the
GRSk(a, v) code consists of all vectors
(c0, c1,
c2, ..., cn-1) = v0m(a0), v1m(a1),
v2m(a2), ..., vn-1m(an-1).
It should be clear that if
the message has k symbols, and the length of the code = n = q - 1, then
the code consists of n equations in k unknowns, which is overspecified
when n > k. For instance, when n = 255, and k = 239, then there will be
255 equations, but only 239 unknown message coefficients, hence the
correct coefficients can be recovered even if some of them are
corrupted, giving the code its error correcting capability. We won't go
into exactly how that is done, but the general idea is to use polynomial
interpolation to derive a bivariate polynomial whose roots are the
coefficients of the message polynomial.
Generator
polynomial approach (construction II)
Recall, from our discussion
above, that a cyclic code can be completely specified as all polynomial
multiples of a generator polynomial. Then given the message m(x) in the
form of a polynomial, as outlined above, whose k coefficients are taken
from the finite field with q elements, we can construct RS codewords c(x)
= m(x) g(x) (or the equivalent systematic construction). All we need to
do is specify the generator polynomial of the code. We'll need a few
additional definitions first:
Powers of a field element
We form the powers of an
element of a Galois field in the usual way, namely a0 = 1, a1
= a, a2 = a∙a, a3 = a∙a∙a, etc.
Primitive element
In any Galois field there
exists one or more primitive elements. A primitive element is defined as
follows: Take any element of the field, and take successive powers of
the element, like so: a0 = 1, a, a2, a3,
... This gives a sequence of distinct field elements. The elements have
to repeat eventually, however, because there are only q distinct
elements in the finite field GF(q). It can easily be proven that the
first field element to repeat is, in fact, always 1. The smallest power
x of a given field element α, such that
αx
= 1, is called the order of
α.
If the order of a field element is q - 1, then the field element is
called a primitive element of the field. A primitive field element
α
can be used to "generate" all the elements of the field by taking
successive powers of α.
The general form of the generator polynomial
of a RS code is defined in such a way as to have as its roots 2t
consecutive powers of a primitive element
α.
Thus we can write,
g(x) = (x -
αb)(x
- αb+1)(x -
αb+2)...(x -
αb+2t-1)
For convenience, the
constant b is often chosen to be 0 or 1. Given the generator polynomial, RS codewords can now be
constructed as c(x) = m(x) g(x), or as c(x) = xn-km(x) + Rg(x)[xn-km(x)].
This is the method used most often in practice.
How RS
codes work
Now that we've covered the
construction of RS codes, let's look at how they work. The idea behind
error correction coding is to start with a "message" (i.e. the thing you
want to encode) of length k, and convert it to a "codeword" of longer
length n, in such a way that the additional information in the coded
form allows one to recover the original message if parts of it are
corrupted. To see how this works, we'll need some additional
definitions:
Hamming weight
The Hamming weight of a
codeword is simply the number of non-zero symbols in the codeword. So,
for example, if you had the following binary codeword: 1001010001, its
weight would be 4. This works the same way regardless of the field the
symbols come from. If you had the following codeword with symbols from
the field GF(5): 30104102, its weight would be 5.
Hamming distance
The Hamming distance between
two codewords in a code is the number of places in which the codewords
differ. So, for example, given the following two binary codewords:
100011 and 110000, the Hamming distance between them would be 3.
Minimum distance of a code
The minimum distance of a
code is the minimum distance between all the codewords in the code. In
other words, take the distance between each codeword in the code and
every other codeword in the code, and the smallest distance obtained
over all the comparisons is the minimum distance of the code.
Fortunately, for linear codes, there is a much easier way to find the
minimum distance. For linear codes, the minimum distance of a code is
the weight of the lowest weight codeword in the code.
The minimum distance of a
code is by far the most important property of the code in determining
the error correcting capability of the code. To see why this is, we need
to look more closely at the decoding process. Consider a simple binary
repetition code of length 4. A repetition code of length n, as the name
suggests, is a code where each codeword consists of n repetitions of a
single symbol. So there are two codewords in the binary repetition code
of length 4: (0000) and (1111). Clearly, the minimum distance of this
code is 4. Now suppose we send the message (1) as the codeword (1111)
across our communications channel. Clearly, if the first bit gets
corrupted in transmission, then we will receive the codeword as (0111).
In this case the (Hamming) distance between our received word and (1111)
is 1, and the distance between our received word and (0000) is 3. So a
reasonable decoding scheme would be that if the received word is not
(1111) or (0000), then choose as the decoded word the word that is
closest in Hamming distance to the received word. This is called nearest
neighbor decoding, and in our example clearly (0111) would be corrected
to (1111). Now consider the case where two bits are corrupted in
transmission. We send (1111), and the word received is (1010). Now we
can't recover the sent word, because the distance to both (1111) and
(0000) is 2. This is known as decoder failure. The decoder knows it has
received a corrupted codeword, but it isn't capable of correcting it.
Now consider that we sent (1111) and three bits are corrupted in
transmission and we receive (0001). In this case we will incorrectly
decode this word as (0000). This situation is known as decoder error.
This type of decoding can be
generalized to much larger and more sophisticated codes, but it very
quickly becomes impractical to compare a received codeword to all other
words in the code, and to choose the codeword that is the smallest
distance away from the received word. The important thing to observe,
however, is that for any code with a minimum distance d, we can always
correct up to [(d - 1)/2] errors, (here we are using square brackets []
to indicate the "floor" function, i.e. take the greatest integer less
than or equal to the expression in the brackets).
For an RS code with 2t
redundant "check" symbols, the minimum distance cannot exceed 2t + 1
(that is, dmin ≤
n - k + 1), because a message can exist with only one non-zero symbol.
This is referred to as the Singleton bound. Using construction I, we can
see that m(x), being of degree at most k - 1, cannot have more than k -
1 zeros. Thus c(x) can't have more than k - 1 zero positions (for a
non-zero codeword). This means that dmin
≥
n - (k - 1). Hence (since dmin
≤
n - k + 1 and dmin
≥
n - (k - 1)), for RS codes, dmin = n - k + 1 = 2t + 1. Codes
that have this distance property are called Maximum Distance Separable
(MDS) codes.
So an RS code with 2t check
symbols can correct up to [(2t + 1 - 1)/2] = t errors.
The foregoing is true for
all codes. So what makes RS codes so special? First, RS codes are MDS,
which has been proven to be the best minimum distance obtainable. Recall
that minimum distance is the most important property of an error
correction code. Secondly, because of their structure (they are linear,
cyclic, and their generator polynomial has well defined roots), RS codes
are easy to encode and relatively easy to decode.
References
1. Wicker, Bhargava, eds.,
"Reed-Solomon Codes And Their Applications", IEEE Press 1994
2. Wicker, "Error Control
Systems for Digital Communications and Storage", Prentice-Hall 1995
3. Lin and Costello, "Error
Control Coding: Fundamentals and Applications", Prentice-Hall 1983
4. Clark and Cain, "Error
Correction Coding for Digital Communications", Plenum 1988
|
