前回の練習問題について
情報記号 (x1, …, xk) に対し,検査記号 p = x1+…+xk+1として
与えられる奇パリティ符号を考える.この符号が線形符号とな
らないことを証明せよ.
解答例:
線形符号とならない反例を示せばよい.
x1=1, x2=x3=...=xk=0 ⇒ p = 0,対応する符号語は100...00
x2=1, x1=x3=...=xk=0 ⇒ p = 0,対応する符号語は010...00
2つの符号語の和は110...0 ⇒ これは正しい符号語でない
1
前回の練習問題について
6個の情報記号を,以下のように配置し,水平垂直パリティ検
査符号を構成する.この符号の生成行列を求めよ
a1 a2 a3
a4 a5 a6
q1 q2 q3
p1
p2
r
(a1, ..., a6)
→ (a1, ..., a6, p1, p2, q1, q2, q3, r)
(a1, ..., a6, p1, p2, q1, q2, q3, r) = (a1, ..., a6)G となる G を求める
検査記号の定義式は
p1 = a1 + a2 + a3
p2 =
a4 + a5 + a6
q1 = a1
+ a4
q2 =
a2
+ a5
q3 =
a3
+ a6
r = a1 + a2 + a3 + a4 + a5 + a6
2
前回の練習問題について
(a1, ..., a6, p1, p2, q1, q2, q3, r) = (a1, ..., a6)G となる G を求める
検査記号の定義式は
a1 a2 a3
a4 a5 a6
q1 q2 q3
p1
p2
r
1

0
0
G 
0
0

0
p1 = a1 + a2 + a3
p2 =
a4 + a5 + a6
q1 = a1
+ a4
q2 =
a2
+ a5
q3 =
a3
+ a6
r = a1 + a2 + a3 + a4 + a5 + a6
0 0 0 0 0 1 0 1 0 0 1

1 0 0 0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0 0 1 1

0 0 1 0 0 0 1 1 0 0 1
0 0 0 1 0 0 1 0 1 0 1

0 0 0 0 1 0 1 0 0 1 1
3
前回の内容について
線形符号は...
符号語集合がベクトル空間をなすような符号
検査記号が,情報記号の線形式で定義される符号
生成行列
基底符号語を行とする行列
符号化操作を効率的に行うための道具
4
今回の内容
線形符号の復号操作(誤りの検出と訂正)
検査行列とシンドローム
1ビット誤りの訂正法
ハミング符号
1ビット誤り訂正可能な符号のクラス
完全符号(ある意味で,もっとも効率の良い符号)である
5
ある系列が符号語であるためには...
復号操作について考える前に...「符号語」である条件を整理する
水平垂直パリティ検査符号の場合:
1 0 0 0 1 0 1 01




 0 1 0 0 1 0 0 1 1
( x1 x2 x3 x4 p1 p2 q1 q2 r )  ( x1 x2 x3 x4 )
.
0 0 1 0 0 1 1 0 1


 0 0 0 1 0 1 0 1 1
系列 (x1 x2 x3 x4 p1 p2 q1 q2 r) が「正しい」符号語
必要十分条件
p1 = x1 + x2
p2 =
x3 + x4
q1 = x1
+ x3
q2 =
x2
+ x4
r = x1 + x2 + x3 + x4
6
符号語であるための必要十分条件
各左辺を右辺に移項すると...
p1 = x1 + x2
p2 =
x3 + x4
q1 = x1
+ x3
q2 =
x2
+ x4
r = x1 + x2 + x3 + x4
– p1
x1 + x2
x3 + x4
x1
+ x3
x2
+ x4
x1 + x2 + x3 + x4
=0
– p2
=0
– q1
=0
– q2 = 0
–r=0
2進演算: x – y = x + y
+ p1
(x1 x2 x3 x4 p1 p2 q1 q2 r) x1 + x2
x3 + x4
+ p2
が「正しい」符号語
x1
+ x3
x2
+ x4
x1 + x2 + x3 + x4
=0
=0
+ q1
=0
+ q2
=0
+r=0
パリティ検査方程式
7
検査行列
(x1 x2 x3 x4 p1 p2 q1 q2 r)
が「正しい」符号語
x1 + x2
+ p1
=0
x3 + x4
+ p2
=0
x1
+ x3
+ q1
=0
x2
+ x4
+ q2
=0
x1 + x2 + x3 + x4
+r=0
(x1 x2 x3 x4 x5 x6 x7 x8 x9) が
正しい符号語か?
系列を転置して,この行列
に右からかけ,0 になるかを
確かめれば良い.
• 0 ベクトル ⇒ 符号語
• 0 ベクトル以外 ⇒ 符号語でない
1

