A set of messages destined for transmission over a
communication channel
with noise with the property that the
"neighbourhood"
of
each message (that is, the set of most likely distorted versions
of this message) does not intersect with the neighbourhoods of other
messages. This property of an error-correcting code enables one to
correct
the errors (that is, to recover the
transmitted message) in those distorted messages (received at the output of
the channel) that belong to the neighbourhood of the message. Elements of
an error-correcting code (codewords) are employed in
the encoding of sequences of information symbols being
presented by the source of information (cf.
Information, source of).
The encoding consists in the representation of the information sequence
in a special form and in the introduction of additional information
(redundancy)
into it. This redundancy is usually introduced by appending to the
message extra symbols, by some means or other. For
example, the sequence of symbols may be divided into blocks of a fixed length
,
and, independently of one another, the blocks are
replaced by different blocks of greater length
,
which are elements of a so-called
error-correcting block code.
Other methods
[1]
are known for the introduction of redundancy
and the error-correcting codes related to them.
The codewords of an error-correcting block code are taken from a certain set of
-dimensional
vectors
endowed with a metric
,
and the neighbourhood of a codeword is a ball with
centre at the codeword. The radius of this ball defines the
correcting capacity of the block code.
The metric
depends on the nature of the errors for the
correction of which the code is intended. The subsequent account deals only with
block codes,
these being the most prevalent.
In order that it be possible to transmit the maximum amount of information
over the channel, it is necessary, for a
prescribed correcting capacity, to use codes with maximum number
of elements (codewords). The construction of such codes is one of
the basic problems in the theory of error-correcting codes. Sufficient progress
has been made with this problem only for certain finite sets
,
which are discussed below. Meanwhile, codes on certain
infinite spaces, for example, the sphere in Euclidean space
,
are of interest both in theory and in applications.
In the practical use of error-correcting codes there arise problems of mapping
the information to be transmitted into the set
of elements of the error-correcting code, and
of the determination of the transmitted element
of the code from the received element
.
The first problem is called the
problem of encoding,
the second the
problem of decoding.
The complexity of encoding and decoding is determined to
a large extent by the properties of the error-correcting code being used. As
a result, this leads to the study of a relatively
narrow class of codes such as, for example, the
binary linear codes
considered below.
The most widely investigated such codes are the
-ary block codes
in the
Hamming metric.
This is because they have found numerous applications, while the
methods for constructing them are related to well-known mathematical structures. The
words of these codes are certain elements of the set
consisting of all vectors of length
with coordinates belonging to a set of
elements. By the
Hamming distance
between two vectors
in
one means the number of positions
such that
.
The neighbourhood
of radius
(where
is an integer) of the vector
consists of all vectors in
differing from
in at most
coordinates, that is,
is the ball in the metric
of radius
with centre at
.
In particular,
consists of
vectors. For an arbitrary set
the function
is called the
minimum distance
of the
-ary
code
.
A code
is a
-error-correcting code
if
.
When the latter inequality holds, each neighbourhood
,
,
is disjoint with
for every other vector
in
.
Significant progress in the study of
-ary
codes has been made in case
is a power of a prime number. In this case the
set of coordinates is taken to be the finite field
of
elements, and the algebraic properties of this concept are used.
In what follows it is supposed that the elements of
are the coordinates of the elements of the set
.
The set
is a linear space over
.
If the vectors of the code
form a linear subspace of
,
then the code is said to be
linear.
A linear code
can be specified either by a basis of it or by a basis of the linear space dual to
.
The latter method is the most prevalent one. A matrix
whose rows form a basis for the vector space dual to
is called a
parity-check matrix
of
.
For all
,
,
where
is the transpose of
.
In what follows,
denotes the code length,
is the dimension of the linear code and
is the minimum distance. A code in
is called a
binary code.
In order to estimate the quality of specific
codes one studies the behaviour of the function
— the maximum number of vectors of a code of length
with minimum distance
.
The function
has been comparatively well studied for large
,
,
and for small
,
,
.
In the first case
is at most
when
,
and
when
;
in the second case it has order
when
.
If
,
,
then
.
A linear code for which this last equality is attained is called a
binary Hamming code.
A binary Hamming code (that corrects one error)
has the following property: The balls of radius
with centres at the points of the code are disjoint
but at the same time fill out the whole of
.
Such codes are called
perfect.
It is known that, apart from the Hamming codes and codes with
the same parameters, there is only one non-trivial binary perfect code.
In the case
,
,
,
the function
(the logarithmic asymptotic of
)
is studied. It is called the
information rate
for a maximal code with relative distance
.
Substantially distinct upper and lower bounds are known for
.
The lower bound (the
Varshamov–Gilbert bound)
has the form
where
and guarantees the existence of codes with the above parameters. The
proof of
(*)
is not constructive, for other bounds see
[6],
[7].
Next
constructive methods
(that is, methods that require a relatively small
number of operations for their realization) for making
error-correcting codes will be considered. The most important
constructive codes
are
Reed–Solomon codes
(RS-codes),
Bose–Choudhuri–Hocquenghem codes
(BCH-codes)
and
Reed–Muller codes
(RM-codes).
All these codes are linear. The starting point for
the construction of the first two is the matrix
with elements in
:
where
is a primitive root of
.
The matrix
is the parity-check matrix of the
-code
over
with the following parameters:
,
,
.
The distance of
is maximal among all linear codes of length
and dimension
.
The
binary BCH-code
consists of all vectors of the RS-code
in
whose vectors belong to
,
that is,
.
The BCH-code
with
has the following parameters:
,
,
.
The
Hamming code,
mentioned earlier, is the same as the BCH-code
.
If
(here
denotes the integer part of
),
then the dimension of
is equal to
.
A BCH-code is
cyclic,
that is, if a vector
belongs to it, then so do all its cyclic shifts. As
,
,
the number of vectors of BCH-codes is of the same
order as the cardinality of the best code; best with respect to
.
The
-th
order binary RM-code is defined as the set of binary vectors of the form
,
where
,
are all possible binary vectors of length
and
runs through the set of all functions of the
algebra of logic
that are represented by a polynomial over
in
binary variables and of degree not exceeding
.
An RM-code has the following parameters:
,
,
.
The
information rate
of a binary code
of length
with
vectors is defined as
If
is linear code of dimension
,
then
.
The information rates of the constructive codes listed above tend to zero as
,
,
.
Constructive codes are known with positive information rate as
,
,
,
but less than the information rates of codes whose
existence was established by the bound in
(*).
In the practical application of a
-error-correcting
code for the correction of errors on a communication channel, a device (a
decoder)
is required that determines the transmitted codeword from the distorted word
.
For this it is preferable to use error-correcting codes
for which the complexity of the decoder is not too large. By the
complexity of a decoder
of a binary code
with distance
one means, for example, the minimum number of functional
elements necessary for the realization of the Boolean operator
,
,
.
The constructive codes considered above have decoders
of small complexity. Moreover, other error-correcting codes are known
with information rate not tending to 0 as
,
,
,
and with a decoder of small complexity. Examples of such codes are cascade codes and
codes with low-density parity checks.
A
cascade code
consists, in the simplest case, of the iteration of an RS-code in the field
and a binary code of length
,
dimension
with distance
.
A one-to-one correspondence is established by means
of some linear mapping between the elements of
and the vectors of the binary code. The elements of the
RS-codes are then replaced by the corresponding vectors of the binary code.
As a result, a binary linear cascade code is obtained with parameters
,
,
.
The best results are obtained by the use of distant
binary codes for the replacement of distinct bits of
the RS-code. By this means, codes of length
can be obtained that correct a fixed segment of
errors using a decoder with complexity of order
.
An ensemble of
binary codes with low-density parity checks
is defined by the ensemble of parity-check matrices
consisting of binary matrices of a certain type, of dimension
,
that contain
and
units respectively in each column and row,
.
For fixed
and
and
,
a typical code of the ensemble of length
can correct a fixed segment of
errors by means of a decoder with complexity of order
.
The information rate both of cascades and codes with
low-density checks lies below the bound in
(*).
Codes on sets
with metrics differing from the Hamming metric have been
fairly widely investigated. The approaches and results of these investigations are,
by and large, similar to the corresponding results for the Hamming metric.
In particular, codes have been considered in
metrics connected with synchronous errors, with errors in
the arithmetic apparatus of computers
(arithmetic codes), with blocks of
errors, with asymmetric errors, and with errors in a continuous
communication channel. For example, in the latter case the set
is the unit sphere
in the Euclidean space
with centre at the origin, while a
"neighbourhood"
,
,
is the surface cut out from
by the circular cone with semi-angle
and axis passing through the points 0 and
.
It must also be pointed out that codes in
,
in a somewhat different interpretation, have been considered
in geometry since the end of the
19th century.
The development of the theory of error-correcting codes was stimulated by the work
of
C.E. Shannon
on information theory, in which
he showed the possibility, in principle, of transmitting over
a communication channel with noise with speed less than the channel
capacity and with arbitrarily small error. Initially the theory of error-correcting
codes satisfied the requirements of communications engineers in that
the mathematical constructions guaranteed reliable transmission
of information under certain restrictions on the number and
form of the errors in the information. Subsequently the results and
methods of the theory of error-correcting codes found application in other fields.
In particular, in mathematics, best estimates (up to
1978)
have obtained for the density of packing spheres
in Euclidean space; significant progress has been made in estimating
the complexity in typical disjunctive forms for almost-all Boolean functions;
some new objects in combinatorics have
been constructed; self-correcting diagrams of functional
elements have been constructed, etc.