Límite singleton

Límite superior en la teoría de la codificación

En teoría de codificación , el límite Singleton , llamado así por Richard Collom Singleton, es un límite superior relativamente crudo del tamaño de un código de bloque arbitrario con longitud de bloque , tamaño y distancia mínima . También se lo conoce como límite Joshi . ^[1] Probado por Joshi (1958) e incluso antes por Komamiya (1953). ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle d}$

Declaración del obligado

La distancia mínima de un conjunto de palabras de código de longitud se define como donde es 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  . ${\displaystyle C}$ ${\displaystyle n}$ $${\displaystyle d=\min _{\{x,y\in C:x\neq y\}}d(x,y)}$$ ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{q}(n,d)}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle d}$

Entonces el límite Singleton establece que $${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$$

Prueba

Primero observe que el número de palabras -arias de longitud es , ya que cada letra en dicha palabra puede tomar uno de diferentes valores, independientemente de las letras restantes. ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle q^{n}}$ ${\displaystyle q}$

Sea ahora un código de bloque -ario arbitrario de distancia mínima . Claramente, todas las palabras de código 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 deben seguir siendo diferentes por pares, ya que todas las palabras de código originales en tienen una distancia de Hamming al menos entre sí. Por lo tanto, el tamaño del código alterado es el mismo que el código original. ${\displaystyle C}$ ${\displaystyle q}$ ${\displaystyle d}$ ${\displaystyle c\in C}$ ${\displaystyle d-1}$ ${\displaystyle C}$ ${\displaystyle d}$

Las palabras de código recién obtenidas tienen longitud y, por lo tanto, puede haber como máximo una de ellas. Como es arbitrario, este límite debe cumplirse para el código más grande posible con estos parámetros, por lo tanto: ^[2] $${\displaystyle n-(d-1)=n-d+1,}$$ ${\displaystyle q^{n-d+1}}$ ${\displaystyle C}$ $${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$$

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 Singleton implica: de modo que lo que usualmente se escribe como ^[3] ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle q}$ ${\displaystyle q^{k}}$ $${\displaystyle q^{k}\leq q^{n-d+1},}$$ $${\displaystyle k\leq n-d+1,}$$ $${\displaystyle d\leq n-k+1.}$$

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 deduce de la observación de que las filas de cualquier matriz generadora en forma estándar tienen un peso como máximo de . ${\displaystyle n-k}$ ${\displaystyle n-k+1}$

Historia

La referencia habitual para este resultado es Singleton (1964), pero Joshi (1958) lo demostró antes. Joshi señala que Komamiya (1953) había obtenido el mismo resultado utilizando una prueba más compleja. Welsh (1988, p. 72) también señala lo mismo con respecto a Komamiya (1953).

Códigos MDS

Los códigos de bloque lineales que logran la igualdad en el límite Singleton se denominan códigos MDS (distancia máxima separable) . Algunos ejemplos de estos códigos incluyen códigos que solo tienen palabras de código (la palabra completa para , que tiene, por lo tanto, 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 . Estos a menudo se denominan códigos MDS triviales . ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle x\in \mathbb {F} _{q}}$ ${\displaystyle n}$ ${\displaystyle (\mathbb {F} _{q})^{n}}$

En el caso de los alfabetos binarios, sólo existen códigos MDS triviales. ^{[5] [6]}

Entre los ejemplos de códigos MDS no triviales se 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 número fijo y , tienen las mayores capacidades de detección y corrección de errores. Existen varias formas de caracterizar los códigos MDS: ^[9] ${\displaystyle n}$ ${\displaystyle k}$

Teorema  —  Sea un código lineal [ ] sobre . Los siguientes son equivalentes: ${\displaystyle C}$ ${\displaystyle n,k,d}$ ${\displaystyle \mathbb {F} _{q}}$

• ${\displaystyle C}$es un código MDS.
• Todas las columnas de una matriz generadora para son linealmente independientes . ${\displaystyle k}$ ${\displaystyle C}$
• Todas las columnas de una matriz de comprobación de paridad son linealmente independientes. ${\displaystyle n-k}$ ${\displaystyle C}$
• ${\displaystyle C^{\perp }}$es un código MDS.
• Si es una matriz generadora para en forma estándar, entonces cada submatriz cuadrada de es no singular . ${\displaystyle G=(I|A)}$ ${\displaystyle C}$ ${\displaystyle A}$
• Dadas cualquier posición de coordenadas, existe una palabra de código (de peso mínimo) cuyo soporte son precisamente esas posiciones. ${\displaystyle d}$

