岡村耕二 http://okaweb.ec.kyushu-u.ac.jp/lectures/in/ ビット誤りと訂正 岡村耕二 http://okaweb.ec.kyushu-u.ac.jp/lectures/in/ 情報ネットワーク

デジタル通信 ICT機器で使われる様々な情 報の種類 計算機 ネットワーク 文字、画像、動画、音声 数字(Byte=8bit) ビット列 情報は計算機やネットワークでどのように扱われているか ICT機器で使われる様々な情 報の種類 文字、画像、動画、音声 計算機 数字(Byte=8bit) ネットワーク ビット列

デジタル通信(処理) 1ビットでも誤ると しかも 通信 嘘の情報 誤りは検知できない 受信者は送信者がどのような 信号を出したかわからない。 CD/DVD 書き込み、読み出し 1ビットでも誤ると 嘘の情報 しかも 誤りは検知できない 受信者は送信者がどのような 信号を出したかわからない。

ビット誤り 1bit の処理に誤りが発生する確率を 0.1% として、 1024bit が処理された時の誤り率 1bit 2bit 1-(1-0.01)^1 =0.001 2bit 1-(1-0.001)^2=0.002 16bit 1-(1-0.001)^16=0.016 1024 1 - (1 – 0.001) ^ 1024 = 0.641

ビット誤りが発生しても自動的に訂正して欲しい たくさん送る？ 1101 1001 をたくさん送る 1101 1001 1101 1001 1101 1001

誤りの発生する状況でも正しく情報を伝達する(1) 名簿 岡村耕二 中村誠一 金子耕一 誤り訂正ができる例 中村耕二さんをお願いします。 間違えてるけど岡村耕二さんか ひと文字くらいは間違えているかもという前提で。

誤りの発生する状況でも正しく情報を伝達する(2) 名簿 金井耕一 金子耕助 金子誠二 誤り検出ができる例 間違えているけど 金井耕一さんか 金子耕助さんか 金子耕一さんをお願いします。 ひと文字くらいは間違えているかもという前提で。

誤りの発生する状況でも正しく情報を伝達する(3) 名簿 岡村耕二 岡村誠二 金子耕助 誤り検出できない例 岡村耕二さんをお願いします。 間違えていなければ岡村耕二さんかな？ 岡村誠二さんの間違いかな？ ひと文字くらいは間違えているかもという前提で。

誤りの発生する状況でも正しく情報を伝達する(4) 名簿 岡村Pretty耕二 岡村Sweet 誠一 金子Dandy 耕助 冗長化してみる 岡村Pretty誠二さんをお願いします。 名前間違えているけど 岡村Pretty耕二さんか ひと文字くらいは間違えているかもという前提で。

誤り検出/訂正 ハミング距離 【定義】長さの等しい2つのビット列 x, y に対して x と y のハミング距離を以下で 定義する。 d(x,y) (x[i]≠[y[i]となる i の個数) x = 1011 0100 1110 y = 1001 0101 1010 d(x,y)=3

誤り検出・訂正 高々 s 個の誤り検出 【定理】 高々 t 個の誤り検出 符号語どうしがハミング距離 s+1 以上離れて いれば、高々 s 個の誤りの自動検出が可能 高々 t 個の誤り検出 符号語どうしがハミング距離 2t + 1 以上離れ ていれば、高々 t 個の誤りについて自動訂正 が可能

符号化

誤り検出符号

誤り訂正符号

ハミング距離が2以上なので、高々１文字の誤り検出が可能 金井耕一 金子耕助 金子誠二 2 3 ハミング距離が2以上なので、高々１文字の誤り検出が可能

ハミング距離が3以上なので、高々１文字の誤り訂正が可能 岡村耕二 中村誠一 金子耕一 3 ハミング距離が3以上なので、高々１文字の誤り訂正が可能

演習 “abc” 文字コード 01100001 01100010 01100011 97 98 99

1ビット誤りの訂正ができるようにアルファベットを符号化 検査ビット a 97 0110 0001 b 98 0110 0010 c 99 0110 0011 d 100 0110 0100 e 101 0110 0101 ハミング距離が3以上になるように検査ビットを設計して、高々１ビットの誤り訂正を可能にする 0110 0001 0110 0010 0110 0011 0110 0100 0110 0101 2 1 3

ここは見ないでまずは自分で考えてみよう 0110 0001 00 0110 0010 01 0110 0011 11 0110 0100 01 0110 0101 11 3 2 4 0110 0001 000 0110 0010 010 0110 0011 111 0110 0100 011 0110 0101 110 3 4

ここは見ないでまずは自分で考えてみよう 0110 0001 0110 0010 0110 0011 0110 0100 0110 0101 2 1 3 000 010 111 011 110 1 3 2 検査ビット a 97 0110 0001 000 b 98 0110 0010 010 c 99 0110 0011 111 d 100 0110 0100 011 e 101 0110 0101 110

コンピュータでシミュレーション 11bit の処理で、1ビットだけ反転する 可能性がある。 復号 文字列が正しく送れるか？ 11bit 単位で、1bit コピーするときにある 確率でbit が反転する。1bit反転したら、 次の11bit 単位までは反転しない。 復号 ハミング距離が1以下のものを選ぶ 文字列が正しく送れるか？

伝送部 #define DENSOERR 1 denso(src,dst,u,b) char *src,*dst; int u,b; { int i; int f=DENSOERR,cnt=0; for(i=0;i<b;i++){ if(f && rand()%10<3){ dst[i]= '0' + ('1' - src[i] ); f--; }else dst[i]=src[i]; cnt++; if(cnt==u){ f=DENSOERR; cnt=0; }

符号化・復号化 #define MOJI11A "01100001000“ #define MOJI11B "01100010010“ #define MOJI11C "01100011111“ #define MOJI11D "01100100011“ #define MOJI11E "01100101110“ char　moji11[5][11]={MOJI11A, MOJI11B, MOJI11C, MOJI11D, MOJI11E}; enc11(src,dst) char src,*dst; { strncpy(dst,moji11[src-'a'],11); } char dec11(src) char *src; { int i; for(i=0;i<5;i++){ int h=0,j; for(j=0;j<11;j++) if(src[j]!=moji11[i][j]) h++; if( h<2) return 'a' + i; } return '?';

メインプログラム main() { char iii[1024],sss[1024],ddd[1024]; int i; fscanf(stdin,"%s",iii); bzero(sss,1024); bzero(ddd,1024); for(i=0;i<strlen(iii);i++){ char enc[16]; bzero(enc,16); enc11(iii[i],enc); 　　strncpy(sss + i * 11,enc,11); } printf("%s\n",iii); printf("%s\n",sss); denso(sss,ddd,11,strlen(sss)); printf("%s\n",ddd); for(i=0;i<strlen(ddd);i+=11){ char dec[16]; strncpy(dec,ddd + i ,11); printf("%c",dec11(dec)); } printf("\n");

コンピュータでシミュレーション 伝送誤りの発生を確認する。 伝送誤りが自動訂正されているこ とを確認する。 誤り発生率を厳しくしてみる。 1ビット反転してもさらに反転させ る。