Encuadernado singleton

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

En teoría de 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 de bloque , tamaño y distancia mínima . También se le conoce como Joshibound . ^[1] demostrado 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 ${\displaystyle C}$ ${\displaystyle n}$

$${\displaystyle d=\min _{\{x,y\in C:x\neq y\}}d(x,y)}$$

distancia de Hamming ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{q}(n,d)}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle d}$

Entonces el límite de 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 de dicha palabra puede tomar uno de diferentes valores, independientemente de las letras restantes. ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle q^{n}}$ ${\displaystyle q}$

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. ${\displaystyle C}$ ${\displaystyle q}$ ${\displaystyle d}$ ${\displaystyle c\in C}$ ${\displaystyle d-1}$ ${\displaystyle C}$ ${\displaystyle d}$

Cada una de las palabras clave recién obtenidas tiene una longitud

$${\displaystyle n-(d-1)=n-d+1,}$$

^[2] ${\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: ${\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,}$$

^[3]

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

Historia

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).

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 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 . ${\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]}

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] ${\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.
• Cualquier columna de una matriz generadora de es linealmente independiente . ${\displaystyle k}$ ${\displaystyle C}$
• Cualquier columna de una matriz de verificación de paridad es linealmente independiente. ${\displaystyle n-k}$ ${\displaystyle C}$
• ${\displaystyle C^{\perp }}$es un código MDS.
• Si es una matriz generadora de en forma estándar, entonces cada submatriz cuadrada de es no singular . ${\displaystyle G=(I|A)}$ ${\displaystyle C}$ ${\displaystyle A}$
• Dadas las posiciones de coordenadas, existe una palabra clave (de peso mínimo) cuyo soporte son precisamente estas posiciones. ${\displaystyle d}$

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 ${\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 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] ${\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 la matriz generadora de un código MDS está sobre . ${\displaystyle K}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle [m,N+1,m-N]}$ ${\displaystyle \mathbb {F} _{q}}$

Ver también

• Gilbert-Varshamov obligado
• Griesmer obligado
• Hamming atado
• Johnson obligado
• 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. pag. 270.ISBN​ 0-444-88899-3.
2. Ling y Xing 2004, pág. 93
3. Romano 1992, pag. 175
4. Pless 1998, pag. 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. Romano 1992, pag. 237, Teorema 5.3.7
10. Romano 1992, pag. 240
11. Bruen, AA; Eso, 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. Matemáticas. , 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 de 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", Proc. 3º Japón. Nat. Cong. Aplica. Matemáticas. : 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, Holanda Septentrional, págs. 33, 37, ISBN 0-444-85193-3
• Pless, Vera (1998), Introducción a la teoría de los códigos correctores de errores (3.ª ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Teoría de la información y codificación , GTM , vol. 134, Springer-Verlag, ISBN 0-387-97812-7
• Singleton, RC (1964), "Códigos q-narios 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
• Welsh, 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 . vol. 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 Sociedad Matemática de Londres. vol. 285. Cambridge : Prensa de la Universidad de Cambridge . ISBN 0-521-66543-4. Zbl  0971.11033.