Griesmer atado

En las matemáticas de la teoría de la codificación , el límite de Griesmer , llamado así por James Hugo Griesmer, es un límite de la longitud de los códigos binarios lineales de dimensión k y distancia mínima d . También existe una versión muy similar para los códigos no binarios.

Declaración del obligado

Para un código lineal binario, el límite de Griesmer es:

${\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

Prueba

Sea C la longitud mínima de un código binario de dimensión k y distancia d . Queremos demostrar que ${\displaystyle N(k,d)}$

${\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

Sea G una matriz generadora de C. Siempre podemos suponer que la primera fila de G tiene la forma r  = (1, ..., 1, 0, ..., 0) con peso d .

${\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}$

La matriz genera un código , que se llama código residual de obviamente tiene dimensión y longitud tiene una distancia pero no la conocemos. Sea tal que . Existe un vector tal que la concatenación Entonces Por otro lado, también como y es lineal: Pero ${\displaystyle G'}$ ${\displaystyle C'}$ ${\displaystyle C.}$ ${\displaystyle C'}$ ${\displaystyle k'=k-1}$ ${\displaystyle n'=N(k,d)-d.}$ ${\displaystyle C'}$ ${\displaystyle d',}$ ${\displaystyle u\in C'}$ ${\displaystyle w(u)=d'}$ ${\displaystyle v\in \mathbb {F} _{2}^{d}}$ ${\displaystyle (v|u)\in C.}$ ${\displaystyle w(v)+w(u)=w(v|u)\geqslant d.}$ ${\displaystyle (v|u)+r\in C,}$ ${\displaystyle r\in C}$ ${\displaystyle C}$ ${\displaystyle w((v|u)+r)\geqslant d.}$

${\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),}$

Por lo tanto, esto se convierte en . Sumando esto con obtenemos . Pero entonces obtenemos Como es integral, obtenemos Esto implica ${\displaystyle d-w(v)+w(u)\geqslant d}$ ${\displaystyle w(v)+w(u)\geqslant d,}$ ${\displaystyle d+2w(u)\geqslant 2d}$ ${\displaystyle w(u)=d',}$ ${\displaystyle 2d'\geqslant d.}$ ${\displaystyle d'}$ ${\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .}$

${\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}$

de modo que

${\displaystyle N(k,d)\geqslant d+N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right).}$

Por inducción sobre k eventualmente obtendremos

${\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

Nótese que en cualquier paso la dimensión disminuye en 1 y la distancia se reduce a la mitad, y usamos la identidad

${\displaystyle \left\lceil {\frac {\left\lceil a/2^{k-1}\right\rceil }{2}}\right\rceil =\left\lceil {\frac {a}{2^{k}}}\right\rceil }$

para cualquier entero a y entero positivo k .

Limitado al caso general

Para un código lineal sobre , el límite de Griesmer se convierte en: ${\displaystyle \mathbb {F} _{q}}$

${\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{q^{i}}}\right\rceil .}$

La prueba es similar al caso binario y por eso se omite.

Véase también

• Elias Bassalygo encuadernado
• Límite Gilbert-Varshamov
• Hamming atado
• Johnson se dirige hacia
• Plotkin atado
• Límite singleton

Referencias

• JH Griesmer, "Un límite para los códigos de corrección de errores", IBM Journal of Res. and Dev., vol. 4, núm. 5, págs. 532-542, 1960.