Information Theory

次回予告
6/2
June 2
lecture 30min
講義30分
test 60min
試験60分
you can bring books & PC
本,PC等の持込み可
use of a calculator recommended
電卓の使用を推奨
この後は...
前回の復習
練習問題の解答
今日の内容
0
前回の復習:線形符号と生成行列
線形符号:情報記号の線形式で検査記号を定義
符号語 = 1 , 2 , … ,  , 1 , 2 , … , 
 = ,1 1 + ,2 2 + ⋯ +,  (, = 0 or 1)
生成行列:符号化のための便利な道具
1 , …  , 1 , … , 
1 ⋯ 0 1,1
符号語
⋮
= 1 , … ,  ⋮ ⋱ ⋮
0 ⋯ 1 1,
符号化したいデータ
 × 単位行列
生成行列
⋯ ,1
⋱
⋮
⋯ ,
検査記号定義式の
係数行列の転置
1
練習問題
情報記号(1 , 2 , 3 )に対し,
1 = 1 +2 +3
2 = 1 +2
3 = 1
+3
とし,(1 , 2 , 3 , 1 , 2 , 3 )を符号語と定義する.
この符号の生成行列を求めよ
この符号の符号語をすべて列挙せよ
p.31 のような符号化器を示せ
2
練習問題の解答例
1 = 1 +2 +3
2 = 1 +2
3 = 1
+3
係数行列
転置
生成行列 
111
110
101
111
110
101
100111
010110
001101
符号語を列挙: 1 , 2 , 3 = 0,0,0 , … , (1,1,1)をに掛けると,
000000,
001101,
010110,
011011,
100111,
101010,
110001,
111100.
1
2
3
1 2 3 1
2
3
3
本日の講義内容
線形符号
定義と基本的な性質
線形符号の符号化
線形符号の復号
ハミング符号
線形符号の性能評価
前回
今回
4
線形符号の復号
アプリケーション
送信者
受信者
情報源符号化
符号化
復号
情報保護
暗号化
復号
通信路符号化
符号化
復号
符号語
 ∈ を送信
通信路
を受信
【誤り検出】  ∈ か否かを判定する
【誤り訂正】 に一番近い符号語 ′ ∈ を求める
5
「復号」と生成行列
復号...「どのように符号化されたか」が重要
水平垂直パリティ検査符号:(1 , 2 , 3 , 4 , 1 , 2 , 3 , 4 , 5 )
1
1 = 1 +2
2 =
3 +4
3 = 1
+3
4 =
2
+4
5 = 1 +2 +3 +4
2 1
3 4 2
3
4 5
=
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
6
符号語であるための条件(1)
符号化の計算:
1
0
(1 , … 4 , 1 , … , 5 ) = (1 , … , 4 )
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
受信系列  = (1 , … , 9 )が符号語... 1 , … , 9 ∈ 
5 = 1 +2
6 =
3+4
7 = 1
+3
2
+4
必要十分条件 8 =
9 = 1 +2+3 +4
7
符号語であるための条件(2)
各左辺を右辺に移項すると...
5 = 1 +2
6 =
3+4
7 = 1
+3
8 =
2
+4
9 = 1 +2+3 +4
−5
=0
−6
3+4
=0
−7
1
+3
=0
−8
=0
2
+4
−9 = 0
1 +2+3 +4
1 +2
2進演算: −  =  + 
1 , … , 9 ∈ 
+5
=0
+6
3+4
=0
+7
1
+3
=0
+8
=0
2
+4
+9 = 0
1 +2+3 +4
1 +2
パリティ検査方程式
8
符号語であるための条件(3)
+5
=0
+6
3+4
=0
+7
1
+3
=0
+8
=0
2
+4
+9 = 0
1 +2+3 +4
1 +2
1 , … , 9 ∈ 
1
0
1
0
1
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
⋮ =
9
0
0
0
0
0
9
検査行列
1
0
1
0
1
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
⋮ =
9
0
0
0
0
0
検査行列 
系列  が符号語か否かを検査したいときは...
検査行列  の右から, の転置ベクトルを乗ずる
T =  ...  ∈ 
【誤り検出】
T
 ≠  ...  ∉ 
10
検査行列を用いた誤り検出
水平垂直パリティ検査符号
• 110101101 は符号語か? yes
1

0
1

0
1

1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0

 
0
0
0 1 1 0 1 0 1 1 0 1T   0 

 
0
0
0
1 
 
• 011011010 は符号語か? no
1

0
1

0
1

1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0

 
0
0
0 0 1 1 0 1 1 0 1 0T   1 

 
0
0
0
1 
 
11
生成行列と検査行列
検査記号の定義式
p1 = a1,1x1 + a1,2x2 + ... + a1,kxk
p2 = a2,1x1 + a2,2x2 + ... + a2,kxk
:
pm = am,1x1 + am,2x2 + ... + am,kxk
a1,1x1 + a1,2x2 + ... + a1,kxk + p1
a2,1x1 + a2,2x2 + ... + a2,kxk
+ p2
:
am,1x1 + am,2x2 + ... + am,kxk
生成行列
0  0 a1,1 a2,1  am,1 

