Johnson obligado

En matemáticas aplicadas, el límite de Johnson (llamado así por Selmer Martin Johnson ) es un límite en el tamaño de los códigos de corrección de errores , tal como se utiliza en la teoría de la codificación para la transmisión de datos o las comunicaciones.

Definición

Sea un código q -ario de longitud , es decir, un subconjunto de . Sea la distancia mínima de , es decir ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle d}$ ${\displaystyle C}$

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

¿Dónde está la distancia de Hamming entre y ? ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

Sea el conjunto de todos los códigos q -arios con longitud y distancia mínima y denotemos el conjunto de códigos de modo que cada elemento tenga exactamente entradas distintas de cero. ${\displaystyle C_{q}(n,d)}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle C_{q}(n,d,w)}$ ${\displaystyle C_{q}(n,d)}$ ${\displaystyle w}$

Denota por el número de elementos en . Luego, definimos como el tamaño más grande de un código con longitud y distancia mínima : ${\displaystyle |C|}$ ${\displaystyle C}$ ${\displaystyle A_{q}(n,d)}$ ${\displaystyle n}$ ${\displaystyle d}$

${\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}$

De manera similar, definimos como el tamaño más grande de un código en : ${\displaystyle A_{q}(n,d,w)}$ ${\displaystyle C_{q}(n,d,w)}$

${\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}$

Teorema 1 (Johnson con destino ): ${\displaystyle A_{q}(n,d)}$

Si , ${\displaystyle d=2t+1}$

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}}.}$

Si , ${\displaystyle d=2t+2}$

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.}$

Teorema 2 (Johnson con destino ): ${\displaystyle A_{q}(n,d,w)}$

(i) Si ${\displaystyle d>2w,}$

${\displaystyle A_{q}(n,d,w)=1.}$

(ii) Si , entonces defina la variable de la siguiente manera. Si es par, entonces defina a través de la relación ; si es impar, definir a través de la relación . Dejar . Entonces, ${\displaystyle d\leq 2w}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle d=2e}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle d=2e-1}$ ${\displaystyle q^{*}=q-1}$

${\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }$

¿Dónde está la función del suelo ? ${\displaystyle \lfloor ~~\rfloor }$

Observación: Al conectar el límite del Teorema 2 al límite del Teorema 1 se produce un límite superior numérico en . ${\displaystyle A_{q}(n,d)}$

Ver también

• Elías Bassalygo obligado
• Gilbert-Varshamov obligado
• Griesmer obligado
• Hamming atado
• Plotkin atado
• Encuadernado singleton

Referencias

• Johnson, Selmer Martin (abril de 1962). "Un nuevo límite superior para los códigos de corrección de errores". Transacciones IRE sobre teoría de la información : 203–207.
• Huffman, William Cary; Pless, Vera S. (2003). Fundamentos de los códigos de corrección de errores . Prensa de la Universidad de Cambridge . ISBN 978-0-521-78280-7.