| Планирование уроков и материалы к урокам | 11 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю) | Количество информации

Уроки 2 - 3
Информация и вероятность. Формула Хартли. Формула Шеннона
(§1. Количество информации)

Ответить на этот вопрос стало возможно только после того, как вы изучили логарифмы в курсе математики. Из формулы

сразу следует, что I - это степень, в которую нужно возвести 2, чтобы получить N, т. е. логарифм:

Эта формула называется формулой Хартли в честь американского инженера Ральфа Хартли, который предложил её в 1928 г.

Пусть, например, на лётном поле стоят 10 самолётов (с номерами от 1 до 10) и известно, что один из них летит в Санкт-Петербург.

Сколько информации в сообщении «Самолёт № 2 летит в Санкт-Петербург»? У нас есть 10 вариантов, из которых выбирается один, поэтому по формуле Хартли количество информации равно

I = log 2 10 ≈ 3,322 бита.

Обратите внимание, что для значений N, которые не равны целой степени числа 2, количество информации в битах - дробное число.

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

I = log 2 50 ≈ 5,644 бита.

Если сообщение содержит 100 символов, его общий информационный объём примерно равен

5,644 100 = 564,4 бита.

В общем случае объём сообщения длиной L символов, использующего алфавит из N символов, равен I = L log 2 N.

Такой подход к определению количества информации называют алфавитным. Конечно, на практике невозможно использовать для кодирования символа нецелое число битов, поэтому используют первое целое число, которое больше теоретически рассчитанного значения. Например, при использовании алфавита из 50 символов каждый символ будет закодирован с помощью 6 битов (50 ≤ 2 6 = 64).

Сколько разных сообщений можно передать, если известен алфавит и длина сообщения? Предположим, что для кодирования сообщения используются 4 буквы, например «А», «Б», «В» и «Г», и сообщение состоит из двух символов. Поскольку каждый символ может быть выбран 4 разными способами, на каждый вариант выбора первого символа есть 4 варианта выбора второго. Поэтому общее число разных двухбуквенных сообщений вычисляется как 4 4 = 4 2 = 16. Если в сообщение добавить ещё один символ, то для каждой из 16 комбинаций первых двух символов третий можно выбрать четырьмя способами, так что число разных трёхсимвольных сообщений равно 4 4 4 = 4 3 = 64.

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

Следующая страница

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

Похожая ситуация сложилась и в отношении информации. Р. Хартли в 1928, а затем К. Шеннон в 1948 предложили формулы для вычисления количества информации, однако на вопрос о том, что такое информация, они так и не ответили. В теории связи информация выступает в виде различных сообщений: например, букв или цифр, как в телеграфии, или в виде непрерывной функции времени, как при телефонии или радиовещании. В любом из указанных примеров, в конечном итоге, задача состоит в передаче смыслового содержания человеческой речи. В свою очередь, человеческая речь может быть представлена в звуковых колебаниях или в письменном изложении.

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

Р. Хартли первым ввел в теорию передачи информации методологию «измерения количества информации». При этом Р. Хартли считал, что информация, которую он собирался измерять, это «… группа физических символов - слов, точек, тире и т. п., имеющих по общему соглашению известный смысл для корреспондирующих сторон». Таким образом, Хартли ставил перед собой задачу ввести какую-то меру для измерения кодированной информации.

Пусть передаётся последовательность из n символов а 1 а 2 а 3 а n , каждый из которых принадлежит алфавиту А m , содержащему m символов. Чему равно число К различных вариантов таких последовательностей? Если n = 1 (передаётся один символ), то K = m; если n=2 (передаётся последовательность из 2-х символов), то K = m*m = m 2 ; в общем случае для последовательности из n символов получим

Количество информации, содержащееся в такой последовательности, Хартли предложил вычислять как логарифм числа K по основанию 2:

I = Log 2 K, (2.1)

где K = m n .

То есть, количество информации, содержащееся в последовательности из n символов из алфавита A m , в соответствии с формулой Хартли равно

I = Log 2 (m n) = n Log 2 m . (2.2)

Замечание 1. Хартли предполагал, что все символы алфавита A m могут с равной вероятностью (частотой) встретиться в любом месте сообщения. Это условие нарушается для алфавитов естественных языков: например, не все буквы русского алфавита встречаются в тексте с одинаковой частотой.

