プロトキン限界

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

定義

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

$d=\min _{x,y\in C,x\neq y}d(x,y)$

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

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

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

$A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor$

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

$A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor$

$d$ が偶数の場合、

$A_{2}(2d,d)\leq 4d$

$d$ が奇数の場合、

$A_{2}(2d+1,d)\leq 4d+4$

となる。ここで $\left\lfloor \ \right\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)\geq d$ であるから、次が成り立つ。

$\sum _{x,y\in C}d(x,y)\geq 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)\leq {\frac {1}{2}}nM^{2}$

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

$M(M-1)d\leq {\frac {1}{2}}nM^{2}$

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

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

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

$M\leq 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)\leq {\frac {1}{2}}n(M^{2}-1)$

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

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

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

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

となる。Mは整数なので

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

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

参考文献

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

関連項目

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