Комбинаторный подход к вычислению количества

Информации. Формула Хартли

 

Обозначим через I количество информации, n – число состояний физической системы, тогда I = I (n) – функция количества информации. И повторим рассуждения Р.Хартли, позволившие ему получить меру количества информации. Предварительно примем, что информация – это устраненная неопределенность.

Предположим, что какое-то событие имеет m равновероятных исходов. Таким событием может быть, например, появление любого символа из алфавита, содержащего m таких символов. Как измерить количество информации, которое может быть передано при помощи такого алфавита? Это можно сделать, определив число N возможных комбинаций букв алфавита, то есть число возможных сообщений, которые могут быть переданы при помощи этого алфавита. Если сообщение формируется из одного символа, то N = m, если из двух, то N = m ². Если сообщение содержит n символов (n – длина сообщения), то N = mⁿ. Казалось бы, искомая мера количества информации найдена. Ее можно понимать как меру неопределенности исхода опыта, если под событием подразумевать случайный выбор какого-либо сообщения из некоторого числа возможных. Однако эта мера не совсем удобна. При наличии алфавита, состоящего из одного символа, т.е. когда m = 1, возможно появление только этого символа. Следовательно, неопределенности в этом случае не существует, и появление этого символа не несет никакой информации. Между тем, значение N при m = 1 не обращается в нуль. Для двух независимых источников сообщений (или алфавита) с N ₁ и N ₂ числом возможных сообщений общее число возможных сообщений , в то время как логичнее было бы считать, что количество информации, получаемое от двух независимых источников, должно быть не произведением, а суммой составляющих величин.

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

. (1.1)

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

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

Аксиомы теории информации

1. Мера неопределенности есть непрерывная функция вероятности исходов некоторого опыта.

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

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

 

Вероятностный подход к вычислению количества

Информации. Формула Шеннона. Понятие об энтропии

Пример. Рассмотрим кодирование оптимальным неравномерным кодом дискретной системы с восемью не равновероятными состояниями.Такой пример нам нужен для дальнейшего объяснения подхода Шеннона к определению количества информации.

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

Таблица кодирования состояний такой системы неравномерным оптимальным кодом (его еще называют кодом Шеннона-Фано) представлена ниже.

 

xi	pi		Двоичные знаки	Кодовое слово
	¼	2^-2
	¼	2^-2
	1/8	2^-3
	1/8	2^-3
	1/16	2^-4
	1/16	2^-4
	1/16	2^-4
	1/16	2^-4

 

Правило кодирования:

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

2) в свою очередь каждая из групп разбивается на две по такому же принципу;

3) операцию продолжают до тех пор, пока в каждой группе не останется по одному символу;

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

Обратите внимание на третий столбец, он вспомогательный, но очень важный для дальнейших выводов. Показатель степени соответствует числу знаков (количеству разрядов) в кодовом слове. То есть, как видим из таблицы, состояние источника с вероятностью вида 2 ^-k имеет кодовое слово с числом знаков k.

Вывод формулы Шеннона

Рассмотрим ряд чисел , где i = 1,.., n, а m_i – целые положительные числа, такие что .

Для кодового слова длиной m_i меру неопределенности закодированного состояния можно представить в виде:

_.

Для примера, приведенного в таблице, мера неопределенности будет равна:

– среднее количество знаков в кодовом слове (математическое ожидание).

Если взять не двоичную систему счисления, а систему счисления с основанием a, то для ряда чисел , закодированных кодовыми словами длиной m_i меру неопределенности закодированного состояния можно представить в виде:

_.

Если опять обратимся к таблице, то увидим, что – это вероятность состояния, закодированного кодовым словом длиной m_i, то есть p_i. При этом .

Поэтому, выражение для неопределенности (1.1) Шеннон записал, объединив формулу для любой системы счисления и получил:

,

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

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

 

исходы опыта	А 1	А 2	А 3	…	Аk
вероятности				…		(1.2)

 

меранеопределенностиравна

и называется энтропией опыта (или дискретного распределения (1.2). Напомним, что .

Итак, энтропия – это среднее количество информации, приходящееся на один исход опыта (для дискретных систем).

Аналогичная (1.3) формула имеет место и при в предположении сходимости соответствующего ряда.

Наряду с энтропией дискретного распределения рассматривается также и энтропия непрерывной случайной величины, которая определяется формулой

, (1.4)

где – плотность распределения вероятностей. В предположении сходимости интеграл (1.4) является мерой неопределенности непрерывной случайной величины.