La última de estas caracterizaciones permite, mediante el uso de las identidades de MacWilliams , una fórmula explícita para la distribución de peso completa de un código MDS. ^[10]

Teorema  :  Sea un código MDS lineal [ ] sobre . Si denota la cantidad de palabras de código en de peso , entonces ${\displaystyle C}$ ${\displaystyle n,k,d}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle A_{w}}$ ${\displaystyle C}$ ${\displaystyle w}$ $${\displaystyle A_{w}={\binom {n}{w}}\sum _{j=0}^{w-d}(-1)^{j}{\binom {w}{j}}(q^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{w-d}(-1)^{j}{\binom {w-1}{j}}q^{w-d-j}.}$$

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 . Sea el espacio proyectivo finito de dimensión (geométrica) sobre el cuerpo finito . Sea un conjunto de puntos en este espacio proyectivo representados con coordenadas homogéneas . Forme la matriz cuyas columnas sean las coordenadas homogéneas de estos puntos. Luego, ^[11] ${\displaystyle PG(N,q)}$ ${\displaystyle N}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle K=\{P_{1},P_{2},\dots ,P_{m}\}}$ ${\displaystyle (N+1)\times m}$ ${\displaystyle G}$

Teorema  —  es un arco (espacial) si y solo si es la matriz generadora de un código MDS sobre . ${\displaystyle K}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle [m,N+1,m-N]}$ ${\displaystyle \mathbb {F} _{q}}$

Véase también

• Límite Gilbert-Varshamov
• Griesmer atado
• Hamming atado
• Johnson se dirige hacia
• Plotkin atado

Notas

1. Keedwell, A. Donald; Dénes, József (24 de enero de 1991). Cuadrados latinos: nuevos desarrollos en la teoría y aplicaciones. Ámsterdam: Elsevier. p. 270. ISBN 0-444-88899-3.
2. Ling y Xing 2004, pág. 93
3. Romano 1992, pág. 175
4. Pless 1998, pág. 26
5. Vermani 1996, Proposición 9.2
6. Ling y Xing 2004, pág. 94 Observación 5.4.7
7. MacWilliams y Sloane 1977, cap. 11
8. Ling y Xing 2004, pág. 94
9. Roman 1992, pág. 237, Teorema 5.3.7
10. Romano 1992, pág. 240
11. Bruen, AA; Thas, JA; Blokhuis, A. (1988), "Sobre códigos MDS, arcos en PG(n,q), con q par, y una solución de tres problemas fundamentales de B. Segre", Invent. Math. , 92 (3): 441–459, Bibcode :1988InMat..92..441B, doi :10.1007/bf01393742, S2CID  120077696

Referencias

• Joshi, DD (1958), "Una nota sobre los límites superiores para los códigos de distancia mínima", Información y control , 1 (3): 289–295, doi : 10.1016/S0019-9958(58)80006-6
• Komamiya, Y. (1953), "Aplicación de las matemáticas lógicas a la teoría de la información", Actas del 3.º Congreso Nacional de Japón, Matemáticas Aplicadas : 437
• 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, North-Holland, 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 (3.ª ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Teoría de la codificación y la información , GTM , vol. 134, Springer-Verlag, ISBN 0-387-97812-7
• Singleton, RC (1964), "Códigos q-narios de máxima distancia", IEEE Trans. Inf. Theory , 10 (2): 116–118, doi :10.1109/TIT.1964.1053661
• Vermani, LR (1996), Elementos de la teoría de codificación algebraica , Chapman & Hall
• Welsh, Dominic (1988), Códigos y criptografía , Oxford University Press, ISBN 0-19-853287-3

Lectura adicional

• JH van Lint (1992). Introducción a la teoría de la codificación. GTM . Vol. 86 (2.ª ed.). Springer-Verlag. pág. 61. ISBN. 3-540-54894-7.
• Niederreiter, Harald ; Xing, Chaoping (2001). "6. Aplicaciones a la teoría de codificación algebraica". Puntos racionales en curvas sobre cuerpos finitos. Teoría y aplicaciones . Serie de notas de conferencias de la London Mathematical Society. Vol. 285. Cambridge : Cambridge University Press . ISBN 0-521-66543-4.Zbl 0971.11033  .