Lee distance

In coding theory, the Lee distance is a distance between two strings ${\displaystyle x_{1}x_{2}\dots x_{n}}$ and ${\displaystyle y_{1}y_{2}\dots y_{n}}$ of equal length n over the q-ary alphabet {0, 1, …, q − 1} of size q ≥ 2. It is a metric[1] defined as

$${\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).}$$

If q = 2 or q = 3 the Lee distance coincides with the Hamming distance, because both distances are 0 for two single equal symbols and 1 for two single non-equal symbols. For q > 3 this is not the case anymore; the Lee distance between single letters can become bigger than 1. However, there exists a Gray isometry (weight-preserving bijection) between ${\displaystyle \mathbb {Z} _{4}}$ with the Lee weight and ${\displaystyle \mathbb {Z} _{2}^{2}}$ with the Hamming weight.[2]

Considering the alphabet as the additive group Z_q, the Lee distance between two single letters ${\displaystyle x}$ and ${\displaystyle y}$ is the length of shortest path in the Cayley graph (which is circular since the group is cyclic) between them.[3] More generally, the Lee distance between two strings of length n is the length of the shortest path between them in the Cayley graph of ${\displaystyle \mathbf {Z} _{q}^{n}}$. This can also be thought of as the quotient metric resulting from reducing Zⁿ with the Manhattan distance modulo the lattice qZⁿ. The analogous quotient metric on a quotient of Zⁿ modulo an arbitrary lattice is known as a Mannheim metric or Mannheim distance.[4][5]

The metric space induced by the Lee distance is a discrete analog of the elliptic space.[1]