User:Richard Pinch/sandbox-5

Lee distance

A metric on words over an alphabet $A = \{ a_1, \ldots, a_m \}$ where a single error is changing a letter one place in cyclic order. If the alphabet is identified with $\mathbf{Z}_m = \{0, \ldots, m-1 \}$ then the Lee distance between $x, y \in \mathbf{Z}_m^n$ is $$ d_L (x,y) = \sum_{i=1}^n \min\left(|x_i-y_i|, m-|x_i-y_y|\right) \ . $$

When $m=2$ or $m=3$, Lee distance coincides with Hamming distance. The Lee distance on $\mathbf{Z}_4$ corresponds to Hamming distance on $\mathbf{F}_2^2$ under the Gray map $$ 0 \mapsto 00 \ ,\ \ 1 \mapsto 01 \ ,\ \ 2 \mapsto 11 \ ,\ \ 3 \mapsto 10 \ . $$

References

• Deza, Michel Marie; Deza, Elena Encyclopedia of distances (3rd ed.) Springer (2014) ISBN 978-3-662-44341-5 Zbl 1301.51001
• Roth, Ron Introduction to Coding Theory, Cambridge University Press (2006) ISBN 0-521-84504-1 DOI 10.1017/CBO9780511808968.011 Zbl 1092.94001

Gray map

A map from $\mathbf{Z}_4$ to $\mathbf{F}_2^2$, extended in the obvious way to $\mathbf{Z}_4^n$ and $\mathbf{F}_2^n$ which maps Lee distance to Hamming distance. Explicitly, $$ 0 \mapsto 00 \ ,\ \ 1 \mapsto 01 \ ,\ \ 2 \mapsto 11 \ ,\ \ 3 \mapsto 10 \ . $$

The map instantiates a Gray code in dimension 2.