プロトキン限界のソースを表示

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

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

:<math>d = \min_{x,y \in C, x \neq y} d(x,y)</math> 

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

<strong>定理 （プロトキン限界）:</strong>

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

:<math> A_{2}(n,d) \leq 2 \left\lfloor\frac{d}{2d-n}\right\rfloor </math>

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

:<math> A_{2}(n,d) \leq 2 \left\lfloor\frac{d+1}{2d+1-n}\right\rfloor </math>

<math>d</math> が偶数の場合、

:<math> A_{2}(2d,d) \leq 4d </math>

<math>d</math> が奇数の場合、

:<math> A_{2}(2d+1,d) \leq 4d+4 </math>

となる。ここで <math>\left\lfloor \ \right\rfloor</math> は[[床関数]]を意味する。

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

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

:<math> \sum_{x,y \in C} d(x,y) \geq M(M-1) d </math>

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

:<math> \sum_{x,y \in C} d(x,y) = \sum_{i=1}^n 2s_i (M-s_i)</math>

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

:<math> \sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n M^2</math>

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

:<math> M(M-1) d \leq \frac{1}{2} n M^2</math>

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

:<math> M \leq \frac{2d}{2d-n}</math>

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

:<math> M \leq 2 \lfloor \frac{d}{2d-n} \rfloor </math>

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

:<math> \sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n (M^2-1)</math>

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

:<math> M(M-1) d \leq \frac{1}{2} n (M^2-1)</math>

または、<math>2d > n</math> なら

:<math> M \leq \frac{2d}{2d-n} - 1</math>

となる。Mは整数なので

:<math> M \leq \lfloor \frac{2d}{2d-n} - 1 \rfloor = \lfloor \frac{2d}{2d-n} \rfloor -1 \leq 2 \lfloor \frac{d}{2d-n} \rfloor </math>

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

== 参考文献 ==
*<em>Binary codes with specified minimum distance,</em> M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960. 

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

{{DEFAULTSORT:ふろときんけんかい}}

[[Category:符号理論]]
[[Category:数学に関する記事]]