Подпишитесь на наши новости
Вернуться к началу с статьи up
 

ИНФОРМА́ЦИИ ТЕО́РИЯ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 11. Москва, 2008, стр. 485

  • image description

    Скопировать библиографическую ссылку:




Авторы: Ю. В. Прохоров

ИНФОРМА́ЦИИ ТЕО́РИЯ, раз­дел ма­те­ма­ти­ки, ис­сле­дую­щий про­цес­сы хра­не­ния, пре­об­ра­зо­ва­ния и пе­ре­да­чи ин­фор­ма­ции. И. т. – часть ки­бер­не­ти­ки. В ос­но­ве И. т. ле­жит оп­ре­де­лён­ный спо­соб из­ме­ре­ния ко­ли­че­ст­ва ин­фор­ма­ции, со­дер­жа­щей­ся в к.-л. дан­ных (со­об­ще­ни­ях).

И. т. ис­хо­дит из пред­став­ле­ния о том, что со­об­ще­ния, пред­на­зна­чен­ные для со­хра­не­ния в за­по­ми­наю­щем уст­рой­ст­ве или для пе­ре­да­чи по ка­на­лу свя­зи, не из­вест­ны за­ра­нее с пол­ной оп­ре­де­лён­но­стью. За­ра­нее из­вес­тен лишь ис­точ­ник со­об­ще­ний, т. е. мно­же­ст­во $x_1,\,x_2,\,…,x_n$, из ко­то­ро­го мо­гут быть вы­бра­ны эти со­об­ще­ния, ве­ро­ят­но­сти $p_1,\,p_2,\,…,p_n$ по­яв­ле­ния этих со­об­ще­ний. В И. т. не­оп­ре­де­лён­ность, с ко­то­рой стал­ки­ва­ют­ся в по­доб­ной об­ста­нов­ке, до­пус­ка­ет ко­ли­че­ст­вен­ное вы­ра­же­ние, и имен­но это ко­ли­че­ст­во, а не кон­крет­ная при­ро­да са­мих со­об­ще­ний, оп­ре­де­ля­ет воз­мож­ность их хра­не­ния и пе­ре­да­чи. Рас­смат­ри­ва­ют­ся все­воз­мож­ные спо­со­бы за­пи­си со­об­ще­ний це­поч­ка­ми сим­во­лов 0 и 1, на­зы­вае­мые дво­ич­ны­ми ко­да­ми, удов­ле­тво­ряю­щие ус­ло­ви­ям: а) разл. со­об­ще­ни­ям со­от­вет­ст­ву­ют разл. це­поч­ки; б) по за­пи­си лю­бой по­сле­до­ва­тель­но­сти со­об­ще­ний в ко­ди­ро­ван­ной фор­ме эта по­сле­до­ва­тель­ность долж­на од­но­знач­но вос­ста­нав­ли­вать­ся. В ка­че­ст­ве ме­ры не­оп­ре­де­лён­ности ис­точ­ни­ка со­об­ще­ний при­ни­ма­ют сред­нее зна­че­ние дли­ны ко­до­вой це­поч­ки, со­от­вет­ст­вую­щее са­мо­му эко­ном­но­му спо­со­бу ко­ди­ро­ва­ния; еди­ни­цей из­ме­ре­ния слу­жит один дво­ич­ный знак.

При­мер. Пусть не­ко­то­рые со­об­ще­ния $x_1,\, x_2,\, x_3$ по­яв­ля­ют­ся с ве­ро­ят­но­стя­ми, рав­ны­ми со­от­вет­ст­вен­но 1/2, 3/8, 1/8. К.-л. ко­рот­кий код, напр. $x_1=0,\, x_2=1,\, x_3=01$, не при­го­ден, т. к. на­ру­ша­ет­ся ус­ло­вие б), по­сколь­ку це­поч­ка 01 мо­жет оз­на­чать как $x_1x_2$, так и $x_3$. Код $x_1=0,\, x_2=10,\, x_3=11$ удов­ле­тво­ря­ет ус­ло­ви­ям а) и б). Ему со­от­вет­ст­ву­ет сред­нее зна­че­ние дли­ны ко­до­вой це­поч­ки, рав­ное $$1\cdot \frac{1}{2}+2\cdot \frac{3}{8} +2\cdot \frac{1}{8}=1,5. $$ Ока­зы­ва­ет­ся, что ни­ка­кой дру­гой код не мо­жет дать мень­ше­го зна­че­ния, т. е. ука­зан­ный код – са­мый эко­ном­ный, ме­ра не­оп­ре­де­лён­но­сти дан­но­го ис­точ­ни­ка со­об­ще­ний рав­на 1,5 (дво­ич­ных зна­ков).

Не су­ще­ст­ву­ет про­стой фор­му­лы, вы­ра­жаю­щей точ­ный ми­ни­мум $H′$ сред­не­го чис­ла дво­ич­ных зна­ков, не­об­хо­ди­мых для ко­ди­ро­ва­ния со­об­ще­ний $x_1,x_2,…,x_n$, че­рез ве­ро­ят­но­сти $p_1,p_2,…,p_n$ этих со­об­ще­ний. Од­на­ко этот ми­ни­мум не мень­ше ве­ли­чи­ны $$H=\sum_{i=1}^n p_i \log_2(1/p_i)$$ и мо­жет пре­вос­хо­дить её не бо­лее чем на еди­ни­цу. Ве­ли­чи­на $H$ на­зы­вае­мая эн­тро­пи­ей ис­точ­ни­ка со­об­ще­ний, об­ла­да­ет про­сты­ми свой­ст­ва­ми, а для всех вы­во­дов И. т., ко­то­рые но­сят асим­пто­тич. ха­рак­тер, т. е. со­от­вет­ст­ву­ют слу­чаю $H'\to \infty$, различие между $H$ и $H'$ несущественно. Поэтому именно энтропия принимается в качестве меры неопредлённости данного источника. В приведенном выше примере энтропия равна $$H=\frac{1}{2} \log_2+\frac{3}{8}\log_2 \frac{8}{3} + \frac{1}{8} \log_2 8=1,40564.$$

