Związany z Plotkinem

W matematyce teorii kodowania granica Plotkina, nazwana na cześć Morrisa Plotkina, jest granicą (lub granicą) maksymalnej możliwej liczby słów kodowych w kodach binarnych o danej długości n i danej minimalnej odległości d .

Oświadczenie związane

alfabetu binarnego. ${\ displaystyle \ {0,1 \}}$ . W szczególności, jeśli wszystkie słowa kodowe mają stałą długość n , to kod binarny ma długość n . Równoważnie w tym przypadku słowa kodowe można uznać za elementy przestrzeni wektorowej nad polem skończonym ${\ displaystyle \ mathbb {f} _ {2} ^ {$ $n$ . niech będzie minimalną odległością do ${ \ displaystyle$ $}$ , tj

{\ Displaystyle d = \ min _ {x, y \ w C, x \ neq y} d (x, y)}

gdzie $y$ odległość Hamminga między y $_$ $_$ _ Wyrażenie reprezentuje maksymalną liczbę możliwych słów kodowych w kodzie binarnym o długości $\ displaystyle$ minimalnej odległości re $\ Displaystyle A_ {2} (n, d)$ $, re ) {$ . Granica Plotkina ogranicza to wyrażenie.

Twierdzenie (związane z Plotkinem):

${\ Displaystyle 2d> n}$ ) Jeśli $re$ parzysta i , to

{\ Displaystyle A_ {2} (n, d) \ równoważnik 2 \ lewo \ lfloor {\ Frac {d} {2d-n}} \ prawo \ rfloor.}

ii) Jeśli $nieparzysta$ i ${\ Displaystyle 2d + 1> n}$ , to

{\ Displaystyle A_ {2} (n, d) \ równoważnik 2 \ lewo \ lfloor {\ Frac {d + 1} {2d + 1-n}} \ prawo \ rfloor.}

iii) Jeśli jest parzysta, to ${\ displaystyle d}$

{\ Displaystyle A_ {2} (2d, d) \ równoważnik 4d.}

iv) Jeśli jest nieparzyste, to ${\ displaystyle d}$

{\ Displaystyle A_ {2} (2d + 1, d) \ równoważnik 4d + 4}

gdzie ${\ Displaystyle \ lewo \ lfloor ~ \ prawo \ rfloor}$ oznacza funkcję podłogi .

Dowód sprawy I

Niech $)}$ ${\ Displaystyle C}$ $y$ będzie odległością Hamminga i y $\ Displaystyle$ $}$ i będzie liczbą elementów w (a więc ${\ Displaystyle M}$ jest równe ${\ Displaystyle A_ {2} (n, d)}$ ). Ograniczenie jest udowodnione przez ograniczenie ilości ${\ Displaystyle \ suma _ {(x, y) \ w C ^ {2}, x \ neq y}d(x,y)}$ na dwa różne sposoby.

Z jednej strony istnieją wybory dla i dla każdego takiego $wyboru$ są wybory dla $displaystyle M-$ ${$ $}$ Ponieważ z definicji ${\ Displaystyle d (x, y) \ geq d}$ dla wszystkich i ${\ Displaystyle x}$ i ${\ Displaystyle y}$ ( ${\ displaystyle x \ neq y}$ ), wynika z tego

{\ Displaystyle \ suma _ {(x, y) \ w C ^ {2}, x \ neq y} d (x, y) \ geq M (M-1) d.}

$niech$ drugiej strony $będzie$ macierzą , $wiersze$ Niech ${\ displaystyle s_ {$ liczbą zer zawartych w ' tej kolumnie $} s ja$ $}$ } Oznacza to $,$ że ta kolumna zawiera ${\ Displaystyle M-s_ {i}}$ jedności. Każdy wybór zera i jedynki w tej samej kolumnie wnosi dokładnie ${\ Displaystyle 2}$ (ponieważ ${\ Displaystyle d (x, y) = d (y, x )}$ ) do sumy ${\ Displaystyle \ suma _ {(x, y) \ w C, x \ neq y} d (x, y)}$ i dlatego

{\ Displaystyle \ suma _ {(x, y) \ w C, x \ neq y} d (x, y) = \ suma _ {i = 1} ^ {n} 2s_ {i} (Ms_ {i} }).}

Wielkość po prawej stronie jest zmaksymalizowana wtedy i tylko wtedy, gdy $tym$ w $fakt$ dowodu że ${\ displaystyle s_ {i}}$ są liczbami całkowitymi), a następnie

{\ Displaystyle \ suma _ {(x, y) \ w C, x \ neq y} d (x, y) \ równoważnik {\ Frac {1} {2}} nM ^ {2}.}

$\ Displaystyle \ suma _ {(x, y) \ w C, x \ neq y} d (x, y)}$ do , które właśnie wyprowadziliśmy,

{\ Displaystyle M (M-1) d \ równoważnik {\ Frac {1} {2}} nM ^ {2}}

co biorąc pod uwagę, że jest równoważne ${\ displaystyle 2d> n}$

{\ Displaystyle M \ równoważnik {\ Frac {2d} {2d-n}}.}

Ponieważ $jest parzysta$ wynika z tego

{\ Displaystyle M \ równoważnik 2 \ lewo \ lfloor {\ Frac {d} {2d-n}} \ prawo \ rfloor.}

To kończy dowód wiązania.

Zobacz też

Plotkin, Morris (1960). „Kody binarne z określoną minimalną odległością”. Transakcje IRE dotyczące teorii informacji . 6 (4): 445–450. doi : 10.1109/TIT.1960.1057584 .