Лекции - Прикладная теория информации. Краткий конспект лекций

вероятностью, равной единице, и во всех остальных—с ве-

роятностью, равной нулю. При этом имеется в виду, что

lim log

p

i

ii

pp

→∞

= 0.

При равномерном распределении

p

m

i

X

=













1

энтропия

(X)=log m

x

Докажем, что это максимальное значение энтро-

пии.Исполь-

зуя равенство p

i

m

X

=

∑

1

0

, можно выполнить следующие тож-

дественные преобразования :

HX m p

p

Xi

i

m

X

i

()log log−= −

=

∑

1

−=−













=

==

∑∑

pm p

p

m

i

m

X

Xi

i

X

i

m

X

11

1

log log log

=

∑

p

pm

i

iX

i

m

X

log

1

для оценки выражения log

1

pm

iX

воспользуемся неравенст-

вом

ln ,zz

pm

iX

≤−1 положив z=

1

.

Заменяя

log log

1

pm pm

e

iX iX

на

1

−













, получим

HX m p

pm

e

Xi

iX

i

m

X

()log log−≤ −













=

∑

1

H 1

0,8

0,6

рис.1 Энтропия сис-

темы

0,4 с двумя состояниями

:

p - вероятность

одно-

0,2 го из состояний

0 0,2 0,4 0,6 0,8 1 P

=−













=− =

==

∑∑

1

11 0

11

m

pe e

X

i

m

i

m

i

log ( ) log ,

где log e- модуль перехода . Отсюда

HX m

X

() log

≤

.

Пусть множество Х состоит из двух элементов, которые

обозначим через единицу и ноль, причем единица позволя-

ет-

ся с вероятностью, равной р, а ноль — с вероятностью, рав-

ной q=1—р. Тогда

HX p p p p() log ( )log( )=− − − −11.

Указанная зависимость изображена на рис. 1. Максимум

достигается при p=q==0,5.

ЦЕННОСТЬ ИНФОРМАЦИИ

Все определения ценности информации связаны с поня-

тием цели. Ценной считается та информация, которая спо-

собствует достижению поставленной цели.

Один из способов измерения ценности информации,

сформулированный в рамках статистической теории ин-

формации, был предложен А. А. Харкевичем [3]. Ценность

информации может быть выражена через приращение веро-

ятности достижения цели. Если значение априорной веро-

ятности достижения цели обозначить через p

i

, а апостери-

орной — через р

2

, то ценность полученной информации

можно определить как

log

p

2

1

.

В системах передачи информации цель сводится к пра-

вильной передаче сообщений независимо от их конкретного

содержания и формулируется относительно каждого сим-

вола множества X. Пусть целью является принятие решения

в пользу x

i

. Тогда относительно этой цели ценность сведе-

ний,

содержащихся в принятом у

1

равна log

(| )

()

px y

px

ij

i

, где

p(x

i

) — априорная вероятность передачи x

i

, p(x

i

|y

j

) — ве-

роятность того, что было передано x

i

после принятия у

j

. При

такой формулировке цели ценность информации совпадает

с обычным количеством информации, которое определено

выше.

Таким образом, количество информации, которое у

j

, не-

сет об x

i

, равно

Iy x

px y

px

ji

ij

i

(,) log

(| )

()

=

Умножая числитель и знаменатель под логарифмом на p(y

j

)

и учитывая равенства

px y py px y py x px

ij j i j ji i

( | )( ) ( , ) ( | )( )

==

,

получим

Iy x

px y

px

px y

px py

py x

py

Ix y

ji

ij

i

ij

ji

j

ij

(,)

(| )

()

log

(, )

()( )

log

(|)

()

(, ).

== =

==

(3)

Отсюда следует, что у

j

несет об x

i

такое же количество ин-

формации, какое x

i

несет об у

j

(свойство симметрии). По-

этому I (x

i

,у

j

) называется взаимным количеством информа-

ции между i-м символом множества Х и j-м символом мно-

жества Y. Взаимное количество информации I(x

i

,у

j

) может

быть положительным (p(x

i

|y

j

)>p(x

i

)), отрицательным

(p(x

i

|y

j

)<p(x

i

)) и равным нулю (p(x

i

|y

j

)=p(x

i

)). Отрицательная

информация называется д е з и н ф о р м а ц и е й.

СОБСТВЕННАЯ ИНФОРМАЦИЯ И ЭНТРОПИЯ

Пусть в канале отсутствуют помехи. Тогда между эле-

ментами множеств X и Y имеет место взаимно однозначное

соответствие и p(x

i

|y

j

)=1 при i=j. В этих условиях количе-

ство информации, которое у

j

(j=i) доставляет об x

i

, согласно

(3) равно

I(x

i

)= - log p(x

i

)= - log p(y

j

).

Эта величина называется собственным количеством ин-

формации, которое несет символ x

i

, причем всегда I(x

i

)

>0.

Усредняя I(x

i

) по всему множеству X, получим количество

информации, которое в среднем несут сообщения множест-

ва X. Среднее значение совпадает с энтропией

