MDS符号
Maximum Distance Separable code
以下が成り立つ線形符号$ [n,k,d]_q のこと $ d= n-k+1を満たす
定理
$ [n,k]_q 符号$ \mathcal{C}の検査行列$ Hに対して $ \mathcal{C}:\mathrm{MDS}$ \Leftrightarrow$ Hは$ (n-k)-独立
$ \mathcal{C}:\mathrm{MDS} $ \Leftrightarrow $ H=[B,I_{n-k}] のとき、$ Bのどの部分正方行列も正則 $ [n,k]_q 符号$ \mathcal{C}に対して
$ \mathcal{C}:\mathrm{MDS}\Leftrightarrow \mathcal{C}^\bot:\mathrm{MDS}
$ \mathcal{C}:\mathrm{MDS}$ \Leftrightarrow$ \mathcal{C}の生成行列$ Gは$ k-独立 $ q が奇数のとき、MDS符号$ [n, 3]_q 符号が存在する$ nの最大値は$ q + 1
$ q が偶数 $ (q = 2h, h ∈ \mathbb{N}) のとき、MDS符号$ [n, 3]_q 符号が存在する$ n の最大値は$ q + 2
ググっても1件もヒットしない..mrsekut.icon
授業の20で見た
$ q が奇数のとき、MDS符号$ [q + 1, 3]_q 符号はGRS符号に限る 集合$ 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
他にもこんなのものも考えられる
$ H=\left[\begin{array}{cccc}1 & 1 & \cdots & 1 \\a_{1} & a_{2} & \cdots & a_{n} \\a_{1}^{2} & a_{2}^{2} & \cdots & a_{n}^{2} \\\vdots & \vdots & \ddots & \vdots \\a_{1}^{n-k-1} & a_{2}^{n-k-1} & \cdots & a_{n}^{n-k-1} \end{array}\right]
具体例$ [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}も同じ
MDS符号$ [n, 3]_q 符号の生成行列$ G = [G_1, G_2, \cdots, G_n] の各列を点$ P_i = {}^tG_i ∈ \mathrm{PG}(2, q)とみなして$ K = \{P_1, P_2,\cdots, P_n\} ⊂ \mathrm{PG}(2, q)とすると、$ Kはn-arcになる。
$ PG(2, q)のn-arcが存在する$ nの最大値は、
$ qが奇数のとき$ q + 1
$ qが偶数のとき$ q + 2