0
1

0
1

1 0 0 1 0 0 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
1 0 1 0 0 0 1
1 1 1 0 0 0 0
検査行列
 x1 
 
 x2 
0  x3   0 
   
0  x4   0 
0  x5    0 
   
0  x6   0 
1  x7   0 
 
 x8 
 
 x9 
8
検査行列の利用例
水平垂直パリティ検査符号
• 110101101 は符号語か? yes
1

0
1

0
1

1 0 0 1 0 0 0 0
0

 
0 1 1 0 1 0 0 0
0
0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1T   0 

 
1 0 1 0 0 0 1 0
0
0
1 1 1 0 0 0 0 1 
 
• 011011010 は符号語か? no
1

0
1

0
1

1 0 0 1 0 0 0 0
0

 
0 1 1 0 1 0 0 0
0
0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 T   1 

 
1 0 1 0 0 0 1 0
0
0
1 1 1 0 0 0 0 1 
 
9
生成行列と検査行列
検査記号の定義式
p1 = a1,1x1 + a1,2x2 + ... + a1,kxk
p2 = a2,1x1 + a2,2x2 + ... + a2,kxk
:
a1,1x1 + a1,2x2 + ... + a1,kxk + p1
pm = am,1x1 + am,2x2 + ... + am,kxk a x + a x + ... + a x
+ p2
2,1 1
2,2 2
2,k k
:
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 1 0  0 

a 2, 2  a 2, k 0 1  0 
      

am,2  am,k 0 0  1 
係数行列
単位行列
10
生成行列と検査行列
水平垂直パリティ検査符号: n = 9, k = 4, m = n - k = 5.
p1 = x1 + x2
x1 x2 p1
p2 =
x3 + x4
x3 x4 p2
q1 = x1
+ x3
q1 q2 r
q2 =
x2
+ x4
r = x1 + x2 + x3 + x4
生成行列
1

0
0

0
0 0 0 1 0 1 0 1

1 0 0 1 0 0 1 1
0 1 0 0 1 1 0 1

0 0 1 0 1 0 1 1
検査行列
1

0
1

0
1

1 0 0 1 0 0 0 0

0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0

1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 1 
11
シンドローム
検査行列:
ある系列が,正しい符号語かどうか検査するのに有用
系列(の転置ベクトル)を,検査行列に右から掛ける
結果が 0 ベクトル
⇒ 正しい符号語
結果が 0 ベクトルでない ⇒ 符号語ではない
系列の転置ベクトルを,検査行列に右から掛けて得られるベクトル
系列のシンドローム(syndrome)と呼ぶ
• シンドロームが 0 である系列 ⇒ 符号語
• シンドロームが 0 でない系列 ⇒ 符号語でない
シンドロームを用いて,誤りの訂正ができないか?
12
誤りを含む系列のシンドローム
2元対称通信路(BSC)に符号語 u を送信
誤りベクトル e が発生し,符号語に対して加法的に作用
受信系列は v = u + e
• 誤りが発生しなければ (e=0),
雑音源
受信系列 v のシンドロームは0
符号語
u
e
受信系列
v = u + e • 誤りが発生したとすると (e≠0),
v のシンドロームは 0 以外
検査行列を H とすると,v のシンドロームは
HvT = H(u + e)T = HuT + HeT = HeT.
シンドロームは,送信符号語に依存せず,誤りにのみ依存する
シンドロームを見ればどんな誤りが発生したかわかる
13
誤りパターンとシンドローム
1

0
H  1

0
1

1 0 0 1 0 0 0 0

0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0

1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 1 
• 000000000 を送信して 000100000 を受信したとすると,
H(0 0 0 1 0 0 0 0 0)T = (0 1 0 1 1)T.
• 110000110 を送信して 110100110 を受信したとすると,
H(1 1 0 1 0 0 1 1 0)T = (0 1 0 1 1)T.
送信符号語に依存しない
⇒ シンドロームが (0 1 0 1 1) ならば,受信語の4ビット目が誤り
14
シンドロームを利用した誤り訂正
誤りパターンとシンドロームの対応がわかっていれば,
受信系列のシンドロームから誤りパターンを推測可能.
誤りパターンを受信系列から引く(足す)ことで,
送信符号語を特定可能 (誤りの影響を打消す / 誤り訂正).
受信系列
v=u+e
シンドローム計算
s = HvT
誤りパターン
e
復号結果
u
シンドローム
s
誤り / シンドローム対応表
.....
.....
.....
.....
.....
.....
15
1ビット誤りパターンとシンドローム
符号長を n とし,検査行列 H の第 i 列目の列ベクトルを hi と書く:




