情報理論

線形符号（１０章）
1
組織符号
組織符号
情報部分と検査部分（冗長部分）が明確に分
離できる通信路符号を組織符号という。
組織符号は以下のように表現できる。
通信路符号＝情報部分＋検査部分
w  ( w1 , w2 ,
 ( x1 , x2 ,
, wn )
, xk , p1 ,
情報部分
, pn  k )
検査部分
 ( x , p)
2
２元（n,k)符号
２元（n,k)符号
符号アルファベットの大きさが２であり、
k
符号長が n ビット、情報部分が
（通信路）符号を２元（n,k)符号という。
このとき、検査ビットは、当然
nk
ビットの
ビットである。
情報ビットから、検査ビットの作成には様々な方法が考えられ
る。この中で、情報ビットを線形写像して（行列演算で）検査
ビットを作成する方法が応用上重要である。
線形符号
3
線形符号
線形符号
情報ビット x  ( x1 , , xk )から、検査ビット p  ( p1 , , pnk )
を生成する定義式が、線形写像で表されるような通信路符号を
線形符号という。
 p1  p11 x1  p21 x2  pk1 xk


p  p
x

p
x

p
x
n

k
1(
n

k
)
1
2(
n

k
)
2
k
(
n

k
)
k

4
情報・検査関連行列
線形符号では、検査ビットの定義式は以下のように行
列の形で表現可能である。
p  xP
( p1 ,
, pn k )  ( x1 ,
この行列
P
 p11

, xk ) 
p
 k1
p1 nk  


pk ( n k ) 

を、情報・検査関連行列という。
5
生成行列
線形符号では、情報ビットから符号を行列を用いて表
現可能である。
Ik は k  k
w  xG
の単位行列
( x, p)  x  I k
( w1 ,
, wn )  ( x1 ,
1 0
0 1
, xk ) 


0

P
0
p11
p12
p21
p22
pk1
pk 2
0
0

P
この行列G  I k
( n, k ) 符号では k  n
1
p1( n  k ) 

p2( n  k ) 


pk ( n k ) 
を、生成行列という。
行列となる。
6
生成行列例
(7,4)ハミング符号は、線形符号である。したがって、
情報ビットから、行列を用いて検査ビットおよび符号
を構成可能である。この行列を示す。
w  (w1 , w2 ,
, w7 )
 ( x1 , x2 , x3 , x4 , p1 , p2 , p3 )
 ( x, p)
p1  x1  x2  x3
p2  x2  x3  x4
p3  x1  x2
 x4
7
前のスライドより、（７，４）ハミング符号の情報・検査関
連行列 PH および生成行列 G H が以下のように表
現できる。
1
1
PH  
1

0
1
0
GH  
0

0
0
1
0
0
0
1
1
1
1

1
0

1
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1

1
0

1
8
例
生成行列が以下で与えられるとする。
1
0
GH  
0

0
0
1
0
0
0
0
1
0
0
0
0
1
１
1
1
0
0
1
1
1
1
1 
0

1
このとき、以下の情報ビットから符号を生成せよ。
（１）
（２）
x1  (1,0,0,1)
x2  (0,1,1,1)
9
w1  x1GH
1
0
 (1, 0, 0,1) 
0

0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1 
0

1
 (1, 0, 0,1,1,1, 0)
w 2  x 2G H
1
0
 (0,1,1,1) 
0

0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1 
0

1
 (0,1,1,1, 0,1, 0)
10
練習
前のスライドの生成行列 GH で符号を生成するとする。
このとき、次の情報ビットに対する符号を求めよ。
（１）
x１  0001
（２）
（３）
x2  0110
x3  1101
（４）
x4  1110
11
練習
垂直・水平パリティ符号は線形符号である。（9,4)垂直
水平符号に対して、情報・検査関連行列 PO および
生成行列 G を求めよ。
O
12
練習
前のスライドの生成行列 GO で符号を生成するとする。
このとき、次の情報ビットに対する符号を求めよ。
（１）
x１  0001
（２）
（３）
x2  0110
x3  1101
（４）
x4  1110
13
検査行列
生成行列 G  [ I k
検査行列という。
H  [tP
P ] に対して、次の形の行列
H を
I nk ]
 p11
p
12




 p1( n k )
p21
p22
pk1
pk 2
1 0
0 1
p2( n k )
pk ( n k )
0
0
0


0

1 
14
性質：検査行列
情報ビット x  ( x1 , , xk ) に対して、生成行列 G  [ I k P ]で
符号 w  (w1 , , wn )
が生成されたとする。このとき、検査
行列 H  [ t P I nk ] に対して、次式が成り立つ。
wtH  0
 ( w1 ,
 p11


 pk1
, wn ) 
1


0
p1( n  k ) 


pk ( n k ) 
  (0, 0, , 0)
0

