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

по мотивами учебного пособия «Теория информации» Блинова И.В., Попов И.Ю. (университет ИТМО — 2018)

Что изучает теория информации

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

Задачи теории информации:

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

[свернуть]
Энтропия

Энтропия

1. Информация — это совокупность сведений о каких-либо событиях, процессах, явлениях. Передают информацию в виде сообщений.

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

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

4. Степень неопределенности системы характеризуется количеством различных возможных состояний. Пример, если продолжительность лабораторной работы колеблется от 1 часа до 2-х, то  множество состояний системы (окончания работы) это 1 час, 1 час 1 минут, 1 час 2 минут и т.д. до 2 часов.

5. После получения сведений степень неопределенности может быть уменьшена. Чем больше будет получено полезных сведений, тем меньше становится неопределенность системы.

6. Энтропия — мера неопределенности системы. Энтропия — это то, как много нам неизвестно о системе. Чем более неопределенна система, тем больше энтропия. Общая формула для любой энтропии:

 H(X)=-\sum_{i=1}^{n} p_{i}log_{a} p_{i},

H (X) — энтропия;  n — количество разных состояний; pi — вероятность каждого из этих состояний;

а — основание логарифма может быть любым (большим 1), но на практике мы будем принимать равным 2;

 так как в теории информации договорились, что основание логарифма всегда равно 2,

то в записи решили использовать упрощение — основание логарифма не пишется,

но всегда подразумевается, что оно равно 2.

7. Значение вероятности любого события pi находится на отрезке [0;1].

8. За единицу измерения энтропии принимается 1 бит.

  • 8 бит = 1 байт;
  • 1024 байт=210 байт= 1килобайт=1Кб;
  • 1024 Кб =1 Мб = 1 мегабайт = 210 килобайт = 220 байт;
  • 1024 Мб =1 Гб = 1 гигабайт = 210 мегабайт = 220 килобайт = 230 байт;
  • 1024 Гб =1 Тб = 1 терабайт = 210 гигабайт = 220 мегабайт = 230 килобайт; 240 байт.

9. Если система может принимать 2 равновероятных события, то вероятность каждого равна \frac {1}{2}. Тогда,  энтропия

H(X)=-\frac{1}{2}log_{2}\frac{1}{2}-\frac{1}{2}log_{2}\frac{1}{2}=1.

10. Если система может принимать n равновероятных событий, то вероятность каждого равна \frac{1}{n}. Тогда, энтропия

H(X)=-\frac{1}{n}log_{2}\frac{1}{n}-...-\frac{1}{n}log_{2}\frac{1}{n} (n одинаковых членов), упростим:

H(X)=-n\frac{1}{n}log_{2}\frac{1}{n}=log_{2}n

(формула энтропии справедлива только для систем с равновероятными событиями)

То есть, энтропия системы с равновероятными состояниями равна логарифму количества состояний.

11. Свойства энтропии:

  • если все состояния любой системы известны, то ее энтропия равна 0, так как из всех вероятностей только одна равна 1 (остальные 0):

H(X)=p_{i}log_{2}p_{i}=1\cdot log_{2}1=0 (логарифм 1 равен 0).

  • если все состояния системы с конечным множеством состояний равновероятны, то энтропия этой системы максимальна.

12. Энтропия сложной системы:

H(X, Y)=-\sum_{i=1}^{n} \sum_{j=1}^{m} p_{ij}log p_{ij},

H (XY) — энтропия систем Х и  Y; n — количество разных состояний системы X; m — количество разных состояний системы Y;

pij — вероятность каждого из состояний систем Х и Y .

13. Если системы X и Y независимы, то вероятность их событий находится перемножением. Их энтропии склfдываются: H(X, Y)= H(X)+H(Y).

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

15. Частная условная энтропия системы Y — это энтропия систем Y, при условии что система Х находится в определенном состоянии, при этом системы X и Y зависимы: H(Y/xi).

16. Полная условная энтропия  системы Y — энтропия системы Y, при условии что система Х полностью определена: H(Y/X):

H(Y/x_{i})=\sum_{i=1}^{n}p_{i}\cdot H(Y/x_{i}).

17. Теорема об энтропии объединения зависимых систем:

  • если две системы X и Y объединить в одну систему, то энтропия объединенной системы равна энтропии одной из ее частей плюс условная энтропия второй части относительно первой: H(X,Y)= H(X)+H(Y/X).

