Lee distance

In coding theory, the Lee distance is a distance between two strings $x\_1\; x\_2\; \backslash dots\; x\_n$ and $y\_1\; y\_2\; \backslash dots\; y\_n$ of equal length n over the q-ary alphabet {{math|{0, 1, …, q − 1}}} of size {{math|q ≥ 2}}. It is a metric defined as

$$\backslash sum\_\{i=1\}^n\; \backslash min(|x\_i\; -\; y\_i|,\backslash ,\; q\; -\; |x\_i\; -\; y\_i|).$$

If {{math|q {{=}} 2}} or {{math|q {{=}} 3}} the Lee distance coincides with the Hamming distance, because both distances are 0 for two single equal symbols and 1 for two single non-equal symbols. For {{math|q > 3}} this is not the case anymore; the Lee distance between single letters can become bigger than 1. However, there exists a Gray isometry (weight-preserving bijection) between $\backslash mathbb\{Z\}\_4$ with the Lee weight and $\backslash mathbb\{Z\}\_2^2$ with the Hamming weight.

Considering the alphabet as the additive group Z_q, the Lee distance between two single letters $x$ and $y$ is the length of shortest path in the Cayley graph (which is circular since the group is cyclic) between them.{{cite book |first=Richard E. |last=Blahut |author-link=Richard E. Blahut |title=Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach |url=https://archive.org/details/algebraiccodeson00blah_516 |url-access=limited |year=2008 |publisher=Cambridge University Press |isbn=978-1-139-46946-3 |page=[https://archive.org/details/algebraiccodeson00blah_516/page/n131 108] }} More generally, the Lee distance between two strings of length {{mvar|n}} is the length of the shortest path between them in the Cayley graph of $\backslash mathbf\{Z\}\_q^n$. This can also be thought of as the quotient metric resulting from reducing {{math|Zⁿ}} with the Manhattan distance modulo the lattice {{math|qZⁿ}}. The analogous quotient metric on a quotient of {{math|Zⁿ}} modulo an arbitrary lattice is known as a {{visible anchor|Mannheim metric}} or Mannheim distance.{{cite journal |author-first=Klaus |author-last=Huber |title=Codes over Gaussian Integers |journal=IEEE Transactions on Information Theory |volume=40 |number=1 |pages=207–216 |date=January 1994 |orig-date=1993-01-17, 1992-05-21 |doi=10.1109/18.272484 |id=IEEE Log ID 9215213. |s2cid=195866926 |issn=0018-9448 |eissn=1557-9654 |url=https://www.researchgate.net/publication/220036065 |access-date=2020-12-17 |url-status=live |archive-url=https://web.archive.org/web/20201217002024/https://www.researchgate.net/profile/Klaus_Huber/publication/220036065_Codes_over_Gaussian_Integers/links/0d1c84f564dae5d496000000/Codes-over-Gaussian-Integers.pdf |archive-date=2020-12-17}} [https://www.researchgate.net/publication/220036065_Codes_over_Gaussian_Integers][https://dl.acm.org/doi/10.1109/18.272484] (1+10 pages) (NB. This work was partially presented at CDS-92 Conference, Kaliningrad, Russia, on 1992-09-07 and at the IEEE Symposium on Information Theory, San Antonio, TX, USA.){{cite conference |title=Using Gray codes as Location Identifiers |author-first1=Thomas |author-last1=Strang |author-first2=Armin |author-last2=Dammann |author-first3=Matthias |author-last3=Röckl |author-first4=Simon |author-last4=Plass |work=6. GI/ITG KuVS Fachgespräch Ortsbezogene Anwendungen und Dienste |language=en, de |date=October 2009 |publisher=Institute of Communications and Navigation, German Aerospace Center (DLR) |publication-place=Oberpfaffenhofen, Germany |citeseerx=10.1.1.398.9164 |url=http://elib.dlr.de/60489/3/paper.pdf |access-date=2020-12-16 |url-status=live |archive-url=https://web.archive.org/web/20150501063457/http://elib.dlr.de/60489/3/paper.pdf |archive-date=2015-05-01}} (5/8 pages) [https://web.archive.org/web/20201216231728/https://elib.dlr.de/60489/2/Strang_Thomas.pdf]

• {{cite web |author=Thomas Strang |display-authors=etal |date=October 2009 |title=Using Gray codes as Location Identifiers |type=Abstract |website=ResearchGate |url=https://www.researchgate.net/publication/225003251}}

The metric space induced by the Lee distance is a discrete analog of the elliptic space.{{Citation |last1=Deza |first1=Elena |author1-link=Elena Deza|first2=Michel |last2=Deza |author2-link=Michel Deza |title=Dictionary of Distances |year=2014 |edition=3rd |publisher=Elsevier |isbn=9783662443422 |page=52 }}