(Communication and Network) 1
1 0/1, a/b/c/ {0, 1} S = {s 1, s 2,..., s q } S x = X 1 X 2 X 3 X n S (n = 1, 2, 3,...) n n s i P (X n = s i ) X m (m < n) P (X n = s i X n 1 = s j ) p i = P (X n = s i ) n p ij = P (X n = s i X n 1 = s j ) n 2
p i p ij p i 0 p ij 0 q p i = 1 q p ij = 1 i=1 { } r i=1 T = {t 1,..., t r } 3
2 2 T = Z 2 {0, 1} 3 3 3 ( ) w w w ϵ 0 ( ) T n n T T + = T {ϵ} T = n 0 T n T + = n 1 T n 4
C : S T + (S T + ) w i = C(s i ) w i s i C C = {w 1, w 2,..., w q } C S S C : s = s i1 s i2 s i3 s in t = w i1 w i2 w i3 w in w in = C(s in ) C = {w i1 w i2 w i3 w in w ij C, n 0} l i = w i L(C) C L(C) = q i=1 p i l i 5
1.1 t s L(C) i (i = 1, 2, 3, 4, 5, 6) 2 s i = i p i = 1 6 w 1 = 1, w 2 = 10, w 3 = 11, w 4 = 100, w 5 = 101, w 6 = 110 s = s 1 s 2 s 5 t = 110101 1 6 (1 + 2 + 2 + 3 + 3 + 3) = 7 3 ( 110 ) 6
1.2 ( u.d. ) C : S T 2 u 1 u m = v 1 v n (u 1,..., u m, v 1,..., v n C) m = n u i = v i C w 1 = 001, w 2 = 010, w 3 = 011, w 4 = 100, w 5 = 101, w 6 = 110 w 1 = 0, w 2 = 01, w 3 = 011, w 4 = 0111, w 5 = 01111, w 6 = 011111 t = 001011 7
1.2.1 C 0 = C C n = {w T + uw = v, u C, v C n 1 or u C n 1, v C} C = n 1 C n C 1 = {w T + uw = v, u, v C} C n C = {1, 10, 11, 100, 101, 110} C 1 = {0, 1, 00, 01, 10} C 2 = {0, 1, 00, 01, 10} C = {0, 1, 00, 01, 10} C = {0, 01, 010, 111} C 1 = {0, 1, 10} C 2 = {1, 10, 11} C 3 = {1, 11}, C 4 = {1, 11}, C = {0, 1, 10, 11} 8
C = {0, 01, 011, 0111, 01111, 011111} C 1 = {1, 11, 111, 1111, 11111} C 2 = ϕ C 3 = ϕ C = {1, 11, 111, 1111, 11111} C C = ϕ ( 5 ) C = {1, 10, 11, 100, 101, 110} C = {0, 01, 011, 0111, 01111, 011111} 9
1.3 w 1 = 0, w 2 = 01, w 3 = 11 C 1 = {1} C 2 = {1} C = {1} 0111110 s 2 s 3 s 3 01111110 s 1 s 3 s 3 s 3 1 1 01 11 w 1 = 0, w 2 = 10, w 3 = 11 0101111100 s 1 s 2 s 3 s 3 s 2 s 1 w i1 w i2 w in w i1 w i2 w in ( ) s i1 s i2 s in 10
w i w j (j i) ( ) C 1 = ϕ (C 1 = ϕ) 11
1.3.1 12
13
14
r l 1, l 2,..., l q q r l i 1 ( ) i=1 l 1 l 2 l q l = l q (l i ) l l i ( ) r l l i 15
l 1 l 2 l q q r l l i r l q i=1 r l i > 1 q r l l i > r l i=1 i=1 16
17
1.3.2 r l 1, l 2,..., l q q r l i 1 i=1 ( ) ( ) 18
l = max(l 1, l 2,... l q ) m = min(l 1, l 2,... l q ) K K = q i=1 r l i K n (K n ) r l i 1 r l i 2 r l in = r j j = l i1 + l i2 + + l in m l i1, l i2,..., l in l mn j ln K n K n = ln j=mn N j,n r j 19
N j,n j n n w i1 w i2 w in j j r j N j,n r j K n = ln i=mn N j,n r j ln i=mn r j r j = ln i=mn 1 = (l m)n + 1 n K n 1 K > 1 n K 1 20
2 w 1, w 2,..., w q l 1, l 2,..., l q w 1, w 2,..., w q p 1, p 2,..., p q w 1, w 2,..., w q L(C) q L(C) = p i l i i=1 p 1 = 1/2 p 2 = 1/4 p 3 = 1/8 p 4 = 1/8 C 1 w 1 = 00 w 2 = 01 w 3 = 10 w 4 = 11 L(C 1 ) = 1 2 2 + 1 4 2 + 1 8 2 + 1 8 2 = 2 C 2 w 1 = 0 w 2 = 10 w 3 = 110 w 4 = 111 L(C 1 ) = 1 2 1 + 1 4 2 + 1 8 3 + 1 8 3 = 1.75 21
( ) r p i ( ) S r r ( ) 22
2.1 2 2 T = Z 2 = {0, 1} S s 1, s 2,..., s q 2, s q 1, s q p 1, p 2,..., p q 2, p q 1, p q s s q 1 s q (s = (s q 1 s q )) S s 1, s 2,..., s q 2, s p 1, p 2,..., p q 2, (p q 1 + p q ) S C = {w 1, w 2,..., w q 2, w } S C = {w 1, w 2,..., w q 2, w 0, w 1} C C 23
2 1. S (0) = S k = 1 2. k == q 1 C (q) = ϵ goto 5 3. S (k) 2 S (k+1) 4. k = k + 1 goto 2 5. k == 0 6. S (k 1) S (k) C (k) w (k) 2 w (k) 0 w (k) 1 S (k 1) C (k 1) 7. k = k 1 goto 5 (1 4 5 7 ) 24
2.1.1 L(C) = 0.3 2 + 0.2 2 + 0.2 2 + 0.2 3 + 0.1 3 = 2.3 25
2.1.2 1. p (k) S (k 1) S (k) 2. p (k 1) p (k 1) 2 i j p (k) = p (k 1) i + p (k 1) j 3. L(C (k 1) ) L(C (k) ) w (k 1) 0 1 L(C (k 1) ) L(C (k) ) = p (k) 26
2.1.3 2 w 1 w 2 w w0 w1 S 2 D ( ) ( ) S 2 D (1 ) D σ(d) σ(d) = i l i σ(d) D 0 D 0 1 w w0 w1 2 D 0 D 27
w D 0 w0 w1 w D 0 D σ(d 0 ) = σ(d 0) 1 D 0 ( ) 2 ( ) q 1 C = {ϵ} L(C) = 0 q 1 q C s 1,..., s q 2, s q 1, s q ( ) s 1,..., s q 2, (s q 1 s q ) C C L(C) L(C ) = p q 1 + p q 28
C D 2 s i s j (i < j) s i s q 1 s j s q D l i D s i s j l i l q 1 l j l q (l i, l j, l q 1, l q D ) p i p q 1, p j p q L(D ) L(D) = p q 1 l q 1 + p q l q + p i l i + p j l j (p q 1 l i + p q l j + p i l q 1 + p j l q ) = (p q 1 p i )(l q 1 l i ) + (p q p j )(l q l j ) 0 L(D) L(D ) L(D) s q 1 s q D s q 1 s q D L(D) L(D ) = p q 1 + p q = L(C) L(C ) C L(C ) L(D ) L(C) L(D) D C 29
2.2 r 2 r 1 s s w w 0, w 1,..., w r 1 r 1 r n(r 1) + 1 0 (n ) r = 3, p 1 = 0.4, p 2 = 0.3, p 3 = 0.2, p 4 = 0.1 1 s 5 p 5 = 0 w 1 = 0, w 2 = 1, w 3 = 20, w 4 = 21 ( w 4 = 22) w 1 = 0, w 2 = 10, w 3 = 11, w 4 = 12 (2 ) 30
3 3.1 I(s i ) s i I(s i ) I(s i ) s i p i p i = 1 I(s i ) = 0 (P (s i s j ) = P (s i )P (s j )) I(s i s j ) = I(s i ) + I(s j ) I r (s i ) = log r (p i ) r r = 2 [bit] r 31
q H r (S) = p i I r (s i ) = i=1 q p i log r p i i=1 q q H(S) = p i I(s i ) = p i log p i i=1 p = 0 p log p = 0 H(p) S p 1 p 2 i=1 H(S) = H(p) p log p (1 p) log(1 p) p = 1/2 1 H(p) = H(1 p) 32
p log p 33
H(p) = p log p (1 p) log(1 p) 34
3.2 H r (S) = i p i log r p i H r (S) 0 H r (S) = 0 i p i = 1 x > 0 ln x x 1 x = 1 (ln x = log e x) 35
x i 0 y i > 0 i x i = i y i = 1 x i log r x i x i log r y i i i ( ) y x i log i r = 1 x x i i ln r i ln y i 1 x i i ln r i = 1 (y ln r i x i ) = 1 (1 1) = 0 ln r i x i ( yi x i 1 y i /x i = 1 i y i = 0 x i = 0 x i log r y i ) 36
( ) S q H r (S) log r q p 1 = p 1 = = p q = 1/q ( ) x i = p i y i = 1/q H r (S) = p i log r p i i i p i log r (1/q) = log r q 37
3.3 C S r ( ) C l 1, l 2,..., l q L(C) H r (S) K = q i=1 r l i y i = r l i/k q i=1 y i = 1 p.36 38
K 1 (log r K 0) q H r (S) = p i log r p i = i=1 q p i log r y i = i=1 q p i l i + i=1 L(C) q p i log r (r l i/k) i=1 q p i log r K = L(C) + log r K i=1 39
i log r p i ( ) p i = y i log r K = 0 (K = 1) log r p i = l i log r p i l i = log r p i q q r l i = p i = 1 i=1 i=1 η H r(s) L(C) 40
S p 1 = 1/2 p 2 = 1/4 p 3 = 1/8 p 4 = 1/8 C w 1 = 0 w 2 = 10 w 3 = 110 w 4 = 111 H 2 (S) = 1 2 log 1 2 2 1 4 log 1 2 4 1 8 log 2 1 8 1 8 log 2 L(C) = 1 2 1 + 1 4 2 + 1 8 3 + 1 8 3 = 1.75 η = 1.75/1.75 = 1.0 1 8 = 1.75 S p 1 = 0.3 p 2 = 0.2 p 3 = 0.2 p 4 = 0.2 p 5 = 0.1 C w 1 = 00 w 2 = 10 w 3 = 11 w 4 = 010 w 4 = 011 H 2 (S) = 0.3 log 2 0.3 0.2 log 2 0.2 0.2 log 2 0.2 0.2 log 2 0.2 0.1 log 2 0.1 = 2.2464 L(C) = 0.3 2 + 0.2 2 + 0.2 2 + 0.2 3 + 0.1 3 = 2.3 η = 2.2464/2.3 = 0.9767 41
3.4 x x x 2.3 = 3 4.0 = 4 0 l i = log r p i log r p i log r p i < log r p i + 1 q q r l i p i = 1 i=1 i=1 H r (S) L(C) < H r (S) + 1 0 H r (S) L(C) H r (S) + 1 42
( 0 p 0 = 1 p 1 = 0 w 0 = 0 w 1 = 1) H r (S) + 1 H r (S) + 1 S p 1 = 0.3 p 2 = 0.2 p 3 = 0.2 p 4 = 0.2 p 5 = 0.1 log 2 0.3 = 1.73 log 2 0.2 = 2.321 log 2 0.1 = 3.32 L(C) = 0.3 2 + 0.2 3 + 0.2 3 + 0.2 3 + 0.1 4 = 2.8 η = 0.8214 ( L(C) = 2.2464 ) 43
3.5 S {s 1,..., s q } p 1,..., p q T {t 1,..., t q } p 1,..., p q S T S T (s i, t j ) (s i, t j ) p i p j S T ( ) H r (S T ) = q i=1 H r (S T ) = H r (S) + H r (T ) q p i p j log r p i p j = j=1 i = p i log r p i i j = H r (S) + H r (T ) p j j p i p j (log r p i + log r p j ) j p j log r p j i p i 44
n S 1, S 2,..., S n S n S 1 S 2 S n = (S 1 S 2 S n 1 ) S n S 1, S 2,..., S n s 1,i1, s 2,i2,..., s n,in p 1,i1, p 2,i2,..., p n,in S 1, S 2,..., S n S 1 S 2 S n (s 1,i1, s 2,i2,, s n,in ) ( 1 ) p 1,i1 p 2,i2 p n,in ( ) S 1, S 2,..., S n H r (S 1 S 2 S n ) = H r (S 1 ) + H r (S 2 ) + + H r (S n ) 45
S 1, S 2,..., S n S n S n S 1 S 2 S n H r (S n ) = nh r (S) 46
3.6 L n S n H r (S n ) L n H r (S n ) + 1 S n S n S 1 L n /n H r (S n ) = nh r (S) H r (S) L n n H r(s) + 1 n n 1/n 0 n S n S r H r (S) 47
p 1 = 3/4 p 2 = 1/4 H 2 (S) = 0.81128 S w 1 = 0, w 2 = 1 L 1 = 1 S 2 w 11 = 0, w 12 = 10, w 21 = 110, w 22 = 111 L 2 /2 = 0.84375 S 3 w 111 = 0, w 112 = 110, w 121 = 100, w 122 = 11100, w 211 = 101, w 212 = 11101, w 221 = 11110, w 222 = 11111 L 3 /3 = 0.82292 48
3.7 p ij j i p i i ( ) p i = j p ij p j j i ( ) log p ij i p ij log r p ij 49
j H r (S) = p j p ij log r p ij j i i p ij = 1 p.36 j i p ij log r p ij i p ij log r p i H r (S) = j i p j p ij log r p ij j i p ij p j log r p i = i p i log r p i 50
4 ( ZIP, LHA, JPEG ) 51