18. Полная условная энтропия H(Y/X) не может превосходить безусловную H(Y).

19. Вероятность сложной системы может быть найдена по формуле pij=pi•p(yj/xi).

20. Степень неопределенности системы не может увеличиваться от того, что состояние какой-то другой системы стало известным.

21. Энтропия сложной системы достигает максимума когда ее составные части независимы.

22. Если состояние одной системы (Х) полностью определяет состояние другой системы (Y), то H(Y/X)=0 и H(X,Y)=H(X).

23. Если состояние каждой из систем Х и Y однозначно определяет состояние другой системы, (системы эквивалентны), то H(X,Y)=H(X)=H(Y).

24. Энтропия каждой последующей системы определяется только после того, как определены состояния всех предыдущих.

[свернуть]
Образцы решения задания по теме "Энтропия"

Пример 1.

Найти энтропию системы X, вероятности состояний которой заданы законом распределения: p1=0,1; p2=0,4; p3=0,8. 

Решение.

Используем формулу: H(X)=-\sum_{i=1}^{n} p_{i}log_{a} p_{i}.

H(X)=-0,1log20,1-0,4log20,4-0,8log20,8= 0,332+0,528+0,2576=1,1176.

Ответ: 1,1176.


Пример 2.

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

  • рассмотрим техническое устройство как систему X, которая может находиться в нескольких состояниях.
  • общее количество состояний найдем по формуле: 24=16;
  • энтропия максимальна, если все состояния равновероятны;
  • энтропия системы с равновероятными событиями: H(X)=log_{2}n = log216 = 4 бит.

Ответ: 4.


Пример 3.

Написать функцию H(Х), определяющую энтропию системы с 4 состояниями. Чему равно наибольшее значение этой функции?
Решение.

  • рассмотрим систему X с тремя состояниями x1, x2, x3,x4; вероятности состояний: p1, p2, p3, 1 − (p1 + p2+p3);
  • энтропия такой системы равна: H(Х) = −p1 log2p1 − p2 log2p2 -p3logp3− (1 − p1 — p2 — p3) log2(1 − p1 — p2-p3) — это искомая функция;
  • энтропия системы максимальна, если состояния системы равновероятны; энтропия системы с равновероятными событиями равна логарифму числа состояний: H(X)=log24=2.

Пример 4.

Имеются две урны. В первой – 3 красных, 5 белых шаров. Во второй – 6 красных и 7 белых шаров. Из каждой урны берут по два шара. Исход какого из двух опытов следует считать более неопределенным?

Решение.

1. Рассмотрим первый опыт, извлечение двух шаров из первой урны, как систему X с тремя исходами:

  • 1 случай (достаем два красных шара), вероятность: \frac{3}{8}\cdot \frac{2}{7}=\frac{3}{28};
  • 2 случай (достаем два белых шара), вероятность: \frac{5}{8}\cdot \frac{4}{7}=\frac{5}{14};
  • 3 случай (достаем красный и белый шары), вероятность: \frac{3}{8}\cdot \frac{5}{7}+\frac{5}{8}\cdot \frac{3}{7}=\frac{15}{28}.
  • энтропия первой системы (первой урны): -\frac{3}{28}log_{2}\frac{3}{28}-\frac{5}{14}log_{2}\frac{5}{14}-\frac{15}{28}log_{2}\frac{15}{28}= 0,345+0,530+0,482=1,357 бит.

2. Рассмотрим второй опыт, извлечение двух шаров из второй урны, как систему Y с тремя исходами:

  • 1 случай (достаем два красных шара), вероятность: \frac{6}{13}\cdot \frac{5}{12}=\frac{5}{26};
  • 2 случай (достаем два белых шара), вероятность: \frac{7}{13}\cdot \frac{6}{12}=\frac{7}{26};
  • 3 случай (достаем красный и белый шары), вероятность: \frac{6}{13}\cdot \frac{7}{12}+\frac{7}{13}\cdot \frac{6}{12}=\frac{7}{13}.
  • энтропия первой системы (первой урны): -\frac{5}{26}log_{2}\frac{5}{26}-\frac{7}{26}log_{2}\frac{7}{26}-\frac{7}{13}log_{2}\frac{7}{13}= 0,4575+0,51+0,481=1,4485 бит.

3. Сравниваем значения энтропий. Энтропия второго опыта больше, то есть неопределенность второй системы выше.


Пример 5.

