プロトキン縛り

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

コードワードがバイナリアルファベット のシンボルを使用する場合、コードは「バイナリ」と見なされます。特に、すべてのコードワードが固定長nを持つ場合、バイナリコードの長さは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)}$

ここで、は との間のハミング距離です。 この式は、長さと最小距離 のバイナリ コードで可能なコードワードの最大数を表します。 Plotkin 境界により、この式に制限が課されます。 ${\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 }$

をおよびのハミング距離とし、を の要素数とします(したがって、は に等しい)。この境界は、量を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 が含まれることを意味します。同じ列に 0 と 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 .}$

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

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

• Plotkin, Morris (1960)。「指定された最小距離を持つバイナリコード」。IRE Transactions on Information Theory。6 ( 4): 445–450。doi :10.1109/TIT.1960.1057584。