プログラミング論 II 2008年9月25日 誤り検出，訂正符号 ハミング符号 http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/ProgRo2/

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

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

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

計算機の世界での"情報" 全ての情報は，「(大量の)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進数表記)

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

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

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

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

(非常に簡単な)誤り訂正符号の例 ‘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

(非常に簡単な)誤り訂正符号の例 誤りが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 復元 失敗

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

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

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

パリティ “シンドローム” という 元情報 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 成功

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

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

検出失敗とハミング距離 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ビット反転)以内に別のものがなければ良い．より強力な誤り検出＆無駄遣い．

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

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

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

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

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

パリティの算出(再) [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

排他的論理和 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

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

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

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

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

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

パリティ検査関数 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; }

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

水平垂直パリティ検査符号 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

水平垂直パリティ検査符号 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

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

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

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

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

解答 1 10111001 1011 01001100 0101 11001011 1100

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

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 */ 以下略

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

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

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

ハミング符号

ハミング符号 (検査ビット長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 ただし加算は排他的論理和

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

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

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

ハミング符号 検査ビット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の列があっては困る． (そのビットがシンドロームに 影響を与えない)

水平垂直パリティ検査符号 #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); 水平垂直パリティ検査符号