Gilbert-Varshamov vinculado

En teoría de la codificación , la cota de Gilbert-Varshamov (debida a Edgar Gilbert ^{[ 1 ]} e independientemente a Rom Varshamov ^{[ 2 ]} ) es una cota para el tamaño de un código (no necesariamente lineal ) . A veces se la conoce como la cota de Gilbert- Shannon -Varshamov (o la cota GSV ), pero el nombre "cota de Gilbert-Varshamov" es, con mucho, el más popular. Varshamov demostró esta cota utilizando el método probabilístico para códigos lineales. Para más información sobre esta demostración, véase Cota de Gilbert-Varshamov para códigos lineales .

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

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

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

Entonces:

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

dónde${\displaystyle H_{q}}$es la función de entropía q -aria,

${\displaystyle H_{q}(x)=x\log _{q}(q-1)-x\log _{q}x-(1-x)\log _{q}(1-x).}$

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

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

Entonces para todos${\displaystyle x\in \mathbb {F} _{q}^{n}}$ Existe al menos una palabra clave.${\displaystyle c_{x}\in C}$de tal manera que la distancia de Hamming${\displaystyle d(x,c_{x})}$entre${\displaystyle x}$y${\displaystyle c_{x}}$Satisface

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

ya que de otro modo podríamos agregar x al código manteniendo la distancia de Hamming mínima del código.${\displaystyle d}$– una contradicción sobre la máxima de${\displaystyle |C|}$.

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

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

Ahora cada pelota tiene tamaño

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

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

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

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

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

• Elias-Bassalygo se dirige
• Cota de Gilbert-Varshamov para códigos lineales
• Griesmer se dirige
• Hamming se dirigió
• Johnson se dirige
• Plotkin estaba atado
• Singleton