Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Сейчас мы исследуем энтропию марковского источника. Энтропия выходной буквы источника в заданный момент времени при условии, что задано текущее состояние источника, равна
Н (t/|s ==/)=— S Pj(ah)\ogPj(ah). (3.6.9)
k=\
Затем найдем энтропию выхода источника при условии, что задано некоторое частное состояние в некоторый момент в прошлом и заданы промежуточные выходы источника.
83
Лемма.
H(Ul\Ul^Ul^...U1, s^-j) =
J
— 2 Pf (S; = i I s1 — /) H (U | s = i). (3.6.10)
i = I
Доказательство. По определению марковского источника состояние s2 в момент 2 однозначно определяется sx и и1г т. е. предыдущим состоянием и выходной буквой. Подобно этому s3 однозначно определяется s2 и и2 и, следовательно, определяется с помощью и2, иг и sx. Продолжая по индукции, находим, что для любого положительного I состояние S; однозначно определяется иъ ..., и Следовательно,
Рг («г | «j,..., щ_х, sa) Pr (щ | st, ии..., «ц, Sj),
где s; является состоянием, определяемым иъ ..., t^_i и Sj. Так как «г зависит только от s; [см. (3.6.4)], то отсюда получаем
Рг{щ\иъ ..., Sj) =- РГ (М; ] S;). (3.6.11)
Логарифмируя обе части равенства (3.6.11) и усредняя по иъ ..., ut nsb будем иметь
2 РГ(Ы1( ... , Щ, S[ | Sj) log Pr (ll[ | Uj, ..., !iw, Sx)=--=
,... ,u^,s^
= 2 PrK, ... , «/_!, sJs^Pr^ls^logPr^ls,).
"l....u/’si
Суммируя правую часть равенства по иъ ..., «/_ь получаем
(3.6.10). |
Отметим, что доказательство этой леммы существенно опирается на предположение, что состояние источника определяется предыдущим состоянием и выходной буквой. Вычисления левой части (3.6.10) для источников, не удовлетворяющих этому условию, крайне искусственны и сложны*’.
Любое заданное распределение вероятностей для состояния определяет распределение вероятности состояний во все будущие моменты времени, поэтому можно усреднить (3.6.9) по sx и получить
j
Н (Ut I и,_! ... Ur Sj) = ^ Pr (s, = i) H(U\s ^ i). (3.6.12)
i— 1
Для стационарного эргодического марковского источника Pr (si = i) не зависит от I и из (3.6.8) имеем
Н (Ul | U-_!... U1Si) = 2 9(0 Н (U | s = 0 для всех 1^1. (3.6.13)
*> Блекуэлл (1957) рассмотрел эту задачу в пределе при I -» оо и показал, что она может быть сведена к решению трудного интегрального уравнения.
84
Рассмотрим теперь энтропию на букву последовательности букв источника при условии, что задано начальное состояние
= 4 У (3.6.14)
1 = 1
Отсюда согласно (3.6.12) имеем
, J
-l-H(U1...UL\S1) = 2 q{l,L)(i)H(U\s = i), (3.6.15)
L i = 1
где i J-
W)(i) = 7- 2 Pr (*' = *¦). (3-6.16)
z=i
Отсюда видно, что <?(1,ц(0 в точности равна средней по времени вероятности пребывания в состоянии i. Для стационарного эргодического марковского источника q(i, i)(i) совпадают с q (i), как показывают
(3.6.5) и (3.6.6), и поэтому
, J
— Я(г/Х ... f/z. i Sj) = 2 q(i)H{U\s = i). (3.6.17)
L i= l
В пределе при L ->¦ оо определим
<7 (0 = 1^4- У Pr («1 = 0- (3.6.18)
Этот предел всегда существует, хотя вообще он зависит от распределения вероятностей для Sj. Так, например, на рис. 3.6.1 это отличие становится ясным, когда sx задается как состояние 2 с вероятностью 1 или как состояние 4 с вероятностью 1. Вместе с тем для цепи Маркова, имеющей только одно неразложимое множество состояний, <7о, «)(!’) не зависят от начального распределения вероятностей. При этом определении <7d, оо)(0 получаем
\\m~H{Ux ... UL\S1)=-- 2 q (i) Н (U \s = i). (3.6.19)
> oo L 1=1 ' • '
Рассмотрим далее безусловную энтропию на букву последовательности источника. Имеем
Н (U1... UL) == / (5]j Ui ... UL)-\- H (Ux... UL j 5,).
Средняя взаимная информация в правой части приведенного выше выражения ограничена 0 и log У и, следовательно,
\im—H(U1...UL)^Um — H(U1...UL\S1). (3.6.20)
L-УОО L L-VOO L
Обозначая левую часть (3.6.20) через Hx (U), получаем в силу (3.6.19), что
HdU)^- 2 <?(1 OB)(i)H(U\s = i). (3.6.21)
1 = 1
