AN codes are
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
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
and
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
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
and
hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
. 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
in base
is defined by
:
where
<
,
, and
. 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
where the
are the digits in the integer. Removing all the terms where
will simulate a
equal to its hamming weight. The arithmetic weight will usually be less than the hamming weight since the
are allowed to be negative. For example, the integer
which is
in binary has a hamming weight of
. This is a quick upper bound on the arithmetic weight since
. However, since the
can be negative, we can write
which makes the arithmetic weight equal to
.
The arithmetic distance between two integers is defined by
:
This is one of the primary metrics used when analyzing arithmetic codes.
AN Codes
AN codes are defined by integers
and
and are used to encode integers from
to
such that
:
Each choice of
will result in a different code, while
serves as a limiting factor to ensure useful properties in the distance of the code. If
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
. Let the result of the operation on the codewords be
. Note that
must also be between
to
for proper decoding. To decode, simply divide
. If
is not a factor of
, then at least one error has occurred and the most likely solution will be the codeword with the least arithmetic distance from
. As with codes using hamming distance, AN codes can correct up to
errors where
is the distance of the code.
For example, an AN code with
, the operation of adding
and
will start by encoding both operands. This results in the operation
. Then, to find the solution we divide
. As long as
>
, this will be a possible operation under the code. Suppose an error occurs in each of the binary representation of the operands such that
and
, then
. Notice that since
, the hamming weight between the received word and the correct solution is
after just
errors. To compute the arithmetic weight, we take
which can be represented as
or
. In either case, the arithmetic distance is
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
is a subgroup of
, where
. The codes are measured in terms of modular distance which is defined in terms of a graph with vertices being the elements of
. Two vertices
and
are connected iff
:
where
and
<
<
,
. 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
which is equal to
:
In practice, the value of
is typically chosen such that
since most computer arithmetic is computed
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
also tends to result in codes with larger distances than other codes.
By using modular weight with
, the AN codes will be
cyclic code
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detecti ...
.
definition: A cyclic AN code is a code
that is a subgroup of