Difference between revisions of "Lee distance"
From Encyclopedia of Mathematics
(Start article: Lee distance) |
(→References: isbn link) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 3: | Line 3: | ||
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 | 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- | + | d_L (x,y) = \sum_{i=1}^n \min\left(|x_i-y_i|, m-|x_i-y_i|\right) \ . |
$$ | $$ | ||
| Line 12: | Line 12: | ||
====References==== | ====References==== | ||
| − | * Deza, Michel Marie; Deza, Elena ''Encyclopedia of distances'' (3rd ed.) Springer (2014) ISBN 978-3-662-44341-5 {{ZBL|1301.51001}} | + | * 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}} | + | * Roth, Ron ''Introduction to Coding Theory'', Cambridge University Press (2006) {{ISBN|0-521-84504-1}} {{DOI|10.1017/CBO9780511808968.011}} {{ZBL|1092.94001}} |
Latest revision as of 19:39, 17 November 2023
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
- 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
How to Cite This Entry:
Lee distance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lee_distance&oldid=38584
Lee distance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lee_distance&oldid=38584