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

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

ПРИКЛАДНАЯ ТЕОРИЯ ИНФОРМАЦИИ

Конспект лекций

ПРЕДИСЛОВИЕ

Цель конспекта — помочь студентам усвоить основ-

ные понятия теории информации и научить их применять

информационные методы решения прикладных задач.

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

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

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

можности простой математический аппарат.

К сожалению, ограниченный объем работы не позво-

лил изложить интересные и важные вопросы передачи не-

прерывных сообщений и помехоустойчивого кодирования.

1. МОДЕЛИ, ИСПОЛЬЗУЕМЫЕ В СТАТИСТИЧЕ-

СКОЙ

2. ТЕОРИИ ИНФОРМАЦИИ

В основе любой теории лежит соответствующая модель

подлежащей изучению части реального мира. Область при-

менения результатов’ теории ограничена областью приме-

нения принятой модели. Мы рассмотрим модель, которая

лежит в основе статистической теории информации [1, 2].

Существуют и другие модели, на основе которых строятся

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

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

прагматической (ценностной) теории информации, которая

может быть построена в рамках статистической теории ин-

формации.

Понятие информация тождественно понятию сведения и

ассоциирует с наличием по крайней мере двух взаимодейст-

вующих систем А и В, одна из которых В является наблю-

даемой системой (приемником), а вторая А—источником

информации. Вне указанной схемы понятие информация те-

ряет смысл.

Любая система описывается совокупностью физических

величин, которые могут зависеть от параметров. Состояния

системы — это значения физической величины или пара-

метра, которые ее описывают. Если эти значения дискрет-

ны, то система называется д и с к р е т н о й , а если непре-

рывны, то система называется с и с т е м о й с н е п р е р

ы в н ы м м н о ж е с т в о м с о с т о я н и й .

Сообщение — это то, что можно сообщить, а сообщить

можно только состояние системы.Следовательно, с о о б щ

е- н и е — это состояние системы.

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

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

приходит в состояние, которое соответствует передаваемой

букве). Следовательно, множество состояний системы

можно рассматривать как множество случайных событий.

Две системы будем называть статистически зависимы-

ми,если состояние одной из них влияет на вероятность со-

стояния другой.

Множества состояний Х и Y соответственно систем А и

В в зависимости от того, в каком отношении они рассмат-

риваются, можно интерпретировать как множества состоя-

ний, сообщений и событий.

Два множества Х и Y с заданным на них двумерным рас-

пределением Px y x X y Yi m j m

ij i j X Y

(,)( , , , , , )∈∈= =11 пред-

ставляют собой модель двух взаимодействующих систем.

Эта модель лежит в основе построения статистической тео-

рии информации.

С и г н а л — это материальный переносчик информации

в пространстве и во времени.

Сигналы могут быть динамическими и статическими.

Д и н а м и ч е с к и е с и г н а л ы предназначены для пе-

редачи информации в пространстве (электромагнитная вол-

на). С т а т и ч е с к и е с и г н а л ы (запоминающие

устройства) предназначены для передачи информации во

времени (магнитная лента, книга, кинофильм и т. д.). Точ-

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

информации, а его состояние. Поэтому целесообразно кон-

кретизировать определение сигнала. С и г н а л — это зна-

чение физической величины, которое отображает состояние

источника сообщений. Поскольку множество сообщений

можно рассматривать как множество случайных событий,

то отображающее значение физической величины также

будет случайным.

Следовательно, случайную величину можно принять в

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

темны (передаваемое сообщение) изменяется во времени,

поэтому

указанная случайная величина также будет изме-

няться во времени, зависеть от времени. Случайная величи-

на, зависящая от времени (некоторого параметра), назы-

вается с л у ч а й- н о й ф у н к ц и е й . Следовательно,

случайная функция является моделью сигнала.

2. УСТАНОВЛЕНИЕ КОЛИЧЕСТВЕННОЙ МЕРЫ

ИНФОРМАЦИИ