Прогноз погоды информирует, что 1 мая будет дождь с вероятностью 0,25, а вероятность того, что дождя не будет 0,75. Вероятность же дождя здесь 15 мая равна 0,8, вероятность снега в эту же дату – 0,1, а вероятность того, что осадков не будет – 0,1. В какой из перечисленных дней погоду следует считать более неопределенной?
Решение.

Решим задачу при уточненных условиях:

  • первый случай: характер осадков не интересен, важен сам факт их наличия или отсутствия (тогда для каждого дня нужно рассмотреть системы с двумя состояниями — есть осадки/ нет осадков);
  • второй случай: важно учесть и характер осадков (тогда для каждого дня рассматриваем систему с тремя состояниями — нет осадков / идет снег/ идет дождь).

Первый случай.

Рассмотрим опыт по выяснению погоды систему X с двумя состояниями:

  • энтропия погоды 1 мая: H(X)=-(0,25log20,25+0,75log20,75)=0,5+0,311=0,811 бит;
  • энтропия погоды 15 мая: H(X)=-(0,8log20,8+0,2log20,2)=0,2576+0,4644=0,722 бит;
  • энтропия 1 мая больше, то есть неопределенность погоды 1 мая выше.

Второй случай.

Рассмотрим опыт по выяснению погоды систему X с тремя состояниями:

  • энтропия погоды 1 мая: H(X)=-(0,25log20,25+0,75log20,75)=0,5+0,311=0,811 бит;
  • энтропия погоды 15 мая: H(X)=-(0,8log20,8+0,1log20,1+0,1log20,1)=0,2576+0,332+0,332=0,9216 бит;
  • энтропия 1 мая меньше, то есть неопределенность погоды 15 мая выше.

Пример 6.

Заданы вероятности состояний независимых систем X и Y:

  • для системы Х вероятности: p1=0,1; p2=0,2; p3=0,3;
  • для системы Y вероятности: p1=0,2; p2=0,3; p3=0,4.

Найти энтропию объединенной системы (X, Y ).

Решение:

  • найдем энтропию системы Х: H(X)=-(0,1log20,1+0,2log20,2+0,3log20,3)=0,332+0,464+0,522=1,318 бит;
  • найдем энтропию системы Y: H(X)=-(0,2log20,2+0,3log20,3+0,4log20,4)=0,464+0,522+0,528=1,514 бит;
  • энтропия объединенных независимых систем находится как сумма их энтропий: H(X,Y)=1,318+1,514=2,832 бит.

Пример 7.

Системы X и Y зависимы. Совместное распределение их вероятностей  показано ниже. Найти энтропию объединенной системы.

  • p11=0,1; p12=0,2; p21= 0,3; p22= 0,4.

Решение:

  • H(X,Y)=-(0,1log20,1+0,2log20,2+0,3log20,3+0,4log20,4)=0,332+0,464+0,522+0,528=1,846 бит.

Пример 8.

Сложная система (X, Y ), задана таблицей:

х1 х2 х3 х4
у1 0,1 0,21 0,3 0,45
у2 0,02 0,3 0,04 0,01

Найти полную условную энтропию H(Y/X) и частную энтропию H(Y/xi), i=1,2,3,4.

Решение.

  • составим таблицы вероятностей для систем X и Y, для системы Х сложим данные по столбикам, для системы Y сложим данные по строкам:
    • для системы Х: р1=0,12; р2 = 0, 51; р3 = 0,34; р4=0,46;
    • для системы  Y: p1 = 1,06 ;p2 = 0,37.
  • используем формулу вероятности сложной системы: pij=pi•p(yj/xi), найдем условные вероятности p(yj/xi)=pij/pi:
    • p(y1/x1)=\frac{0,1}{0,12}=\frac{5}{6}; p(y2/x1)=\frac{0,02}{0,12}=\frac{1}{6};
    • p(y1/x2)=\frac{0,21}{0,51}=\frac{7}{17}; p(y2/x2)=\frac{0,3}{0,51}=\frac{1}{17};
    • p(y1/x3)=\frac{0,3}{0,34}=\frac{3}{34}; p(y2/x3)=\frac{0,04}{0,34}=\frac{2}{17}; 
    • p(y1/x4)=\frac{0,45}{0,46}=\frac{45}{46}; p(y2/x4)=\frac{0,01}{0,46}=\frac{1}{46};
    • найдем энтропию H(Y/x1)= -(\frac{5}{6}log_{2}\frac{5}{6}+\frac{1}{6}log_{2}\frac{1}{6})=0,2192+0,431=0,65 бит;
    • найдем энтропию H(Y/x2)= -(\frac{7}{17}log_{2}\frac{7}{17}+\frac{1}{17}log_{2}\frac{1}{17})=0,527+0,24=0,767 бит;
    • найдем энтропию H(Y/x3)=-(\frac{3}{34}log_{2}\frac{3}{34}+\frac{2}{17}log_{2}\frac{2}{17})=0,3088+0,363=0,6718 бит;
    • найдем энтропию H(Y/x4)= -(\frac{45}{46}log_{2}\frac{45}{46}+\frac{1}{46}log_{2}\frac{1}{46})=0,031+0,12=0,151 бит;
    • тогда, полная условная энтропия H(Y/X)= 0,12•0,65+0,51•0,767+0,34•0,6718+0,46•0,151=0,078+0,39117+1,0118+0,06946=1,55 бит.

