Límite Gilbert-Varshamov

En teoría de codificación , el límite de Gilbert–Varshamov (debido a Edgar Gilbert ^[1] e independientemente a Rom Varshamov ^[2] ) es un límite del tamaño de un código (no necesariamente lineal ) . A veces se lo conoce como límite de Gilbert– Shannon –Varshamov (o límite GSV ), pero el nombre "límite de Gilbert–Varshamov" es, con diferencia, el más popular. Varshamov demostró este límite utilizando el método probabilístico para códigos lineales. Para obtener más información sobre esa prueba, consulte Límite de Gilbert–Varshamov para códigos lineales .

Declaración del obligado

Recuerde que un código tiene una distancia mínima si dos elementos cualesquiera en el código están separados por al menos una distancia. ${\displaystyle d}$ ${\displaystyle d}$

${\displaystyle A_{q}(n,d)}$

denota el tamaño máximo posible de un código q -ario con longitud n y distancia de Hamming mínima d (un código q -ario es un código sobre el campo de q elementos). ${\displaystyle C}$ ${\displaystyle \mathbb {F} _{q}}$

Entonces:

${\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

Prueba

Sea un código de longitud y distancia de Hamming mínima que tenga un tamaño máximo: ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle d}$

${\displaystyle |C|=A_{q}(n,d).}$

Entonces, para todos  , existe al menos una palabra de código tal que la distancia de Hamming entre y satisface ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ ${\displaystyle c_{x}\in C}$ ${\displaystyle d(x,c_{x})}$ ${\displaystyle x}$ ${\displaystyle c_{x}}$

${\displaystyle d(x,c_{x})\leqslant d-1}$

ya que de lo contrario podríamos añadir x al código manteniendo la distancia mínima de Hamming del código – una contradicción en la maximalidad de . ${\displaystyle d}$ ${\displaystyle |C|}$

Por lo tanto, el todo está contenido en la unión de todas las bolas de radio que tienen su centro en algún punto  : ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle d-1}$ ${\displaystyle c\in C}$

${\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).}$

Ahora cada bola tiene tamaño

${\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

ya que podemos permitir (o elegir ) que hasta de los componentes de una palabra de código se desvíen (del valor del componente correspondiente del centro de la bola ) a uno de los otros valores posibles (recuerde: el código es q-ario: toma valores en ). Por lo tanto, deducimos ${\displaystyle d-1}$ ${\displaystyle n}$ ${\displaystyle (q-1)}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

${\displaystyle q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\left|\bigcup _{c\in C}B(c,d-1)\right|\leqslant \sum _{c\in C}|B(c,d-1)|=|C|\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

Eso es:

${\displaystyle A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

Una mejora en el caso de potencia principal

Para q una potencia prima, se puede mejorar el límite a donde k es el mayor entero para el cual ${\displaystyle A_{q}(n,d)\geq q^{k}}$

${\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}.}$

Véase también

• Elias-Bassalygo encajonado
• Gilbert-Varshamov rumbo a los códigos lineales
• Griesmer atado
• Hamming atado
• Johnson se dirige hacia
• Plotkin atado
• Límite singleton

Referencias

1. Gilbert, EN (1952), "Una comparación de alfabetos de señalización", Bell System Technical Journal , 31 (3): 504–522, doi :10.1002/j.1538-7305.1952.tb01393.x.
2. Varshamov, RR (1957), "Estimación del número de señales en códigos de corrección de errores", Dokl. Akad. Nauk SSSR , 117 : 739–741.