東京大学 情報理工学系研究科 電子情報学専攻 2015年8月実施 専門 第4問

标签：

• Tokyo-University
• Parity-Bit-Single-Error-Detection
• Hamming-74-Code-and-Minimum-Distance
• Interleaving-for-Burst-Error

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)

• 対応手法

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

• 利害得失

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