- •Теория информационных процессов и систем
- •Лекции читает канд.техн.наук, доцент Литвинов Владислав Леонидович
- •Энтропия и ее свойства
- ••Пусть информационная система может порождать ансамбль
- ••Энтропия не зависит от конкретного сообщения. Это характеристика информационной системы (источника сообщений или
- •Свойства энтропии
- •• Раскроем неопределенность вида 0∙∞ по правилу Лопиталя.
- •2.Энтропия - величина неотрицательная и ограниченная.
- •3.Энтропия системы, имеющей m равновероятных состояний, максимальна и равна log2m.
- ••Следовательно, при двух символах в алфавите максимум энтропии достигается в случае равновероятных символов.
- •4.Совместная энтропия независимых источников сообщений равна сумме энтропий.
- •Условная энтропия
- ••Пусть источник А порождает ансамбль Na сообщений (a1, a2,…, aNa), источник B порождает
- •• В первом слагаемом индекс j имеется только у B, изменив порядок
- ••Если ввести данное понятие и использовать его обозначение, то второе слагаемое будет иметь
- ••Полученное выражение представляет собой общее правило нахождения энтропии сложной системы. Совершенно очевидно, что
- •Энтропия непрерывных сообщений
- •Относительная энтропия
- ••Одно и то же количество информации I(s) может содержаться в
- •Количественные характеристики источника сообщений
- ••Экономичность источников информации
- ••Очевидно, что троичный алфавит является более экономичным, чем двоичный. Именно поэтому в истории
- ••Производительность источника сообщений
- •Вопросы и задачи к главе
- •3.Бросаются одновременно две игральные кости. Определить количество информации, содержащееся в сообщении о том,
- •5.Имеются два ящика, в каждом из которых по 12 шаров. В первом –
- ••Какое количество информации требуется, чтобы узнать исход броска монеты?
- ••Игра «Угадайка–4». Некто задумал целое число в интервале от 0 до 3. Наш
- •Таким образом, для решения задачи оказалось достаточно двух вопросов независимо от того, какое
- ••В Белгороде 28000 жителей. Какое минимальное количество вопросов, требующих ответа "да" или "нет",
- ••Эллочка-Людоедка знает 20 слов. В обычном состоянии она произносит в среднем 50 слов
- ••В буфере ИС ожидают обработки 6 заданий. 2 из них запрашивают дополнительный ресурс
- ••Какими свойствами обладает логарифмическая мера информации?
Теория информационных процессов и систем
Кафедра информационных управляющих систем
Лекции читает канд.техн.наук, доцент Литвинов Владислав Леонидович
Энтропия и ее свойства
•Энтропия – мера неопределенности случайного состояния некоторой системы.
•Мы рассматриваем информационные системы, то есть системы, воспринимающие, хранящие, перерабатывающие и использующие информацию. Нормальное функционирование подобных систем – это прием-передача информационных сообщений.
•Для целей теории информации мы определим энтропию как среднее количество информации, приходящееся на одно сообщение в ансамбле сообщений (или на один символ в отдельном сообщении). Иначе говоря, энтропия – это математическое ожидание количества информации в сообщении.
•Пусть информационная система может порождать ансамбль
(алфавит) сообщений a1, a2,…,am. Вероятности каждого сообщения: P(a1), P(a2), …,P(am). Так как вероятности сообщений не одинаковы, то они несут разное количество информации.
•I(ai) = - log2 P(ai).
•Среднее количество информации (математическое ожидание):
• |
m |
m |
|
(8) |
H(a) M I(a) P(ai ) I(ai ) P(ai ) log2 |
P(ai ) |
|||
|
i 1 |
i 1 |
|
|
• |
Совершенно аналогично вводится энтропия сообщений: |
m
H pi log2 pi
i 1
•Энтропия не зависит от конкретного сообщения. Это характеристика информационной системы (источника сообщений или канала передачи сообщений).
•Энтропия в таком виде является априорной характеристикой и может быть вычислена до эксперимента, если известна статистика сообщений.
•Энтропия характеризует неопределенность ситуации до передачи сообщения, поскольку заранее не известно, какое сообщение из ансамбля будет передано. Чем больше энтропия, тем сильнее неопределенность и тем большую информацию в среднем несет одно сообщение источника.
•Сравнивая формулы (8) и (6) видим, что I = n∙H.
Свойства энтропии
1.Энтропия принимает значение, равное 0, только в случае детерминированного источника сообщений системы.
•Детерминированность источника означает, что один из возможных символов генерируется источником постоянно (с единичной вероятностью), а остальные – не производятся вовсе. Предположим для определенности, что генерируется k-й символ.
• |
Пусть P(ak)=1 , а P(ai)=0 для всех i=1,m i≠k |
•Тогда, обозначив элемент суммы в формуле (8) через hi, получим
hk P(ak )log2 P(ak ) 0
hi 0 log2 0 0 (?)
• Раскроем неопределенность вида 0∙∞ по правилу Лопиталя.
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
lim( x log2 x) lim x log |
|
1 |
lim |
log x |
|
1 |
z |
|
|
|
|
|
|
||||||||
2 |
|
|
|
|
|
|
|
||||||||||||||
x |
|
x |
|
|
|
|
|
||||||||||||||
x 0 |
|
|
x 0 |
|
x 0 |
1 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
lim |
log z |
lim |
(log2 z) |
|
|
(log2 z)' |
|
1 |
,log2 e |
1 |
|
lim |
log e |
0 |
|||||||
|
|
|
|||||||||||||||||||
z |
z' |
|
z ln 2 |
ln 2 |
|
z |
|||||||||||||||
z |
z |
|
|
|
|
|
|
|
|
|
|
|
z |
|
•Следовательно, для детерминированного источника hi= 0 для всех i. С другой стороны, если ни одна p(ai)≠1, то ни одно слагаемое hi не обращается в 0. Что и требовалось доказать.
2.Энтропия - величина неотрицательная и ограниченная.
•Если каждое слагаемое hi=-p(ai)log2p(ai) неотрицательно и ограниченно, то и их сумма также будет неотрицательна и ограниченна.
•Докажем неотрицательность:
•p(a) ≥ 0; p(a) ≤ 1 следовательно log p(a) ≤ 0 и (- p(a) log p(a)) ≥ 0.
•Докажем ограниченность, продифференцировав по p:
hi |
|
pi |
logpi pi |
logpi logpi pi |
1 |
logpi loge 0 |
|
pi ln 2 |
|||||||
pi |
|
pi |
|
pi |
|
•Следовательно, величина hi имеет экстремум (можно доказать, что это максимум), а значит это величина ограниченная (см. рис.2).
h
i
|
|
pi |
|
0 |
|
1/e |
|
|
|
||
|
1
Рис. 2. К свойству ограниченности энтропии.
3.Энтропия системы, имеющей m равновероятных состояний, максимальна и равна log2m.
•Докажем максимальность
•Пусть m=2, тогда p1+p2=1
•H = -p1∙logp1 - p2∙logp2 = -p1∙logp1-(1-p1)∙log(1-p1). Чтобы найти максимум энтропии, определим и приравняем нулю частную производную.
H |
logp1 loge (1 p1 ) log(1 |
p1 ) (1 p1 ) |
log(1 p1 ) |
|||
|
||||||
p1 |
|
p1 |
|
|
p1 |
|
logp1 |
loge log(1 |
p1 ) (1 p1 ) |
1 |
|
||
(1 p1 ) ln 2 |
||||||
logp1 |
loge log(1 |
p1 ) log e 0. |
|
|
•-log p1 + log(1-p1) = 0
•p1= ½ = p2