Code with correction of arithmetical errors
code for correction of arithmetic errors, code that corrects arithmetic errors, arithmetic code
A code intended for the control of the functioning of an adder. When adding numbers represented in the binary number system, a single slip in the functioning of the adder leads, as a rule, to a change in the result by some power of 2. In this connection, a (single) arithmetic error in the ring of integers is defined as a transformation of a number
to a number
,
. The function
on
, defined as the minimum number of arithmetic errors taking
to
, is a metric. An arbitrary finite subset (a code)
is characterized by its minimum distance
![]() |
where the minimum is taken over all distinct . The sets of
or fewer arithmetic errors transform a number
into a metric ball of radius
and centre
. Therefore if the metric balls of radius
described around any two numbers of a code do not intersect (that is, if the minimum distance of the code is greater than
), then the code is said to be a code that corrects
arithmetic errors. If the metric ball of radius
described around any number of the code contains no other numbers of the code (that is, if the minimum distance of the code is greater than
), then the code is called a code that detects
arithmetic errors. The metric
has the following alternative description:
![]() |
where is the (arithmetic) weight of
, i.e. the smallest possible number of non-zero coefficients in the representations
![]() | (*) |
For each there is a unique representation (*) on which
,
,
, and the number of non-zero coefficients in the representation is
. For example,
and
. Since
for any
, one restricts attention to codes that do not contain negative numbers. By the length of a code
one means the quantity
, where
is the largest number of the code
. There corresponds to an arbitrary number
of a code of length
a unique word
over the alphabet
such that
. If the code
corrects
arithmetic errors, then the code
corrects
errors (of substitution type) by virtue of the fact that
, where
is the Hamming metric (see Error-correcting code). In the study of problems of control of an adder one usually considers an encoding
(see Coding and decoding) such that
for
(which is equivalent to
, where
). In this case, the coding operation consists in the multiplication of the number to be encoded by
, while the detection of errors in the functioning of the adder consists in verifying that the result of the addition is divisible by
. The code
is called an
-code. The minimum distance of an
-code is the minimum of the
,
. For example, the minimum distance of a
-code is equal to 2; the code detects single arithmetic errors and is often applied in computers (in the form of a control modulo 3). The best studied are (cyclic and negacyclic)
-codes with
; they are characterized by the property that whenever the number
,
, belongs to the code, then so does the number
. Such codes, called
-codes, can be conveniently regarded as subsets of the metric space
, with metric
. The minimum distances of an
-code in the metrics
and
are equal. To each
-code there is associated the
-code where
; it is called the dual code. If 2 or
are primitive roots modulo a prime number
, then the
-code corrects single arithmetic errors and is perfect in the metric
, that is, the metric balls of radius 1 described around the numbers of the code are not only pairwise disjoint but also fill out the whole of
. In the dual code, all distances between different numbers of the code are equal to
. The results listed above for codes are analogues of results for binary linear cyclic error-correcting codes. Meanwhile, there are no known arithmetic analogues of B.C.H. (Bose–Chaudhury–Hocquenghem)-codes; nor are there any known upper bounds for the size of codes with given length and distance, analogous to the best bound for error-correcting codes. Codes correcting
-ary arithmetic errors
possess even more characteristics (a
-ary arithmetical error is a transformation of a number
to a number
,
;
). Interest in such codes has increased with the development of computing techniques. Thus, in contrast to error-correcting codes, there are no perfect
-codes with
(
) that correct single
-ary arithmetic errors; for
there are examples known of such codes. Existence conditions for perfect
-codes are of a number-theoretic character and are connected with the study of reciprocity laws in number fields.
References
[1] | Yu.G. Dadaev, "The theory of arithmetic codes" , Moscow (1981) (In Russian) |
[2] | E. Weldon jr., "Error-correcting codes" , M.I.T. (1972) |
[3] | J.L. Massey, O.N. Garcia, , Advances in information systems science , 4 , New York-London (1972) pp. 273–326 |
[4] | I.M. Boyarinov, G.A. Kabatyanskii, "Perfect single-error-correcting arithmetic ![]() |
Code with correction of arithmetical errors. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Code_with_correction_of_arithmetical_errors&oldid=17963