2024年度　符号理論 試験問題

高知工科大学 情報学群

2024年 7月23日

試験の注意

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

問 1. $f(X) = X^5 + X^2 + 1$ を原始多項式とする有限体（ガロア体）$GF(2^5)$ について、以下の問いに答えなさい。 ただし、$f(X)=0$の根を$\alpha$とする。

(1)	べき表現 $\alpha^5$ の多項式表現を求めなさい。
(2)	べき表現 $\alpha^6$、$\alpha^8$ の多項式表現を求めなさい。
(3)	$X^3 + X^2 + 1$ と $X^3 + X$ の乗算をしなさい。

問 2. $p$を素数として、2元符号の最小（ハミング）距離が

$$d_{\min} = p$$    〔ビット〕 $$$$

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

(1)	この2元符号の誤り検出能力について説明しなさい。
(2)	この2元符号の誤り訂正能力について説明しなさい。

問 3. (10,6)ハミング符号の検査行列 $H$ が

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

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

(1)	情報ビット [ 0 1 0 1 0 1 ] を符号化した符号語ベクトルを求めなさい。
(2)	受信語ベクトル [ 1 0 0 0 1 0 0 0 0 1 ] の誤りの有無を調べ、 誤りが有る場合は誤り訂正した符号語ベクトルを求めなさい。

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

(1)	次の $GF(2)$上の多項式のうち、生成多項式として適しているものを選びなさい。 $$\{ x+1, x^2+x+1, x^3+x+1, x^3+x^2+x+1, x^4+x^3+1, x^5+x^3+1, x^6+x^5+1 \}$$
(2)	(1) で選んだ生成多項式を用いて、情報ビット ( 0 1 0 1 0 1 ) を巡回ハミング符号化した符号多項式を求めなさい。
(3)	(2) で求めた符号多項式に、誤り多項式 $E(x) = x^5$ を付加した受信多項式の誤りを訂正しなさい。

問 5. 生成多項式 $G(x) = 1 + x^2 + x^5$ を用いて構成された (9,4)巡回ハミング符号によって誤り訂正などする場合について、以下の問いに答えなさい。

(1)	[ 0 0 1 1 1 ? ? ? ? ] のように、 第1ビットから第5ビットはわかっているが、残りの4ビット（第6ビット以降）は不明な場合について、 正しい符号語を求めなさい。 ただし、第1ビットから第5ビットに誤りはないものとする。
(2)	この(9,4)巡回ハミングを使うと、何個まで不明なビットを復元可能か説明しなさい。
(3)	この(9,4)巡回ハミング符号の最小（ハミング）距離と誤り訂正能力について説明しなさい。