HX pIx p p

ii i i

i

X

m

i

X

m

() () log==−

==

∑∑

11

,

где ppx

ii

= ().

ВЗАИМНАЯ ИНФОРМАЦИЯ

Источник информации и приемник можно рассматривать

как подсистемы одной сложной системы. Взаимную ин-

формацию между состояниями подсистем, используя (3),

можно записать в виде

Iy x px pxy

px py px y

py py x Ix y

ji i ij

ij ij

jjiij

( , ) log ( ) [ log ( | )]

log ( ) log ( ) [ log ( , )]

log ( ) [ log ( | )] ( , )

=− − − =

=− − − − =

=− − − =

. (4)

Поскольку сложная система случайным образом приходит в

то

или иное состояние, определяемое парой чисел (x

i

, y

j

), то

I(x

i

, y

j

) будет случайной величиной, которую можно усред-

нить по всему множеству состояний. В результате почлен-

ного усреднения (4) получим выражение для средней (пол-

ной) взаимной информации:

IYX HX HXY HX HY HXY(, ) ( ) ( |) ( ) () ( ,)=− =+− =

=− =HY HYX I XY() (| ) ( ,), (5)

где IYX px y Ix y

ij

j

m

Y

ij

i

m

X

(, ) ( , )( , );=

==

∑∑

11

HXY px y pxy

ij ij

j

m

Y

i

m

X

(|) (, )log(| );=−

==

∑∑

11

HYX px y py x

ij

j

m

Y

ji

i

m

X

(| ) ( , )log ( | ).=−

==

∑∑

11

С точки зрения информационного описания системы свя-

зи безразлично, какую из подсистем рассматривать в каче-

стве передатчика, а какую в качестве приемника.

Поэтому энтропии Н(Х) и H(Y) можно интерпретировать

как информацию, которая поступает в канал связи, а услов-

ные энтропии H(X/Y), H(Y/X) как информацию, которая рас-

сеивается в канале. В [1] доказано, что I(Х,Y)>0.

При выполнении указанного неравенства из (5) следует, что

HXY HX

HYX HY

HXY HX HY

(|) (),

(| ) (),

(,) () ().

≤

≤+

Условную энтропию можно представить в виде

HXY py pxy pxy py HXy

jij

i

m

X

ij j j

j

m

Y

j

m

Y

(|) ( ) (| )log(| ) ( )(| ),=− =

===

∑∑∑

111

где величина

HXy pxy pxy

jijij

j

m

X

(|) (|)log(|)=−

=

∑

1

называется ч а с т н о й у с л о в н о й э н т р о п и е й. Она

характеризует неопределенность состояния системы А в

случае, когда известно состояние у у наблюдаемой системы

В. Зафиксировав состояние у

j

системы В, мы тем самым из-

меняем комплекс условий, при которых может реализовать-

ся событие x

i

. Это обнаруживается как изменение вероят-

ности реализации события x

i

(,)in

=

1

(имеет место стати-

стическая зависимость). Если до изменения условий ука-

занная вероятность была равна безусловной (полной) веро-

ятности p(x

i

), то после изменения условий она стала равной

условной вероятности р(x

i

,y

j

). При отсутствии статистиче-

ской зависимости Н(X| у

j

) = Í(Õ), поскольку

px y px

ij i

(| ) ().

=

Таблица 1

X

y

x

1

x

2

p(y

j

)

y

1

y

2

0,5

0,25

0

0,25

0,5

p(x

i

) 0,75 0,25

Таблица 2

X

y

x

1

x

2

y

1

y

2

1

0,5

0

0,5

При наличии статистической зависимости энтропия Н(Х|у

j

)

может оказаться как меньше, так и больше Н(Х). Напомним,

что для энтропии H(X|Y) всегда справедливо неравенство

HXY HX(|) ()≤ .

В качестве примера вычислим энтропии Н(X), H(X|Y),

H(X|y

j

) и взаимную информацию I(X, Y) , когда системы А и

В описываются двумерным распределением р(x

i

, у

j

), задан-

ным в виде табл. 1. Вычисленные значения условной веро-

ятности

px y

py

ij

j

(| )

(, )

()

= записаны в табл. 2

Используя записанные в таблицах значения вероятностей,

получим

HXy px y px y px y px y(|) (|)log(|) (|)log(|)

111112121

=− − =

=− − =11000log log ,

HXy pxy pxy px y x y(|) (|)log(|) (|)log(|)

212122222

=− − =

=− + =(,log , ,log ,) ,05 05 05 05 1

HXY py HXy py HXy(|) ()(|) ( )(| ) , , ,,=+ =⋅+⋅=

112 2

05 0 05 1 05

HX() (, log, , log,) , ,=− + ≈025 025 075 075 0811

IXY HX HXY(,) () (|) , , , .=− ≈−=>0811 05 0311 0

Отсюда

HXy HX HXy

HX HXY

(|)()(|),

,,

() (|),

,,.

12

008111

0811 05

<<

>

3. ДИСКРЕТНЫЕ ИСТОЧНИКИ СООБЩЕНИЙ И

