Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-5"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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

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.

How to Cite This Entry:
Richard Pinch/sandbox-5. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-5&oldid=38580