バイオ情報科学

情報量の話
1
情報量
クイズ
次のどちらが「情報量が多い」と感じるか。
理由も書け。
問１
a) A君が遅刻をした。（よく遅刻する人の場合）
b) B君が遅刻をした。（いつも早く来る人の場合）
問２
a) 東京に雪が降った。
b) 金沢に雪が降った。
2
情報量
めったに起こらないことは、
情報量が多いと感じる。
ある事象xが起こる確率をP(x)とする。
自己情報量
と定義する。
i( x)   log2 P( x)
問題
1) コインをころがして、裏か表を出すとする。
表が出る事象をxとする時、i(x)を求めよ。
2) 自己情報量i(x)は、P(x)の減少関数であることを
説明せよ。
3) i(x)が加法的であること、つまり事象xとyが独立の
時、xとyが両方起こる事象をzとすると、
i( z)  i( x)  i( y) を示せ。
3
補助問題：対数関数
y  loga x
a 1
１．意味を述べてください。
２．グラフを描いてください。
３．対数関数の性質を述べてください。
４．底の変換公式を書いてください。
５．対数関数の微分を書いてください。
a) 底がeの場合
b) 底がa (a>1)の場合
4
A  a1, a2 ,  , an 
平均情報量
に対して、
n
事象の列
k 1
エントロピーとも言う。
H ( A)   P(ak ) log2 P(ak )
問題
1)
1
1
A  a1 , a2 , P(a1 )  , P(a2 ) 
の時、H(A)を求めよ。
2
2
2) A  a , a , P(a )  1 , P(a )  3 の時、H(A)を求めよ。
1
2
1
2
4
4
3) 1)と2)のH(A)は、どちらが大きいか。なぜか。
4) n=2の時、a1の起こる確率をpとすると、
H ( p)   p log p  (1  p) log(1  p)
を示せ。
5) 4)の場合のH(p)のグラフを書け。
5
符号化の話
6
符号化
情報源の記号を0,1を使って書く。
例：記号a, b, c, dを0,1を使って書く。
問１．a -> 0, b -> 01, c-> 10, d-> 11の符号化を使って、
abcddcba を符号化せよ。
問２．問１の符号化の方法の場合、復号化
（元のa, b, c, dの配列に戻すこと）が一意的でない。
例をあげよ。
問３．a-> 0, b-> 10, c-> 110, d-> 1110 の方法では、
復号化が一意的であることを説明せよ。
問４
a-> 0, b-> 01, c-> 011, d-> 0111の方法で、
復号化が一意的であることを説明せよ。
問５問３、４の符号化の方法により、00101101110
を復号化せよ。
7
誤りの検出
パリティチェック
符号列に余分の符号１ビットを付ける。
偶数パリティ各桁の和が0になるようにする（１ビット計算）
奇数パリティ
1
問題１
1011011に符号ビットを付ける。
a) 偶数パリティの時の符号ビットを求めよ。
b) 奇数パリティの時の符号ビットを求めよ。
問題２パリティチェックによって、
検出できる誤りはどんな場合か、書け。
8
誤りの検出２
偶数パリティで考える。
行と列の両方にパリティビットを付ける。
問題１４ビットを2x2に並べる。□にパリティビットを入れよ。
００ □
１０ □
□□
問題２１６ビットを4x4に並べる。□のパリティビットを求めよ。
０１０１ □
１１００ □
１０１１ □
０００１ □
□□□□
問題３
この方法で検出できる誤り、検出できない誤りを述べよ。
9
ハミング距離
n
h(x, y )    ( xk , yk )
k 1
 ( xk , yk )  0( xk  yk ),
1( xk  yk )
異なる記号がいくつあるかを示す。
問題
x  101000,
y  110010
の時のハミング距離を求めよ。
10

Download Report