プロトキン縛り

符号理論の数学において、モリス・プロトキンにちなんで名付けられたプロトキン境界は、与えられた長さnと与えられた最小距離dのバイナリコードにおけるコードワードの最大可能数の制限 (または境界) です。

束縛の声明

符号語が2進アルファベット の記号を用いる場合、その符号は「2進」であるとみなされます。特に、すべての符号語が固定長nを持つ場合、2進符号の長さはnとなります。同様に、この場合、符号語は有限体上のベクトル空間の要素とみなすことができます。を の最小距離とします。すなわち、 ${\displaystyle \{0,1\}}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle d}$ ${\displaystyle C}$

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

ここで、 はと の間のハミング距離です。この式は、長さと最小距離 のバイナリコードで可能なコードワードの最大数を表します。プロトキン境界はこの式に制限を課します。 ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle n}$ ${\displaystyle d}$

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

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

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

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

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

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

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

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

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

ここで は床関数を表します。 ${\displaystyle \left\lfloor ~\right\rfloor }$

ケースiの証明

と のハミング距離を とし、の要素数を とします（したがって、は に等しい）。この上限は、2つの異なる方法で を上限とすることで証明されます。 ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle A_{2}(n,d)}$ ${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)}$

一方で、の選択肢があり、それぞれの選択肢に対しての選択肢がある。定義により、すべてのおよび( ) に対して、 ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M-1}$ ${\displaystyle y}$ ${\displaystyle d(x,y)\geq d}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\neq y}$

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

一方、を の要素を行とする行列とします。を の 列目に含まれるゼロの数とします。これは、列目に1が含まれることを意味します。同じ列にゼロと1が1つずつ含まれる場合、その合計はとなるため、 となります。したがって、 ${\displaystyle A}$ ${\displaystyle M\times n}$ ${\displaystyle C}$ ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle M-s_{i}}$ ${\displaystyle 2}$ ${\displaystyle d(x,y)=d(y,x)}$ ${\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}$

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

右辺の量が最大化されるのは、すべてに対して成り立つ場合のみである（証明のこの時点では、が整数であるという事実は無視する）。 ${\displaystyle s_{i}=M/2}$ ${\displaystyle i}$ ${\displaystyle s_{i}}$

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

先ほど導出した上限と下限を組み合わせると、 ${\displaystyle \sum _{(x,y)\in C,x\neq y}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\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

これで境界の証明が完了します。

参照

• ダイヤモンドコード
• エリアス・バサリゴは縛られる
• ギルバート・ヴァルシャモフ境界
• グリースマー行き
• ハミング境界
• ジョンソン行き
• シングルトン境界

参考文献

• プロトキン、モリス (1960). 「最小距離を指定したバイナリコード」. IRE Transactions on Information Theory . 6 (4): 445– 450. doi :10.1109/TIT.1960.1057584.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Plotkin_bound&oldid=1249382245"