符号理論　試験問題（2016年度）

2016年8月2日

問 1. $f_3(X) = X^4 + 1$ を $GF(3)$上の多項式とする。 $f_3(X) = 0$ は $GF(3)$上で根を持たないが、 この $f_3(X)$ が拡大体 $GF(3^4)$ の原始多項式として適当であるかどうかについて答え、その理由を説明しなさい。

問 2. 2元符号の誤り検出・訂正能力と符号の最小ハミング距離について以下の問いに答えなさい。

　(1) 誤り検出を$e_d$ビットまで可能にするためには最小ハミング距離を何ビット以上にすればよいか

　(2) 誤り訂正を$e_c$ビットまで可能にするためには最小ハミング距離を何ビット以上にすればよいか

問 3. ハミング符号の（パリティ）検査行列$H$が

$$H = \left[ \begin{array}{rrrrrrrrrrrrrrr} 0 & 0 & 0 & 0 & 1 &... ... & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{array} \right]$$

で与えられるとき、以下の問に答えなさい。

　(1) 次の情報ビットを符号化した符号語を求めなさい。

　　　[ 1 0 1 0 1 0 1 0 1 0 1 ]

　(2) 次の受信語に対して正しいと推定される情報ビットを求めなさい。

　　　[ 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 ]

問 4. $GF(2)$上の3次既約多項式を1つ選び、それを原始多項式とする拡大体$GF(2^3)$の元の べき表現と多項式表現の対応表を示しなさい。

問 5. 問 4.で選んだ既約多項式を生成多項式とする(7,4)巡回符号（巡回ハミング符号）に ついて次の問に答えなさい。

　(1) 情報ビット[ 1 1 1 1 ] を符号化した符号語を求めなさい。

　(2) 受信語[ 1 0 1 0 1 0 1 ] の誤りの有無を調べ、誤りがある場合には訂正しなさい。