Замечание 2. Любое сообщение длины n в алфавите A m будет содержать одинаковое количество информации. Например, в алфавите {0; 1} сообщения 00111, 11001 и 10101 содержат одинаковое количество информации. Это означает, что при вычислении количества информации, содержащегося в сообщении, мы отвлекаемся от его смыслового содержания. «Осмысленное» сообщение и сообщение, полученное из него произвольной перестановкой символов, будут содержать одинаковое количество информации.

Пример. В телеграфном сообщении используются два символа - точка (.) и тире (-), т.е. алфавит состоит из m = 2 символов. Тогда при передаче одного символа (n =1) количество информации I = Log 2 2 = 1. Это количество было принято за единицу измерения количества информации и называется 1 бит (от английского binary unit = bit ). Если телеграфное сообщение в алфавите {. ; -} содержит n символов, то количество информации I = n Log 2 2 = n (бит).

С помощью символов 0 и 1 кодируется информация в компьютере и при передаче в вычислительных сетях, т.е. алфавит состоит из двух символов {0 ; 1}; один символ и в этом случае содержит I = Log 2 2 = 1 бит информации, поэтому сообщение длиной n символов в алфавите {0 ; 1} в соответствии с формулой Хартли (2.2) будет содержать n бит информации.

Если рассматривать передачу сообщений в алфавите русского языка, состоящего из 33 букв, то количество информации, содержащееся в сообщении из n символов, вычисленное по формуле Хартли, равно I = n*Log 2 33 » n* 5.0444 бит. Английский алфавит содержит 26 букв, один символ содержит Log 2 26 » 4.7 бит, поэтому сообщение из n символов, вычисленное по формуле Хартли, содержит n* Log 2 26 » 4.7 *n бит информации. Однако, этот результат не является правильным, так как не все буквы встречаются в тексте с одинаковой частотой. Кроме того, к буквам алфавита надо добавить разделительные знаки: пробел, точку, запятую и др.

Формула (2.1) внешне напоминает формулу Больцмана для вычисления энтропии системы с N равновероятными микросостояниями:

S= - k*Ln(W), (2.3)

где k - постоянная Больцмана = 1,38*10 -23 , а W- вероятность спонтанного принятия одного из микросостояний системы в единицу времени t = 10 -13 сек., W = 1/N, т.е.

S= -k*Ln(1/N) = k*Ln(N), (2.4)

что полностью согласуется с формулой (2.1) за исключением множителя k и основания логарифма. Из-за этого внешнего сходства величину Log 2 K в теории информации также называют энтропией и обозначают символом H. Информационная энтропия - это мера неопределённости состояния некоторой случайной величины (физической системы) с конечным или счётным числом состояний. Случайная величина (с.в.) - это величина, которая в результате эксперимента или наблюдения принимает числовое значение, заранее неизвестно какое.

Итак, пусть X - случайная величина, которая может принимать N различных значений x 1 , x 2 , … x N ; если все значения с.в. X равновероятны, то энтропия (мера неопределённости) величины X равна:

H(X) = Log 2 N. (2.5)

Замечание. Если случайная величина (система) может находиться только в одном состоянии (N=1), то её энтропия равна 0. Фактически это уже не случайная величина. Неопределённость системы тем выше, чем больше число её возможных равновероятных состояний.

Энтропия и количество информации измеряются в одних и тех же единицах - в битах.

Определение. 1 бит - это энтропия системы с двумя равновероятными состояниями.

Пусть система X может находиться в двух состояниях x1 и x2 с равной вероятностью, т.е. N = 2; тогда её энтропия H(X) = Log 2 2 = 1 бит. Пример такой системы даёт нам монета, при подбрасывании которой выпадает либо орёл (x1), либо решка (x2). Если монета «правильная», то вероятность выпадения орла или решки одинаковая и равна 1/2.

Дадим ещё одно определение единицы измерения информации.

Определение. Ответ на вопрос любой природы (любого характера) содержит 1 бит информации, если он с равной вероятностью может быть «да» или «нет».

Пример. Игра в «пусто-густо». Вы прячете мелкий предмет в одной руке и предлагаете партнёру угадать, в какой руке вы его спрятали. Он спрашивает вас « в левой руке?» (или просто выбирает руку: левую или правую). Вы отвечаете «да», если он угадал, или «нет», в противном случае. При любом варианте ответа партнёр получает 1 бит информации, а неопределённость ситуации полностью снимается.

