生成行列 - mrsekut-p

生成行列

$ Gで表す

$ k\times n行列

$ k行が$ Cの基底を成す

全ての符号語を生成する (後述)

$ q^k個

生成行列を$ [I_k, A] の形に変形した行列

左側が$ k次の単位行列

$ Aは$ k\times (n-k)行列

例えば、$ \begin{pmatrix}{1}& {0}& {1}&{1}&{1} \\ {0}&{1}&{1}&{2}&{2}\end{pmatrix}

どういう形をしている?

$ k\times nの行列

標準形の場合は$ [I_k, A] の形

標準形でない場合はそれ以外の特徴はない

生成行列が与えられていると何が嬉しい？

$ nと$ kがわかる

$ Gは$ k\times n行列

$ [n,k]_q 符号を全て求めることができる

$ qは与えられているはず。

全符号は$ 1\times nのベクトルで、全部で$ q^k個ある

求め方

$ q元線形符号は$ (0,0)G,$ (0,1)G,..,$ (q-1,q-1)Gで求められる

↑は$ k=2なので$ (0,0),..書いてるが、$ k=3なら$ (0,0,0),..

例えば、3元線形符号$ Cの生成行列$ \begin{pmatrix} 1&2&0&2&0 \\ 2&2&1&0&2\end{pmatrix}が与えられた時を考える

つまり、$ q=3

まずこれを標準形に直す$ \begin{pmatrix}1&0&1&1&2 \\ 0&1&1&2&2\end{pmatrix}

この標準形の1行目を$ c_1、2行目を$ c_2とする

$ \lambda_1 c_1 + \lambda_2 c_2を以下のようにして考えることで、全ての符号が求まる

$ q=3なので、$ (\lambda_1, \lambda_2)=(0,0),(0,1),(0,2),(1,0),..,(2,2)の$ q^k通りある

この計算をする時に、標準形に直してからやらないと

$ (\lambda_1, \lambda_2)=(0,0),(1,1),(2,2)が全て等しくなってしまい、ちゃんと求まらない

どうやって求める

$ Cの符号語が全て与えられている時

$ \begin{pmatrix}1&0&0&1\end{pmatrix}, $ \begin{pmatrix}0&1&0&1\end{pmatrix},$ \begin{pmatrix} 0&0&1&1\end{pmatrix}

のように、上下に重ねると単位行列になるようなものを$ k個探して重ねる

$ kは$ |C|=q^kから求まる

反復符号と長さ$ nが与えられている時

生成行列は$ 1\times nで、要素が全て1の行列になる

検査行列が与えられている時

検査行列は$ H=[-{}^t\!A, I_{n-k}] の形をしているので、それを$ G=[I_k, A] の形に変形すればいい

$ [n,k,d]_q だけ与えられているとき

ref 18.3