誤り訂正検出の原理と
具体的符号
1
誤り検出・訂正の原理
2
通信路モデルにおける誤り
x ( x1 , x2 ,
通信路
, xn )
y ( y1 , y2 ,
xe
( x1 e1 ,
e (e1, e2 ,
, yn )
, xn en )
, en )
誤りの混入
3
0110
1010
1110
0010
：符号語
1000
0000
1100
0100
0011
0111
1001
0101
0001
0000
0111
0101
0001
1000
0100
0011
1011
通
信
1101
1010
1110
0110
0010
1111
1100
1011
1001
1101
：受信語
1111
4
前のスライドにおいては、
符号は
C {0000,0011,0101,0110,1001,1010,1100,1111}
である。
このとき符号語 ci 0000 C を伝送したとき、系列
yを受信したとする。
i 0100 C
このとき、 誤り e 0100 が混入される。
i
しかし、受信語がからは誤りが特定されない。
yi 0100
0101 0001?
0110 0010?
0000 0100?
1100 1000?
5
誤り空間
ei
ci
yi c i ei
(mod 2)
は省略する。
h( yi , c i ) h(0, ei ) w(ei )
０ベクトルからのハミン
グ距離を考えると便利
なことが多い。
6
誤り空間例
１ビットの誤りが起こるとする。すなわち、
h(0, ei ) w(ei ) 1
の誤り空間を考える。
c C の誤り空間 E (ci )
このとき、各符号語 i
は以下のように表される。
1
c1 0000
1
E (c1 ) {0000,0001,0010,0100,1000}
（２）
c2 1010
1
E (c2 ) {1010,1011,1000,1110,0010}
（１）
7
練習１
情報ビットが４ビットで、偶数パリティのパリティビットが１
ビットの５ビットの符号空間
を考える。
この符号空間において、以下の符号語に対する１ビット
の誤り空間を求めよ。
C
c1 00000
E1 (c1 )
c2 10001
E1 (c2 )
（１）
（２）
（３）
c3 01010
E (c3 )
c4 10111
E1 (c4 )
（４）
1
8
練習２
情報ビットが３ビットで、偶数パリティのパリティビットが１
ビットの４ビットの符号空間
を考える。
この符号空間において、以下の符号語に対する２ビット
の誤り空間を求めよ。
C
（１）
c1 1111
2
（２）
E (c1 )
c2 1010
2
E (c2 )
9
誤り空間と誤り検出
001
101
100
000
011
010
111
110
001
E (c1 ) {000,001,010,100}
100
000
011
010
c1 000
101
111
110
C {000, 011,101,110}
1
E (ci ) c j i j
1
１ビット誤り検出を可能とする関係式。
10
誤り検出の模式図
ei s
ej s
cj
ci
h(ci , c j )
s
ビット誤りを検出するためには次式が成り立つ
必要がある。
i, j h(ci , c j ) s 1
11
誤り空間と誤り訂正
001
101
100
000
011
010
c1 000
111
110
001
101
100
000
011
010
111
110
c2 111
1
E
(c2 ) {111,110,101,011}
E (c1 ) {000,001,010,100}
1
E1 (c1 ) E1 (c2 )
１ビット誤り訂正を可能とする関係式。
12
誤り訂正の模式図
ej t
ei t
cj
ci
h(ci , c j )
t
ビット誤りを訂正するためには次式が成り立つ
必要がある。
i, j h(ci , c j ) 2t 1
13
誤り訂正の具体的符号
垂直水平パリティ検査符号
ハミング符号
14
垂直水平パリティ符号
1ビット誤り検出可能な符号であるパリティ検査符号の考
え方に基づいて１ビット誤り訂正可能な符号を構成でき
る。
まず、情報ビット４ビット、冗長ビット５ビットからの９ビットの
垂直水平パリティ符号の構成法を示す。
w ( w1 , w2 ,
, w9 )
( x1 , x2 , x3 , x4 , p1 , p2 , p3 , p4 , p5 )
( x , p)
15
情報ビット
列に関する
冗長ビット
u11
u12
r1
u21 u22
c1 c2
r2
s
行に関する
冗長ビット
全体の
冗長ビット
w (u11, u12 , u21, u22 , r1, r2 , c1, c2 , s)
ただし、冗長ビットは次式で定める。
r2 u21 u22
r1 u11 u12
c1 u11 u21 c2 u12 u22
s r1 r2 c1 c2 u11 u12 u21 u22
16
垂直水平パリティ符号における誤り訂
正の原理
i
j
列の誤り検出
行の誤り検出
誤っている (i, j ) 要素を
特定→１ビット誤り訂正
17
垂直水平パリティ符号における誤り訂
正能力
２ビット誤りを検出可能であるが、丸
と四角のどちらがあやまりかを判定
できない。
２ビット誤りを検出可能である。行は
特定できるが、どの列がは特定不
能。
２ビット誤りを検出可能である。列は
特定できるが、どの行かは特定不
能。
18
一般的な垂直水平パリティ符号
c
r
r c
r 1
c 1
r c
一般に、情報ビットが
であるとき、
符号ビットを (r 1) (c 1) として構成できる。
したがって冗長ビットは r c 1 である。
19
例
w (u11, u12 , u21, u22 , r1, r2 , c1, c2 , s)
の垂直水平パリティ符号を考える。このとき、次の情報
ビットから垂直水平符号を求めよ。
x 0101 u11u12u21u22
r1 u11 u12 0 1 1, r2 u21 u22 0 1 1,
c1 u11 u21 0 0 0, r2 u12 u22 1 1 0,
s u11 u12 u21 u22 0
w (0,1,0,1,1,1,0,0,0)
20
練習
w (u11, u12 , u21, u22 , r1, r2 , c1, c2 , s)
の垂直水平パリティ符号を考える。このとき、次の情報
ビットから垂直水平パリティ符号を求めよ。
（１）
x１ 0001
（２）
（３）
x2 1001
x3 1101
（４）
x4 1110
21
例
w (u11, u12 , u21, u22 , r1, r2 , c1, c2 , s)
の垂直水平パリティ符号を考える。このとき、次の符号か
ら誤りを訂正せよ。
w 000111000
e
0 0 1
0 1 1
パリティの検査から、
u21 が誤っていることが判明する。
0 0 0
したがって、正しい符号は以下である。
w 010111000
22
練習
w (u11, u12 , u21, u22 , r1, r2 , c1, c2 , s)
の垂直水平パリティ符号を考える。このとき、このとき、次
の符号から誤りを訂正せよ。
（１）
（２）
（３）
w 100101011
e
1
w 2 111101101
e
w 3 100110110
e
（４）
w 4 111001010
e
23
ハミング符号
垂直水平パリティ符号より効率的に冗長ビットを作り出す
方法が知られている。
まず、情報ビット４ビット、冗長ビット３ビットからの７ビットのハ
ミング符号の構成法を示す。（これを（７，４）ハミング符号とい
う。）
w (w1 , w2 ,
, w7 )
( x1 , x2 , x3 , x4 , p1 , p2 , p3 )
( x, p)
(7, 4) ハミング符号という。
( n, k ) 符号
n : 符号総長
k : 情報ビット長
24
（７，４）ハミング符号
w (w1 , w2 ,
, w7 )
( x1 , x2 , x3 , x4 , p1 , p2 , p3 )
( x, p)
冗長ビットを次の規則で定める。
p1 x1 x2 x3
(mod 2) での演算。
(mod 2) は省略する。
p2 x2 x3 x4
p3 x1 x2
x4
25
検査方程式
w (w1 , w2 ,
, w7 ) ( x1 , x2 , x3 , x4 , p1 , p2 , p3 )
に対して、冗長ビットの決め方から次の関係式が成り立つ。
w1 w2 w3 w5 0 ( x1 x2 x3 p1 0)
w2 w3 w4 w6 0 ( x2 x3 x4 p2 0)
w w w w 0 ( x x x p 0)
2
4
7
1
2
4
3
1
この関係式を検査方程式という。誤りが混入しなければ、
検査方程式を満足するはずである。
26
シンドローム
検査方程式から、誤りの位置を特定するための情報を抽
出することができる。受信語が y ( y1 , y2 , , y7 )
であるとき、受信語から次式で定義される３ビット s1s2 s3
をシンドロームという。
s1 y1 y2 y3 y5
s2 y2 y3 y4 y6
s y y y y
1
2
4
7
3
受信語の誤り位
置を診断するた
めの情報
検査方程式の右辺で、送信記号 wi
を受信記号 y
に置き換える。
i
27
誤りベクトルとシンドローム
s1 y1 y2 y3 y5
s2 y2 y3 y4 y6
s y y y y
1
2
4
7
3
通信路により誤りの混入
s1 w1 e1 w2 e2 w3 e3 w5 e5
s2 w2 e2 w3 e3 w4 e4 w6 e6
s w e w e w e w e
1
1
2
2
4
4
7
7
1
s1 e1 e2 e3 e5
s2 e2 e3 e4 e6
s e e e e
3 1 2 4 7
検査方程式より
28
ハミング符号の誤り訂正原理
７ビットからなる符号には、１ビット誤りベクトルは７個しかない。
正しい場合を含めて８通りを区別できれば良い。
e1 e2
1 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
e3
0
0
1
0
0
0
0
0
e4
0
0
0
1
0
0
0
0
e5
0
0
0
0
1
0
0
0
e6
0
0
0
0
0
1
0
0
e7
0
0
0
0
0
0
1
0
s1
1
1
1
0
1
0
0
0
s2
0
1
1
1
0
1
0
0
s3
1
1
0
1
0
0
1
0
29
一般のハミング符号
( n, k )
符号長：
情報ビット長：
ハミング符号
n 2 1
m
k n m 2 1 m
m
冗長ビット長：
nk m
シンドローム長：
m
30
例
w ( x1, x2 , x3 , x4 , p1, p2、, p3次のように冗長ビットを
)
定める（７，４）ハミング符号を考える。
p1 x1 x2 x3
p2 x2 x3 x4
p3 x1 x2 x4
このとき、次の情報ビットに対して符号語を求めよ。
x 0101
p1 x1 x2 x3 0 1 0 1
p2 x2 x3 x4 1 0 1 0
p3 x1 x2 x4 0 1 1 0
w ( x, p) 0101100
31
練習
w ( x1, x2 , x3 , x4 , p1, p、2 , p3 )
に対して、 次のように
冗長ビットを定める（７，４）ハミング符号を考える。
p1 x1 x2 x3
p2 x2 x3 x4
p3 x1 x2 x4
このとき、次の情報ビットに対して符号語を求めよ。
（１）
（３）
x１ 0001
x3 1101
（２）
（４）
x2 1001
x4 1110
32
例
w ( x1, x2 , x3 , x4 , p1, 、
p2 , p3 )
に対して、次のように
冗長ビットを定める（７，４）ハミング符号を考える。
p1 x1 x2 x3
p2 x2 x3 x4
p3 x1 x2 x4
このとき、次の受信語に対して誤り訂正を行え。
y y1, y2 ,
, y7 0111100
まず、シンドロームを求める。
s1 y1 y2 y3 y5 0 1 1 1 1
s2 y2 y3 y4 y6 1 1 1 0 1
s3 y1 y2 y4 y7 0 1 1 0 0
33
よって、シンドローム s s1s2 s3 110 より、誤りベクトル
が一意に e (e1 , e2 ,
, e7 ) 0010000 と特定できる。
したがって、次のように誤り訂正できる。
y y1, y2 ,
, y7 0111100
w y e 0111100 0010000
0101100
34
練習
w ( x1, x2 , x3 , x4 , p1, 、
p2 , p3 )
に対して、次のように
冗長ビットを定める（７，４）ハミング符号を考える。
p1 x1 x2 x3
p2 x2 x3 x4
p3 x1 x2 x4
このとき、次の受信語に対して誤り訂正を行え。
（１）
y1 1001011
（３）
y3 1101011
（２）
y2 1001001
（４）
y4 0110001
35
© Copyright 2024 ExpyDoc
