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

2017年8月1日

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

　(1) $d$ 個までの誤り検出を可能にするために必要な最小ハミング距離の条件を示しなさい。

　(2) $c$ 個までの誤り訂正を可能にするために必要な最小ハミング距離の条件を示しなさい。

問 2. $GF(2)$ 上の多項式$x^3+x+1$ を原始多項式とする拡大体$GF(2^3)$ の元のべき表現と多項式表現の 対応表を示しなさい。

問 3. $x^3+x+1$ を生成多項式とする(7,4)巡回ハミング符号について次の問に答えなさい。

　(1) 情報多項式 $x^3 + x^2 + 1$ を符号化した符号語ベクトルを求めなさい。

　(2) 受信多項式 $x^6 + x^5 + x^3 + x^2$ の誤りの有無を調べ、訂正した符号語ベクトルを示しなさい。

問 4. 巡回組織符号のしくみを用いて (12,8)ハミング符号を生成するための以下の問いに答えなさい。

　(1) 生成多項式の選び方を説明し、適当な生成多項式を1つ示しなさい。

　(2) 高々7次の情報多項式 $I_8(x)=i_0 + i_1 x + i_2 x^2 + i_3 x^3 + i_4 x^4 + i_5 x^5 +i_6 x^6 + i_7 x^7$ から、 (1)で選んだ生成多項式を用いて符号多項式$F_{12}(x)$ を求める方法を説明しなさい。

問 5. (7,4)ハミング符号の生成行列$G$ と検査行列$H$ がそれぞれ

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

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

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

　(1) 情報ビット [ 1 1 0 1 ] を符号化した符号語ベクトルを求め、 組織符号になっていることを確認しなさい。

　(2) 誤りのある受信語ベクトル [ 0 0 1 1 1 1 1 ] の誤り訂正した符号語を求め、 正しいと推定される情報ビットを示しなさい。