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 en 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 códigos no binarios.
Para un código lineal binario, el límite de Griesmer es:
Dejar denotar la longitud mínima de un código binario de dimensión k y distancia d . Sea C tal código. Queremos demostrar que
Deje que G sea 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 .
La matriz genera un código , que se llama el código residual de obviamente tiene dimensión y longitud tiene una distancia pero no lo sabemos. Dejar ser tal que . Existe un vector tal que la concatenación Luego Por otro lado, también desde y es lineal: Pero
así que esto se convierte en . Sumando esto con obtenemos . Pero así que obtenemos Esto implica
por lo tanto, debido a la integralidad de
así que eso
Por inducción sobre k finalmente obtendremos
Tenga en cuenta que en cualquier paso la dimensión disminuye en 1 y la distancia se reduce a la mitad, y usamos la identidad
para cualquier entero una y entero positivo k .
Para un código lineal sobre , el límite de Griesmer se convierte en:
La prueba es similar al caso binario, por lo que se omite.