グリースマー行き

符号理論の数学において、グリースマー境界は、ジェームズ・ヒューゴ・グリースマーにちなんで名付けられた、次元kおよび最小距離dの線形バイナリ符号の長さの境界です。非バイナリ符号にも非常によく似たバージョンがあります。

バイナリ線形コードの場合、グリースマー境界は次のようになります。

${\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

次元kと距離dのバイナリコードの最小の長さを表す。Cをそのようなコードとする。次のことを示したい。 ${\displaystyle N(k,d)}$

${\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

G をCの生成行列とします。Gの最初の行は常に重みdを持つr  = (1, ..., 1, 0, ..., 0)の形式であると仮定できます。

${\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}$

行列はコード を生成し、これは の残差コードと呼ばれます。は明らかに次元を持ち、長さは距離を持ちますが、それはわかりません。が となるとします。連結が となるベクトルが存在し、となると となります。一方、 と は線形であるため、も となります。しかし ${\displaystyle G'}$${\displaystyle C'}$${\displaystyle C.}$ ${\displaystyle C'}$${\displaystyle k'=k-1}$${\displaystyle n'=N(k,d)-d.}$ ${\displaystyle C'}$${\displaystyle d',}$${\displaystyle u\in C'}$${\displaystyle w(u)=d'}$${\displaystyle v\in \mathbb {F} _{2}^{d}}$${\displaystyle (v|u)\in C.}$${\displaystyle w(v)+w(u)=w(v|u)\geqslant d.}$${\displaystyle (v|u)+r\in C,}$${\displaystyle r\in C}$${\displaystyle C}$${\displaystyle w((v|u)+r)\geqslant d.}$

${\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=dw(v)+w(u),}$

となる。これを と足し合わせるととなる。しかしとなる。は積分なのでとなる。これはつまり ${\displaystyle dw(v)+w(u)\geqslant d}$${\displaystyle w(v)+w(u)\geqslant d,}$${\displaystyle d+2w(u)\geqslant 2d}$${\displaystyle w(u)=d',}$${\displaystyle 2d'\geqslant d.}$${\displaystyle d'}$${\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .}$

${\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}$

となることによって

${\displaystyle N(k,d)\geqslant d+N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right).}$

kについての帰納法により、最終的に

${\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$

どのステップでも次元は1ずつ減少し、距離は半分になることに注意してください。

${\displaystyle \left\lceil {\frac {\left\lceil a/2^{k-1}\right\rceil }{2}}\right\rceil =\left\lceil {\frac {a}{2^{k}}}\right\rceil }$

任意の整数aと正の整数kに対して。

上の線形コードの場合、グリースマー境界は次のようになります。 ${\displaystyle \mathbb {F} _{q}}$

${\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{q^{i}}}\right\rceil .}$

証明はバイナリの場合と同様なので省略します。

• エリアス・バサリゴは拘束される
• ギルバート＝ヴァルシャモフ境界
• ハミング境界
• ジョンソン行き
• プロトキン縛り
• シングルトンバウンド

• JH Griesmer、「誤り訂正符号の限界」、IBM Journal of Res. and Dev.、第 4 巻、第 5 号、pp. 532-542、1960 年。