Distancia de Lee - Lee distance

En la teoría de la codificación , la distancia de Lee es una distancia entre dos cadenas y de igual longitud n sobre el alfabeto q -ary {0, 1,…,  q  - 1} de tamaño q  ≥ 2. ${\ Displaystyle x_ {1} x_ {2} \ dots x_ {n}}$${\ Displaystyle y_ {1} y_ {2} \ dots y_ {n}}$

Es una métrica , definida como

${\ Displaystyle \ sum _ {i = 1} ^ {n} \ min (| x_ {i} -y_ {i} |, \, q- | x_ {i} -y_ {i} |).}$

Considerando el alfabeto como el grupo aditivo Z _q , la distancia de Lee entre dos letras simples y es la longitud de la ruta más corta en el gráfico de Cayley (que es circular ya que el grupo es cíclico) entre ellas. ${\ Displaystyle x}$${\ Displaystyle y}$

Si o la distancia de Lee coincide con la distancia de Hamming , porque ambas distancias son 0 para dos símbolos iguales individuales y 1 para dos símbolos no iguales individuales. Dado que este ya no es el caso, la distancia de Lee puede ser mayor que 1. ${\ Displaystyle q = 2}$${\ Displaystyle q = 3}$${\ Displaystyle q> 3}$

El espacio métrico inducido por la distancia de Lee es un análogo discreto del espacio elíptico .

Ejemplo

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

Historia y aplicación

La distancia de Lee lleva el nombre de CY Lee . Se aplica para la modulación de fase, mientras que la distancia de Hamming se utiliza en caso de modulación ortogonal.

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

Además, existe una isometría de Gray (biyección que conserva el peso) entre el peso Lee y el peso Hamming . ${\ Displaystyle \ mathbb {Z} _ {4}}$${\ Displaystyle \ mathbb {Z} _ {2} ^ {2}}$

Referencias

• Lee, CY (1958), "Algunas propiedades de los códigos de corrección 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, José Felipe; Walker, Judy L. (1998). "Lee pesos de códigos 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 .