Griesmer符号

Griesmer限界の等号を満たす$ [n,k,d]_q 符号をGriesmer符号と言う

次元と最小距離が等しい$ [n_1,k,d]_q 符号$ \mathcal{C}_1 と$ [n_2,k,d]_q 符号$ \mathcal{C}_2では、$ n_1\lt n_2の場合、より早く情報を転送できるという意味で$ \mathcal{C}_1の方が良い符号といえる

$ n_q(k,d)

与えられた$ q,k,d の値に対して、$ [n,k,d]_q 符号が存在するような長さ$ nの最小値

$ n_q(k,d)\ge d+k-1であるが、Griesmer限界の方が実際の$ nの限界に近い

BelowタイプのGriesmer符号が存在するための条件

s重simplex符号以外の正整数$ dを

$ s=\lceil d/q^{k-1}\rceilと

①$ k-2\ge u_1\ge u_2\ge \cdots\ge u_t\ge0　

ただし同じ値の$ u_iはたかだか$ q-1個

を使って②$ d=sq^{k-1}-\sum^t_{i=1}q^{u_i}と表す

$ u,tは未知数であり、$ d,s,q,kはこの時点で確定している

よって条件①と、式②から$ u,tを求めることができる

このとき$ t\le sまたは$ \sum^{s+1}_{i=1}u_i\le sk-s-1ならば、

$ [g_q(k,d),k,d]_q 符号が存在する

補足

予め与えられているもの

$ q,k,d

未知数

$ s,u,t

例

$ q = 8, k = 4, d = 442 のとき、

最初の式より$ s = ⌈442/8^3]=1 が求まる

式②にわかっているものを代入すると

$ 442=8^3-\sum^t_{i=1}8^{u_i}

移項などして計算すると$ 70=\sum^t_{i=1}8^{u_i}が得られる

つまり、$ 8^○でこの等式が成り立つものを探す

今回は$ 8^2+8^0+8^0+8^0+8^0+8^0+8^0

よって$ t=7であり、$ u_1=2で$ u_2,..,u_7=0が得られる

よって$ t = 7 > s = 1、$ u_1 + u_2 = 2 = sk − s − 1 となり

上述の条件より$ [g_8(4, d) = 506, 4, 442]_8 符号が存在する。