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.

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

d L ( x , y ) = ∑ i = 1 n min ( | x i − y i | , q − | x i − y i | ) {\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 F n {\displaystyle F^{n}} bestaat uit alle woorden van de lengte n {\displaystyle n} met symbolen uit het alfabet F = { 0 , 1 , … , q − 1 } {\displaystyle F=\{0,1,\ldots ,q-1\}} .

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

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

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

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

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

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

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

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

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

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

S L ( x , e ) ∩ S L ( y , e ) = ∅   ∀ x , y ∈ C , x ≠ y {\displaystyle S_{L}(x,e)\cap S_{L}(y,e)=\varnothing \ \forall x,y\in C,x\neq y}

De woorden die binnen de e {\displaystyle e} -sfeer van een codewoord uit C {\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:

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

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

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

Golomb en Welch^[2] formuleerden het vermoeden dat er geen perfecte e {\displaystyle e} -foutencorrigerende Lee-codes bestaan voor n > 2 {\displaystyle n>2} en e > 1. {\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 q ≥ 2 e + 1. {\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 e {\displaystyle e} van 2 of meer. Dat bewijst het vermoeden van Golomb en Welch voor n = 3. {\displaystyle n=3.} Het vermoeden is nadien ook bewezen voor n = 4 {\displaystyle n=4} en n = 5. {\displaystyle n=5.} ^[1]