Понятие энтропии. Количество информации как мера уменьшения неопределенности знаний Что такое неопределенность знания о результате

Случайные события могут быть описаны с использованием понятия «вероятность». Соотношения теории вероятностей позволяют найти (вычислить) вероятности как одиночных случайных событий, так и сложных опытов, объединяющих несколько независимых или связанных между собой событий. Однако описать случайные события можно не только в терминах вероятностей.

То, что событие случайно, означает отсутствие полной уверенности в его наступлении, что, в свою очередь, создает неопределенность в исходах опытов, связанных с данным событием. Безусловно, степень неопределенности различна для разных ситуаций.

Например, если опыт состоит в определении возраста случайно выбранного студента 1-го курса дневного отделения вуза, то с большой долей уверенности можно утверждать, что он окажется менее 30 лет; хотя по положению на дневном отделении могут обучаться лица в возрасте до 35 лет, чаще всего очно учатся выпускники школ ближайших нескольких выпусков. Гораздо меньшую определенность имеет аналогичный опыт, если проверяется, будет ли возраст произвольно выбранного студента меньше 18 лет. Для практики важно иметь возможность произвести численную оценку неопределенности разных опытов. Попробуем ввести такую количественную меру неопределенности.

Начнем с простой ситуации, когда опыт имеет %%n%% равновероятных исходов. Очевидно, что неопределенность каждого из них зависит от n, т.е.

Мера неопределенности является функцией числа исходов %%f(n)%%.

Можно указать некоторые свойства этой функции:

1. %%f(1) = 0%%, поскольку при %%n = 1%% исход опыта не является случайным и, следовательно, неопределенность отсутствует;
2. %%f(n)%% возрастает с ростом %%n%%, поскольку чем больше число возможных исходов, тем более затруднительным становится предсказание результата опыта.

* Для обозначения опытов со случайными исходами будем использовать греческие буквы (%%α%%, %%β%% и т.д.), а для обозначения отдельных исходов опытов (событий) - латинские заглавные (%%А%%, %%В%% и т.д.).

Для определения явного вида функции %%f(n)%% рассмотрим два независимых опыта %%α%% и %%β*%% с количествами равновероятных исходов, соответственно %%n_α%% и %%n_β%%. Пусть имеет место сложный опыт, который состоит в одновременном выполнении опытов α и β; число возможных его исходов равно %%nα \cdot nβ%%, причем, все они равновероятны. Очевидно, неопределенность исхода такого сложного опыта %%α ^ β%% будет больше неопределенности опыта %%α%%, поскольку к ней добавляется неопределенность %%β%%; мера неопределенности сложного опыта равна %%f(n_α \cdot n_β)%%. С другой стороны, меры неопределенности отдельных %%α%% и %%β%% составляют, соответственно, %%f(n_α)%% и %%f(n_β)%%. В первом случае (сложный опыт) проявляется общая (суммарная) неопределенность совместных событий, во втором - неопределенность каждого из событий в отдельности. Однако из независимости %%α%% и %%β%% следует, что в сложном опыте они никак не могут повлиять друг на друга и, в частности, %%α%% не может оказать воздействия на неопределенность %%β%%, и наоборот. Следовательно, мера суммарной неопределенности должна быть равна сумме мер неопределенности каждого из опытов, т.е. мера неопределенности аддитивна:

$$f(n_α \cdot n_β)=f(n_α)+f(n_β)~~~~~~(2.1)$$

Теперь задумаемся о том, каким может быть явный вид функции %%f(n)%%, чтобы он удовлетворял свойствам (1) и (2) и соотношению (2.1)? Легко увидеть, что такому набору свойств удовлетворяет функция %%log(n)%%, причем можно доказать, что она единственная из всех существующих классов функций. Таким образом:

За меру неопределенности опыта с n равновероятными исходами можно принять число %%log(n)%%.

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

$$log_b n=log_b а\cdot log_a n $$

переход к другому основанию состоит во введении одинакового для обеих частей выражения (2.1) постоянного множителя %%log_b а%%, что равносильно изменению масштаба (т.е. размера единицы) измерения неопределенности. Поскольку это так, имеется возможность выбрать удобное (из каких-то дополнительных соображений) основание логарифма. Таким удобным основанием оказывается 2, поскольку в этом случае за единицу измерения принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода, которые можно обозначить, например, ИСТИНА (True) и ЛОЖЬ (False) и использовать для анализа таких событий аппарат математической логики.

