Johnson vázán - Johnson bound

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

  • Johnson, Selmer Martin (Duben 1962). Msgstr "Nová horní hranice pro kódy opravující chyby". Transakce IRE na teorii informací: 203–207.
  • Huffman, William Cary; Pless, Vera S. (2003). Základy kódů pro opravu chyb. Cambridge University Press. ISBN  978-0-521-78280-7.