Presentation is loading. Please wait.

Presentation is loading. Please wait.

プログラミング論 II 2008年9月25日 誤り検出,訂正符号 ハミング符号

Similar presentations


Presentation on theme: "プログラミング論 II 2008年9月25日 誤り検出,訂正符号 ハミング符号"— Presentation transcript:

1 プログラミング論 II 2008年9月25日 誤り検出,訂正符号 ハミング符号

2 練習 0 以下の関数を作成せよ. 引数はint型2個で,int a, int bとする. 戻り値はint型で,値は"aのb乗".
関数名は po

3 解答 0 int po(int a, int b){ int seki=1, i; for(i=0; i<b; i++){
seki *= a; } return seki;

4 概要 伝送誤り,誤り検出,誤り訂正とは パリティ,ハミング符号 そのプログラミング

5 計算機の世界での"情報" 全ての情報は,「(大量の)0と1で表現される」 10進数の50  0110010 (2進数表記)
10進数の65  (2進数表記) 'A'という文字  文字コード65 (10進数)  (2進数表記) 'B'という文字  文字コード66 (10進数)  (2進数表記) 'a'という文字  文字コード97 (10進数)  (2進数表記)

6 計算機の世界での"情報" 文字列 "Hello,World!" は 通常は, 8個(8bit)ずつ で区切る.

7 計算機の世界での"情報" Gigabit Ethernet 100GBのHDD 1秒間に1bitの情報を約10億個転送.

8 伝送誤り ネットワークを用い情報を伝送した場合, 必ずデータが正しく届くとは限らない. 通信路にはノイズがある. 情報を送信 →
→ 情報を受信 1 1 1 1 通信路 計算機A 計算機B 情報を送信 → → 情報を受信 1 1 1 1 1 通信路

9 伝送誤り ネットワークを用い情報を伝送した場合, 必ずデータが正しく届くとは限らない. 受信者は しかし,受信者には正誤は判断できない?
通信路にはノイズがある. 情報メディアへの記録もしかり 受信者は 受信情報の正誤を判断する必要がある. 誤りを検出できれば,最低でも「再送依頼」が可能. 誤っている情報を,修正できることが好ましい. しかし,受信者には正誤は判断できない?

10 (非常に簡単な)誤り訂正符号の例 ‘0か1の情報’を伝送したいが, 伝送路で誤りが生じる可能性がある. 同じ情報を3回繰り返し送る.
‘0’を送る場合は‘000’と, ‘1’を送る場合は‘111’と送る. 送信 受信 受信者の判断 送信 受信 受信者の判断 000 000 おそらく 0 000 011 おそらく 1 000 010 おそらく 0 000 111 おそらく 1 000 100 おそらく 0 111 010 おそらく 0 111 111 おそらく 1 3個のうち,誤りが1個以下なら 受信者は正しく情報を復元できる. 2個以上の誤りで,誤判断する. 111 011 おそらく 1

11 (非常に簡単な)誤り訂正符号の例 誤りが3個中1個以下なら,正しく伝わる. あるビットが誤りで反転する確率を p とする
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 復元 失敗

12 補足:バースト誤り 現実では,伝送誤りの発生は独立でない. “10ビット連続誤り”は決して珍しくない. 連続して発生する誤り(エラー)を
落雷が発生したら,伝送情報が誤りだらけに. 無線LANの横で電子レンジを使用したら, 誤りが大量に発生する. 無線LAN,電子レンジともに2.4GHz帯を使用. 連続して発生する誤り(エラー)を バースト誤り(バーストエラー)と呼ぶ.

13 誤り訂正符号の概要 「伝送したい情報」に誤り対策用の情報を付加して伝送する. 誤り検出/訂正用情報を付加すると,伝送効率は悪くなる.
「3回送る」例では,消費資源3倍,伝送効率1/3. 基本的に,付加情報量を増やすほど, 誤り検出/訂正能力が上がり, 伝送効率が下がる. 符号率=(元の情報量)/(符号化後情報量)

14 パリティ 単一パリティ検査符号 偶数パリティ:全体の‘1’の数が偶数となるよう,検査ビットを1ビット付加する.
1の数が奇数なら,伝送誤り. 奇数ビットの誤りを正しく検出できる. 誤り訂正はできない. 元情報 P 送信するデータ ‘1’の数 0000 00000 0個 0001 1 00011 2個 0101 01010 2個 1101 1 11011 4個 1111 1 11110 4個

15 パリティ “シンドローム” という 元情報 P 送信データ 発生誤 受信データ 1の数 検出 0000 00000 00000 0個 OK
受信者 の判断 検出 0000 00000 00000 0個 OK 成功 0001 1 00011 00011 2個 OK 成功 0101 01010 01010 2個 OK 成功 1101 1 11011 11011 4個 OK 成功 1111 11110 11110 4個 OK 成功 1 0101 01010 01110 3個 NG 成功 1 0101 01010 01000 1個 NG 成功 1 0101 01010 01011 3個 NG 成功 2 0101 01010 11110 4個 OK 失敗 2 0101 01010 00011 2個 OK 失敗 3 0101 01010 11100 3個 NG 成功 4 0101 01010 10001 2個 OK 失敗 5 0101 01010 10101 5個 NG 成功

16 パリティ 4ビットの元情報に, 1ビットの誤り検出用パリティビットを付加し, 5ビットに符号化し転送.
符号化率 4/5=0.8 5ビット中,1,3,5ビットの誤りを正しく検出. 2,4ビットの誤りは検出できない. 当然,0ビット誤りでも正しく動作. 偶数ビット誤りの場合は,検出失敗.

17 パリティ ビット誤確率を p とする(誤りは独立とする). 誤り検出失敗確率は 5C2 p2(1-p)3+5C4 p4(1-p)
2ビット誤り率と 4ビット誤り率の 合計

18 検出失敗とハミング距離 1ビットの誤り正しく誤り検出. 2ビットの誤り誤り検出失敗. 2ビット違う(ハミング距離2)ものが存在する.
元情報 P 送信データ 発生誤 受信データ 1の数 受信者 の判断 検出 0101 01010 01110 3個 NG 成功 0101 01010 11110 4個 OK 失敗 1ビットの誤り正しく誤り検出. “01110”は存在しない.必ず誤り. 2ビットの誤り誤り検出失敗. “11110”は別のものが存在する. 受信者は“1111”+“0”が送信されたと誤解. 2ビット違う(ハミング距離2)ものが存在する. ハミング距離n(nビット反転)以内に別のものがなければ良い.より強力な誤り検出&無駄遣い.

19 パリティの算出 送信者は,パリティを計算する必要がある. 情報が[0110]なら,パリティーは 0 情報が[0010]なら,パリティーは 1
[x0 x1 x2 x3]の,パリティは? 以下が,一つの考え方(一般的でない) ‘1’が偶数個なら,パリティは‘0’ ‘1’が奇数個なら,パリティは‘1’

20 パリティ算出関数 int parity(int x0, int x1, int x2, int x3){ x0~x3 の中の1の数を数える.
if( 1の数が偶数 ){ return 0; } else { return 1; }

21 パリティ算出関数 int count_one(int x0, int x1, int x2, int x3){ int num;
if( x0 == 1 ){ num = num + 1; } if( x1 == 1 ){ if( x2 == 1 ){ if( x3 == 1 ){ return num;

22 パリティ算出関数 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; }

23 パリティ算出関数 void main(){ int x0, x1, x2, x3; int parity; x0 = 0; x1 = 1;
parity = get_parity( x0, x1, x2, x3); printf("%d %d %d %d -> %d\n", x0, x1, x2, x3, parity); }

24 パリティの算出(再) [x0 x1 x2 x3]の,パリティは? 1 1 1 1 1 1 排他的論理和を用いて計算可能. これが一般的.
PとQの排他的論理和は P Qと記述 入力 x 入力 y 出力 z 1 1 x z y 1 1 xor 1 1

25 排他的論理和 P Qは,(Pに対して, Qが施されたと考える) Qが0ならP. Qが1なら¬P. つまり, 0は値を保持, 1は値を反転.
つまり, 0は値を保持, 1は値を反転. P Q R S Tは 1が登場するたびに反転する. 1が偶数個の場合→結果は 0 1が奇数個の場合→結果は 1 入力 P 入力 Q 出力 P Q 1 1 1 1 1 1

26 C言語の排他的論理和 ^ が(ビット毎の)排他的論理和演算子. 196 ^ 161  101
106日本語キーボードでは, 右上のキー.‘0’の2個右のキー. Shiftを押しながら押すと,「~」が出る. 196 ^ 161  101 ^  ~ ^ 1 1 1 1 1 1 1 1 1 1

27 パリティ算出関数 int get_parityB(int x0, int x1, int x2, int x3){ int xor;
xor = x0 ^ x1 ^ x2 ^ x3; if( xor == 0 ){ return 0; } else { return 1; }

28 パリティ算出関数 int get_parityC(int x0, int x1, int x2, int x3){
return ( x0 ^ x1 ^ x2 ^ x3 ); }

29 C言語の排他的論理和 左の桁に0が多数あっても,問題ない. 10進数 2進数 0 0=0なので, 上位に0があっても 無視できる.

30 パリティ処理:パリティの検査 受信者は,受信データに対してパリティチェックを行い,受信データが正しいか否かを検査.
1が偶数個  正しい(と思われる) 1が奇数個  誤り

31 パリティ検査関数 int parity_check(int x0, int x1, int x2, int x3, int p){
int xor; xor = ( x0 ^ x1 ^ x2 ^ x3 ^ p ); if( xor == 1 ){ printf("NG!\n"); return 1; } else { printf("OK!\n"); return 0; }

32 水平垂直パリティ検査符号 1ビットの誤りを訂正可能. 4ビットの情報に,4ビットのパリティを付加する例.符号化率0.5で半分は冗長ビット.
x0 x1 p0 1 1 x2 x3 p1 1 1 p2 p3 1 元情報1011 parity1001

33 水平垂直パリティ検査符号 1ビットの誤りを訂正
x0 x1 p0 1 1 送信者が 送信した 情報 x2 x3 p1 1 1 p2 p3 1 元情報1011 parity1001 送信側 受信側 1 1 1 1 1 訂正 1 1 1 1 送信情報1011 parity 1001 ↓エラー 受信情報1001 受信者の判断 1011

34 水平垂直パリティ検査符号 1ビットの誤りを訂正
x0 x1 p0 1 1 送信者が 送信した 情報 x2 x3 p1 1 1 p2 p3 1 元情報1011 parity1001 送信側 受信側 1 1 1 1 1 1 1 訂正 1 1 1 1 送信情報1011 parity 1001 ↓エラー 受信情報1011 parity 1101 受信者の判断 1011

35 水平垂直パリティ検査符号 2ビットの誤りで,誤訂正,訂正不能
1 1 1 1 1 1 1 誤訂正 1 1 1 1 1 1 受信者 の判断 1001 1 1 1 ? ? 1 訂正不能 ? ? 1 受信者の判断 誤り

36 水平垂直パリティの例 伝えたい情報“1000” 送信する情報“ ”

37 水平垂直パリティの例 受信した情報“ ” 訂正された情報“1000”

38 練習 1 下記の通り受信したとき,受信者はどのように復号するか

39 解答 1 1011 0101 1100

40 水平垂直パリティ検査符号 3 int horizontal_vertical_p0(int x0, int x1,
return x0^x1; 6 } 8 int horizontal_vertical_p1(int x0, int x1, int x2, int x3){ return x2^x3; 11 } 13 int horizontal_vertical_p2(int x0, int x1, int x2, int x3){ return x0^x2; 16 } 以下略.

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; s3 = x1 ^ x3 ^ p3; printf("%d %d %d %d %d %d %d %d --> ", x0, x1, x2, x3, p0, p1, p2, p3); 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 */ 以下略

42 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"); }

43 水平垂直パリティ検査符号 1ビットの誤りを訂正可能. 9ビットの情報に,6ビットのパリティを付加する例.符号化率0.6. x0 x1 x2
p0 x3 x4 x5 p1 x6 x7 x8 p2 p3 p4 p5

44 ハミング符号 (Hamming Code) 2ビットの誤り検出と1ビットの誤り訂正が可能 検査ビット長が m の場合,
任意の符号間のハミング距離が3以上 3ビット以上誤らなければ,他の符号結果と同じならない. 検査ビット長が m の場合, 2m-1 の符号を作り出す. つまり,情報ビット長は 2m-1-m となる. 検査ビット長3, 情報ビット長4, 符号全体長7 の場合,(7,4)のハミング符号

45 ハミング符号

46 ハミング符号 (検査ビット長3の例) 上記の3本全て,「1が偶数個」となるようにp0,p1,p2を定める. p0=x0 x1 x2
シンドローム 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 ただし加算は排他的論理和

47 ハミング符号 (検査ビット長3の例) ハミング符号 生成行列 p0=x0 x1 x2 p1=x1 x2 x3 p2=x0 x1 x3
ただし,加算は排他的論理和

48 ハミング符号 (検査ビット長3の例) ハミング符号 検査行列 x0 x1 x2 p0=0 x1 x2 x3 p1=0
のはず シンドローム (全て0のはず)

49 ハミング符号 (検査ビット長3の例) ハミング符号 誤り訂正 x0 x1 x2 x3 p0 p1 p2 s0 奇 s1 奇 s2 偶
シンドローム (全て偶のはず) 上記のようなシンドロームが得られたとする. 「奇数」が含まれているので誤りである. 誤りが1ビットしか無いと仮定すると, 「s0に含まれる」,「s1に含まれる」,「s2に含まれない」 はずである.→x2が誤り

50 ハミング符号 検査ビット3なら, 23=8通り. 全て0を除き8-1=7通り.横の長さ=全符号長=7 検査ビット長 m 符号長 2m-1
x0 x1 x2 x3 p0 p1 p2 検査ビット3なら, 23=8通り. 全て0を除き8-1=7通り.横の長さ=全符号長=7 検査ビット長 m 符号長 2m-1 情報ビット 2m-1-m (2m-1,2m-1-m)ハミング符号 全て異なる必要がある. (同一のあると,どちらが 誤ったのか判別不能) 全て0の列があっては困る. (そのビットがシンドロームに 影響を与えない)

51 水平垂直パリティ検査符号 #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, return x2^x3; int horizontal_vertical_p2(int x0, int x1, return x0^x2; int horizontal_vertical_p3(int x0, int x1, 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; 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, p1, p2, p3); 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 */ x1 = x1 ^ 1; /* Reversal */ printf("%d %d %d %d (x1 is error)\n", x0, x1, x2, x3); } else if( s0 == 0 && s1 == 1 && s2 == 1 && s3 == 0 ){ /* x2 is error */ x2 = x2 ^ 1; /* Reversal */ printf("%d %d %d %d (x2 is error)\n", x0, x1, x2, x3); } else if( s0 == 0 && s1 == 1 && s2 == 0 && s3 == 1 ){ /* x3 is error */ x3 = x3 ^ 1; /* Reversal */ printf("%d %d %d %d (x3 is error)\n", x0, x1, x2, x3); } else if( s0 == 1 && s1 == 0 && s2 == 0 && s3 == 0 ){ /* p0 is error */ p0 = p0 ^ 1; /* Reversal */ printf("%d %d %d %d (p0 is error)\n", x0, x1, x2, x3); } else if( s0 == 0 && s1 == 1 && s2 == 0 && s3 == 0 ){ /* p1 is error */ p1 = p1 ^ 1; /* Reversal */ printf("%d %d %d %d (p1 is error)\n", x0, x1, x2, x3); } else if( s0 == 0 && s1 == 0 && s2 == 1 && s3 == 0 ){ /* p2 is error */ p2 = p2 ^ 1; /* Reversal */ printf("%d %d %d %d (p2 is error)\n", x0, x1, x2, x3); } 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"); void main(){ int x0, x1, x2, x3; for(x0=0; x0<2; x0++){ for(x1=0; x1<2; x1++){ for(x2=0; x2<2; x2++){ for(x3=0; x3<2; x3++){ int p0, p1, p2, p3; p0 = horizontal_vertical_p0(x0, x1, x2, x3); p1 = horizontal_vertical_p1(x0, x1, x2, x3); p2 = horizontal_vertical_p2(x0, x1, x2, x3); p3 = horizontal_vertical_p3(x0, x1, x2, x3); printf("%d %d %d\n", x0, x1, p0); printf("%d %d %d\n", x2, x3, p1); printf("%d %d\n", p2, p3); printf("\n"); hv_parity_check(1,0,1,1,1,0,0,1); hv_parity_check(1,0,0,1,1,0,0,1); hv_parity_check(1,0,1,1,1,1,0,1); hv_parity_check(1,0,1,1,1,1,1,1); hv_parity_check(1,1,0,1,1,0,0,1); 水平垂直パリティ検査符号


Download ppt "プログラミング論 II 2008年9月25日 誤り検出,訂正符号 ハミング符号"

Similar presentations


Ads by Google