Gilbert-Varshamov obligado

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

Declaración del obligado

Recuerde que un código tiene una distancia mínima si dos elementos cualesquiera del código están separados por al menos una distancia. Dejar ${\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 mínima de Hamming 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 mínima de Hamming 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 clave 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 agregar x al código manteniendo la distancia mínima de Hamming del código , una contradicción con la maximalidad de . ${\displaystyle d}$ ${\displaystyle |C|}$

Por tanto, el conjunto de está contenido en la unión de todas las bolas de radio que tienen su centro en algún lugar  : ${\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 uno de los componentes de una palabra clave se desvíe (del valor del componente correspondiente del centro de la bola ) a uno de otros valores posibles (recuerde: el código es q-ario: toma valores en ). De ahí 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 la energía primaria.

Para q una potencia prima, se puede mejorar el límite 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}}}.}$

Ver también

• Elias-Bassalygo obligado
• Gilbert-Varshamov destinado a códigos lineales
• Griesmer obligado
• Hamming atado
• Johnson obligado
• Plotkin atado
• Encuadernado 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. Akád. Nauk SSSR , 117 : 739–741.