2022年度　符号理論 試験問題

高知工科大学 情報学群

2022年 7月26日

試験の注意

• 不明な点がある場合は、手をあげて申し出てください。
• 解答は指定の解答用紙の解答欄に記入してください。
  なお、解答用紙には答えのみではなく答えに至る過程を必ず記してください。 過程まで正しく記述されているものに限り採点の対象とします。
• 受験の際は、机上の見やすい場所に「学生証」を置いてください。
• 「学生証」を忘れた者は、教務課で仮学生証の交付を受けてください。
• 教員が指示したもの以外は、机の上に置いてはいけません（試験に不要なものは、カバン等に入れて床に置くこと）。
• 自筆ノート、指定教科書、計算用紙、筆記用具等のみ持ち込みを認めます。
  それ以外の書籍、印刷・コピーしたもの、情報通信機器は認めません。
• 不正（持ち込み制限違反、発声、のぞき見、物品授受、他者との情報のやり取り（カンニング行為）、その他、試験に際しての不適切な行為）は厳重に処分します。
• 不正行為を行った場合は、2クォータおよび1学期に履修したすべての授業科目の単位の認定が取り消されます。

問 1. (12,8)ハミング符号の検査行列$H$、生成行列$G$ がそれぞれ

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

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

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

　(1) 誤りのある受信語ベクトル [ 1 1 0 0 1 0 1 0 1 1 1 1 ] に対して、誤り訂正した情報ビットを求めなさい。

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

問 2. $m$を正整数（自然数）とするとき、2元符号の誤り検出および訂正能力について以下の問いに答えなさい。

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

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

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

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

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

問 4. 8ビットの情報ビットを符号化率がもっとも高くなるように巡回ハミング符号で符号化する場合について、以下の問いに答えなさい。

　(1) 次の多項式のうち、生成多項式として適しているものを選びなさい。

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

　(2) (1) で選んだ生成多項式を用いて、情報ビット ( 1 0 1 0 1 0 1 1 ) を巡回ハミング符号化した符号多項式を求めなさい。

　(3) (2) で求めた符号語に、誤りパターン ( 0 0 0 0 0 0 0 0 0 1 0 0 ) を付加した受信語の誤りを訂正しなさい。

問 5. 12ビットの情報ビットに対して CRC により誤り検出する場合について、以下の問いに答えなさい。

　(1) CRC のための巡回符号化に適した生成多項式を1つ選び、その理由を説明しなさい。

　(2) (1) で選んだ生成多項式で生成される巡回符号を用いた場合の、5個以下（5重以下）の誤りを検出できる場合について説明しなさい。

　(3) (1) で選んだ生成多項式で生成される巡回符号の符号長を$n$とした場合に、この符号により検出される長さ$(n-11)$ビットのバースト誤りの誤り多項式を求めなさい。