Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
P Ы = з/7; p (a2) = p (a,) = */7.
(б) H (U\s=l) = n/2 бит, Я (t/ | s = 2) = 1 бит, tf(t/|s = 3)=0 бит.
(B) Hoo(u) = sh бит.
(г) Для состояния 1: ах -> 0, а2 -> 10, a3 -> 11. Для состояния 2: ^ -*¦ 0, а2 -> 1; состоянию 3 не сопоставляется никакой кодовый символ. Для заданного начального состояния конец первого кодового слова можно установить, и это определит букву источника и, следовательно, следующее состояние и т. д.
(д) п равно 7 бит. Имеем п — Нх (U), если каждый код, относящийся к текущему состояню, имеет среднюю длину, равную энтропии данного текущего состояния. Поэтому п = Нх (U) тогда и только тогда, когда вероятности всех
букв имеют вид 2~п при некотором неотрицательном целом п.
3.23. (а). Последовательность состояний является стационарной последовательностью статистически независимых случайных величин, принимающих значения 1 и 2, и индексы букв источника совпадают с номерами состояний.
590
(б) н{ul I и^.., ulSl)=H{ul+l \ur..u2s2)=H{U[+ll ur..u2s2 ux sl} <
<Ii(Ul+1\Ul...UlS1).
Второе из указанных выше равенств является результатом того, что t/x и Sx статистически независимы от l/;+i при условии, что заданы [см. (2.3.13)]. Поэтому Н (Ui\Ui-i ...L/1S1) — неубывающая функция I и согласно теореме 3.5.1 Я (Ui | ?/;_! ...Uj) — невозрастающая функция I. Из (2.3.13) также следует, что
Н (Ui 11/г_! ... U1S1) < Н (Ui 11/г_! ... U{) при всех I.
Так как левая часть не убывает с ростом I, то
H(Ul\Ui-1...U1,iS1) < lim Я (<Уг It/,-, ... t/,) =Яоо (U).
/ - - ОО
Скорость сходимости можно оценить, если заметить, что 1 1 1
— HW.-U^SJ^— J //(t/г | t/i_!... t/i Sx) <H(Ui\Ui-1...U1S1).
1 1 г=1
Вместе с тем
HiUi...U1)-H(Ul...U1\S1) =/(Si; t/д... Ui) < H (S±) < log J,
где J является числом состояний. Объединяя эти соотношения и учитывая (3.5.3), получаем
H(Ul\Ui-1...Ul)-H(Ul\Ul-1...U1S1)
4.1. Пусть Qn (х) является совместным распределением вероятностей N входных символов канала. Для любого такого распределения имеем
I(XN; Уы) =H(\N) - H(\n\\n).
Заметим, что Н (Y^IX^) является математическим ожиданием величины
N
— log Я (у 1 х) = — 2 log Р (Уп I Хп) п— 1
и поэтому
N
H(\N\XN)= 2 H(Yn\Xn). п — 1
Из (2.3.10) также следует, что
H(\N) < 2
п= 1
Из этих соотношений получаем
N N
i{xN-,\N)< s ПХп.УпХ 3 °п- (2)
п= I п= I
Равенство в (1) имеет место, если входы являются статистически независимыми, и в (2), если, кроме того, входные вероятности выбираются так, чтобы достигалась пропускная способность отдельных каналов. Таким образом, пропускная способность параллельного соединения равна 2Сп.
591
4.3. Единственным неочевидным соотношением является последнее. Имеем
= 2 Рг (v 1 е) 2 Pr(«]t>e)log
о
и ^tv
Рг (и | ve)'
При любом выборе v последняя сумма является энтропией для алфавита М — 1 значений и, неравных v, и, таким образом, последняя сумма не более чем log (М — 1) для любого v. Суммируя по v, получаем
Если бы некоторая стратегия давала вероятность ошибки, большую чем 1 — е, то все решения при этой стратегии могли бы быть обращены, что привело бы к вероятности ошибки, меньшей чем е. На обычном языке студентов это означает, что также трудно дать все неправильные ответы при контрольном испытании по системе «да—нет», как дать все правильные ответы. Без кодирования <Ре> = s; это значит, что нельзя сделать ничего лучшего, чем просто передавать символы без изменения.
Н (и I Ve) < log (М - 1).
4.4. Применяя (4.3.22) к источнику и каналу этой задачи, получаем ^«Ре» > 1 —С = &6 (е).
Это означает, что
е < <Ре> < 1—е.
4.5. (а) <Ре> log З+^f «Ре» > 2—Ct.
(1)
(0) /¦«!*>-( '/3 "р" 1 * ”¦
(, 1 — Е ПрИ ] = k,
где е < 3/4 удовлетворяет равенству е log Ъ-\-&? (е) = 2 — С*.
(в) <Ре> log (М—(<Ре>) > 1.
log (М— 1) > М> Н-2(10,-2°).
4.6. Первые два соотношения, содержащиеся в доказательстве, получаются непосредственно. Далее
l(UXn-, K„|K1...K„_1) = /(^n; Yn\Yi--Yn-i) +
+ /(U; Yn\XnYj ...Fn-i).
В ДКБП, однако, выход канала в любой момент времени зависит только от входа в этот момент, что дает
Р(Уп\хп,У1.....уп-1,и) = Р (уп\хп). (1)
