Plotkin atado

En las matemáticas de la teoría de codificación , el límite de Plotkin , llamado así por Morris Plotkin, es un límite en el número máximo posible de palabras de código en códigos binarios de longitud dada n y distancia mínima dada d .

Declaración del obligado

Un código se considera "binario" si las palabras del código utilizan símbolos del alfabeto binario . En particular, si todas las palabras del código tienen una longitud fija n , entonces el código binario tiene una longitud n . De manera equivalente, en este caso las palabras del código pueden considerarse elementos del espacio vectorial sobre el cuerpo finito . Sea la distancia mínima de , es decir ${\displaystyle \{0,1\}}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle d}$ ${\displaystyle C}$

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}$

donde es la distancia de Hamming entre y . La expresión 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 impone un límite a esta expresión. ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle n}$ ${\displaystyle d}$

Teorema (límite de Plotkin):

i) Si es par y , entonces ${\displaystyle d}$ ${\displaystyle 2d>n}$

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

ii) Si es impar y , entonces ${\displaystyle d}$ ${\displaystyle 2d+1>n}$

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .}$

iii) Si es par, entonces ${\displaystyle d}$

${\displaystyle A_{2}(2d,d)\leq 4d.}$

iv) Si es impar, entonces ${\displaystyle d}$

${\displaystyle A_{2}(2d+1,d)\leq 4d+4}$

donde denota la función de piso . ${\displaystyle \left\lfloor ~\right\rfloor }$

Prueba del caso i

Sea la distancia de Hamming de y , y el número de elementos en (por lo tanto, es igual a ). La cota se demuestra acotando la cantidad de dos maneras diferentes. ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)}$

Por un lado, existen opciones para y para cada una de esas opciones, existen opciones para . Dado que por definición para todos y ( ), se sigue que ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M-1}$ ${\displaystyle y}$ ${\displaystyle d(x,y)\geq d}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\neq y}$

${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}$

Por otra parte, sea una matriz cuyas filas son los elementos de . Sea el número de ceros contenidos en la 'ésima columna de . Esto significa que la 'ésima columna contiene unos. Cada elección de un cero y un uno en la misma columna contribuye exactamente (porque ) a la suma y por lo tanto ${\displaystyle A}$ ${\displaystyle M\times n}$ ${\displaystyle C}$ ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle M-s_{i}}$ ${\displaystyle 2}$ ${\displaystyle d(x,y)=d(y,x)}$ ${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$

${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)=\sum _{i=1}^{n}2s_{i}(M-s_{i}).}$

La cantidad de la derecha se maximiza si y solo si se cumple para todos (en este punto de la prueba ignoramos el hecho de que son números enteros), entonces ${\displaystyle s_{i}=M/2}$ ${\displaystyle i}$ ${\displaystyle s_{i}}$

${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.}$

Combinando los límites superior e inferior que acabamos de derivar, ${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$

${\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}$

lo cual dado que es equivalente a ${\displaystyle 2d>n}$

${\displaystyle M\leq {\frac {2d}{2d-n}}.}$

Como es par, se sigue que ${\displaystyle M}$

${\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

Con esto se completa la prueba del límite.

Véase también

• Código de diamante
• Elias Bassalygo encuadernado
• Límite Gilbert-Varshamov
• Griesmer atado
• Hamming atado
• Johnson se dirige hacia
• Límite singleton

Referencias

• Plotkin, Morris (1960). "Códigos binarios con distancia mínima especificada". IRE Transactions on Information Theory . 6 (4): 445–450. doi :10.1109/TIT.1960.1057584.