Формулы хартли и шеннона реферат

Обновлено: 04.05.2024

В. С. Симанков, Е. В. Луценко

Глава 4: Теория информации и ее ключевые понятия

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

В основе всей теории информации лежит открытие, сделанное Р. Хартли в 1928 году, и состоящее в том, что информация допускает количественную оценку [374]. Завершенный и полный вид этой теории придал в 1948 году К. Шеннон [390]. Большой вклад в дальнейшее развитие и обобщение теории информации внесли отечественные ученые А.Н. Колмогоров, А.А. Харкевич, Р.Л. Стратанович [373]. Недавно германские исследователи советских архивов сообщили о том, что теория, известная сегодня как теория Шеннона, была создана А.Н.Колмогоровым еще в 1938 году, но была засекречена, так как использовалась в военных разработках.

Подход Р. Хартли

Подход Р. Хартли основан на весьма фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

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

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

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

Рассмотрим множество, состоящее из чисел в двоичной системе счисления длиной I двоичных разрядов. При этом каждый из разрядов может принимать значения только 0 и 1 (табл. 4.1).

Таблица 4.1 — К выводу формулы количества информации по Р.Хартли

Количество двоичных разрядов (i) Количество состояний, которое можно пронумеровать i-разрядными двоичными числами (N) Основание системы счисления
10 16 2
1 2 0
1		 0
1		 0
1
2 4 0
1
2
3		 0
1
2
3		 00
01
10
11
3 8 0
1
2
3
4
5
6
7		 0
1
2
3
4
5
6
7		 000
001
010
011
100
101
110
111
4 16 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15		 0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F		 0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
. .
i 2 i

Очевидно, количество этих чисел (элементов) в множестве равно:

Рассмотрим процесс выбора чисел из рассмотренного множества. До выбора вероятность выбрать любое число одинакова. Существует объективная неопределенность в вопросе о том, какое число будет выбрано. Эта неопределенность тем больше, чем больше N — количество чисел в множестве, а чисел тем больше — чем больше разрядность i этих чисел.

Примем, что выбор одного числа дает нам следующее количество информации:

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

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

При увеличении длины числа в два раза количество информации в нем также должно возрасти в два раза, несмотря на то, что количество чисел в множестве возрастает при этом по показательному закону (в квадрате, если числа двоичные), т.е. если

Это невозможно, если количество информации выражается линейной функцией от количества элементов в множестве. Но известна функция, обладающая именно таким свойством: это Log:

Это второе требование называется требованием аддитивности.

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

Подход К. Шеннона

Пусть существует некоторое конечное множество событий (состояний системы): X = 1, x2, . xN>, которые могут наступать с вероятностями: p(xi), соответственно, причем множество вероятностей удовлетворяет естественному условию нормировки:

Исходное множество событий характеризуется некоторой неопределенностью, т.е. энтропией Хартли, зависящей, как мы видели выше, только от мощности множества. Но Шеннон обобщает это понятие, учитывая, что различные события в общем случае не равновероятны. Например, неопределенность системы событий: , значительно выше, чем неопределенность событий: , так как в первом случае варианты равновероятны, а во втором случае вероятности вариантов сильно отличаются:

H(X) = -∑p(xi)⋅Log2(p(xi)) (4.1)

Если измерять количество информации изменением степени неопределенности, то шенноновское количество информации численно совпадает с энтропией исходного множества:

I(X) = -∑p(xi)⋅Log2(p(xi)) (4.2)

Связь формул К. Шеннона И Р. Хартли

Следуя [391], приведем вывод выражения Шеннона (4.2) непосредственно из выражения Хартли для количества информации: I = Log2(N).

Пусть события исходного множества мощности N равновероятны:

тогда учитывая, что

Log(1/N) = Log(1)⋅Log(N) = Log(N),
∑1/N = 1

непосредственно из формулы Хартли получаем

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

Сравнение подходов Р. Хартли и К. Шеннона

В теории Шеннона существенным образом используется статистика, причем предполагается, что случайные события (состояния системы) распределены по нормальному закону.

Таким образом, различие между подходами Хартли и Шеннона к построению теории информации соответствует различию между непараметрическими и параметрическими методами в статистике.

Если говорить более конкретно, то очевидно, что мера Шеннона асимптотически переходит в меру Хартли при условии, что вероятности всех событий (состояний) равны.

В статистике доказано [273, 391] фундаментальное свойство энтропии случайного процесса, состоящее в том, что при условии нормальности распределения и достаточно больших выборках все множество событий можно разделить на две основные группы:

  • высоковероятные события (считающиеся заслуживающими изучения);
  • маловероятные события (считаются не заслуживающими особого внимания).

