プロトキン限界

ウィキペディア

プロトキン限界

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/09/23 19:30 UTC 版)

プロトキン限界（英: Plotkin bound）とは、バイナリ符号のパラメータ（符号語の数）の限界値の1つ。

定義

2進数の符号 C の符号語の長さが n、すなわち の部分集合であるとする。C における最小ハミング距離を d とすると、次が成り立つ。

ここで d(x,y) は x と y のハミング距離である。符号語の長さが n で最小ハミング距離が d のときの可能な最大符号語数を A₂(n,d) とする。

定理 （プロトキン限界）:

d が偶数で 2d > n の場合、

d が奇数で 2d + 1 > n の場合、

d が偶数の場合、

d が奇数の場合、

となる。ここで は床関数を意味する。

証明

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

まず x として選択肢が r 個あるなら、y の選択肢は r − 1 個になる。定義から全ての x と y について であるから、次が成り立つ。

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

M が偶数なら、右辺は s_i = M / 2 のときに最大となり

となる。以上の の上限と下限を組み合わせると、次式が導かれる。

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

M が偶数の場合なので、次が成り立つ。

一方、M が奇数なら のときに が最大化する。従って、次が成り立つ。

以上の の上限と下限を組み合わせると、次式が導かれる。

または、2d > n なら

となる。Mは整数なので

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

参考文献

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

関連項目

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