Лидовский В.В., Теория информации
.pdfoB]AQ SHEMA PEREDA^I INFORMACII IZOBRAVENA NA RIS. 3.
ISHODNAQ |
|
|
|
|
|
|
[UMOZA]ITNOE |
|
||
! |
[IFROWANIE |
! |
SVATIE |
|
! |
|||||
INFORMACIQ |
|
KODIROWANIE |
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
# |
|
|
|
|
|
|
|
[UM! |
KANAL |
|
|||
|
|
|
|
|
SWQZI |
|
||||
|
|
|
|
|
|
|
|
# |
|
|
|
|
|
|
|
|
|
DEKODIROWANIE |
|
||
POLU^ENNAQ |
|
|
|
|
|
|
||||
|
|
|
|
|
|
[UMOZA]ITNYH |
. |
|||
|
DE[IFROWKA |
|
RASPAKOWKA |
|
|
|||||
INFORMACIQ |
|
|||||||||
|
|
|
rIS. 3 |
|
|
|
KODOW |
|
||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
eMKOSTX KANALA SWQZI BEZ [UMA MOVNO PRIBLIZITELXNO WY^ISLITX, ZNAQ MAKSIMALXNU@ ^ASTOTU WOLNOWYH PROCESSOW, DOPUSTIMU@ W \TOM KANALE. mOVNO S^ITATX, ^TO SKOROSTX PEREDA^I DANNYH MOVET BYTX NE MENX[E, ^EM \TA ^ASTOTA. nAPRIMER, PRI PREDELXNOJ ^ASTOTE, RAWNOJ 1000 gC, MOVNO OBESPE^ITX SKOROSTX PEREDA^I DANNYH NE MENX[E 1 kBOD.
pRIMERY KANALOW SWQZI I SWQZANNYH S NIMI PREDELXNYH ^ASTOT: TELEGRAF | 140 gC, TELEFON | DO 3.1 kgC, KOROTKIE WOLNY (10{100 M) | 3{30 mgC, ukw (1{10 M) | 30{300 mgC, SPUTNIK (SANTIMETROWYE WOLNY) | DO 30 ggC, OPTI^ESKIJ (INFRAKRASNYJ DIAPAZON) | 0.15{ 400 tgC, OPTI^ESKIJ (WIDIMYJ SWET) | 400{700 tgC, OPTI^ESKIJ (ULXTRAFIOLETOWYJ DIAPAZON) | 0.7{1.75 pgC.
tIPI^NYE SOWREMENNYE KANALY: TELEGRAFNYJ I TELEFONNYJ. pERSPEKTIWNYE, WNEDRQEMYE NYNE: OPTOWOLOKONNYJ (TERABODY) I CIFROWOJ TELEFONNYJ (ISDN, Integrated Services Digital Networks) | 57{128 kBOD. w REALXNYH OPTOWOLOKONNYH SISTEMAH SKOROSTX GORAZDO NIVE TEO-
RETI^ESKIH PREDELOW (REDKO PREWOSHODIT 1{10 gBOD).
nAIBOLEE [IROKO POKA ISPOLXZU@TSQ TELEFONNYE LINII SWQZI. zDESX DOSTIGNUTA SKOROSTX BOLEE 50 kBOD!
6. sPOSOBY IZMERENIQ INFORMACII
pONQTIE KOLI^ESTWA INFORMACII ESTESTWENNO WOZNIKAET, NAPRIMER, W SLEDU@]IH TIPOWYH SLU^AQH:
1. rAWENSTWO WE]ESTWENNYH PEREMENNYH a = b, ZAKL@^AET W SEBE INFORMACI@ O TOM, ^TO a RAWNO b. pRO RAWENSTWO a2 = b2 MOVNO SKAZATX, ^TO ONO NESET MENX[U@ INFORMACI@, ^EM PERWOE, T.K. IZ PERWOGO SLEDUET WTOROE, NO NE NAOBOROT. rAWENSTWO a3 = b3 NESET W SEBE INFORMACI@ PO OB_EMU TAKU@ VE, KAK I PERWOE;
9
2.pUSTX PROISHODQT NEKOTORYE IZMERENIQ S NEKOTOROJ POGRE[NOSTX@. tOGDA ^EM BOLX[E BUDET PROWEDENO IZMERENIJ, TEM BOLX[E INFORMACII OB IZMERQEMOJ SU]NOSTI BUDET POLU^ENO;
3.m.O. NEKOTOROJ SL.W. SODERVIT W SEBE INFORMACI@ O SAMOJ SL.W. dLQ SL.W., RASPREDELENNOJ PO NORMALXNOMU ZAKONU, S IZWESTNOJ DISPERSIEJ ZNANIE M.O. DAET POLNU@ INFORMACI@ O SL.W.;
4.rASSMOTRIM SHEMU PEREDA^I INFORMACII. pUSTX PEREDAT^IK OPISYWAETSQ SL.W. X, TOGDA IZ-ZA POMEH W KANALE SWQZI NA PRIEMNIK BUDET PRIHODITX SL.W. Y = X + Z, GDE Z | \TO SL.W., OPISYWA@]AQ POMEHI. w \TOJ SHEME MOVNO GOWORITX O KOLI^ESTWE INFORMACII, SODERVA]EJSQ W SL.W. Y , OTNOSITELXNO X. ~EM NIVE UROWENX POMEH (DISPERSIQ Z MALA), TEM BOLX[E INFORMACII MOVNO POLU^ITX IZ Y . pRI OTSUTSTWII POMEH Y SODERVIT W SEBE WS@ INFORMACI@ OB X.
w 1865 G. NEMECKIJ FIZIK rUDOLXF kLAUZIUS WWEL W STATISTI^E- SKU@ FIZIKU PONQTIE \NTROPII ILI MERY URAWNOWE[ENNOSTI SISTEMY. w 1921 G. OSNOWATELX BOLX[EJ ^ASTI MATEMATI^ESKOJ STATISTIKI, ANGLI^ANIN rONALD fI[ER WPERWYE WWEL TERMIN \INFORMACIQ" W MATEMATIKU, NO POLU^ENNYE IM FORMULY NOSQT O^ENX SPECIALXNYJ HARAK-
TER.
w 1948 G. kLOD {ENNON W SWOIH RABOTAH PO TEORII SWQZI WYPISYWAET FORMULY DLQ WY^ISLENIQ KOLI^ESTWA INFORMACIQ I \NTROPII. tERMIN \\NTROPIQ" ISPOLXZUETSQ {ENNONOM PO SOWETU PATRIARHA KOMPX@TERNOJ \RY FON nEJMANA, OTMETIW[EGO, ^TO POLU^ENNYE {ENNONOM DLQ TEORII SWQZI FORMULY DLQ EE RAS^ETA SOWPALI S SOOTWETSTWU@]I- MI FORMULAMI STATISTI^ESKOJ FIZIKI, A TAKVE TO, ^TO \TO^NO NIKTO NE ZNAET" ^TO VE TAKOE \NTROPIQ.
I uPRAVNENIE 4
kAKOE IZ SOOTNO[ENIJ NESET W SEBE BOLX[E INFORMACII x = 5 ILI x > 3?
7. wEROQTNOSTNYJ PODHOD K IZMERENI@ DISKRETNOJ I NEPRERYWNOJ INFORMACII
w OSNOWE TEORII INFORMACII LEVIT PREDLOVENNYJ {ENNONOM SPOSOB IZMERENIQ KOLI^ESTWA INFORMACII, SODERVA]EJSQ W ODNOJ SL.W. OTNOSITELXNO DRUGOJ SL. W. |TOT SPOSOB PRIWODIT K WYRAVENI@ KOLI^E- STWA INFORMACII ^ISLOM.
dLQ D.S.W. X I Y , ZADANNYH ZAKONAMI RASPREDELENIQ P (X = Xi) = pi, P (Y = Yj) = qj I SOWMESTNYM RASPREDELENIEM P (X = Xi; Y = Yj) = pij, KOLI^ESTWO INFORMACII, SODERVA]EJSQ W X OTNOSITELXNO Y , RAWNO
I(X; Y ) = |
pij log2 |
pij : |
|
|
X |
|
|
|
i;j |
piqj |
|
|
|
|
10
dLQ NEPRERYWNYH SL. W. X I Y , ZADANNYH PLOTNOSTQMI RASPREDELENIQ WEROQTNOSTEJ pX(t1), pY (t2) I pXY (t1; t2), ANALOGI^NAQ FORMULA IMEET WID
|
I(X; Y ) = Z Z2 pXY (t1; t2) log2 pX(t1)pY (t2)dt1dt2: |
|||||||
|
|
|
|
|
|
pXY (t1; t2) |
||
|
R |
|
|
|
|
|
|
|
|
o^EWIDNO, ^TO |
|
P (X = Xi); |
|
|
|||
|
|
|
PRI i = j |
|||||
|
P (X = Xi; X = Xj) = |
0; |
|
|
PRI i 6= j |
|||
I, SLEDOWATELXNO, |
|
|
|
|
|
|
|
|
|
I(X; X) = Xi |
pi log2 |
pi |
= Xi |
pi log2 pi: |
|||
|
pipi |
|||||||
|
|NTROPIQ D.S.W. X W TEORII INFORMACII OPREDELQETSQ FORMULOJ |
|||||||
|
H(X) = HX = I(X; X): |
|
|
|||||
|
sWOJSTWA MERY INFORMACII I \NTROPII: |
|
|
|||||
1) |
I(X; Y ) > 0, I(X; Y ) = 0 |
, |
|
X I Y NEZAWISIMY; |
||||
2) |
I(X; Y ) = I(Y; X); |
|
|
|
|
|
|
|
3) |
HX = 0 , X | KONSTANTA; |
|
|
|
|
4)I(X; Y ) = HX + HY H(X; Y ), GDE H(X; Y ) = Pi;j pij log2 pij;
5)I(X; Y ) 6 I(X; X). eSLI I(X; Y ) = I(X; X), TO X | FUNKCIQ OT Y .
1)lOGARIFMIROWANIEM IZ O^EWIDNOGO DLQ WSEH x NERAWENSTWA ex 1 > x (RAWENSTWO USTANAWLIWAETSQ TOLXKO PRI x = 1) POLU^AETSQ NERAWENSTWO x 1 >
ln x ILI xln 21 > log2 x.
|
|
|
|
|
|
|
|
|
piqj |
|||
|
|
X |
|
|
piqj |
|
X |
|
1 |
|||
|
|
|
|
6 |
pij |
|||||||
I(X; Y ) = |
pij log2 |
|
|
pij |
|
|
= |
|||||
pij |
ln 2 |
|||||||||||
|
|
i;j |
P |
P ln 2 |
|
i;j |
|
|
|
|
||
i;j |
ln 2 |
P |
|
ln 2 |
||||||||
= |
piqj pij = |
|
i pi |
j qj |
i;j pij |
= 1 1 = 0; |
||||||
X |
|
|
|
|
|
|
|
|
|
|
|
|
T.E. I(X; Y ) = 0 TOLXKO PRI pij |
= piqj DLQ WSEH i I j, T.E. PRI NEZAWISIMOSTI |
X I Y . eSLI X I Y NEZAWISIMY, TO pij = piqj I, SLEDOWATELXNO, ARGUMENTY LOGARIFMOW RAWNY 1 I, SLEDOWATELXNO, SAMI LOGARIFMY RAWNY 0, ^TO OZNA^AET,
^TO I(X; Y ) = 0;
2) sLEDUET IZ SIMMETRI^NOSTI FORMUL OTNOSITELXNO ARGUMENTOW;
11
3)eSLI HX = 0, TO WSE ^LENY SUMMY, OPREDELQ@]EJ HX, DOLVNY BYTX NULI, ^TO WOZMOVNO TOLXKO TOGDA I TOLXKO TOGDA, KOGDA X | KONSTANTA;
4)iZ ^ETYREH O^EWIDNYH SOOTNO[ENIJ
XX
pij = pi; |
pij = qj; |
ji
XX
HX = pi log2 pi = pij log2 pi;
ii;j
XX
HY = qj log2 qj = pij log2 qj
ji;j
POLU^AETSQ
HX + HY H(X; Y ) = |
X |
|
pij(log2 pij log2 qj log2 pi) = I(X; Y ); |
||
|
i;j |
|
5) nUVNO DOKAZATX I(X; Y ) = HX + HY H(X; Y ) 6 HX ILI |
||
HY H(X; Y ) 6 0. |
X |
X |
X |
||
HY H(X; Y ) = pij log2 qj + pij log2 pij = |
pij log2(pij=qj); |
|
i;j |
i;j |
i;j |
NO pij = P (X = Xi; Y = Yj) 6 qj = P (Y = Yj), A ZNA^IT ARGUMENTY U WSEH LOGARIFMOW NE BOLX[E 1 I, SLEDOWATELXNO, ZNA^ENIQ LOGARIFMOW NE BOLX[E 0, A \TO I ZNA^IT, ^TO WSQ SUMMA NE BOLX[E 0.
eSLI HX = I(X; X) = I(X; Y ), TO DLQ KAVDOGO i pij RAWNO LIBO qj,
LIBO 0. nO IZ pij = P (X = Xi; Y = Yj) = P (X = Xi=Y = Yj)P (Y = Yj) 2 fqj; 0g SLEDUET P (X = Xi=Y = Yj) 2 f0; 1g, ^TO WOZMOVNO TOLXKO W SLU^AE, KOGDA X | FUNKCIQ OT Y .
pRI NEZAWISIMOSTI SL. W. X I Y ODNA IZ NIH NI^EM NE OPISYWAET DRUGU@, ^TO I OTRAVAETSQ W TOM, ^TO DLQ TAKIH SL.W. I(X; Y ) = 0.
rASSMOTRIM PRIMER IZMERENIQ KOLI^ESTWA INFORMACII PRI PODBRASYWANII DWUH IGRALXNYH KOSTEJ.
pUSTX ZADANY D. S. W. X1, X2 I Y . X1 I X2 | KOLI^ESTWA O^KOW, WYPAW[IH SOOTWETSTWENNO NA 1-J I 2-J IGRALXNOJ KOSTI, A Y = X1 +X2. nAJTI I(Y; X1), I(X1; X1), I(Y; Y ).
zAKONY RASPREDELENIQ WEROQTNOSTEJ DLQ D.S.W. X1 I X2 SOWPADA@T, T.K. KOSTI ODINAKOWYE I BEZ IZ_QNOW.
X1 1 2 3 4 5 6
p1/6 , T.E. PRI j = 1:::6 qj = P (X1 = j) = 1=6.
12
zAKON RASPREDELENIQ WEROQTNOSTEJ DLQ D.S.W. Y ,
P (Y = i) = P (X1 + X2 = i); i = 2:::12;
WSLEDSTWIE TOGO, ^TO X1, X2 | NEZAWISIMY I PO\TOMU
P (X1 = n; X2 = m) = P (X1 = n)P (X2 = m);
BUDET
|
|
|
16X6 |
|
P (X1 = n)P (X2 = m) = |
6X6 |
1=36: |
|||||||||
pi = P (X1 + X2 = i) = |
|
|
|
|
|
|
||||||||||
|
|
|
n+m=i |
|
|
|
|
|
|
|
n+m=i |
|
||||
|
|
|
|
n;m |
6 |
|
|
|
|
|
1 |
|
n;m 6 |
|||
tABLICY, OPREDELQ@]IE Y : |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
X2 nX1 |
|
|
1 2 3 4 5 6 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
1 |
|
|
|
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
2 |
|
|
|
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
|
|
|
3 |
|
|
|
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
4 |
|
|
|
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
5 |
|
|
|
6 |
7 |
8 |
9 |
10 |
11 |
|
|
|
|
|
|
|
6 |
|
|
|
7 |
8 |
9 |
10 |
11 |
12; |
|
|
|
|
Y = X1 + X2 |
|
2 |
3 |
4 |
|
5 |
|
6 |
7 |
8 |
9 10 11 12 |
|||||
|
|
|
||||||||||||||
p |
|
1=36 |
2=36 |
3=36 |
|
4=36 |
5=36 |
6=36 |
5=36 |
4=36 3=36 |
2=36 1=36; |
|||||
T.E. PRI i = 2:::12, pi |
= P (Y = i) = (6 j7 ij)=36. |
|
zAKON SOWMESTNOGO RASPREDELENIQ WEROQTNOSTEJ D.S.W. X1 I Y BUDET
pij = P (Y = i; X1 = j) = P (Y = i=X1 = j)P (X1 = j);
NAPRIMER,
P (Y = 2; X1 = 1) = P (Y = 2=X1 = 1)P (X1 = 1) =
= P (X2 = 1)P (X1 = 1) = 1=36:
w OB]EM SLU^AE POLU^ITSQ |
= j) = |
|
INA^E.6 |
|
|
|
|
|
|
|||||||
|
pij = P (Y = i; X1 |
0; |
i |
j |
6 |
6, |
|
|||||||||
|
|
|
|
|
|
|
|
1=36; |
PRI 1 |
|
|
|
||||
|
X1 nY |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
|
12 |
|
|
|
|
||||||||||||||
|
1 |
|
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 0 |
0 |
0 |
|
|
0 |
|
0 |
|
2 |
|
0 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 0 |
0 |
|
|
0 |
|
0 |
||
3 |
|
0 |
0 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 0 |
|
|
0 |
|
0 |
||
4 |
|
0 |
0 |
0 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
|
0 |
|
0 |
||
5 |
|
0 |
0 |
0 |
0 |
1=36 |
1=36 |
1=36 |
1=36 |
1=36 |
|
1=36 |
0 |
|||
6 |
|
0 |
0 |
0 |
0 |
0 |
1=36 |
1=36 |
1=36 |
1=36 |
|
1=36 |
1=36 |
13
tOGDA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
pij log2 |
|
pij = |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I(Y; X1) = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X X |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j=1 16i j66 |
|
|
|
|
|
|
|
|
piqj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
6 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X X |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
|
|
|
log |
|
|
|
|
|
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36 |
j=1 16i j66 |
|
2 6pi |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
1 |
|
7 |
|
|
|
|
1 |
|
|
|
8 |
|
|
1 |
|
|
|
|
11 |
|
|
|
1 |
|
|
|
|
|
|
|
12 |
|
|
|
1 |
|
|
|
|
|||||||||||
|
|
|
|
|
Xi |
|
|
|
|
X |
|
|
|
|
X |
|
|
|
|
|
|
|
|
|
X |
|
|
|
|
|
|
|||||||||||||||||||||||
|
= |
|
|
|
( |
|
|
log2 |
|
+ |
|
|
log2 |
|
|
|
|
+ + |
|
|
|
|
log2 |
|
|
+ |
|
|
|
log2 |
|
|
) = |
|||||||||||||||||||||
|
36 |
=2 |
6pi |
|
|
6pi |
|
|
|
|
6pi |
|
6pi |
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i=3 |
|
|
|
|
|
|
|
i=6 |
|
|
|
|
|
|
|
|
|
|
|
|
i=7 |
|
|
|
|
|
|
|
||||||||||
|
1 |
|
|
|
|
6 |
|
|
|
|
|
6 |
|
|
|
|
6 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
6 |
|
|
|
|
|
6 |
|
||||||||||||||||
= |
|
|
((log2 |
|
|
+log2 |
|
+ |
+log2 |
|
)+ +(log2 |
|
+log2 |
|
|
|
+ +log2 |
|
)) = |
|||||||||||||||||||||||||||||||||||
36 |
1 |
2 |
6 |
6 |
5 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||
|
= |
|
1 |
(2 log |
|
6 + 4 log |
|
3 + 6 log |
|
|
|
2 + 8 log |
|
|
3 |
+ 10 log |
|
6 |
+ 6 log |
|
|
1) = |
||||||||||||||||||||||||||||||||
|
36 |
2 |
2 |
2 |
2 2 |
2 5 |
2 |
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= (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 BIT/SIMWOL:
2:58 BIT/SIM. |
12 |
|
|
|
|
6 |
|
|
2 |
|
2 |
|
|
|
|
|
|
2 |
|
|
|||||||
|
|
Pj=1 |
qj log |
qj = log |
6 = 1 + log |
3 |
|||||||||||||||||||||
|
|
I(X1; X1) = I(X2; X2) = |
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
I(Y; Y ) = Pi=2 pi log2 pi = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
= |
|
1 |
(2 log |
|
36 + 4 log |
|
18 + 6 log |
|
12 + 8 log |
|
|
9 + 10 log |
|
|
36 |
+ 6 log |
|
6) = |
|||||||||
|
|
|
|
|
|
|
|
|
5 |
|
|
||||||||||||||||
|
36 |
2 |
|
|
2 |
|
|
2 |
|
|
2 |
|
|
|
2 |
|
|
2 |
|
|
|
|
= (4+4 log2 3+4+8 log2 3+12+6 log2 3+16 log2 3+20+20 log2 3 10 log2 5+ + 6 + 6 log2 3)=36 = (46 + 60 log2 3 10 log2 5)=36 3:27 BIT/SIM:
zDESX 0 < I(Y; X1) = I(Y; X2) < I(X1; X1) = I(X2; X2) < I(Y; Y ),
^TO SOOTWETSTWUET SWOJSTWAM INFORMACII.
pOD^EKNUTYJ ^LEN 361 2 log2 6 = I(X1; X1)=18 W RAS^ETE I(X1; Y ) SOOTWETSTWUET INFORMACII O DWUH SLU^AQH IZ 36, KOGDA Y = 2 I Y = 12,
KOTORYE ODNOZNA^NO OPREDELQ@T X1. {ESTX SLU^AEW, KOGDA Y = 7, NE NESUT NIKAKOJ INFORMACII OB X1, ^TO SOOTWETSTWUET POD^ERKNUTOMU ^LENU 6 log2 1 = 0.
rAS^ETY MOVNO PROWODITX, ISPOLXZUQ 4-E SWOJSTWO INFORMACII, ^EREZ \NTROPI@.
H(Y; X1) = Pi;j pij log2 pij = log2 36 = 2(1 + log2 3) = 2HX1
5:17 BIT/SIM.
I(Y; X1) = HX1 + HY H(X1; Y ) = HY HX1 3:27 2:58 = 0:69
BIT/SIM.
14
rAS^ET KOLI^ESTWA INFORMACII S ISPOLXZOWANIEM 4-GO SWOJSTWA, A NE OPREDELENIQ, OBY^NO TREBUET MENX[E WY^ISLENIJ.
rASSMOTRIM BOLEE PROSTOJ PRIMER. pUSTX D.S.W. X RAWNA KOLI^E-
STWU O^KOW, WYPAW[IH NA IGRALXNOJ KOSTI, |
A D. S. W. Y RAWNA 0, ESLI |
|||||||||||||||||||||||||||||||
WYPAW[EE KOLI^ESTWO O^KOW NE^ETNO, I 1, ESLI WYPAW[EE KOLI^ESTWO |
||||||||||||||||||||||||||||||||
O^KOW ^ETNO. nAJTI I(X; Y ) I I(Y; Y ). |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
sOSTAWIM ZAKONY RASPREDELENIQ WEROQTNOSTEJ D.S.W. X I Y . |
||||||||||||||||||||||||||||||||
|
|
X |
|
1 |
2 3 4 5 |
|
6 |
|
|
|
|
|
|
|
Y |
|
0 1 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
p |
|
|
|
|
|
|
|
|
1=6 |
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
1=2 |
|||||
tAKIM OBRAZOM, PRI i = 1:::6 pi = P (X = i) = 1=6 I, SOOTWETSTWEN- |
||||||||||||||||||||||||||||||||
NO, PRI j = 0:::1 qj = P (Y |
= j) = 1=2. |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
sOSTAWIM TAKVE ZAKON SOWMESTNOGO RASPREDELENIQ WEROQTNOSTEJ |
||||||||||||||||||||||||||||||||
\TIH D.S.W. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 = Pp |
|
|
|
|
|
|
|
|
|
1=6; INA^E. |
|||||||||||||
tAKIM OBRAZOM |
|
|
|
|
|
|
|
(X = i; Y = j) = |
|
0; |
|
ESLI i + j | ^ETNO, |
||||||||||||||||||||
I(X; Y ) = |
|
|
|
|
|
|
p |
|
|
log |
|
|
|
ij |
= 61 log |
|
2 = 1 BIT/SIM. |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
I(Y; Y ) = |
P j=0 qj |
log2 qj |
= 221 log2 2 = 1 BIT/SIM. |
|||||||||||||||||||||||||||||
|
|
|
|
i;j |
|
ij |
|
|
2 |
|
piqj |
|
|
|
6 |
2 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tO^NOE |
KOLI^ESTWO WYPAW[IH O^KOW DAET TO^NU@ INFORMACI@ O |
|||||||||||||||||||||||||||||||
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
^ETNOSTI, T.E. 1 BIT. iZ I(X; Y ) = I(Y; Y ) = 1 BIT/SIM I 3-GO SWOJSTWA INFORMACII SLEDUET, ^TO INFORMACIQ OB X POLNOSTX@ OPREDELQET Y ,
NO NE NAOBOROT, T.K. I(X; Y ) 6= I(X; X) = 1+log2 3 2:58 BIT/SIM. dEJSTWITELXNO, Y FUNKCIONALXNO ZAWISIT OT X, A X OT Y FUNKCIONALXNO
NE ZAWISIT.
rAS^ETY ^EREZ \NTROPI@ BUDUT SLEDU@]IMI |
|
|
|
||||||||||
I(X; Y ) = |
|
|
P |
|
|
|
|
|
|
|
|
|
|
H(X; Y ) = |
i;j pij log2 pij = log2 6 = 1 + log2 |
3 = HX, |
|||||||||||
|
|
HX + HY |
|
HX = HY = 1 BIT/SIM. |
|
|
|||||||
I uPRAVNENIE 5 |
|
|
|
|
|
|
|
|
|
||||
nAJTI \NTROPI@ D.S.W. X, ZADANNOJ RASPREDELENIEM |
|
|
|||||||||||
|
|
1 |
2 |
|
3 |
4 |
5 |
6 |
7 |
8 |
|
||
|
X |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
p |
|
0.1 |
0.2 |
0.1 |
0.05 |
0.1 |
0.05 |
0.3 |
0.1. |
I uPRAVNENIE 6
zNA^ENIQ D. S. W. X1 I X2 OPREDELQ@TSQ PODBRASYWANIEM DWUH IDEALXNYH MONET, A D.S.W. Y RAWNA SUMME KOLI^ESTWA \GERBOW", WYPAW[IH PRI PODBRASYWANII \TIH MONET. sKOLXKO INFORMACII OB X1 SODERVITSQ W
Y ?
15
I uPRAVNENIE 7
sKOLXKO INFORMACII OB X1 SODERVITSQ W D.S.W. Z = (X1 + 1)2 X2, GDE NEZAWISIMYE D. S. W. X1 I X2 MOGUT S RAWNOJ WEROQTNOSTX@ PRINIMATX ZNA^ENIE LIBO 0, LIBO 1? nAJTI HX1 I HZ. kAKOW HARAKTER ZAWISIMOSTI MEVDU X1 I Z?
I uPRAVNENIE 8
d. S. W. X1, X2 | ZAWISIMY I RASPREDELENY TAKVE KAK I SOOTWETSTWU- @]IE D.S.W. IZ PREDYDU]EJ ZADA^I. nAJTI I(X1; X2), ESLI SOWMESTNOE RASPREDELENIE WEROQTNOSTEJ X1 I X2 OPISYWAETSQ ZAKONOM
X1 |
0 |
0 |
1 |
1 |
|
X2 |
0 |
1 |
0 |
1 |
|
p |
1/3 |
1/6 |
1/6 |
1/3. |
|
I uPRAVNENIE 9
d. S. W. X1 I X2 OPREDELQ@TSQ PODBRASYWANIEM DWUH IDEALXNYH TETRA\DROW, GRANI KOTORYH POME^ENY ^ISLAMI OT 1 DO 4. d. S. W. Y RAWNA SUMME ^ISEL, WYPAW[IH PRI PODBRASYWANII \TIH TETRA\DROW, T. E.
Y = X1 + X2. wY^ISLITX I(X1; Y ), HX1 I HY .
I uPRAVNENIE 10
pODS^ITATX SKOLXKO INFORMACII OB X1 SODERVITSQ W D.S.W. Z = X1 X2, A TAKVE HZ. d.S.W. X1 I X2 BERUTSQ IZ PREDYDU]EGO UPRAVNENIQ.
I uPRAVNENIE 11
d.S.W. X1 MOVET PRINIMATX TRI ZNA^ENIQ 1, 0 I 1 S RAWNYMI WEROQTNOSTQMI. d.S.W. X2 S RAWNYMI WEROQTNOSTQMI MOVET PRINIMATX ZNA^ENIQ 0, 1 I 2. X1 I X2 | NEZAWISIMY. Y = X12 +X2. nAJTI I(X1; Y ), I(X2; Y ),
HX1, HX2, HY .
I uPRAVNENIE 12
nAJTI \NTROPII D. S. W. X, Y , Z I KOLI^ESTWO INFORMACII, SODERVA- ]EJSQ W Z = X + Y OTNOSITELXNO Y . X I Y | NEZAWISIMY I ZADA@TSQ RASPREDELENIQMI
X |
0 |
1 |
3 |
4 |
|
Y |
2 |
2 |
|
p |
1/8 |
1/8 |
1/4 |
1/2 |
|
p |
3/8 |
5/8. |
|
8. sMYSL \NTROPII {ENNONA
|NTROPIQ D.S.W. | \TO MINIMUM SREDNEGO KOLI^ESTWA BIT, KOTOROE NUVNO PEREDAWATX PO KANALU SWQZI O TEKU]EM ZNA^ENII DANNOJ D.S.W.
16
rASSMOTRIM PRIMER (SKA^KI). w ZAEZDE U^ASTWU@T 4 LO[ADI S RAWNYMI [ANSAMI NA POBEDU, T.E. WEROQTNOSTX POBEDY KAVDOJ LO[ADI RAWNA 1/4. wWEDEM D. S. W. X, RAWNU@ NOMERU POBEDIW[EJ LO[ADI. zDESX HX = 2. pOSLE KAVDOGO ZAEZDA PO KANALAM SWQZI DOSTATO^NO BUDET PEREDAWATX DWA BITA INFORMACII O NOMERE POBEDIW[EJ LO[ADI. kODIRUEM NOMER LO[ADI SLEDU@]IM OBRAZOM: 1|00, 2|01, 3|10, 4|11. eSLI WWESTI FUNKCI@ L(X), KOTORAQ WOZWRA]AET DLINU SOOB]ENIQ, KODIRU@]EGO ZADANNOE ZNA^ENIE X, TO M.O. ML(X) | \TO SREDNQQ DLINA SOOB]ENIQ, KODIRU@]EGO X. mOVNO FORMALXNO OPREDELITX L ^EREZ DWE FUNKCII L(X) = len(code(X)), GDE code(X) KAVDOMU ZNA^ENI@ X STAWIT W SOOTWETSTWIE NEKOTORYJ BITOWYJ KOD, PRI^EM, WZAIMNO ODNOZNA^- NO, A len WOZWRA]AET DLINU W BITAH DLQ L@BOGO KONKRETNOGO KODA. L | \TO FUNKCIQ OT D.S.W., T.E. TOVE D.S.W. w \TOM PRIMERE ML(X) = HX.
pUSTX TEPERX D.S.W. X IMEET SLEDU@]EE RASPREDELENIE
P (X = 1) = 34; P (X = 2) = 18; P (X = 3) = P (X = 4) = 161 ;
T.E. LO[ADX S NOMEROM 1 | \TO FAWORIT. tOGDA
|
3 |
4 |
|
1 |
|
1 |
|
19 |
|
3 |
|
|
|
||||||
HX = |
|
log2 |
|
+ |
|
log2 |
8 + |
|
log2 |
16 = |
|
|
|
|
|
|
log2 |
3 |
1:186 BIT/SIM: |
4 |
3 |
8 |
8 |
8 |
4 |
zAKODIRUEM NOMERA LO[ADEJ: 1|0, 2|10, 3|110, 4|111, | T. E. TAK, ^TOBY KAVDOJ KOD NE BYL PREFIKSOM DRUGOGO KODA (PODOBNOE KODIROWANIE NAZYWA@T PREFIKSNYM). w SREDNEM W 16 ZAEZDAH 1-Q LO[ADX DOLVNA POBEDITX W 12 IZ NIH, 2-Q | W 2-H, 3-Q | W 1-M I 4-Q | W 1-M. tAKIM OBRAZOM, SREDNQQ DLINA SOOB]ENIQ O POBEDITELE RAWNA
(1 12 + 2 2 + 3 1 + 3 1)=16 = 1:375 BIT/SIM ILI M. O. L(X). dEJ-
STWITELXNO, L(X) SEJ^AS ZADAETSQ SLEDU@]IM RASPREDELENIEM WEROQT-
NOSTEJ: P (L(X) = 1) = 3=4, P (L(X) = 2) = 1=8, P (L(X) = 3) = 1=8. sLEDOWATELXNO,
ML(X) = 34 + 28 + 38 = 118 = 1:375 BIT/SIM:
iTAK, ML(X) > HX.
mOVNO DOKAZATX, ^TO BOLEE \FFEKTIWNOGO KODIROWANIQ DLQ DWUH RASSMOTRENNYH SLU^AEW NE SU]ESTWUET.
tO, ^TO \NTROPIQ {ENNONA SOOTWETSTWUET INTUITIWNOMU PREDSTAWLENI@ O MERE INFORMACII, MOVET BYTX PRODEMONSTRIROWANO W OPYTE PO OPREDELENI@ SREDNEGO WREMENI PSIHI^ESKIH REAKCIJ. oPYT ZAKL@- ^AETSQ W TOM, ^TO PERED ISPYTUEMYM ^ELOWEKOM ZAVIGAETSQ ODNA IZ
17
NLAMPO^EK, KOTORU@ ON DOLVEN UKAZATX. pROWODITSQ BOLX[AQ SERIQ
ISPYTANIJ, W KOTORYH KAVDAQ LAMPO^KA ZAVIGAETSQ S OPREDELENNOJ WEROQTNOSTX@ pi (PNi pi = 1), GDE i | \TO NOMER LAMPO^KI. oKAZYWAETSQ, SREDNEE WREMQ, NEOBHODIMOE DLQ PRAWILXNOGO OTWETA ISPYTUEMOGO, PROPORCIONALXNO WELI^INE \NTROPII PNi=1 pi log2 pi, A NE ^ISLU LAMPO^EK
N, KAK MOVNO BYLO BY PODUMATX. w \TOM OPYTE PREDPOLAGAETSQ, ^TO ^EM BOLX[E INFORMACII BUDET POLU^ENO ^ELOWEKOM, TEM DOLX[E BUDET WREMQ EE OBRABOTKI I, SOOTWETSTWENNO, REAKCII NA NEE.
I uPRAVNENIE 13
nAJTI \NTROPI@ D. S. W. X I SREDN@@ DLINU KAVDOGO IZ PRIWEDENNYH KODOW DLQ \TOJ D.S.W.
X |
1 |
3 |
4 |
5 |
6 |
p |
0.4 |
0.2 |
0.1 |
0.2 |
0.1 |
code1(X) |
000 |
001 |
010 |
011 |
111 |
code2(X) |
0 |
100 |
101 |
110 |
111 |
code3(X) |
00 |
01 |
110 |
10 |
111 |
code4(X) |
0 |
10 |
1110 |
110 |
1111. |
I uPRAVNENIE 14
d.S.W. X RAWNA KOLI^ESTWU \GERBOW", WYPAW[IH NA DWUH IDEALXNYH MONETKAH. nAJTI \NTROPI@ X. pRIDUMATX MINIMALXNYJ KOD DLQ X, WY- ^ISLITX EGO SREDN@@ DLINU I OBOSNOWATX EGO MINIMALXNOSTX.
I uPRAVNENIE 15
d.S.W. X ZADANA RASPREDELENIEM P (X = 2n) = 1=2n, n = 1; 2; : : : nAJTI \NTROPI@ \TOJ D.S.W. pRIDUMATX MINIMALXNYJ KOD DLQ X, WY^ISLITX EGO SREDN@@ DLINU I OBOSNOWATX EGO MINIMALXNOSTX.
I uPRAVNENIE 16
pRO D.S.W. X IZWESTNO, ^TO EE ZNA^ENIQMI QWLQ@TSQ BUKWY KIRILLICY. pROIZWEDEN RQD POSLEDOWATELXNYH IZMERENIJ X, REZULXTAT KOTORYH | \teoriqinformacii". sOSTAWITX NA OSNOWANII \TOGO REZULXTATA PRIBLIZITELXNYJ ZAKON RASPREDELENIQ WEROQTNOSTEJ \TOJ D. S. W. I OCENITX MINIMALXNU@ SREDN@@ DLINU KODOW DLQ X.
9. sEMANTI^ESKAQ INFORMACIQ
w 50-H GODAH XX WEKA POQWILISX PERWYE POPYTKI OPREDELENIQ ABSOL@TNOGO INFORMACIONNOGO SODERVANIQ PREDLOVENIJ ESTESTWENNOGO QZYKA. sTOIT OTMETITX, ^TO SAM {ENNON ODNAVDY ZAMETIL, ^TO SMYSL
18