H   h1 h2  hn 




誤りベクトルが e = (0 0 ... 0 1 0 ... 0) のときのシンドロームは
i ビット目

 

 0   

   
T
He   h1 h2  hn  1   hi .

 0   

   

 
受信系列の第 i ビット目だけに誤りが発生
⇔ シンドロームは,検査行列の第 i 列ベクトルと等しい
(わざわざ対応表を作らなくてもOK) 16
シンドロームを使った誤り訂正
水平垂直パリティ検査符号
1

0
検査行列 H   1

0
1

1 0 0 1 0 0 0 0

0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0

1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 1 
符号語 000000000, 100010101,
000101011,
001001101,
001100110,
010010011,
010111000,
011011110,
011110101,
100111110,
101011000,
101110011,
110000110,
110101101,
111001011,
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
17
検査行列と符号の能力(1)
受信系列の第 i ビット目に誤りが発生
⇔ シンドロームは,検査行列の第 i 列ベクトル
検査行列が同一の列ベクトルを複数含んでいると...
⇒ 複数の1ビット誤りに対し,同一シンドロームが生成される
⇒ シンドロームからは,誤り位置の特定ができない
誤
り
訂


H

1
1
1
偶パリティ符号
p = x 1 + x2
正
能
情報記号 (x1, x2, x3) に対し,
力
1 1 0 1 0
p1 = x1 + x2
H

の
0
1
1
0
1


p2 =
x2 + x3
な
い
符
号
18
検査行列と符号の能力(2)
受信系列の第 i ビット目に誤りが発生
⇔ シンドロームは,検査行列の第 i 列ベクトル
もし検査行列の列ベクトルが全て異なっていれば...
⇒ 異なる1ビット誤りパターンには異なるシンドロームが対応
⇒ シンドロームから,誤り位置が一意に特定できる
⇒ 符号語中の1ビット誤りを訂正可能
1

0
水平垂直パリティ検査符号 H   1
0
1

1 0 0 1 0 0 0 0

0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0

1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 1 
符号語中の1ビット誤りを訂正可能
19
誤り訂正符号の設計方針
符号語中の1ビット誤りを訂正可能な符号を構成したい
「列ベクトルが全て異なる検査行列」を持つ符号を作れば良い
(簡単のため,検査行列の右部分行列は単位行列とする)
1 1 0 1 0 0


たとえば H   1 0 1 0 1 0  とする.
0 1 1 0 0 1


符号語は 000000,
001011,
010101,
011110,
1 0 0 1 1 0


G   0 1 0 1 0 1 .
0 0 1 0 1 1


100110,
101101,
110011,
111000.
20
検査行列の大きさと符号の効率
検査行列が m 行 n 列
⇒ 構成される符号は,符号長 n,
情報記号数 k = n - m,
検査記号数 m.
1 0 0 1 0 0 0 0

0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0

1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 1 
m=5
1

0
水平垂直パリティ検査符号 H   1

0
1

符号長 9, 情報記号数 4.
n=9
検査行列が縦に長いと,符号語の中の検査記号数が多くなる
⇒ 符号語の中の情報記号数が少なくなる
⇒ 符号の効率は悪い
21
ハミング符号
符号語中の1ビット誤りを訂正可能な符号を構成したい
できるだけ効率の良い符号を作りたい
⇒ できるだけ「横長」な検査行列を作れば良い.
ハミング符号 (Hamming Code)の構成法
1) 検査記号数 m を決定
2) 検査行列の列ベクトルとして,長さ m のベクトルを全て列挙
• ゼロベクトルは列ベクトルに含めない
• (右部分行列が単位行列になるようにする)
• 他の列ベクトルの順番は,適当で良い  1 0 0 0 1 1 1 


m = 3 の場合, 1 1 1 0 1 0 0 


 0 1 0 0 1 1 0
H  1 1 0 1 0 1 0 , G  
0 0 1 0 1 0 1
1 0 1 1 0 0 1 




