Lee distance explained

In coding theory, the Lee distance is a distance between two strings

x _{1} x _{2} ... x _{n} and y _{1} y _{2} ... y _{n} of equal length n over the q-ary alphabet of size . It is a metric defined as$$\backslash sum\_^n\; \backslash min(|x\_i\; -\; y\_i|,\backslash ,\; q\; -\; |x\_i\; -\; y\_i|).$$If or 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 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 Z _{4} with the Lee weight and 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.^[1] More generally, the Lee distance between two strings of length is the length of the shortest path between them in the Cayley graph of Z ^{n} _{q} . This can also be thought of as the quotient metric resulting from reducing with the Manhattan distance modulo the lattice . The analogous quotient metric on a quotient of modulo an arbitrary lattice is known as a or Mannheim distance.^{[2] [3]}

The metric space induced by the Lee distance is a discrete analog of the elliptic space.

Example

If, then the Lee distance between 3140 and 2543 is .

History and application

The Lee distance is named after William Chi Yuan Lee (Chinese: 李始元). It is applied for phase modulation while the Hamming distance is used in case of orthogonal modulation.

The Berlekamp code is an example of code in the Lee metric.^[4] Other significant examples are the Preparata code and Kerdock code; these codes are non-linear when considered over a field, but are linear over a ring.^[5]

References

• • • Book: Voloch, Jose Felipe . Vardy, Alexander . Alexander Vardy . Codes, Curves, and Signals: Common Threads in Communications . 1998 . Springer Science & Business Media . 978-1-4615-5121-8 . Lee Weights of Codes from Elliptic Curves . Judy L. . Walker .

Notes and References

1. Book: Blahut, Richard E. . Richard E. Blahut . Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach . limited . 2008 . Cambridge University Press . 978-1-139-46946-3 . 108 .
2. Klaus . Huber . Codes over Gaussian Integers . . 40 . 1 . 207–216 . January 1994 . 1993-01-17, 1992-05-21 . 10.1109/18.272484 . IEEE Log ID 9215213. . 195866926 . 0018-9448 . 1557-9654 . 2020-12-17 . live . 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 . 2020-12-17. https://www.researchgate.net/publication/220036065_Codes_over_Gaussian_Integershttps://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.)
3. Using Gray codes as Location Identifiers . Thomas . Strang . Armin . Dammann . Matthias . Röckl . Simon . Plass . 6. GI/ITG KuVS Fachgespräch Ortsbezogene Anwendungen und Dienste . en, de . October 2009 . Institute of Communications and Navigation, German Aerospace Center (DLR) . Oberpfaffenhofen, Germany . 10.1.1.398.9164 . 2020-12-16 . live . https://web.archive.org/web/20150501063457/http://elib.dlr.de/60489/3/paper.pdf . 2015-05-01. (5/8 pages) https://web.archive.org/web/20201216231728/https://elib.dlr.de/60489/2/Strang_Thomas.pdf
   • Web site: Thomas Strang . etal . October 2009 . Using Gray codes as Location Identifiers . Abstract . ResearchGate .
4. Book: Roth, Ron . Introduction to Coding Theory . limited . 2006 . . 978-0-521-84504-5 . 314.
5. Book: Sala . Massimiliano . Mora . Teo . Perret . Ludovic . Sakata . Shojiro . Traverso . Carlo . Gröbner Bases, Coding, and Cryptography . limited . 2009 . . 978-3-540-93806-4 . An Introduction to Ring-Linear Coding Theory . Marcus . Greferath . 220.