vopros-otvet (519806), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

p_i(t) = p_i(t + Δt) = p_i(t + n · Δt) = const = p(i).

Таким образом дискретный источник характеризуется тремя факторами:

• алфавитом {x_i}, где 1 ≤ i ≤ M;

• количеством состояний S( j); j = 1; k;

• столбцами вероятностей ||p_i(S_j)||; i = 1; M появления i-той буквы в j-том состоянии.

В 1928 году Хартли предложил меру для измерения информации дискретных сообщений:

I = log N,

где I – количество полученной информации, а N – количество возможных исходов или различных сообщений, которое может быть получено от источника дискретных сообщений с алфавитом в M букв при длине сообщения в n букв.

Рассмотрим эту меру подробнее.

Если получили одно элементарное сообщение – x_i, а оно выбрано из алфавита в M букв, то получено I = log M единиц информации. Поскольку в данной мере не учитывается ни в каком состоянии находился источник, ни какова вероятность появления каждой буквы, то считается, что имеет место элементарный источник с одинаковой вероятностью употребления различных букв алфавита p_i = ¹⁄_M = p_j, когда i ≠ j. Это очень сильные ограничения, которые значительно завышают истинное значение информации в сообщении.

С другой стороны у этой меры есть положительные моменты:

• она пропорциональна длине сообщения, так как если составлено сообщение длиной в n букв, то общее число различных сообщений из n букв будет равно N = M ⁿ и следовательно I_n = n log M;

• предложенная мера аддитивна, то есть если имеет место сообщение, полученное путем одновременного наступления нескольких событий от разных источников, то количество полученной при этом информации будет равно сумме информаций, полученных от каждого из них независимо друг от друга. Например, есть два источника Q₁ и Q₂ со своими алфавитами {x_i}, где 1 ≤ i ≤ M₁ и {y_j}, где 1 ≤ j ≤ M₂. Наступило событие: (x_i; y_j). Какое при этом получено количество информации? Так как общее число возможных исходов N в этом случае равно (M₁·M₂), то I = log N = log(M₁·M₂) = log M₁ + log M₂.

Основание логарифма можно принять различным. Это не принципиально, так как полученные меры будут отличаться только числовым коэффициентом. Но этим мерам даны различные названия:

log_a M = lg 10 = 1[дит];

log_a M = ln e = 1[нит(нат)];

log_a M = log₂ 2 = 1[бит];

1[дит] = 1 ⁄ lg 2 = 1 ⁄ 0.301 = 3.322[бит].

4. Измерение информации по Шеннону.

Необходимо было устранить основной недостаток меры Хартли – учесть вероятности появления букв в каждый момент времени в каждом состоянии.

Определим количество полученной информации от факта появления какой-либо буквы x_i источника, находящегося в состоянии S_j, как

I_i (S_j ) = –log p_i(S_j),

где p_i(S_j) – вероятность появления i-той буквы, если источник находится в состоянии S_j.

При таком определении количества полученной информации от факта получения i-той буквы видно, что количество информации, создаваемое каждой буквой, различно. Принято источник в целом по всему алфавиту в одном из состояний характеризовать средним значением количества информации, приходящемся на одну букву:

.

А количество информации, приходящееся на одну букву, вырабатываемую источником, по всем его состояниям определим путем усреднения:

,

где P(S_j) – вероятность нахождения источника в состоянии S_j.

Информация связана со снятием неопределенности. Пока мы предполагали, что в результате опыта наступает вполне определенное событие, то есть однозначно выбирается та или иная буква или знак. Но это не всегда так. В результате опыта или получения дополнительных сведений неопределенность ситуации изменяется, но не становится однозначной, то есть сохраняется апостериорная неопределенность. В этом случае количество полученной информации можно определить как разницу неопределенностей до и после эксперимента, то есть:

I_экспер = H_апр – H_апост,

где – априорная неопределенность источника; когда неизвестно, что будет передаваться;

H_апост – апостериорная неопределенность источника, то есть неопределенность, которая остается на приемной стороне, когда известно, что передавалось.

Формула для подсчета H_апост та же, что и для H_апр, только вероятности p_i(S_j) другие и определяются ошибками в передаче букв или знаков по каналу связи.

