プロトキン限界

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

定義

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

$d=\underset{x,y\in C,x\ne y}{\min }d(x,y)$

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

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

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

$A_2(n,d)\le 2\lfloor \frac{d}{2d-n}\rfloor$

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

$A_2(n,d)\le 2\lfloor \frac{d+1}{2d+1-n}\rfloor$

$d$ が偶数の場合、

$A_2(2d,d)\le 4d$

$d$ が奇数の場合、

$A_2(2d+1,d)\le 4d+4$

となる。ここで $\lfloor \rfloor$ は床関数を意味する。

証明

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

まず $x$ として選択肢が $r$ 個あるなら、$y$ の選択肢は $r-1$ 個になる。定義から全ての $x$ と $y$ について $d(x,y)\ge d$ であるから、次が成り立つ。

$\sum _{x,y\in C}d(x,y)\ge M(M-1)d$

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

$\sum _{x,y\in C}d(x,y)=\sum _{i=1}^{n}2s_i(M-s_i)$

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

$\sum _{x,y\in C}d(x,y)\le \frac{1}{2}n{M}^2$

となる。以上の $\sum _{x,y\in C}d(x,y)$ の上限と下限を組み合わせると、次式が導かれる。

$M(M-1)d\le \frac{1}{2}n{M}^2$

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

$M\le \frac{2d}{2d-n}$

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

$M\le 2\lfloor \frac{d}{2d-n}\rfloor$

一方、$M$ が奇数なら $s_i=\frac{M\pm 1}{2}$ のときに $\sum _{i=1}^{n}2s_i(M-s_i)$ が最大化する。従って、次が成り立つ。

$\sum _{x,y\in C}d(x,y)\le \frac{1}{2}n(M^2-1)$

以上の $\sum _{x,y\in C}d(x,y)$ の上限と下限を組み合わせると、次式が導かれる。

$M(M-1)d\le \frac{1}{2}n(M^2-1)$

または、$2d>n$ なら

$M\le \frac{2d}{2d-n}-1$

となる。Mは整数なので

$M\le \lfloor \frac{2d}{2d-n}-1\rfloor =\lfloor \frac{2d}{2d-n}\rfloor -1\le 2\lfloor \frac{d}{2d-n}\rfloor$

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

参考文献

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

関連項目

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