プロトキン限界(英: Plotkin bound)とは、バイナリ符号のパラメータ(符号語の数)の限界値の1つ。
2進数の符号 の符号語の長さが 、すなわち の部分集合であるとする。 における最小ハミング距離を とすると、次が成り立つ。
ここで は と のハミング距離である。符号語の長さが で最小ハミング距離が のときの可能な最大符号語数を とする。
定理 (プロトキン限界):
が偶数で の場合、
が奇数で の場合、
が偶数の場合、
が奇数の場合、
となる。ここで は床関数を意味する。
と のハミング距離を とし、 に存在する符号語数を とする(つまり、 と は等しい)。するとプロトキン限界は、 について2種類の方法で限界を求めることで得られる。
まず として選択肢が 個あるなら、 の選択肢は 個になる。定義から全ての と について であるから、次が成り立つ。
また、 の符号語を並べた の行列を とする(行が符号語に対応)。 の 番目の列にあるゼロの個数を とする。つまり、番目の行には 個の1がある。 であるため、 という総和におけるある行の1や0の寄与は常に である。従って、次が成り立つ。
が偶数なら、右辺は のときに最大となり
となる。以上の の上限と下限を組み合わせると、次式が導かれる。
の場合、この式は次のように変形できる。
が偶数の場合なので、次が成り立つ。
一方、 が奇数なら のときに が最大化する。従って、次が成り立つ。
以上の の上限と下限を組み合わせると、次式が導かれる。
または、 なら
となる。Mは整数なので
となり、限界の証明が完了する。
- Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960.