Difference between revisions of "User:Richard Pinch/sandbox-5"
(Start article: Lee distance) |
(Start article: Gray map) |
||
| Line 5: | Line 5: | ||
$$ | $$ | ||
| − | When $m=2$ or $m=3$, Lee distance coincides with [[Hamming distance]]. | + | 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==== | ====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}} | ||
| + | |||
| + | =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. | ||
Revision as of 17:29, 17 April 2016
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.
Richard Pinch/sandbox-5. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-5&oldid=38579