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,\dots ,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,\dots ,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)\le 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(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{e}{i})$ voor $q\ge 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 \mathrm{\forall }x,y\in C,x\ne 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{P}\mathrm{L}(n,e).$ Er bestaan perfecte Lee-codes $\mathrm{P}\mathrm{L}(n,1)$ voor elke $n\ge 1$ en $\mathrm{P}\mathrm{L}(2,e)$ voor elke $e\ge 1.$ Er bestaat geen $\mathrm{P}\mathrm{L}(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\ge 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.$