プロトキン限界

プロトキン限界（英: 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.

関連項目 
シングルトン限界
ハミング限界
ギルバート＝バルシャモフ限界
ジョンソン限界

符号理論
数学に関する記事