# Lee-code

Een Lee-code is een foutcorrigerende lineaire code die men kan beschouwen als een uitbreiding van de Hamming-code naar niet-binaire woorden. Lee-codes kunnen gebruikt worden in die gevallen waarin niet-binaire signalen worden verzonden of opgeslagen.

## Definities
### Lee-afstand

Voor twee woorden van gelijke lengte met symbolen uit $\{0,1,\ldots ,q-1\}$ is de Lee-afstand gedefinieerd. Twee woorden $x$ en $y$ van $n$ symbolen hebben de Lee-afstand:
    $d_{L}(x,y)=\sum _{i=1}^{n}\min(|x_{i}-y_{i}|,q-|x_{i}-y_{i}|)$
Deze metriek lijkt enigszins op de Manhattan-metriek.

### Lee-sfeer

De verzameling $F^{n}$ bestaat uit alle woorden van de lengte $n$ met symbolen uit het alfabet $F=\{0,1,\ldots ,q-1\}$.
De Lee-sfeer met straal $e$ rond een woord $x$ wordt gegeven door:
    $S_{L}(x,e)=\{y\in F^{n}|d_{L}(x,y)\leq e\}$
Dit is de verzameling van alle woorden met lengte $n$ waarvan de Lee-afstand tot $x$ niet meer bedraagt dan $e$ eenheden.
Lee-sferen hebben een meetkundige interpretatie. Voor bijvoorbeeld woorden met lengte 2 worden ze in het vlak voorgesteld door:
    voor $e=1$voor $e=2$ Lee-sfeer voor $n=2,e=1$Lee-sfeer $n=2,e=2$
enzovoort. Het woord $x$ bevindt zich in het midden van de figuur. De horizontale en verticale as komen overeen met de coördinaten $x_{1}$ en $x_{2}.$ De woorden op een Lee-afstand ten hoogste $e$ bevinden zich in het centrum van de vierkantjes die binnen de figuur gelegen zijn. Dus 13 woorden liggen op afstand 2 of minder van $x.$
In drie dimensies ($n=3$) worden de vierkantjes kubussen die rondom een centraal punt gestapeld zijn.
Het volume (aantal woorden) van een Lee-sfeer is:
    $\sum _{i=0}^{\min\{n,e\}}2^{i}{\binom {n}{i}}{\binom {e}{i}}$ voor $q\geq 3$

### Lee-code

Een deelverzameling $C\subset F^{n}$ is een e-foutencorrigerende Lee-code indien voor elk paar codewoorden $x,y\in C$ geldt dat hun Lee-sferen met straal $e$ disjunct zijn:
    $S_{L}(x,e)\cap S_{L}(y,e)=\varnothing \ \forall x,y\in C,x\neq y$
De woorden die binnen de $e$-sfeer van een codewoord uit $C$ liggen zijn "gedekt" door dat codewoord.

### Perfecte Lee-code

Het aantal codewoorden, dus het aantal codeerbare boodschappen, van een e-foutencorrigerende Lee-code is zo groot mogelijk wanneer de Lee-sferen van de codewoorden een dichte pakking hebben. Een Lee-code is perfect wanneer:
    $\bigcup _{x\in C}S_{L}(x,e)=F^{n}$
wat betekent dat de Lee-sferen met straal $e$ van de codewoorden met lengte $n$ de vectorruimte $F_{n}$ volledig opvullen of betegelen; ze vormen een partitie van die ruimte. Met andere woorden elk woord van lengte $n$ wordt gedekt door een uniek codewoord uit $C.$
Alleen als een dergelijke betegeling van $F_{n}$ met Lee-sferen met straal $e$ mogelijk is, bestaat er een perfecte Lee-code, genoteerd als $\mathrm {PL} (n,e).$ Er bestaan perfecte Lee-codes $\mathrm {PL} (n,1)$ voor elke $n\geq 1$ en $\mathrm {PL} (2,e)$ voor elke $e\geq 1.$ Er bestaat geen $\mathrm {PL} (2,3).$

## Vermoeden van Golomb en Welch

Golomb en Welch formuleerden het vermoeden dat er geen perfecte $e$-foutencorrigerende Lee-codes bestaan voor $n>2$ en $e>1.$ Het is nog niet in zijn algemeenheid bewezen, maar er zijn vele resultaten die het vermoeden bevestigen. Zo is onder meer bewezen dat er geen perfecte Lee-codes bestaan wanneer $q\geq 2e+1.$ Gravier et al. bewezen in 1998 dat er geen betegeling van de driedimensionele ruimte mogelijk is met Lee-sferen met een straal $e$ van 2 of meer. Dat bewijst het vermoeden van Golomb en Welch voor $n=3.$ Het vermoeden is nadien ook bewezen voor $n=4$ en $n=5.$
* 1 2 P. Horak. "Tilings in Lee metric." European Journal of Combinatorics (2009), vol. 30 nr. 2, blz. 480-489. DOI:10.1016/j.ejc.2008.04.007
* ↑ S.W. Golomb, L.R. Welsh. "Algebraic coding and the Lee metric" in Error Correcting Codes, Wiley, New York (1968), blz. 175–189
* ↑ K.A. Post. " Nonexistence theorems on perfect Lee codes over large alphabets." Information and Control (1975), vol. 29 nr. 4, blz. 369-380. DOI:10.1016/S0019-9958(75)80005-2
* ↑ P. Horak. "On perfect Lee codes." Discrete Mathematics (2009), vol. 309 nr. 18, blz. 5551-5561. DOI:10.1016/j.disc.2008.03.019