En la teoría de la codificación , el límite Singleton , que lleva el nombre de Richard Collom Singleton, es un límite superior relativamente burdo del tamaño de un código de bloque arbitrario con longitud , tamaño y distancia mínima del bloque . También se le conoce como Joshibound . [1] demostrado por Joshi (1958) e incluso antes por Komamiya (1953).
La distancia mínima de un conjunto de palabras en código de longitud se define como dónde está la distancia de Hamming entre y . La expresión representa el número máximo de palabras de código posibles en un código de bloque ario de longitud y distancia mínima .
Entonces el límite de Singleton establece que
Primero observe que el número de palabras -arias de longitud es , ya que cada letra de dicha palabra puede tomar uno de diferentes valores, independientemente de las letras restantes.
Ahora sea un código de bloque arbitrario de distancia mínima . Claramente, todas las palabras en clave son distintas. Si perforamos el código eliminando las primeras letras de cada palabra de código, entonces todas las palabras de código resultantes aún deben ser diferentes por pares, ya que todas las palabras de código originales tienen una distancia de Hamming al menos entre sí. Por tanto, el tamaño del código modificado es el mismo que el del código original.
Cada una de las palabras en clave recién obtenidas tiene longitud y, por lo tanto, puede haber como máximo . Como era arbitrario, este límite debe ser válido para el código más grande posible con estos parámetros, por lo tanto: [2]
Si es un código lineal con longitud de bloque , dimensión y distancia mínima sobre el campo finito con elementos, entonces el número máximo de palabras de código es y el límite Singleton implica: lo que generalmente se escribe como [3]
En el caso del código lineal, se puede obtener una prueba diferente del límite Singleton observando que el rango de la matriz de verificación de paridad es . [4] Otra prueba simple se desprende de la observación de que las filas de cualquier matriz generadora en forma estándar tienen peso como máximo .
La cita habitual para este resultado es Singleton (1964), pero Joshi (1958) lo demostró anteriormente. Joshi señala que Komamiya (1953) obtuvo el resultado anteriormente utilizando una prueba más compleja. Welsh (1988, p. 72) también señala lo mismo respecto de Komamiya (1953).
Los códigos de bloque lineal que logran la igualdad en el límite Singleton se denominan códigos MDS (distancia máxima separable) . Ejemplos de tales códigos incluyen códigos que solo tienen palabras de código (la palabra completa para , por lo que tiene una distancia mínima ), códigos que usan el conjunto de (distancia mínima 1), códigos con un solo símbolo de paridad (distancia mínima 2) y sus códigos duales. . A menudo se les llama códigos MDS triviales .
En el caso de los alfabetos binarios, sólo existen códigos MDS triviales. [5] [6]
Ejemplos de códigos MDS no triviales incluyen los códigos Reed-Solomon y sus versiones extendidas. [7] [8]
Los códigos MDS son una clase importante de códigos de bloque ya que, para un tiempo fijo y , tienen las mayores capacidades de detección y corrección de errores. Hay varias formas de caracterizar los códigos MDS: [9]
Teorema : sea un código lineal [ ] sobre . Los siguientes son equivalentes:
La última de estas caracterizaciones permite, utilizando las identidades de MacWilliams , una fórmula explícita para la distribución completa del peso de un código MDS. [10]
Teorema : sea un código MDS lineal [ ] sobre . Si denota el número de palabras de código en peso , entonces
La independencia lineal de las columnas de una matriz generadora de un código MDS permite la construcción de códigos MDS a partir de objetos en geometría proyectiva finita . Sea el espacio proyectivo finito de dimensión (geométrica) sobre el campo finito . Sea un conjunto de puntos de este espacio proyectivo representados con coordenadas homogéneas . Forme la matriz cuyas columnas sean las coordenadas homogéneas de estos puntos. Entonces, [11]