title: Lee-code
text: 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  is de 
  Lee-afstand gedefinieerd. Twee woorden  en  van  symbolen hebben de Lee-afstand:
  
  Deze metriek lijkt enigszins op de Manhattan-metriek.
  
  Lee-sfeer
  De verzameling  bestaat uit alle woorden van de lengte  met symbolen uit het alfabet . 
  
  De Lee-sfeer met straal  rond een woord  wordt gegeven door:
  
  Dit is de verzameling van alle woorden met lengte  waarvan de Lee-afstand tot  niet meer bedraagt dan  eenheden.
  
  Lee-sferen hebben een meetkundige interpretatie. Voor bijvoorbeeld woorden met lengte 2 worden ze in het vlak voorgesteld door:
  
  {|class="wikitable"
  |-
  |voor ||voor 
  |-
  |  || 
  |}
  
  enzovoort. Het woord  bevindt zich in het midden van de figuur. De horizontale en verticale as komen overeen met de coördinaten  en  De woorden op een Lee-afstand ten hoogste  bevinden zich in het centrum van de vierkantjes die binnen de figuur gelegen zijn. Dus 13 woorden liggen op afstand 2 of minder van  
  
  In drie dimensies () worden de vierkantjes kubussen die rondom een centraal punt gestapeld zijn.
  
  Het volume (aantal woorden) van een Lee-sfeer is:
  
   voor
  
  Lee-code
  Een deelverzameling  is een e-foutencorrigerende Lee-code indien voor elk paar codewoorden  geldt dat hun Lee-sferen met straal  disjunct zijn:
  
  De woorden die binnen de -sfeer van een codewoord uit  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:
  
  wat betekent dat de Lee-sferen met straal  van de codewoorden met lengte  de vectorruimte  volledig opvullen of betegelen; ze vormen een partitie van die ruimte. Met andere woorden elk woord van lengte  wordt gedekt door een uniek codewoord uit 
  
  Alleen als een dergelijke betegeling van  met Lee-sferen met straal  mogelijk is, bestaat er een perfecte Lee-code, genoteerd als  Er bestaan perfecte Lee-codes  voor elke  en  voor elke  Er bestaat geen
  
  Vermoeden van Golomb en Welch
  Golomb en Welch formuleerden het vermoeden dat er geen perfecte -foutencorrigerende Lee-codes bestaan voor  en  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  Gravier et al. bewezen in 1998 dat er geen betegeling van de driedimensionele ruimte mogelijk is met Lee-sferen met een straal  van 2 of meer. Dat bewijst het vermoeden van Golomb en Welch voor  Het vermoeden is nadien ook bewezen voor  en 
  
  Discrete wiskunde
  Lineaire algebra
  Code