プロトキン限界

プロトキン限界（英: Plotkin bound）とは、バイナリ符号のパラメータ（符号語の数）の限界値の1つ。
定義.
2進数の符号 formula_1 の符号語の長さが formula_2、すなわち formula_3 の部分集合であるとする。formula_1 における最小ハミング距離を formula_5 とすると、次が成り立つ。
ここで formula_7 は formula_8 と formula_9 のハミング距離である。符号語の長さが formula_2 で最小ハミング距離が formula_5 のときの可能な最大符号語数を formula_12 とする。
定理 （プロトキン限界）:
formula_5 が偶数で formula_14 の場合、
formula_5 が奇数で formula_17 の場合、
formula_5 が偶数の場合、
formula_5 が奇数の場合、
となる。ここで formula_23 は床関数を意味する。
証明.
formula_8 と formula_9 のハミング距離を formula_7 とし、formula_1 に存在する符号語数を formula_28 とする（つまり、formula_28 と formula_12 は等しい）。するとプロトキン限界は、formula_31 について2種類の方法で限界を求めることで得られる。
まず formula_8 として選択肢が formula_33 個あるなら、formula_9 の選択肢は formula_35 個になる。定義から全ての formula_8 と formula_9 について formula_38 であるから、次が成り立つ。
また、formula_1 の符号語を並べた formula_41 の行列を formula_42 とする（行が符号語に対応）。formula_42 の formula_44番目の列にあるゼロの個数を formula_45 とする。つまり、formula_44番目の行には formula_47 個の1がある。formula_48 であるため、formula_49 という総和におけるある行の1や0の寄与は常に formula_50 である。従って、次が成り立つ。
formula_28 が偶数なら、右辺は formula_53 のときに最大となり
となる。以上の formula_55 の上限と下限を組み合わせると、次式が導かれる。
formula_57 の場合、この式は次のように変形できる。
formula_28 が偶数の場合なので、次が成り立つ。
一方、formula_28 が奇数なら formula_62 のときに formula_63 が最大化する。従って、次が成り立つ。
以上の formula_55 の上限と下限を組み合わせると、次式が導かれる。
または、formula_67 なら
となる。Mは整数なので
となり、限界の証明が完了する。