Lee-afstand

De Lee-afstand is een metriek die wordt toegepast in de coderingstheorie. Het is een maat voor de "afstand" tussen twee "woorden" van gelijke lengte uit een zeker "alfabet".

Definities

• het alfabet F bestaat uit q symbolen, waarbij q ≥ 2, waarvoor we de gehele getallen van 0 tot en met q-1 gebruiken; dus F = {0, 1, ..., q-1}.
• een woord x van lengte n is een n-tupel van symbolen uit het alfabet: x = (x₁, ..., x_n). Dit is dus een punt in de vectorruimte $F^{n}$ bestaande uit alle mogelijke woorden van lengte n.
• het (Lee-)gewicht van een woord x is de som:

$W_{L}(x)=\sum _{i=1}^{n}\min(x_{i},q-x_{i})$

• de (Lee-)afstand tussen twee woorden x en y van lengte n is dan:

$d_{L}(x,y)=W_{L}(x-y)=\sum _{i=1}^{n}\min(|x_{i}-y_{i}|,q-|x_{i}-y_{i}|).$

De Lee-afstand is genoemd naar de wiskundige C.Y. Lee. De Lee-afstand is verwant aan de Hammingafstand; deze is gedefinieerd voor binaire woorden en wordt gebruikt voor de binaire Hamming-code, terwijl de Lee-afstand is gedefinieerd voor niet-binaire foutencorrigerende codes, de Lee-codes. Wanneer q=2 valt de Lee-afstand samen met de Hammingafstand.

Voorbeeld

Stel q=6 en het alfabet is {0,1,2,3,4,5}. De woorden "32145" en "54123" hebben beide als Lee-gewicht 3+2+1+2+1=9. De Lee-afstand tussen beide is 2+2+0+2+2=8.

Bronnen, noten en/of referenties