Формула Хартли: I = log2N или N = 2 i

Легко заметить, что если вероятности p1, . pN равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit — binary digit — двоичная цифра).

Бит — слишком мелкая единица измерения. На практике чаще применяется более крупная единица — байт, равная восьми битам. Именно восемь битов требуется для того, чтобы закодировать любой из 256 символов алфавита клавиатуры компьютера (256=2 8 ).

Широко используются также ещё более крупные производные единицы информации:

1 Килобайт (Кбайт) = 1024 байт = 210 байт,

1 Мегабайт (Мбайт) = 1024 Кбайт = 220 байт,

1 Гигабайт (Гбайт) = 1024 Мбайт = 230 байт.

В последнее время в связи с увеличением объёмов обрабатываемой информации входят в употребление такие производные единицы, как:

1 Терабайт (Тбайт) = 1024 Гбайт = 240 байт,

1 Петабайт (Пбайт) = 1024 Тбайт = 250 байт.

При содержательном подходе возможна качественная оценка информации: полезная, безразличная, важная, вредная, … Одну и туже информацию разные люди могут оценить по-разному.

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

В компьютере информация представлена в двоичном коде или на машинном языке, алфавит которого состоит из двух цифр (0 и 1). Эти цифры можно рассматривать как два равновероятных состояния. При записи одного двоичного разряда реализуется выбор одного из двух возможных состояний (одной из двух цифр) и, следовательно, один двоичный разряд несет количество информации в 1 бит. Два двоичных разряда несут информацию 2 бита, три разряда – 3 бита и т.д.

В общем случае количество различных двоичных чисел можно определить по формуле

где I – количество информации;

N – количество возможных событий (равновероятных). ;

В математике существует функция, с помощью которой решается показательное уравнение, эта функция называется логарифмом. Решение такого уравнения имеет вид:

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

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

где I – количество информации;

N – количество возможных событий;

Pi – вероятность отдельных событий.

Пример 3.4

Поскольку вытаскивание любого из 32 шаров равновероятно, то количество информации об одном выпавшем номере находится из уравнения: 2 I =32.

Но 32=2 5 . Следовательно, I=5 бит. Очевидно, ответ не зависит от того, какой именно выпал номер.

Пример 3.5

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

Будем рассматривать 12 месяцев как 12 возможных событий. Если спрашивать о конкретном месяце рождения, то, возможно, придется задать 11 вопросов (если на 11 первых вопросов был получен отрицательный ответ, то 12-й задавать не обязательно, так как он и будет правильным).

По формуле 2 и с помощью калькулятора получаем:

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

Пример 3.6

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

Пример 3.7

Пример 3.8

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

I=log2256=8 бит=1 байт

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



Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.


Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

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

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

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

Что такое информация и ее классификация

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

· в кибернетике под информацией понимает ту часть знаний, которая используется для ориентирования, активного действия, управления, т.е. в целях сохранения, совершенствования, развития системы (Н. Винер).

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

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

1.2 Виды информации

Основные виды информации по ее форме представления, способам ее кодирования и хранения, что имеет наибольшее значение для информатики, это:

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

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

3. Текстовая — способ кодирования речи человека специальными символами — буквами, причем разные народы имеют разные языки и используют различные наборы букв для отображения речи; особенно большое значение этот способ приобрел после изобретения бумаги и книгопечатания;

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

1.3 Виды подходов к оценке количества информации


(РИСУНОК 1)

При всем многообразии подходов к определению понятия информации, с позиции измерения информации нас будут интересовать два из них: определение К. Шеннона, применяемое в математической теории информации (содержательный подход), и определение А. Н. Колмогорова, применяемое в отраслях информатики, связанных с использованием компьютеров (алфавитный подход). (рисунок 1)

1.4 Содержательный подход

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

Для человека информация — это знания человека. Рассмотрим вопрос с этой точки зрения.

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

Причем обычно значение N известно, а I приходится подбирать, что не совсем удобно. Поэтому те, кто знает математику получше, предпочитают преобразовать данную формулу так, чтобы сразу выразить искомую величину I в явном виде: I = log2 N

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

Формула Шеннона: I = - ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN),

Легко заметить, что если вероятности p1, . pN равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.

1.5 Алфавитный подход

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

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

Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой (равновероятно), то количество информации, которое несет каждый символ, вычисляется по формуле Хартли:

Алфавит - множество используемых символов в языке.

Мощность алфавита (N) - количество символов, используемых в алфавите.

i=log2N , где N - мощность алфавита.

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