0 0 0 1 0 1 1
符号長(列数) 7, 検査記号数(行数) 3, 情報記号数 7-3 = 4.
22
ハミング符号のパラメータ
ハミング符号の構成法
1) 検査記号数 m を決定する.
2) 検査行列の列ベクトル:長さ m のベクトル全て
ゼロベクトルは列ベクトルに含めない
検査行列は m 行 2m-1 列
符号長
n = 2m-1
検査記号数 m
情報記号数 k = n-m = 2m-1-m
符号長 n, 情報記号数 k の符号を
(n, k) 符号と言う.
m
2
3
4
5
6
7
n
3
7
15
31
63
127
k
1
4
11
26
57
120
23
符号の比較
(7, 4) ハミング符号:
符号長 7, 情報記号数 4, 1 ビット誤り訂正可能
(9, 4) 水平垂直パリティ検査符号:
符号長 9, 情報記号数 4, 1 ビット誤り訂正可能
どちらの符号が「良い」か?
• 効率ではハミング符号
• 情報伝達の信頼性でもハミング符号
ビット誤り率 p の BSC で,正しく情報を伝達できる確率
– ハミング符号:
(1-p)7 + 7p(1-p)6
= 0.85
– 水平垂直パリティ検査符号:(1-p)9 + 9p(1-p)8
= 0.77
p=0.1 のとき
同じ情報記号数,同じ誤り訂正能力なら,符号長が短いほうが有利
24
符号パラメータの限界
(7, 4) ハミング符号:
符号長 7, 情報記号数 4, 1 ビット誤り訂正可能
同等以上の能力で,より効率的な符号はあるか?
符号長 6, 情報記号数 4, 1 ビット誤り訂正可能な符号
存在しない!
• ある符号語に復号される長さ 6 の系列は,1+6=7 通りある
• ある符号語に復号される系列は,他の符号語には復号されない
• 情報記号数は 4 なので,符号語は全部で 24=16 個
• 合計 16×7=112 通りの相異なる系列が存在するはず
• 長さ 6 の系列の総数は,全部で 26=64 個
⇒ 112通りの相異なる系列が存在するはずがなく,矛盾
25
ハミング符号の場合は...
(7, 4) ハミング符号:
符号長 7, 情報記号数 4, 1 ビット誤り訂正可能
• ある符号語に復号される長さ 7 の系列は,1+7=8 通りある
• ある符号語に復号される系列は,他の符号語には復号されない
• 情報記号数は 4 なので,符号語は全部で 24=16 個
• 合計 16×8=128 通りの相異なる系列が存在するはず
• 長さ 7 の系列の総数は,全部で 27=128 個
128 個の系列が,ちょうど 16 個の部分集合に分割される.
ハミング符号は完全符号である.
26
少し高度な話題:多重誤り訂正符号
1ビット誤りが発生
⇒ シンドロームは,誤り発生位置の列ベクトルと等しい
2ビット誤りが発生
⇒ シンドロームは,誤り発生位置の列ベクトルの和と等しい




H   h1 h2  hn 




i ビット目と j ビット目で誤りが発生
⇒ シンドロームは hi + hj
H の任意の t 個以下の列ベクトルの組合せに対し,
それら列ベクトルの和が一意的である ⇒ t 重誤りを訂正可能
多重誤りを訂正できる線形符号の設計法も,多数存在
27
少し高度な話題:二重誤り訂正符号の例
1 1 1 0 0 0 0 0


1 1 0 1 0 0 0 0
1 0 0 0 1 0 0 0
.
H
1 0 0 0 0 1 0 0
0 1 0 0 0 0 1 0


0 1 0 0 0 0 0 1
この検査行列を持つ符号は,符号語中に発生した2ビットの
誤りを訂正することができる
受信系列が 11111000 ⇒シンドロームは 110111T
⇒2ビット目,6ビット目が誤り
⇒送信符号語は 10111100
28
本日のまとめ
線形符号の復号操作(誤りの検出と訂正)
検査行列とシンドローム
1ビット誤りの訂正法
ハミング符号
1ビット誤り訂正可能な符号のクラス
完全符号(ある意味で,もっとも効率の良い符号)である
29
練習問題
6個の情報記号を,以下のように配置し,水平垂直パリティ検
査符号を構成する.
この符号の検査行列を求めよ
110111001010 を復号せよ
a1 a2 a3
a4 a5 a6
q1 q2 q3
p1
p2
r
(a1, ..., a6)
→ (a1, ..., a6, p1, p2, q1, q2, q3, r)
(15, 11)ハミング符号について,
検査行列(のひとつ)を作成せよ
生成行列を求めよ
30
ダウンロード

Document