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

Author

diohabara

Description

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

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

(3) ハミング符号においては, 情報ビット に対して検査ビット を

 を用いて生成し, という符号語に符号化する。ここで, "+"は排他的倫理和の演算である。全ての符号語を表にして記せ。

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

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

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

Kai

(1)

とすればよい。 のどれか つが反転した際に は となり検出ができる。

(2)

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

(3)

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

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)

表で の個数が最小のものを探せば良く、。

(5)

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

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

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

(6)

• 対応手法

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

• 利害得失

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