Parity, Hamming Code

プログラミング論 II
2008年9月25日
誤り検出，訂正符号
ハミング符号
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/ProgRo2/
B-1
練習 0
• 以下の関数を作成せよ.
引数はint型2個で，int a, int bと
する.
戻り値はint型で,値は"aのb乗".
関数名は po
B-2
解答 0
int po(int a, int b){
int seki=1, i;
for(i=0; i<b; i++){
seki *= a;
}
return seki;
}
B-3
概要
• 伝送誤り，誤り検出，誤り訂正とは
• パリティ，ハミング符号
• そのプログラミング
B-4
計算機の世界での"情報"
• 全ての情報は，「(大量の)0と1で表現される」
– 10進数の50  0110010 (2進数表記)
– 10進数の65  1000001 (2進数表記)
– 'A'という文字  文字コード65 (10進数)
 1000001 (2進数表記)
– 'B'という文字  文字コード66 (10進数)
 1000010 (2進数表記)
– 'a'という文字  文字コード97 (10進数)
 1100001 (2進数表記)
B-5
計算機の世界での"情報"
• 文字列 "Hello,World!" は
文字
H
e
l
l
o
,
W
o
r
l
d
!
文字コード
10進数 16進数
2進数
072
48
01001000
101
65
01100101
108
6c
01101100
108
6c
01101100
111
6f
01101111
044
2c
00101100
087
57
01010111
111
6f
01101111
114
72
01110010
108
6c
01101100
100
64
01100100
033
21
00100001
通常は，
8個(8bit)ずつ
で区切る．
B-6
計算機の世界での"情報"
• Gigabit Ethernet
– 1秒間に1bitの情報を約10億個転送．
• 100GBのHDD
– 8bitの情報を約1000億個保存可能．
B-7
伝送誤り
• ネットワークを用い情報を伝送した場合，
必ずデータが正しく届くとは限らない．
– 通信路にはノイズがある．
情報を送信 →
0 1 0 1
→ 情報を受信
0 1 0 1
通信路
計算機A
情報を送信 →
0 1 0 1
→ 情報を受信
0 1 1 1
通信路
計算機B
B-8
伝送誤り
• ネットワークを用い情報を伝送した場合，
必ずデータが正しく届くとは限らない．
– 通信路にはノイズがある．
– 情報メディアへの記録もしかり
• 受信者は
– 受信情報の正誤を判断する必要がある．
• 誤りを検出できれば，最低でも「再送依頼」が可能．
– 誤っている情報を，修正できることが好ましい．
• しかし，受信者には正誤は判断できない？
B-9
(非常に簡単な)誤り訂正符号の例
• ‘0か1の情報’を伝送したいが，
伝送路で誤りが生じる可能性がある．
• 同じ情報を3回繰り返し送る．
– ‘0’を送る場合は‘000’と，
‘1’を送る場合は‘111’と送る．
送信
000
000
000
111
111
受信受信者の判断
送信
受信受信者の判断
000
000
011
おそらく 0
おそらく 1
010
000
111
おそらく 0
おそらく 1
100
111
010
おそらく 0
おそらく 0
111
おそらく 1
3個のうち，誤りが1個以下なら
011
おそらく 1
受信者は正しく情報を復元できる．
2個以上の誤りで，誤判断する．
B-10
(非常に簡単な)誤り訂正符号の例
• 誤りが3個中1個以下なら，正しく伝わる．
– 3個中2個も誤る可能性は極端に低いと期待．
• あるビットが誤りで反転する確率を p とする
(そして，誤りは独立に発生すると仮定)
– 3ビット正しく伝わる確率
(1-p)3
– 2ビット正，1ビット誤の確率
3p(1-p)2
– 1ビット正，2ビット誤の確率
3p2(1-p)
– 3ビット誤の確率
p3
復元
失敗
• p =0.01なら，復元失敗確率は約 3×10-4
• p =0.001なら，復元失敗確率は約 3×10-6
B-11
補足：バースト誤り
• 現実では，伝送誤りの発生は独立でない．
• “10ビット連続誤り”は決して珍しくない．
– 落雷が発生したら，伝送情報が誤りだらけに．
– 無線LANの横で電子レンジを使用したら，
誤りが大量に発生する．
• 無線LAN，電子レンジともに2.4GHz帯を使用．
• 連続して発生する誤り(エラー)を
バースト誤り(バーストエラー)と呼ぶ．
B-12
誤り訂正符号の概要
• 「伝送したい情報」に誤り対策用の情報を
付加して伝送する．
– 誤り検出/訂正用情報を付加すると，伝送効
率は悪くなる．
• 「3回送る」例では，消費資源3倍，伝送効率1/3．
– 基本的に，付加情報量を増やすほど，
誤り検出/訂正能力が上がり，
伝送効率が下がる．
– 符号率＝(元の情報量)/(符号化後情報量)
B-13
パリティ
• 単一パリティ検査符号
– 偶数パリティ：全体の‘1’の数が偶数となるよ
う，検査ビットを1ビット付加する．
• 1の数が奇数なら，伝送誤り．
– 奇数ビットの誤りを正しく検出できる．
– 誤り訂正はできない．
元情報
0000
0001
0101
1101
1111
P
0
1
0
1
1
送信するデータ ‘1’の数
00000
0個
00011
2個
01010
2個
11011
4個
11110
4個
B-14
パリティ
“シンドローム”
という
元情報 P 送信データ発生誤受信データ 1の数受信者
の判断
0000 0 00000
00000
OK
0個
0001 1 00011
00011
OK
2個
0101 0 01010
01010
OK
2個
1101 1 11011
11011
OK
4個
OK
1111 0 11110
11110
4個
1
NG
0101 0 01010
01110
3個
1
NG
0101 0 01010
01000
1個
1
NG
0101 0 01010
01011
3個
2
OK
0101 0 01010
11110
4個
2
OK
0101 0 01010
00011
2個
3
NG
0101 0 01010
11100
3個
4
OK
0101 0 01010
10001
2個
5
NG
0101 0 01010
10101
5個
検出
成功
成功
成功
成功
成功
成功
成功
成功
失敗
失敗
成功
失敗
成功
B-15
パリティ
• 4ビットの元情報に，
1ビットの誤り検出用パリティビットを付加し，
5ビットに符号化し転送．
– 符号化率 4/5=0.8
• 5ビット中，1,3,5ビットの誤りを正しく検出．
2,4ビットの誤りは検出できない．
当然，0ビット誤りでも正しく動作．
– 偶数ビット誤りの場合は，検出失敗．
B-16
パリティ
• ビット誤確率を p とする(誤りは独立とする)．
• 誤り検出失敗確率は 5C2 p2(1-p)3+5C4 p4(1-p)
1
誤り検出失敗確率
2ビット誤り率と
4ビット誤り率の
合計
0.1
0.01
0.001
0.0001
0.00001
0.000001
0.001
0.01
0.1
ビット誤り発生確率 p
1
B-17
検出失敗とハミング距離
元情報 P 送信データ発生誤受信データ 1の数受信者
の判断検出
NG
0101 0 01010
01110
3個
成功
OK
0101 0 01010
11110
4個
失敗
• 1ビットの誤り正しく誤り検出．
– “01110”は存在しない．必ず誤り．
• 2ビットの誤り誤り検出失敗．
– “11110”は別のものが存在する．
受信者は“1111”+“0”が送信されたと誤解．
• 2ビット違う(ハミング距離2)ものが存在する．
• ハミング距離n(nビット反転)以内に別のものがなけ
れば良い．より強力な誤り検出＆無駄遣い．B-18
パリティの算出
• 送信者は，パリティを計算する必要がある．
• 情報が[0110]なら，パリティーは 0
• 情報が[0010]なら，パリティーは 1
• [x0 x1 x2 x3]の，パリティは？
以下が，一つの考え方(一般的でない)
– ‘1’が偶数個なら，パリティは‘0’
– ‘1’が奇数個なら，パリティは‘1’
B-19
パリティ算出関数
int parity(int x0, int x1,
int x2, int x3){
x0～x3 の中の1の数を数える．
if( 1の数が偶数 ){
return 0;
} else {
return 1;
}
}
B-20
パリティ算出関数
int count_one(int x0, int x1, int x2, int x3){
int num;
num = 0;
if( x0 == 1 ){
num = num + 1;
}
if( x1 == 1 ){
num = num + 1;
}
if( x2 == 1 ){
num = num + 1;
}
if( x3 == 1 ){
num = num + 1;
}
return num;
}
B-21
パリティ算出関数
int get_parityA(int x0, int x1, int x2, int x3){
int num_of1;
num_of1 = count_one( x0, x1, x2, x3);
if( num_of1 % 2 == 0 ){
return 0;
} else {
return 1;
}
}
B-22
パリティ算出関数
void main(){
int x0, x1, x2, x3;
int parity;
x0 = 0;
x1 = 1;
x2 = 1;
x3 = 1;
parity = get_parity( x0, x1, x2, x3);
printf("%d %d %d %d -> %d\n",
x0, x1, x2, x3, parity);
}
B-23
パリティの算出(再)
• [x0 x1 x2 x3]の，パリティは？
– 排他的論理和を用いて計算可能．
これが一般的．
入力入力
x
y
– PとQの排他的論理和は
P  Qと記述
0
0
x
y
z
xor
出力
z
0
0
1
1
1
0
1
1
1
0
B-24
排他的論理和
• P  Qは，(Pに対して，  Qが施されたと考える)
– Qが0ならP． Qが1なら￢P．
つまり， 0は値を保持， 1は値を反転．
P  Q  R  S  Tは
1が登場するたびに反転する．
1が偶数個の場合→結果は 0
1が奇数個の場合→結果は 1
入力
P
入力
Q
出力
PQ
0
0
1
1
0
1
0
1
0
1
1
0
B-25
C言語の排他的論理和
• ^ が(ビット毎の)排他的論理和演算子．
– 106日本語キーボードでは，
~
右上のキー．‘0’の2個右のキー． ^ へ
– Shiftを押しながら押すと，「~」が出る．
• 196 ^ 161  101
11000100 ^ 10100001  01100101
1 1 0 0 0 1 0 0