КОМБИНАТОРНОЕ ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА

ИНФОРМАЦИИ

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

дано американским инженером Р. Хартли. Это определение

пред- полагает модель с детерминированной связью (поме-

хи отсут-ствуют) между дискретными состояниями двух

систем без их вероятностного описания.

До получения сведений о состоянии системы имеется ап-

риорная неопределенность ее состояния. Сведения позво-

ляют снять эту неопределенность, то есть определить со-

стояние системы. Поэтому количество информации можно

определить как меру снятой неопределенности, которая

растет с ростом числа состояний системы.

Количественная мера информации устанавливается сле-

дующими аксиомами.

Аксиома 1. Количество информации, необходимое для

снятия неопределенности состояния системы, представляет

собой монотонно возрастающую функцию числа состояний

системы.

В качестве количественной меры информации можно вы-

брать непосредственно число состояний системы m

, кото-

рое является единственной характеристикой множества X.

Однако такое определение не удобно с точки зрения его

практического применения. Поэтому в теории информации

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

которая является функцией т

. Вид указанной функции по-

зволяет установить аксиома 2.

Аксиома 2.Неопределенность состояния сложной систе-

мы, состоящей из двух подсистем, равна сумме неопреде-

ленностей подсистем.

Если для снятия неопределенности первой подсистемы

необходимо количество информации, равное I(т

), а для