Эн­тро­пия бес­ко­неч­ной со­во­куп­но­сти со­об­ще­ний $x_1,x_2,…$, по­яв­ляю­щих­ся с ве­ро­ят­но­стя­ми $p_1,p_2,…$, ока­зы­ва­ет­ся, как пра­ви­ло, бес­ко­неч­ной, по­это­му в при­ме­не­нии к ис­точ­ни­кам с бес­ко­неч­ным чис­лом со­об­ще­ний по­сту­па­ют ина­че. Имен­но, за­да­ют­ся оп­ре­де­лён­ным уров­нем точ­но­сти и вво­дят по­ня­тие $ε$-эн­тро­пии как эн­тро­пии со­об­ще­ния, за­пи­сы­вае­мо­го с точ­но­стью до $ε$, ес­ли со­об­ще­ние пред­став­ля­ет со­бой не­пре­рыв­ную ве­ли­чи­ну или функ­цию, напр., вре­ме­ни.

Так же, как и по­ня­тие эн­тро­пии, по­ня­тие ко­ли­че­ст­ва ин­фор­ма­ции, со­дер­жа­щей­ся в од­ном слу­чай­ном объ­ек­те (слу­чай­ной ве­ли­чи­не, слу­чай­ном век­то­ре, слу­чай­ной функ­ции и т. д.) от­но­си­тель­но дру­го­го, вво­дит­ся сна­ча­ла для объ­ек­тов с ко­неч­ным чис­лом $n$ воз­мож­ных зна­че­ний. За­тем об­щий слу­чай изу­ча­ет­ся при по­мо­щи пре­дель­но­го пе­ре­хо­да при $n→∞$. В от­ли­чие от эн­тро­пии ко­ли­че­ст­во ин­фор­ма­ции, напр. в од­ной не­пре­рыв­но рас­пре­де­лён­ной слу­чай­ной ве­ли­чи­не от­но­си­тель­но дру­гой не­пре­рыв­но рас­пре­де­лён­ной ве­ли­чи­ны, час­то ока­зы­ва­ет­ся ко­неч­ным.

По­ня­тие ка­на­ла свя­зи в И. т. но­сит весь­ма об­щий ха­рак­тер. Ка­нал свя­зи за­да­ёт­ся ука­за­ни­ем мно­же­ст­ва до­пус­ти­мых со­об­ще­ний на вхо­де ка­на­ла, мно­же­ст­вом со­об­ще­ний на вы­хо­де и на­бо­ром ус­лов­ных ве­ро­ят­но­стей по­лу­че­ния то­го или ино­го со­об­ще­ния на вы­хо­де при дан­ном вход­ном со­об­ще­нии. Эти ус­лов­ные ве­ро­ят­но­сти опи­сы­ва­ют влия­ние по­мех, ис­ка­жаю­щих пе­ре­да­вае­мые со­об­ще­ния. При­сое­ди­няя к ка­на­лу свя­зи ис­точ­ник со­обще­ний, мож­но рас­счи­тать ко­ли­че­ст­во ин­фор­ма­ции от­но­си­тель­но со­об­ще­ния на вхо­де, со­дер­жа­щее­ся в со­об­ще­нии на вы­хо­де. Верх­няя грань та­ких ко­ли­честв ин­фор­ма­ции, взя­тая по всем до­пус­ти­мым ис­точ­ни­кам, на­зы­ва­ет­ся про­пу­ск­ной спо­соб­но­стью (ём­ко­стью) ка­на­ла. Про­пуск­ная спо­соб­ность ка­на­ла – его осн. ин­фор­мац. ха­рак­те­ри­сти­ка. Не­смот­ря на влия­ние (быть мо­жет, силь­ное) по­мех в ка­на­ле, при оп­ре­де­лён­ном со­от­но­ше­нии ме­ж­ду эн­тро­пи­ей по­сту­паю­щих со­об­ще­ний и про­пу­ск­ной спо­соб­но­стью ка­на­ла при над­ле­жа­щем ко­ди­ро­ва­нии воз­мож­на поч­ти без­оши­боч­ная пе­ре­да­ча со­об­ще­ний.

В И. т. изу­ча­ют­ся оп­ти­маль­ные в смыс­ле ско­ро­сти и на­дёж­но­сти спо­со­бы пе­ре­да­чи ин­фор­ма­ции и ус­та­нав­ли­ва­ют­ся тео­ре­тич. пре­де­лы дос­ти­жи­мо­го ка­че­ст­ва. И. т. но­сит су­ще­ст­вен­но ве­ро­ят­но­ст­ный ха­рак­тер и зна­чи­тель­ная часть её ма­те­ма­тич. ме­то­дов за­им­ст­ву­ет­ся из тео­рии ве­ро­ят­но­стей.

Ос­но­вы И. т. бы­ли за­ло­же­ны в 1948–1949 К. Шен­но­ном. Её тео­ре­тич. раз­де­лы раз­ра­ба­ты­ва­лись А. Н. Кол­мо­го­ро­вым и А. Я. Хин­чи­ным, а раз­де­лы, свя­зан­ные с при­ме­не­ния­ми, – В. А. Ко­тель­ни­ко­вым.

Лит. см. при ст. Ин­фор­ма­ция.

Вернуться к началу