GRS符号
Generalized Reed-Solomon Code
集合$ Kから適当に、$ n(\gt k )個のベクトルを列として並べれば良い
$ K=\left\{\left(1, a, a^{2}, \cdots, a^{n-k-1}\right) \in \mathbb{F}_{q}^{n-k} \mid a \in \mathbb{F}_{q}\right\} \cup\left\{(0,0, \cdots, 0,1) \in \mathbb{F}_{q}^{n-k}\right\}
$ q+1種類の候補の中から$ n個を選んで列にする
例えば、$ a_1,\cdots,a_{n-1}\in\mathbb{F}_qを選ぶと$ Hは以下のようになる
$ H=\left[\begin{array}{ccccc}1 & 1 & \cdots & 1 & 0 \\a_{1} & a_{2} & \cdots & a_{n-1} & 0 \\a_{1}^{2} & a_{2}^{2} & \cdots & a_{n-1}^{2} & 0 \\\vdots & \vdots & \ddots & \vdots & \vdots \\a_{1}^{n-k-1} & a_{2}^{n-k-1} & \cdots & a_{n-1}^{n-k-1} & 1\end{array}\right]
最右列は、最下行が1であることに注意mrsekut.icon
具体例$ [6,3,4]_5 の検査行列を求める
よって、$ 0,1,2,3,4\in\mathbb{F}_5を選び以下のように構成できる
$ H=\begin{pmatrix}1&1&1&1&1&0 \\ 0&1&2&3&4&0 \\ 0^2&1^2&2^2&3^2&4^2&1\end{pmatrix}= \begin{pmatrix}1&1&1&1&1&0 \\ 0&1&2&3&4&0 \\ 0&1&4&4&1&1\end{pmatrix}
これは、$ a_iの順序が変わっていても等価
$ H=\begin{pmatrix}1&1&1&1&1&0 \\ 1&2&3&4&0&0 \\ 1^2&2^2&3^2&4^2&0^2&1\end{pmatrix}も同じ
$ P =S_2^2-S_1S_3
$ Q=S_1S_4-S_2S_3
$ R = S_3^2-S_2S_4
定理
$ \mathcal{C}がGRS符号$ \Leftrightarrow$ \mathcal{C}^\botがGRS符号
言い換えれば、$ Hの任意の$ n-k列でできる正方行列の行列式は必ず0にならない
任意の$ n-k列を選んで、並び替えてもok
Normal Rartional Curve, NRC
$ K=\left\{\left(1, a, a^{2}, \cdots, a^{k-1}\right) \in \mathrm{PG}(k-1, q) \mid a \in \mathbb{F}_{q}\right\} \cup\{(0,0, \cdots, 0,1)\}
$ 2\le k\le q
射影空間$ \mathrm{PG}(k-1,q)の$ q+1点集合$ Kのことを、正規有理曲線という $ PG(k-1,q)という図の中の(一つの、任意の)点を表すmrsekut.icon
$ K の$ n 点を列ベクトルとして並べてできる行列が生成する符号に等価な$ [n, k]_q 符号を長さ n の GRS 符号という
$ 2 ≤ k ≤ q のとき、MDS$ [n, k]_q 符号が存在する$ nの最大値は
$ k = 3or $ k = q − 1 かつ$ qが偶数$ (q = 2h, h ∈ \mathbb{N})の場合は$ q + 1、
それ以外は$ q + 1であると予想されている。
MDS符号$ [q + 1, 3]_q は、GRS符号として構成できる