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

Lee-sfeer

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

Lee-code

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.

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:

${\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]

Vermoeden van Golomb en Welch

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]