1 0 1 0 0 0 0 1
0 1 1 0 0 1 0 1
B-26
パリティ算出関数
int get_parityB(int x0,
int xor;
xor = x0 ^ x1 ^
if( xor == 0 ){
return
} else {
return
}
}
int x1, int x2, int x3){
x2 ^ x3;
0;
1;
B-27
パリティ算出関数
int get_parityC(int x0, int x1, int x2, int x3){
return ( x0 ^ x1 ^ x2 ^ x3 );
}
B-28
C言語の排他的論理和
• 左の桁に0が多数あっても，問題ない．
10進数
入力A 入力B
0
0
0
1
1
0
1
1
出力
0
1
1
0
入力A
00000000
00000000
00000001
00000001
2進数
入力B
00000000
00000001
00000000
00000001
出力
00000000
00000001
00000001
00000000
0  0=0なので，
上位に0があっても
無視できる．
B-29
パリティ処理：パリティの検査
• 受信者は，受信データに対してパリティ
チェックを行い，受信データが正しいか否
かを検査．
– 1が偶数個  正しい(と思われる)
– 1が奇数個  誤り
B-30
パリティ検査関数
int parity_check(int x0, int x1,
int x2, int x3, int p){
int xor;
xor = ( x0 ^ x1 ^ x2 ^ x3
if( xor == 1 ){
printf("NG!\n");
return 1;
} else {
printf("OK!\n");
return 0;
}
}
^ p );
B-31
水平垂直パリティ検査符号
• 1ビットの誤りを訂正可能．
• 4ビットの情報に，4ビットのパリティを付加
する例．符号化率0.5で半分は冗長ビット．
x0 x1
p0
1
0
1
偶
x2 x3
p1
1
1
0
偶
0
1
p2 p3
偶偶
元情報1011
parity1001
B-32
水平垂直パリティ検査符号
1ビットの誤りを訂正
x0 x1
p0
1
0
1
x2 x3
p1
1
1
0
0
1
p2 p3
1
0
1
偶
0
1
0
奇
送信側
受信側
1 送信情報1011
parity 1001
奇偶
↓エラー
受信情報1001
parity 1001
0
送信者が
送信した
情報
元情報1011
parity1001
訂正
1
0
1
偶
1
1
0
偶
0
1
偶偶
受信者の判断 1011
B-33
水平垂直パリティ検査符号
1ビットの誤りを訂正
x0 x1
p0
1
0
1
x2 x3
p1
1
1
0
0
1
p2 p3
1
0
1
偶
1
1
1
奇
送信側
受信側
1 送信情報1011
parity 1001
偶偶
↓エラー
受信情報1011
parity 1101
0
送信者が
送信した
情報
元情報1011
parity1001
訂正
1
0
1
偶
1
1
0
偶
0
1
偶偶
受信者の判断 1011
B-34
水平垂直パリティ検査符号
2ビットの誤りで，誤訂正，訂正不能
1
0
1
偶
1
0
1
偶
1
1
1
奇
0
1
1
偶
1
1
1
1
誤訂正
奇偶
偶偶
1
1
1
奇
?
?
0
1
0
奇
?
?
0
1
奇奇
訂正不能
受信者
の判断
1001
受信者の判断誤りB-35
水平垂直パリティの例
• 伝えたい情報“1000”
• 送信する情報“10001010”
B-36
水平垂直パリティの例
• 受信した情報“10101010”
• 訂正された情報“1000”
B-37
練習 1
• 下記の通り受信したとき,受信者はどのよ
うに復号するか
• 10111001
• 01001100
• 11001011
B-38
解答 1
• 10111001
–1011
• 01001100
–0101
• 11001011
–1100
B-39
水平垂直パリティ検査符号
3
4
5
6
8
9
10
11
13
14
15
16
int horizontal_vertical_p0(int x0, int x1,
int x2, int x3){
return x0^x1;
}
int horizontal_vertical_p1(int x0, int x1,
int x2, int x3){
return x2^x3;
}
int horizontal_vertical_p2(int x0, int x1,
int x2, int x3){
return x0^x2;
}
以下略．
B-40
void hv_parity_check(int x0, int x1, int x2, int x3,
int p0, int p1, int p2, int p3){
int s0, s1, s2, s3;
s0 = x0 ^ x1 ^ p0;
s1 = x2 ^ x3 ^ p1;
s2 = x0 ^ x2 ^ p2;
s3 = x1 ^ x3 ^ p3;
printf("%d %d %d %d %d %d %d %d --> ", x0, x1, x2, x3, p0,
if( s0 == 0 && s1 == 0 && s2 == 0 && s3 == 0 ){
/* no error */
printf("%d %d %d %d (no error)\n", x0, x1, x2, x3);
} else if( s0 == 1 && s1 == 0 && s2 == 1 && s3 == 0 ){
/* x0 is error */
x0 = x0 ^ 1;
/* Reversal */
printf("%d %d %d %d (x0 is error)\n", x0, x1, x2, x3);
} else if( s0 == 1 && s1 == 0 && s2 == 0 && s3 == 1 ){
/* x1 is error */
以下略
B-41
void hv_parity_check(int x0, int x1, int x2, int x3,
int p0, int p1, int p2, int p3){
int s0, s1, s2, s3;
s0 = x0 ^ x1 ^ p0;
s1 = x2 ^ x3 ^ p1;
s2 = x0 ^ x2 ^ p2;
途中，省略
} else if( s0 == 0 && s1 == 0 && s2 == 0 && s3 == 1 ){
/* p3 is error */
p3 = p3 ^ 1;
/* Reversal */
printf("%d %d %d %d (p3 is error)\n", x0, x1, x2, x3);
} else {
printf("ERROR\n");
}
}
B-42
水平垂直パリティ検査符号
• 1ビットの誤りを訂正可能．
• 9ビットの情報に，6ビットのパリティを付加
する例．符号化率0.6．
x0 x1 x2
p0
x3 x4 x5
p1
x6 x7 x8
p2
p3 p4 p5
B-43
ハミング符号 (Hamming Code)
2ビットの誤り検出と1ビットの誤り訂正が可能
– 任意の符号間のハミング距離が3以上
– 3ビット以上誤らなければ，他の符号結果と同
じならない．
• 検査ビット長が m の場合，
2m-1 の符号を作り出す．
つまり，情報ビット長は 2m-1-m となる．
– 検査ビット長3, 情報ビット長4, 符号全体長7
の場合，(7,4)のハミング符号
B-44
ハミング符号
検査ビット全符号長情報ビット符号化率
1
1
0
0.000
2
3
1
0.333
3
7
4
0.571
4
15
11
0.733
5
31
26
0.839
6
63
57
0.905
7
127
120
0.945
8
255
247
0.969
B-45
ハミング符号 (検査ビット長3の例)
シンドローム
x0 x1 x2 x3 p0 p1 p2
偶
偶
偶
4ビットの情報を，
7ビットに符号化．
(7,4)のハミング符号
• 上記の3本全て，「1が偶数個」となるように
p0,p1,p2を定める．
p0=x0  x1  x2
p1=x1  x2  x3
p2=x0  x1  x3
1

 p0 p1 p2 
1
x0 x1 x2 x3
1

ただし加算は排他的論理和  0
0 1

1 1
1 0

1 1 
B-46
ハミング符号 (検査ビット長3の例)
p0=x0 x1  x2
p1=x1 x2  x3
p2=x0 x1  x3
1

0
x0 x1 x2 x3
0

0

 x0 x1 x 2 x3
ハミング符号
生成行列
0
1
0
0
p0
0
0
1
0
0
0
0
1
1
1
1
0
p1 p 2
0
1
1
1
1

1
0

1 
ただし，加算は排他的論理和
B-47
ハミング符号 (検査ビット長3の例)
x0  x1  x2  p0=0
x1  x2  x3  p1=0 のはず
x0  x1  x3  p2=0
1

1
1

p1 p 2 0
1

0

0
シンドローム
(全て0のはず)
s0
s1 s2 
x0 x1 x2 x3
p0
ハミング符号
検査行列
0 1

1 1
1 0

1 1
0 0 
1 0

0 1
B-48
ハミング符号 (検査ビット長3の例)
x0 x1 x2 x3 p0 p1 p2
s0 奇
ハミング符号
誤り訂正
s1 奇
s2 偶
上記のようなシンドロームが得られたとする．
シンドローム
(全て偶のはず)
「奇数」が含まれているので誤りである．
誤りが1ビットしか無いと仮定すると，
「s0に含まれる」，「s1に含まれる」，「s2に含まれない」
はずである．→x2が誤り
B-49
ハミング符号
x0 x1 x2 x3 p0 p1 p2
偶
偶
偶
全て異なる必要がある．
(同一のあると，どちらが
誤ったのか判別不能)
全て0の列があっては困る．
(そのビットがシンドロームに
影響を与えない)
• 検査ビット3なら，
23=8通り．
全て0を除き8-1=7通り．
横の長さ=全符号長=7
• 検査ビット長 m
符号長
2m-1
情報ビット
2m-1-m
• (2m-1,2m-1-m)ハミング
符号
B-50
#include <stdio.h>
int horizontal_vertical_p0(int x0, int x1,
int x2, int x3){
return
x0^x1;
}
水平垂直パリティ検査符号
int horizontal_vertical_p1(int x0, int x1,
int x2, int x3){
return
x2^x3;
}
int horizontal_vertical_p2(int x0, int x1,
int x2, int x3){
return
x0^x2;
}
int horizontal_vertical_p3(int x0, int x1,
int x2, int x3){
return
x1^x3;
}
void hv_parity_check(int x0, int x1, int x2, int x3,
int p0, int p1, int p2, int p3){
int s0, s1, s2, s3;
B-51

Download Report