книги из ГПНТБ / Толстоусов, Г. Н. Прикладная теория информации учеб. пособие
.pdfх іъ). В момент времени bz источник переходит в со стояние X? и т .д .
Состояние источника в любой момент времени является случай ным. Моменты времени, в которые происходит смена состояний, тан- хе могут быть случайными. Зафиксированная последовательность со стояний одного источника называется случайной последовательное стью. Пример случайной последовательности показан на рис“; 7;І;На неограниченном интервале времени число различных случайных пос ледовательностей бесконечно.
Для описания случайной последовательности необходимо энать законы распределения состояний для каждого момента времени и за кон распределения моментов смены состояний.
Для вопросов, рассматриваемых в данном курсе, достаточно описывать процесс смены состояний с помощью средней частоты сме ны состояний или математического ожидания числа смен состояний в
единицу времени |
А . |
|
|
|
|
|
Для статистического описания сами-*- состояний примем следую |
||||||
щий спосс1. Состояние |
системы после |
£ |
-го переключения есть |
|||
случайная величина |
X |
, |
которая может |
принять одно из гь воз |
||
можных состояний |
( |
X |
|
эСц, |
) . |
Необходимо знать вероят |
ности появления значений |
( XitXZr... х п ) для каждого момента |
|||||
смены состояний. Пусть у источника эти вероятности не зависят от чередования состояний до рассматриваемого момента времени, т .ѳ . состояния источника независимы. Тогда случайная величина X е характеризуется априорными вероятностями р? , где
29
Для стационарного источника вероятности состояний от време ни нѳ еавиояі. Поэтому для каждого момента переключений (для лю
бого |
I ) |
можно записать вероятности состояний в виде табл.7 Л . |
|||
|
|
Таблица |
7Л |
Если состояния источника |
|
|
|
зависимые, то случайную величину |
|||
Хі, |
|
Ял. |
• • • |
|
|
Pi |
Р* |
Xенеобходимо описывать с по |
|||
Pi |
Рл, |
• • • |
мощью условных вероятностей |
||
|
|
|
|
|
р(ХеІХ£ч,Х*-,л...,Х°). в |
случае, когда состояние источни ка зависит от конечного числа предыдущих состояний, условные ве роятности имеют конечную размерность. У марковских источников каждое соотоянне зависит только от предыдущего, и для описания источника необходимы следующие условные вероятности:
М
Боли источники стационарные, то их условные вероятности не
аавиоят от |
значения |
^ |
и для описания марковских источников |
необходимо |
знать /г |
априорных вероятностей состояния Х ° и пх |
|
условных вероятностей последующих состоянийX \ X ? ...
В дальнейшем будут рассматриваться эргодичѳскиѳ источники. Эргодичѳскиѳ источники отационарны, зависимость между состояния ми у них наблюдается на ограниченном интервале. Кроме того, для эргодических источников понятие вероятности, определенное для партии однородных источников и для случайной последовательности, совпадают.
При вычислении энтропии случайной последовательности эрго-
дичѳокого источника энтропия первого состояния X |
|
н іх ° )^ - 1 р .е ^ р . |
« .и |
Энтропия второго состояния X * определяется в общем случае с по мощью условных вероятностей и будет равна следующей условной энт ропии:
*(х7х°)=-£ £ Р,Р(х-/х/)&>$р(х1/х/)' |
из) |
я |
|
80
Неопределенность третьего состояние X * определяется ус ловной энтропией Н(Х*'/Х°Х ) и т .д . Энтропия конечной случай ной последовательности
Н(Х°Х\ .. Х*)=Н(Х°)+Н(Х'/Х°) + |
|
+н(х1(х°х< )+ . . x H ^ / x ° x f. . . x K-,)_ |
(W |
Следует иметь в виду, что |
|
н (х °)> н (х '/х°)? н (х Ч х 4х *)... |
|
Однако в силу конечного интервала зависимости, начиная о некоторого состояния, уменьшение энтропии прекращается и в силу стационарности она остается постоянной;
Энтропия случайной последовательности максимальна, когда состояния источника независимы. Тогда
н ( х Ѵ . . . |
Н ( х Ь ...+ Ш Х ‘). |
Но в силу стационарности имеем
Н(Х°Х<...Хк)=к-Н (Х°). ' &5)
Кроме того, вторым условием максимума является равновероятное распределение состояний. При этом получим
ггиххН(Х°Х\..Хк)=К- &xjrt. (**)
Для неограниченной олучайной последовательности энтропия бесконечна. Поэтому часто рассматривают среднюю величину энтро пии, приходящуюся на одно состояние:
Ѵ * |
f t» ; |
В данном курсе будет использована также величина
Н*Л-Н,(Х)9 |
(1(8) |
81
которая называется скоростью изменения энтропии и показывает,ка кое количество информации в единицу времени необходимо передать от источника.
§Ѳ. Передача информации при отсутствии помех
Впредыдущих разделах было введено понятие неопределенно
сти источника информации и получены выражения для энтропии ис точника Н как меры неопределенности. Допустим, что нам удалось
получить сообщение от источника, обладающего некоторой неопре деленностью состояний, причем принятое сообщение точно указыва ет, в каком состоянии находится источник. Область возможных со стояний сузилась до одного состояния, того, в котором действи тельно находится источник. Энтропия источника после приема со
общения равна нулю. Будем считать в этом случае, что количество информации в сообщении У(Х) равно энтропии:
Ѵ (Х )-Н (Х ). |
(at) |
Рассмотрим процесс более подробно. |
Источник информации ме |
няет свое состояние. Пусть о каждом состоянии мы получаем сооб щение, которое на данный момент времени, до следующей смены со стояния, полностью раскрывает неопределенность источника. Одна ко количество информации в разных сообщениях может быть различ
ным, |
Рассмотрим |
источник |
|
со свойствами, указанными в табл. 8 .1 . |
||
|
|
Таблица |
8.1 |
|
|
Очевидно предположить, что в сооб |
Хі |
X, |
X*. |
щении "источник находится в состоянии |
|||
|
Хі" содержится меньше информации,чем |
|||||
|
Pi |
0,999 |
0,001 |
в |
сообщении о состоянии Xz , Мы, не |
|
|
|
|
|
получая сообщений, почти всегда будем |
||
|
|
|
|
правы, утверждая, что источник находит- |
||
ся в |
состоянии |
Xf . Сообщений об этом состоянии нам почти не |
||||
нужно. Сообщение о состоянии |
Хх несет большую информацию, так |
|||||
как гарантирует нас от ощибки, указывая на те редкие случаи, |
||||||
когда |
наступает |
состояние |
x z |
. Опираясь на такое рассуждение, |
||
предположим, что количество информации о конкретном сообщении
Хі~ частное количество информации У(Хі)- тем |
больше, чем мень |
ше вероятность соответствующего состояния р- |
. Предположим,что |
вто частное количество информации |
|
32 |
3(х;)-= -& урі |
иг) |
|
|
Тогда средноѳ количество информации в одном сообщении равно математическому ожиданию частных количеств информации:
УХ)=м[-& уР(Х)]=-£р. бо$Рі . |
І8.Ъ) |
Сравнивая (8.3) с (8.1) и 1,4. Its;, видим, что количество |
инфор |
мации в одном сообщении равно энтропии. Следовательно, предпо ложение (9.2) справедливо.
Так как О -Рі - •У , то и среднее, и частное количества
информации всегда |
вещественны |
и неотрицательны. Единицы измере |
||
ния информации те |
же, что и для энтропии. Рассмотрим следующий |
|||
пример, имеется 64 элемента. |
Известно, что один из них неиспра |
|||
вен, причем вероятности того, |
что |
неисправен любой |
элемень,оди |
|
наковы. Тогда каждый элемент |
есть |
источник с двумя |
состояниями: |
|
X, - исправен, |
Xz - неисправен. Вероятности состояний указа |
||||
ны в |
табл. |
8 .2 . |
Частное количество информации в сообщении, что |
||
проверяемый элемент исправее, равно |
g* |
||||
Таблица |
8.2 |
. , . |
|||
|
|
|
|
jY=o,ozb(Tur. |
|
Хі |
£± |
У |
Частное количество |
информации в сообщении, |
|
Рі |
что проверяемый элемент неисправен, равно |
||||
64 |
|
||||
|
|
|
У(хл)=- |
71 |
|
Количество информации в- сообщении о результате проверки одного элемента равно
|
|
У(Х) Н(Х)~ |
gtj &Х]ßif |
6tf |
ßif-O'O^d'u.r. |
||
Таблица |
8 .3 |
Процесс передачи информации от ис |
|||||
|
|
|
|||||
|
|
я*. |
точника с двумя возможными состояниями |
||||
Рі |
р |
(табл. |
8 .3) можно |
представить следующим |
|||
*-Р |
образом. |
Задается |
вопрос, |
"находится ли |
|||
|
|
|
источник |
в состоянии |
?" На этот воп |
||
|
|
|
рос возможны два |
ответа: |
"да" и "нет". |
||
Вопросом монет быть измерение, проверка и т .д . Ответом тогда является результат измерения или проверки. Ответ несет нѳкото-
33
ров количество информации. Максимальное количество информации в ответе равно I биту в том случае, когда оба ответа равновероят ны, т .е . равновероятны состояния источника.
Рассмотрим источник с П возможными состояниями и энтропи ей Н(Х) . Объединим состояния источника в две группы и зада дим вопрос: "находится ли состояние источника в І-й группе?" На этом этапе источник может быть описан табл. 8.3, где р - веро ятность І-й группы состояний. Поэтому возможны только два отве та :"да" и "нет". Эти ответы несут некоторое количество информа
ции. Максимально возможное количество информации |
в ответе |
равно |
I биту и достигается, когда ответы равновероятны. |
Отсюда |
следу |
ет принцип образования групп. |
|
|
Полученный ответ не уничтожает неопределенности полностью. Он только указывает группу, в которой находится состояние источ ника. Необходимо эту группу разбить на две равновероятные под группы и поставить вопрос: "находится ли состояние в первой под
группе?", |
чтобы ответы |
"да" или |
"нет" несли информацию, равную |
I биту. |
|
|
|
После |
двух ответов |
получено |
два бита информации. Для пол - |
ного устранения неопределенности необходимо получить количество информации, равное энтропии источника Н(Х) бит. Следователь
но, |
энтропия определяет наименьшее количество вопросов, с |
помо |
||
щью |
которых можно полностью определить состояние системы. |
Эти |
||
вопросы должны быть поставлены так, |
чтобы ответы |
"да" или |
"нет" |
|
были |
равновероятны. |
|
|
|
|
Пример: Имеется система из трех |
элементов; |
известно, |
что |
неисправен один из элементов. Вероятности неисправности каждого
элемента указаны на рис. |
8 .1 . Энтропия истѳмы |
|
||
н= ~ А л Ң Р с=~ |
t y - T - z - T |
|
|
|
|
Вопросы будут заключать |
|||
|
ся в проверке элементов или |
|||
|
групп элементов. Следователь |
|||
|
но, минимальное среднее число, |
|||
Рис. 8.1 |
проверок |
равно |
1,5 . Разобьем |
|
элементы |
на дье |
равновероятны* |
||
|
||||
ЗФ
группы. В первую включим І-й элемент, во вторую - 2-й и 3-й эле
менты. |
Сначала проверяем І-й элемент. Если он неисправен (ответ |
|
"да")* |
проверка системы заканчивается. Если он исправен |
( ответ |
"нет"), |
то проверка продолжается и неисправный элемент |
необхо |
димо искать во второй группе. В этом случае проверяем второй элемент. Ответ "да" говорит о неисправности 2-го элемента. От вет "нет" - о неисправности 3-го элемента.
Подсчитаем среднее количество проверок. С вероятностью не исправности первого элемента, равной 1/2, для поиска неисправно сти элемента необходима одна проверка. С вероятностью неисправ ности 2-го или 3-го элементов, равной 1/2, необходимо две про - верки. Тогда среднее количество проверок Кср равно
Кф= 1/2 . I + 1/2 . 2 = 1,5 проверки.
Заметим, что в случае большого числа элементов группы не обходимо было бы делить на подгруппы, подгруппы на более мелкие подгруппы и т .д . до определения неисправного элемента.
Если состояния источника информации нельзя разделить на равновероятные группы, количество информации в одном ответе бу дет меньше I бита и количество задаваемых вопросов будет больше энтропии.
Возможны случаи, когда на поставленный вопрос возможный ответов. Тогда минимальное среднее количество вопросов будет равно энтропии, системы, вычисленной в такой системе единиц,ког да основание логарифмов равно â . Задавая очередной вопрос, необходимо состояние системы делить на б равновероятных групп.
Известна задача о девяти шарах, среди которых находится один шар отличающийся только тем, что он тяжелее. Имеются весы с двумя чашками Необходимо найти минимальное число взвешиваний для определения тяжелого шара. На один вопрос (одно взвешивание) возможно три ответа: "тяжелый шар на правой чашке", " . . . на ле вой чашке", " . . . не на весах” (если весы находятся в равнове сии).
Вычислим энтропию системы при основании логарифмов, равном трем. Система имеет девять равновероятных состояний, поэтому имеем
Н - foXjs 9 - 2 .
35
Следовательно, минимальное число взвешиваний равно двум. Делим состояния на три равновероятные группы: по три шара
кладем на каждую чашку весов, три шара оставляем. Взвешивание указывает, в какой группе находится тяжелый шар. По одному шару из этой группы кладем на чашки, третий шар оставляем. Второе взвешивание определяет тяжелый шар.
§ 9 . Кодирование равновероятных сообщений
Рассматривается дискретный источник информации с п рав новероятными состояниями. Для передачи сообщений необходим пе редатчик, канал связи и приемник. По каналу связи передаются сигналы пѳродатчика. Пусть передатчик имеет ггь различных сиг налов. Эти сигналы могут различаться по уровню (глубине модуля
ции), по длительности (длительности модуляции) |
или по |
каким-ли |
|
бо иным признакам, различаемым приемником. |
Если |
т |
, то |
каждому сообщению ставится в соответствие свой, отличный от |
|||
других, сигнал передатчика. Если таблица |
-ответствия |
известна |
|
приемнику и помехи отсутствуют, по принятому сигналу восстанав
ливается переданное сообщение. |
Сигналов передатчика мень |
В большинстве случаев |
ше, чем сообщений источника. Тогда необходимо образовывать ком бинации сигналов передатчика. Комбинации должны отличаться друг от друга входящими в них сигналами и порядком их расположения.
Ясно, что количество комбинаций, называемых кодовыми комбинаци ями, будет больше, чем сигналов. Если число кодовых комбинаций равно числу сообщений, то каждому сообщению ставится в соответ
ствие |
одна, отличная от других, кодовая |
«■омбинация, которая и |
||||||
передается |
по линии связи при |
появлении |
данного |
сообщения. |
||||
|
В простейших случаях составление кодовых комбинаций сводит |
|||||||
ся к |
нумерации |
сообщений в |
системе |
счисления с основанием пъ |
||||
(двоичной, троичной, десятичной и т . д . ). Разрядность кодовых |
||||||||
комбинаций |
к |
(количество |
сигналов, включаемых в одну комбина |
|||||
цию) |
выбирается |
из условия, |
чтобы |
количество комбинаций Q-гтъ* |
||||
было |
не меньше |
числа сообщений |
гъ |
. Тогда п- |
т к , откуда |
|||
(Ѳ і)
36
Чей меньше сигналов передатчика пь , тем проще передатчик, но длиннее кодовая комбинация К и больше времени уходит на пере дачу.
Первая задача кодирования заключается в составлении таких кодовых комбинаций, которые могут быть декодированы. Приемник должен по принятым сигналам восстановить переданное сообщение. Для этого необходимо выполнение следующих условий:
1. Каждое сообщение должно кодироваться своей, отличной от всех других, кодовой комбинацией. Это выполняется, ѳ сл и ^ ^ л ь .
2. При последовательном приеме кодовых комбинаций должен быть введен признак, по которому можно различить, где кончается одна кодовая комбинация и начинается следующая.
Признаком может быть одинаковое число сигналов в каждой кодовой комбинации. Такие комбинации называются равномерными и могут быть составлены следующим образом. Состояния источника нумеруются в принятой системе счисления. Например,
0; I; 10; II; 100; ІОІ; ІЮ; III.
Затем полученные номера дополняются нулями до образования равномерных комбинаций:
000; 001; 010; ОН; 100; ІОІ; ІЮ; HIV
Признаком, определяющим начало кодовой комбинации, может быть специальный разделительный сигнал, стоящий в конце или в начале каждой кодовой комбинации. Сами комбинации при этом могут быть неравномерными. Тогда этот сигнал в самих комбинациях не должен присутствовать. Примером разделительных знаков являются паузы в три единицы времени (промежуток между буквами) и в шесть единиц времени (промежуток между словами), используемые в
коде Морзе. Очевидно, что использование при передаче разделитель ных знаков, не несущих информации, неэффективно.
Возможно использование неравномерного кода без разделитель ных знаков. При этом никакая кодовая комбинация не должна быть началом другой, более длинной комбинации. Например, использова
ние комбинации |
10 и |
ІОІ |
недопустимо. Один из |
способов построе |
||
ния неравномерного |
кода |
показан на |
рис. |
9 .1 . |
Из каждой вершины |
|
так называемого |
кодового дереза' |
вниз |
возможны два пути: впра |
|||
во и влево. На пути |
влево к предыдущей комбинации добавляется О, |
|||||
на пути вправо - I . |
Если испоь^зуется какая-то комбинация, то |
|||||
остальные, лежащие |
ш., пути к пей от исходной |
вершины Л, квляют- |
||||
37
си запретенньши, так как по принципу построения кода будут яв ляться её началом. Например, если используется комбинация 1000, то запрещенными комбинациями будут 100,10 и I . На рис. 9.1 для примера подчеркнуты 10 разрешенных комбинаций неравномерного кода.
Рис. 9.1
Вторая задача кодирования заключается в использовании ко да минимальной длины, так как длина кодовой комбинации - это время, эатраченноѳ на передачу сообщения. Минимальная длина при использовании равномерного кода определяется соотношением (9 .1 ). Равенство выполняется в случае, когда правая часть (9.1) - це лое число. В противном случае, разрядность кодовой комбинации
К равна наименьшему целому числу, удовлетворяющему неравен ству (9 .1 ). При этом возникает избыточность, сигналы передатчи ка несут меньшее количество информации. Количество информации в каждом сообщении источника при п равновероятных состояниях
УX - іо^гь.
Каждый сигнал передатчика будет нести максимальное количе ство информации
Уг = & у т ,
если все т> сигналов будут равновероятны. Следовательно, чтобы передать информацию, содержащуюся в одном сообщении, необходи мо
58