Материал: 6593
36
в мишень, которое подчинено биномиальному закону распреде-
ления p(X = m) = Cnm pm (1− p)n−m ,
|
|
Таблица 2.2.1 |
|
|
где Cnm = |
n! |
|
|
. |
|
|||||
|
|
|
|
m!(n − m)! |
|
||||||||||
|
m |
0 |
1 |
2 |
|
|
|
||||||||
|
|
|
|
|
|
|
|||||||||
|
p(x=m) |
1/4 |
1/2 |
1/4 |
|
|
|
Составляем |
ряд |
распре- |
|||||
|
|
|
|
Таблица 2.2.2 |
|
деления для числа попаданий |
|||||||||
|
|
|
|
|
в первую мишень при n=2 и |
||||||||||
|
m |
0 |
|
1 |
|
2 |
|
3 |
|
p=1/2 (табл. 2.2.1) и вторую |
|||||
|
p(x=m) |
8/27 |
|
4/9 |
|
2/9 |
|
1/27 |
|
мишень |
при |
n=3 |
и p=1/3 |
||
|
|
|
|
|
|
|
|
|
|
(табл. 2.2.2). |
|
|
|
|
|
|
Мерой неопределенности исхода стрельбы служит энтропия |
||||||||||||||
числа попаданий. Энтропия числа попаданий при стрельбе по первой мишени
|
n1 |
|
|
|
|
|
|
|
|
|
1 |
log2 |
1 |
+ |
1 |
log2 |
1 |
=1,5 áèò. |
|||||
H1(X ) = −∑p(xj )log p(xj ) = − 2 |
4 |
4 |
|
2 |
2 |
|
|||||||||||||||||
|
j=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Аналогично для второй мишени имеем |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
8 |
|
8 |
|
4 |
|
4 |
|
2 |
|
|
2 |
|
1 |
|
|
|
1 |
|
|
||
H2 |
(X ) = − |
|
log2 |
|
+ |
|
log2 |
|
+ |
|
log2 |
|
+ |
|
|
log2 |
|
|
|
=1,7 áèò, |
|||
27 |
27 |
9 |
9 |
9 |
9 |
27 |
27 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
т.е. исход стрельбы по второй мишени обладает большей неопределенностью.
Пример 2.2.3. Источник сообщений вырабатывает ан-
самбль символов |
|
|
|
|
|
|
|
X |
x |
x |
x |
x |
x |
x |
|
= 1 |
2 |
3 |
4 |
5 |
6 |
. |
|
|
0,4 |
0,2 |
0,15 |
0,1 |
0,1 |
0,05 |
|
Символы в последовательности независимы.
Вычислить энтропию источника и определить избыточность.
Решение. Энтропия источника для случая неравновероятных и независимых сообщений определяется формулой (2.2.1)
m
H (X ) = −∑p(xj )log p(xj ) = −[0,4 log 0,4 +0,2 log 0,2 +
j=1
0,15 log 0,15 + 2 0,1 log 0,1+0,05 log 0,05] = 2,2842 áèò.
Избыточность за счет неоптимальности (неравновероятно-
37
сти) распределения сообщений в источнике определяется
формулой (1.2.12) R =1− H
Hmax , где Hmax = log m по фор-
муле (2.2.3).
Отсюда R =1−2,2842
log 6 = 0,1164.
Пример 2.2.4. Алфавит источника состоит из трех букв:
х1, х2, х3.
|
Определить энтропию на 1 букву текста X (1) , X (2) |
для |
||||||||||
следующих случаев: |
|
|
|
|
|
|
|
p(x1) = 0,5 , |
||||
|
а) буквы |
алфавита |
неравновероятны: |
|||||||||
|
|
|
|
|
|
|
|
p(x2 ) = p(x3 ) = 0,25 , |
а |
|||
|
|
|
Таблица 2.2.3 |
символы в последовательно- |
||||||||
|
i – индекс |
|
j – индекс |
сти |
на выходе |
источника |
||||||
|
|
последующей |
статистически |
зависимы. |
||||||||
|
предыдущей |
|
||||||||||
|
|
|
буквы |
|
Условные |
|
вероятности |
|||||
|
буквы |
|
|
|
|
|||||||
|
|
1 |
|
2 |
|
3 |
p(xj |
(2) / xi |
(1) ) заданы в табл. |
|||
|
|
|
|
|
||||||||
|
1 |
|
0,4 |
|
0,2 |
|
0,4 |
|||||
|
|
|
|
2.2.3; |
|
|
|
|||||
|
2 |
|
0 |
|
0,6 |
|
0,4 |
|
|
|
||
|
|
|
|
б) вероятности букв те |
||||||||
|
3 |
|
0,3 |
|
0 |
|
0,7 |
|||||
|
|
|
|
же, что и в п. а), но символы |
||||||||
|
|
|
|
|
|
|
|
|||||
независимы; в) символы в последовательности независимы, вероятности
букв одинаковы.
Вычислить избыточность источников для случаев а) и б). Решение. а) В случае неравновероятных и зависимых со-
общений энтропия текста по формуле (2.2.9)
H (X (1) X (2) ) = H (X (1) ) + H (X (2) / X (1) ) ,
m
где H (X (1) ) = −∑p(xj )log p(xj ) =1,5 áèò,
j=1
аусловная энтропия по формуле (2.2.8) равна
|
|
3 |
3 |
|
|
|
|
|
|
|
H (X (2) |
/ |
X (1) ) = −∑ ∑p(xi |
(1) ) p(xj |
(2) / xi |
(1) )log p(xj |
(2) / xi |
(1) ) = |
|
||
|
|
i=1 |
j=1 |
|
|
|
|
|
|
|
−{p(x1(1) )[p(x1(2) / x1(1) )log p(x1(2) / x1(1) ) + p(x2 |
(2) / x1(1) )log |
p(x2 |
(2) / x1(1) ) + |
|||||||
38
p(x3(2) / x1(1) )log p(x3(2) / x1(1) )]+ p(x2 |
(1) )[p(x1(2) / x2 |
(1) )log p(x1(2) / x2 |
(1) ) + |
|||||||||||
p(x2 |
(2) / x2 |
(1) )log p(x2 |
(2) / x2 |
(1) ) + p(x3(2) / x2 |
(1) )log p(x3(2) / x2 |
(1) )]+ |
|
|||||||
+p(x3(1) )[p(x1(2) / x3(1) )log p(x1(2) / x3(1) ) + p(x2 |
(2) / x3(1) )log p(x2 |
(2) / x3(1) ) + |
||||||||||||
p(x3(2) / x3(1) )log p(x3(2) / x3(1) )]}= −{12[0, 4 log2 0, 4 +0, 2 log2 |
0, 2 + |
|||||||||||||
0, 4 log2 |
0, 4]+ 1[0 +0,6 log2 0,6 +0, 4 log2 0, 4]+ |
1[0,3 log |
2 |
0,3 |
+ |
|||||||||
|
|
|
4 |
|
|
|
|
|
|
4 |
|
|
|
|
0,7 log2 |
0,7]}≈1, 224 бит. |
|
|
|
|
|
|
|
|
|
||||
Энтропия на один символ
H1(X (1) , X (2) ) = H (X (1) ) + H (X (2) / X (1) ) 
2 =1,362 áèò
ñèì â.
б) При неравновероятных, но зависимых сообщениях энтропия вычисляется по формуле (2.2.1)
n |
1 |
|
1 |
|
|
1 |
|
1 |
|
áèò |
|
||
H (X ) = −∑p(xj )log p(xj ) = − |
|
log2 |
|
+ 2 |
|
|
log2 |
|
=1,5 |
|
. |
||
2 |
2 |
4 |
4 |
ñèì â |
|||||||||
j=1 |
|
|
|
|
|
|
|
||||||
Избыточность, обусловленная статистической зависимостью
R1 =1− H1(X )
H (X ) =1−1,362
1,5 = 0,092.
в) В случае равновероятных и независимых сообщений энтропия по формуле (2.2.3)
Hmax (X ) = log2 m = log2 3 =1,585 áèò.
Избыточность, обусловленная неоптимальностью распределения
R2 =1− H (X )
Hmax (X ) =1−1,5
1,585 = 0,054.
Полная избыточность (за счет неоптимальности распределения и наличия статистических взаимосвязей)
R =1− H1(X )
Hmax (X ) = 0,141.
ЗАДАЧИ
2.2.1. Алфавит русского языка состоит из 32 букв (если не различать е и ё, ь и ъ), включая промежуток между буквами. Вычислить энтропию однобуквенного текста, считая вероятности появления любой из букв в заданном месте текста одинако-
39
выми.
2.2.2. Источник вырабатывает ансамбль сообщений
X |
x |
x |
x |
x |
|
= 1 |
2 |
3 |
4 |
|
|
|
0,2 |
0,3 |
0,4 |
0,1 |
|
Символы в последовательности независимы. Вычислить энтропию источника и определить избыточность.
2.2.3. Найти число значений m равномерно распределенной случайной величины Y, при котором ее энтропия будет равна энтропии случайной величины X, заданной табл. 2.2.4
Таблица 2.2.4
xj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
р(xj |
1/2 |
1/4 |
1/8 |
1/16 |
1/32 |
1/ |
|
) |
|||||||
|
|
|
|
|
|
2.2.4. Производится стрельба по мишени. Сделано 2 выстрела. Вероятность попадания при одном выстреле Ѕ. Найти неопределенность исхода стрельбы (числа попаданий) по мишени.
2.2.5. Определить энтропию случайной величины X, распределенной по биномиальному закону:
а) в общем случае,
б) при p=q= 12 и m=3.
2.2.6. В двух урнах имеется по 15 шаров: в первой урне 5 красных, 7 белых и 3 черных; во второй соответственно 4, 4,7. Из каждой урны вынимается по одному шару. Сравнить неопределенности исхода опытов для двух урн.
2.2.7. Алфавит источника сообщений состоит из двух букв x1 и х2 с вероятностями 0,6 и 0,4. В последовательности на выходе источника символы статистически зависимы. Условные
вероятности переходов p(x |
(2) / x (1) ) заданы табл. 2.2.5 |
j |
i |
40
Таблица 2.2.5
i- индекс преды- |
j- индекс последующей буквы |
|
дущей буквы |
|
|
1 |
2 |
|
1 |
0,2 |
0,8 |
2 |
0,7 |
0,3 |
Определить энтропию на один символ текста. X (1) X (2) . Вычислить избыточность источника.
2.2.8. Выполнить задачу 2.2.7, если условные вероятности
переходов p(x (2) |
/ x (1) ) |
заданы табл. 2.2.6 |
|
|
||
j |
i |
|
|
|
|
|
Таблица 2.2.6 |
|
|
|
|
|
|
|
|
|
|
|
||
i – индекс предыду- |
j – индекс последующей буквы |
|||||
щей буквы |
|
1 |
2 |
|
3 |
4 |
1 |
|
0,0 |
0,2 |
|
0,4 |
0,4 |
2 |
|
0,2 |
0,2 |
|
0,3 |
0,3 |
3 |
|
0,25 |
0,0 |
|
0,25 |
0,5 |
4 |
|
0,2 |
0,4 |
|
0,4 |
0,0 |
Безусловные вероятности букв x1 …. x4 |
равны |
соответ- |
||||
ственно 0,5; 0,25; 0,125; 0,125. |
|
|
|
|
||
2.2.9.Символы азбуки Морзе могут появиться в сообщении
свероятностями: для точки — 0,51, для тире — 0,31, для промежутка между буквами — 0,12, между словами — 0,06. Определить среднее количество информации в сообщении из 500
символов данного алфавита, считая, что связь между последовательными символами отсутствует.
2.2.10. Система радиозонда измеряет давление. Барометр имеет 10 отметок шкалы, и его отсчеты могут изменяться до любого допустимого значения за 0,01 с. Связь между отсчетами отсутствует. Найти энтропию источника за 1 с, если показания барометра будут появляться со следующими вероятностями (табл. 2.2.7).
Таблица 2.2.7
Отметка |
0 |
1 |
2 |
3 |
4 |
5 |
|
шкалы |
|||||||
|
|
|
|
|
|