Заключение

  • Для учеников 1-11 классов и дошкольников
  • Бесплатные сертификаты учителям и участникам

Формулы Хартли, Шеннона.

Иногда формулу Хартли записывают так:

I = log 2 K = log 2 (1 / р ) = - log 2 р

т. к. каждое из К событий имеет равновероятный исход р = 1 / К, то К = 1 / р.

Но не все ситуации имеют одинаковые вероятности реализации. Существует много таких ситуаций, у которых вероятности реализации различаются. Например, если бросают несимметричную монету или "правило бутерброда".

"Однажды в детстве я уронил бутерброд. Глядя, как я виновато вытираю масляное пятно, оставшееся на полу, старший брат успокоил меня:

- не горюй, это сработал закон бутерброда.

- Что еще за закон такой? - спросил я.

- Закон, который гласит: "Бутерброд всегда падает маслом вниз". Впрочем, это шутка, - продолжал брат. - Никакого закона нет. Просто бутерброд действительно ведет себя довольно странно: большей частью масло оказывается внизу.

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

Проверили. Из десяти раз восемь бутерброд упал маслом вниз.

И тут я задумался: а можно ли заранее узнать, как сейчас упадет бутерброд маслом вниз или вверх?

Наши опыты прервала мать…"

( Отрывок из книги "Секрет великих полководцев", В.Абчук).

В 1948 г. американский инженер и математик К. Шеннон предложил формулу для вычисления количества информации для событий с различными вероятностями.

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

К - количество возможных событий,

р i - вероятности отдельных событий,

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

где i принимает значения от 1 до К.

Формулу Хартли теперь можно рассматривать как частный случай формулы Шеннона:

I = - Sum 1 / К log 2 (1 / К ) = I = log 2 К .

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

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

Молекулы ДНК (дезоксирибонуклеиновой кислоты) состоят из четырех различных составляющих (нуклеотидов), которые образуют генетический алфавит. Информационная емкость знака этого алфавита составляет:

4 = 2 I , т.е. I = 2 бит.

Каждая буква русского алфавита (если считать, что е=ё) несет информацию 5 бит (32 = 2 I ).

поезд прибывает на один из 8 путей?

Формула Хартли: I = log 2 N ,

I = log 2 8 = 3(бит) Ответ: 3 бита.

Модифицированная формула Хартли для неравновероятностных событий. Так как наступление каждого из N возможных событий имеет одинаковую вероятность

p = 1 / N , то N = 1 / p и формула имеет вид

I = log 2 N= log 2 (1/p) = - log 2 p

I = log 2 (1/p)

Вероятность события вычисляется по формуле p=K/N , K – величина, показывающая, сколько раз произошло интересующее нас событие; N – общее число возможных исходов, событий. Если вероятность уменьшается, то количество информации увеличивается.

I = log 2 (1/p) = - log 2 p

вероятность события 15/30

Основные информационные единицы:

Iср - количество бит информации, приходящееся в среднем на одну букву;

I ср = -

Значение I ср достигает максимума при равновероятных событиях, то есть при равенстве всех p i p i = 1 / N.

В этом случае формула Шеннона превращается в формулу Хартли.

Аналогично, p р = 0,04, p ф = 0,002. Далее поступаем согласно К.Шеннону. Берем двоичный логарифм от величины 0,2 и называем то, что получилось количеством информации, которую переносит одна-единственная буква “а” в рассматриваемом тексте. Точно такую же операцию проделаем для каждой буквы. Тогда количество собственной информации, переносимой одной буквой равно log 2 1/p i = - log 2 p i , Удобнее в качестве меры количества информации пользоваться средним значением количества информации, приходящейся на один символ алфавита

I ср = -

Значение I ср достигает максимума при равновероятных событиях, то есть при равенстве всех p i

p i = 1 / N.

В этом случае формула Шеннона превращается в формулу Хартли.

При составлении таблицы мы должны учитывать:

Ввод данных (что дано в условии).

Подсчет общего количества числа возможных исходов (формула N=K 1 +K 2 +…+K i ).

Подсчет вероятности каждого события (формула p i = К i /N).

Подсчет количества информации о каждом происходящем событии (формула I i = log 2 (1/p i )).

Подсчет количества информации для событий с различными вероятностями (формула Шеннона).

1 . Сделать табличную модель для вычисления количества информации.

2 . Используя табличную модель, сделать вычисления к задаче №2 (рис.3), результат вычисления занести в тетрадь.

3 . Используя таблицу-шаблон, решить задачи №3,4 (рис.4, рис.5), решение оформить в тетради.

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

Читайте также: