Namespaces
Variants
Actions

Lee distance

From Encyclopedia of Mathematics
Revision as of 15:28, 11 April 2018 by Richard Pinch (talk | contribs) (typo)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


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_i|\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

How to Cite This Entry:
Lee distance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lee_distance&oldid=43120