Если после эксперимента неопределенность исчезает (передача информации по линии связи идет без ошибок), то есть однозначно известна переданная буква сообщения, то H_апост = 0 и I = H_апр, то есть полученная информация равна устранению априорной неопределенности.

Единицы измерения информации по Шеннону те же, что и по Хартли.

Рассмотрим примеры подсчета информации и неопределенности (энтропии) ситуаций по Шеннону.

Пример 1

Рассчитаем энтропию двоичного источника при различных вероятностях появления его символов. Источник элементарный, то есть j = 1.

а)

Таблица 2.1

xi	0	1
p(xi)	0.5	0.5

.

б)

Таблица 2.2

xi	0	1
p(xi)	0.01	0.99

H(x) = –0.01log 0.01 – 0.99log 0.99 = –0.01·(–6.644) – 0.99 · (–0.0145) = 0.0808.

в)

Таблица 2.3

xi	0	1
p(xi)	0	1

.

Так как –log p(0) при p(0) ® 0 стремится к ∞, то имеет место неопределенность типа (0 · ∞), которая раскрывается как неопределенность дроби:

Из расчетов видно, что максимальная энтропия у источника с равными вероятностями выдачи символов p(0) = p(1) = 0.5. Неопределенность равна нулю, если вероятность одного из символов равна 1, а всех остальных – нулю.

5. Свойства информации по Шеннону.

1. Энтропия дискретного источника всегда положительна. Это определяется способом ее подсчета.

,

где 0 ≤ p(x_i) ≤ 1 – положительное число;

0 ≤ [–log p(x_i)] ≤ ∞ – положительное число;

0 ≤ –p(x_i)log p(x_i) ≤ 0.531 – положительное число;

H(x) – сумма положительных чисел.

Рис. 2.2

Энтропия равна нулю только в том случае, когда вероятность появления одной из букв источника равна 1, а всех остальных – нулю.

2. Можно доказать, что максимум энтропии достигается при равных вероятностях появления букв алфавита, то есть

.

Покажем это на примере источника из двух букв.

Таблица 2.5

Буквы	x1	x2
Вероятности их появления	p	q = 1 – p

H(x) = –plog p – qlog q = –plog p – (1 – p)log(1 – p),

где H(x), будет максимально, когда H '(x), то есть

,

откуда следует, что –log p + log(1 – p) = 0; и p = 0.5 = q.

Максимум H(x) равен в данном случае 1 или H_max(x) = log M.

3. Если в системе событие x_k состоит из двух событий x'_k и x"_k с вероятностями q₁ и q₂ (q₁ + q₂ = p_k), то общая энтропия системы будет равна сумме энтропий исходной системы и энтропии разветвленной части с весом p_k и условными вероятностями ветвления ^q₁ ⁄_pk и ^q₂ ⁄_pk , то есть H{x₁; x₂; ... x_k-1; x'_k; x"_k} = H{x₁; x₂; ... x_k-1; x_k} + p_kH(x'_k; x"_k).

Покажем это на примере.

Пусть имеется система с двумя состояниями.

Таблица 2.6

xi	x1	x2
p(xi)	0.5	0.5

H(x₁; x₂) = (–0.5log 0.5) · 2 = 1 бит.

Пусть состояние x₂ разбилось на два.

Таблица 2.7

xi	x'2	x"2
p(xi)	0.4	0.1

бита.

Энтропию новой системы можно подсчитать двумя способами:

1.

Таблица 2.8

xi	x1	x'2	x"2
p(xi)	0.5	0.4	0.1

H_сист = –0.5log 0.5 – 0.4log 0.4 – 0.1log 0.1 = 0.5 + 0.529 + 0.332 = 1.361 бита.

2. H_сист = H(x₁; x₂) + p(x₂) · H(x'₁; x"₂) = 1 + 0.5 · 0.722 = 1.361 бита.

Как видим, ответ получился один и тот же, но при втором способе расчета не нужно пересчитывать всю систему, а только к старой энтропии добавить энтропию разветвления.

Характеристики

Список файлов ответов (шпаргалок)