プロトキン限界

${\displaystyle x}$ と ${\displaystyle y}$ のハミング距離を ${\displaystyle d(x,y)}$ とし、${\displaystyle C}$ に存在する符号語数を ${\displaystyle M}$ とする（つまり、${\displaystyle M}$ と ${\displaystyle A_{2}(n,d)}$ は等しい）。するとプロトキン限界は、${\displaystyle \sum _{x,y\in C}d(x,y)}$ について2種類の方法で限界を求めることで得られる。

まず ${\displaystyle x}$ として選択肢が ${\displaystyle r}$ 個あるなら、${\displaystyle y}$ の選択肢は ${\displaystyle r-1}$ 個になる。定義から全ての ${\displaystyle x}$ と ${\displaystyle y}$ について ${\displaystyle d(x,y)\geq d}$ であるから、次が成り立つ。

${\displaystyle \sum _{x,y\in C}d(x,y)\geq M(M-1)d}$

また、${\displaystyle C}$ の符号語を並べた ${\displaystyle M\times n}$ の行列を ${\displaystyle A}$ とする（行が符号語に対応）。${\displaystyle A}$ の ${\displaystyle i}$番目の列にあるゼロの個数を ${\displaystyle s_{i}}$ とする。つまり、${\displaystyle i}$番目の行には ${\displaystyle M-s_{i}}$ 個の1がある。${\displaystyle d(x,y)=d(y,x)}$ であるため、${\displaystyle \sum _{x,y\in C}d(x,y)}$ という総和におけるある行の1や0の寄与は常に ${\displaystyle 2}$ である。従って、次が成り立つ。

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

${\displaystyle M}$ が偶数なら、右辺は ${\displaystyle s_{i}=M/2}$ のときに最大となり

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

となる。以上の ${\displaystyle \sum _{x,y\in C}d(x,y)}$ の上限と下限を組み合わせると、次式が導かれる。

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

${\displaystyle 2d>n}$ の場合、この式は次のように変形できる。

${\displaystyle M\leq {\frac {2d}{2d-n}}}$

${\displaystyle M}$ が偶数の場合なので、次が成り立つ。

${\displaystyle M\leq 2\lfloor {\frac {d}{2d-n}}\rfloor }$

一方、${\displaystyle M}$ が奇数なら ${\displaystyle s_{i}={\frac {M\pm 1}{2}}}$ のときに ${\displaystyle \sum _{i=1}^{n}2s_{i}(M-s_{i})}$ が最大化する。従って、次が成り立つ。

${\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}n(M^{2}-1)}$

以上の ${\displaystyle \sum _{x,y\in C}d(x,y)}$ の上限と下限を組み合わせると、次式が導かれる。

${\displaystyle M(M-1)d\leq {\frac {1}{2}}n(M^{2}-1)}$

または、${\displaystyle 2d>n}$ なら

${\displaystyle M\leq {\frac {2d}{2d-n}}-1}$

となる。Mは整数なので

${\displaystyle M\leq \lfloor {\frac {2d}{2d-n}}-1\rfloor =\lfloor {\frac {2d}{2d-n}}\rfloor -1\leq 2\lfloor {\frac {d}{2d-n}}\rfloor }$

となり、限界の証明が完了する。

• Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960.

• シングルトン限界
• ハミング限界
• ギルバート＝バルシャモフ限界
• ジョンソン限界