Энтропия (теория информации). Энтропия источника дискретных сообщений (ИДС) и её свойства
Аннотация: Вводится понятие энтропии. На нескольких примерах показывается, как вычисляется энтропия дискретной случайной величины. Вводится понятие префиксного кодирования. Задачи на самостоятельную работу улучшают восприятие материала. Также много различных математических исследований
Энтропия д.с.в. - это минимум среднего количества бит , которое нужно передавать по каналу связи о текущем значении данной д.с.в.
Рассмотрим пример (скачки). В заезде участвуют 4 лошади с равными шансами на
победу, т.е. вероятность
победы каждой лошади равна 1/4. Введем д.с.в. , равную номеру победившей лошади. Здесь .
После каждого заезда по каналам связи достаточно будет передавать два
бита информации о номере победившей лошади. Кодируем номер лошади следующим
образом: 1-00, 2-01, 3-10, 4-11. Если ввести функцию ,
которая возвращает длину сообщения, кодирующего заданное значение
, то м. о. - это средняя длина
сообщения, кодирующего . Можно формально определить через две функции , где каждому значению ставит в соответствие
некоторый битовый код, причем, взаимно однозначно, а возвращает длину в битах для
любого конкретного кода. В этом примере 
.
Пусть теперь д.с.в. имеет следующее распределение
Т.е. лошадь с номером 1 - это фаворит. Тогда
Закодируем номера лошадей: 1-0, 2-10, 3-110, 4-111, - т.е. так, чтобы каждый код не был префиксом другого кода (подобное кодирование называют префиксным ). В среднем в 16 заездах 1-я лошадь должна победить в 12 из них, 2-я - в 2-х, 3-я - в 1-м и 4-я - в 1-м. Таким образом, средняя длина сообщения о победителе равна бит /сим или м. о. . Действительно, сейчас задается следующим распределением вероятностей: , , . Следовательно,
Итак, 
.
Можно доказать, что более эффективного кодирования для двух рассмотренных случаев не существует.
То, что энтропия Шеннона
соответствует интуитивному представлению о мере
информации, может быть продемонстрировано в опыте по определению среднего
времени психических реакций. Опыт
заключается в
том, что перед испытуемым человеком зажигается одна из
лампочек, которую он должен указать. Проводится большая серия испытаний, в которых
каждая лампочка зажигается с определенной вероятностью 
,
где - это номер лампочки. Оказывается, среднее
время, необходимое для правильного ответа испытуемого, пропорционально
величине энтропии 
, а не числу лампочек , как можно было бы подумать. В этом опыте предполагается, что чем больше
информации будет получено человеком, тем дольше будет время ее обработки
и, соответственно, реакции на нее.
Упражнение 13 Найти энтропию д.с.в. и среднюю длину каждого из приведенных кодов для этой д.с.в.
Упражнение 14 д.с.в. равна количеству "гербов", выпавших на двух идеальных монетках. Найти энтропию . Придумать минимальный код для , вычислить его среднюю длину и обосновать его минимальность.
Упражнение 15
д.с.в. задана распределением , 
Найти
энтропию этой д.с.в. Придумать минимальный код для , вычислить
его среднюю длину и обосновать его минимальность.
Упражнение 16 Про д.с.в. известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для .
Семантическая информация
В 50-х годах XX века появились первые попытки определения абсолютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, целиком построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности существования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Примером одной из таких мер является функция , где - это предложение, смысловое содержание которого измеряется, -
Как мы можем измерить информацию в событии? Сколько информации нам доставляет событие? Давайте ответим на эти вопросы с помощью примеров.
Пример F.1
Вообразите человека, сидящего в комнате. Глядя из окна, он может ясно видеть, что сияет солнце. Если в этот момент он получает сообщение (событие) от соседа, который говорит "Хороший день", это сообщение содержит какую-либо информацию? Конечно нет! Человек уже уверен, что это день и погода хорошая. Сообщение не уменьшает неопределенности его знаний.
Пример F.2
Вообразите, что человек купил лотерейный билет. Если друг звонит, чтобы сказать, что он выиграл первый приз, это сообщение (событие) содержит информацию? Конечно да! Сообщение содержит много информации, потому что вероятность выигрыша первого приза является очень маленькой. Приемник сообщения потрясен.
Вышеупомянутые два примера показывают, что есть отношения между полноценностью события и ожиданиями приемника. Если приемник удален от места события, когда событие случается, сообщение содержит много информации; иначе - это не так. Другими словами, информационное содержание сообщения обратно пропорционально связано с вероятностью возникновения этого сообщения. Если событие очень вероятно, оно не содержит никакой информации (Пример F.1); если оно является маловероятным, оно содержит много информации (Пример F.2).
F.2. Энтропия
Предположим, что S - распределение вероятностей конечного числа событий (См. "приложение D"). Энтропия или неопределенность в S может быть определена как:
где - возможный результат одного испытания. Обратите внимание, что, если. P (s) = 0 , то мы будем считать, что P(S) x равно 0 , чтобы избежать деления на 0.
Пример F.3
Предположим, что мы бросаем правильную монету. Результаты - "орел" и "решка", каждый с вероятностью 1/2, и это означает
H (S) = P(орел) x + P (решка) x H (S) = (1/2) x = 1 бит
Этот пример показывает, что результат бросания правильной монеты дает нам 1 бит информации (неопределенность). При каждом бросании мы не знаем, каков будет результат, поскольку две возможности одинаково вероятны.
Пример F.4
Предположим, что мы бросаем неправильную (поврежденную) монету. Результаты выпадения "орла" и "решки" следующие P ("орел") = 3/4 и P ("решка") = 1/4 . Это означает, что
H (S) = (3/4) x + (1/4) x = 0,8 бит
Этот пример показывает, что результат бросания неправильной монеты дает нам только 0,8 битов информации (неопределенность). Количество информации здесь меньше, чем количество информации в Примере F.3, потому что мы ожидаем получить "орлов" большее число раз, чем "решек".
Пример F.5
Теперь предположим, что мы бросаем полностью неправильную монету, в которой результат является всегда "орел", P ("орел") = 1 и P ("решка") = 0 . Энтропия в этом случае
H (S) = (1) x + (0) x = (1) x (0) + (0) = 0
В этом эксперименте нет никакой информации (неопределенности). Мы знаем, что результатом всегда будет "орел" ; энтропия - 0.
Максимальная энтропия
Может быть доказано, что для распределения вероятностей с n возможными результатами максимальная энтропия может быть достигнута, только если все вероятности равны (все результаты одинаково вероятны). В этом случае максимальная энтропия
H max = log 2 n бит
Другими словами, энтропия любого множества вероятностей имеет верхний предел , который определяется этой формулой.
Пример F.6
Предположим, что бросается шестигранная игральная кость. Энтропия испытания равна
Минимальная энтропия
Можно доказать, что для распределения вероятностей с n возможными результатами, получается минимальная энтропия тогда и только тогда, когда все время получается один из результатов. В этом случае минимальная энтропия
H min (S) = 0 битов
Другими словами, эта формула определяет нижний предел энтропии для любого набора вероятностей.
Энтропия любого набора вероятностей находится между 0 бит и log 2 n бит, где n - число возможных результатов .
Интерпретация энтропии
Энтропию можно воспринимать как число бит , которым можно представить каждый результат из множества вероятностей, в том случае, когда результаты одинаково вероятны. Например, когда возможное случайное распределение имеет восемь возможных результатов, каждый результат может быть представлен в виде трех бит (от 000 до 111 ). Когда мы получаем результат эксперимента, мы можем сказать, что получили 3 бита информации. Энтропия этого набора вероятностей - также 3 бита (ln 2 8 = 3 ).
Совместная энтропия
Когда мы имеем два набора распределения вероятностей, S 1 и S 2 , мы можем определить совместную энтропию H (S 1 , S 2) как
Условная энтропия
Мы часто должны знать неопределенность распределения вероятностей S 1 , при условии получения результата, который определяется неопределенностью распределения вероятности S 2 . Она называется условной энтропией H (S 1 | S 2) . Может быть доказано, что
H (S 1 | S 2) = H (S 1 , S 2) - H (S 2) бит
Другие соотношения
Приведем здесь без доказательства некоторые другие соотношения для энтропии:
- H (S 1 , S 2) = H (S2 | S 1) + H (S 1) = H (S 1 | S 2) + H (S2)
- H (S 1 , S 2) <= H (S 1) + H (S2)
- H (S 1 | S 2) <= H (S 1)
- H (S 1 , S2, S3) = H (S 1 | S2, S3) + H (S 1 , S3)
Второе и третье соотношения справедливы, если S 1 и S 2 статистически независимы.
Пример F.7
В криптографии, если P - распределение вероятностей исходного текста, C - распределение вероятностей зашифрованного текста и K - распределение вероятностей ключей, то H (K|C) может интерпретироваться как сложность атаки зашифрованного текста, в которой знание C может привести к знанию K .
Пример F.8
В криптографии, учитывая исходный текст и ключ, детерминированный алгоритм шифрования создает уникальный зашифрованный текст, что означает H (C | K, P) = 0 . Также учитывая зашифрованный текст и ключевой алгоритм дешифрования, создается уникальный исходный текст, что означает H (P | K, C) = 0 . Если дан зашифрованный текст и исходный текст, ключ также определяется уникально: H (K | P, C) = 0 .
Совершенная секретность
В криптографии, если P , K и C - пространства выборки вероятности исходного текста, зашифрованного текста и ключа соответственно, то мы имеем H (P|C) <=H (P) . Это может быть интерпретировано так: неопределенность P данного C меньше или равна неопределенности P . В большинстве криптографических систем, справедливо отношение H (P|C)< H (P) , что означает, что перехват зашифрованного текста уменьшает знание, которое требуется для того, чтобы найти исходный текст. Криптографическая система обеспечивает совершенную секретность , если соблюдается соотношение H (P|C)=H (P) , - это означает, что неопределенность исходного текста и данного зашифрованного текста - одна и та же неопределенность исходного текста. Другими словами, Ева не получает никакой информации, перехватив зашифрованный текст; она по-прежнему должна исследовать все возможные варианты.
Криптографическая система обеспечивает совершенную секретность, если H (P | C) = H (P) .
Пример F.9
В предыдущих лекциях мы утверждали, что одноразовый шифр блокнота обеспечивает совершенную секретность. Докажем этот факт, используя предыдущие соотношения энтропии. Предположим, что алфавит - только 0 и 1 . Если длина сообщения - L , может быть доказано, что ключ и зашифрованный текст состоят из 2 L символов, в которых каждый символ является одинаково вероятным. Следовательно, H (K) = H (C) = log 2 2 L = L . Используя отношения, полученные в примере F.8, и то, что H (P, K) = H (P) + H (K) , потому что P и K независимы, мы имеем
H (P, K, C) = H (C|P, K) + H (P, K) = H (P, K) = H (P) + H (K) H (P, K, C) = H (K|P, C) + H (P, C) = H (P, C) = H (P|C) + H (C)
Это означает, что H (P | C) = H (P)
Пример F.10
Шеннон показал, что в криптографической системе, если (1) ключи возникают с равной вероятностью и (2) для каждого исходного текста и каждого зашифрованного текста есть уникальный ключ, то криптографическая система обеспечивает совершенную секретность. Доказательство использует тот факт, что в этом случае распределения вероятностей ключей, исходного текста и зашифрованного текста имеют один и тот же размер.
F.3. Энтропия языка
Интересно связать концепцию энтропии с естественными языками, такими как английский язык. В этом разделе мы касаемся некоторых пунктов, связанных с энтропией языка.
Энтропия произвольного языка
Предположим, что язык использует N букв и все буквы имеют равную вероятность появления. Мы можем сказать, что энтропия этого языка - H L = log 2 N . Например, если мы используем двадцать шесть прописных букв (от A до Z), чтобы передать наше сообщение, то
Человечество в прошлом не испытывало потребностей в количественном измерении информации. Такая потребность возникла в связи с развитием средств коммуникаций, измерительной техники, компьютерных систем.
Первую количественную метрику предложил Хартли в 1928 году и назвал её информационной емкостью.
Рассмотрим некоторую ячейку из n
реле. Считая, что каждое реле может хранить два состояния m
= 2, вся ячейка может содержать N =
2 n
состояний. Хартли ввел двоичную логарифмическую меру, позволяющую измерять информацию в двоичных единицах – битах. Один бит – это количество информации, которое может храниться в элементарной ячейке на два состояния: .
В ячейке на состояний хранится 
. Основание логарифма определяет размерность единиц измерения информации. Поскольку используют двоичные единицы – биты, основание логарифма опускают. Двоичная единица информации «бит» произошла от «сжатия» английских слов binary digit – двоичная единица.
Такая мера является аддитивной , она позволяет осуществлятьсложение информации в разных ячейках при объединении их в одну.
Мера Хартли (структурная метрика информации) не отражала вероятностного характера информации и не могла быть использована для оценки информационных свойств источников сообщений. В 1948 году Шенноном была предложена статистическая, т.е. вероятностная мера.
Пусть дискретный источник выдает сообщение а , принадлежащее некоторому конечному ансамблю А (). Определим количество информации, содержащееся в этом сообщении, используя три исходных естественных (очевидных) требования:
1) количество информации должно быть аддитивной величиной, т. е. в двух независимых сообщениях количество информации определяется как сумма количеств информации в каждом из них;
2) количество информации в сообщении о достоверном событии равно 0;
3) количество информации не должно зависеть от качественного содержания сообщения (степени важности, возможных последствий его передачи, эмоциональной окраски и т. п.).
В общем случае сообщение а из ансамбля А характеризуется вероятностью , что источник формирует или посылает это сообщение, т. е. количество информации I (a ), содержащейся в сообщении а , должно быть функцией от вероятности .
,
где – вероятности формирования сообщения а 1 и а 2 соответственно.
Общее количество информации I (a 1 , а 2), содержащейся в этих двух сообщениях, согласно условию аддитивности определяется как сумма количеств информации в каждом из них:
Таким образом, надо найти функцию от вероятности такую, чтобы при перемножении двух аргументов значения функции складывались. Этому условию удовлетворяет только логарифмическая функция
,
где k – произвольный коэффициент.
Логарифм, вообще говоря, может быть взят по любому основанию. Эта формула может быть использована для определения количества информации, содержащейся в сообщении а i . Эта формула удовлетворяет и требованию 2): в случае достоверного события вероятность сообщения = 1. Тогда количество информации согласно полученной формуле:
Поскольку < 1, и следовательно, log ≤ 0, то, чтобы измерять количество информации неотрицательными числами, выбираем значение коэффициента k = –1:
.
Основание логарифма чаще всего в формуле для определения количества информации выбирают равным двум. Получаемая при этом единица информации носит название двоичная единица, или бит.
Такая единица наиболее удобна потому, что в современной вычислительной технике, технике связи широко используются двоичные коды, двоичные дискретные устройства.
Пусть дискретный источник сообщений вырабатывает полный ансамбль сообщений , где – вероятность -го сообщения. Этот источник может быть охарактеризован средним количеством информации, приходящимся на одно сообщение:
.
Эту величину Шеннон назвал энтропией источника
. Понятие энтропии (от греческого «эн-тропе» – обращение) существовало и до Шеннона и распространилось на ряд областей знания. В термодинамике энтропия означает вероятность теплового состояния вещества, в математике – степень неопределенности ситуации или задачи, в информатике она характеризует способность источника отдавать информацию
. Количество информации, которое переносится одним сообщением источника 
.
Эта мера вытекает из меры Хартли: 
и является ее обобщением на случай неравновероятности сообщений. Видно, что чем меньше вероятность сообщения, тем большее количество информации оно несет. Мера Шеннона также аддитивна.
И количество информации I в сообщении и энтропия источника H измеряются в одних единицах – в битах, но эти величины различны. Энтропия H источника определяет способность источника производить информацию; при наличии достаточной статистики она может быть вычислена априори, до получения сообщений. Получение информации I снимает часть неопределенности источника, уменьшает его энтропию. Это уменьшение энтропии происходит после (апостериори) получения сообщения, т.е. I определяется апостериорно. Таким образом, количество информации может рассматриваться как противоположность энтропии , в этом проявляется диалектический закон единства и борьбы противоположностей.
Энтропия источника дискретных сообщений обладает следующими свойствами:
1. Энтропия положительна.
2. Энтропия детерминированных сообщений равна нулю. Если одно из сообщений источника достоверно, т.е. его вероятность равна 1, то вероятности других сообщений равны нулю.
3. Энтропия максимальна, если сообщения источника равновероятны.
.
4. В случае равновероятных сообщений энтропия возрастает с увеличением числа сообщений.
5. Энтропия источника бинарных (двоичных) сообщений изменяется от нуля до единицы в зависимости от вероятности сообщений и имеет максимум при 
.
В этом случае мера Шеннона совпадает с мерой Хартли. Источник с энтропией в 1 бит полностью согласован с каналом, например, реле, имеющим информационную емкость в 1 бит. При неравновероятности сообщений канал будет недогружен. Зависимость энтропии от вероятности для бинарного источника иногда называют функцией Шеннона (рис. 40). При большом числе сообщений источника и при равновероятности сообщений они могут быть переданы с помощью равномерного двоичного кода. Так, восемь сообщений кодируются: 000, 001, 010, 011, 100, 101, 110, 111. Энтропия источника равна трем: 
это совпадает со средним числом символов на сообщение. Иногда используется понятие удельной энтропии
, это – энтропия, приходящаяся на один символ. Данный источник имеет энтропию 3 бита на сообщение, можно также сказать, что его энтропия 1 бит/символ. Такая оценка удобна при сравнении различных источников.
Рассмотрим, как можно использовать введенные понятия при вскрытии неопределенности источника.
Пример 1. Пусть, надо отгадать задуманное число от 1 до 32, задавая источнику двоичные вопросы. Так как задуманное число с равной вероятностью может быть любым, энтропия источника Н = log 32 = 5 бит/число. Задаем первый вопрос: Число в нижней половине? Ответ: да. Количество полученной от источника информации I = 1 бит. Энтропия источника уменьшилась и стала Н = 4 бит/число. Задавая подобный вопрос еще раз и получая любой ответ, мы сужаем диапазон поиска вдвое и уменьшаем неопределенность источника на один бит. Таких вопросов и ответов будет ровно пять, после чего энтропия источника будет равна нулю.
Пример 2. Предположим, среди 25 монет одна фальшивая, более легкая. Какое минимальное число взвешиваний на рычажных весах необходимо сделать для нахождения фальшивой монеты?
Прежде всего определяем энтропию источника. Так как весы могут быть в трех состояниях, каждое взвешивание уменьшает энтропию источника на одну троичную единицу информации. Поэтому монеты следует разделить на три примерно равные кучки: 8, 8 и 9 монет. Положив на чашки весов одинаковое число монет 8 и 8, определяем, есть ли среди них фальшивая и, если есть, то в какой чашке. Предположим, что первая кучка легче второй. Значит, монета здесь. Эту кучку делим на три части 3, 3 и 2. Взвешиваем одинаковые части. Допустим, они равны. Значит, искомая монета находится среди двух оставшихся. При третьем взвешивании монета найдена.
Число характеризует число кодовых признаков, используемых при передаче сообщений. Это число определяет алфавит источника. При удельная энтропия источника возрастает. В принципе, такой источник более эффективен, он позволяет передавать больше информации в единицу времени. Так, если алфавит источника равен 32 буквам, то энтропия источника – 5 бит/букву; если в китайском языке используется около 2000 иероглифов, то энтропия такого источника – 11 бит/иероглиф, т.е. 11 бит/символ. Ясно, что использование большого алфавита приводит к техническим сложностям, отсюда, наибольшее распространение в технике получил двоичный алфавит с буквами или символами 0 и 1. Источник, работающий на таком алфавите, не может иметь энтропию больше 1 бит/символ.
Количество и качество информации помимо статистической теории могут характеризоваться также терминами структурной теории, рассматривающей строение массивов информации, а также семантической теории, учитывающей целесообразность, полезность и ценность информации.
Л Е К Ц И Я № 29
Тема:
Текст лекции по дисциплине: «Теория электрической связи»
Г. Калининград 2012 г.
Текст лекции № 30
по дисциплине: «Теория электрической связи»
«Основные понятия теории информации»
Введение
В каналах связи передаётся информация, преобразованная в сигналы.
Для согласования объёма информации с каналом необходимо научиться определять количество информации, подлежащее передаче. Без решения этого вопроса невозможно строить современные системы передачи информации.
Под термином “информация” понимают различные сведения, которые поступают к получателю. В более строгой форме определение информации следующее:
Информация – это сведения, являющиеся объектом передачи, распределения, преобразования, хранения или непосредственного использования.
В дальнейшем нас будут интересовать лишь вопросы, связанные с информацией как объектом передачи.
Сообщение является формой представления информации.
Одно и то же сведение может быть представлено в различной форме. Например, передача голосового сообщения по телефону или изображения по телевизионному каналу. В этом случае мы имеем дело с информацией, представленной в непрерывном виде (непрерывное сообщение ). Будем считать, что это сообщение вырабатывается источником непрерывных сообщений. Либо мы передаем сообщение по телеграфному каналу, в этом случае речь идет об информации, представленной в дискретном виде (дискретное сообщение ). Это сообщение вырабатывается источником дискретных сообщений.
В технических устройствах и системах прием, обработка и передача информации осуществляется с помощью сигналов .
Сигнал (от латинского signum – знак) представляет собой любой процесс, несущий информацию.
Сигналы отражают физические характеристики изучаемых объектов и процессов. Посредством сигналов информация может передаваться на короткие и большие расстояния. Информация в виде сигнала может различным образом перерабатываться, сохраняться, уничтожаться и т. п.
Различают несколько видов сигналов: звуковые , которые можно услышать при работе милицейской сирены; световые , передающие информацию от пульта дистанционного управления к телевизору, а также электрические.
Основное отличие дискретного и непрерывного источников состоит в следующем. Множество всех различных сообщений, вырабатываемых дискретным источником всегда конечно. Поэтому на конечном отрезке времени количество символов дискретного источника так же является конечным. В то же время число возможных различных значений звукового давления (или напряжения в телефонной линии), измеренное при разговоре, даже на конечном отрезке времени, будет бесконечным.
В нашем курсе мы будем рассматривать вопросы передачи именно дискретных сообщений.
Информация, содержащаяся в сообщении, передается от источника сообщений к получателю по каналу передачи дискретных сообщений (ПДС).
| Рис.1. Тракт передачи дискретных сообщений |
Вид передаваемого сигнала определяет тип канала связи.
Понятие информации, постановка задачи её определения.
Какое количество информации содержится, к примеру, в тексте романа «Война и мир», во фресках Рафаэля или в генетическом коде человека? Возможно ли, объективно измерить количество информации?
Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно. В конце 40-х годов XX века один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации, а работы по созданию ЭВМ привели к «объемному» подходу .
Вероятностный подход
Этот подход заключается в том, что понятие «количество информации», основывается на том, что информацию, содержащуюся в сообщении, можно нестрого трактовать в смысле ее новизны или, иначе, уменьшения неопределенности наших знаний об объекте.
При этом понятие «информация » связывается с вероятностью осуществления того или иного события.
Американский инженер Р. Хартли (1928 г.) процесс получения информации рассматривал как выбор одного сообщения из конечного заранее заданного множества из равновероятных сообщений, а количество информации , содержащееся в выбранном сообщении, определял как двоичный логарифм .
Формула Хартли:
Ту же формулу можно представить иначе:
| ; | (1.2) |
Допустим, нужно угадать одно число из набора натуральных целых чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: . То есть сообщение о верно угаданном числе содержит количество информации, приблизительно равное .
Приведем примеры равновероятных сообщений: при бросании монеты: «выпала решка», «выпал орел»; на странице книги: «количество букв четное», «количество букв нечетное».
Определим теперь, являются ли равновероятными сообщения «первой выйдет из дверей здания женщина» и «первым выйдет из дверей здания мужчина». Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.
Для задач такого рода американский ученый Клод Шеннон предложил в 1948г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.
Формула Шеннона:
Если вероятности равны, то каждая из них равна , и формула Шеннона превращается в формулу Хартли.
Анализ формулы показывает, что чем выше вероятность события, тем меньшее количество информации возникает после его осуществления, и наоборот.
Если вероятность равна (т.е. событие достоверно), количество информации равно . Если вероятность свершения или не свершения, какого либо события одинакова, т.е. равна , то количество информации, которое несет с собой это событие, равно .
Это – единица измерения информации. Она получила наименование бит.
Если событие имеет равновероятных исходов, как при подбрасывании монеты или при игре в кости, то вероятность конкретного исхода равна , и формула Шеннона приобретает вид: .
В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из букв и знака «пробел» для разделения слов. По формуле Хартли:
 ;
