Lee-code

Voor twee woorden van gelijke lengte met symbolen uit ${\displaystyle \{0,1,\ldots ,q-1\}}$  is de Lee-afstand gedefinieerd. Twee woorden ${\displaystyle x}$  en ${\displaystyle y}$  van ${\displaystyle n}$  symbolen hebben de Lee-afstand:

${\displaystyle 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.

De verzameling ${\displaystyle F^{n}}$  bestaat uit alle woorden van de lengte ${\displaystyle n}$  met symbolen uit het alfabet ${\displaystyle F=\{0,1,\ldots ,q-1\}}$ .

De Lee-sfeer met straal ${\displaystyle e}$  rond een woord ${\displaystyle x}$  wordt gegeven door:

${\displaystyle S_{L}(x,e)=\{y\in F^{n}|d_{L}(x,y)\leq e\}}$ 

Dit is de verzameling van alle woorden met lengte ${\displaystyle n}$  waarvan de Lee-afstand tot ${\displaystyle x}$  niet meer bedraagt dan ${\displaystyle e}$  eenheden.

Lee-sferen hebben een meetkundige interpretatie. Voor bijvoorbeeld woorden met lengte 2 worden ze in het vlak voorgesteld door:

voor ${\displaystyle e=1}$	voor ${\displaystyle e=2}$

enzovoort. Het woord ${\displaystyle x}$  bevindt zich in het midden van de figuur. De horizontale en verticale as komen overeen met de coördinaten ${\displaystyle x_{1}}$  en ${\displaystyle x_{2}.}$  De woorden op een Lee-afstand ten hoogste ${\displaystyle 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 ${\displaystyle x.}$ 

In drie dimensies (${\displaystyle n=3}$ ) worden de vierkantjes kubussen die rondom een centraal punt gestapeld zijn.

Het volume (aantal woorden) van een Lee-sfeer is:

${\displaystyle \sum _{i=0}^{\min\{n,e\}}2^{i}{\binom {n}{i}}{\binom {e}{i}}}$  voor ${\displaystyle q\geq 3}$ 

Een deelverzameling ${\displaystyle C\subset F^{n}}$  is een e-foutencorrigerende Lee-code indien voor elk paar codewoorden ${\displaystyle x,y\in C}$  geldt dat hun Lee-sferen met straal ${\displaystyle e}$  disjunct zijn:

${\displaystyle S_{L}(x,e)\cap S_{L}(y,e)=\varnothing \ \forall x,y\in C,x\neq y}$ 

De woorden die binnen de ${\displaystyle e}$ -sfeer van een codewoord uit ${\displaystyle C}$  liggen zijn "gedekt" door dat codewoord.

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:

${\displaystyle \bigcup _{x\in C}S_{L}(x,e)=F^{n}}$ 

wat betekent dat de Lee-sferen met straal ${\displaystyle e}$  van de codewoorden met lengte ${\displaystyle n}$  de vectorruimte ${\displaystyle F_{n}}$  volledig opvullen of betegelen; ze vormen een partitie van die ruimte. Met andere woorden elk woord van lengte ${\displaystyle n}$  wordt gedekt door een uniek codewoord uit ${\displaystyle C.}$ 

Alleen als een dergelijke betegeling van ${\displaystyle F_{n}}$  met Lee-sferen met straal ${\displaystyle e}$  mogelijk is, bestaat er een perfecte Lee-code, genoteerd als ${\displaystyle \mathrm {PL} (n,e).}$  Er bestaan perfecte Lee-codes ${\displaystyle \mathrm {PL} (n,1)}$  voor elke ${\displaystyle n\geq 1}$  en ${\displaystyle \mathrm {PL} (2,e)}$  voor elke ${\displaystyle e\geq 1.}$  Er bestaat geen ${\displaystyle \mathrm {PL} (2,3).}$ ^[1]

Golomb en Welch^[2] formuleerden het vermoeden dat er geen perfecte ${\displaystyle e}$ -foutencorrigerende Lee-codes bestaan voor ${\displaystyle n>2}$  en ${\displaystyle 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 ${\displaystyle q\geq 2e+1.}$ ^[3][4] Gravier et al. bewezen in 1998 dat er geen betegeling van de driedimensionele ruimte mogelijk is met Lee-sferen met een straal ${\displaystyle e}$  van 2 of meer. Dat bewijst het vermoeden van Golomb en Welch voor ${\displaystyle n=3.}$  Het vermoeden is nadien ook bewezen voor ${\displaystyle n=4}$  en ${\displaystyle n=5.}$ ^[1]