Con destino a Gilbert-Varshamov

---

En la teoría de la codificación , el límite de Gilbert-Varshamov (debido a Edgar Gilbert ^[1] e independientemente Rom Varshamov ^[2] ) es un límite en los parámetros de un código (no necesariamente lineal ) . En ocasiones se conoce como el Gilbert- Shannon obligado -Varshamov (o la GSV obligado ), pero el nombre de "Gilbert-Varshamov obligado" es, con mucho, los más populares. 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 Gilbert-Varshamov enlazado para códigos lineales .

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

Sea un código de longitud y distancia mínima de Hamming que tenga el tamaño máximo:${\ Displaystyle C}$${\ Displaystyle n}$ ${\ Displaystyle 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}}$

ya que, de lo contrario, podríamos agregar x al código mientras mantenemos la distancia mínima de Hamming del código, una contradicción con la maximidad de .${\ Displaystyle d}$${\ Displaystyle | C |}$

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

---