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.$

Bronnen, noten en/of referenties