Plotkin estaba atado

En las matemáticas de la teoría de la codificación , la cota de Plotkin , que recibe su nombre de Morris Plotkin, es un límite (o cota) sobre el número máximo posible de palabras clave en códigos binarios de longitud n y distancia mínima d dadas .

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

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

dónde${\displaystyle d(x,y)}$es la distancia de Hamming entre${\displaystyle x}$y${\displaystyle y}$. La expresión${\displaystyle A_{2}(n,d)}$representa el número máximo de posibles palabras clave en un código binario de longitud${\displaystyle n}$y distancia mínima ${\displaystyle d}$La cota de Plotkin impone un límite a esta expresión.

Teorema (cota de Plotkin):

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

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

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

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

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

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

iv) Si${\displaystyle d}$es extraño, entonces

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

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

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

Por un lado, hay${\displaystyle M}$opciones para${\displaystyle x}$y para cada una de esas elecciones, hay${\displaystyle M-1}$opciones para${\displaystyle y}$. Puesto que por definición${\displaystyle d(x,y)\geq d}$a pesar de${\displaystyle x}$y${\displaystyle y}$(${\displaystyle x\neq y}$), se deduce que

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

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

${\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${\displaystyle s_{i}=M/2}$se aplica a todos${\displaystyle i}$(en este punto de la demostración ignoramos el hecho de que el${\displaystyle s_{i}}$son números enteros), entonces

${\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 para${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$que acabamos de derivar,

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

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

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

Desde${\displaystyle M}$es par, se deduce que

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

Esto completa la demostración de la cota.

• Código diamante
• Elias Bassalygo se dirige
• Gilbert-Varshamov vinculado
• Griesmer se dirige
• Hamming se dirigió
• Johnson se dirige
• Singleton

• 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 .