情報理論

（通信）符号理論入門
（誤り検出と誤り訂正）
（９章）
1
通信路符号と冗長性
ここからは、通信路符号化において、主に２元符号を考察してい
く。通信路アルファベットを B  {0,1} とする。
（定義）情報ビットと検査ビット
通信路符号語は、情報源符号語に加えて意識的に冗長部分
を付加して構成される。情報を表す記号列を情報部分といい、
冗長性を表す記号列を冗長部分という。特に、２元符号の場
合、情報部分を情報ビット、冗長部分を検査ビットという。
2
通信路符号の数学的表現
情報ビット
冗長ビット
u  (u1, u2 , , un )  ( x1, , xk , p1, , pnk )
nビット
kビット
n kビット
 ( x, p)
符号語＝情報部分＋冗長部分
ただし、
x  ( x1, x2 , , xk )
p  ( p1, p2 , , pnk )
 1  i  k , ui  xi  B  {0,1}

k  1  i  n, ui  pi k  B  {0,1}
3
パリティ検査（符号）
まず、１番単純な通信路符号としてパリティ検査について考え
る。パリティ検査は１誤り検出符号になっている。
パリティ検査符号は以下の符号語の形式になる。
u  ( x1, x2 , , xn1 , p )
n1ビット
情報ビット
１ビット
冗長ピット
これらに関係する概念を順にみていく。
4
ハイパーキューブ
（定義）ハイパーキューブ
次のように再帰的に定義される構造をハイパーキューブ
という。n 次元のハイパーキューブを HC(n) と書く。
（１）１次元のハイパーキューブ（基礎）
線分
HC(1)
0
1
(2)次元のハイパーキューブ（帰納）
HC(n 1)と HC(n 1) を対応する頂点同士、辺で
結び,最上位ビットだけが異なるように０，１を割り振る。
HC(n 1)
HC(n 1)
0 x1
1 x1
xn1
n1
HC(n)
xn1
n1
5
例
HC(1) 0
HC(2)
1
00
10
01
11
HC(3)
001
000
011
010
101
100
111
110
6
HC(4)
0010
0000
1010
0110
1000
1100
0100
0011
0111
1110
1011
1111
0001
0101
1001
1101
7
練習
HC(5)
を図示せよ。
8
排他的論理和
（定義）排他的論理和
次の真理値で定められる論理関数を排他的論理和という。
論理変数
と論理変数
の排他的論理和を
と書く。
x
y
x y
0
0
1
1
0
1
0
1
x y
x y
0
1
1
0
排他的論理和は２進数の加算、
減算に対応する。
9
２を法とする計算
で X を２で割った余りを意味する。（この計
算を２を法とする計算という。）
X (mod2)
x  y (mod2)
を考える。これは、以下のように計算できる。
x (mod2) y (mod2)
0
0
1
1
0
1
0
1
x y
0
1
1
2
x  y (mod2)
0
1
1
0
排他的論理和と同一
10
x  y (mod2) を考える。これは、以下のように計算できる。
x (mod2) y (mod2)
0
0
1
1
0
1
0
1
x y
x  y (mod2)
0
1
1
0
0
1
1
0
排他的論理和と同一。、
２を法とする加算とも同一。
1(mod2)  1
11
練習
次の式を計算せよ。
（１）
1 0 11 0 11
（２）
11 0  0  0 11
（３）
1 0 1 0  0 1 0
（４）
3  4  7  5  8  9 1(mod2)
（５）
9  3  6  4  8  7  5 (mod2)
（６）
5  4  3  8  6  9  2 (mod2)
12
パリティ（遇奇性）
（定義）パリティ
n
符号語 u  u1 , , un  B
に対して、次式が
成り立つとき、偶数パリティを持つという。

u1  u2 

 un  0
 n

  ui (mod 2)  0 
 i 1

また、次式が成り立つとき、奇数パリティを持つという。
u1  u2 
 un  1
 n

  ui (mod 2)  1
 i 1

13
例
次の符号が偶数パリティを持つか、奇数パリティを持つ
かを判定せよ。
u  (u1 , , un )  (0,0,1,1,0,1,0,1)
 00110101
略記法
u mod2  0
i
よって、偶数パリティを持つ。
これ以降では、
 mod2
符号に現れる１の
個数が偶数
を省略することもある。
14
練習
次の符号が偶数パリティを持つか、奇数パリティを持つ
かを判定せよ。
（１）
(1,1,1,0,1,1,0,1)
（２） (0,1,0,1,1,0,1,1)
（３） (0,0,0,1,1,0,1,1)
（４） 10111000
11001100
（６） 01001100
（５）
15
パリティ検査（符号）
（定義）パリティ検査（符号）
１ビットの検査ビット（パリティビット） p  B を持ち、偶数パリ
ティだけを符号語とするような符号を（偶数）パリティ検査符号と
n1
いう。情報ビットを x  ( x1 , , xn1 )  B とすると次式が
成り立つ。
u  ( x1 , , xn1 , p)  B
x1   xn1  p  0
 p  x1   xn1
