プロトキン限界

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

定義

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

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

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

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

${\displaystyle d}$ が偶数で ${\displaystyle 2d>n}$ の場合、

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

${\displaystyle d}$ が奇数で ${\displaystyle 2d+1>n}$ の場合、

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

${\displaystyle d}$ が偶数の場合、

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

${\displaystyle d}$ が奇数の場合、

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

となる。ここで ${\displaystyle \left\lfloor \ \right\rfloor }$ は床関数を意味する。

証明

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

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

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

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

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

${\displaystyle M}$ が偶数なら、右辺は ${\displaystyle s_{i}=M/2}$ のときに最大となり

${\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}nM^{2}}$

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

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

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

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

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

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

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

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

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

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

または、${\displaystyle 2d>n}$ なら

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

となる。Mは整数なので

${\displaystyle 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.

関連項目

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