2023年度　符号理論 試験問題

高知工科大学 情報学群

2023年 7月25日

試験の注意

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

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

(1)	べき表現 $\alpha^4$ の多項式表現を求めなさい。
(2)	べき表現 $\alpha^5$、$\alpha^6$、$\alpha^7$ の多項式表現を求めなさい。

問 2. $m$を正整数（自然数）として、2元符号の最小（ハミング）距離が

$$d_{\min} = 2^m + 1$$    〔ビット〕 $$(m=1,2,\cdots)$$

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

(1)	$m=2$のとき、誤り検出は何ビットまで可能か求めなさい。
(2)	誤り訂正は何ビットまで可能か求めなさい。

問 3.  (8,4)ハミング符号の情報ビットを [ $x_1$ $x_2$ $x_3$ $x_4$ ]として、 検査ビット [ $p_1$ $p_2$ $p_3$ $p_4$ ]が

$$\left[ \begin{array}{r} p_1 \\ p_2 \\ p_3 \\ p_4 \end{array} \... ...ght] \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right]$$

により求められるとき、以下の問いに答えなさい。
ただし、符号語ベクトルは [ $p_1$ $p_2$ $p_3$ $p_4$ $x_1$ $x_2$ $x_3$ $x_4$ ]のように示されるものとしなさい。

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

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

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

問 5.  10ビットの情報ビットに対して巡回ハミング符号を用いて誤り訂正や誤り検出する場合について、
以下の問いに答えなさい。

(1)	この巡回組織符号の生成多項式として $x^4 + x + 1$ が適していることを説明しなさい。
(2)	(1) で示した生成多項式を用いたときに、CRCにより誤りを検出できる場合について説明しなさい。
(3)	(1) で示した生成多項式より次数を1大きくした（5次）生成多項式を用いると、 誤り訂正能力と CRCによる誤り検出能力はそれぞれどのように変わるか説明しなさい。