| (1.4) |
Однако, в словах русского языка (равно как и в словах других языков) различные буквы встречаются неодинаково часто. Ниже приведена таблица вероятностей частоты употребления различных знаков русского алфавита, полученная на основе анализа очень больших по объему текстов.
Воспользуемся для подсчета формулой Шеннона; бит. Полученное значение , как и можно было предположить, меньше вычисленного ранее. Величина ,вычисляемая по формуле Хартли, является максимальным количеством информации, которое могло бы приходиться на один знак.
Таблица . Частотность букв русского языка
| i | Символ | P(i) | i | Символ | P(i) | i | Символ | P(i) |
| Пробел | 0,175 | К | 0,028 | Г | 0.012 | |||
| 0,090 | М | 0,026 | Ч | 0,012 | ||||
| Е | 0,072 | Д | 0,025 | И | 0,010 | |||
| Ё | 0,072 | П | 0,023 | X | 0,009 | |||
| А | 0,062 | У | 0,021 | Ж | 0,007 | |||
| И | 0,062 | Я | 0,018 | Ю | 0,006 | |||
| Т | 0,053 | Ы | 0,016 | Ш | 0.006 | |||
| Н | 0,053 | З | 0.016 | Ц | 0,004 | |||
| С | 0,045 | Ь | 0,014 | Щ | 0,003 | |||
| Р | 0,040 | Ъ | 0,014 | Э | 0,003 | |||
| В | 0,038 | Б | 0,014 | Ф | 0,002 | |||
| Л | 0,035 |
Запомните комбинацию из наиболее повторяющихся букв русского алфавита СЕНОВАЛИТР. Эти знания использовали дешифровальщики при вскрытии тайных переписок в различные исторические периоды.
Аналогичные подсчеты можно провести и для других языков, например, использующих латинский алфавит – английского, немецкого, французского и др. ( различных букв и «пробел»).
Рассмотрим алфавит, состоящий из двух знаков и
. Если считать, что со знаками и
в двоичном алфавите связаны одинаковые вероятности их появления 
, то количество информации на один знак при двоичном кодировании будет равно:
 ;