ИХ ОПИСАНИЕ

ЭРГОДИЧЕСКИЕ ИСТОЧНИКИ

Источник будем называть эргодическим, если его веро-

ятностные параметры можно оценить по одной достаточно

длинной реализации, которую он вырабатывает. При не-

ограниченном возрастании длины реализации (п) оценка

параметра (результат измерения) совпадает с его истинным

значением с вероятностью, равной единице. Например, при

бросании игральной кости можно оценить вероятность вы-

па-дания какой-либо цифры через относительную частоту

ее появления в достаточно длинной серии испытаний. Ука-

занная серия испытаний представляет собой ту самую реа-

лизацию, по которой осуществляется оценка вероятности

(параметра). Реализации, по которым можно оценить закон

распределения, являются типичными. Поэтому эргодиче-

ским источником можно назвать источник, который выра-

батывает типичные последовательности. Типичная после-

довательность несет сведения о структуре источника, то

есть является типичной для данного источника. Если два

источника различаюгся своей структурой (значением оце-

ниваемого параметра), то, наблюдая реализацию, можно

определить, какому из них она принадлежит. Источник, эр-

годический по одному параметру, может оказаться не эрго-

дическим по другому параметру.

ПРОИЗВОДИТЕЛЬНОСТЬ ДИСКРЕТНОГО ИСТОЧ-

НИКА СООБЩЕНИЙ

Кодовое слово, которое вырабатывает источник, будем

записывать в виде

xx x x x i

ii i

k

i

n

i

л

k

где

12

, ,... ,..., ,

−−

ÿ буква

(символ) алфавита с k порядковым номером в слове. Напри-

мер, пусть k=5, a i

5

==3. Это значит, что пятой буквой в сло-

ве является третья буква алфавита. Обозначим через Х

k

множество букв (алфавит), из которых выбирается k-ÿ буква

слова. В нашем случае все множества X

k

(k=1,n) состоят из

одних и тех же т

x

букв. Когда не требуется указывать место

буквы в слове, i-þ букву алфавита будем обозначать через

x

i

.

Количество информации, которое в среднем несет отдель-

ное слово, равно энтропии

HX X px x px x

nii

n

ii

n

( ,..., ) ( ,... )log ( ,... )

1

11

=−

∑

,

где суммирование ведется по всему множеству слов. Опре-

делим производительность источника Н

И

как предел отно-

шения

количества информации, которое в среднем несет отдельно

слово, к числу букв в слове п при неограниченном возраста

нии п:

H

HX X

n

И

n

=

→∞

lim

( ,..., )

1

(6)

Если буквы в слове статистически независимы (вероят-

ность выбора очередной буквы не зависит от состава пред

шествующих ей букв), то

HX X HX HX HX

nkn

( ,..., ) ( ) ... ( )... ( ),

11

=++ +

где H X px px

ki

k

i

k

i

k

m

X

() ()log()=−

=

∑

1

.

Источник со статистически независимыми буквами сооб-

щений будет стационарным, если вероятность выбора 1-й

буквы алфавита не зависит от того, какое место в слове она

занимает

(( ) ( ))px px

i

k

i

=

.

В этом случае

H(X

1

,...,X

n

)=nH(x)

н производительность источника (бит/символ)

HHX px px

И ii

i

m

X

==−

=

∑

() ()log()

1

.

Часто производительность источника измеряется количе-

ством информации

ν

HX()

, которое он вырабатывает за од-

ну секунду (

ν

—количество букв за одну секунду). Макси-

мальная производительность источника достигается, когда

все буквы алфавита появляются с равными вероятностями.

В этом случае Hm

И X

= log .

МАРКОВСКИЕ ИСТОЧНИКИ СООБЩЕНИЙ

Рассмотренная модель дискретного источника сообще-

ний имеет сравнительно узкую область применения, по-

скольку реальные источники вырабатывают слова при на-

личии статистической зависимости между буквами. В ре-

альных источниках вероятность выбора какой-либо очеред-

ной буквы зависит от всех предшествующих букв. Многие

реальные источники достаточно хорошо описываются мар-

ковскими моделями источника сообщений. Согласно ука-

занной модели условная вероятность выбора источником

очередной x

i

k

, буквы зависит

только от

ν

предшествующих. Математической моделью

сообщений, вырабатываемых таким источником, являются

цепи Маркова

ν

-ãî порядка. В рамках указанной модели

условная вероятность выбора i

k

-й буквы

px x x x px x x

i

k

i

k

i

k

ii

k

i

k

i

k

( | ..., ,..., ) ( | ,..., )

−−− − −

=

νν ν

11 1

.

Если последнее равенство не зависит от времени, то есть

справедливо при любом значении k, источник называется

однородным. Однородный марковский источник называет-

ся стационарным, если безусловная вероятность выбора

очередной буквы не зависит от k

(( ) ( ))px px

i

k

i

=

.

В даль-

Лекции - Прикладная теория информации. Краткий конспект лекций

Подождите немного. Документ загружается.