Plotkin bunden

I matematiken för kodningsteorin är Plotkin -bunden, uppkallad efter Morris Plotkin, en gräns (eller bunden) för det maximalt möjliga antalet kodord i binära koder med given längd n och givet minsta avstånd d .

Uttalande av bunden

En kod anses vara "binär" om kodorden använder symboler från det binära alfabetet $\{0,1\}$ . I synnerhet, om alla kodord har en fast längd n , så har den binära koden längden n . På motsvarande sätt kan kodorden i detta fall betraktas som element i vektorrymden $\mathbb {F} _{2}^{n}$ över det finita fältet $\mathbb {F} _{ 2}$ . Låt $d$ vara det minsta avståndet för $C$ , dvs

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

där $d(x,y)$ är Hamming-avståndet mellan $x$ och $y$ . Uttrycket $A_{2}(n,d)$ representerar det maximala antalet möjliga kodord i en binär kod med längden $n$ och minsta avstånd $d$ . Plotkin-bunden sätter en gräns för detta uttryck.

Sats (Plotkin bunden):

i) Om $d$ är jämn och $2d>n$ , då

A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .

ii) Om $d$ är udda och ${\displaystyle 2d+1>n$ }

A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .

iii) Om $d$ är jämnt, då

A_{2}(2d,d)\leq 4d.

iv) Om $d$ är udda, då

A_{2}(2d+1,d)\leq 4d+4

där $\left\lfloor ~\right\rfloor$ anger golvfunktionen .

Bevis i

Låt $d(x,y)$ vara Hamming-avståndet för $x$ och $y$ , och $M$ är antalet element i $C$ (därmed är $M$ lika med ${\displaystyle A_{2}(n,d)} )$ . Bindningen bevisas genom att avgränsa kvantiteten $\sum _{(x,y)\i C^{2},x\neq y}d(x,y)$ på två olika sätt.

Å ena sidan finns det $M$ -val för $x$ och för varje sådant val finns det $M-1$ -val för $y$ . Eftersom per definition $d(x,y)\geq d$ för alla $x$ och $y$ ( $x\neq y$ ), följer det

\sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.

Å andra sidan, låt $A$ vara en $M\times n$ -matris vars rader är elementen i $C$ . Låt $s_{i}$ vara antalet nollor som finns i ${\displaystyle i}:$ e kolumnen i $A$ . Detta betyder att $i$ ':te kolumnen innehåller $M-s_{i}$ ettor. Varje val av en nolla och en etta i samma kolumn bidrar med exakt $2$ (eftersom $d(x,y)=d(y,x )$ ) till summan $\summa _{(x,y)\in C,x\neq y}d(x,y )$ och därför

\sum _{(x,y)\in C,x\neq y}d(x,y)=\summa _{i=1}^{n}2s_{i}(M-s_{i }).

Kvantiteten till höger maximeras om och endast om $s_{i}=M/2$ gäller för alla $i$ (vid denna punkt av beviset ignorerar vi faktum, att $s_{i}$ är heltal), då

\sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.

Kombinera de övre och nedre gränserna för $\sum _{(x,y)\i C,x\neq y}d(x, y)$ som vi just har härlett,

M(M-1)d\leq {\frac {1}{2}}nM^{2}

vilket givet att $2d>n$ är ekvivalent med

M\leq {\frac {2d}{2d-n}}.

Eftersom $M$ är jämnt följer det

M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .

Detta fullbordar beviset för bunden.

Se även

Plotkin, Morris (1960). "Binära koder med specificerat minimiavstånd". IRE-transaktioner på informationsteori . 6 (4): 445–450. doi : 10.1109/TIT.1960.1057584 .