プロトキン限界
従って、次が成り立つ。
∑ x , y ∈ C d ( x , y ) ≤ 1 2 n ( M 2 − 1 ) {\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}n(M^{2}-1)}
以上の ∑ x , y ∈ C d ( x , y ) {\displaystyle \sum _{x,y\in C}d(x,y)} の上限と下限を組み合わせると、次式が導かれる。
M ( M − 1 ) d ≤ 1 2 n ( M 2 − 1 ) {\displaystyle M(M-1)d\leq {\frac {1}{2}}n(M^{2}-1)}
または、 2 d > n {\displaystyle 2d>n} なら
M ≤ 2 d 2 d − n − 1 {\displaystyle M\leq {\frac {2d}{2d-n}}-1}
となる。Mは整数なので
M ≤ ⌊ 2 d 2 d − n − 1 ⌋ = ⌊ 2 d 2 d − n ⌋ − 1 ≤ 2 ⌊ d 2 d − n ⌋ {\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 }
となり、限界の証明が完了する。
プロトキン限界(英: Plotkin bound)とは、バイナリ符号のパラメータ(符号語の数)の限界値の1つ。