V matematika z teorie kódování, Plotkin vázán, pojmenovaný po Morrisovi Plotkinovi, je limit (nebo limit) maximálního možného počtu kódových slov v binární kódy dané délky n a vzhledem k minimální vzdálenosti d.
Prohlášení o vazbě
Kód je považován za „binární“, pokud kódová slova používají symboly z binárního souboru abeceda
. Zejména pokud mají všechna kódová slova pevnou délku n, pak má binární kód délku n. Ekvivalentně v tomto případě lze kódová slova považovat za prvky vektorový prostor
přes konečné pole
. Nechat
být minimální vzdálenost
, tj.

kde
je Hammingova vzdálenost mezi
a
. Výraz
představuje maximální počet možných kódových slov v binárním kódu délky
a minimální vzdálenost
. Plotkinova vazba omezuje tento výraz.
Věta (Plotkinova vazba):
i) Pokud
je sudé a
, pak

ii) Pokud
je liché a
, pak

iii) Pokud
je tedy vyrovnaný

iv) Pokud
je tedy zvláštní

kde
označuje funkce podlahy.
Důkaz případu i)
Nechat
být Hammingova vzdálenost z
a
, a
být počet prvků v
(tím pádem,
je rovný
). Vazba se prokáže ohraničením množství
dvěma různými způsoby.
Na jedné straně existují
možnosti pro
a pro každou takovou volbu existují
možnosti pro
. Protože podle definice
pro všechny
a
(
), z toho vyplývá, že

Na druhou stranu
být
matice, jejíž řádky jsou prvky
. Nechat
být počet nul obsažených v
sloupec
. To znamená, že
sloupec obsahuje
ty. Každá volba nuly a jedné ve stejném sloupci přispívá přesně
(protože
) k součtu
a proto

Množství vpravo je maximalizováno právě tehdy
platí pro všechny
(v tomto bodě důkazu ignorujeme skutečnost, že
jsou celá čísla)

Kombinace horní a dolní hranice pro
které jsme právě odvodili,

který to dal
je ekvivalentní k

Od té doby
je dokonce, z toho vyplývá

Tím je dokončen důkaz vázaného.
Viz také
Reference