Файл: А.В. Бирюков Энтропия, информация, кодирование.pdf

1

1. ЭНТРОПИЯ Энтропия служит количественной характеристикой степени не-

определенности значения случайной величины. Для дискретной случайной величины, принимающей N значений с вероятностями Pk (k = 1, 2, …, N), энтропия определяется формулой

H = - (P1LP1 + … + PnLPn),

где символом L обозначены логарифмы по основанию 2.

Поскольку Pk ≤ 1, то H ≥ 0. При фиксированном числе слагаемых энтропия имеет наибольшее значение H = 1 для равномерного распределения вероятностей. Поэтому в общем случае 0 ≤ H ≤ 1. Нулевую энтропию имеет лишь вырожденное распределение, когда одна из вероятностей равна единице, а остальные равны нулю.

При вычислении энтропии можно пользоваться приведенной ниже таблицей двоичных логарифмов (табл. 1.1) для чисел от 3 до 32.

Таблица 1.1

Понятие энтропии является весьма продуктивным при изучении графов. Пусть имеется граф A (n, m) с n вершинами и m ребрами. Рассмотрим все его подграфы третьего порядка, число которых N равно числу сочетаний из n элементов по 3.

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

Обозначим через N1, N2, N3, N4 число подграфов каждого вида, содержащихся в графе A(n, m), и рассмотрим отношения

2

P1 = NN1 , P2 = NN2 , P3 = NN3 , P4 = NN4 ,

которые являются вероятностями встречи каждого подграфа в графе A(n, m). Этому распределению соответствует энтропия

H = - 0,5 (P1LP1 + … + PnLPn),

называемая энтропией графа A(n, m). Она служит характеристикой алгоритмической сложности описания данного графа.

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

Рассмотрим конкретные примеры. Пусть имеется граф пятого порядка, у которого вероятность смежности вершин равна 1/2. Поскольку у полного графа пятого порядка число ребер равно 10, то у случайного графа с указанным свойством число ребер всреднем равно 5. Все графы вида A (5, 5) изображены на рис. 1.2.

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

Найдем энтропию графов A(8, 12) и A(6, 12), соответствующих платоновым телам – кубу и октаэдру. Напомним, что гранями октаэдра являются 8 правильных треугольников, а степень каждой вершины равна 4.

3

Легко видеть, что для куба P1 = 0, P2 = P3 = 3/7, P4 = 1/7, а для октаэдра P1 = P2 = 2/5, P3 = 0, P4 = 1/5. Соответствующие значения энтропии составляют H = 0,72 и H = 0,76.

Упражнения.

Найти энтропию всех графов четвертого порядка (рис. 1.3).

2. ИНФОРМАЦИЯ

Рассмотрим два опыта E и F со случайными исходами Ek и Fk и соответствующими вероятностями этих исходов P(Ek), P(Fk), где k = 1, 2, …, N. Каждому из этих опытов соответствует его энтропия (мера неопределенности исхода).

Сложный опыт, состоящий в одновременном наблюдении за исходами обоих опытов, имеет больше исходов и, следовательно, обладает большей неопределенностью исхода. Если опыты E и F независимы, т.е. исходы одного не зависят от исходов другого, то энтропия сложного опыта равна сумме энтропий H(E) + H(F).

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

P(Ek, Fi) = P(Fi, Ek),

где k, i = 1, 2, …, N. Для зависимых опытов условная энтропия опыта E при условии, что произошло событие Fi, равна H (E, Fi).

Усредняя по всем значениям индекса, получим условную энтропию сложного опыта, равную

H (E, F) + H (F)

При этом очевидна справедливость неравенства

4

0 ≤ H (E, F) ≤ H (E).

В силу взаимной зависимости случайных событий

H (E, F) = H (F, E) + H (E) - H (F).

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

Приведем следующий пример. Опыты E и F состоят в последовательном извлечении двух шаров из урны, содержащей 2 черных и 3 белых шара. При этом E – извлечение первого шара, F – извлечение второго шара. Требуется найти безусловные и условные энтропии опытов.

Пусть события E1, E2 состоят в появлении соответственного черного и белого шара в опыте E, а F1 и F2 – в появлении черного и белого шара в опыте F. Пока ничего не известно об исходах опытов, можно ожидать осуществление событий с вероятностями

P(E1 ) = P(F1 ) = 52 , P(E2 ) = P(F2 ) = 53 .

Тогда безусловные энтропии опытов одинаковы и равны

H (E ) = H (F ) = 0,971 .

Если известен исход опыта E, то вероятности исходов опыта F будут иметь другие значения: P(F1, E1) = 0,25; P(F2, E1) =

= 0,75; P(F1, E2) = 0,5; P(F2, E2) = 0,5

Отсюда условные энтропии имеют значения H (F, E1) = 0,811; H (F, E2) = 1 или всреднем H (F, E) = 0,905.

Следовательно, известный исход опыта E уменьшает энтропию опыта F на величину 0,971-0,905 = 0,066.

В общем случае разность энтропий

I (E, F) = H (F) – H (F, E)

называется информацией относительно опыта F, содержащейся в опыте E. Из определения информации следует, что

I (E, F) = I (F, E)

Приведем следующий пример. Пусть имеются графы A(8, 12) и A(8, 11), соответствующие полному кубу и кубу с удаленным ребром. Выше (п.1) была найдена энтропия графа A(8, 12), равная 0,72. Найдем энтропию графа A(8, 11), у которого общее число подграфов третьего порядка такое же, как и у графа A(8, 12), т.е. равно 56, а число подграфов каждого из четырех видов (рис. 1.1) равно 0, 14, 22, 20, что дает распределение вероятностей, энтропия которого равна 0,78. Следовательно, дополнение графа А(8, 11) до графа А(8, 12) присоединением одного ребра вносит информацию, равную 0,78 - 0,72 = 0,06.

5

Упражнения.

Имеется полный граф четвертого порядка (квадрат с диагоналями). Как и у любого полного графа, его энтропия равна нулю. Требуется найти информацию, которую вносит удаление из данного графа 1) одного ребра, 2) двух ребер, 3) трех ребер (рис. 2.1).

3.КОДИРОВАНИЕ

Втехнике связи правило, сопоставляющее каждому передаваемому сообщению определенную последовательность единиц (посылка тока) и нулей (пауза), называется двоичным кодом. Рассмотрим передачу сообщений с помощью десяти цифр 0, 1, 2, …, 9, записанных в двоичной системе счисления:

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

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

Приведем соответствующий пример. Пусть имеется сообщение, записанное цифрами 12345678. Переведем это сообщение в двоичный код при m=1, т.е. закодируем каждую цифру в отдельности:

11011100101110111100.

6

Этот код содержит 13 единиц и 8 нулей. Следовательно, вероятности встречи единицы и нуля равны соответственно 13/21 и 8/21

Энтропия этого распределения равна

Перевод двухзначных чисел в двоичную систему дает последовательность:

11001001001110001001110.

Здесь 11 единиц и 12 нулей, что соответствует вероятностям 11/23 и 12/23. Найдем энтропию этого распределения:

Таким образом, разбиение сообщения на блоки по две цифры увеличило информацию на величину 0,998 - 0,959 = 0,039.

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

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

Таблица 3.1