Формулу Хартли можно использовать при решении задач на определение выделенного элемента некоторого заданного множества. Этот результат можно сформулировать в виде следующего правила.

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

Рассмотрим несколько задач на применение формулы Хартли.

Задача 1. Некто задумал натуральное число в диапазоне от 1 до 32. Какое минимальное число вопросов надо задать, чтобы гарантированно угадать задуманное (выделенное) число. Ответы могут быть только «да» или «нет».

Комментарий. Можно попытаться угадать задуманное число простым перебором. Если повезёт, то придётся задать только один вопрос, а при самом неудачном варианте перебора придётся задать 31 вопрос. В предложенной задаче нужно определить минимальное число вопросов, с помощью которых вы гарантированно определяете задуманное число.

Решение. По формуле Хартли можно вычислить количество информации, которое необходимо получить для определения выделенного элемента x из множества целых чисел {1,2,3 32}. Для этого необходимо получить Н = Log 2 32 = 5 бит информации. Вопросы надо задавать так, чтобы ответы на них были равновероятны. Тогда ответ на каждый такой вопрос будет приносить 1 бит информации. Например, можно разбить числа на две равные группы от 1 до 16 и от 17 до 32 и спросить, в какой группе находится задуманное число. Далее, аналогично следует поступить с выделенной группой, которая содержит уже лишь 16 чисел, и т.д. Пусть, например, задумано число 7.

Вопрос №1: Задуманное число принадлежит множеству {17; 32}? Ответ «нет» приносит вам 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1 ; 16}.

Вопрос №2: Задуманное число принадлежит множеству {1 ; 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1 ; 8}.

Вопрос №3: Задуманное число принадлежит множеству {1 ; 4}? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {5 ; 8}.

Вопрос №4: Задуманное число принадлежит множеству {7 ; 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {7 ; 8}.

Вопрос №5: Задуманное число равно 8? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что задуманное число равно 7. Задача решена. Было задано пять вопросов, в ответ получено 5 бит информации и определено задуманное число. ‚

Задача 2. (Задача о фальшивой монете). Имеется 27 монет, из которых 26 настоящих и одна фальшивая. Каково минимальное число взвешиваний на рычажных весах, за которое можно гарантированно определить одну фальшивую монету из 27, используя то, что фальшивая монета легче настоящей.

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

Решение. Это задача на определение одного выделенного элемента из 27. По формуле Хартли мы сразу можем определить количество информации, которое нужно получить для определения фальшивой монеты: оно равно I = Log 2 27 = Log 2 (3 3) = 3 Log 2 3 бит. Отметим, что ещё не зная стратегии взвешивания, можно сказать, сколько информации мы должны получить для решения задачи.

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

1. Левая чашка тяжелее правой (Л > П);

2. Левая чашка легче правой (Л < П);

3. Левая чашка находится в равновесии с правой (Л = П);

Система «рычажные весы» может находиться в трёх равновероятных состояниях, поэтому одно взвешивание даёт Log 2 3 бит информации. Всего для решения задачи надо получить I = 3 Log 2 3 бит информации, значит надо сделать три взвешивания для определения фальшивой монеты. Мы уже знаем минимальное число взвешиваний, но ещё не знаем, как их следует проводить. Стратегия должна быть такой, чтобы каждое взвешивание давало максимальное количество информации. Разделим все монеты на три равные кучки A, B и C по 9 штук в каждой. Фальшивая монета, обозначим её буквой f, может с равной вероятность находиться в любой из трёх кучек. Выберем любые две из них, например A и B, и взвесим их.

Возможны три исхода:

1) A тяжелее B (A > B); значит f Î B;

2) A легче B (A < B); значит f Î A;

3) A находится в равновесии с B (A = B); значит f Î С.

При любом исходе мы определим в какой кучке находится фальшивая монета f, но в этой кучке будет уже только 9 монет. Разобъём её на три равные кучки A1, B1, C1 по 3 монеты в каждой. Выберем любые две и взвесим их. Как и на предыдущем шаге, мы определим ту кучку монет, в которой находится фальшивая монета, но теперь кучка состоит только из трёх монет. Выберем любые две монеты и взвесим их. Это будет последнее, третье взвешивание, после которого мы найдём фальшивую монету.

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

Решение. По формуле Хартли H = Log 2 50. Оценим данное выражение.

