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

ppt