Материал: 6593
31
необходимы 12 градаций (уровней) яркости. Предполагается, что, все уровни яркости встречаются с одинаковой вероятностью. Элементы изображения независимы. Какое количество информации надо передать по каналу связи, если передача продолжается 5 мин?
2.1.11. По дискретному каналу передается одно из сообщений x1, х2, x3. Вследствие действия шумов на выходе канала появляется сигнал y1 или y2. Вероятности совместного появления заданы табл. 2.1.3
Таблица 2.1.3
|
|
Вычислить взаимные информации I(х1; |
x |
yk |
у2), I(x3; y1 ), I(x2; у2). |
jy y передаются сообщения x1, х2, х3 с вероятно-
12
x0 0 стями 0,2; 0,3; 0,5. На выходе канала пр о-2.1.12. По двоичному каналу с шумом
1 |
|
,4 |
|
,1 |
|
являются сигналы y1, y2, y3. Вероятности ис- |
||
|
|
|
|
|
|
|
кажения в канале (условные вероятности |
|
|
x |
0 |
0 |
|||||
2 |
переходов): |
|
||||||
|
,2 |
|
,15 |
|
p(y1 / x1) = 3 4; p (y1 / x2 )=1 8; p (y1 |
/ x3 )=1 8; |
||
|
x |
0 |
0 |
|
||||
3 |
|
,1 |
|
,05 |
|
|
|
|
|
p (y2 / x1 )=1 |
8; p (y2 / x2 )= 3 4; p (y2 / x3 )=1 8; |
|
|||||
|
p (y3 / x1 )=1 8; p (y3 / x2 )=1 8; p (y3 / x3 )= 3 4. |
|
||||||
|
Найти взаимные информации I ( x1;y3), I(x3;y1). |
|
||||||
|
2.1.13. По двоичному каналу с помехами передаются рав- |
|||||||
новероятные и статистически независимые сообщения x1 |
и |
|||||||
x2. |
В результате действия помех они преобразуются в сигналы |
|||||||
у1, у2, у3. Условные вероятности переходов p(yk/xj) заданы |
||||||||
табл. |
2.1.4. |
|
Вычислить взаимные информации I(x1 ;у3) |
и |
||||
I(x2;y2). |
|
|
|
|
|
|||
|
Таблица 2.1.4 |
|
|
|||||
|
|
|
yk |
|
|
|
|
|
j |
1 |
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|||
1 |
/8 |
|
/8 |
|
/8 |
|
|
|
|
|
|
|
|
|
|
|
|
32
2 |
/8 |
/8 |
/8 |
2.1.14. Рассматривается ансамбль сообщений X, приведенный в табл. 2.1.5.
Таблица 2.1.5
xj |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
р(xj) |
1/4 |
1/4 |
1/8 |
1/8 |
1/1 |
1/1 |
1/1 |
1/1 |
|
6 |
6 |
6 |
6 |
||||||
|
|
|
|
|
|||||
Кодовое |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
|
слово |
|||||||||
Сообщение |
х2 |
поступает |
в кодер. Вычислить |
дополнитель- |
|||||
ную информацию об этом сообщении, доставляемую каждым последующим символом на выходе кодера.
2.1.15. Сообщения источника x1,...,х4 для согласования с каналом кодируются в соответствии с табл. 2.1.6.
Таблица 2.1.6
Сообщения xj |
x1 |
x2 |
x3 |
x4 |
р(xj) |
1/2 |
1/4 |
1/8 |
1/8 |
Кодовое слово |
000 |
011 |
101 |
100 |
Пусть на вход кодера поступает сообщение х3. Вычислить дополнительную информацию об этом сообщении, которую содержит каждый последующий символ на выходе кодера.
2.1.16. Среди студенток некоторого института 25% всех девушек – блондинки, а 75% всех блондинок имеют голубые глаза; всего же голубые глаза имеет половина всех девушек. Пусть мы знаем, что некоторая студентка имеет голубые глаза. Сколько дополнительной информации будет содержаться в сообщении о том, что эта девушка – блондинка?
2.2 Средняя собственная информация (энтропия)
Энтропия. Дискретный источник удобнее характеризовать количеством собственной информации, содержащимся в среднем в одном символе ансамбля X.
Это среднее количество собственной информации есть
|
33 |
|
|
|
|
|
|
|
|
|
|
I (X )= M |
−log p (X ) = |
n |
I |
( |
x |
j ) |
p |
( |
x |
j ) |
= |
|
|
∑ |
|
|
|
|
(2.2.1) |
||||
|
|
j=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
−∑p(xj )log p(xj |
) = H |
(X ) |
|
|
|
|
|
||||
j=1
иназвано энтропией (по аналогии с понятием энтропии в термодинамике).
Свойства энтропии.
1)Энтропия неотрицательна
H (X ) ≥ 0. |
(2.2.2) |
Знак равенства имеет место, когдаX – неслучайна, т.е. p(xj) = 1, a p(xi) = 0 для i ≠ j. При этом неопределенность относительно ан-
самбля X отсутствует. Таким образом, энтропия есть мера неопределенности случайного ансамбля.
2) Величина энтропии удовлетворяет неравенству
H (X ) ≤ log n. |
(2.2.3) |
Знак равенства имеет место при равновероятности символов ансамбля X, т.е. при p(xj ) =1
n.
3) Свойство аддитивности энтропии.
В последовательности i независимых символов энтропия равна сумме энтропий, содержащихся в отдельных символах
|
(1) |
,..., X |
(i) |
(1) |
) +...+ H (X |
(i) |
). |
(2.2.4) |
H X |
|
= H (X |
|
|
|
|||
Вычисление энтропии по формуле (2.2.1) можно упростить, |
||||||||
введя функцию η( p) = −log p, тогда формула примет вид |
|
|||||||
|
|
|
n |
|
|
|
|
|
|
|
H (X ) = ∑η( pj ). |
|
|
(2.2.5) |
|||
j=1
Значения функции η( p) приведены в Приложении 1.
Условная энтропия. Пусть имеются два статистически зависимых конечных ансамбля символов X и Y. Пары символовxjyk c вероятностями p(xj, уk) можно рассматривать как элементарные символыобъединенного ансамбляXY с энтропией
n |
m |
|
H (XY ) = −∑ ∑p(xj, yk )log p(xj, yk ). |
(2.2.6) |
|
j=1 |
k =1 |
|
34
Появление символа xj вызовет появление символа yk с условной вероятностью
p(yk / xj ) = p(xj, yk ) . p(xj )
При этом условная энтропия ансамбля Y в предположении, что выбран символ хj, будет
H (Y / xj ) = M −log p(Y / xj ) =
m |
(2.2.7) |
|
∑p(yk / xj )log p(yk / xj ). |
||
|
k =1
Здесь каждому хj соответствует свое значение энтропии H (Y / xj ) , т.е. H (Y / xj ) - случайная величина.
Тогда средняя условная энтропия случайной величины Y, вычисленная при условии, что известно значение другой случайной величины X, равна
H (Y / X ) = M[ |
n |
|
−log p(Y / X )]= ∑p(xj )H (Y / xj ) = |
(2.2.8) |
|
|
j=1 |
|
|
|
|
n |
m |
|
−∑p(xj )∑p(yk / xj )log p(yk / xj ). |
|
|
j=1 |
k =1 |
|
Энтропия объединенного ансамбля H (XY ) удовлетворяет |
||
следующим соотношениям: |
(2.2.9) |
|
а) H (XY ) = H (X ) + H (Y / X ) = H (Y ) + H (X /Y ), |
||
если X и Y зависимы; |
(2.2.10) |
|
в) |
H (XY ) = H (X ) + H (Y ), |
|
если X и Y независимы.
Для объединенного ансамбля XY условная энтропия удовлетворяет неравенствам:
H (Y / X ) ≤ H (Y ), H (X /Y ) ≤ H (X ). |
(2.2.11) |
Избыточность. Считают, что имеется избыточность, если количество информации, содержащейся в сигнале (энтропия сигнала), меньше того количества, которое этот сигнал мог бы содержать по своей физической природе. Введем количественную меру избыточности. Пусть сигнал длиной в n символов (от-
35
счетов) содержит количество информации Н. Пусть далее наибольшее количество информации, которое в принципе может содержаться в данном сигнале с учетом наложенных на него ограничений (заданное основание кода, заданная средняя мощность сигнала и т.п.), равно Hmax. Тогда количественной мерой избыточности является величина
R =1− H Hmax . |
(2.2.12) |
Причины появления избыточности – это статистическая связь между символами (отсчетами) сигнала и неэкстремальность распределения вероятностей отдельных символов (отсчетов). Введение избыточности приводит к удлинению сигнала, но зато повышает его информационную устойчивость при воздействии помех.
РЕШЕНИЕ ТИПОВЫХ ПРИМЕРОВ Пример 2.2.1. На измерительной станции имеются два при-
бора. Первый имеет шкалу, содержащую 100 делений, его показания могут меняться через каждые 0,05 с. Шкала второго прибора имеет 10 делений, и его показания могут меняться каждые
0,01 с.
Какова наибольшая средняя информация, поставляемая двумя приборами в 1 с?
Решение. 1-й прибор. Энтропия одного значения (отсчета)
по формуле (2.2.3) H1(X ) = log m1 = log 100.
Число отсчетов в 1 секунду равно n1 =1
0,05 = 20.
2-й прибор. Энтропия одного значения H2 (X ) = log 10 , а число отсчетов в 1 секунду равно n2 =100.
Энтропия двух приборов в 1 с по формуле (2.2.4.) равна
HΣ (X ) = n1H1(X ) + n2 H2 (X ) = 20 6,64 +100 3,32 ≈ 465 áèò/ñ.
Пример 2.2.2. Производится стрельба по двум мишеням, по одной сделано 2 выстрела, по второй – 3. Вероятности попадания при одном выстреле соответственно равны 1/2 и 1/3. Исход стрельбы (число попаданий) по какой мишени является более определенным?
Решение. Исход стрельбы определяется числом попаданий