nk


1

15
証明
w  xG
であるので、
w t H  x[ I k
P]t[ P
 ( x1 ,
 ( x1 ,
1

, xk ) 
0

t
P]
I nk ]
0
p11
1
pk1
 p11  p11
p  p
21
21
, xk ) 


 pk1  pk 1
w  x[ I k
p12  p12
p22  p22
pk 2  pk 2
p1( n  k ) 
 p11



p1( n  k )  
pk ( n k ) 
  pk 1

 1
0

pk ( n  k )  




1
0

p1( n  k )  p1( n  k ) 
p2( n  k )  p2( n k ) 


pk ( n k )  pk ( n k ) 
16
0 0
0 0
 w t H  ( x1 , , xk ) 


0 0
 (0, 0, , 0)
別証明
G t H  [Ik
0
0 


0
t
P]t[ P
I nk ]
 P 
 [Ik P ] 

I
 nk 
PP
0
QED
17
（７，４）ハミング符号の生成行列
は以下のように表現できる。
1
0
GH  
0

0
0
1
0
0
0
0
1
0
0
0
0
1
１
1
1
0
G H および検査行列 H H
0
1
1
1
1
1 
0

1
1 1 1 0 1 0 0 


H H  0 1 1 1 0 1 0 
1 1 0 1 0 0 1 
18
実際、
1
0
GH t H H  
0

0
0
0

0

0
0 0 0 １
1
0
0 0 1 1
0 1
0 1 1
0 0 1
0 1
1
1
1 
1

1 
0

0
 1
1 
0
0

0 1
1 1 
1 0

1 1
0 0

1 0
0 1 
0 0
0 0 
0 0

0 0
19
練習
垂直・水平パリティ符号は線形符号である。（9,4)垂直
水平符号に対して、検査行列 H を求めよ。
O
また、
GO HO  0
t
を確かめよ。
20
シンドローム
シンドローム
２元 ( n, k ) 線形符号の受信語が y  ( y1 , y2 ,
であるとき、受信語から次式で定義される長さ n  k
列
s  (s , , s ) をシンドロームという。
, yn )
の２元系
n k
1
s  ytH
 ( s1 ,
, sn  k )  ( y1 ,
受信語の誤り位
置を診断するた
めの情報
 p11


 pk1
, yn ) 
1


0
p1( n  k ) 


pk ( n  k ) 

0



1

21
シンドロームの性質
s  ytH
である。
一方、受信語 y  ( y1 ,
と誤りベクトル e  (e1 ,
, yn ) は符号語 w  (w1 , , wn )
, en ) 用いて次のように表現できる。
y  we
 ( y1 , , yn )  ( w1  e1 ,
, wn  en )
したがって、シンドロームに関して次式が成り立つ。
s  ytH
 (w  e) t H
 w tH  etH
0
 etH
22
このように、実はシンドロームは誤りベクトルのみで定まる。
よって、以下が成り立つ。
s0
誤りなし
s0
誤りあり
シンドロームにより、
誤りそのものの検出および
誤り位置の導出
が可能である。（１ビット誤り）
23
シンドロームを用いた誤り訂正
t
s

y
H のように計算可能であ
符号語より、シンドロームが
る。このシンドロームが検査行列のt H の i 列と等しいと
する。
t
このとき、シンドロームと誤りベクトルの関係式 s  e H
から、誤りベクトルはe  (0, , ei  1, 0) であり、送信符
号は
w  ye
 ( w1 ,
, wi ,
, wn )  ( y1  e1 ,
 ( y1 ,
, yi  ei ,
, yi  1,
, yn  en )
, yn )
であることがわかる。
24
練習
以下の各系列は次の検査行列を持つ（７、４）ハミング符号
である。このとき、シンドロームを計算することにより、誤り
訂正を行え。
1 1 1 0 1 0 0 
H H  0 1 1 1 0 1 0 
1 1 0 1 0 0 1 
（１）
y１  1110111
（２）
y2  0111101
（３）
y3  0101000
（４）
y4  0100110
25
練習
垂直・水平パリティ符号は線形符号である。（9,4)垂直水平
符号に対して、先ほど求めた検査行列 H O を求いてシン
ドローム
を計算できる。
1 2
5
s  (s , s ,
,s )
このシンドロームを用いて以下の符号の誤りを訂正せよ。
（１）
y１  110100000
（３）
y3  110101001
（２）
y2  011010011
（４）
y4  000101010
26
情報伝達モデル（複雑版）
情報源符号化
（５、６章）
情報
情報源復号化
（５、６章）
外乱（雑音）
情
報
源
値通情
表表報
現現の
共
）（
２
通信路符号化
（８章）
通
信
路
通信路
（７章）
値通情
表表報
現現の
共
）（
２
通信路復号化
（８章）
受
信
者
27

Download Report