In
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
and
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 mathem ...
defined as
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 representat ...
(weight-preserving bijection) between
with the Lee weight and
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
and
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
. 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 set ...
induced by the Lee distance is a discrete analog of the
elliptic space
Elliptic geometry is an example of a geometry in which Euclid's parallel postulate does not hold. Instead, as in spherical geometry, there are no parallel lines since any two lines must intersect. However, unlike in spherical geometry, two lines a ...
.
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 while the Hamming distance is used in case of orthogonal modulation.
The
Berlekamp code
Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Contributors, ''IEEE Transactions on Information Theory'' 42, #3 (May 1996), p. 1048. DO10.1 ...
is an example of code in the Lee metric.
Other significant examples are the
Preparata code In coding theory, the Preparata codes form a class of non-linear double-error-correcting codes. They are named after Franco P. Preparata who first described them in 1968.
Although non-linear over GF(2) the Preparata codes are linear over Z4 with ...
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