Пример 9.

Опыт X состоит в извлечение двух шаров из урны, содержащей 7 красных и 4 белых шаров. Опыт Y — в извлечение из той же урны еще одного шара. Чему равна энтропия H(Y) опыта Y и условная энтропия H(Y/X) этого опыта?

Решение.

  • рассмотрим опыт X, как систему с тремя исходами. Вероятности исходов:
    • 1 случай (достаем два красных шара), вероятность: \frac{7}{11}\cdot \frac{6}{10}=\frac{21}{55};
      • в этом случаем вероятность для опыта Y достать тоже красный шар = \frac{5}{9};
      • а вероятность для опыта Y достать белый шар = \frac{4}{9}
    • 2 случай (достаем два белых шара), вероятность: \frac{4}{11}\cdot \frac{3}{10}=\frac{6}{55};
      • в этом случае вероятность для опыта Y достать красный шар = \frac{7}{9};
      • а вероятность достать в опыте Y белый шар = \frac{2}{9};
    • 3 случай (достаем красный и белый шары), вероятность: \frac{7}{11}\cdot \frac{4}{10}+\frac{4}{11}\cdot \frac{7}{10}=\frac{28}{55};
      • в этом случае вероятность для опыта Y достать красный шар = \frac{6}{9}=\frac{2}{3};
      • а вероятность в опыте Y достать белый шар = \frac{3}{9}=\frac{1}{3}.
  • найдем условные энтропии:
    • H(Y/x1)=-(\frac{5}{9}log_{2}\frac{5}{9}+\frac{4}{9}log_{2}\frac{4}{9})=0,47+0,52=0,99;
    • H(Y/x2)=-(\frac{7}{9}log_{2}\frac{7}{9}+\frac{2}{9}log_{2}\frac{2}{9})=0,282+0,482=0,764;
    • H(Y/x3)=-(\frac{2}{3}log_{2}\frac{2}{3}+\frac{1}{3}log_{2}\frac{1}{3})=0,39+0,528=0,918;
  • тогда, H(Y/X)=-(\frac{21}{55}\cdot 0,99+\frac{6}{55}\cdot 0,764+\frac{28}{55}\cdot 0,918)=0,378+0,083+0,467=0,928 бит.

Пример 10.

В условиях примера 9 найти энтропию H(X) опыта X и условную энтропию H(X/Y ) этого опыта.
Решение.

  • по известному правилу (смотри теорию по теме «Энтропия», имеем

H(X, Y ) = H(X) + H(Y/X) и H(X, Y ) = H(Y ) + H(X/Y ), то H(X)+H(Y/X) = H(Y )+H(X/Y).

  • следовательно, получим H(X/Y ) = H(X) + H(Y/X) − H(Y );
  • найдем H(X)=-(\frac{21}{55}log_{2}\frac{21}{55}+\frac{6}{55}log_{2}\frac{6}{55})+\frac{28}{55}log_{2}\frac{28}{55})= 0,53+0,349+0,496=1,375 бит.
  • найдем энтропию опыта Y (отдельно от любых событий опыта X) H(Y)= -(\frac{7}{11}log_{2}\frac{7}{11}+\frac{4}{11}log_{2}\frac{4}{11})=0,415+0,531=0,946бит;
  • тогда, H(X/Y ) = H(X) − H(Y ) + H(Y/X) = 1,375- 0,946+0,928=1,357 бит.

[свернуть]
Измерение информации

Измерение информации

1. Количество информации о системе измеряется уменьшением ее энтропии. Количество информации системы Х обозначим I(X) (полная информация).