1  0 a1,2 a2,2  am,2 
   
   

0  1 a1,k a2,k  am,k 
+ pm = 0
検査行列
n-k行
k行
1

0


0

=0
=0
単位行列 係数を転置した行列
 a1,1

 a2,1
 

a
 m,1
a1,2  a1,k
a 2, 2  a 2, k
  
am, 2  am, k
係数行列
1 0  0

0 1  0
   

0 0  1 
単位行列
12
生成行列と検査行列(実例)
水平垂直パリティ検査符号:  = 9,  = 4,  =  −  = 5
1
2 1
1 = 1 +2
2 =
3 +4
3 = 1
+3
4 =
2
+4
5 = 1 +2 +3 +4
3 4 2
3
4 5
生成行列
1

0
0

0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
検査行列
0
0
1
1
1
0
1
0
0
1
0
1
1

1
1

1
1

0
1

0
1

1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0

0
0

0
1 
13
シンドローム
検査行列 , 系列  に対し,
T =  ならば  ∈ 
T ≠  ならば  ∉ 
T を,系列  のシンドロームと呼ぶ
 のシンドロームが 0 ならば  ∈ 
 のシンドロームが 0 でなければ  ∉ 
シンドロームには,誤りに関する情報が含まれている
⇒ シンドロームを使って,誤りを訂正することが可能
14
加法的通信路とシンドローム
2元対称通信路(BSC)に符号語  を送信
誤りベクトル  が発生し,符号語に対して加法的に作用
受信系列は  =  + 
誤りがない場合(=0),
雑音源
受信系列  のシンドロームは0
符号語


受信系列
 =  + 
誤りがある場合( ≠ 0),
 のシンドロームは 0 以外
受信系列  のシンドロームは
T = ( + )T = T + T = T
シンドロームは送信符号語に依存せず,誤りのみに依存する
シンドロームを見れば,どんな誤りが発生したかわかる
15
誤りパターンとシンドローム
=
1
0
1
0
1
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
• 000000000 を送信して 000100000 を受信した...
 0 0 0 1 0 0 0 0 0 T = (0 1 0 1 1)T.
• 110000110 を送信して 110100110 を受信した...
 1 1 0 1 0 0 1 1 0 T = (0 1 0 1 1)T.
送信符号語に依存していない
⇒ シンドロームが (0 1 0 1 1) ならば,受信語の4ビット目が誤り
16
シンドロームを利用した誤り訂正
誤りパターンとシンドロームの対応がわかっていれば,
受信系列のシンドロームから誤りパターンを推測可能.
誤りパターンを受信系列から引く(足す)ことで,
送信符号語を特定可能 (誤りの影響を打消す).
受信系列
 =  + 
シンドローム計算
 = T
誤りパターン

復号結果

【誤り訂正】
シンドローム

誤り / シンドローム対応表
.....
.....
.....
.....
.....
.....
17
1ビット誤りパターンとシンドローム
検査行列 の第  列目の列ベクトルを と書く:
 = (

⋯  )

誤りベクトルが  = (0, … , 0,1,0, … , 0) のときのシンドロームは
⋮
0
T
 =   ⋯  1 = 
0
⋮
^
第  ビット目だけに誤りが発生
⇔ シンドロームは,検査行列の第  列ベクトルと等しい
(わざわざ対応表を作らなくてもOK)
18
シンドロームを使った誤り訂正
水平垂直パリティ検査符号
符号語 000000000, 100010101,
検査行列 1 1 0 0 1 0 0 0 0
=
0
1
0
1
0
0
1
1
1
1
0
1
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
000101011, 100111110,
001001101, 101011000,
001100110, 101110011,
010010011, 110000110,
010111000, 110101101,
011011110, 111001011,
011110101, 111100000.
• 受信系列が 101001000 のとき,
⇒ シンドロームは H(1 0 1 0 0 1 0 0 0)T = (1 0 0 0 0)T
⇒ H の5列目と等しい
⇒ 5ビット目が誤り,送信符号語は 101011000
• 受信系列が 101100110 のとき,
⇒ シンドロームは H(1 0 1 1 0 0 1 1 0)T = (1 0 1 0 1)T
⇒ H の1列目と等しい
⇒ 1ビット目が誤り,送信符号語は 001100110
19
ここまでのまとめ:復号と検査行列
検査行列:シンドローム計算のための道具
シンドロームが0なら誤りなし
0以外なら,そのシンドロームから誤り位置を特定可能
線形符号では,符号化も,復号も,行列演算で実現可能
20
検査行列と符号の能力
第  ビット目に誤りが発生
⇔ シンドローム=検査行列の第 列ベクトル
検査行列が同一の列ベクトルを複数含んでいると...
⇒ 複数の1ビット誤りに対し,同一シンドロームが得られる
⇒ シンドロームからは,誤り位置の特定ができない
偶パリティ符号  = 1 + 2
 = (1 1 1)
