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

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

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

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

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

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

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

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

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

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

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

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

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

12 符号化

13 誤り検出符号

14 誤り訂正符号

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

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

17 演習 “abc” 文字コード

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

19 ここは見ないでまずは自分で考えてみよう 3 2 4 3 4

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

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

22 伝送部 #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; }

23 符号化・復号化 #define MOJI11A "01100001000“ #define MOJI11B "01100010010“
#define MOJI11C " “ #define MOJI11D " “ #define MOJI11E " “ 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 '?';

24 メインプログラム 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");

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