En la teoría de la codificación , el límite de 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 de bloque , Talla y distancia mínima . También se conoce como Joshibound . [1]
Declaración del obligado
La distancia mínima de un conjunto de palabras de código de longitud Se define como
dónde es la distancia de Hamming entre y . La expresion representa el número máximo de palabras de código posibles en un -código de bloque de longitud y distancia mínima .
Entonces el límite de Singleton establece que
Prueba
Primero observe que el número de -palabras de longitud es , ya que cada letra en una palabra así puede tomar una de valores diferentes, independientemente de las letras restantes.
Ahora deja ser arbitrario -código de bloque de la distancia mínima . Claramente, todas las palabras en claveson distintos. Si pinchamos el código eliminando el primer letras de cada palabra de código, entonces todas las palabras de código resultantes deben ser pares diferentes, ya que todas las palabras de código originales en tener distancia de Hamming al menosde cada uno. Por tanto, el tamaño del código alterado es el mismo que el del código original.
Las palabras de código recién obtenidas tienen una longitud
- ,
y así, puede haber como máximo de ellos. Desdeera arbitrario, este límite debe ser válido para el código más grande posible con estos parámetros, así: [2]
Códigos lineales
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 de Singleton implica:
- ,
así que eso
- ,
que generalmente se escribe como [3]
- .
En el caso del código lineal, se puede obtener una prueba diferente del límite de Singleton observando que el rango de la matriz de verificación de paridad es. [4] Otra prueba simple se deriva de observar que las filas de cualquier matriz generadora en forma estándar tienen un peso como máximo.
Historia
La cita habitual dada para este resultado es Singleton (1964) , pero según Welsh (1988 , p. 72) el resultado se puede encontrar en un artículo de 1953 de Komamiya. [5]
Códigos MDS
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 tienen sólo dos palabras de código (la palabra todo-cero y la palabra todo-uno, por lo que tienen una distancia mínima), códigos que utilizan la totalidad de (distancia mínima 1), códigos con un solo símbolo de paridad (distancia mínima 2) y sus códigos duales . Suelen denominarse códigos MDS triviales .
En el caso de los alfabetos binarios, solo existen códigos MDS triviales. [6] [7]
Ejemplos de códigos MDS no triviales incluyen códigos Reed-Solomon y sus versiones extendidas. [8] [9]
Los códigos MDS son una clase importante de códigos de bloque ya que, para un y , tienen las mayores capacidades de corrección y detección de errores. Hay varias formas de caracterizar los códigos MDS: [10]
- Teorema : Sea ser lineal [ ] codificar sobre . Los siguientes son equivalentes:
- es un código MDS.
- Alguna columnas de una matriz generadora parason linealmente independientes .
- Alguna columnas de una matriz de verificación de paridad para son linealmente independientes.
- es un código MDS.
- Si es una matriz generadora para en forma estándar, entonces cada submatriz cuadrada de no es singular .
- Dado cualquier posiciones de coordenadas, existe una palabra clave (peso mínimo) cuyo soporte son precisamente estas posiciones.
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. [11]
- Teorema : Sea ser lineal [ ] Código MDS sobre . Si denota el número de palabras de código en de peso , luego
Arcos en geometría proyectiva
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 . Dejarser el espacio proyectivo finito de dimensión (geométrica) sobre el campo finito . Dejarser un conjunto de puntos en este espacio proyectivo representados con coordenadas homogéneas . Forma el matriz cuyas columnas son las coordenadas homogéneas de estos puntos. Entonces, [12]
- Teorema : es un (espacial) -arc si y solo si es la matriz generadora de un Código MDS terminado .
Ver también
Notas
- ^ Keedwell, A. Donald; Dénes, József (24 de enero de 1991). Cuadrados latinos: nuevos desarrollos en la teoría y aplicaciones . Amsterdam: Elsevier. pag. 270. ISBN 0-444-88899-3.
- ^ Ling y Xing 2004 , p. 93
- ^ Roman 1992 , p. 175
- ^ Pless 1998 , p. 26
- ^ Komamiya, Y. (1953), "Aplicación de las matemáticas lógicas a la teoría de la información", Proc. 3º Japón. Nat. Cong. Apl. Matemáticas. : 437
- ^ Vermani 1996 , Proposición 9.2
- ^ Ling y Xing 2004 , p. 94 Observación 5.4.7
- ^ MacWilliams y Sloane 1977 , Cap. 11
- ^ Ling y Xing 2004 , p. 94
- ^ Roman 1992 , p. 237, Teorema 5.3.7
- ^ Roman 1992 , p. 240
- ^ Bruen, AA; Thas, JA; Blokhuis, A. (1988), "Sobre códigos MDS, arcos en PG (n, q), con q par, y solución de tres problemas fundamentales de B. Segre", Invent. Matemáticas. , 92 : 441–459, doi : 10.1007 / bf01393742
Referencias
- Ling, San; Xing, Chaoping (2004), Teoría de la codificación / Un primer curso , Cambridge University Press, ISBN 0-521-52923-9
- MacWilliams, FJ ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores , Holanda Septentrional, págs. 33, 37 , ISBN 0-444-85193-3
- Pless, Vera (1998), Introducción a la teoría de los códigos de corrección de errores (3a ed.), Wiley Interscience, ISBN 0-471-19047-0
- Roman, Steven (1992), Teoría de la información y la codificación , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
- Singleton, RC (1964), "Códigos q-nary de distancia máxima", IEEE Trans. Inf. Teoría , 10 (2): 116-118, doi : 10.1109 / TIT.1964.1053661
- Vermani, LR (1996), Elementos de la teoría de la codificación algebraica , Chapman & Hall
- Galés, Dominic (1988), Códigos y criptografía , Oxford University Press, ISBN 0-19-853287-3
Otras lecturas
- JH van Lint (1992). Introducción a la teoría de la codificación . GTM . 86 (2ª ed.). Springer-Verlag. pag. 61 . ISBN 3-540-54894-7.
- Niederreiter, Harald ; Xing, Chaoping (2001). "6. Aplicaciones a la teoría de la codificación algebraica". Puntos racionales en curvas sobre campos finitos. Teoría y Aplicaciones . Serie de notas de conferencias de la London Mathematical Society. 285 . Cambridge : Cambridge University Press . ISBN 0-521-66543-4. Zbl 0971.11033 .