книги из ГПНТБ / Толстоусов, Г. Н. Прикладная теория информации учеб. пособие
.pdfвтся с разной частотой, мера Хартли является непригодной.Напри мер,контролируемые системы при правильном режиме эксплуатации и контроле должны чаще быть исправными, чем неисправными. Парамет ры движения самолета должны чаще находиться вблизи расчетных значений, а большие отклонения хотя и могут иметь место, но бу дут наблюдаться реже и т .д . Подобные примеры могут быть приве дены для большинства информационных систем. Но все состояния источника равноправны с точки зрения частоты их появления.
Частота появления различных состояний источника информации характеризуется законом распределения вероятностей. Поэтому в отличии от Р.Хартли, который в качостве признака источника ин формации рассматривал число его возможных состояний, К. Шѳннои ввел для определения дискретного источника информации вероятно
сти |
его состояний. |
|
|
|
|
|
X |
Пусть |
иыоѳтся статический дискретный источник информации |
||||
, определяемый табл. 3 .1 . |
В ней указывается л |
возможных |
||||
состояний |
источника х |
и вероятности этих состояний |
рс * |
|||
|
|
Таблица |
3.1 |
Рассматривается |
один ис- |
|
|
X , |
|
••• |
------ |
точник, который находится в ка- |
|
|
|
рп |
ком-то одном состоянии. Какую |
|||
Pi |
Л |
Рх |
••• |
же роль здесь играют |
вѳроятно- |
|
|
|
сти - характеристики |
частоты |
|||
|
|
|
|
|
||
|
|
|
|
|
появления состояний в массовой |
|
серии опытов? Под источником в теории информации понимается фи зическая система из некоторой большой партии систем с одинаковы ми законами распределения вероятностей состояний. Каждая из этих систем находится в каком-то одном состоянии и не меняет
его. Вероятность |
примерно есть число систем, находящихся в |
|
состоянии |
, |
деленное на число всех систем. Более точно в |
терминах теории вероятности это положение формулируется следую щим образом. Вероятность того, что отношение числа систем,нахо
дящихся в состоянии |
, к числу всех систем мало |
отличается |
от вероятности р' |
, стремится к единице с ростом |
числа систем |
в партии. |
|
|
Для характеристики статистического источника информации К.Шенноном предложена мера, аналогичная мере Р.Хартли и наз ванная им энтропией. Эта характеристика может быть получена, например, следующим путем.
9
Среди различных длинных блоков из N сообщений источника информации согласно теории вероятности большая часть будет та
ких, где сообщение х , будет встречаться A/f раз, сообщение Хг - раза и т .д . Причем
и т .д .
Общее число различных блоков такого вида равно
/ , .. М.....
L /Ц /Ц /...Л /п / '
Согласно Р.Хартли информационной характеристикой блока,ко торую К.Шеннон называет энтропией Н^ , является логарифм чи сла различных блоков. Поэтому
Используя формулу Стирлинга |
|
Ш ! |
1), |
имеем
HN~ к[ы (іпЫ -і)-£(епЫ і - <)].
Так как
Л . - Р
получаем
HN — N Lpcfojp. .
Это характеристика блока из N сообщений, а для одного сообще ния, входящего в блок,
Н=- £ рс tyPc ■
Найденное выражение справедливо не только в рассмотренном комбинаторном смысле. К.Шеннон получил это выражение при самых общих предположениях, к рассмотрению которых мы и перейдем.
До получения сообщения источник информации обладает некото рой неопределенностью. Известно, какие могут быть состояния у
10
источника, известны вероятности их появления и не известно,какое состояние имеет место в действительности.
Аксиомы, предложенные К.Шенноном, позволяют найти соотноше ние для вычисления количества неопределенности.
Первая аксиома. "Мера неопределенности есть непрерывная функция вероятностей состояний источника информации".
Для иллюстрации этой аксиомы можно привести следующие рас суждения. Неопределенность источника, заданного табл. 3 .2 ,будет больше, чем неопределенность источника, заданного табл. 3 .3 .
Таблица 3.2 Таблица 3.3
X, |
Я-Л |
Уі |
У, |
У* |
Pi 0.5 |
|
_ J L |
0.999 |
0.001 |
Выбирая для второго источника |
состояние |
у, , |
мы почти все |
|
гда будем правы. |
Почти все источники Y находятся |
в этом состо |
||
янии. Неопределенность состояний мала. Для первого источника не определенность больше. Нам надо выбрать одно из двух равноверо ятных состояний. Таким образом, неопределенность зависит от ве роятностей состояний. С другой стороны, если, например, в табл. 3.2 изменить вероятности на малую величину, то очевидно, что неопределенность изменится. Однако нет оснований предполагать, что неопределенность изменится существенно. Поэтому в аксиоме указано, что неопределенность есть непрерывная функция вероят ностей.
Заметим, что неопределенность не зависит по аксиоме от фи зической природы состояний, от их конкретных значений. Эти ха - рактѳристики систем остаются вне поля зрения аппарата теории ин формации, изучаемого в данном курсе. ^
Вторая аксиома. "Для источников с равновероятными состоя ниями мера неопределенности увеличивается с ростом числа состоя ний". Действительно, для источника с двумя равновероятными со стояниями возможности выбора меньше, чем для источника с тремя равновероятными состояниями.
Третья аксиома. "При раскрытии неопределенности имеется свобода выбора". Процесс раскрытия неопределенности может прохо дить различным образом. Рассмотрим следующий пример. Курсовой
II
угол полета самолета может лежать в пределах + 5°. Информация
о курсе выдается гироскопом с интервалом 1°. Тогда самолет пред ставляет собой источник информации с II состояниями. Неопреде ленность зависит от вероятностей этих состояний и может быть раскрыта (устранена) после получения сообщения от источника ин формации - гироскопа. Однако возможен другой способ раскрытия неопределенности. Пусть кроме гироскопа на борту имеется директорный указатель курса. Предположим, что при положении самолета в пределах + 2° он выдает сигнал о нормальном полете. При поло жении в пределах + 3° * + 5° поступает сигнал об отклонении влево. При положении в пределах - 3° + - 5° поступает сигнал об отклонениях вправо. С помощью директорного указателя и гироско па можно неопределенность раскрыть следующим образом. На первом этапе пилот получает информацию от директорного указателя, а на втором этапе он уточняет её по информации гироскопа.
Неопределенность, раскрываемая на первом этапе, равна не определенности источника с тремя возможными состояниями: "нор ма", "влево", "вправо"-и определяется вероятностями этих состо яний. На втором этапе раскрытия неопределенности может встре титься три различных случая. Первый случай, когда после сигнала "влево" может поступить три сигнала гироскопа: + 5°; + 4°; + 3° и раскрывается неопределенность источника с тремя состояниями. Неопределенность в этом случае определяется вероятностями ука занных состояний. Второй случай будет после сигнала "норма".Тѳперь возможные сигналы гиооскопа лежат в пределах + 2 4 - - 2°. Третий случай будет после сигнала "вправо".
Таким образом, при раскрытии неопределенности на втором этапе мы в общем случае получаем разные значения неопределенно сти, так как число возможных сообщений и их вероятности могут быть различными. Поэтому в качестве меры неопределенности, рас крываемой на втором этапе,следует принимать среднестатистичес кое значение неопределенности для разных случаез, т .е . матема тическое ожидание. Как вычисляется математическое ожидание не определенности на втором этапе, будет показано в следующем па раграфе.
Мы рассмотрели два возможных способа раскрытия неопреде ленности: первый, когда с помощью гироскопа сразу указывается состояние источника, и второй, когда сначала с помощью дирек
12
торного указателя определяется группа, к которой принадлежи состояние источника, а затем с помощью гироскопа указывается состояние. Оба способа схематично показаны на рис. 3,1;
Рис. 3.1
Оба способа точно указывают состояние одного и того же ис точника, поэтому в третьей аксиоме и утверждается, что величина раскрытой неопределенности в обоих случаях одинакова.
Три аксиомы К.Шеннона являются только одним из методов по строения математического аппарата теории информации. Существует еще несколько методов определения количества информации, но все они приводят прсктичѳски к одинаковым результатам,и нами рассма триваться не будут,
§ 4. Эн т р о п и я дискретного источника информации
Рассмотренные в предыдущем параграфе трп аксиомы позволяют получить математическое выражение для меры неопределенности дискретного источника информации. К.Шеннон меру неопределенности называет энтропией; в дальнейшем и мы будем пользоваться этим термином.
Предварительно найдем выражение для энтропии источника с
равновероятными состояниями. |
, |
|
Пусть имеется источник информации^ S '* "равновероятными |
||
состояниями. Вероятность каждого |
состояния равна |
. Энтропию |
такого источника, как функцию вероятностей состояний
13
для краткости обозначим в вида
H=H(sm). |
(4. О |
Будем раскрывать неопределенность по этапам. На гервом |
|
этапе все состояния разобьем на S |
одинаковых групп. Каждая |
группа объединяет |
s m~f равновероятных |
состояний, следовательно, |
|
группы'будут равновероятны и вероятность их равна |
. На вто |
||
ром этапе каждая |
группа разобьется на |
5 одинаковых |
групп |
(рис. 4 .1 ). |
|
|
|
>&т
Таких групп будет S , и все они равновероятны, так как в каждую входят Sm'~z равновероятных состояний. 11а третьем эта
пе каждая группа разбивается на |
s |
групп, |
а всего |
групп |
будет |
|
S 3 |
и т .д . Очевидно, что после |
т. этапов |
групп |
будет |
Sm , |
|
т .ѳ . |
в каждую группу входит одно |
состояние |
источника. |
|
||
|
При раскрытии неопределенности |
на первом этапе имеем S |
||||
равновероятных групп. Величина этой неопределенности в соответ ствии с первой аксиомой есть некоторая функция
S
которую для краткости обозначим как
Ht=H(s)
При раскрытии неопределенности на втором этапе мы имеем S вариантов, так как на первом этапе выбирается одна из 5
групп. Но все эти варианты равноценны, так как в каждом иэ них на втором этапе надо выбрать одну иэ S равновероятных групп, поэтому величина неопределенности, раскрытой па втором этапе,
На третьем этапе может быть s г вариантов, но в каждом раскрывается неопределенность
M9 = H(s).
Так как для полного раскрытия неопределенности источника необ
ходимо т этапов, то |
неопределенность источника |
|
|
H=/nH(s) . |
( ы ) |
Согласно третьей |
аксиоме неопределенность источника |
не за |
висит от способа её раскрытия. Поэтому величина неопределеннос
ти (4 .1 ), полученной |
при непосредственном раскрытии, равна вели |
||||||
чине |
(4 .2 ), |
полученная при раскрытии по этапам: |
|||||
|
|
|
|
|
H(s m)=rnH(s) . |
(4.ъ) |
|
|
Рассмотрим два источника с равновероятными состояниями. |
||||||
Пусть |
количества |
состояний |
одного источника |
s m и другого Ьп |
|||
(где |
S |
, |
т , |
t |
, гъ |
- целые числа, и |
ѣ - велико),нахо |
дятся в |
следующем соотношении: |
|
|||||
|
|
|
|
|
|
|
(4.4) |
15
В соответствии оо второй аксиомой, используя обозначение (4 .1 ), запишем
Н(з'"'М H(tn)<H(sm*1. |
(4.5) |
Согласно (4.3) последнее выражение примет вид
mH( s) éп Н ) Н ( $ ) .
Разделив все части неравенства на величину nH(s)
т „ H it) у т |
. / |
п, ~~ H(S) гъ |
п • |
Прологарифмируем выражение (4 .4 ). Тогда
(4.6)
, получим
(4J)
(48)
Разделим все части этого неравенства |
на величину п toflS |
, ПОЛУ' |
|||||
чим |
|
|
|
|
|
|
|
|
|
т s foot |
, т |
4 |
|
|
(4.9) |
|
|
іь ~~ eSgs |
л |
п |
• |
|
|
|
|
|
|
||||
Сравним выражения (4.7) |
|
и |
(4 .8 ). Видно, |
что две ве |
|||
Hit) |
ШЬ) |
равны между собой |
с точностью до малой величины |
||||
ш |
г |
|
|
|
|
|
|
п |
' |
|
|
|
|
|
|
|
|
!н (і) |
бю(і) / |
/ |
|
|
|
|
|
/ H(s) |
eoa(seotf(s), |
a |
|
|
|
Отношение неизвестной |
нам функции Н |
для двух произволь |
|||||
ных значений её аргументов равно отношению логарифмов этих аргу ментов. Следовательно, функция пропорциональна логарифму аргу мента: __.___
H(s )=k £oqs.
Так как основание логарифмов может быть любое, коэффициент пропорциональности к можно опустить и записать выражение для энтропии источника информации с равновероятными состояниями в виде
16
H=H(s)= Boys. |
(WO) |
Для источника с равновероятным состояниям мера неопреде ленности или энтропия равна логарифму числа состояний.
Найдем выражение для энтропии источника с неравновероятны ми, состояниями, заданного в общем виде табл. 3.1* При непосред ственном раскрытии неопределенности этого источника,согласно первой аксиоме,получим некоторую величину
н=н(Рі.Рл ,.-.р*). tort
Представим вероятности состояний источника в следующем ви
де: |
|
|
Кі ' |
|
1 |
|
|
|
п= |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
л — |
|
Кг |
|
|
|
(WZ) |
|
Н.- |
5 |
* |
' |
[ |
|
|
|
|
|
|
||||
|
• |
|
Кп. |
|
|
|
|
|
Нт 4 |
|
|
|
|
|
|
где Кі \ |
; . . . |
; |
Кп - |
целые |
числа. |
г |
|
Например, |
если |
р1= | |
| |
, |
то Kt = 2, Kt - |
3,J l rtj, = 5. |
|
Если pt = 0,81, />*= 0,19, |
то |
Кі = 81, Кг = 19, f |
=100 . |
|
Представление вероятностей в |
виде |
(4.12) возможно с‘'любой |
задан |
|
ной |
наперед точностью и тогда, когда вероятности - иррациональ |
|||
ные |
числа. |
|
|
|
Рассмотрим некоторый вспомогательный источник информации с
А |
|
равновероятных состояний. Очевидно, что вероятность как- |
|
дого состояния равна |
К,- . Раскроем неопределенность этого |
источника в два этапа. Группы на первом этапе образуем следую
щим образом. В |
первую группу (обозначим её |
x t ) объединим ні |
|||||
состояний ^ р и с .4 .2 ). Очевидно, что |
вероятность этой |
группы . |
|||||
равна |
— |
или»согласно |
(4.12)» |
Рі . Во вторую группу ( х д ) |
|||
о б ъ е д и н и м с о с т о я н и й . |
Тогда вероятность |
этой |
группы равна |
||||
Кг |
или р |
. Объединяя |
в каждую группу |
x L |
по |
состоя- |
|
£,Кі |
|
|
|
|
|
|
|
ГіубЛИЧИЯ.І1 - -алгі», ,е кая
loi-j С ОС?"
с 'чЗг'.'СЛЛЯР
41 IT ■*'l'sw r.r п 3 л Г д
ний, мы распределим BceZZ^ состояний вспомогательного источни ка в гь групп. Вероятность группы Хс равна рс . Обращаясь к табл. 8 .1 , видим, что вероятности этих групп совпадают с вероят ностями состояний исходного источника. На первом этапе раскрытия неопределенности вспомогательного источника устраняется неопре деленность исходного источника, записанная в виде (4 .I I ) . Коли чество неопределенности на первом этапе
п
Г а*
ы
На втором этапе,раскрывая неопределенность перЕій группы, мы должны выбрать одно из Я , равновероятных состояний. Неопре деленность .согласно (4.10)»
Ні =
Раскрывая неопределенность второй |
группы, следует выбрать |
одно |
||
из Кц |
равновероятных состояний. |
Неопределенность в |
этом |
случае |
Всего на |
втором этапе может быть |
П разных случаев, |
так |
как |
имеется гь групп, и может быть получено гь |
различных |
значений |
неопределенности в зависимости от того, в какой группе |
содержит |
|
ся состояние вспомогательного источника. |
|
|
Необходимо вычислить среднее значение |
неопределенности, |
|
18