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

2021年7月30日

問 1. (7,4)ハミング符号の検査行列$H$が

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

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

　(1) 情報ビット [ 1 0 1 0 ] を(7,4)ハミング符号化した符号語ベクトルを求めなさい。

　(2) 誤りのある受信語ベクトル [ 1 1 0 1 0 1 1 ] の誤り訂正した符号語ベクトルを求めなさい。

問 2. 2元符号の誤り検出および訂正能力について以下の問いに答えなさい。

　(1) $2^m$重誤りを検出可能にするためには、符号の最小（ハミング）距離をどのようにすればよいか。

　(2) $2^m$重誤りを訂正可能にするためには、符号の最小（ハミング）距離をどのようにすればよいか。

問 3. 原始多項式を $f(X) = X^4 + X + 1$ とする拡大体 $GF(2^4)$ の元について、 $f(X)=0$の根を$\alpha$として、以下の問いに答えなさい。

　(1) べき表現 $\alpha^7$ の元に対する多項式表現を示しなさい。

　(2) べき表現 $\alpha^{12}$ の元に対する多項式表現を示しなさい。

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

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

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

問 5. $(17, k)$巡回ハミング符号（正整数 $k \leqq 16$）により符号化された符号語に対する受信語ベクトルが
　　[ 0 0 0 1 1 $a_5$ $a_6$ 1 1 0 1 1 0 1 1 0 1 ] （$a_5$、$a_6$は不明）
であるとき、以下の問いに答えなさい。

　(1) この符号の生成多項式として適切であるものを

$$\{ x^3+x^2+1, x^3+1, x^4+x^3+1, x^4+1, x^5+x^3+1, x^5+1 \}$$

　　から選び、それ以外が適切でない理由を説明しなさい。

　(2) $a_5$、$a_6$以外の受信語の各ビットに誤りがないものとして、 (1) で選んだ生成多項式を用いて $a_5$、$a_6$ を求めなさい。