プロトキン限界

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

プロトキン限界: 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)xyハミング距離である。符号語の長さが 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床関数を意味する。

証明[編集]

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

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

 \sum_{x,y \in C} d(x,y) \geq M(M-1) d

また、C の符号語を並べた M \times n の行列を A とする(行が符号語に対応)。Ai番目の列にあるゼロの個数を 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} n M^2

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

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

関連項目[編集]