Очевидно, 32 < 50 < 64; логарифмируем это неравенство à Log 2 32 < Log 2 50 < Log 2 64 à 5 < Log 2 50 < 6. Энтропия системы с точностью до 1 бита 5 < H < 6 . ‚

Задача 4. Известно, что энтропия системы составляет 7 бит. Определите число состояний этой системы, если известно, что все они равновероятны.

Решение. Обозначим через N число состояний системы. Так как все состояния равновероятны, то H = Log 2 N à N = 2 H , т.е. N = 2 7 = 128.

Информация может существовать в виде:

текстов, рисунков, чертежей, фотографий;

световых или звуковых сигналов;

радиоволн;

электрических и нервных импульсов;

магнитных записей;

жестов и мимики;

запахов и вкусовых ощущений;

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

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

1.4. Как передаётся информация?

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

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

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

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

1.5. Как измеряется количество информации?

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

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

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

Подходы к определению количества информации. Формулы Хартли и Шеннона.

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N .

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

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log 2 100 = 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

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

при бросании монеты: "выпала решка" , "выпал орел" ;

на странице книги: "количество букв чётное" , "количество букв нечётное" .

Определим теперь, являются ли равновероятными сообщения "первой выйдет из дверей здания женщина" и "первым выйдет из дверей здания мужчина" . Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, кинотеатр, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.

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

Формула Шеннона: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N ), где p i - вероятность того, что именно i -е сообщение выделено в наборе из N сообщений.

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

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ . bit - bi nary digi t - двоичная цифра).

Бит в теории информации - количество информации, необходимое для различения двух равновероятных сообщений (типа "орел"- "решка", "чет"- "нечет" и т.п.). В вычислительной технике битом называют наименьшую "порцию" памяти компьютера, необходимую для хранения одного из двух знаков "0" и "1", используемых для внутри машинного представления данных и команд.

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

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

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

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

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

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

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

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

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

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

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

Для других же равновероятных событий, таких как подброс монеты (вероятность того что выпадет орёл или решка будет одинаковой — 50 %) используется формула Хартли.

Теперь, давайте рассмотрим применение этой формулы на конкретном примере:

В каком сообщений содержится меньше всего информации (Считайте в битах):

1. Василий сьел 6 конфет, из них 2 было барбариски.
2. В комьютере 10 папок, нужный файл нашелся в 9 папке.
3. Баба Люда сделала 4 пирога с мясом и 4 пирога с капустой. Григорий сьел 2 пирога.
4. В Африке 200 дней сухая погода, а 165 дней льют муссоны. африканец охотился 40 дней в году.

В этой задаче обратим внимания что 1,2 и 3 варианты, эти варианты считать легко, так как события равновероятны. И для этого мы будем использовать формулу Хартли I = log 2 N (рис.1) А вот с 4 пунком где видно, что распределение дней не равномерно(перевес в сторону сухой погоды), что же тогда нам в этом случае делать? Для таких событий и используется формула Шеннона или информационной энтропии: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N), (рис.3)

ФОРМУЛА КОЛИЧЕСТВА ИНФОРМАЦИ (ФОРМУЛА ХАРТЛИ, РИС.1)

В которой:

• I — количество информации
• p — вероятность того что это события случиться

Интересующие нас события в нашей задаче это

1. Было две барбариски из шести (2/6)
2. Была одна папка в которой нашлась нужный файл по отношению к общему количеству (1/10)
3. Всего пирогов было восемь из которых сьедено григорием два (2/8)
4. и последнее сорок дней охоты по отношению к двести засушливым дням и сорок дней охоты к сто шестидесяти пяти дождливым дням. (40/200) + (40/165)

таким образом получаем что:

ФОРМУЛА ВЕРОЯТНОСТИ ДЛЯ СОБЫТИЯ.

Где K — это интересующие нас событие, а N общее количество этих событий, также чтобы проверить себя вероятность того или иного события не может быть больше единицы. (потому что вероятных событий всегда меньше)

ФОРМУЛА ШЕННОНА ДЛЯ ПОДСЧЕТА ИНФОРМАЦИИ (РИС.3)

Вернемся к нашей задаче и посчитаем сколько информации содержится.

Кстате, при подсчёте логарифма удобно использовать сайт — https://planetcalc.ru/419/#

