4. Обратная теорема Шеннона для дискретного канала связи (1107643), страница 2
Текст из файла (страница 2)
ðÕÓÔØ ÓÕÝÅÓÔ×ÕÅÔ ÍÅÔÏÄ ÐÅÒÅÄÁÞÉ ÐÏ äëâð Ó ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ C1 É Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ ≤ = N . ôÏÇÄÁ ÎÅÏÂÈÏÄÉÍÏ ×ÙÐÏÌÎÅÎÉÅ ÎÅÒÁ×ÅÎÓÔ×ÁC + ln 2=N: = N ≥ 1 − 1RéÚ ÔÅÏÒÅÍÙ 4 ×ÙÔÅËÁÅÔ ×ÁÖÎÏÅóÌÅÄÓÔ×ÉÅ. (ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ) åÓÌÉ ÓËÏÒÏÓÔØ ÐÅÒÅÄÁÞÉ ÂÏÌØÛÅ ÐÒÏÐÕÓËÎÏÊÓÐÏÓÏÂÎÏÓÔÉ äëâð, Ô.Å. ÅÓÌÉ R > C1 , ÔÏ ÐÒÉ N → ∞ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÌÀÂÏÇÏÍÅÔÏÄÁ ÐÅÒÅÄÁÞÉ N 6→ 0.äÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 4. éÚ ÔÅÏÒÅÍ 1 − 3 ÓÌÅÄÕÅÔ, ÞÔÏ ÐÁÒÁÍÅÔÒÙ ÍÅÔÏÄÁ ÐÅÒÅÄÁÞÉ (M; ; C1 ; N ) ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÎÅÒÁ×ÅÎÓÔ×Õ (1 − ) ln M − ln 2 ≤ NC1 , ËÏÔÏÒÏÅ × ÓÉÌÕÏÐÒÅÄÅÌÅÎÉÑ ÓËÏÒÏÓÔÉ R ÏÚÎÁÞÁÅÔ(1 − )RN − ln 2 ≤ NC1 ;ÞÔÏ ÒÁ×ÎÏÓÉÌØÎÏ ÎÅÒÁ×ÅÎÓÔ×Õ × ÔÅÏÒÅÍÅ 4.54.2 ó×ÏÊÓÔ×Á ÉÎÆÏÒÍÁÃÉÉ É ÜÎÔÒÏÐÉÉ4.2.1 õÓÌÏ×ÎÁÑ ÜÎÔÒÏÐÉÑ É ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑ÷×ÅÄÅÍ ÓÌÅÄÕÀÝÉÅ ÐÏÎÑÔÉÑ:H (X ) , −Pp(x) ln p(x) − ÜÎÔÒÏÐÉÑ;x PH (X ; Y ) , −H (Y |X ) , −xyPxyp(x; y) ln p(x; y) − ÓÏ×ÍÅÓÔÎÁÑ ÜÎÔÒÏÐÉÑ;p(x; y) ln p(y|x) − ÕÓÌÏ×ÎÁÑ ÜÎÔÒÏÐÉÑ:ó ÐÏÍÏÝØÀ ÜÔÉÈ ×ÅÌÉÞÉÎ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ÏÐÒÅÄÅÌÅÎÉÅ ÉÎÆÏÒÍÁÃÉÉ × ×ÉÄÅ:J (X ; Y ) = H (Y ) − H (Y |X ) = H (X ) − H (X |Y ) == H (X ) + H (Y ) − H (X ; Y ) =PP)= p(x; y) ln pp(y(y|x)) = p(x; y) ln pp(x(x;y)p(y) ;xy(1)xyÁ ÔÁËÖÅ ÏÐÒÅÄÅÌÅÎÉÅ ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉ × ×ÉÄÅ:J (X ; Y |Z ) = H (Y |Z ) − H (Y |X; Z ) =P)= H (X |Z ) − H (X |Y; Z ) = p(x; y; z ) ln pp(x(x|y;z|z ) ==Pxyzxyz|z )p(x; y; z ) ln p(xp(|zx;y:)p(y|z )(2)ðÕÓÔØ |X | ÏÂÏÚÎÁÞÁÅÔ ÞÉÓÌÏ ×ÏÚÍÏÖÎÙÈ ÚÎÁÞÅÎÉÊ ×ÅÌÉÞÉÎÙ X .
ïÞÅ×ÉÄÎÏ, ÞÔÏ ÅÓÌÉ XÉÍÅÅÔ ÒÁ×ÎÏÍÅÒÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ, Ô.Å. ÄÌÑ ÌÀÂÏÇÏ ×ÏÚÍÏÖÎÏÇÏ ÚÎÁÞÅÎÉÑ x ×ÅÒÏÑÔÎÏÓÔØPr{X = x} = 1=|X |, ÔÏ ÜÎÔÒÏÐÉÑ H (X ) = ln |X |. éÍÅÅÔ ÍÅÓÔÏó×ÏÊÓÔ×Ï 1. (üËÓÔÒÅÍÁÌØÎÏÓÔØ ÒÁ×ÎÏÍÅÒÎÏÇÏ ÒÁÓÐÒÅÄÅÌÅÎÉÑ). H (X ) ≤ ln |X |, ÇÄÅ ÚÎÁËÒÁ×ÅÎÓÔ×Á ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ X ÉÍÅÅÔ ÒÁ×ÎÏÍÅÒÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ.äÏËÁÚÁÔÅÌØÓÔ×Ï Ó×ÏÊÓÔ×Á 1.
äÁÎÎÏÅ Ó×ÏÊÓÔ×Ï ×ÙÔÅËÁÅÔ ÉÚ ÎÅÒÁ×ÅÎÓÔ×Á (*) (ÓÍ.×Ù×ÏÄ Ó×ÏÊÓÔ×Á 0), × ËÏÔÏÒÏÍ ÎÁÄÏ ÐÏÌÏÖÉÔØ: ! = x ; Q1 (!) = p(x) ; Q2 (w) = 1=|X | :ïÞÅ×ÉÄÎÏ (ÌÅÇËÏ ÐÒÏ×ÅÒÑÅÔÓÑ) ÓÌÅÄÕÀÝÅÅ ×ÁÖÎÏÅó×ÏÊÓÔ×Ï 2. éÍÅÅÔ ÍÅÓÔÏ ÆÏÒÍÕÌÁ ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉJ (X ; Y1 ; Y2 ) = J (X ; Y1 ) + J (X ; Y2 |Y1 ) ;(3)Á ÔÁËÖÅ ÏÂÏÂÝÅÎÎÁÑ ÆÏÒÍÕÌÁ ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉJ (X ; Y1 ; Y2 |Z ) = J (X ; Y1 |Z ) + J (X ; Y2 |Y1 ; Z ) :(4)éÚ Ó×ÏÊÓÔ×Á 2 ×ÙÔÅËÁÅÔó×ÏÊÓÔ×Ï 3. (ãÅÐÎÏÅ ÐÒÁ×ÉÌÏ).J (X ; Y1N ) =NXn=1J (X ; Yn |Y1n−1 ) :6(5)4.2.2 éÎÆÏÒÍÁÃÉÏÎÎÙÅ ÎÅÒÁ×ÅÎÓÔ×ÁðÕÓÔØ y~ = f (y) | ÐÒÏÉÚ×ÏÌØÎÁÑ ÆÕÎËÃÉÑ. ôÏÇÄÁ Y~ = f (Y ) | ÓÌÕÞÁÊÎÁÑ ×ÅÌÉÞÉÎÁ ÉÓÐÒÁ×ÅÄÌÉ×Ïó×ÏÊÓÔ×Ï 4.
(íÏÎÏÔÏÎÎÏÓÔØ ÉÎÆÏÒÍÁÃÉÉ).J (X ; f (Y )) ≤ J (X ; Y ) ;(6)ÇÄÅ ÒÁ×ÅÎÓÔ×Ï ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ (Y ; f (Y ); X ) | ÃÅÐØ íÁÒËÏ×Á.äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÏÓËÏÌØËÕ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÐÁÒÙ (Y ; f (Y )) ÏÄÎÏÚÎÁÞÎÏ ÚÁÄÁÅÔÓÑ ÒÁÓÐÒÅÄÅÌÅÎÉÅÍ Y , ÔÏ J (X ; Y ) = J (X ; Y; f (Y )), Á ÓÌÅÄÏ×ÁÔÅÌØÎÏ ÉÚ (3) ÉÍÅÅÍJ (X ; Y ) = J (X ; f (Y )) + J (X ; Y |f (Y )) ≥ J (X ; f (Y )) :üÔÏ ÎÅÒÁ×ÅÎÓÔ×Ï ÏÂÏÂÝÁÅÔÓÑ É ÎÁ ÕÓÌÏ×ÎÕÀ ÉÎÆÏÒÍÁÃÉÀ, Ô.Å.
ÉÚ (4) ×ÙÔÅËÁÅÔó×ÏÊÓÔ×Ï 5. (íÏÎÏÔÏÎÎÏÓÔØ ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉ).J (X ; f (Y )|Z ) ≤ J (X ; Y |Z ) ;(7)ÇÄÅ ÒÁ×ÅÎÓÔ×Ï ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÔÒÏÊËÁ (X ; (Z; f (Y )); Y ) | ÃÅÐØ íÁÒËÏ×Á.äÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 1. ðÒÉÍÅÎÑÑ Ó×ÏÊÓÔ×Ï 4, ÍÏÖÅÍ ÎÁÐÉÓÁÔØ~ Y1N ) = J (; X1N ; Y1N );J ( ; ~) ≤ J (; X1N ; ;ÇÄÅ ×ÔÏÒÏÅ ÒÁ×ÅÎÓÔ×Ï ×ÙÔÅËÁÅÔ ÉÚ ÔÏÇÏ, ÞÔÏ ~ = g(Y1N ). äÁÌÅÅ, ÐÏ Ó×ÏÊÓÔ×Õ 2 ÉÍÅÅÍJ (Y1N ; ; X1N ) = J (X1N ; Y1N ) + J ( ; Y1N |X1N ):óÏÇÌÁÓÎÏ ÔÒÅÂÏ×ÁÎÉÀ õ3), ÔÒÏÊËÁ (; X1N ; Y1N ) | ÃÅÐØ íÁÒËÏ×Á.
óÌÅÄÏ×ÁÔÅÌØÎÏ, ÐÏ Ó×ÏÊÓÔ×Õ 0 ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑ J ( ; Y1N |X1N ) = 0. ðÏÜÔÏÍÕ ÄÌÑ ÌÀÂÏÇÏ ÓÏ×ÍÅÓÔÎÏÇÏ ÒÁÓÐÒÅÄÅÌÅÎÉÑ p(u; xN1 ; y1N ; u~), ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÇÏ ÕÓÌÏ×ÉÑÍ õ1)|õ3), ÓÐÒÁ×ÅÄÌÉ×Ï ÎÅÒÁ×ÅÎÓÔ×ÏÐÅÒÅÒÁÂÏÔËÉ ÄÁÎÎÙÈJ ( ; ~) ≤ J (X1N ; Y1N ) ;ÉÚ ËÏÔÏÒÏÇÏ ÏÞÅ×ÉÄÎÙÍ ÏÂÒÁÚÏÍ ÓÌÅÄÕÅÔ ÎÅÒÁ×ÅÎÓÔ×Ï ÍÅÖÄÕ -ÜÎÔÒÏÐÉÅÊ É ÐÒÏÐÕÓËÎÏÊÓÐÏÓÏÂÎÏÓÔØÀ, ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÏÅ × ÔÅÏÒÅÍÅ 1.éÚ ÎÅÏÔÒÉÃÁÔÅÌØÎÏÓÔÉ ÉÎÆÏÒÍÁÃÉÉ É ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉ ×ÙÔÅËÁÅÔó×ÏÊÓÔ×Ï 6.
(íÏÎÏÔÏÎÎÏÓÔØ ÜÎÔÒÏÐÉÉ).H (Y |X ) ≤ H (Y ) ; H (Y |XZ ) ≤ H (Y |X ) ;(8)ÇÄÅ ÒÁ×ÅÎÓÔ×Ï ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ p(y|x) = p(y) ÌÉÂÏ p(y|xz ) = p(y|x), ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ.õÓÌÏ×ÉÑ ÄÌÑ ÓÒÁ×ÎÅÎÉÑ ÉÎÆÏÒÍÁÃÉÉ É ÕÓÌÏ×ÎÏÊ ÉÎÆÏÒÍÁÃÉÉ ÄÁÀÔ Ó×ÏÊÓÔ×Á 7 É 8.ó×ÏÊÓÔ×Ï 7.
åÓÌÉ ÔÒÏÊËÁ (Z; X; Y ) | ÃÅÐØ íÁÒËÏ×Á, Ô.Å. p(y|xz ) = p(y|x), ÔÏJ (X ; Y |Z ) ≤ J (X ; Y ) :7(9)äÏËÁÚÁÔÅÌØÓÔ×Ï Ó×ÏÊÓÔ×Á 7. éÍÅÅÍJ (X ; Y |Z ) = H (Y |Z ) − H (Y |XZ ) ≤ H (Y ) − H (Y |X ) = J (X ; Y ) ;ÇÄÅ ÐÒÉÍÅÎÉÌÉ ÏÐÒÅÄÅÌÅÎÉÅ (2), Ó×ÏÊÓÔ×Ï 6, Á ÚÁÔÅÍ ÏÐÒÅÄÅÌÅÎÉÅ (1).ó×ÏÊÓÔ×Ï 8. åÓÌÉ × ÔÒÏÊËÅ (Z; X; Y ) ×ÅÌÉÞÉÎÙ (X; Z ) | ÎÅÚÁ×ÉÓÉÍÙ, ÔÏJ (X ; Y |Z ) ≥ J (X ; Y ) :(10)äÏËÁÚÁÔÅÌØÓÔ×Ï Ó×ÏÊÓÔ×Á 8. éÍÅÅÍJ (X ; Y |Z ) = H (X |Z ) − H (X |Y Z ) ≥ H (X ) − H (X |Y ) = J (X ; Y ) ;ÇÄÅ ÐÒÉÍÅÎÉÌÉ Ó×ÏÊÓÔ×Ï 6 É ÒÁ×ÅÎÓÔ×Ï H (X |Z ) = H (X ), ÒÁ×ÎÏÓÉÌØÎÏÅ ÎÅÚÁ×ÉÓÉÍÏÓÔÉ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ X É Z .éÚ ÎÅÏÔÒÉÃÁÔÅÌØÎÏÓÔÉ ÉÎÆÏÒÍÁÃÉÉ É ÏÐÒÅÄÅÌÅÎÉÑ ÉÎÆÏÒÍÁÃÉÉ × ×ÉÄÅ (1) ×ÙÔÅËÁÅÔ,ÞÔÏ H (X ; Y ) ≤ H (X ) + H (Y ), Ô.Å. ÓÐÒÁ×ÅÄÌÉ×Ïó×ÏÊÓÔ×Ï 9.
(óÕÂÁÄÄÉÔÉ×ÎÏÓÔØ ÜÎÔÒÏÐÉÉ). óÏ×ÍÅÓÔÎÁÑ ÜÎÔÒÏÐÉÑH (Y1N ) ≤NXn=1H (Yn ) ;ÇÄÅ ÚÎÁË ÒÁ×ÅÎÓÔ×Á ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ Yn ; n = 1; N , ÎÅÚÁ×ÉÓÉÍÙ.ó×ÏÊÓÔ×Ï 10. åÓÌÉ X1N É Y1N | ×ÈÏÄÎÏÊ É ×ÙÈÏÄÎÏÊ ÓÉÇÎÁÌÙ äëâð, ÔÏ ÕÓÌÏ×ÎÁÑÜÎÔÒÏÐÉÑH (Y1N |X1N ) =NXn=1H (Yn |Xn )äÏËÁÚÁÔÅÌØÓÔ×Ï Ó×ÏÊÓÔ×Á 10. ïÐÒÅÄÅÌÅÎÉÅ ÕÓÌÏ×ÎÏÇÏ ÒÁÓÐÒÅÄÅÌÅÎÉÑ p(y1N |xN1 ) ÄÌÑäëâð ÉÚ ÕÓÌÏ×ÉÑ õ2) ÏÚÎÁÞÁÅÔ, ÞÔÏH (Y1N |X1N )=−=−=−PNxN1 y1Np(xN1 ; y1 )PPxn ynNPNxN1 \xn y1 \ynPn=1 xn ynln·NQn=1¸p(yn |xn ) =Np(xN1 ; y1 )NPn=1ln p(yn |xn ) =p(xn ; yn ) ln p(yn |xn ) =NPn=1H (yn |xn ) :ó×ÏÊÓÔ×Ï 10 ÄÏËÁÚÁÎÏ.äÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 2.
éÓÐÏÌØÚÕÑ ÐÒÅÄÓÔÁ×ÌÅÎÉÅ (1) ÉÎÆÏÒÍÁÃÉÉ ÞÅÒÅÚ ÜÎÔÒÏ-ÐÉÀ, ÉÍÅÅÍJ (X1N ; Y1N ) = H (YN ) − H (YN |XN ) :ðÏÜÔÏÍÕ ÉÚ Ó×ÏÊÓÔ× 9 É 10 ×ÙÔÅËÁÅÔ, ÞÔÏ ÄÌÑ äëâðJ (X1N ; Y1N ) ≤NXn=1[H (Yn ) − H (Yn |Xn )] =8NXn=1J (Xn ; Yn );ÇÄÅ ÚÎÁË ÒÁ×ÅÎÓÔ×Á ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ×ÅÌÉÞÉÎÙ Yn , n = 1; N { ÎÅÚÁ×ÉÓÉÍÙ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÏÐÒÅÄÅÌÅÎÉÅ ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔÉ äëâð ÎÁ N ÅÄÉÎÉà ×ÒÅÍÅÎÉ ÏÚÎÁÞÁÅÔ,ÞÔÏCN = CN (PN ) ≤ N C1 ;(11)ÇÄÅ C1 | ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ ÎÁ ÅÄÉÎÉÃÕ ×ÒÅÍÅÎÉ, Ô.Å.C1 = C1 (P) = max J (X ; Y ) :(12)p(x)úÎÁË ÒÁ×ÅÎÓÔ×Á × (11) ×ÙÔÅËÁÅÔ ÉÚ ÔÏÇÏ, ÞÔÏ × ËÁÞÅÓÔ×Å ÜËÓÔÒÅÍÁÌØÎÏÇÏ ÒÁÓÐÒÅÄÅÌÅÎÉÑp^(xN1 ), ÎÁ ËÏÔÏÒÏÍ ÄÏÓÔÉÇÁÅÔÓÑ ÍÁËÓÉÍÕÍ × ÏÐÒÅÄÅÌÅÎÉÉ 4 ×ÅÌÉÞÉÎÙ CN , ÍÏÖÎÏ ×ÚÑÔØp^(xN1),NYn=1p^(xn ) ;ÇÄÅ p^(x), x = 0; K − 1, | ÒÁÓÐÒÅÄÅÌÅÎÉÅ, ÎÁ ËÏÔÏÒÏÍ ÄÏÓÔÉÇÁÅÔÓÑ ÍÁËÓÉÍÕÍ × (12).ôÅÏÒÅÍÁ 2 ÄÏËÁÚÁÎÁ.úÁÄÁÞÁ 1.
òÁÓÓÍÏÔÒÉÍ äóë ÂÅÚ ÐÁÍÑÔÉ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ p, 0 < p < 1=2; .äÏËÁÚÁÔØ, ÞÔÏ ÅÇÏ ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ C1 ÄÏÓÔÉÇÁÅÔÓÑ ÐÒÉ p^(0) = p^(1) = 1=2 É ÚÎÁÞÅÎÉÅC1 = ln 2 − h(p) ;ÇÄÅ Ä×ÏÉÞÎÁÑ ÜÎÔÒÏÐÉÑ h(p) , −p ln p − (1 − p) ln(1 − p).ó×ÏÊÓÔ×Ï 11. (îÅÒÁ×ÅÎÓÔ×Ï æÁÎÏ). äÌÑ ÐÒÏÉÚ×ÏÌØÎÏÊ ÐÁÒÙ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ (; ~), ∈ [M ], ~ ∈ [M~ ], M~ ≥ M , ÔÁËÏÊ ÞÔÏ Pr{ 6= ~} = , ÕÓÌÏ×ÎÁÑ ÜÎÔÒÏÐÉÑH ( |~) ≤ ln M + h() :äÏËÁÚÁÔÅÌØÓÔ×Ï Ó×ÏÊÓÔ×Á 11. ðÕÓÔØ p(u; u~) | ÓÏ×ÍÅÓÔÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÐÁÒÙ (; ~),Ô.Å.p(u; u~) = Pr{ = u; ~ = u~} ; u ∈ [M ] ; u~ ∈ [M~ ]:ôÏÇÄÁ ÉÚ ÏÐÒÅÄÅÌÅÎÉÑ ÞÉÓÌÁ ÓÌÅÄÕÅÔ, ÞÔÏ=M~ XXu~=1 u6=u~p(u; u~);1−=MXu=1p(u; u);Á ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ ÕÓÌÏ×ÎÏÊ ÜÎÔÒÏÐÉÉ ÉÍÅÅÍH ( |~) =M~ XXu~=1µ¶µ¶MX11p(u; u~) ln+ p(u; u) ln:p(u|u~)p(u|u)u=1u6=u~éÚ ÜÔÉÈ ÓÏÏÔÎÏÛÅÎÉÊ ×ÙÔÅËÁÅÔ, ÞÔÏ ÒÁÚÎÏÓÔØ = H ( |~) − h() − ln M = 1 + 2 , ÇÄÅ1 =M~Xu~=1·¸·¸MX1−p(u; u~) lnp(u; u) ln; 2 =:p(u|u~)Mp(u|u)u=1u6=u~X9éÓÐÏÌØÚÕÑ ÄÌÑ ÏÃÅÎËÉ ÎÅÒÁ×ÅÎÓÔ×Ï ln x ≤ (x − 1), ÉÍÅÅÍ1≤2≤P Pu~ u6=u~Pup(u; u~)p(u; u)hhiMp(u|u~) − 1i1− − 1p(u|u)=Pu=P Pu~ u6=u~p(~u) M − ≤ Pu~p(~u) − = 0 ;p(u)(1 − ) − (1 − ) = 0 :óÌÅÄÏ×ÁÔÅÌØÎÏ, ≤ 0, ÞÔÏ ÒÁ×ÎÏÓÉÌØÎÏ ÄÏËÁÚÙ×ÁÅÍÏÍÕ ÎÅÒÁ×ÅÎÓÔ×Õ.ó×ÏÊÓÔ×Ï 11 ÄÏËÁÚÁÎÏ.äÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 3.
ðÕÓÔØ Pr{ 6= ~} = . ðÏÓËÏÌØËÕ p(u) = 1=M; u ∈ [M ],ÔÏ H ( ) = ln M . óÌÅÄÏ×ÁÔÅÌØÎÏ, ÉÎÆÏÒÍÁÃÉÑJ ( ; ~) = H ( ) − H ( |~) = ln M − H ( |~) :ðÏÜÔÏÍÕ ÉÚ ÎÅÒÁ×ÅÎÓÔ×Á æÁÎÏ ÓÌÅÄÕÅÔ, ÞÔÏJ ( ; ~) ≥ ln M − h() − ln M ≥ (1 − ) ln M − log 2 ;ÇÄÅ ÍÙ ÕÞÌÉ, ÞÔÏ Ä×ÏÉÞÎÁÑ ÜÎÔÒÏÐÉÑ h() = − ln − (1 − ) ln(1 − ) ≤ ln 2. ôÁË, ËÁË ÆÕÎËÃÉÑ(1 − ) ÕÂÙ×ÁÅÔ Ó ÒÏÓÔÏÍ , ÔÏ ÎÅÒÁ×ÅÎÓÔ×ÏJ ( ; ~) ≥ (1 − ) ln M − ln 2 ;×ÅÒÎÏ É ÄÌÑ ÌÀÂÏÊ ÐÁÒÙ (; ~), ÔÁËÏÊ, ÞÔÏ Pr( 6= ~) ≤ .
ïÔÓÀÄÁ, ÐÒÉÍÅÎÑÑ ÏÐÒÅÄÅÌÅÎÉÅ-ÜÎÔÒÏÐÉÉ, ÉÍÅÅÍH () = inf J ( ; ~) ≥ (1 − ) ln M − ln 2;õ1ÅÓÌÉ ÓÏÏÂÝÅÎÉÅ ÉÍÅÅÔ ÒÁ×ÎÏÍÅÒÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ p(u) = 1=M , u = 1; M .ôÅÏÒÅÍÁ 3 ÄÏËÁÚÁÎÁ.4.3 ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ Ä×ÏÉÞÎÏÇÏ ËÁÎÁÌÁÓ ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ (ëòû)äÌÑ Ä×ÏÉÞÎÏÇÏ ËÁÎÁÌÁ Ó ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ (ëòû), ××ÅÄÅÎÎÏÇÏ × §2, ÕÓÌÏ×ÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉŽ ¡ ¢−1NN; ÅÓÌÉ (xN1 ; y 1 ) = t,tP (y1N |xN)=10;ÅÓÌÉ (xN1 ; y1N ) 6= t; 1 ≤ t < N;ÇÄÅ (xN1 ; y1N ) | ÞÉÓÌÏ ÎÅÓÏ×ÐÁÄÁÀÝÉÈ ÐÏÚÉÃÉÊ (ÒÁÓÓÔÏÑÎÉÅ èÜÍÍÉÎÇÁ) × Ä×ÏÉÞÎÙÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÑÈ yN É xN .
äÁÎÎÙÊ ËÁÎÁÌ Ñ×ÌÑÅÔÓÑ¡ ¢ÐÒÉÍÅÒÏÍ ËÁÎÁÌÁ Ó ÐÁÍÑÔØÀ É ÏÞÅ×ÉÄÎÏ,ÞÔÏ ÕÓÌÏ×ÎÁÑ ÜÎÔÒÏÐÉÑ ëòû H (Y1N |X1N ) = ln Nt . ðÏÜÔÏÍÕ ÉÎÆÏÒÍÁÃÉÑJ (X1N ; Y1N ) = H (Y1N ) − lnµ ¶Ntµ ¶≤N ln 2 − lnN;tÇÄÅ ÎÅÒÁ×ÅÎÓÔ×Ï ×ÙÔÅËÁÅÔ ÉÚ Ó×ÏÊÓÔ×Á 1. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÚÎÁË ÒÁ×ÅÎÓÔ×Á × ÜÔÏÍ ÎÅÒÁ×ÅÎÓÔ×Å ÄÏÓÔÉÇÁÅÔÓÑ ÎÁ ÒÁ×ÎÏÍÅÒÎÏÍ ×ÈÏÄÎÏÍ ÒÁÓÐÒÅÄÅÌÅÎÉÉ, Ô.Å.
ËÏÇÄÁNN−Np(xN1 ) = Pr{X1 = x1 } = 2 ;10NxN1 ∈ (0; 1) :ôÁËÉÍ ÏÂÒÁÚÏÍ, ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ ëòû ÚÁ ×ÒÅÍÑ N :µ ¶CN = N ln 2 − lnN:tðÏÜÔÏÍÕ ÔÅÏÒÅÍÙ 1 É 3 ÏÚÎÁÞÁÀÔ, ÞÔÏ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ = N ÐÒÉ ÐÅÒÅÄÁÞÅ ÐÏ ëòûÓÏÏÂÝÅÎÉÑ , ÐÒÉÎÉÍÁÀÝÅÇÏ M ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÈ ÚÎÁÞÅÎÉÊ, ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÎÅÒÁ×ÅÎÓÔ×Õµ ¶(1 − ) ln M − ln 2≤N ln 2 − lnN:täÁÎÎÏÅ ÎÅÒÁ×ÅÎÓÔ×Ï, Ó ÕÞÅÔÏÍ ÏÐÒÅÄÅÌÅÎÉÑ ÓËÏÒÏÓÔÉ ÐÅÒÅÄÁÞÉ R > 0, ÍÏÖÎÏ ÐÅÒÅÐÉÓÁÔØ ××ÉÄÅln Nln 2 − N( t ) + lnN2 = N ≥ 1 −:RðÕÓÔØ R > 0, 0 < p ≤ 1=2, | ÆÉËÓÉÒÏ×ÁÎÎÙÅ ÞÉÓÌÁ. òÁÓÓÍÏÔÒÉÍ ÁÓÉÍÐÔÏÔÉÞÅÓËÉÅÕÓÌÏ×ÉÑN → ∞ ; M = dexp{RN }e; t = dNpe :éÓÐÏÌØÚÕÑ ÉÚ×ÅÓÔÎÕÀ (ÓÍ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
