coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...

, the Lee distance is a

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

between two strings

x_1 x_2 \dots x_n

and

y_1 y_2 \dots y_n

of equal length ''n'' over the ''q''-ary

alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...

of size . It is a

metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathe ...

defined as

\sum_^n \min(, x_i - y_i, ,\, q - , x_i - y_i, ).

If or the Lee distance coincides with the

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 ...

, because both distances are 0 for two single equal symbols and 1 for two single non-equal symbols. For this is not the case anymore; the Lee distance between single letters can become bigger than 1. However, there exists a

Gray isometry The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...

(weight-preserving bijection) between

\mathbb_4

with the Lee weight and

\mathbb_2^2

with 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 ...

. Considering the alphabet as the additive group Z_''q'', the Lee distance between two single letters

x

and

y

is the length of shortest path in the

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

(which is circular since the group is cyclic) between them. More generally, the Lee distance between two strings of length is the length of the shortest path between them in the Cayley graph of

\mathbf_q^n

. This can also be thought of as the quotient metric resulting from reducing with the

Manhattan distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...

modulo the

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...

. The analogous quotient metric on a quotient of modulo an arbitrary lattice is known as a or Mannheim distance.
https://dl.acm.org/doi/10.1109/18.272484] (1+10 pages) (NB. This work was partially presented at CDS-92 Conference, Kaliningrad, Russia, on 1992-09-07 and at the IEEE Symposium on Information Theory, San Antonio, TX, USA.) (5/8 pages

* The

metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setti ...

induced by the Lee distance is a discrete analog of the elliptic space.

Example

If , then the Lee distance between 3140 and 2543 is .

History and application

The Lee distance is named after C. Y. Lee. It is applied for phase

modulation In electronics and telecommunications, modulation is the process of varying one or more properties of a periodic waveform, called the '' carrier signal'', with a separate signal called the ''modulation signal'' that typically contains informat ...

while the Hamming distance is used in case of orthogonal modulation. The Berlekamp code is an example of code in the Lee metric. Other significant examples are the Preparata code and Kerdock code; these codes are non-linear when considered over a field, but are linear over a ring.

References

* * * {{Strings Coding theory String metrics