情報記号 (x1, x2, x3) に対し,
11010
p1 = x 1 + x 2
=
01101
p2 =
x2 + x3
誤
り
訂
正
能
力
な
し
21
誤り訂正符号の設計方針
符号語中の1ビット誤りを訂正可能な符号を構成したい
「列ベクトルが全て異なる検査行列」を持つ符号を作れば良い
良い例:
H= 101100
110010
011001
H= 1010011
0100111
1101001
悪い例:
H= 110100
101010
010001
H= 1010011
1100111
1101001
 =  T = }
H= 101001
010011
110100
010101
(簡単のため,検査行列の
右部分行列は単位行列とする)
22
符号の構成例
係数行列
H= 101 100
101
110 010
110
転置
011 001 左部分 011
p1 = x 1
+ x3
p2 = x 1 + x 2
p3 =
x2 + x3
G= 100 110
010 011
001 101
000000,
001101,
010011,
011110,
100110,
101011,
110101,
111000.
符号語
23
検査行列の大きさと符号の効率
検査行列が  行  列
⇒ 構成される符号は,符号長 ,
情報記号数  =  − ,
検査記号数 .
符号長 9, 情報記号数 4.
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
=5
水平垂直パリティ検査符号
1
0
1
0
1
=9
検査行列が縦に長いと,符号語の中の検査記号数が多くなる
⇒ 符号語の中の情報記号数が少なくなる
⇒ 符号の効率は悪い
24
ハミング符号
効率の良い1ビット誤り訂正可能な符号
⇒ できるだけ「横長」な検査行列を作れば良い
Richard Hamming
ハミング符号 (Hamming Code)
1915-1998
1) 検査記号数  を決定
2) 長さ  の非零ベクトルを全て列挙
3) 列挙したベクトルを,検査行列の列ベクトルに
(右部分行列が単位行列になるようにする)
1
1
1
1
0
1
0
0





0

 = 3 の場合, H  1 1 0 1 0 1 0 , G 
0
1 0 1 1 0 0 1 



0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
1
1
0
1
1

0
1

1
符号長(列数) 7, 検査記号数(行数) 3, 情報記号数 7 – 3 = 4
25
ハミング符号のパラメータ
ハミング符号:
検査行列は,個の行ベクトルを持つ
検査行列は,2 – 1個の列ベクトルを持つ
符号長
検査記号数
情報記号数
2
=
−1

 =  −  = 2 − 1 − 

2
3
4
5
6
7

3
7
15
31
63
127

1
4
11
26
57
120
26
ハミング符号の性能
ビット誤り率  の BSC上で,4ビット情報を送受信
情報が正しく伝わる確率を評価
符号化を行わない... 1 −  4
 = 7,  = 4のハミング符号を使用 ... 1 − 
7
+ 7 1 −  6
1
0.8
ハミング符号
0.6
0.4
符号化なし
0.2

0
0
0.1
0.2
0.3
0.4
0.5
27
どうして,誤りを訂正できるのか?
検査行列とは異なる視点から,誤り訂正のメカニズムを考える
「符号語  を送信したところ,誤りが発生し,系列  を受信した」
符号語 
 が符号語でないならば,誤りを検出できる
に一番近い符号語が  ならば,誤りを訂正できる
受信系列 
他の符号語 ′
符号語と符号語のあいだの「距離」が重要
... できるだけ離れていることが望ましい
28
ハミング距離
 = (1, 2, … , ),  = (1, 2, … , ) ...同じ長さの系列
 と のハミング距離  (, ) : 系列中で異なる記号の個数
dH(0100,1101) = 2
dH(000, 011) = 2
dH(010, 110) = 1
dH(000, 111) = 3
dH(011, 011) = 0
符号語  = 01011
受信系列  = 01001
1ビットの誤り発生
⇒ 送信符号語と受信系列の
ハミング距離は 1
29
最小ハミング距離
符号 C の最小ハミング距離
min = min
,∈,≠
 (, )
定理:ハミング符号の最小ハミング距離は3である(証明略)
どの符号語の間も,3以上離れている
「 ∈ から1ビットだけ誤って得られる系列」と,
「 ∈ から1ビットだけ誤って得られる系列」を区別可能
符号語 
符号語 
誤り
誤り
⇒ だから,1ビット誤りを訂正できる
30
一般的な線形符号
ハミング符号は,線形符号の作り方の1つに過ぎない
「最小ハミング距離 > 3」の符号も存在
最小ハミング距離が min
⇒max =
min −1
2
ビットまでの誤りを訂正可能
dmin=7, tmax=3
tmax
tmax
詳しくは III 期の「符号理論」で
31
まとめ
線形符号... 取扱いに優れた通信路符号化方式
生成行列による符号化
検査行列による誤り検出・訂正
ハミング符号
最小ハミング距離は 3
1ビット誤り訂正可能な線形符号
32
練習問題
 = 15,  = 11のハミング符号の検査行列,生成行列を作れ
上記の符号に対し,p.27 のように,性能を評価せよ
6/2
June 2
lecture 30min
講義30分
test 60min
試験60分
you can bring books & PC
本,PC等の持込み可
use of a calculator recommended
電卓の使用を推奨
33