In [[coding theory]], the '''Lee distance''' is a [[distance]] between two [[String (computer science)|string]]s <math>x_1 x_2 \dots x_n</math> and <math>y_1 y_2 \dots y_n</math> of equal length ''n'' over the ''q''-ary [[alphabet]] {{math|{0, 1, …, ''q'' &minus; 1}}} of size {{math|''q'' ≥ 2}}. It is a [[Metric (mathematics)|metric]]<ref name="Deza" /> defined as <math display="block">\sum_{i=1}^n \min(|x_i - y_i|,\, q - |x_i - y_i|).</math> 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 <math>\mathbb{Z}_4</math> with the Lee weight and <math>\mathbb{Z}_2^2</math> with the [[Hamming weight]].<ref name="Greferath2009"/>

Considering the alphabet as the additive group [[modular arithmetic|'''Z'''<sub>''q''</sub>]], the Lee distance between two single letters <math>x</math> and <math>y</math> is the length of shortest path in the [[Cayley graph]] (which is circular since the group is cyclic) between them.<ref name="Blahut2008">{{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] }}</ref> 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 <math>\mathbf{Z}_q^n</math>. This can also be thought of as the [[metric space#Quotient metric spaces|quotient metric]] resulting from reducing {{math|'''Z'''<sup>''n''</sup>}} with the [[Manhattan distance]] modulo the [[lattice (discrete subgroup)|lattice]] {{math|''q'''''Z'''<sup>''n''</sup>}}. The analogous quotient metric on a quotient of {{math|'''Z'''<sup>''n''</sup>}} modulo an arbitrary lattice is known as a '''{{visible anchor|Mannheim metric}}''' or '''Mannheim distance'''.<ref name="Huber_1994">{{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<!-- February --> 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.)</ref><ref name="Strang-Dammann-Roeckl-Plass_2009">{{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<!-- also written as: Roeckl --> |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<!-- Institut für Kommunikation und Navigation -->, [[German Aerospace Center]]<!-- Deutsches Zentrum für Luft‐ und Raumfahrt e.V. --> (DLR) |publication-place=Oberpfaffenhofen, Germany |citeseerx=10.1.1.398.9164<!-- https://web.archive.org/web/20201216232905/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.398.9164&rep=rep1&type=pdf --> |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}}</ref>

The [[metric space]] induced by the Lee distance is a discrete analog of the [[Elliptic geometry|elliptic space]].<ref name="Deza">{{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 }}</ref>

==Example== If {{math|''q'' {{=}} 6}}, then the Lee distance between 3140 and 2543 is {{math|1 + 2 + 0 + 3 {{=}} 6}}.

==History and application== The Lee distance is named after William Chi Yuan Lee ({{lang|zh-CN|李始元}}). 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.<ref name="Roth2006">{{cite book |first=Ron |last=Roth |title=Introduction to Coding Theory |url=https://archive.org/details/introductiontoco00roth_028 |url-access=limited |date=2006 |publisher=[[Cambridge University Press]] |isbn=978-0-521-84504-5 |page=[https://archive.org/details/introductiontoco00roth_028/page/n325 314]}}</ref> Other significant examples are the [[Preparata code]] and [[Kerdock code]]; these codes are non-linear when considered over a field, but are [[ring-linear code|linear over a ring]].<ref name="Greferath2009">{{cite book |editor-last1=Sala |editor-first1=Massimiliano |editor-last2=Mora |editor-first2=Teo |editor-last3=Perret |editor-first3=Ludovic |editor-last4=Sakata |editor-first4=Shojiro |editor-last5=Traverso |editor-first5=Carlo |title=Gröbner Bases, Coding, and Cryptography |url=https://archive.org/details/grbnerbasescodin00sala |url-access=limited |year=2009 |publisher=[[Springer Science & Business Media]] |isbn=978-3-540-93806-4 |chapter=An Introduction to Ring-Linear Coding Theory |author-first=Marcus |author-last=Greferath |page=[https://archive.org/details/grbnerbasescodin00sala/page/n226 220]}}</ref>

==References== {{Reflist}} * {{Citation |first=C. Y. |last=Lee |title=Some properties of nonbinary [[error-correcting codes]] |journal=[[IEEE Transactions on Information Theory|IRE Transactions on Information Theory]] |volume=4 |year=1958 |pages=77–82 |issue=2 |doi=10.1109/TIT.1958.1057446 }} * {{Citation |first=Elwyn R. |last=Berlekamp |author-link=Elwyn Berlekamp |title=Algebraic Coding Theory |publisher=McGraw-Hill |year=1968}} * {{cite book |editor=Vardy, Alexander |editor-link=Alexander Vardy |title=Codes, Curves, and Signals: Common Threads in Communications |year=1998 |publisher=Springer Science & Business Media |isbn=978-1-4615-5121-8 |chapter=Lee Weights of Codes from Elliptic Curves |first=Jose Felipe |last=Voloch |first2=Judy L. |last2=Walker }}

{{Strings}}

[[Category:Coding theory]] [[Category:String metrics]]