Frontera Varshamov-Gilbert

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de noviembre de 2021; la verificación requiere 1 edición .

El límite de Varshamov-Gilbert es una desigualdad que define valores límite para parámetros de código (no necesariamente lineales ), obtenidos de forma independiente por Edgar Gilbert y Rom Varshamov . A veces se usa el nombre de desigualdad de Gilbert- Shannon - Varshamov , y en la literatura científica extranjera, desigualdad de Gilbert-Varshamov .

Redacción

Dejar

A_q(n,\;d)

denota la máxima cardinalidad posible del -ésimo código de longitud y distancia de Hamming ( el -ésimo código es el código con símbolos del campo que consta de elementos). $q$ $C$ $norte$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Después

A_q(n,\;d)\geqslant\frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1) ^j}.

Cuando es una potencia de un número primo , se puede simplificar la desigualdad a , donde es el entero más grande para el cual . $q$ $A_q(n,\;d)\geqslant q^k$ $k$ $\displaystyle A_q(n,\;d)\geqslant\displaystyle \frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-2}\displaystyle \binom{n-1}{j }(q-1)^j}$

Prueba

Sea el código de potencia máxima para la longitud y la distancia de Hamming : $C$ $norte$ $d$

|C|=A_q(n,\;d).

Entonces, para cualquiera hay al menos una palabra de código , por lo que la distancia de Hamming entre y satisface $x\in\mathbb{F}_q^n$ $c_x \in C$ $d(x,\;c_x)$ $X$ $c_x$

d(x,\;c_x)\leqslant d-1,

porque de lo contrario podríamos expandir el código con la palabra , dejando la distancia de Hamming sin cambios, lo que contradice la suposición de potencia máxima . $X$ $d$ $|C|$

Por lo tanto, el campo puede empaquetarse mediante la unión de los conjuntos de todas las esferas de radio con centro en : ${\matemáticas {F}}_{q}^{n}$ $d-1$ $c\en C$

\mathbb{F}_q^n =\bigcup_{c\in C}B(c,\;d-1).

El volumen de cada bola.

\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j,

porque podemos dejar (o elegir ) como máximo -th de los componentes de la palabra clave para tomar uno de los otros valores posibles. Por lo tanto, la siguiente desigualdad es verdadera $(d-1)$ $norte$ $(q-1)$

|\mathbb{F}_q^n|=\left|\bigcup_{c\in C}B(c,\;d-1)\right|\leqslant\bigcup_{c\in C}|B(c, \;d-1)|=|C|\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j.

Eso es

A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j }

(sustituyendo ). $|\mathbb{F}_q^n|=q^n$

Literatura

Gilbert EN Una comparación de los alfabetos de señalización // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Estimación del número de señales en códigos con corrección de errores // Informes de la Academia de Ciencias de la URSS , 117(5):739-741 [1], 1957.

Frontera Varshamov-Gilbert

Redacción

Prueba

Literatura

Véase también