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 -codes" Problemy Peredachi Informatsii , 12 : 1 (1976) pp. 16–23 (In Russian)