В.В. Лидовский - Теория Информации

  • Published on
    28-Jul-2015

  • View
    376

  • Download
    4

Embed Size (px)

Transcript

<p> www.kodges.ru wbooks.ifolder.ru </p> <p>www.kodges.ru</p> <p>. . </p> <p>www.kodges.ru</p> <p>. . </p> <p> 2003www.kodges.ru</p> <p> . . : . .: ?????????, 2003. 112 . ISBN ?-????-????-?.</p> <p> . , . , , , . , , , Internet. . . . 23 . . 28. : (. -. . . . ), . . </p> <p> plain TEX, AMS-Fonts, PICTEX TreeTEX</p> <p>www.kodges.ru</p> <p> 108 , - 5 . . . . 1995 . (220200). (2, 9, 3336) , . : (...), , (..) .. , , . 1 9 , , .. , , , , , , , . 1018 . (-, , ), -. . . , . 19 . () , , . , , , . 2027 3</p> <p>www.kodges.ru</p> <p> . . 23- . 2832 . , , . . Internet. , , . , , . , . , , , . , , , . ., . . . . 1. . , , . , , . : , , , , . , . . . ( ) : , , , , . ( 1948 , ) (Wiener, ) (Shannon, ). 4</p> <p>www.kodges.ru</p> <p> , , , , , , , . , . , , . : . , , . . . . . 50- , , , ( ) . , , ( ). , , . . . , , .. () . , , , . ., , , . , , . , 5</p> <p>www.kodges.ru</p> <p> , , . , , . 2. . ( ). , , . ASCII (American Standard Code for Information Interchange), . ( , , , ) 0 127. :var i: byte; begin for i := 32 to 126 do write(i:6, chr(i):2); writeln end.</p> <p> ASCII, ASCII (ASCII+), 256 ( 0 255). 128 ASCII , 128 . , ASCII . , , . , 65 ASCII A, , . A, , A, 9.5 , A . (, Fine Reader). 6</p> <p>www.kodges.ru</p> <p> 1 W w ASCII? 3. : () (). , . , , . : , .. , , () . ( ) : - . , (T = 1/) (. . 1)................. ................... .... ..... .... ... ... .. . ... .... ... ... ... ... .. ... .. .. .. ... ... .. ... ... .. ... ... .. ... ... ... . ... .. .. .. ... . ............................................................................................................................... ........................................................... ............................................... .................... . .. .. .. . .. . ... ... ... .. .. . ........... ... .............. ... . ... ... ... ... . .. .. .. .. ... . . .. . . . .. ... ... .. ... ... ... ... ... .... .... ... ... .. ...... ....... .......... ........... .. ......</p> <p>t</p> <p>T</p> <p>... .. . .............................................................................................................................. ............................................................................................................................. .. . . ... ... ... . .............. ............... .. . . ... . . ..</p> <p> T . 1 </p> <p>t</p> <p> , . , , , , , . . 7</p> <p>www.kodges.ru</p> <p>, (Nyquist). , , A sin(t + ), A , , t . , , [17]. -, . , , 20 , . 40 ( 44.1 ). , : , . , . , 3 . . (- ) ADC (Analog to Digital Convertor, A/D), (- ) DAC (Digital to Analog Convertor, D/A). 2 DAT 48 . , ? 4. , , . , . . . , . 8</p> <p>www.kodges.ru</p> <p> - - . , , . , , , , . . (bit, binary digit). . , . . . . , 8 (byte), 4- . B . , (K), (M), (G ), (T), (P ) . 10, : 210 = 1024 103 , 220 106 , 230 109 , 240 1012 , 250 1015 . , 1 KB = 8 bit = 1024 B = 8192 bit, 1 = 1024 = 1 048 576 = 8192 . , : ( ) , ( ) . , , . . , , . , f (t), F (t) f (t). , . , . , , . . 2 . , , , . 9</p> <p>www.kodges.ru</p> <p> . -: ( ), . , , . . P. 2 (baud): 1 = 1 / (bps). , , 10 Kbaud = 10240 baud. , . . , , .. . , . , , 5 . 3 ? 5. , (), () . . , ( ). . : , , . . 3. , , . , , . , , 1000 , 1 . : 140 , 3.1 , (10100 ) 10</p> <p>www.kodges.ru</p> <p> 330 , (110 ) 30300 , ( ) 30 , ( ) 0.15 400 , ( ) 400700 , ( ) 0.71.75 . . . 3 : . , : () (ISDN, Integrated Services Digital Networks) 57128 . ( 110 ). . 50 ! 6. , , : 1. a = b, , a b. a2 = b2 , , , .. , . a3 = b3 , ; 2. . , ; 3. .. .. .. .., , .. ..; 4. . . . X, - .. Y = X + Z, Z .., . , .. Y , X. ( Z ), 11 </p> <p>www.kodges.ru</p> <p> Y . Y X. 1865 . . 1921 . , , . 1948 . . , , , , . 4 x = 5 x &gt; 3? 7. , .. . . . ... X Y , P (X = Xi ) = pi , P (Y = Yj ) = qj P (X = Xi , Y = Yj ) = pij , , X Y , I(X, Y ) =i,j</p> <p>pij log2</p> <p>pij . pi q j</p> <p> . . X Y , pX (t1 ), pY (t2 ) pXY (t1 , t2 ), I(X, Y ) =R2</p> <p>pXY (t1 , t2 ) log2</p> <p>pXY (t1 , t2 ) dt1 dt2 . pX (t1 )pY (t2 )</p> <p>, P (X = Xi , X = Xj ) = 0, i = j P (X = Xi ), i = j 12</p> <p>www.kodges.ru</p> <p>, , I(X, X) =i</p> <p>pi log2</p> <p>pi = p i pi</p> <p>pi log2 pi .i</p> <p> ... X H(X) = HX = I(X, X). : 1) I(X, Y ) 0, I(X, Y ) = 0 X Y ; 2) I(X, Y ) = I(Y, X); 3) HX = 0 X ; 4) I(X, Y ) = HX + HY H(X, Y ), H(X, Y ) = i,j pij log2 pij ; 5) I(X, Y ) I(X, X). I(X, Y ) = I(X, X), X Y . 1) x ex1 x ( x = 1) x1 ln x x1 log2 x. ln 2 I(X, Y ) =i,j</p> <p>pi q j pij log2 piji</p> <p>piji,j</p> <p>pi qj pij</p> <p>1</p> <p>ln 2</p> <p>=</p> <p>=i,j</p> <p>pi qj pij = ln 2</p> <p>pi</p> <p>j</p> <p>qj ln 2</p> <p>i,j</p> <p>pij</p> <p>=</p> <p>11 = 0, ln 2</p> <p>. . I(X, Y ) = 0 pij = pi qj i j , . . X Y . X Y , pij = pi qj , , 1 , , 0, , I(X, Y ) = 0; 2) ; 3) HX = 0, , HX , , , X ; 4) </p> <p>pij = pi ,j i</p> <p>pij = qj ,</p> <p>HX = i</p> <p>pi log2 pi = i,j</p> <p>pij log2 pi , pij log2 qji,j</p> <p>HY = j</p> <p>qj log2 qj = 13</p> <p>www.kodges.ru</p> <p>HX + HY H(X, Y ) =i,j</p> <p>pij (log2 pij log2 qj log2 pi ) = I(X, Y ); HX </p> <p>5) I(X, Y ) = HX + HY H(X, Y ) HY H(X, Y ) 0.</p> <p>HY H(X, Y ) = i,j</p> <p>pij log2 qj +i,j</p> <p>pij log2 pij =i,j</p> <p>pij log2 (pij /qj ),</p> <p> pij = P (X = Xi , Y = Yj ) qj = P (Y = Yj ), 1 , , 0, , 0. HX = I(X, X) = I(X, Y ), i pij qj , 0. pij = P (X = Xi , Y = Yj ) = P (X = Xi /Y = Yj )P (Y = Yj ) {qj , 0} P (X = Xi /Y = Yj ) {0, 1}, , X Y .</p> <p> . . X Y , , .. I(X, Y ) = 0. . . . . X1 , X2 Y . X1 X2 , 1- 2- , Y = X1 +X2 . I(Y, X1 ), I(X1 , X1 ), I(Y, Y ). ... X1 X2 , .. . X1 1 2 3 4 5 6 p 1/6 , .. j = 1...6 qj = P (X1 = j) = 1/6. ... Y , P (Y = i) = P (X1 + X2 = i), i = 2...12,</p> <p> , X1 , X2 P (X1 = n, X2 = m) = P (X1 = n)P (X2 = m), pi = P (X1 + X2 = i) =1 n+m=i n,m 6</p> <p>P (X1 = n)P (X2 = m) =1 n+m=i n,m 6</p> <p>1/36.</p> <p>, Y : 14</p> <p>www.kodges.ru</p> <p>X2 \</p> <p>X1</p> <p>1 2 3 4 5 6</p> <p>1 2 3 4 5 6 7</p> <p>2 3 4 5 6 7 8</p> <p>3 4 5 6 7 8 9</p> <p>4 5 6 7 8 9 10</p> <p>5 6 6 7 7 8 8 9 9 10 10 11 11 12,</p> <p>Y = X1 + X2 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 5 4 p /36 /36 /36 /36 /36 /36 /36 /36 3/36 2/36 1/36 , .. i = 2...12, pi = P (Y = i) = (6 |7 i|)/36. ... X1 Y pij = P (Y = i, X1 = j) = P (Y = i/X1 = j)P (X1 = j), , P (Y = 2, X1 = 1) = P (Y = 2/X1 = 1)P (X1 = 1) = = P (X2 = 1)P (X1 = 1) = 1/36. pij = P (Y = i, X1 = j) =X1 \ Y</p> <p>1/36, 1 i j 0, . 7 1 /36 1 /36 1 /36 1 /36 1 /36 1 /36 8 0 1 /36 1 /36 1 /36 1 /36 1 /36 9 0 0 1 /36 1 /36 1 /36 1 /36 10 0 0 0 1 /36 1 /36 1 /36</p> <p>6,</p> <p>1 2 3 4 5 6 </p> <p>2 1 /36 0 0 0 0 0</p> <p>3 1 /36 1 /36 0 0 0 0</p> <p>4 1 /36 1 /36 1 /36 0 0 0</p> <p>5 1 /36 1 /36 1 /36 1 /36 0 06</p> <p>6 1 /36 1 /36 1 /36 1 /36 1 /36 0</p> <p>11 0 0 0 0 1 /36 1 /36</p> <p>12 0 0 0 0 0 1 /36</p> <p>I(Y, X1 ) =j=1 1 ij 6</p> <p>pij log26</p> <p>pij = pi q j</p> <p>1 = 367 8</p> <p>log2j=1 1 ij 6</p> <p>1 = 6pi12</p> <p>1 1 1 1 1 = ( log2 + log2 + + log2 + log2 )= 36 i=2 6pi i=3 6pi 6pi i=7 6pi i=6 15</p> <p>11</p> <p>www.kodges.ru</p> <p>=</p> <p>1 6 6 6 6 6 6 ((log2 +log2 + +log2 )+ +(log2 +log2 + +log2 )) = 36 1 2 6 6 5 1 3 6 1 = (2 log2 6 + 4 log2 3 + 6 log2 2 + 8 log2 + 10 log2 + 6 log2 1) = 36 2 5</p> <p>= (2 + 2 log2 3 + 4 log2 3 + 6 + 8 log2 3 8 + 10 log2 3 + 10 10 log2 5)/36 = = (10 + 24 log2 3 10 log2 5)/36 0.69 /. I(X1 , X1 ) = I(X2 , X2 ) = 2.58 /. 12 I(Y, Y ) = i=2 pi log2 pi = =6 j=1 qj</p> <p>log2 qj = log2 6 = 1 + log2 3 </p> <p>1 36 (2 log2 36 + 4 log2 18 + 6 log2 12 + 8 log2 9 + 10 log2 + 6 log2 6) = 36 5</p> <p>= (4+4 log2 3+4+8 log2 3+12+6 log2 3+16 log2 3+20+20 log2 310 log2 5+ + 6 + 6 log2 3)/36 = (46 + 60 log2 3 10 log2 5)/36 3.27 /. 0 &lt; I(Y, X1 ) = I(Y, X2 ) &lt; I(X1 , X1 ) = I(X2 , X2 ) &lt; I(Y, Y ), . 1 36 2 log2 6 = I(X1 , X1 )/18 I(X1 , Y ) 36, Y = 2 Y = 12, X1 . , Y = 7, X1 , 6 log2 1 = 0. , 4- , . H(Y, X1 ) = i,j pij log2 pij = log2 36 = 2(1 + log2 3) = 2HX1 5.17 /. I(Y, X1 ) = HX1 + HY H(X1 , Y ) = HY HX1 3.27 2.58 = 0.69 /. 4- , , . . . . . X , , . . . Y 0, , 1, . I(X, Y ) I(Y, Y ). ... X Y . X 1 2 3 4 5 6 Y 0 1 p 1/6 p 1/2 , i = 1...6 pi = P (X = i) = 1/6 , , j = 0...1 qj = P (Y = j) = 1/2. 16</p> <p>www.kodges.ru</p> <p> ... X 1 3 5 2 4 6 1 3 5 2 4 6 Y 0 0 0 1 1 1 1 1 1 0 0 0 p 1/6 0 , pij = P (X = i, Y = j) = I(X, Y ) =pij i,j pij log2 pi qj 1 j=0 qj log2 qj</p> <p>0, i + j , 1/6, . 1 = 6 6 log2 2 = 1 /.</p> <p>1 I(Y, Y ) = = 2 2 log2 2 = 1 /. , . . 1 . I(X, Y ) = I(Y, Y ) = 1 / 3- , X Y , , .. I(X, Y ) = I(X, X) = 1 + log2 3 2.58 /. , Y X, X Y . H(X, Y ) = i,j pij log2 pij = log2 6 = 1 + log2 3 = HX, I(X, Y ) = HX + HY HX = HY = 1 /.</p> <p> X p</p> <p>5 ... X, 1 2 3 4 5 6 7 0.1 0.2 0.1 0.05 0.1 0.05 0.3</p> <p>8 0.1.</p> <p> 6 . . . X1 X2 , ... Y , . X1 Y? 7 X1 ... Z = (X1 + 1)2 X2 , . . . X1 X2 0, 1? HX1 HZ. X1 Z? 8 . . . X1 , X2 . . . . I(X1 , X2 ), X1 X2 X1 X2 p 0 0 1/3 0 1 1 1 0 1 1/6 1/6 1/3. 17</p> <p>www.kodges.ru</p> <p> 9 . . . X1 X2 , 1 4. . . . Y , , . . Y = X1 + X2 . I(X1 , Y ), HX1 HY . 10 X1 ... Z = X1 X2 , HZ. ... X1 X2 . 11 ... X1 1, 0 1 . ... X2 2 0, 1 2. X1 X2 . Y = X1 +X2 . I(X1 , Y ), I(X2 , Y ), HX1 , HX2 , HY . 12 . . . X, Y , Z , Z = X + Y Y . X Y X 0 1 3 4 Y 2 2 p 1/8 1/8 1/4 1/2 p 3/8 5/8. 8. ... , ... (). 4 , .. 1/4. . . . X, . HX = 2. . : 100, 201, 310, 411. L(X), , X, .. M L(X) , X. L L(X) = len(code(X)), code(X) X , , , len . L ..., .. ... M L(X) = HX. ... X P (X = 1) = 1 1 3 , P (X = 2) = , P (X = 3) = P (X = 4) = , 4 8 16 18</p> <p>www.kodges.ru</p> <p>.. 1 . HX = 4 1 1 19 3 3 log2 + log2 8 + log2 16 = log2 3 1.186 /. 4 3 8 8 8 4</p> <p> : 10, 210, 3110, 4111, . . , ( ). 16 1- 12 , 2- 2-, 3- 1- 4- 1-. , (1 12 + 2 2 + 3 1 + 3 1)/16 = 1.375 / . . L(X). , L(X) : P (L(X) = 1) = 3/4, P (L(X) = 2) = 1/8, P (L(X) = 3) = 1/8. , M L(X) = 3 2 3 11 + + = = 1.375 /. 4 8 8 8</p> <p>, M L(X) &gt; HX. , . , , . , N , . , N pi ( i pi = 1), i . , , , N i=1 pi log2 pi , N , . , , , , . 13 . . . X ... X p code1(X) code2(X) code3(X) code4(X) 1 0.4 000 0 00 0 3 0.2 001 100 01 10 19 4 0.1 010 101 110 1110 5 0.2 011 110 10 110 6 0.1 111 111 111 1111.</p> <p>www.kodges.ru</p> <p> 14 ... X , . X. X, . 15 . . . X P (X = 2n ) = 1/2n , n = 1, 2, . . . . . . X, . 16 ... X , . X, . . . . X. 9. 50- XX . , , , . , , . inf (s) = log2 p(s), s , , p(s) s. : 1) s1 s2 ( s1 s2 ) , inf (s1 ) inf (s2 ); 2) inf (s) 0; 3) s , inf (s) = 0; 4) inf (s1 s2 ) = inf (s1 ) + inf (s2 ) p(s1 s2 ) = p(s1 )p(s2 ), . . s1 s2 . - , . : s1 a &gt; 3 s2 a = 7 , s2 s1 inf (s2 ) inf (s1 ); , s2 , s1 . - cont(s) = 1 p(s). , cont(s) = 1 2inf (s) inf (s) = log2 (1 cont(s)). 20</p> <p>www.kodges.ru</p> <p> 17 inf (s) cont(s) s1 , , 50%, s2 , 25%. 10. , , ( , , , ). , , , , .. - ZIP, GZ, ARJ . , ( 80- ), . . n , . . . Xi n ... X. [20], , . . ., , ..., .. M L(X) HX ... X . , [20] , (-, Fano), HX M L(X) 1. ... X1 X2 , . HX1 = HX2 I(X1 , X2 ) = 0, , H(X1 , X2 ) = HX1 + HX2 I(X1 , X2 ) = 2HX1 . X1 X2 . . . X = (X1 , X2 ). n- ... X = (X1 , X2 , . . . , Xn ) , H X = nHX1 . L1 (X) = L(X)/n, X = (X1 , X2 , . . . , Xn ), .. L1 (X) X. M L1 (X) X. M L(X) 1 H X M L(X) - X M L1 (X) 1/n HX1 M L1 (X) . 21</p> <p>www.kodges.ru</p> <p> , , , n , - . - , . , , . , . . &gt; 0 s, s ( n/s ), - , , , . , Y = (Y1 , Y2 , . . . , Yn/s ), Y1 = (X1 , X2 , . . . , Xs ), Y2 = (Xs+1 , Xs+2 , . . . , X2s ) . ., . . Yi = (Xs(i1)+1 , Xs(i1)+2 , . . . , Xsi ). H Y1 = sHX1 sM L1 (Y1 ) = M L(Y1 ) H Y1 + 1 = sHX1 + 1, , M L1 (Y1 ) HX1 + 1/s,</p> <p>.. s = 1/. s 1/. . . . . X1 , X2 , . . . Xn P (Xi = 0) = p = 3/4 P (Xi = 1) = q = 1/4 i 1 n. HXi = 4 1 3 3 log2 + log2 4 = 2 log2 3 0.811 /. 4 3 4 4</p> <p> 0 1 1 . 1. 2. 2- . . . X = (X1 , X2 ) X 00 01 10 11 p 9/16 3/16 3/16 1/16 code(X) 0 10 110 111 L(X) 1 2 3 3. 22</p> <p>www.kodges.ru</p> <p> M L1 (X) = 1 9 3 3 1 27 +2 +3 +3 /2 = = 0.84375, 16 16 16 16 32</p> <p>.. , . 3 0.823, 4 0.818 .. , . . . ( 0 1). . . . m . . . . X , M L(X) H X/ log2 m M L1 (X) HX1 / log2 m. , , M L(X) 1 H X/ log2 m M L1 (X) 1/n HX1 / log2 m, n = dim(X). , , , , . . , ..., . 11. - , ... , , 0, 1. X 00 01 10 1...</p>

Recommended

View more >