2. Если после получения информации система становится полностью определена, то ее энтропия равна 0. А вся полученная информация равна первоначальной энтропии системы:

I(X)=H(X)=-(p1log2p1+…+pnlog2pn)

H (X) — энтропия;  n — количество разных состояний; pi — вероятность каждого из этих состояний;

в записи решили использовать упрощение — основание логарифма не пишется,

но всегда подразумевается, что оно равно 2.

3. Если все состояния равновероятны, то каждый отдельный элемент I(xi)=-log2pi — частная информация, получаемая от отдельного сообщения.

4. Свойства информации:

  • полная и частная информация не могут быть отрицательными;
  • если все возможные ситуации равновероятны, то частная информация равна полной информации I(xi)=I(X)=log2n;
  • если состояния обладают разными вероятностями, то информация, получаемая от разных сообщений, неодинакова;
  • наибольшую информацию несут сообщения о наименее вероятных событиях.

5. Сведения о системе Х можно получить через систему Y, тогда, данные могут быть менее точным. Причины:

  • в системе Y данные были округлены;
  • не все состояния системы Х представлены в системе Y;
  • ошибки при передаче сигнала из-за помех.

6. Если система Х и система Y различны, то I(X,Y)=H(X)-H(X/Y) — полная информация о системе Х, содержащаяся в системе Y.

7. Теорема: информация о системе Х через систему Y равна информации о системе Y через систему Х. Т.е. из двух систем каждая содержит относительно другой одну и ту же информацию: I(X,Y)=I(Y,X).

8. Если Х и Y независимы, то H(Y/X)=H(Y) и I(X,Y)=0, то есть полная взаимная информация, содержащаяся в независимых системах равна 0. Нельзя получить сведения о системе Х из абсолютно независимой от нее системы Y.

9. Если состояние системы X полностью определяет состояние системы Y и наоборот, системы эквивалентны, тогда H(X) = H(Y ) и H(X/Y ) = H(Y/X) = 0. Следовательно, I(X, Y ) = I(X) = I(Y ) = H(X) = H(Y ).

10. Если состояние системы Y полностью определяет систему Х (система Х является подчиненной), то говорят, что есть строгая односторонняя зависимость. В этом случае, Н(Х/Y)=0 и I(X,Y)=H(X).

11. В общем случаем для двух объединенных систем полная взаимная информация находится следующим образом: I(X,Y)=H(X)+H(Y)-H(X,Y). 

12. Частная информация о системе Х через конкретное состояние системы Y/

[свернуть]
Решение задач по теме "Измерение информации"

Пример 1.

Ребенок съезжает с горы на велосипеде без падения с вероятностью 0, 88. Какое количество информации мы получим, узнав, что ребенок упал на склоне?
Решение.

  • рассмотрим ребенка, как систему X с двумя состояниями: р1 =0,88; р2 = 0,12;
  • тогда, I(X)=-log20,12=3,059 бит.

Пример 2.

Игрок наудачу бросает два игральных кубика. Какое количество информации при этом получает игрок?
Решение.

  • изначально исход броска абсолютно неизвестен, то есть энтропия максимальна;
  • всего различных равновероятных состояний 36 (количество состояний находим как 6•6=35);
  • тогда, I(X) = log2 36 = 5, 1699 бит.

Пример 3.

Из колоды в 36 карт наудачу берут две карты. Найти частную информацию из сообщения: «выпали дама, король».
Решение:

  • ситуации, подходящие условию задачи: ДК+КД;
  • вероятность их выпадения: \frac{4}{36}\cdot \frac{4}{35}+\frac{4}{36}\cdot \frac{4}{35}=\frac{8}{315}
  • частная информация в этом случае равна: I(xi) = − log pi = − log p (8/315)=5,299 бит.

Пример 4.

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

Решение:

  • количество информации будет максимальным, если события попал/не попал будут равновероятны;
  • вероятность не попал: 1-0,15=0,85;
  • составим формулы для вычисления вероятностей события «не попал» для произвольного выстрела k: 0,85•0,85•…0,85 = 0,85k;
  • тогда, вероятность «попал»: 1-0,85k;
  • так как нужны равные вероятности, то приравниваем выражение для вероятность попадания и промаха k-выстрелом: 1-0,85k=0,85k, то есть

1=2•0,85k

0,85k=0,5

k=log2(0,5/0,85)≈4.

[свернуть]