n
偶数パリティ検査では、
情報ビットが偶数パリティを持
てばパリティビットは０で、
奇数パリティを持てばパリティ
ビットは１。
16
例
次の情報源符号語から、偶数パリティ検査符号を構成せよ。
x1  ( x11 , , x71 )  (1,0,1,1,1,0,0)
p1   x11  mod2  0
（１）
よって、以下のように通信路符号語が得られる。
u1  ( x , , x , p )  (1,0,1,1,1,0,0,0)
 (1011100,0)
略記法
1
1
（１）
1
7
1
x2  ( x12 , , x72 )  (0,1,1,1,1,0,1)
p2   x12  mod2  1
よって、以下のように通信路符号語が得られる。
u2  ( x12 , , x72 , p2 )  (0,1,1,1,1,0,1,1)
 (0111101,1)
17
練習
以下のような情報源記号が与えられているとき、偶数
パリティ検査符号を求めよ。
（１）
（２）
（３）
（４）
（５）
（６）
x1  (1,1,1,0,1,1,0)
x2  (0,1,0,1,1,0,1)
x3  (0,0,0,1,1,0,1)
x4  1011100
x5  1100110
x6  0100110
18
偶数パリティ符号における符号語
HC(1)
0
HC(2)
00
01
HC(3) 001
000
011
010
1
：符号語
10
11
101
100
111
110
19
HC(4)
0010
0000
1010
0110
1000
1100
0100
0011
0111
1110
1011
1111
0001
0101
1001
1101
：符号語
20
練習
情報ビットが４ビット x  B で、パリティビットが１ビット p  B
の偶数パリティ符号 u  B5 を考える。この符号語になりえ
るハイパーキューブ HC(5) 上頂点を図示せよ。
4
21
ハミング距離
（定義）ハミング距離
長さ n の２元符号（
n次元ブールベクトル）
x  ( x1 , , xn )  Bn
y  ( y1 , , yn )  Bn
に対して、次式で定義される距離 h( x, y) をハミング距離と
いう。
n
h( x, y)   ( xi , yi )
i 1
ただし、
0 xi  yi
  xi , yi   
1 xi  yi
異なる
ビットの
総数
ビットが異なるとき
に１で等しいとき０。
22
ハミング距離は次のようにも書ける。
n
h( x, y)   xi  yi
i 1
n
h( x, y)   xi  yi 
2
i 1
23
例
次の２つの系列のハミング距離を求めよ。
x  100101 B
6
y  101110  B
6
解
100101
101110
h( x, y)  3
24
練習
次のハミング距離を求めよ。
（１）
h(011,110)
（２）
h(1100,0110)
（３）
（４）
h(011001,101010)
h(00011011,10010110)
25
ハミング距離とハイパーキューブ
HC(3)
001
000
101
100
011
010
111
110
h(001,010)  2
HC(3)
001
000
101
100
011
010
111
110
h(001,110)  3
ハイパーキューブ上での
経路長がハミング距離
26
HC(4)
1010
0110
0010
1000
0000
1100
0100
0011
0111
1110
1011
1111
0001
0101
1001
1101
h(0010,1111)  3
27
練習
x  1100  B , y  1011 B
4
次の２つの系列
をハイパーキューブ
を求めよ。
4
HC(4) 上に図示し、ハミング距離
h( x, y)
28
距離の３公理
（公理）距離の公理
n
x,
y,z

K
,(K  Bやや）
n
任意の
次元ベクトル
に対して、次の３つの性質を満たす関係 d : K n  K n 
を距離という。
（１）
（２）
（３）
d ( x, x)  0 逆に、 d ( x, y)  0 なら x  y
d ( x, y)  d ( y, x)
同一地点間の距離は０
d ( x, y)  d ( y, z)  d ( x, z)
ユークリッド距離だけが距離なのでは
ない。様々な距離の概念がある。
距離は対称的
３角不等式
29
様々な距離１（ユークリッド距離）
x  ( x1 , , xn ), y  ( y1 , , yn ) 
d2 ( x, y) 
n
( xi  yi )
i 1
n
2
  xi  yi 
 i 1

1
2
2
n
最もよく用いられる
距離
x2
２次元での等
距離線は円
になる。
x1
30
様々な距離２（マンハッタン距離）
x  ( x1 , , xn ), y  ( y1 , , yn ) 
n
d1 ( x, y)   xi  yi
i 1
1
1 1
n

  xi  yi 
 i 1

n
碁盤の目状の町で
の最短路。
x2
２次元での等
距離線は菱型
（回転した正方
形）になる。
x1
31
様々な距離３（ L 距離）
x  ( x1 , , xn ), y  ( y1 , , yn ) 
d ( x, y)  max  xi  yi 
n
ある軸での最大値
n
i 1
n
p
 lim  xi  yi 
p   i 1

1
p
x2
２次元での等
距離線は正方
形になる。
x1
32
様々な距離４（ Lp 距離）
x  ( x1 , , xn ), y  ( y1 , , yn ) 
n
p
d p ( x, y)   xi  yi 
 i 1

マンハッタン距離は
別名
1 距離と
もいう。
L
n
1
p
ユークリッド距離は
別名
2 距離と
もいう。
L
33

Download Report