AN codes are error-correcting code that are used in arithmetic applications.
Arithmetic codes were commonly used in computer processors to ensure the accuracy of its arithmetic operations when electronics were more unreliable. Arithmetic codes help the processor to detect when an error is made and correct it. Without these codes, processors would be unreliable since any errors would go undetected. AN codes are arithmetic codes that are named for the integers formula_1 and formula_2 that are used to encode and decode the codewords.
These codes differ from most other codes in that they use arithmetic weight to maximize the arithmetic distance between codewords as opposed to the hamming weight and hamming distance. The arithmetic distance between two words is a measure of the number of errors made while computing an arithmetic operation. Using the arithmetic distance is necessary since one error in an arithmetic operation can cause a large hamming distance between the received answer and the correct answer.
Arithmetic Weight and Distance.
The arithmetic weight of an integer formula_3 in base formula_4 is defined by
formula_5
where formula_6 ; formula_4, formula_8, and formula_9.
The arithmetic distance of a word is upper bounded by its hamming weight since any integer can be represented by its standard polynomial form of formula_10 where the formula_11 are the digits in the integer. Removing all the terms where formula_12 will simulate a formula_13 equal to its hamming weight. The arithmetic weight will usually be less than the hamming weight since the formula_14 are allowed to be negative. For example, the integer formula_15 which is formula_16 in binary has a hamming weight of formula_17. This is a quick upper bound on the arithmetic weight since formula_18. However, since the formula_14 can be negative, we can write formula_20 which makes the arithmetic weight equal to formula_21.
The arithmetic distance between two integers is defined by
formula_22
This is one of the primary metrics used when analyzing arithmetic codes.
AN Codes.
AN codes are defined by integers formula_1 and formula_24 and are used to encode integers from formula_25 to formula_26 such that
formula_27 ;formula_28
Each choice of formula_1 will result in a different code, while formula_24 serves as a limiting factor to ensure useful properties in the distance of the code. If formula_24 is too large, it could let a codeword with a very small arithmetic weight into the code which will degrade the distance of the entire code. To utilize these codes, before an arithmetic operation is performed on two integers, each integer is multiplied by formula_1. Let the result of the operation on the codewords be formula_33. Note that formula_33 must also be between formula_25 to formula_26 for proper decoding. To decode, simply divide formula_37. If formula_1 is not a factor of formula_33, then at least one error has occurred and the most likely solution will be the codeword with the least arithmetic distance from formula_33. As with codes using hamming distance, AN codes can correct up to formula_41 errors where formula_42 is the distance of the code.
For example, an AN code with formula_43, the operation of adding formula_44 and formula_45 will start by encoding both operands. This results in the operation formula_46. Then, to find the solution we divide formula_47. As long as formula_24 ;formula_49, this will be a possible operation under the code. Suppose an error occurs in each of the binary representation of the operands such that formula_50 and formula_51, then formula_52. Notice that since formula_53, the hamming weight between the received word and the correct solution is formula_54 after just formula_55 errors. To compute the arithmetic weight, we take formula_56 which can be represented as formula_57 or formula_58. In either case, the arithmetic distance is formula_55 as expected since this is the number of errors that were made. To correct this error, an algorithm would be used to compute the nearest codeword to the received word in terms of arithmetic distance. We will not describe the algorithms in detail.
To ensure that the distance of the code will not be too small, we will define modular AN codes. A modular AN code formula_60 is a subgroup of formula_61, where formula_62. The codes are measured in terms of modular distance which is defined in terms of a graph with vertices being the elements of formula_61. Two vertices formula_64 and formula_65 are connected iff
formula_66
where formula_67 and formula_68 ;formula_69 ;formula_70, formula_71. Then the modular distance between two words is the length of the shortest path between their nodes in the graph. The modular weight of a word is its distance from formula_25 which is equal to
formula_73
In practice, the value of formula_74 is typically chosen such that formula_75 since most computer arithmetic is computed formula_76 so there is no additional loss of data due to the code going out of bounds since the computer will also be out of bounds. Choosing formula_77 also tends to result in codes with larger distances than other codes.
By using modular weight with formula_77, the AN codes will be cyclic code.
definition: A cyclic AN code is a code formula_79 that is a subgroup of formula_80, where formula_81.
A cyclic AN code is a principal ideal of the ring formula_80. There are integers formula_1 and formula_24 where formula_85 and formula_86 satisfy the definition of an AN code. Cyclic AN codes are a subset of cyclic codes and have the same properties.
Mandelbaum-Barrows Codes.
The Mandelbaum-Barrows Codes are a type of cyclic AN codes introduced by D. Mandelbaum and J. T. Barrows.
 These codes are created by choosing formula_24 to be a prime number that does not divide formula_4 such that formula_89 is generated by formula_4 and formula_91, and formula_77. Let formula_93 be a positive integer where formula_94 and formula_95. For example, choosing formula_96, and formula_97 the result will be a Mandelbaum-Barrows Code such that formula_98 ;formula_99 in base formula_55.
To analyze the distance of the Mandelbaum-Barrows Codes, we will need the following theorem.
theorem: Let formula_101 be a cyclic AN code with generator formula_1, and
formula_103
Then,
formula_104
proof: Assume that each formula_105 has a unique cyclic NAF representation which is
formula_106
We define an formula_107 matrix with elements formula_108 where formula_109 and formula_110. This matrix is essentially a list of all the codewords in formula_79 where each column is a codeword. Since formula_79 is cyclic, each column of the matrix has the same number of zeros. We must now calculate formula_113, which is formula_93 times the number of codewords that don't end with a formula_25. As a property of being in cyclic NAF, formula_116 iff there is a formula_117 with formula_118 ;formula_119. Since formula_120 with formula_121 ;formula_24, then formula_123 ;formula_124. Then the number of integers that have a zero as their last bit are formula_125. Multiplying this by the formula_93 characters in the codewords gives us a sum of the weights of the codewords of formula_127 as desired.
We will now use the previous theorem to show that the Mandelbaum-Barrows Codes are equidistant (which means that every pair of codewords have the same distance), with a distance of
formula_128
proof: Let formula_129, then formula_120 and formula_2 is not divisible by formula_24. This implies there formula_133. Then formula_134. This proves that formula_79 is equidistant since all codewords have the same weight as formula_1. Since all codewords have the same weight, and by the previous theorem we know the total weight of all codewords, the distance of the code is found by dividing the total weight by the number of codewords (excluding 0).
References.
 ;templatestyles src="Reflist/styles.css" / ;