東京大学 情報理工学系研究科 電子情報学専攻 2016年度 専門 第4問

Author

diohabara

Description

(1) 情報ピット \(x_1,x_2,x_3,x_4\) の \(4\) ピットの符号に対して \(1\) ピットの検査ピット \(x_5\) を付加する。単一誤りを検出することが可能であるような \(x_5\) の生成方法を述べよ。

(2) (1) の符号の符号語 \((0,0,0,0,0)\) と他の符号語の間の最小ハミング距離を求めよ。また, \((0,0,0,0,0)\) とのハミング距離が最小ハミング距離となる符号語を一つ示せ。

(3) \((7,4)\) ハミング符号においては, 情報ビット \(x_1,x_2,x_3,x_4\) に対して検査ビット \(x_5,x_6,x_7\) を

\[ \begin{aligned} x_5 &= x_1 + x_2 + x_4 \\ x_6 &= x_2 + x_3 + x_4 \\ x_7 &= x_1 + x_2 + x_3 \\ \end{aligned} \]

 を用いて生成し, \((x_1,x_2,x_3,x_4,x_5,x_6,x_7)\) という符号語に符号化する。ここで, "+"は排他的倫理和の演算である。全ての符号語を表にして記せ。

(4) (3)の表を用いて, 符号語 \((0,0,0,0,0,0,0)\) と他的符号語の間の最小ハミング距離を求めよ。

(5) 最小ハミング距離を利用して,(1) で設計した符号と \((7,4)\) ハミング符号が, それぞれ最大何ビットの誤りまで訂正可能であるかを示せ。

(6) 一般にハミング符号は, 同一のピット誤り率であっても, バースト誤りの場合にはランダム誤りの場合よりも性能が劣化する。バースト誤りに対応する手法とその利害得失を論ぜよ。

Kai

(1)

\(x_5 = x_1 \oplus x_2 \oplus x_3 \oplus x_4\) とすればよい。\(x_1, \dots ,x_4\) のどれか \(1\) つが反転した際に \(x_5\) は \(1\) となり検出ができる。

(2)

情報ビットの \(1\) の個数が奇数のとき、検査ビットは \(1\) となる。よって、情報ビットの \(1\) の個数が最小の \(1\) のとき検査ビットは \(1\) となり \((0, 0, 0, 0, 0)\) とのハミング距離は \(2\) となる。情報ビットの \(1\) の個数が偶数のとき、検査ビットは \(0\) となる。よって、情報ビットの \(1\) の個数が \(0\) を除いて最小の \(2\) のとき検査ビットは \(0\) となり \((0, 0, 0, 0, 0)\) とのハミング距離は \(2\) となる。よって最小ハミング距離は \(2\) であり、その符号語の \(1\) つに \((1, 1, 0, 0, 0)\) が挙げられる。

(3)

すべての符号語を表にすると以下の通り。

\(x_1\)	\(x_2\)	\(x_3\)	\(x_4\)	\(x_5\)	\(x_6\)	\(x_7\)
0	0	0	0	0	0	0
0	0	0	1	1	1	0
0	0	1	0	0	1	1
0	0	1	1	1	0	1
0	1	0	0	1	1	1
0	1	0	1	0	0	1
0	1	1	0	1	0	0
0	1	1	1	0	1	0
1	0	0	0	1	0	1
1	0	0	1	0	1	1
1	0	1	0	1	1	0
1	0	1	1	0	0	0
1	1	0	0	0	1	0
1	1	0	1	1	0	0
1	1	1	0	0	0	1
1	1	1	1	1	1	1

(4)

表で \(1\) の個数が最小のものを探せば良く、\(3\)。

(5)

最小ハミング距離 \(d_H\) に対して \(2d + 1 \le d_H\) となる最大の整数 \(d\) を考える。このとき、\(d\) ビットの誤り訂正が可能。

• (1) の場合、最小ハミング距離は \(2\) なので \(d = 0\) となる。すなわち誤り訂正はできない

• (3) の場合、最小ハミング距離は \(3\) なので \(d = 1\) となる。したがって、\(1\) ビットの誤りまでなら誤り訂正が可能。

(6)

• 対応手法

短い区間に多数の誤りが集中するバースト誤りに対して、符号の順序を入れ替え、同じブロックのデータを分散させ、ある区間に誤りが集中しないようにする。

• 利害得失

バースト誤りの訂正が可能になるという利点がある。一方で伝送速度が犠牲になるという欠点がある。