Borde de trama

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de julio de 2014; las comprobaciones requieren 2 ediciones .

El límite de Plotkin : en la teoría de la codificación, determina el límite de potencia de un código binario de longitud y distancia mínima . Lleva el nombre del matemático estadounidense Morris Plotkin (1907-2003). $norte$ $d$

Redacción

Sea un código binario de longitud o, en otras palabras, un subconjunto de . Sea la distancia mínima del código , es decir $C$ $norte$ $\mathbb{F}_2^n$ $d$ $C$

d=\min_{\begin{pequeña matriz}x,\;y\in C,\\x\neq y\end{pequeña matriz}}d(x,\;y),

donde es la distancia de Hamming entre y . La expresión denota el número máximo posible de palabras de código en un código binario de longitud y distancia mínima . El límite de Plotkin da un límite superior a esta expresión. $d(x,\;y)$ $X$ $y$ $A_2(n,\;d)$ $norte$ $d$

Teorema (límite de Plotkin):

1. Si es un número par , entonces $d$ $2d>n$

A_2(n,\;d)\leqslant 2\left\lpiso\frac{d}{2d-n}\right\rpiso.

2. Si es un número impar y , entonces $d$ $2d+1>n$

A_2(n,\;d)\leqslant 2\left\lpiso\frac{d+1}{2d+1-n}\right\rpiso.

3. Si es un número par, entonces $d$

A_2(2d,\;d)\leqslant 4d.

4. Si es un número impar, entonces $d$

A_2(2d+1,\;d)\leqslant 4d+4,

donde el operador denota la parte entera de un número . $\left\lpiso ~ \right\rpiso$

Prueba de la primera parte

Sea la distancia de Hamming entre y , y sea la potencia de . Encontremos el límite del valor de dos maneras diferentes. $d(x,\;y)$ $X$ $y$ $METRO$ $C$ $\sum_{x,\;y\in C}d(x,\;y)$

Por un lado, hay diferentes opciones entre las que elegir , y para cada una de ellas hay opciones entre las que elegir . Por definición para todos y , por lo tanto $METRO$ $X$ $M-1$ $y$ $d(x,\;y)\geqslant d$ $X$ $y$

\sum_{x,\;y\in C}d(x,\;y)\geqslant M(M-1)d.

Por otro lado, la definimos como una matriz de dimensiones , cuyas filas serán elementos de código . Si es el número de ceros en una columna de matriz , entonces la columna contiene unos. Cualquier cero y uno en la misma columna se suman exactamente (porque ) al total , lo que significa $A$ $M\veces n$ $C$ $si}$ $i$ $A$ $i$ $M-s_i$ $2$ $d(x,\;y)=d(y,\;x)$ $\sum_{x,\;y\in C}d(x,\;y)$

\sum_{x,\;y\in C}d(x,\;y)=\sum_{i=1}^n 2s_i(M-s_i).

Incluso , el valor del lado derecho de la igualdad alcanza un máximo en , lo que significa $METRO$ $s_i=M/2$

\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}nM^2.

Combinando los límites inferior y superior de la expresión en una desigualdad, obtenemos $\sum_{x,\;y\in C}d(x,\;y)$

M(M-1)d\leqslant\frac{1}{2}nM^2,

que es equivalente bajo la condición $2d>n$

M\leqslant\frac{2d}{2d-n}.

Como es un número par, entonces $METRO$

M\leqslant 2\left\lpiso\frac{d}{2d-n}\right\rpiso.

Por otro lado, si es impar, alcanza un máximo en , de donde se sigue que $METRO$ $\sum_{i=1}^n 2s_i(M-s_i)$ $s_i=\frac{M\pm1}{2}$

\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}n(M^2-1).

Combinando los límites inferior y superior de la expresión en una desigualdad, obtenemos $\sum_{x,\;y\in C}d(x,\;y)$

M(M-1)d\leqslant\frac{1}{2}n(M^2-1),

que es equivalente bajo la condición $2d>n$

M\leqslant\frac{2d}{2d-n}-1.

Como es un número entero, entonces $METRO$

M\leqslant\left\lfloor\frac{2d}{2d-n}-1\right\rfloor=\left\lfloor\frac{2d}{2d-n}\right\rfloor-1\leqslant 2\left\ lpiso\frac{d}{2d-n}\derecho\rpiso,

lo que completa la prueba de la primera parte.

Prueba de la segunda parte

Para obtener la desigualdad necesaria, necesitamos probar el siguiente lema.

Lema 1

A(n,\;2r-1)=A(n+1,\;2r).

Prueba del lema

Que sea -código. Agregando a la verificación de paridad, obtenemos -code, lo que implica que $C$ $(n,\;M,\;2r-1)$ $C$ $(n+1,\;M,\;2r)$

A_2(n,\;2r-1)\leqslant A_2(n+1,\;2r).

En la dirección opuesta, arrojar una coordenada en un código dado da como resultado un código, de modo que $(n+1,\;M,\;2r)$ $(n,\;M,\;d\geqslant 2r-1)$

A_2(n,\;2r-1)\geqslant A_2(n+1,\;2r).

El resultado requerido se sigue de la primera parte de la demostración y del Lema 1.

Prueba de la tercera parte

Nuevamente, primero demostramos la siguiente afirmación auxiliar.

Lema 2

A_2(n,\;d)\leqslant 2A_2(n-1,\;d).

Prueba del lema

En un código dado , dividimos todas las palabras del código en dos clases, asignando a una clase las palabras que comienzan con cero y a la otra las que comienzan con uno. Una de estas clases contiene al menos la mitad de las palabras clave, lo que significa $(n,\;M,\;d)$

A_2(n-1,\;d)\geqslant\frac{A_2(n,\;d)}{2}.

De la primera parte de la demostración y del Lema 2 se sigue que

A_2(4r,\;2r)\leqslant 2A_2(4r-1,\;2r)\leqslant 8r.

El resultado deseado se obtiene sustituyendo . $d=2r$

Prueba de la cuarta parte

El lema 1 implica que

A_2(2d+1,\;d)=A_2(2d+2,\;d+1).

Como y son números pares, podemos usar el resultado de la tercera parte de la demostración: $2d+2$ $d+1$

A_2(2d+2,\;d+1)=A_2(2(d+1),\;d+1)\leqslant 4(d+1)=4d+4,

lo que completa la demostración de todo el teorema.

Códigos que logran el límite de Plotkin

Si existen matrices de Hadamard de todos los órdenes posibles (que, sin embargo, aún no se ha demostrado), entonces las igualdades se cumplen en todas las partes del teorema. Así, la cota de Plotkin es exacta en el sentido de que hay códigos que alcanzan esta cota [1] .

Notas

↑ Levenshtein V. I. Aplicación de matrices de Hadamard a un problema de codificación. — Problemas de Cibernética . - 5:123-136 [2A], 1961.

Literatura

Plotkin M. Códigos binarios con una distancia mínima dada. — Colección cibernética . - Moscú, 7:60-73 [2], 1963.
FJ MacWilliams y NJA Sloane. La teoría de los códigos correctores de errores . - Ámsterdam, Países Bajos, Holanda Septentrional, § 2.2, 1977.