¾ðÊóÍýÏÀ

情報理論
第 11 回
情報理論
1 / 17
1
誤り訂正
シンドローム復号
ハミング符号
2
練習問題
情報理論
2 / 17
シンドローム
シンドローム
パリティ検査行列 H と受信語 y に対して，以下のように定義されるベク
トル s をシンドロームという．
sT = Hy T
問
次のパリティ検査行列 H を考える．


1 1 0 1 0 0
H= 1 0 1 0 1 0 
0 1 1 0 0 1
この H に対し，受信語 y = (0, 1, 1, 1, 0, 1) のシンドローム s を求めよ．
情報理論
3 / 17
シンドロームと誤りベクトル
シンドロームと誤りベクトル
1 つの誤りベクトル e に対して，シンドローム s が 1 つ決まる．
【証明】受信語が y = x + e とかけることより，
sT = Hy T = H(x + e)T = HxT + HeT
パリティ検査行列 H と符号語 x は HxT = 0 を満たすので，
sT = HeT
よって，1 つの e に対し，s は 1 つ決まる．
情報理論
4 / 17
シンドローム復号
シンドローム復号
1．各誤りベクトルに対し，s を sT = HeT により計算する．
2．受信語に対し，s を sT = Hy T により計算する．
3． 2 の s に対応する誤りベクトル e を 1 より求める．
4． y = x + e より，x を計算し復号する．
（注）この方法は 1 ビットのみの誤りを訂正するときに使うものである．
情報理論
5 / 17
シンドローム復号の例
【例】次のパリティ検査行列 H を考える．


1 1 0 1 0 0
H= 1 0 1 0 1 0 
0 1 1 0 0 1
この H に対し，1 ビットだけの誤りベクトルに対するシンドロームをそ
れぞれ求める．
誤りパターン
(1,0, 0, 0, 0, 0)
(0,1, 0, 0, 0, 0)
(0,0, 1, 0, 0, 0)
(0,0, 0, 1, 0, 0)
(0,0, 0, 0, 1, 0)
(0,0, 0, 0, 0, 1)
シンドローム
(1,1,0)
(1,0,1)
(0,1,1)
(1,0,0)
(0,1,0)
(0,0,1)
情報理論
6 / 17
シンドローム復号の例
【例の続き】
誤りパターン
(1,0, 0, 0, 0, 0)
(0,1, 0, 0, 0, 0)
(0,0, 1, 0, 0, 0)
(0,0, 0, 1, 0, 0)
(0,0, 0, 0, 1, 0)
(0,0, 0, 0, 0, 1)
シンドローム
(1,1,0)
(1,0,1)
(0,1,1)
(1,0,0)
(0,1,0)
(0,0,1)
y = (0, 1, 0, 1, 1, 1) を受信したとして，これを復号する．
s = Hy T = (0, 1, 0)
より，これに対応する誤りパターンは，(0, 0, 0, 0, 1, 0) となり，
x = y − e = (0, 1, 0, 1, 0, 1)
と復号できる．
情報理論
7 / 17
シンドローム復号
問
次のパリティ検査行列 H を考える．


1 0 1 1 0 0
H= 0 1 1 0 1 0 
1 1 0 0 0 1
(a) 受信語 y = (1, 0, 1, 1, 0, 1) を復号化せよ
(b) 受信語 y = (0, 1, 1, 1, 0, 1) を復号化せよ．
情報理論
8 / 17
ハミング符号
ハミング符号
符号 C に対する k × n 行列のパリティ検査行列の列ベクトルにおいて，
F2k の要素のうち零ベクトル以外の要素が全て現れている符号 C をハミ
ング符号という．
【例】次のパリティ検査符号をもつ符号はハミング符号である．


1 0 1 1 0 0 1
H= 0 1 1 0 1 0 1 
1 1 0 0 0 1 1
問
ハミング符号のパリティ検査行列 H の行数が 2 であるものを 1 つ作成
せよ．
情報理論
9 / 17
ハミング符号のパリティ検査行列
ハミング符号のパリティ検査行列の行数と列数の関係
ハミング符号のパリティ検査行列の行数を k ，列数を n とすると，以下
の関係が成り立つ．
n = 2k − 1
【証明】ハミング符号のパリティ検査行列の行数が k であるとすると，各
列には F2k から零ベクトルを除いた全ての要素が現れるので明らか．
情報理論
10 / 17
ハミング符号の復号
問
次のパリティ検査行列 H を考える．


1 0 1 1 1 0 0
H= 0 1 1 0 1 0 1 
1 1 1 0 0 1 0
(a) H をもつ符号はハミング符号かどうか答えよ．
(c) 受信語 y = (0, 1, 1, 1, 0, 1, 0) を復号化せよ．
情報理論
11 / 17
パリティ検査行列と生成行列
例題
次のパリティ検査行列 H をもつ線形符号 C の生成行列 G を求めよ．


1 0 1 1 1 0 0
H= 0 1 1 0 1 0 1 
1 1 1 0 0 1 0
情報理論
12 / 17
パリティ検査行列と生成行列
【解答】符号 v = (v1 , v2 , · · · , v7 ) とおく．Hv T = O より，
v1 + v3 + v4 + v5 = 0
v2 + v3 + v5 + v7 = 0
v1 + v2 + v3 + v6 = 0
全式を通して 1 度しか現れていない変数が v4 ，v6 ，v7 なので，
v4 = v1 + v3 + v5
v7 = v2 + v3 + v5
v6 = v1 + v2 + v3
つまり，v1 ，v3 ，v2 ，v5 が決まれば，v4 ，v7 ，v6 がそれぞれ決まるので，
v1 ，v3 ，v2 ，v5 を情報ベクトルと考える．
情報理論
13 / 17
パリティ検査行列と生成行列
【解答】
v4 = v1 + v3 + v5
v7 = v2 + v3 + v5
v6 = v1 + v2 + v3
あとは，v1 ，v2 ，v3 ，v5 を単位ベクトルして，G が 4 × 7 行列になること
に注意すれば，


1 0 0 1 0 1 0
 0 1 0 0 0 1 1 

G=
 0 0 1 1 0 1 1 
0 0 0 1 1 0 1
と求められる．
情報理論
14 / 17
パリティ検査行列と生成行列
問
次のパリティ検査行列 H をもつ線形符号 C

1 0 1 1 1
H= 0 1 1 0 1
1 1 1 0 0
情報理論
の生成行列 G を求めよ．

0
0 
1
15 / 17
練習問題
練習問題 1
次のパリティ検査行列 H をもつ線形符号 C の生成行列 G を求めよ．
[
]
1 1 0
(a)
H=
1 0 1


1 1 0 1 0 0
(b)
H= 0 1 1 0 1 0 
1 0 1 0 0 1


1 0 0 1
(c)
H= 0 0 1 1 
1 1 0 0
情報理論
16 / 17
練習問題
練習問題 2
次のパリティ検査行列 H をもつハミング符号 C を考える．


1 1 0 1 1 0 0
H= 1 1 1 0 0 1 0 
1 0 1 1 0 0 1
このとき，以下の問に答えよ．
(a) このハミング符号の生成行列 G を求めよ．
(b) 情報ベクトル (1, 1, 0, 1) に対する符号語を求めよ．
(c) 誤り (1, 0, 0, 0, 0, 0, 0) に対するシンドロームを求めよ．
(d) 受信語 y = (0, 1, 0, 1, 1, 0, 0) を復号せよ．
情報理論
17 / 17

Download Report