Единица измерения неопределенности при двух возможных равновероятных исходах опыта называется бит .

Название бит происходит от английского binary digit, что в дословном переводе означает «двоичный разряд» или «двоичная единица».

Таким образом, нами установлен явный вид функции, описывающей меру неопределенности опыта, имеющего %%n%% равновероятных исходов:

$$f(n)=log_2 n~~~~~~(2.2)$$

Эта величина получила название энтропия . В дальнейшем будем обозначать ее Н.

Вновь рассмотрим опыт с %%n%% равновероятными исходами. Поскольку каждый исход случаен, он вносит свой вклад в неопределенность всего опыта, но так как все %%n%% исходов равнозначны, разумно допустить, что и их неопределенности одинаковы. Из свойства аддитивности неопределенности, а также того, что согласно (2.2) общая неопределенность равна %%log_2 n%%, следует, что неопределенность, вносимая одним исходом составляет

$$\frac{1}{n}log_2 n = - \frac{1}{n}log_2 \frac{1}{n} = -p \cdot log_2 p $$

где %%р =\frac{1}{n}%% - вероятность любого из отдельных исходов.

Таким образом, неопределенность, вносимая каждым из равновероятных исходов, равна:

$$H=-p \cdot log_2 p~~~~~~~~~~~~(2.3)$$

Теперь попробуем обобщить формулу (2.3) на ситуацию, когда исходы опытов неравновероятны, например, %%p(A_1)%% и %%p(A_2)%%. Тогда:

$$H_1=-p(А_1) \cdot log_2 р(А_1)$$ $$H_2=-p(А_2) \cdot log_2 р(А_2)$$

$$H=H_1+H_2=-p(А_1) \cdot log_2 р(А_1)-p(А_2) \cdot log_2 р(А_2)$$

Обобщая это выражение на ситуацию, когда опыт %%α%% имеет %%n%% неравновероятных исходов %%А_1, А_2... А_n%%, получим:

$$H(α)=-\sum^{n}_{i=1} {p(А_i)}\cdot log_2 p(А_i)~~~~~~(2.4)$$

Введенная таким образом величина, как уже было сказано, называется энтропией опыта. Используя формулу для среднего значения дискретных случайных величин, можно записать:

$$H(α)\leqslant -log_2 p(A^α)$$

%%А^α%% - обозначает исходы, возможные в опыте α.

Энтропия является мерой неопределенности опыта, в котором проявляются случайные события, и равна средней неопределенности всех возможных его исходов.

Для практики формула (2.4) важна тем, что позволяет сравнить неопределенности различных опытов со случайными исходами.

Пример 2.1. Имеются два ящика, в каждом из которых по 12 шаров. В первом -3 белых, 3 черных и 6 красных; во втором - каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?

Согласно (2.4) находим энтропии обоих опытов:

%%Н_α = -\frac{3}{12}log_2 \frac{3}{12}-\frac{3}{12}log_2 \frac{3}{12}-\frac{6}{12}log_2 \frac{6}{12}=1,50%% бит

%%Н_β = -\frac{4}{12}log_2 \frac{4}{12}-\frac{4}{12}log_2 \frac{4}{12}-\frac{4}{12}log_2 \frac{4}{12}=1,58%% бит

%%Н_β > Н_α%%, т.е. неопределенность результата в опыте β выше и, следовательно, предсказать его можно с меньшей долей уверенности, чем результат α.

8 . Содержательный подход к измерению информации

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

Вспомним, что с «человеческой» точки зрения информация - это знания, которые мы получаем из внешнего мира. Количество информации, заключенное в сообщении, должно быть тем больше, чем больше оно пополняет наши знания.

Вы уже знаете, что за единицу измерения информации принимается 1 бит.

1 бит - минимальная единица измерения количества информации.

Проблема измерения информации исследована в теории информации, основатель которой - Клод Шеннон .

В теории информации для бита дается следующее определение:

Сообщение, уменьшающее неопределенность знания в два раза, несет 1 бит информации.

Что такое неопределенность знания, поясним на примерах.