| (1.5) |
Таким образом бит можно также определить как количество информации, которое содержит один разряд двоичного числа (отсюда название «бит»: b inary digit - двоичный разряд). Другими словами количество информации (в битах), заключенное в двоичном слове, равно числу двоичных знаков в нем.
Один бит - это количество информации, которое переносит один символ источника дискретных сообщений в том случае, когда алфавит источника состоит из двух равновероятных символов.
Количество информации, равное битам, называется байтом.
В восьми разрядах можно записать различных целых двоичных чисел от до . Этого вполне достаточно для представления в двоичной форме информации об алфавитах Русском и Латинском, всех знаках препинания, цифрах от до , арифметических и алгебраических действиях, а так же специальных символов (например § @ $).
Отметим, что создатели компьютеров отдают предпочтение именно двоичной системе счисления потому, что в техническом устройстве наиболее просто реализовать два противоположных физических состояния: некоторый физический элемент, имеющий два различных состояния: намагниченность в двух противоположных направлениях; прибор, пропускающий или нет электрический ток; конденсатор, заряженный или незаряженный и т.п.
Понятие Энтропи́и
впервые введено в 1865 Р. Клаузиусом в термодинамике для определения меры необратимого рассеяния энергии. Энтропия применяется в разных отраслях науки, в том числе и в теории информации как мера неопределенности какого-либо опыта, испытания, который может иметь разные исходы. Эти определения энтропии имеют глубокую внутреннюю связь. Так на основе представлений об информации можно вывести все важнейшие положения статистической физики. [БЭС. Физика. М: Большая российская энциклопедия, 1998].
Эта величина также называется средней энтропией
сообщения. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины .
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других.
В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки теории информации, которая использует понятие вероятности. Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.
В случае равновероятных событий (частный случай), когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов и формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, как один из научных подходов к оценке сообщений:
, где I – количество передаваемой информации, p – вероятность события, N – возможное количество различных (равновероятных) сообщений.Задание 1. На равновероятные события.
В колоде 36 карт. Какое количество информации содержится в сообщении, что из колоды взята карта с портретом “туз”; “туз пик”?
Вероятность p1 = 4/36 = 1/9, а p2 = 1/36. Используя формулу Хартли имеем:
Ответ: 3.17; 5.17 бит
Заметим (из второго результата), что для кодирования всех карт, необходимо 6 бит.
Из результатов также ясно, что чем меньше вероятность события, тем больше информации оно содержит. (Данное свойство называется монотонностью
)
Задание 2. На неравновероятные события
В колоде 36 карт. Из них 12 карт с “портретами”. Поочередно из колоды достается и показывается одна из карт для определения изображен ли на ней портрет. Карта возвращается в колоду. Определить количество информации, передаваемой каждый раз, при показе одной карты.