• Для первого случая — 2/6 = 0,33 = и далее Log 2 0,33 = 1.599 бит
• Для второго случая — 1/10 = 0,10 Log 2 0,10 = 3.322 бит
• Для третьего — 2/8 = 0,25 = Log 2 0,25 = 2 бит
• Для четвертого — 40/200 + 40/165 = 0.2 и 0,24 соотвественно, далее считаем по формуле -(0,2 * log 2 0,2) +-(o.24 * log 2 0.24) = 0.95856 бит

Таким образом ответ для нашей задачи получился 4.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru

1. Теория информации

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

Клода Шеннона (1916--2001) называют «отцом теории информации».

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

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

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

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

Трудность передачи сообщения не зависит от его содержания; передавать бессмысленные сообщения не менее трудно, чем осмысленные. Например, число 23 в одном контексте может быть ценой одного барреля нефти, а в другом - номером победителя заезда на скачках. Смысл сообщения зависит от контекста и семантики, а трудность его передачи определяется только перечнем возможных сообщений (и их вероятностей).

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

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

Изучение систем передачи информации начинается с источника сообщений. По каналу связи может передаваться самая различная информация: текст, живая речь, музыка или изображения. Для каждого источника можно указать перечень сообщений, которые он может генерировать. Например, источник телеграфных или телексных сообщений передает только буквы и не содержит, скажем, нотных знаков. Если по каналу связи передается живая речь, то сигнал лишается полезного содержания при частоте выше 20 000 Гц, верхнего предела, воспринимаемого человеческим слухом. Этими фактами можно воспользоваться при проектировании входа канала связи.

Для оценки кол-ва информации в сообщении в теории информации, используется логарифмическая мера, введённая Р. Хартли, вероятностная интерпретация которой была дана в работах Шеннона. Если вероятность появления сообщения x есть p(x), причем 0 <р (х)<1, то количество информации - I(x), содержащееся в сообщении, определяется формулой:

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

Формула Хартли:

K=log2 N,

где К - количество информации, N -число равновероятных событий.

Формула Хартли может быть записана и так: N=2k

Так как наступление каждого из N событий имеет одинаковую вероятность P, то:

где P- вероятность наступления события.

Тогда, формулу можно записать иначе:

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

Формула Шеннона:

K = - (p1 *log2 p1+ p2 *log 2p 2 + p 3 *log 2p 3 +…+ pi * log2 pi),

где pi вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Также эту формулу записывают:

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

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

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

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

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

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

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

Объемный подход.

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

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

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

Энтропийный (вероятностный) подход.

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

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

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

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

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

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

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

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

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

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

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

2. в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;

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

Поэтому функция энтропии должна удовлетворять условиям:

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

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

Для целых положительных, должно выполняться следующее неравенство:

Для целых положительных, где, должно выполняться равенство:

информационный пропускной энтропийный

Шеннон определил, что измерение энтропии, применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка -- имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д.

Размещено на Allbest.ru

Подобные документы

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

лабораторная работа , добавлен 06.12.2013


Предмет и задачи теории информации, ее функции при создании АСУ. Определение пропускной способности дискретных (цифровых) каналов при отсутствии шумов. Расчет скорости передачи информации. Вычисление значения энтропии - среднего количества информации.

контрольная работа , добавлен 18.01.2015


Бит, неопределенность, количество информации и энтропия. Формула Шеннона. Формула Хартли. Логарифмы. Количество информации, получаемой в процессе сообщения. Взаимодействие источника и приемника информации. Количество, информационная емкость ячеек памяти.

реферат , добавлен 17.07.2008


Центральное понятие кибернетики – информация. Комплексная автоматизация процессов восприятия, преобразования, передачи, обработки и отображения информации и создание автоматизированных систем управления на различных уровнях. Система передачи информации.

книга , добавлен 07.05.2009


Основы теории передачи информации. Экспериментальное изучение количественных аспектов информации. Количество информации по Хартли и К. Шеннону. Частотные характеристики текстовых сообщений. Количество информации как мера снятой неопределенности.

лабораторная работа , добавлен 15.02.2011


презентация , добавлен 19.10.2014


Основные понятия теории информации как науки. Среднее количество информации, приходящееся на 1 знак определяемое формулой Шеннона. Общая схема передачи сообщения. Пропускная способность канала. Булева алгебра и техническая реализация процесса вычисления.

презентация , добавлен 13.08.2013


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

презентация , добавлен 14.10.2013


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

курсовая работа , добавлен 17.04.2009


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