Допустим, вы бросаете монету, загадывая, что выпадет: орел или решка. Есть всего два возможных результата бросания монеты. Причем ни один из этих результатов не имеет преимущества перед другим. В таком случае говорят, что они равновероятны .

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

Игральный же кубик с шестью гранями может с равной вероятностью упасть на любую из них. Значит, неопределенность знания о результате бросания кубика равна шести.

Еще пример: спортсмены-лыжники перед забегом путем жеребьевки определяют свои порядковые номера на старте. Допустим, что имеется 100 участников соревнований, тогда неопределенность знания спортсмена о своем номере до жеребьевки равна 100 .

Следовательно, можно сказать так:

Неопределенность знания о результате некоторого события (бросание монеты или игрального кубика, вытаскивание жребия и др.) - это количество возможных результатов.

Вернемся к примеру с монетой. После того как вы бросили монету и посмотрели на нее, вы получили зрительное сообщение, что выпал, например, орел. Определился один из двух возможных результатов. Неопределенность знания уменьшилась в два раза: было два варианта, остался один. Значит, узнав результат бросания монеты, вы получили 1 бит информации.

Сообщение об одном из двух равновероятных результатов некоторого события несет 1 бит информации.

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

Тогда количество информации i , содержащееся в сообщении о том, что произошло одно из N равновероятных событий, можно определить из формулы Хартли:

N =2 i .

Данная формула является показательным уравнением относительно неизвестного i . по основанию 2 .

Если N равно целой степени двойки (2,4,8,16 и т. д.), то такое уравнение можно решить «в уме».

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

Информация и знания. Человек получает информацию из окружающего мира с помощью органов чувств, анализирует ее и выявляет существенные закономерности с помощью мышления, хранит полученную информацию в памяти. Процесс систематического научного познания окружающего мира приводит к накоплению информации в форме знаний (фактов, научных теорий и так далее). Таким образом, с точки зрения процесса познания информация может рассматриваться как знания .

Процесс познания можно наглядно изобразить в виде расширяющегося круга знания (такой способ придумали еще древние греки). Вне этого круга лежит область незнания, а окружность является границей между знанием и незнанием. Парадокс состоит в том, что чем большим объемом знаний обладает человек (чем шире круг знаний), тем больше он ощущает недостаток знаний (тем больше граница нашего незнания. мерой которого в этой модели является длина окружности) - рис. 1.1.

Рис. 1.1 Знание и незнание

Так, объем знаний выпускника школы гораздо больше, чем объем знаний первоклассника, однако и граница его незнания существенно больше. Действительно, первоклассник ничего не знает о законах физики и поэтому не осознает недостаточности своих знаний, тогда как выпускник школы при подготовке к экзаменам по физике может обнаружить, что существуют физические законы, которые он не знает или не понимает.

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

Например, после сдачи экзамена по информатике вы мучаетесь неопределенностью, вы не знаете какую оценку получили. Наконец, экзаменационная комиссия объявляет результаты экзамена, и вы получаете сообщение, которое приносит полную определенность, теперь вы знаете свою оценку. Происходит переход от незнания к полному знанию, значит, сообщение экзаменационной комиссии содержит информацию.

Уменьшение неопределенности знаний. Подход к информации как мере уменьшения неопределенности знаний позволяет количественно измерять информацию, что чрезвычайно валено для информатики. Рассмотрим вопрос об определении количества информации более подробно на конкретных примерах.

Пусть у нас имеется монета, которую мы бросаем на ровную поверхность. С равной вероятностью произойдет одно из двух возможных событий - монета окажется в одном из двух положений: "орел" или "решка".

Можно говорить, что события равновероятны, если при возрастающем числе опытов количества выпадений "орла" и "решки" постепенно сближаются. Например, если мы бросим монету 10 раз, то "орел" может выпасть 7 раз, а решка - 3 раза, если бросим монету 100 раз, то "орел" может выпасть 60 раз, а "решка" - 40 раз, если бросим монету 1000 раз, то "орел" может выпасть 520 раз, а "решка" - 480 и так далее.

В итоге при очень большой серии опытов количества выпадений "орла" и "решки" практически сравняются.