второй подсистемы количество информации, равное I(m

то для снятия неопределенности сложной системы необхо-

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

I(m

) = I(m

) + I(m

) ,

где т

— число состояний первой подсистемы; т

— число

состояний второй подсистемы; т

—число состояний

сложной системы.

Единственным решением полученного функционального

уравнения является логарифмическая функция I(т)=К log

т, которая определяет количество информации как лога-

рифм числа состояний системы. Произвольный коэффици-

ент К выбирается равным единице, а основание логарифма

а определяет единицу измерения количества информации.

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

ются двоичными (а=2), троичными (а=3) и в общем случае

а-ичными. В дальнейшем под символом log будем понимать

двоичный логарифм. Двоичная единица иногда обозначает-

ся bit (от английского binary digit - двоичный знак).

Каждое передаваемое слово из п букв, записанное в ал-

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

дельное «укрупненное» состояние источника сообщений.

Всего таких состояний (слов) будет т

Тогда количество информации, которое несет слово из п

букв, равно I=log

=nlog

m. Отсюда следует, что одна бу-

ква несет log

m а-ичных единиц информации. Если единица

измерения информации а=т, то количество информации в

слове (I=п) измеряется количеством содержащихся в нем

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

мером алфавита т. Таким образом, одна a-ичная единица

содержит log

m a-ичных единиц информации.

ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ

ПО К. ШЕННОНУ

Согласно комбинаторному определению количества ин-

формации для установления записанного в регистр двоич-

ного числа, имеющего п разрядов, требуется п двоичных

единиц информации (по одной двоичной единице или по

одному двоичному вопросу на выяснение содержания каж-

дого разряда). Определить записанное в регистр число по-

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

меньшее количество информации, невозможно, если мы об

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

не знаем. Количество необходимой информации можно,

уменьшить только в том случае, если мы будем располагать

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

о способе его записи (генерации).

Допустим, некоторое устройство вырабатывает (генери-

рует) число как независимую последовательность из единиц

и нулей, которые появляются соответственно с вероятно-

стями, равными p и q=1— р. В этом случае при неограни-

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

ностью, равной единице, появляются последовательности,

количество единиц в которых незначительно отличается от

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

называются т и п и ч н ы м и. Они различаются между

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

Поскольку количество типичных последовательностей Q

меньше общего количества последовательностей, то имеет-

ся возможность уменьшить количество информации, необ-

ходимое для определения числа.

Последовательность назовем типичной для заданного ис-

точника, если количество единиц п

в ней удовлетворяет

неравенству

−<ε или

nnpn

−<ε

(1)

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

[[

nnp

−≥ε

. (2)

Вероятность появления нетипичной последовательности

равна вероятности, с которой п

удовлетворяет неравенству

(2). Для оценки этой вероятности воспользуемся нера-

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

величины ξ имеющей конечную дисперсию, при каждом

b>0 записывается в виде

{}

P- b

ξξ

≥≤

где ξ и

— соответственно математическое ожидание и

дисперсия случайной величины

ξ .Полaгаяξξ===

np, , b= n,

σσ

npq

,(q=(1-

p)) получим аналогичное неравенство для случайного числа

единиц n

{}

Pn np n

−≥ ≤ε

Следовательно, вероятность появления нетипичной после-

довательности

≤

а вероятность появления типичной последовательности

THT

=− >−11

Вероятность Р

стремится к нулю, а вероятность Р

стре-

мится к единице при любом сколь угодно малом значении

и неограниченном возрастании длины последовательно-

сти п. Интервал

[]

− nnεε,. которому принадлежит количест-

во единиц в типичной последовательности, неограниченно

увеличивается (

ε→∞

), хотя относительная величина ин-

тервалa

nnp

−

всегда меньше значения

. Докажем, что

одновре-менно с неограниченным увеличением длины по-

следовательности п можно уменьшать значение

εε=

()n

такой скоростью, при которой относительная величина ин-

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

типичной последовательности—к единице. При этом абсо-

лютная величина интервала по-прежнему неограниченно

возрастает. Вероятность Р

стремится к единице, если вели-

чина

()nn неограниченно увеличивается с ростом n.

Пусть

δ22

()nn n

, где

δ>

некоторый параметр, опреде-

ляющий скорость роста величины

()nn.

Oтсюда

εδ

() ( ,)

nn=<<

−+05

005 .

Величина

()n

стремится к нулю с ростом п при

δ<

05,.

При этом абсолютная величина интервала

()

не может

быть постоянной или стремиться к нулю одновременно с

неограниченным увеличением величины

()nn, стремле-

нием

()n

к нулю.

Определим количество типичных последовательностей

Q. Вероятность появления произвольной по-

следовательности B

равна

PB P

()

−

В результате тождественных преобразований

PB p q

npnnp nqnnnq

np nq

nnp

()

() ( )

()













+− +−−

−

Прологарифмировав последнее равенство, получим

log

P(B

)=nplog

p+nqlog

+− =−− − −

−

=− −

( ) log [ log log

log ] [ ( ) ( )],

nnp

np pq q

nnp

nH x On

mmm

где величина H(x)=-plog

p-qlog

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

ется э н т р о п и е й .

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

остаточным членом О (п) по сравнению с величиной

H(X)можно пpенебречь.

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

ли-во неравенство

nnpn

−<ε,то

On n

() ()log log

−+

δ05

Следовательно,

lim ( )

→∞

=≠≠0 (p 0,q 0).

Таким образом, при достаточно большом п справедливо

приближенное равенство

log ( ) ( )

PB nH X

≈−

Отсюда вероятность появления отдельной типичной после-

довательности

PB m

nH X

()

≈

−

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

пичной последовательности k, то все типичные последова-

тельности примерно равновероятны. Вероятность появле-

ния типичной последовательности

PPBQm

nH X

== ≈

−

∑

() ,

()

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

последовательностей. Отсюда.

Q=m

nH(X)

причем единица измерения энтропии Н (X) совпадает с ос-

нованием степени т. Поскольку количество информации,

нужное для определения числа (состояния регистра), равно

logQ, энтропия

()

log

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

ции,

которое необходимо для определения состояния одного раз-

ряда.

Аналогично определяется количество типичных последо-

вательностей, вырабатываемых источником с алфавитом

размера т

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

HX px px

() ()log()=−

∑

СВОЙСТВА ЭНТРОПИИ

Энтропия

HX p p

() log=− ≥

∑

поскольку p

удовлетворяет неравенству 01

≤≤

. Энтро-

пия H(Х)=0,когда система находится в одном из состояний с