En las matemáticas de teoría de la codificación , la Plotkin obligado, el nombre de Morris Plotkin, es un límite (o unido) sobre el número máximo posible de palabras de código en binarios códigos de longitud dada n y dada la distancia mínima d .
Un código se considera "binario" si las palabras de código utilizan símbolos del alfabeto binario. . En particular, si todas las palabras de código tienen una longitud fija n , entonces el código binario tiene una longitud n . De manera equivalente, en este caso las palabras de código pueden considerarse elementos del espacio vectorial sobre el campo finito . Dejar ser la distancia mínima de , es decir
dónde es la distancia de Hamming entre y . La expresion representa el número máximo de palabras de código posibles en un código binario de longitud y distancia mínima . El límite de Plotkin pone un límite a esta expresión.
Teorema (límite de Plotkin):
i) Si es par y , luego
ii) Si es extraño y , luego
iii) Si es par, entonces
iv) Si es extraño, entonces
dónde denota la función de piso .
Dejar ser la distancia de Hamming de y , y ser el número de elementos en (por lo tanto, es igual a ). El límite se demuestra acotando la cantidad de dos formas diferentes.
Por un lado, hay opciones para y para cada una de esas opciones, hay opciones para . Ya que por definición para todos y (), resulta que
Por otro lado, deja frijol matriz cuyas filas son los elementos de . Dejar ser el número de ceros contenidos en el 'a columna de . Esto significa que el'th columna contiene unos. Cada elección de un cero y uno en la misma columna contribuye exactamente (porque ) a la suma y por lo tanto
La cantidad de la derecha se maximiza si y solo si se mantiene para todos (en este punto de la prueba ignoramos el hecho de que el son enteros), entonces
Combinando los límites superior e inferior para que acabamos de derivar,
que dado eso es equivalente a
Desde es par, se sigue que
Esto completa la prueba del encuadernado.