Перед броском существует неопределенность наших знаний (возможны два события), и, как упадет монета, предсказать невозможно. После броска наступает полная определенность, так как мы видим (получаем зрительное сообщение), что монета в данный момент находится в определенном положении (например, "орел"). Это сообщение приводит к уменьшению неопределенности наших знаний в два раза, так как до броска мы имели два вероятных события, а после броска - только одно, то есть в два раза меньше (рис. 1.2).

Рис. 1.2 Возможные и произошедшее события

В окружающей действительности достаточно часто встречаются ситуации, когда может произойти некоторое количество равновероятных событий. Так, при бросании равносторонней четырехгранной пирамиды существуют 4 равновероятных события, а при бросании шестигранного игрального кубика - 6 равновероятных событий.

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

Единицы измерения количества информации. Для количественного выражения любой величины необходимо определить единицу измерения. Так, для измерения длины в качестве единицы выбран метр, для измерения массы - килограмм и так далее. Аналогично, для определения количества информации необходимо ввести единицу измерения.

За единицу количества информации принимается такое количество информации, которое содержит сообщение, уменьшающее неопределенность в два раза. Такая единица названа "бит" .

Если вернуться к опыту с бросанием монеты, то здесь неопределенность как раз уменьшается в два раза и, следовательно, полученное количество информации равно 1 биту.

Минимальной единицей измерения количества информации является бит, а следующей по величине единицей является байт, причем

1 байт = 2 3 бит = 8 бит

В информатике система образования кратных единиц измерения количества информации несколько отличается от принятых в большинстве наук. Традиционные метрические системы единиц, например Международная система единиц СИ, в качестве множителей кратных единиц используют коэффициент 10n, где п = 3, 6, 9 и так далее, что соответствует десятичным приставкам Кило (10 3), Мега (10 6), Гига (10 9) и так далее.

Компьютер оперирует числами не в десятичной, а в двоичной системе счисления, поэтому в кратных единицах измерения количества информации используется коэффициент 2 n .

Так, кратные байту единицы измерения количества информации вводятся следующим образом:

1 Кбайт = 2 10 байт = 1024 байт;
1 Мбайт = 2 10 Кбайт = 1024 Кбайт;
1 Гбайт = 2 10 Мбайт = 1024 Мбайт.

Количество возможных событий и количество информации. Существует формула, которая связывает между собой количество возможных событий N и количество информации I:

N=2 I

(2.1)

По этой формуле можно легко определить количество возможных событий, если известно количество информации. Например, если мы получили 4 бита информации, то количество возможных событий составляло:

Наоборот, для определения количества информации, если известно количество событий, необходимо решить показательное уравнение относительно /. Например, в игре "Крестики-нолики" на поле 8x8 перед первым ходом существует 64 возможных события (64 различных варианта расположения "крестика"), тогда уравнение принимает вид:

Так как 64 = 2 6 , то получим:

Таким образом, I = 6 битов, то есть количество информации, полученное вторым игроком после первого хода первого игрока, составляет 6 битов.

Вопросы для размышления

1. Приведите примеры уменьшения неопределенности знаний после получения информации о произошедшем событии.

2. В чем состоит неопределенность знаний в опыте по бросанию монеты?

3. Как зависит количество информации от количества возможных событий?

Задания

1.1. Какое количество информации получит второй игрок после первого хода первого игрока в игре в "Крестики-нолики" на поле размером 4x4?

1.2. Каково было количество возможных событий, если после реализации одного из них мы получили количество информации, равное 3 битам? 7 битам?

Основоположник теории информации Клод Шеннон определил информацию , как снятую неопределенность . Точнее сказать, получение информации - необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности – уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.

Представьте, что вы зашли в магазин и попросили продать вам жевательную резинку. Продавщица, у которой, скажем, 16 сортов жевательной резинки, находится в состоянии неопределенности. Она не может выполнить вашу просьбу без получения дополнительной информации. Если вы уточнили, скажем, - «Orbit », и из 16 первоначальных вариантов продавщица рассматривает теперь только 8, вы уменьшили ее неопределенность в два раза (забегая вперед, скажем, что уменьшение неопределенности вдвое соответствует получению 1 бита информации). Если вы, не мудрствуя лукаво, просто указали пальцем на витрине, - «вот эту!», то неопределенность была снята полностью. Опять же, забегая вперед, скажем, что этим жестом в данном примере вы сообщили продавщице 4 бита информации.

Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: {1/N , 1/N , … 1/N }.

Минимальная неопределенность равна 0 , т.е. эта ситуация полной определенности , означающая что выбор сделан, и вся необходимая информация получена. Распределение вероятностей для ситуации полной определенности выглядит так: {1, 0, …0} .

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия .

Энтропия (H ) – мера неопределенности, выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.

На рисунке 8. показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (p , (1-p )).

Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны ½, нулевое значение энтропии соответствует случаям (p 0 =0, p 1 =1) и (p 0 =1, p 1 =0).

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I – это количество информации, которое требуется для снятия неопределенности H . По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия) .

Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H .

При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. H t + I t = H .

По этой причине, формулы, которые будут представлены ниже для расчета энтропии H являются и формулами для расчета количества информации I , т.е. когда речь идет о полном снятии неопределенности , H в них может заменяться на I .

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

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

Для сравнения неопределённостей, рассмотрим следующие примеры или опыты a, b и g, содержащие неопределённости H(a), H(b) и H(g) соответственно:

1. Определить очередного чемпиона мира по шахматам (опыт a).

2. Определить номер лотерейного билета, на который выпадет наибольший выигрыш в предстоящем тираже лотереи (опыт b).

3. Определить следующего президента РФ (опыт g).

Очевидно, степень неопределённости каждого опыта отличается от двух других, причём скорее всего имеют место неравенства

H(b) > H(a) > H(g),

где H(a), H(b) и H(g) - количественные меры неопределённостей (или энтропии) опытов a, b и g соответственно. В частном случае, если для некоторого опыта d имеет место равенство H(d) = 0, то говорят, что опыт d достоверный, т.е. он не содержит неопределённости. Другими словами неоределённость опыта есть не что иное как недостача информации или отрицательная информация.

I. Формула Хартли. Пусть a - произвольный опыт с k равновероятными исходами А k

События А 1 А 2 . . . А k

Вероятности 1/ k 1/ k . . . 1/ k .

При k= 1 H(a) = 0, а при возрастании k H(a) также возрастает, т.е.

где f - некоторая функция от k. С другой стороны, если b независимый от a другой опыт с l равновероятными исходами В l , то для сложного опыта ab, состоящего в одновременном выполнении опытов a и b, естественно считать что степень неопределённости опыта ab равна сумме неопределённостей, характеризующих опыты a и b, т.е.

H(ab) = H(a) + H(b).

Таким образом, в качестве функции f можно выбрать логарифмическую функцию и считать, что

H(a) = log 2 k .

Это есть формула Хартли и она представляет собой меру неопределённости относительно опыта a, содержащимся в опыте a и имеющим два равновероятных исхода (например,"да" или "нет"). Другими словами, H(a) это то количество информации (за единицей измерения количества информации считается бит), с помощью которого неопределённость опыта a превращается в достоверность.

Так, например, для угадывания задуманного числа в диапазоне от 1 до 8 необходимо максимум 3 бит информации, т.е. необходимо задать три вопроса.

II. Формула Шеннона. Пусть a - произвольный опыт с к неравновероятными исходами А к:

События А 1 А 2 . . . А k

Вероятности Р(А 1) Р(А 2) . . . Р(А k) .

H(a) = - å P(A i)log 2 P(A i)

Есть мера неопределённости опыта a по Шеннону. В частности, при Р(А i) = 1/ k , из формулы Шеннона следует формула Хартли.

3.1.1. Доказать, что H(ab) = H(a) + H(b).

3.1.2. Сколько вопросов необходимо задать студентам академической группы преподавателю, чтобы определить старосту этой группы (ответы на вопросы преподавателя могут быть либо "да" либо "нет").

3.1.3. Рассмотреть задачу 3.1.2. в случае одного вопроса.

3.1.4. Пусть х- элемент множества М мощности m. Какое количество

информации необходимо для определения элемента х?

3.1.5. Пусть х 1 и х 2 - два произвольных элемента множеств М 1 и М 2 мощностей m 1 и m 2 соответственно. Какое количество информации необходимо для одновременного определения элементов х 1 и х 2 ?

3.1.6. Пусть имеется 27 золотых монет, из которых одна фальшивая (легче настоящих), и весы с чашками. Сколько взвешиваний необходимо произвести, чтобы определить фальшивую монету?

3.1.7. Доказать, что любого опыта a H(a) ³ 0, причём H(a) = 0 тогда и только тогда, когда одна из вероятностей равна 1, а остальные равны 0.

3.1.8. Доказать, что H(a) ≤ log 2 k , где k - число исходов опыта a , причём равенство достигается лишь в случае, когда исходы равновероятны.

3.1.9. Какими свойствами обладает H(a) , если a имеет два исхода?

УСЛОВНАЯ НЕОПРЕДЕЛЁННОСТЬ.

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

Пусть a и b - два произвольных опыта с k и l исходами А k , В l соответственно. Тогда если a и b независимы, то

H(ab) = H(a) + H(b) ,

а если же a и b зависимы, то

H(ab) = H(a) + H a (b) ,

где H a (b) - условная неопределённость опыта b при условии выполнения опыта a и определяется равенством k

H a (b) = å P(A i)H A i (b) .

Здесь H A i (b) - условная неопределённость опыта b при условии исхода A i и определяется формулой: l

H A i (b) = - å P A i (B j) log 2 P A i (B j) , i = 1 , k .

Очевидно, если a и b независимы, то H a (b) = H(b) , и H a (b) ≤ H(b) , если a и b зависимы.

Имеет место также равенство

Рассмотрим разность

I (a , b) = H(b) - H a (b) ,

которая указывает, насколько исход опыта a уменьшает неопределённость опыта b. Число I (a , b) называется количеством информации относительно опыта b, содержащимся в опыте a.

В частности, при a =b имеем I (a , a) = 0, что можно трактовать как количество информации об опыте a, содержащимся в самом себе. Если же a и b независимы, то

т.е. в целом

I (a , b) ≥ 0 ,

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

I (a , b) = I (b, a) ,

то I (a , b) можно назвать также взаимной информацией двух опытов a и b

H(ab) = H(a) + H a (b) ,

I (a , b) = H(a) + H(b) - H(ab) ,

следовательно, k l

I (a , b) = Σ Σ P(A i B j) log 2 P(A i B j) /(P(A i) P(B j)) .

Таким образом, мы получили окончательную формулу относительно количества информации I (a , b).

3.2.1. Доказать, что если a и b произвольные опыты, то;

а) H(ab) = H(a) + H a (b) ;

б) H(ab) ≤ H(a) + H(b) ;

в) 0 ≤ H a (b) ≤ H(b) ;

г) I (a , b) = I (b, a) ;

д) I (a , b) ≤ H(a) ;

3.2.2. Вывести формулу относительно I (a , b) .

3.2.3. Пусть опыт b состоит в извлечении одного шара из урны, содержащий m чёрных и n белых шаров, опыт a k - в предварительном извлечении из той же урны (без возвращения обратно) k шаров. Чему равна неопределённость опыта b и информация об опыте, содержащаяся в опытах a 6,

3.2.4. Пусть из партий в n деталей, изготовленных на конвейере, для выборочного контроля изъяты m деталей. Обозначим через a процент брака всей партии, а через b - процент брака в выборке. Определить I (a , b).

3.2.5. (О городах лжецов и честных людей). Пусть известно, что жители некоторого города А всегда говорят правду, а жители соседнего города Б всегда обманывают. Наблюдатель Н знает, что он находится в одном из этих двух городов, но не знает, в каком именно. Путём опроса встречного ему требуется определить, в каком городе он находится, или в каком городе живёт его собеседник (жители А могут заходить в Б и обратно), или то и другое вместе. Спрашивается, каково наименьшее число вопросов, которые должен задать Н (на все вопросы Н встречный отвечает лишь "да" или "нет").

ПЕРЕДАЧА ИНФОРМАЦИИ

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

В частности, если х и х" - переданное и искажённое сообщения соответственно, то определим количество информации I(x" , x) - выхода канала относительно его входа как:

I(x" , x) = Н(х) - Н х " (х) ,

где Н(х), Н(х") энтропии сообщений х и х" соответственно.

Значение

C = max I(x" , x)

называется пропускной способностью канала, т.е. она характеризует максимальное количество информации, которое может быть передано через канал за один такт времени. А в самом деле, пропускная способность канала является верхней границей скорости R надёжной передачи информации, причём к этой границе можно подойти сколь угодно близко.

Теорема 1 .(о кодировании). Для любого числа R, меньшего пропускной способности С канала, и любого e>0 существует способ блоковой передачи со скоростью, не меньшей R, и вероятностью ошибки Р(е), не превосходящей e.

В то же время всякий способ передачи информации со скоростью, большей пропускной способности, приводит к тому, что вероятность ошибки будет больше некоторой фиксированной величины.

Теорема 2. (обращение теоремы кодирования). Если величина R превосходит пропускную способность канала С, то найдётся константа e 0 (зависящая от R и C) такая, что при любом способе блоковой передачи информации со скоростью, не меньшей R, выполнено неравенство

Р(е)³ e 0 .

Обозначим через I(a i) количество информации, содержащееся в символе a i и определим его как:

I(a i) = - log 2 P(a i) ,

где P(a i) - вероятность появления символа a i в самом тексте сообщения.

Если же текст сообщений записан на некотором естественном языке

(а его можно рассматривать как естественный код, обнаруживающий и исправляющий ошибки), то каждая буква этого языка имеет свою частоту встречаемости в тексте (так, например, в русском языке буквы о, е, ё гораздо чаще встречаются (Р о = 0.09 , Р е,ё = 0.07) , чем буквы э и ф (Р э = 0.003, Р ф = 0.002)) и поэтому неопределённость H L естественного языка определяется как m

H L = - å P(a i) log 2 P(a i) ,

а избыточность С L соответственно как

С L = 1 - H L / log 2 m ,

где m - количество букв естественного языка.

Очевидно, что 0 ≤ С L ≤ 1, следовательно, при оптимальном кодировании часть текста можно без ущерба для понимания опустить.

Так, например, С L = 0.5 для литературного английского языка, а избыточность других языков несколько меньше.

Отметим, что избыточность языка не является недостатком, а скорее преимуществом, так как, например, если С L = 50% , то это означает что по половине искажённого текста можно восстановить весь текст.

3.3.1. Определить пропускную способность ДСК.

3.3.2. Найти I(x" , x) для ДСК.

3.3.3. Определить избыточность и неопределённость русского языка.

3.3.4. Определить количество информации букв английского языка.

3.3.5. Доказать теоремы Шеннона для блочных кодов.

3.3.6. Восстановить текст:

а) С??зд ц?ли??м? п?лн???ью од??ри? м??опр??т?я ц? пар??? ?о??рьб? ? ?а?о?ом;

б) ?об?ка?ае? ка?ав?н???ает.

Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

1. Алфавит дискретных устройств. Конечные поля. . . . . . . . . . 4

1.1. Простое поле Галуа GF(P) . . . . . . . . . . . . . . . . . . . . . 4

1.2. Составное поле Галуа GF(P n) . . . . . . . . . . . . . . . . . . . 6

2. Кодирование информации. . . . . . . . . . . . . . . . . . . . . . .9

2.1. Основные понятия. Примеры кодов. . . . . . . . . . . . . . . 9

2.2. Линейные коды. Способы их задания. . . . . . . . . . . . 15

2.3. Свойства линейного кода. Коды Хэмминга. . . . . . . . . . 22

2.4. Циклические коды. . . . . . . . . . . . . . . . . . . . . . . . 27

2.5. Коды БЧХ, исправляющие две ошибки. . . . . . . . . . . . .32

2.6. Нелинейные коды. Коды Адамара. . . . . . . . . . . . . . . .36

2.7. Границы мощности кодов. . . . . . . . . . . . . . . . . . . . 40

3. Информация и неопределённость. . . . . . . . . . . . . . . . . . 44

3.1. Количественная мера неопределённости. . . . . . . . . . . .45

3.2. Условная неопределённость. Количество информации. . . . .47

3.3. Передача информации. . . . . . . . . . . . . . . . . . . . . .50

Осипян Валерий Осипович

ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕДАЧИ ИНФОРМАЦИИ

Редактор Т.В.Шилова

Технический редактор И.А. Зиновская

Корректор М.Е. Шулепова

ЛР № 200378 от 22.01.97

Подписано в печать 29.01.97.

Формат 60´84 1 /16. Бумага тип. № 3.

Печать трафаретная. Усл. печ. л. 2,75.

Уч.-изд. л. 2,7. Тираж 300 экз. Заказ №

Кубанский государственный университет