V aplikované matematice je Johnson vázán (pojmenoval podle Selmer Martin Johnson ) je limit velikosti kódy opravující chyby, jak se používá v teorie kódování pro přenos dat nebo komunikace.
Definice
Nechat
být q-ary kód délky
, tj. podmnožina
. Nechat
být minimální vzdálenost
, tj.

kde
je Hammingova vzdálenost mezi
a
.
Nechat
být množinou všeho q-ary kódy s délkou
a minimální vzdálenost
a nechte
označit sadu kódů v
tak, že každý prvek má přesně
nenulové položky.
Označit podle
počet prvků v
. Poté definujeme
být největší velikostí kódu s délkou
a minimální vzdálenost
:

Podobně definujeme
být největší velikostí kódu v
:

Věta 1 (Johnson směřoval k
):
Li
,

Li
,

Věta 2 (Johnson směřoval k
):
(i) Li 

ii) Li
, poté definujte proměnnou
jak následuje. Li
je sudé, pak definujte
prostřednictvím vztahu
; -li
je liché, definujte
prostřednictvím vztahu
. Nechat
. Pak,

kde
je funkce podlahy.
Poznámka: Zapojením meze věty 2 do meze věty 1 se vytvoří numerická horní mez
.
Viz také
Reference