Johnson se dirige

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

Dejar${\displaystyle C}$ser un código q -ario de longitud${\displaystyle n}$, es decir, un subconjunto de${\displaystyle \mathbb {F} _{q}^{n}}$. 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}$.

Dejar${\displaystyle C_{q}(n,d)}$sea ​​el conjunto de todos los códigos q -arios con longitud${\displaystyle n}$y distancia mínima${\displaystyle d}$y dejar${\displaystyle C_{q}(n,d,w)}$denotan el conjunto de códigos en${\displaystyle C_{q}(n,d)}$de tal manera que cada elemento tenga exactamente${\displaystyle w}$entradas distintas de cero.

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

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

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

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

Teorema 1 (cota de Johnson para${\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 (cota de Johnson para${\displaystyle A_{q}(n,d,w)}$):

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

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

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

${\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${\displaystyle \lfloor ~~\rfloor }$es la función de piso .

Nota: Sustituyendo la cota del Teorema 2 en la cota del Teorema 1 se obtiene una cota superior numérica en${\displaystyle A_{q}(n,d)}$.

• Elias Bassalygo se dirige
• Gilbert-Varshamov vinculado
• Griesmer se dirige
• Hamming se dirigió
• Plotkin estaba atado
• Singleton

• Johnson, Selmer Martin (abril de 1962). "Un nuevo límite superior para códigos correctores de errores". IRE Transactions on Information Theory : 203–207 .
• Huffman, William Cary; Pless, Vera S. (2003). Fundamentos de los códigos correctores de errores . Cambridge University Press . ISBN 978-0-521-78280-7.