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

2011年 7月29日

問 1. 最小ハミング距離が$d$ビットであるような2元符号では、何ビットまで誤り検出および誤り訂正が可能であるかを示しなさい。

問 2. 巡回符号がCRC(Cyclic redundancy check)と呼ばれて、パケット通信などでの誤り検出に広く利用されている理由を説明しなさい。

問 3. $GF(2)$上の既約多項式 $x^3 + x^2 + 1$ について $x^3 + x^2 + 1 = 0$ の根を $\alpha$ とすると、 0 と $\alpha$ のべき（ $\alpha^i (i = 0, 1, 2, \cdots, 6)$）で$GF(2^3)$の元をすべて表現できることを示しなさい。

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

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

　 (2) 受信語[ 0 0 1 0 1 0 0 ] の誤りの有無を調べ、誤りがある場合には訂正しなさい。

問 5. (7,4)ハミング符号の生成行列$G$が

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

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

　 (1) 次の情報ビットを符号化しなさい。

　　 (a) [ 0 1 1 0 ]

　　 (b) [ 1 1 1 1 ]

　 (2) 次の受信語に対する正しい情報ビットを推定しなさい。

　　 (A) [ 0 1 1 1 1 1 0 ]

　　 (B) [ 0 1 1 1 0 0 1 ]