Cotas en Códigos Lineales

Principales cotas en teoría de códigos:

1. Cota de Singleton:
   Sea $C$ un $(n, M, d)$-código lineal sobre $\mathbb{F}_q$. Entonces, se cumple:

   $$d \leq n - k + 1,$$

   donde $k$ es la dimensión del código. Esta cota establece una relación fundamental entre los parámetros del código.

2. Cota de Hamming:
   Sea $C$ un $(n, M, d)$-código lineal sobre $\mathbb{F}_q$. Entonces, se cumple:

   $$sum = \sum_{i=0}^{t} \binom{n}{i}(q-1)^i \\ M \leq \frac{q^n}{sum}$$

   La cota de Hamming describe un límite superior para el tamaño del código, considerando las esferas de corrección de errores.

3. Cota de Gilbert-Varshamov:
   Sea $C$ un $(n, M, d)$-código lineal sobre $\mathbb{F}_q$. Entonces, se cumple:

   $$sum = \sum_{i=0}^{d-2} \binom{n}{i}(q-1)^i \\ M > \frac{q^n}{sum}$$

   Esta cota proporciona una estimación inferior para el tamaño del código, lo que la hace útil en el diseño de códigos eficientes.

Códigos perfectos:

Un código es perfecto si satisface con igualdad la cota de Hamming. En particular:

• Definición:
  Sea $C$ un $(n, M, d)$-código sobre $\mathbb{F}_q$, con $d \geq 2t + 1$. Decimos que $C$ es perfecto si:

  $$sum = \sum_{i=0}^{d-2} \binom{n}{i}(q-1)^i \\ M = \frac{q^n}{sum}$$

• Propiedades de los códigos perfectos:

  • Un código perfecto es aquel que utiliza todo el espacio disponible para la corrección de errores de forma óptima.
  • Ejemplos de códigos perfectos incluyen:
    • El espacio o código perfecto trivial: $\{(0, 0, 0, \dots, 0)\}$.
    • Los códigos binarios de repetición de longitud impar $n = 2t + 1$.
    • Los códigos de Hamming.

Información adicional:

Relación entre las cotas:

• Cota de Singleton es más general, pero menos estricta, y es aplicable a cualquier código lineal.
• Cota de Hamming tiene en cuenta la corrección de errores y se basa en las propiedades de las esferas.
• Cota de Gilbert-Varshamov proporciona un límite más práctico, especialmente útil para estimar el tamaño mínimo de códigos con una distancia mínima especificada.

Ejemplo práctico:

Considera un código binario de longitud $n = 7$ y distancia mínima $d = 3$:

• Aplicando la cota de Singleton: $$d \leq 7 - k + 1 \implies k \leq 5.$$
• Aplicando la cota de Hamming para $t = 1$: $$sum = \binom{7}{0} + \binom{7}{1} \cdot 1 \newline M \leq \frac{2^7}{sum} = \frac{128}{8} = 16.$$