In teoria dei codici, la distanza di Lee, che prende il nome da William Chi Yuan Lee, (in cinese 李始元) è una distanza fra due stringhe di uguale lunghezza sull'alfabeto -ario con , ossia due tuple e di .
Dato il peso
la metrica è definita come segue
Se o la distanza di Lee coincide con la distanza di Hamming, poiché entrambe danno 0 nel caso di due singoli simboli uguali e 1 con due singoli simboli diversi. Ciò non si verifica più per : in tal caso la distanza di Lee fra singoli simboli può superare 1. Comunque, esiste una "isometria di Gray" (una biiezione che preserva i pesi) fra considerando e con il peso di Hamming (numero di simboli diversi dal simbolo dell'alfabeto).
Considerando l'alfabeto come il gruppo additivo , la distanza di Lee fra due singoli simboli e è la lunghezza del cammino più breve fra di essi nel grafo di Cayley (circolare essendo il gruppo ciclico). Più in generale, la distanza di Lee fra due stringhe di lunghezza è la lunghezza del cammino più breve fra di esse nel grafo di Cayley di . Ciò può anche essere considerato come la metrica quoziente risultante dalla riduzione di con la distanza di Manhattan modulo il reticolo . L'analoga metrica quoziente su un quoziente di modulo un reticolo arbitrario è nota come metrica o distanza di Mannheim.
Lo spazio metrico indotto dalla distanza di Lee costituisce l'analogo discreto dello spazio ellittico.
Esempio Se , allora l'alfabeto è .
Date le stringhe e , la loro distanza di Lee è .
Note
Bibliografia
Categoria:Teoria dei codici Categoria:Metrica