Difference between revisions of "Error-correcting code"
Ulf Rehmann (talk | contribs) m (MR/ZBL numbers added) |
(Category:Information and communication, circuits) |
||
Line 69: | Line 69: | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> J.H. van Lint, "Introduction to coding theory" , Springer (1982) {{MR|1540511}} {{ZBL|0485.94015}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> A. Tietäväinen, "On the existence of perfect codes over finite fields" ''SIAM J. Appl. Math.'' , '''24''' (1973) pp. 88–96</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> R.J. McEliece, E.R. Rodemich, H. Rumsey, L.R. Welch, "New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities" ''IEEE Trans. Inform. Theory'' , '''23''' (1977) pp. 157–166 {{MR|439403}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> M.A. Tsfasman, S.G. Vlăduts, T. Zink, "Modular curves, Shimuro curves and Goppa codes, better than Varshanov–Gilbert bound" ''Math. Nachr'' , '''109''' (1982) pp. 21–28</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) (Updated reprint) {{MR|0893813}} {{ZBL|0611.10017}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> R. Hill, "A first course in coding theory" , Clarendon Press (1986) {{MR|0853914}} {{ZBL|0616.94006}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> J.H. van Lint, G. van der Geer, "Introduction to coding theory and algebraic geometry" , Birkhäuser (1988) {{MR|}} {{ZBL|0648.94011}} {{ZBL|0639.00048}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> V.D. Goppa, "Geometry and codes" , Kluwer (1988) {{MR|1029027}} {{ZBL|1097.14502}} </TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> M.A. Tsfasman, S.G. Vlăduts, "Algebraic geometric codes" , Kluwer (1989) {{MR|1003354}} {{ZBL|0674.94012}} </TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> J.H. van Lint, "Introduction to coding theory" , Springer (1982) {{MR|1540511}} {{ZBL|0485.94015}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> A. Tietäväinen, "On the existence of perfect codes over finite fields" ''SIAM J. Appl. Math.'' , '''24''' (1973) pp. 88–96</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> R.J. McEliece, E.R. Rodemich, H. Rumsey, L.R. Welch, "New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities" ''IEEE Trans. Inform. Theory'' , '''23''' (1977) pp. 157–166 {{MR|439403}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> M.A. Tsfasman, S.G. Vlăduts, T. Zink, "Modular curves, Shimuro curves and Goppa codes, better than Varshanov–Gilbert bound" ''Math. Nachr'' , '''109''' (1982) pp. 21–28</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) (Updated reprint) {{MR|0893813}} {{ZBL|0611.10017}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> R. Hill, "A first course in coding theory" , Clarendon Press (1986) {{MR|0853914}} {{ZBL|0616.94006}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> J.H. van Lint, G. van der Geer, "Introduction to coding theory and algebraic geometry" , Birkhäuser (1988) {{MR|}} {{ZBL|0648.94011}} {{ZBL|0639.00048}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> V.D. Goppa, "Geometry and codes" , Kluwer (1988) {{MR|1029027}} {{ZBL|1097.14502}} </TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> M.A. Tsfasman, S.G. Vlăduts, "Algebraic geometric codes" , Kluwer (1989) {{MR|1003354}} {{ZBL|0674.94012}} </TD></TR></table> | ||
+ | |||
+ | [[Category:Information and communication, circuits]] |
Revision as of 21:42, 1 November 2014
code that corrects errors
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.
References
[1] | W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972) MR0347444 Zbl 0251.94007 |
[2] | E. Berlekamp, "Algebraic coding theory" , McGraw-Hill (1968) MR0238597 Zbl 0988.94521 |
[3] | F.J. MacWilliams, N.J.A. Sloane, "The theory of error correcting codes" , I-II , North-Holland (1977) |
[4] | E.L. Blokh, V.V. Zyablov, "Generalized cascade codes" , Moscow (1976) (In Russian) MR0607525 |
[5] | V.D. Kolesnik, E.T. Mironchikov, "The decoding of cyclic codes" , Moscow (1968) (In Russian) |
[6] | V.M. Sidel'nikov, "Extremal polynomials used in bounds of code volume" Probl. Inform. Transmission , 16 : 3 (1980) pp. 174–185 Probl. Peredach. Inform. , 16 : 3 (1980) pp. 17–30 Zbl 0468.94010 |
[7] | V.I. Levenshtein, "Minimum redundancy of error-correcting codes" Probl. Inform. Transmission , 10 : 2 (1974) pp. 110–123 Probl. Peredach. Inform. , 10 : 2 (1974) pp. 26–42 |
[8] | V.V. Zyablov, M.S. Pinsker, "Estimation of the error correcting complexity for Gallager low-density codes" Probl. Inform. Transmission , 11 : 1 (1975) pp. 18–28 Probl. Peredach. Inform. , 11 : 1 (1975) pp. 23–36 |
Comments
The linear space dual to a linear code is, of course, the space of all vectors
such that the scalar product
for all
. This dual space is denoted by
.
The best upper bound known for up till now (1987) is due to R.J. McEliece, E.R. Rodemich, H. Rumsey, and L.R. Welch (cf. [a3]).
See also Code; Code with correction of arithmetical errors; Code with correction of deletions and insertions; Coding, alphabetical; Coding and decoding.
As already indicated in the main article, coding theory is intimately related to other branches of mathematics, mainly the geometry of numbers (cf. also [a5]) and the theory of finite fields (cf. Finite field).
In 1982 M.A. Tsfasman, S.G. Vlăduts and T. Zink, using ideas of V.D. Goppa and algebraic geometry, constructed a sequence of codes that exceed the Gilbert–Varshamov bound [a4], thus also proving that , cf. (*), does not hold. Cf. Goppa code for more detail.
References
[a1] | J.H. van Lint, "Introduction to coding theory" , Springer (1982) MR1540511 Zbl 0485.94015 |
[a2] | A. Tietäväinen, "On the existence of perfect codes over finite fields" SIAM J. Appl. Math. , 24 (1973) pp. 88–96 |
[a3] | R.J. McEliece, E.R. Rodemich, H. Rumsey, L.R. Welch, "New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities" IEEE Trans. Inform. Theory , 23 (1977) pp. 157–166 MR439403 |
[a4] | M.A. Tsfasman, S.G. Vlăduts, T. Zink, "Modular curves, Shimuro curves and Goppa codes, better than Varshanov–Gilbert bound" Math. Nachr , 109 (1982) pp. 21–28 |
[a5] | P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) (Updated reprint) MR0893813 Zbl 0611.10017 |
[a6] | R. Hill, "A first course in coding theory" , Clarendon Press (1986) MR0853914 Zbl 0616.94006 |
[a7] | J.H. van Lint, G. van der Geer, "Introduction to coding theory and algebraic geometry" , Birkhäuser (1988) Zbl 0648.94011 Zbl 0639.00048 |
[a8] | V.D. Goppa, "Geometry and codes" , Kluwer (1988) MR1029027 Zbl 1097.14502 |
[a9] | M.A. Tsfasman, S.G. Vlăduts, "Algebraic geometric codes" , Kluwer (1989) MR1003354 Zbl 0674.94012 |
Error-correcting code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Error-correcting_code&oldid=34183