Distancia de Lee

En teoría de la codificación , la distancia de Lee es una distancia entre dos cadenas.${\displaystyle x_{1}x_{2}\dots x_{n}}$y${\ Displaystyle y_ {1} y_ {2} \ puntos y_ {n}}$de igual longitud n sobre el alfabeto q -ario {0, 1, …, q − 1 } de tamaño q ≥ 2 . Es una métrica ^{[ 1 ]} definida como $${\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).}$$ Si q = 2 o q = 3, la distancia de Lee coincide con la distancia de Hamming , porque ambas distancias son 0 para dos símbolos iguales y 1 para dos símbolos diferentes. Para q > 3, esto ya no es así; la distancia de Lee entre letras individuales puede ser mayor que 1. Sin embargo, existe una isometría de Gray (biyección que conserva el peso) entre${\displaystyle \mathbb {Z} _ {4}}$con el peso de Lee y${\displaystyle \mathbb {Z} _ {2}^{2}}$con el peso de Hamming . ^{[ 2 ]}

Considerando el alfabeto como el grupo aditivo Z _q , la distancia de Lee entre dos letras individuales${\displaystyle x}$y${\displaystyle y}$es la longitud del camino más corto en el grafo de Cayley (que es circular ya que el grupo es cíclico) entre ellos. ^{[ 3 ]} De manera más general, la distancia de Lee entre dos cadenas de longitud n es la longitud del camino más corto entre ellas en el grafo de Cayley de${\displaystyle \mathbf {Z} _ {q}^{n}}$Esto también puede pensarse como la métrica cociente resultante de reducir Z ⁿ con la distancia de Manhattan módulo la red q Z ⁿ . La métrica cociente análoga en un cociente de Z ⁿ módulo una red arbitraria se conoce comoMétrica de Mannheim odistancia de Mannheim. ^{[ 4 ] [ 5 ]}

El espacio métrico inducido por la distancia de Lee es un análogo discreto del espacio elíptico . ^{[ 1 ]}

Si q = 6 , entonces la distancia de Lee entre 3140 y 2543 es 1 + 2 + 0 + 3 = 6 .

La distancia de Lee recibe su nombre de William Chi Yuan Lee (李始元). Se aplica a la modulación de fase , mientras que la distancia de Hamming se utiliza en el caso de la modulación ortogonal.

El código de Berlekamp es un ejemplo de código en la métrica de Lee. ^{[ 6 ]} Otros ejemplos significativos son el código de Preparata y el código de Kerdock ; estos códigos son no lineales cuando se consideran sobre un cuerpo, pero son lineales sobre un anillo . ^{[ 2 ]}

• Lee, CY (1958), "Algunas propiedades de los códigos correctores de errores no binarios ", IRE Transactions on Information Theory , 4 (2): 77–82 , doi : 10.1109/TIT.1958.1057446
• Berlekamp, ​​Elwyn R. (1968), Teoría de la codificación algebraica , McGraw-Hill
• Voloch, Jose Felipe; Walker, Judy L. (1998). «Pesos de Lee de códigos a partir de curvas elípticas». En Vardy, Alexander (ed.). Códigos, curvas y señales: hilos comunes en las comunicaciones . Springer Science & Business Media. ISBN 978-1-4615-5121-8.