Límite de Johnson

El límite de Johnson define el límite de potencia del código de longitud y la distancia mínima . $norte$ $d$

Redacción

Sea el -ésimo código de longitud sobre el campo o, en otras palabras, el subconjunto de . Sea la distancia mínima del código , es decir $C$ $q$ $norte$ $\mathbb{F} = \mathrm{GF}(q)$ ${\matemáticas {F}}_{q}^{n}$ $d$ $C$

d = \min_{x,y \in C, \; x \neq y} \mathsf{d}(x,y)

donde está la distancia de Hamming entre las palabras clave y . $\mathsf{d}(x,y)$ $X$ $y$

Sea el conjunto de todos los códigos -th de longitud y distancia mínima , y denote el subconjunto de todos los códigos de equilibrio en , en otras palabras, todos los códigos cuyo peso de todas las palabras de código es igual a . $C_q(n,d)$ $q$ $norte$ $d$ $C_q(n,d,w)$ $C_q(n,d)$ $w$

Denotemos por el número de palabras de código en , y por — la cardinalidad máxima del código de longitud y la distancia mínima , es decir $|C|$ $C$ $A_q(n,d)$ $norte$ $d$

A_q(n,d) = \max_{C \in C_q(n,d)} |C|.

Del mismo modo, definimos como la potencia máxima del código en : $A_q(n,d,w)$ $C_q(n,d,w)$

A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.

Teorema 1 (Johnson ligado a ): $A_q(n,d)$

A $d=2t+1$

A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \elegir i} (q-1)^i + \frac{{n \elegir t+1} - {d \elegir t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1} }.

Nota: para encontrar el límite superior para valores pares , puede usar la siguiente igualdad $A_q(n,d)$ $d=2t$

A_q(n,2t) = A_q(n-1,2t-1).

Teorema 2 (Johnson ligado a ): $A_q(n,d,w)$

A $d > 2w$

A_q(n,d,w) = 1.

Cuando let , y también , entonces $d \ leq 2w$ $t = \lceil \frac{d}{2}\rceil$ $q^* = q - 1$

A_q(n,d,w) \leq \lpiso \frac{nq^*}{w} \lpiso \frac{(n-1)q^*}{w-1} \lpiso \cdots \lpiso \frac{ (n-w+t)q^*}{t} \rpiso \cdots \rpiso \rpiso,

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

Nota: Sustituyendo el límite del Teorema 2 en el Teorema 1, obtenemos un límite superior para . $A_q(n,d)$

Demostración del primer teorema

Sea un código de longitud , potencia con distancia mínima , que contiene un vector cero. Denotar por el conjunto de vectores que están a una distancia del código , es decir, $C$ $norte$ $M = A_q(n, d)$ $d=2t+1$ $Si}$ $i$ $C$

S_i = \left\lbrace u \in F^n: \forall v \in C\ d(u, v) \geq i \wedge \exists w \in C\ d(w, u) = i \right\rbrace .

Así, . Entonces , dado que si hubiera un vector ubicado a una distancia o más del código , entonces podríamos agregarlo y obtener un código de potencia aún mayor. Dado que los conjuntos no se intersecan, esto implica el límite del empaquetamiento esférico . Para obtener el límite deseado, estimamos la potencia . $S_0 = C$ $S_0 \taza S_1 \taza \puntos \taza S_{d - 1} = F^n$ $d$ $C$ $C$ $S_0, S_1, S_2, \puntos, S_t$ $M_{t + 1}$

Elijamos una palabra clave arbitraria y mediante el cambio apropiado del código la transferiremos al origen de coordenadas. Las palabras de código de peso forman un código de equilibrio con una distancia mínima de al menos , y por lo tanto el número de palabras de código de peso no excede . $PAGS$ $d=2t+1$ $2t+1$ $d$ $A_q(n, 2t + 1, 2t + 1) = A_q(n, d, d)$

Denote por el conjunto de vectores de peso . Cualquier vector de pertenece a , o . Cada palabra de código de peso corresponde a vectores de peso que están a una distancia de . $W_{t + 1}$ $F^{n}$ $t+1$ $W_{t + 1}$ $S t$ $M_{t + 1}$ $q$ $d$ ${ re \ elige t }$ $t+1$ $q$ $t$

Todos estos vectores son diferentes y pertenecen al conjunto . Como consecuencia, $W_{t + 1} \cap S_t$

|W_{t + 1} \cap S_{t+1}| = |W_{t + 1}| - |W_{t + 1} \cap S_t| \geq {n \elegir t + 1}(q - 1)^{t + 1} - {d \elegir t}(q - 1)^{t + 1} A_q(n, d, d).

El vector del conjunto está a una distancia de no más que de las palabras de código. De hecho, movamos el origen a un punto y calculemos cuántas palabras de código pueden estar a una distancia y tener una distancia de Hamming entre ellas . Esos, por definición, no deberían ser más . Por lo tanto, los vectores del conjunto se pueden contar la mayoría de las veces, es decir, cada palabra de código corresponde al menos a $R$ $W_{t + 1} \cap S_{t+1}$ $t+1$ $A_q(n,d,t+1)$ $R$ $R$ $t+1$ $d$ $A_q(n,d,t+1)$ $W_{t + 1} \cap S_{t+1}$ $A_q(n,d,t+1)$ $PAGS$

\frac{{n \elegir t+1} - {d \elegir t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}

diferentes vectores a una distancia de . $t+1$ $PAGS$

Literatura

S. Johnson, Un nuevo límite superior para los códigos de corrección de errores, IRE Transactions on Information Theory , 203–207, abril de 1962.
FJ MacWilliams y NJA Sloane, The Theory of Error-Correcting Codes , Ámsterdam, Países Bajos, Holanda Septentrional, § 17.2, § 17.3, 1977.
W. C. Huffman, V. Pless, Fundamentos de los códigos de corrección de errores , Cambridge University Press, 2003.

Límite de Johnson

Redacción

Demostración del primer teorema

Literatura

Véase también