パワーポイント

A  a1, a2 ,  , an 
平均情報量
に対して、
n
事象の列
k 1
エントロピーとも言う。
H ( A)   P(ak ) log 2 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)のグラフを書け。
1
符号化の話
2
符号化
情報源の記号を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
を復号化せよ。
3
誤りの検出
パリティチェック
符号列に余分の符号１ビットを付ける。
偶数パリティ各桁の和が0になるようにする（１ビット計算）
奇数パリティ
1
問題１
1011011に符号ビットを付ける。
a) 偶数パリティの時の符号ビットを求めよ。
b) 奇数パリティの時の符号ビットを求めよ。
問題２パリティチェックによって、
検出できる誤りはどんな場合か、書け。
4
誤りの検出２
偶数パリティで考える。
行と列の両方にパリティビットを付ける。
問題１４ビットを2x2に並べる。□にパリティビットを入れよ。
００ □
１０ □
□□
問題２１６ビットを4x4に並べる。□のパリティビットを求めよ。
０１０１ □
１１００ □
１０１１ □
０００１ □
□□□□
問題３
この方法で検出できる誤り、検出できない誤りを述べよ。
5
ハミング距離
n
h(x, y )    ( xk , yk )
k 1
 ( xk , yk )  0( xk  yk ),
1( xk  yk )
異なる記号がいくつあるかを示す。
問題
x  101000,
y  110010
の時のハミング距離を求めよ。
6
データ構造の話
7
データ構造
問題次のデータに最適な構造を図示せよ。
(1) 100人の成績。英語、数学など、科目数10個。
(2) 家族と親戚。自分、兄弟、祖父母、おじおば、いとこ。
(3) バクテリアの分裂。１時間に1回、2個に分裂する。
(4) 顧客の注文がどんどん入ってくる。
5個くらい注文がたまっている。
先に来たものから処理する。
(5) 来た書類を机の上にどんどん重ねる。
5個たまっている。
上から処理していく。
8

Download Report